§4. Логика предикатов

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

«всякое рациональное число есть вещественное число», (А)

« есть рациональное число», (В)

конечно, можно сделать заключение:

« есть вещественное число». (С)

В алгебре высказываний это рассуждение представимо формулой:

((А  В)  С). Очевидно, что тождественная истинность этой формулы не может быть обоснована. Для анализа этого утверждения необходимо в каждом составляющем высказывании выделить объекты рассуждения (подлежащие) и то, что о них говорится (сказуемые). Поэтому алгебра высказываний расширяется путем введения новых понятий: предметные переменные и константы, предикаты, кванторы. Получаемая при этом теория называется логикой предикатов. В ней используются некоторые понятия и обозначения из теории множеств, описанные в §1.

Пусть М – произвольное множество, оно называется предметной областью. Отдельные его элементы называются предметными константами и обозначаются первыми буквами алфавита а, b, с. Переменные, принимающие значения из М , называются предметными переменными и обозначаются буквами x, y, z. Буква t используется для обозначения, как предметных переменных, так и предметных констант. В случае необходимости эти буквы снабжаются числовыми индексами.

Пусть Мⁿ = М М …  М – n-я декартова степень множества М и Р – подмножество Мⁿ. Тогда с Р связывают истинностные значения, а именно: каждому кортежу (а₁, а₂, …, а_n), составленному из элементов М, соответствует истинностное значение Р(а₁, а₂, …, а_n) , которое равно И, если (а₁, а₂, …, а_n)  Р, и равно Л, если (а₁, а₂, …, а_n)  Р. Тем самым, Р соответствует высказывательная функция, обозначаемая символом Р(х₁, х₂, …, х_n), которая каждому (а₁, а₂, …, а_n)  Мⁿ ставит в соответствие И или Л. Эта функция называется n-местным предикатом, определенным на множестве М. Для обозначения предикатов используются заглавные латинские буквы Р, R, S, Т, возможно с числовыми верхними и нижними индексами. Для указания местности используется верхний индекс, например: Р²(х, у), R³(x, y, z). В анализе суждений предикаты выполняют роль сказуемых, а роль подлежащего выполняют предметные переменные и константы, входящие в предикаты. Логические операции по-прежнему выполняют роль связок между высказываниями. Теперь, формулы могут содержать предметные переменные и константы, и потому вводятся еще две логические операции – операции навешивания кванторов на предметные переменные.

Определение 13. Пусть формула F(x) содержит предметную переменную х. Тогда ей сопоставляются две формулы: (x)F(x) и (x)F(x). Символ  называется квантором общности, символ  – квантором существования. Процедура перехода от F(x) к (x)F(x) или (x)F(x) называется навешиванием соответствующего квантора на переменную х.

Чтобы пояснить смысл кванторов содержательно для примера рассматривается одноместный предикат Р(х), определенный на множестве М. Для каждого а из М предикат Р(х) при х = а принимает истинностное значение Р(а), равное И или Л. Тогда формулы (x)Р(x) и (x)Р(x) являются высказываниями, принимающими следующие истинностные значения:

(x)Р(x) = И  для любого аМ: Р(а) = И;

(x)Р(x) = И  существует аМ такой, что: Р(а) = И при х = а.

В разговорном языке формула (x)Р(x) читается, как «для всех х Р(x)» или «для любых х P(x)»; и формула (x)Р(x) читается, как «существует х Р(x)» или «для некоторого х Р(x)».

Пример 23. Пусть R(x) обозначает предикат «х – вещественное число», и Р(х) обозначает предикат «х – рациональное число». Очевидно, что указанное выше высказывание (А) можно пересказать следующим образом:

«Для любого х, если х – рациональное число, то х – вещественное число».

Тогда высказывания (А), (В), (С) можно представить формулами:

(x)(Р(x)  R(x)), Р( ), R( ), соответственно, и высказывание ((АВ)  С) примет вид:

((x)(Р(x)  R(x))  Р( ))  R( )).

Тождественная истинность этой формулы легко обосновывается в логике предикатов.

Формулы логики предикатов образуются из предметных переменных, констант и предикатных символов с помощью логических связок     и кванторов , . Однако для изучения этой теории необходимо дать более строгое определение ее формул. Для этого вводятся дополнительные понятия.

Определение 14. Пусть - символы предикатов и а₁, а₂, … , а_m - символы предметных констант. Тогда множество

 а₁, а₂, … , а_m ;  (41)

называется сигнатурой.

Фиксируется некоторая сигнатура , и определяются правильно образованные формулы сигнатуры  (сокращенно: ПОФ).

Определение 15. Правильно образованными формулами сигнатуры  называются выражения, удовлетворяющие следующим условиям :

1) если – n-местный символ из  и  символы предметных переменных или констант из , то  ПОФ;

2) если А и В – ПОФ, то (А), (А  В), (А  В), (А  В)  ПОФ;

3) если А – ПОФ и х  предметная переменная, то (x)А и (x)А  ПОФ;

4) других ПОФ нет.

Как и в алгебре высказываний, в ПОФ разрешается сокращать внешние скобки и скобки вокруг кванторов, если это не приводит к каким-либо недоразумениям, и в связи с этим вместо термина ПОФ используется слово «формула».

Пример 24. Пусть дана сигнатура  0, 1; . Тогда

а) , , ,

, , ,  ПОФ;

б) , , 0, х, (х  у),  не ПОФ.

Формулы сигнатуры  имеют смысл только тогда, когда имеется какая-нибудь интерпретация символов сигнатуры .

Определение 16. Пусть М – непустое множество и  – сигнатура вида (41). Интерпретацией  на М называется соответствие, при котором каждой константе а_i из сопоставлен некоторый элемент а_i из М, и каждому символу предиката из  сопоставлено n_i–местное отношение , определенное на множестве М. Моделью сигнатуры  называется тройка, состоящая из непустого множества М, сигнатуры  и интерпретации  на М. (Обозначение: М,).

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

Пример 25. а). В формуле первое вхождение х связанное, а второе вхождение х и вхождение у свободные.

б). В формуле оба вхождения х₁ связанные, а вхождение х₂ свободное.

в). Формулы , , замкнутые.

Фиксируются сигнатура вида (41) и модель М, и рассматривается формула A сигнатуры . Пусть t = - список всех предметных констант и свободных переменных, входящих в А. Этот список называется параметрами формулы А. И пусть a = - кортеж допустимых значений из М для этих параметров. Индукцией по логической глубине формулы А определяется истинностное значение А в модели М, при t =а.

Определение 17. 1). Если А = Rⁿ , то

А = И при t =а  Rⁿ = И,

где Rⁿ  n–местное отношение, интерпретирующее символ Rⁿ на М.

2). Пусть формулы В и С имеют определенные истинностные значения приt =а, и формула А имеет вид (В) или (В  С), или (В  С), или (В  С). Тогда истинностное значение А приt =а, определяется согласно определениям 6-9.

3). Пусть для любогоа₀ М формула В(х) имеет определенные истинностные значения при х =а₀ иt =а. Тогда:

а) если А = (x)В(х), то:

А = И приt =а  для любогоа₀ М В(х) = И при х =а₀ иt =а;

б) если А = (x)В(х), то:

А = И приt =а  существуета₀ М такое, что В(х) = И при х =а₀ иt =а.

Пример 26. Пусть Z – множество всех целых чисел, сигнатура  = {0, 1; S³, P³}. Символы 0, 1 интерпретируются как ноль и единица, символы S³, P³ интерпретируются как операции сложение и умножение соответственно. Тогда множество Z с указанной интерпретацией является моделью Z, арифметики целых чисел, и следующие формулы выражают соответствующие математические суждения.

1).  «для произвольных чисел x, y существует их сумма z».

2).  «существует число 0».

3).  «существует число 1».

4).  «для произвольных чисел x, y существует их произведение z».

5).  «для произвольных чисел x, y существует частное z от деления y на x».

Так как Z  множество всех целых чисел, то суждения 1)  4) истинны и суждение 5) ложно в модели Z,.

В определении 17 непосредственно указано, в каком случае формулы вида истинны. Полезно также запомнить случаи, когда эти формулы ложны. Пусть выполняются все условия пункта 3) определения 17, тогда

в) если А = (x)В(х), то:

А = Л приt =а  существуета₀ М такой, что В(х) = Л при х =а₀ иt =а;

г) если А = (x)В(х), то:

А = Л приt =а  для любогоа₀ М В(х) = Л при х =а₀ иt =а.

Определение 18. Формула А сигнатуры  называется тождественно истинной или тавтологией, если она истинна в любой модель М, при любых значениях ее параметров из М. По-прежнему запись А обозначает тождественную истинность формулы А.

Как и в алгебре высказываний, тавтологии логики предикатов отождествляются с правильными суждениями. В связи с этим, нужно отметить, что все тавтологии алгебры высказываний автоматически переносятся в логику предикатов, поэтому теоремы 4  8 выполняются в этой теории. Ниже приводятся новые основные тавтологии и эквивалентности логики предикатов.

Теорема 9. Пусть А(х)- формула логики предикатов и А(у) получается из А(х) заменой всех свободных вхождений х на у. Тогда если все новые вхождения у свободны в А(у), то следующие формулы тождественно истинные:

(x)А(х)  А(у), А(у)  (x)А(х).

Доказательство (см. [3], с.114).

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

Теорема 10. Пусть В(х), С  формулы логики предикатов и С не содержит свободных вхождений переменной х, тогда:

а) если (С  В(х)), то (С  (x)В(х));

б) если (В(х)  С), то ((x)В(х)  С).

Доказательство (см. [3], с.114).

Таким образом, согласно теоремам 5, 6, 9, 10, все теоремы исчисления предикатов являются тождественно истинными формулами. Обратное утверждение также верно (см. [3], с.114).

Определение 19. Формулы А и В сигнатуры  называются эквивалентными, если в любой модели М, при любых фиксированных значениях из М своих свободных переменных эти формулы принимают одинаковые истинностные значения. (Обозначение: А  В).

При доказательстве эквивалентности А  В возможны два способа.

1. Прямое доказательство. Фиксируется произвольная модель М, той же сигнатуры, что и формулы А, В, и доказываются два утверждения:

а) если А = И в М,, то В = И в М,;

б) если В = И в М,, то А = И в М,.

Если эти утверждения доказаны, то эквивалентность доказана, а в противном случае нет.

2. Доказательство от противного. Предполагается, что в некоторой модели М, той же сигнатуры, что и формулы А, В, эти формулы принимают разные истинностные значения, и рассматривают два случая:

в) А = И и В = Л в М,;

г) А = Л и В = И в М,.

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

Пример 27. Доказать следующие эквивалентности:

(х)( у)Р²(х, у)  (у)( х)Р²(х, у), (х)(у)Р²(х, у)  (у)(х)Р²(х, у).

Решение. 1-я часть. а). Пусть в соответствующей этим формулам модели М, формула (х)( у)Р²(х, у) = И, тогда для некоторых элементов а, b из М: Р²(a, b) = И. Но это влечет: (у)(х)Р²(х, у) = И в М,, т.е. этот пункт доказан. Пункт б) доказывается аналогично. Первая эквивалентность доказана.

2-я часть. Доказательство от противного. Пусть существует модель М,, в которой (х)(у)Р²(х, у) = И и (у)(х)Р²(х, у) = Л. Из последнего равенства следует, что для некоторых элементов а, b из М: Р²(a, b) = Л. Но это влечет (х)(у)Р²(х, у) = Л в М,, что противоречит исходному предположению. Следовательно, (у)(х)Р²(х, у) = И в М,. Второй случай: (х)(у)Р²(х, у) = Л и (у)(х)Р²(х, у) = И в М,, рассматривается аналогично. Вторая эквивалентность доказана.

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

Теорема 11. Для любой формулы А(х) логики предикатов верны следующие эквивалентности:

1) (х)А(х)  (х)А(х); 2) (х)А(х)  (х)А(х).

Доказательство. 1). Пусть (х)А(х) = И в модели М,, тогда (х)А(х) = Л в М,. Следовательно, существует элемент аМ такой, что А(х) = Л при х = а. Это влечет А(х) = И при х = а и поэтому (х)А(х) = И в М,. В одну сторону эквивалентность 1) доказана. Остальное доказывается аналогично.

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

В математике и в жизни постоянно встречаются суждения, в которых предметные переменные должны пробегать не весь универсум возможных значений, а лишь некоторую его часть. Например, для суждения А = «Все четные числа являются составными» предметной областью служит множество натуральных чисел N = {1, 2, 3, …}, и характеризующим предикатом является отношение С(х) = «х – составное число». Кроме того, при описании этого суждения формулой возникает желание: ввести ограниченную переменную y_ч, пробегающую множества четных чисел N_ч = {2, 4, 6, ... }, или ввести ограниченные кванторы вида (xN_ч), т.е. использовать следующие записи:

А= (у_ч)С(у_ч) или А= (xN_ч)С(х).

Но при формализации всегда нужно стараться новые понятия конструировать из старых понятий. Такой принцип определения новых понятий имеет еще одно преимущество: в «граничных» случаях, противоречащих интуиции и здравому смыслу, их формальный смысл будет точно определен, и не нужно будет вводить каких-либо новых ограничений, чтобы избегать возникаюшие трудности или не впасть в противоречие. В данном примере можно ввести ограничивающий предикат Ч(х) = «х – четное число», и тогда суждение А запишется следующей формулой логики предикатов:

(x)(Ч(х)  С(х)).

Важный момент в этой записи: в случае ограниченного квантора общности после ограничивающего предиката Ч(х) нужно ставить символ импликации.

Аналогичная ситуация возникает при рассмотрении суждений с ограниченным квантором существования. Например, для суждения В = «Некоторые молодые люди – студенты» предметной областью служит множество W всех жителей нашей планеты, и характеризующим предикатом является отношение С(х) = «х – студент». Ограничивающим предикатом является М(х) = «х – молодой человек», тогда В запишется следующей формулой логики предикатов:

(x)(М(х)  С(х)).

Важный момент в этой записи: в случае ограниченного квантора существования после ограничивающего предиката М(х) нужно ставить символ конъюнкции.

Пример 28. Перевести на формальный язык следующие суждения.

А₁ = «Ни одному лысому не нежна расческа».

А₂ = «Каждый, кто упорно работает, добивается успеха».

А₃ = «Ни один бездельник не станет знаменитостью».

В₁ = «Некоторые кошки поют по ночам».

В₂ = «Некоторые лекции невозможно понять».

Решение. 1. Вводится предметная область М – множество всех мужчин, и пусть Л(х) = «х – лысый», Р(х) = « х нужна расческа». Тогда

А₁ = (x)(Л(х)  Р(х)).

2. Вводится предметная область W  множество всех жителей нашей планеты, и пусть Р(х) = «х упорно работает», У(х)= « х добивается успеха». Тогда А₂ = (x)(Р(х)  У(х)).

3. Вводится предметная область W  множество всех жителей нашей планеты, и пусть Б(х) = «х  бездельник», З(х) = « х  знаменитость». Тогда

А₃ = (x)(Б(х)  З(х)).

4. Вводится предметная область А  множество всех животных нашей планеты, и пусть К(х) = «х  кошка», ПН(х) = « х поет по ночам». Тогда

А₃ = (x)( К(х)  ПН(х)).

5. Вводится предметная область Р  множество всех речей жителей планеты, и пусть Л(х) = «х  лекция», П(х) = « х можно понять». Тогда

А₃ = (x)( Л(х)  П(х)).

Пример 29. Перевести с формального языка на разговорный язык.

(x)( С(х))  (О(х) Сп(х))), где С(х) = «х – студент», О(х) = «х – отличник», Сп(х) = «х – спортсмен».

Ответ: «Не верно, что все студенты отличники или спортсмены».

(x)(О(х)  (у)(Т(у) Б(х, у))), где О(х) = «х – обезьяна», Т(х) = «х – тигр», Б(х, у) = «х боится у».

Ответ: «Любая обезьяна боится тигров».

Отношение «логическое следствие» в логике предикатов определяется следующим образом.

Определение 12. Пусть F₁, F ₂, … , F _к и G  формулы сигнатуры . И пусть в любой модели М, для любого набора значений из М свободных переменных этих формул, на котором все формулы F₁, F ₂, … , F _к истинны, формула G тоже истинна. Тогда G является логическим следствием F₁, F ₂, … , F_к. Обозначение: F₁, F ₂, … , F _к G.

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

1. . 2. . 3. .

4. . 5. . 6. .

7. . 8. . 9. .

10. . 11. . 12. .

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

Пример 30. Проверить (х)А(х)  (х)В(х)  (х)(А(х)  В(х)).

Решение. Применяется метод доказательства от противного. Пусть существует модель М,, в которой эта формула равна Л (1-я строка таблицы). Эта формула является импликацией, тогда, по правилу 6, ее посылка равна И и заключение равно Л (2-я строка).

1	(х)А(х)(х)В(х)  (х)(А(х) В(х)) = Л в М,			от противного
2	(х)А(х)(х)В(х) = И		(х)(А(х)В(х)) = Л		правило 6
3	(х)А(х) = И	(х)В(х) = И	(сМ) (А(с)В(с)) = Л		правила 1, 12
4	(с1М)А(с1) = И	(сМ) В(с) = И			правила 11, 9
5	А(с1) = И	В(с1) = И	(А(с1)В(с1)) = Л		следствие
6	(А(с1)В(с1)) = И				следствие

В первом равенстве формула является конъюнкцией, тогда, по правилу 1, оба ее члена равны И (3-я стр, 1-й и 2-й столбцы). Во втором равенстве формула начинается с (х), тогда, по правилу 12, для любого с из М формула в скобках равна Л (3-я стр, 3-й ст.). В 3-й строке первая формула начинается с (х), тогда, по правилу 11, существует с₁ из М такой, что А(с₁) = И (4-я стр., 1-й ст.). Вторая формула в 3-й стр. начинается с (х), тогда, по правилу 9, для любого с из М В(с) = И (4-я стр., 2-й ст.). В частности, для с₁ В(с₁) = И (стр.5, 2-й столбец), кроме того, А(с₁) = И(стр.5, 1-й столбец), отсюда конъюнкция этих формул равна И (6-я стр., 1-й ст.). Получено противоречие: (А(с₁)В(с₁)) = И и (А(с₁)В(с₁)) = Л. Это означает, что данная формула является истинной в любой модели.

Вывод: эта формула тождественно истинная.

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

Пример 31. Проверить (х)(А(х)В(х))  (х)А(х)(х)В(х).

Решение. Получается следующая семантическая таблица.

1	(х)(А(х)В(х))  (х)А(х)(х)В(х) = Л в М,					от противного
2	(х)(А(х)В(х)) = И			(х)А(х)(х)В(х) = Л			правило 6
3	(сМ) (А(с)В(с)) = И			(х)А(х) = Л	(х)В(х) = Л		правила 9, 4
4		(с1М)А(с1) = Л			(с2М)В(с2) =Л		правило 10
5	(А(с1)В(с1)) = И		А(с1) = Л				следствие
6	(А(с2)В(с2)) = И				В(с2) = Л		следствие

Здесь противоречие не возникает, так как возможна модель, в которой элементы с₁, с₂ будут разными, и при этом А(с₂) = И и В(с₁) = И.

Вывод: эта формула не является тождественно истинной.

Пример 32. Проверить логическое следствие:

(х)(А(х) (х)В(х))  (х)(С(х)  А(х))  (х)(С(х)  В(х)) (х)В(х).

Решение. От противного предполагается, что в модели посылки истинны и заключение ложно, и составляется семантическая таблица.

1	(х)(А(х) (х)В(х)) (х)(С(х)А(х)) (х)(С(х)  В(х)) = И			(х)В(х) = Л	от противного
2	(х)( А(х)  (х) В(х)) = И	(х)(С(х)А(х)) = И	(х)(С(х)  В(х)) = И		правило 1
3	(сМ) А(с)(х)В(х) = И	(сМ) С(с)А(с) = И	(с1М) С(с1)  В(с1) = И	(сМ) В(с) = Л	правила 9,11,12
4	А(с1)(х)В(х)= И	С(с1)А(с1) = И	С(с1) В(с1) = И	В(с1) = Л	следствие
5	А( с1) = Л				правило 6
6		С(с1) = И			правило 3
7			В(с1) = И		правило 6

Получено противоречие: В(с₁) = И и В(с₁) = Л. Вывод: данное отношение верно.

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

«Все молодые козлята прыгают. Ни одно молодое животное не прыгает,

если оно не здорово. Следовательно, все молодые козлята здоровы.»

Решение. Вводится предметная область М  множество всех молодых животных нашей планеты, и пусть К(х) = «х  молодой козленок», П(х) = « х прыгает », З(х) = « х здоров». Тогда данное рассуждение запишется формулой:

(х)(К(х)  П(х)), (х)(З(х)  П(х)) (х)(К(х)  З(х)).

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

1	(х)(К(х) П(х)) = И	(х)(З(х)П(х)) = И	(х)(К(х) З(х)) = Л		от противного
2	(сМ) К(с)П(с) = И	(сМ) З(с)П(с) = И	(с1М) К( с1) З( с1)=Л		правила 9, 12
3			К( с1) = И	З(с1) =Л	правило 6
4	К(с1)П(с1) = И	З(с1)П(с1) = И			следствие
5	П( с1) = И			З(с1) =И	правила 5,7
6		П( с1) = И			правило 5
7		П( с1) = Л			правило 7

Получено противоречие: П(с₁) = И и П(с₁) = Л. Вывод: данное рассуждение логически правильное.

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

«Некоторые птицы гордятся своим хвостом, но не могут петь. Ни одна птица, кроме павлина, не может гордиться своим хвостом. Значит, некоторые павлины не могут петь».

Решение. Вводится предметная область М  множество всех птиц нашей планеты, и пусть П(х) = «х  павлин», Г(х) = « х гордится своим хвостом», МП(х) = « х может петь». Тогда данное рассуждение запишется формулой:

(х)(Г(х) МП(х)), (х)(П(х)Г(х)) (х)(П(х) МП(х)),

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

1	(х)(Г(х) МП(х)) = И		(х)(П(х)Г(х))= И	предположение
2	(с1М) Г(с1) МП(с1) =И		(сМ) П(с)Г(с)= И	правила 11, 9
3	Г(с1)=И	МП(с1) =И	П(с1)Г(с1) = И	правило 1
4	Г(с1)= Л			правило 8
5			П(с1) = Л	правило 5
6			П(с1) = И	правило 8
7		(П( с1) МП( с1)) = И		правило 1
8		(с1М)( П( с1) МП( с1)) = И		следствие
9		(х)(П(х) МП(х)) = И		правило 11