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

Логика высказываний – очень узкая логическая система. Есть такие типы логических рассуждений, которые не могут быть осуществлены в рамках логики высказываний, например:

1. Всякий друг лица А есть друг лица В. С не есть друг В, следовательно, С не есть друг А.
2. Простое число два – четное. Следовательно, существуют простые четные числа.

Корректность этих умозаключений основана на внутренней структуре самих предложений и на смысле слов «всякий» и «существует».

Рассмотрим предложения, зависящие от параметров, например: «х – четное число», «х меньше y », «x +y =z », «u и v – братья». Если в первых трех предложениях заменить x ,y и z некоторыми числами, а в последнем подставить имена членов некоторой семьи, то полученные высказывания могут быть истинными или ложными. Например, для х =5, y =2, z =7, u – Петр, v – Иван получим: «5 – четное число», «5 меньше 2», «5+2=7», «Петр и Иван – братья».

Предложения такого типа называются предикатами. Точнее, предикатом P(x 1 ,…,x n) называется функция, переменные которой принимают значения из некоторого множества М, а сама она принимает два значения: истинное (И) и ложное (Л), т.е. P(x 1 ,…,x n):М {И,Л}.

Предикат от n аргументов называют n-местным предикатом и обозначают полностью P (n) (x 1 ,…,x n) , если нужно подчеркнуть число аргументов. Высказывания считают нуль-местными предикатами.

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

Например:

1. Пусть P (1) (x) означает предикат «х делится на 2», а Q (1) (х) – предикат «х делится на 3». Тогда выражение P (1) (x) &Q (1) (х) означает предикат «х делится на 2 и х делится на 3», т.е. определяет предикат делимости на 6.

2. Пусть S (2) (х,у) означает предикат «х=у ». Он принимает значение И тогда и только тогда, когда х=у . В этом случае выражение ┐S (2) (х,х) ÞS (2) (х,у) определяет предикат, принимающий значение И при любых х и у.

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

Квантор всеобщности. Пусть Р(х) – предикат, принимающий значение И или Л для каждого х ÎМ. Тогда под выражением "хР(х) будем подразумевать высказывание истинное, когда Р(х) истинно для каждого элемента х из М, и ложное – в противном случае. Символ "х называется квантором всеобщности и запись "хР(х) читается так: «для всех х Р(х) ». Это высказывание уже не зависит от х.

Квантор существования. Пусть Р(х) – предикат. Под выражением $х Р(х) будем понимать высказывание истинное, если существует элемент множества М, для которого Р(х) истинно, и ложное – в противном случае. Символ $ х называется квантором существования и запись $ хР(х) читается так: «существует х , такое, что (или для которого) Р(х) » .

Для предикатов, рассмотренных чуть ранее, можем записать:

1. $ х (P (1) (x) &Q (1) (х)) – истинное высказывание;
2. " х (P (1) (x) &Q (1) (х)) – ложное высказывание;
3. " х,у (┐S (2) (х,х) ÞS (2) (х,у)) – истинное высказывание.

Введем теперь строгие определения для исчисления предикатов.

(Чистое) исчисление предикатов (первого порядка) - это формальная теория К, в которой оп­ределены следующие компоненты.

1. Алфавит:

связки основные ┐,

дополнительные &,

служебные символы (,) Î (, ’ , ’ ,)

кванторы всеобщности

существования

предметные константы

переменные

предметные предикаты P, Q, . . .

функторы f, q,. . .

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

2. Формулы имеют следующий синтаксис:

Формула = (атом

| ┐ (формула | ( формула

(фор­мула ) | (переменная формула

| перемен­ная формула

Атом = предикат ( список термов )

Список термов = терм | терм ,

Список термов терм = константа |

Переменная | функтор ( спи­сок термов )

При этом должны быть выполнены следующие контекстные условия: в терме f (t 1 ,. . .,t n) функтор f должен быть n - местным. В атоме (или атомарной формуле) P(t 1 ,. . .,t n) предикат Р должен быть n - местным.

Вхождения переменных в атомарную формулу называются свободными. Свободные вхождения переменных в формулах А и В остаются свободными в формулах А и А В. В формулах x А и x А формула А, как правило имеет, свободные вхождения переменной х. Вхождения пе­ременной х в формулы x А и x А называются связанными. Вхождения других переменных (отличных от x ), которые были свободными в формуле А, остаются свободными и в формулах x А и x А. Одна и та же переменная может иметь в одной и той же формуле как свободные, так и связанные вхождения. Формула, не содержащая свобод­ных вхождений переменных, называется замкнутой.

Например, рассмотрим формулу x (Р(х) y Q(x,y)) и ее подформулы. В подформулу y Q(x,y) пере­менная х входит свободно, а оба вхождения переменной у связаны (квантором существования). Таким образом, эта подформула не замкнута. С другой стороны, то же самое вхождение пере­менной х в подформулу Q(x,y) является связанным вхождением в формуле x (Р(х) y Q(x,y)) . В этой формуле все вхождения всех переменных связаны, а потому формула замкнута.

Язык теории L не содержит кванторов, поэтому понятия свободного и связанного вхождения пе­ременных не применимы непосредственно. Обычно для удобства полагают, что все формулы тео­рии L замкнуты.

Формулы вида А и ┐А, где А - атом, называются литеральными формулами (или литералами). В формулах x А и x А подформула А называется областью действия квантора по х.

Обычно связки и кванторы упорядочивают по приоритету следующим образом: ┐, ,$, &, , . Лишние скобки при этом опускают. Терм t называется свободным для переменной х в формуле А, если никакое свободное вхождение переменной х в формулу А не лежит в области действия никакого квантора по переменной у, входящей в терм t. В частности, терм t свободен для любой переменной в формуле А , если ника­кая переменная терма не является связанной переменной формулы А.

Например:

а) терм у свободен для переменной х в формуле Р(x) , но тот же терм у не свободен для пере­менной х в формуле y P{x).

б) терм f(x, z) свободен для переменной х в формуле y P(x,y) Q(x), но тот же терм f(x, z) не свободен для переменной х в формуле

z y P(x,y) Q(x).

Переход от предиката Р(х) к " х Р(х) или $ х Р(х) называется связыванием переменной х , или навешиванием квантора на переменную х , или квантификацией переменной х.

Выражение " х Р(х) и $ х Р(х) не зависят от х и при фиксированных Р и предметного множества М имеет вполне определенные значения, представляя вполне конкретные высказывания относительно всех х в предметной области М.

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

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

Рассмотрим решение некоторых примеров.

Пример 4.4. Пусть N (х) – предикат «х – натуральное число». Рассмотреть варианты навешивания кванторов, интерпретировать и определить их истинность.

Решение. " х N(х) –«все числа натуральные». Это высказывание истинно на любом множестве натуральных чисел и ложно, если М содержит хоть одно ненатуральное число (например, целое отрицательное).

Пример 4.5. Пусть предикат Р(х,у) описывает отношение «х любит у » на множестве людей. Проанализировать варианты навешивания кванторов и дать интерпретацию.

Решение . Используя взаимно однозначное соответствие между отношениями предикатами, можно проиллюстрировать решение схемами (рис. 4.1.).

Рис. 4.1. Иллюстрация влияния кванторов

Интерпретация:

" х $ y Р(х,у) – «для любого х существует у , которого он любит».

$ у " х Р(х,у) – «существует такой у , которого любят все х ».

" х "уР(х,у ) - «все х любят всех у ».

$ х $ у Р(х,у) – « найдется х , который любит кого-то из у » или «найдется человек, который кого-то любит».

$ х " у Р(х,у) – «существует х , который любит всех у ».

" у $ х Р(х,у) – «для любого из у найдется х , который его любит».

Аксиомы (логические): любая система аксиом исчисления высказываний, плюс

P 1: x A(x) A(t),

P 2: A(t) x A(x),

где терм t свободен для переменной х в формуле А.

Правила вывода:

где формула А содержит свободные вхождения переменной х, а формула В их не содержит.

Исчисление предикатов, которое не содержит предметных констант, функторов, предикатов и собственных аксиом, называется чистым. Исчисление предикатов, которое содержит предметные константы и/или функторы и/или предикаты и связывающие их собственные аксиомы, называется прикладным.

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

Соответствие между предикатами, отношениями и функциями

n – местный предикат можно рассматривать как функцию Р (х 1 ,…х n) от n переменных х i Î М i , где М i - предметные области, а РÎВ={0,1}={И,Л}. Таким образом, предикат Р (х 1 ,…х n) является функцией типа Р: М 1 ´М 2 ´… ´М n ®В , или, если предметная область едина для всех переменных, то имеем Р: М n ®В .

Из рассмотренного очевидно, что для любых М и n существует однозначное соответствие между n-местными отношениями R ÍМ n и предикатами Р (х 1 ,…х n) , М n ®В :

Каждому n – местному отношению R соответствует предикат Р (х 1 ,…х n) такой, что Р (а 1 ,…а n)=1, если и только если (а 1 ,…а n)ÎR;

Всякий предикат Р (х 1 ,…х n) определяет отношение R такое, что (а 1 ,…а n)ÎR , если и только если Р (а 1 ,…а n)=1.

При этом R задает область истинности предиката P.

Рассмотрим теперь функцию f (х 1 ,…, х n), f : М n ®M . Тогда можно видеть, что всякой функции f: М n ®M соответствует предикат Р (х 1 ,…х n +1), Р: М n +1 ®В , такой что Р(а 1 ,…а n +1)=1 , если и только если f (а 1 ,…а n)=а n +1 .

Понятие предиката шире понятия функции (см. рис. 4.1.), поэтому обратное соответствие (от (n+1 )-местного предиката к n–местной функции) возможно не всегда, а только для таких предикатов, для которых выполняется условие, связанное с однозначностью функции:

Р(а 1 ,…а n +1)=0 ® ("а¢ n +1 ÎМ|а¢ n +1 ¹а n +1 Р(а 1 ,…а¢ n +1)=0. (4.3.)

Аналогичное соответствие имеется между подмножеством отношений {R¢}Ì{R} и множеством функций {f} . Для этого класса отношений выполняется условие

(а 1 ,…а n +1)ÎR¢ ® ("а¢ n +1 ÎМ|а¢ n +1 ¹а n +1 (а 1 ,…а¢ n +1)ÎR¢). (4.4.)

Пример 4.6. Каким отношениям и функциям соответствуют предикаты, определенные на множестве натуральных чисел?

1. Предикат суммы S: N 3 ®В:

S(х 1 ,х 2 ,х 3)=1 тогда и только тогда, когда х 1 +х 2 =х 3 .

2. Предикат порядка Q:N 2 ®В:

Q (х 1 ,х 2)=1 тогда и только тогда, когда х 1 £х 2 .

п-местный предикат - это функция Р(х 1 х 2 , х п) от п переменных, принимающих значения из некоторых заданных предметных областей, так что,a функция P принимает два логических значения – «истинно» или «ложно».

Таким образом, предикат Р(х 1, х 2, ..., х п) является функцией типа , где множества, называются предметными областями предиката; х 1, х 2, ..., х п -предметными переменными предиката; В = {1,0}.

Соответствия между предикатами, отношениями и функциями:

1. Для любых М и п существует взаимно однозначное соответствие между n -местными отношениями u n-местными предикатами Р(х 1, х 2, ..., х п), :

Каждому n -местному отношению R соответствует предикат Р(х 1, х 2, ..., х п), такой, что Р(a 1, a 2, ...,a п) = 1, если и только если (a 1, a 2, ..., a п) Î R;

Всякий предикат Р(х 1, х 2, ..., х п) определяет отношение R такое, что (a 1, a 2, ..., a п) Î R, если и только если Р(a 1, a 2, ...,a п) = 1.

При этом R задает область истинности предиката Р.

2. Всякой функции f (х 1, х 2, ..., х п) , соответствует предикат Р(х 1, х 2, ..., х п, х п+1)=1такой, что Р(a 1, a 2, ..., a п, a п+1)=1, если и только если f (a 1, a 2, ..., a п)=a n +1 .

Обратное соответствие (от (n+1 )-местного предиката (рис. 2.17) к n -местной функции) возможно не всегда, а только для таких предикатов Р ’ для которых выполняется условие (связанное с требованием однозначности функции): Р(a 1, a 2, ...,a п, a п+1) = 1, то для любого

a ’ п +1 ≠a п +1 Р(a 1, a 2, ...,a п, a ’ п +1) = 0 {1}

Аналогичное соответствие (взаимно однозначное) имеется между подмножеством отношений {R"}{R} и множеством функций {f }.

Для этого класса отношений выполняется аналогичное условие: если (a 1, a 2, ..., a п, a п+1) Î R ’ то для любого a ’ п+1 ≠a п+1 , (a 1, a 2, ..., a п, a п+1)R ’

Выражение Р(a 1, a 2, ...,a п) будем понимать как высказывание «Р(a 1, a 2, ...,a п)=1», а выражение Р(х 1, х 2, ..., х п) - как переменное высказывание, истинность которого определяется подстановкой элементов множества М вместо переменных (х 1, х 2, ..., х п).

Для обозначения двухместных предикатов помимо префиксной записи Р(х 1, х 2) используется нередко инфиксная запись х 1 Рх 2

Каким отношениям и функциям соответствуют следующие предикаты, определенные на множестве натуральных чисел:

1. Предикат тождества E:N 2 →В: Е(а ], а 2) = 1 тогда и только тогда, когда а ]= а 2

Двухместному предикату тождества Е – «x ]= x 2 » взаимно однозначно соответствуют:

а) двухместное отношение R 1 , - «быть равным», , тогда и только тогда, когда Е (a 1 , а 2) = 1;

б) одноместная функция (операция) тождества f 1 (x 1 )=х 2 , а именно:.

2. Предикат делимости D: N 2 →В: D (а ], а 2) = 1 тогда и только тогда, когда а ] делится на а 2:

Двухместному предикату делимости D – «х 1 делится на х 2 » взаимно однозначно соответствует двухместное отношение R 2 – «делиться», тогда и только тогда, когда D (a 1 , а 2) = 1. Однако функции f 1 (x 1 )=х2 для предиката делимости D (x 1 , x 2) не существует, так как не выполнено условие (1), например D(6, 2) = 1 и D(6, 3) = 1, однако 2≠3.

3. Предикат суммы S:N 3 →В: S(а 1, а 2, а 3) = 1 тогда и только тогда, когда а 1 +a 2 = a 3 .

Трехместному предикату суммы S – «x 1 +x 2 =x 3 » взаимно однозначно соответствуют:

а) трехместное отношение: тогда и только тогда, когда S(а 1, а 2, а 3) = 1;

б) двухместная функция (операция арифметики) - сложение f(х 1 , х 2) = х 3 , а именно: х 1 + х 2 = х 3 .

При задании частичного порядка, если пара элементов (a ,b ) принадлежит U , то говорят, что a предшествует b . Если никакой из этих двух элементов другому не предшествует, но говорят, что они не сравнимы.

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

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

Итальянский экономист Вильфредо Парето (1848-1923) предложил использовать в таких задачах конструкцию, которая в его честь называется границей Парето (Pareto frontier). Мы ее сейчас опишем.

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

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

Рассмотрим предложение

Это предложение не является высказыванием, так как о нем нельзя сказать, истинно оно или ложно. Оно называется предикатом или условием (на х и у). Приведем другие примеры предложений с переменными:

Есть простое число;

Есть четное число;

Меньше у,

Есть общий делитель у, z.

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

2 есть простое число;

3 есть четное число;

5 меньше 7;

3 есть общий делитель 6 и 12.

ОПРЕДЕЛЕНИЕ. Предложения с переменными, дающие высказывания в результате замены свободных переменных их допустимыми значениями, называются предикатами.

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

По числу входящих свободных переменных различают предикаты одноместные, двухместные, трехместные и т. д. Предикаты (2) и (3) - одноместные, предикаты (1) и (4) - двухместные, предикат (5) - трехместный. Высказывания будем считать нульместными предикатами.

Заменяя в одноместном предикате (2) переменную натуральными числами, будем получать высказывания:

0 есть простое число;

1 есть простое число;

2 есть простое число;

3 есть простое число и т. д.

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

Одноместный предикат можно рассматривать как условие на объекты данного вида; двухместный - как условие на пары объектов данного вида и т. д.

Предикаты можно задавать различными способами. В алгебре часто рассматривают предикаты, заданные с помощью уравнений, неравенств, а также систем уравнений или неравенств. Например, неравенство задает одноместный предикат, уравнение - двухместный, а система уравнений - трехместный у, z - рациональные переменные).

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

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

Высказывание, которое получается при подстановке в предикат набора допустимых значений вместо его переменных, будем обозначать Если это высказывание истинное (ложное), говорят, что набор значений удовлетворяет (не удовлетворяет) предикату