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

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

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₁,…,x_n) называется функция, переменные которой принимают значения из некоторого множества М, а сама она принимает два значения: истинное (И) и ложное (Л), т.е. P(x₁,…,x_n):М {И,Л}.

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

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

Например:

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

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

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

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

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

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

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

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

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

1. Алфавит:

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

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

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

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

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

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

переменные

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

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

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

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

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

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

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

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

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

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

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

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

При этом должны быть выполнены следующие контекстные условия: в терме f (t ₁ ,...,t_n) функтор f должен быть n - местным. В атоме (или атомарной формуле) P(t ₁ ,...,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 ₁: x A(x) A(t),

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

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

 

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

Modus ponens,

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

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

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

 

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

 

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

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

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

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

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

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

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

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

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

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

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

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

S(х₁,х₂,х₃)=1 тогда и только тогда, когда х ₁+ х ₂= х ₃.

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

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