Предикаты

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

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

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

«…»

 

 

Факультет _______________________________________________

Кафедра _________________________________________________

РЕФЕРАТ

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

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

    

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

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

 

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

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

 

Дата сдачи:

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

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

 

 

 

 

 

2014

Оглавление

 

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

 

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

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

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

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

 

 

 

 

 

3

 

 

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

 

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

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

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

4

 

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

 

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

 

 

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

Определение 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].

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

 

5

Например, выражение « существует число 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] и пишут:

P 

,

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

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

P 

,

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

 

 

6

 

Предикат называют  выполнимым, если хотя бы на одном наборе аргументов он принимает значение 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]. Эти операции рассмотрим сначала на примерах.

.

 

7

 

 

Пусть дано выражение: « существует число х, такое, что 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].

8

 

Если предикат 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.

9

 

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

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