Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Предикаты

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«…»

Факультет _______________________________________________

Кафедра _________________________________________________

РЕФЕРАТ

по дисциплине_______________

на тему: «Предикаты»

Автор работы: ________________ _______________

(ФИО) (подпись)

Преподаватель ________________ _____________

(ученая степень, звание, ФИО) (подпись)

Дата сдачи:

«____»______________2014 г. Дата защиты:

«____»_____________2014 г. Оценка: __________________

2014

Оглавление

Введение……………………………….…………………………….……........…….3

Основная часть. Предикаты: определения и примеры............................…....5

Заключение……………………………………..............................................….…12

Список используемых источников………………………………………..…......13

Введение

В чем состоит необходимость введения предикатов в математику?

Дело в том, что сама по себе логика высказываний обладает довольно слабыми выразительными возможностями. Пользуясь только логикой, нельзя выразить даже очень простые, с математической точки зрения, рассуждения.

Возьмем, например, следующее умозаключение. «Всякое целое число является рациональным. Число 5 – целое. Следовательно , 5 – рациональное число ». Все эти три утверждения с точки зрения логики высказываний являются атомарными. Т.е. только средствами логики высказываний нельзя вскрыть внутреннюю структуру и поэтому нельзя доказать логичность этого рассуждения в рамках логики высказываний. Средства, предоставляемые логикой высказываний, оказываются недостаточными для анализа многих математических рассуждений. В алгебре логики не рассматриваются ни структура высказываний, ни тем более, их содержание. В то же время и в науке, и в практике используются заключения, существенным образом зависящие как от структуры, так и от содержания используемых в них высказываний.

Например , в рассуждении « Всякий ромб – параллелограмм ; ABCD – ромб ; следовательно , ABCD – параллелограмм» посылки и заключение являются элементарными высказываниями логики высказываний , и с точки зрения этой логики рассматриваются как целые, неделимые, без учёта их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.

Поэтому возникает необходимость в расширении логики высказываний и построении такой логической системы, средствами которой можно исследовать структуру и содержание тех высказываний, которые в логике высказываний рассматриваются как элементарные.

В силу изложенного материала, можно заключить, что актуальность данной работы несомненна.

Цель данного реферата заключается в том, чтобы совершить обзор

литературных источников по проблеме предикатов в дискретной математике.

Для достижения поставленной цели необходимо решить следующие задачи:

найти нужную информацию о предикатах по данной теме;
тщательно проанализировать и выбрать нужные данные;
оформить реферат согласно требованиям.

Объектом исследования является архив материалов по математическим предикатам.

Предметом исследования являются предикаты в дискретной математике.

Реферат состоит из введения, основной части, заключения и списка использованной литературы.

Основная часть.

Предикаты: определения и примеры

Введем основное понятие темы.

Определение 1. Пусть М – непустое множество. Тогда n-местным предикатом, заданным на М, называется выражение, содержащее n переменных и обращающееся в высказывание при замене этих переменных элементами множества М[1].

Поясним конкретными примерами. Пусть М есть множество натуральных чисел N. Тогда, например, такие выражения: «x – простое число», «x – четное число», «x больше 10» являются одноместными предикатами. При подстановке вместо x произвольных натуральных чисел получаются высказывания: «2 – простое число», «6 – простое число», «3 – четное число», «5 больше 10» и т.д.[2]

Множество M, на котором задан предикат, называется областью определения предиката[3].

Множество , на котором предикат принимает только истинные значения, называется областью истинности предиката Р(х)[3].

Так, предикат P(x) – «х – простое число» определён на множестве N, а множество для него есть множество всех простых чисел.

Вот такие выражения: « x больше y », « x делит y нацело », « x плюс y равно 10, или x+y=10 » являются двухместными предикатами. Примеры трехместных предикатов, заданных на множестве натуральных чисел: « число z лежит между x и y », « x плюс y равно z », « |x-y| = z »[4].

Обычно полагают, что, если имеется такой предикат, в котором нет переменных для замены, то подобное высказывание – нульместный предикат[1].

Причем местность предикатов не всегда равна числу всех переменных, содержащихся в выражении.

Например, выражение « существует число x такое, что y = 2 x » на множестве натуральных чисел определяет одноместный предикат.,

По смыслу этого выражения, в нем можно заменять только переменную y. Например: если применить замену y на 6, то получим истинное высказывание: « существует число x такое, что 6 = 2x », а если заменим y на 7, то получим ложное ( на множестве N ) высказывание: « существует число x такое, что 7 =2x ».

Предикат с заменяемыми переменными x1,…,xn обычно обозначается заглавной латинской буквой, после которой в скобках указываются эти переменные. Например, P( x1,x2 ), Q( x2,x3 ), R( x1 ). Среди переменных в скобках могут быть и фиктивные[2].

Определение 2. Предикат ( n-местный, или n-арный ) – это функция с областью значений ( или « Истина » и « Ложь » ), определённая на n-й декартовой степени множества M. Таким образом, каждую n-ку элементов M предикат характеризует либо как «истинную», либо как «ложную»[5].

Предикат можно связать с математическим отношением: если n-ка принадлежит отношению, то предикат будет возвращать на ней 1 [3].

Предикат – один из элементов логики первого и высших порядков. Начиная с логики второго порядка, в формулах можно ставить кванторы по предикатам [3].

Предикат называют тождественно – истинным [2] и пишут:

если на любом наборе аргументов он принимает значение 1.

Предикат называют тождественно – ложным [2] и пишут:

если на любом наборе аргументов он принимает значение 0.

Предикат называют выполнимым, если хотя бы на одном наборе аргументов он принимает значение 1 [5].

Например, обозначим предикатом EQ ( x, y ) отношение равенства ( « x = y » ), где x и y принадлежат множеству вещественных чисел. В этом случае предикат EQ будет принимать истинное значение для всех чисел, равных x и y.

Более житейским примером может служить предикат « ПРОЖИВАЕТ ( x, y, z ) » для отношения « x проживает в городе y на улице z » или предикат « ЛЮБИТ ( x, y ) » для выражения « x любит y», где множество M – это множество всех людей.

Так как предикаты принимают только два значения, то к ним применимы все операции булевой алгебры, например: отрицание, импликация, конъюнкция, дизъюнкция и т. д. Итак, на совокупности всех предикатов, заданных на множестве М, вводятся знакомые логические операции: конъюнкция, дизъюнкция, отрицание, импликация и эквиваленция. Эти операции вводятся довольно очевидным образом. Приведем в качестве примера определение конъюнкции предикатов.

Определение 3. Предикат W ( x1,…,xn ) называется конъюнкцией предикатов U ( x1,…,xn ) и V ( x1,…,xn ), заданных на множестве М, если для любых а1,…,аn из М высказывание W ( а1,…,аn ) есть конъюнкция высказываний U ( а1,…,аn ) и V ( а1,…,аn ) [2].

Аналогично приводятся определения и других упомянутых выше операций.

В логике предикатов первого порядка вводятся и две новые операции. Называются они квантором общности и квантором существования [1]. Эти операции рассмотрим сначала на примерах.

Пусть дано выражение: « существует число х, такое, что x + y=10 ». На множестве натуральных чисел это предложение определяет одноместный предикат P (y), так, например, Р (2) и Р (9) – истинные высказывания, а Р(11) – ложное. Если обозначить предикат « x + y = 10 » через S( x,y ) ( а это предикат двухместный ), то P (y) можно записать так: « существует х такой, что S( x,y ) ». В этом случае говорят, что предикат P(y) получен из предиката S (x,y) навешиванием квантора существования на x и пишут P (y) = ( $x ) S ( x,y )

Рассмотрим другой пример. Выражение « для всех х справедливо, что y = -х2 » определяет на множестве целых чисел одноместный предикат Q (y). Если предикат « y = -х2 » обозначить через T (x,y), то Q(y) можно записать так: «для всех x справедливо T (x,y) ». В таком случае говорят, что предикат Q (y) получен из предиката T (x,y) навешиванием квантора общности на х и пишут Q (y) = ("x) T (x,y).

Пользуясь этими примерами, дадим определение в общем виде.

Определение 4. Пусть P (x1,…,xn) – предикат, заданный на множестве M, y – переменная. Тогда выражение: « для всякого y выполняется P(x1,…,xn) » – предикат, полученный из P навешиванием квантора общности на переменную y, а выражение « существует y такой, что выполняется P (x1,…,xn) » – предикат, полученный из P навешиванием квантора существования на переменную y[1].

Заметим, что в определении не требуется, чтобы y была одна из переменных x1,…,xn, хотя в содержательных примерах, квантор навешивается на одну из переменных x1,…,xn. Указанное требование не накладывается, чтобы избежать усложнения определения формулы логики предикатов. Если y – одна из переменных x1,…,xn, то после навешивания квантора на y новый предикат является ( n-1 ) - местным, если y{ x1,…,xn}, то местность нового предиката равна n[3].

Если предикат W ( x1,…,xn ) получен из предикатов U ( x1,…,xn ) и V ( x1,…,xn ) с помощью связок, то истинность высказывания W ( a1,…,an ) определяется таблицами истинности этих связок[3]. Пусть W ( x1,…,xn ) = ( "y ) U ( x1,…,xn,y ). Тогда высказывание W ( a1,…,an ) истинно тогда и только тогда, когда для любого b M истинно высказывание U ( a1,…,an,b ). Если же W ( x1,…,xn ) = ( $y ) U ( x1,…,xn,y ), то высказывание W ( a1,…,an ) истинно в том и только в том случае, когда найдется b M, для которого высказывание U ( a1,…,an ) истинно[4].

Вообще понятие предиката – весьма широкое понятие[1]. Это видно уже из приведенных выше римеров. Тем не менее, еще раз подчеркнем, показав, что n - местная функция может рассматриваться как ( n+1 ) - местный предикат. Действительно, функции y = f ( x1,…,xn ), заданной на множестве М, можно поставить в соответствие выражение « y равно f ( x1,…,xn ) ». Это выражение есть некоторый предикат P ( x1,…,xn,y ) . При этом, если элемент b есть значение функции в точке ( a1,…,an ), то высказывание P ( a1,…,an,b ) истинно, и обратно. ( Подобное «превращение» функции в предикат мы уже привели в качестве примера выше для сложения натуральных чисел.)

На предикаты можно взглянуть и более формально, причем с двух точек зрения.

Во-первых, предикат можно представить отношением следующим образом.

Пусть предикат P( x1,…,xn ) задан на множестве M. Рассмотрим прямую степень этого множества Mn = Mx Mx…xM и подмножество Dp множества Mn, определяемое равенством:

Dp = { ( a1,…,an ) Mn высказывание P( a1,…,an ) истинно}.

Отношение Dp можно назвать областью истинности предиката P. Во многих случаях предикат P можно отождествить с отношением Dp.

При этом, правда, возникают некоторые трудности при определении операций над отношениями, аналогичными операциям над предикатами[4].

Во-вторых, предикат P ( x1,…,xn ), заданный на M, можно отождествить с функцией fp:Mn {0,1}, определяемой равенством:

Говорят, что предикат Р (х) является следствием предиката Q (х)[5]:

если

;

и предикаты Р (х) и Q (х) равносильны:

если

Приведём примеры к изложенному материалу.

Пример 1. Среди с ледующих предложений выделить предикаты и для каждого из них указать область истинности, если M = R для одноместных предикатов и M = R×R для двухместных предикатов[1]:

1. х + 5 = 1

2. При х = 2 выполняется равенство х2 – 1 = 0

3. х2 – 2х + 1 = 0

4. Существует такое число х, что х3 – 2

5. х + 2 < Зх – 4

6. Однозначное неотрицательное число х кратно 3

7. (х + 2) – (3х – 4)

8. х2 + у2 > 0

Решение.

Предложение является одноместным предикатом Р (х), IP = {– 4};
Предложение не является предикатом. Это ложное высказывание;
Предложение является одноместным предикатом Р (х), IP ={1};
Предложение не является предикатом. Это истинное высказывание;

     5)       Предложение является одноместным предикатом Р(х), IP =(3;+∞);
     6)       Предложение является одноместным предикатом Р (х), IP = {0; 3; 6; 9};
     7)       Предложение не является предикатом;

8) Предложение является двухместным предикатом Q(х,y), IQ = R×R \ {(0,0)}.

Пример 2. Изобразить на декартовой плоскости область истинности предиката [2].

Решение. Неравенство, составляющее исходный предикат, ограничивает часть плоскости, заключенную между ветвями параболы х = у2, она изображена серой частью рисунка:

Рисунок 1. График параболы х = у2

Предикаты, вслед за высказываниями, являются следующим важным предметом, исследуемым математической логикой.

Понятие предиката обобщает понятие высказывания, а теория предикатов представляет собой более тонкий инструмент, по сравнению с теорией высказываний, для изучения закономерностей процессов умозаключения и логического следования, составляющих предмет математической логики[1].

Таким образом, в основном, термин « предикат » понимается в смысле исходного определения, т.е. как языковое выражение. Связано это с тем, что одной из главных целей введения предикатов, как уже отмечалось во введении, является изучение выразительных возможностей логики первого порядка, возможности представления средствами этой логики информации, выраженного на каком - либо естественном языке людей, например, на русском или английском языке.

Заключение

Логика предикатов, как и традиционная формальная логика, расчленяет элементарное высказывание на субъект ( буквально – подлежащее, хотя оно может играть и роль дополнения ) и предикат ( буквально – сказуемое, хотя оно может играть и роль определения).

Субъект – это то, о чем что - то утверждается в высказывании, а предикат – это то, что утверждается о субъекте. Логика предикатов – это расширение логики высказываний за счет использования предикатов в роли логических функций.

Итак, актуальность темы реферата несомненна. Цель достигнута и задачи выполнены. Литература просмотрена, выбрана, проанализирована, результаты представлены в данном реферате.

Список используемых источников

Эвнин А.Ю. Дискретная математика. Конспект лекций. 1998.
Ерусалимский А.Я. Дискретная математика. Теория. Задачи. Приложения. 2000.
Электронный источник. URL: http://forum.vopr.net
Электронный источник. http://lib.mexmat.ru/books/109887
Электронный источник. http://lib.mexmat.ru/books/81214

Предикаты 📙 Реферат → 🆔 214023