Тема 4. Аксиоматические системы логики предикатов

Вопросы:

1. Язык логики предикатов.

2. Аксиоматическая система логики предикатов первого порядка.

3. Теоретико-функциональная интерпретация логики предикатов.

4. Метод аналитических таблиц в логике предикатов.

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

“Всякий друг Иванова является другом Петрова. Сидоров – не друг Петрова. Следовательно, Сидоров не является другом Иванова”.

Корректность этого рассуждения нельзя объяснить истинностными отношениями входящими в него высказываниями, так как представляющее его формула

А  В  С

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

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

При построении языка логики предикатов алфавит языка пропозициональной логики дополняем следующими символами:

1) a, b, c, ..., a₁, a₂, a₃, .... индивидные константы

2) x, y, z, ..., x₁, x₂, x₃, .... индивидные переменные

3) P, Q, R, ..., P₁, P₂, P₃, .... предикатные переменные

4) Кванторы:

 – квантор всеобщности (от английского all – все).

 – квантор существования (от английского exists – существует).

Определение формулы языка пропозициональной логики дополним следующими пунктами:

1) Если P – символ предиката, a, b – индивидные константы, то P(a, b) является элементарной формулой.

2) Если P – символ предиката, x, y – индивидные переменные, то P(x, y) является квазиформулой.

3) Если P(x, y) – квазиформула, то xyP(x, y) является формулой.

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

Предикатные переменные пробегут по множеству свойств и отношений. Собственно, эти свойства и отношения называют предикатами. Предикат можно рассматривать как функцию, аргументами которой являются индивидные переменные. В зависимости от того, сколько переменных может находиться на аргументных местах при предикатных символах, предикаты могут быть одноместными – Р(х), двухместные – Р(x, y), трехместные – P(x, y, z) и вообще k – местные. Количество аргументных мест при предикате обозначается верхним числовым индексом у символа предикатной переменной – Р^k. 0-местный предикатный символ (Р⁰) отождествляется с пропозициональной переменной; им соответствуют такие высказывания как “Вечереет”, “Холодает”, “Моросит”.

С содержательной точки зрения одноместный предикат характеризует присущность некоторого свойства предмету; то есть квазиформула Р(х) означает “х обладает свойством Р”. Двух, трех и т.д. местные предикаты характеризуют отношения. Так, например, если Р будет иметь значение “быть больше”, то выражению “х > y” можно поставить в соответствие следующую квазиформулу – Р(x, y). При построении языка логики предикатов, ориентированной на математические исследования, для таких выражений вводят специальные символы – f₁¹, f₂², ..., f_n^k, – для предметных функций.

Элементарная формула xP(x) будет означать “для всякого х имеет место свойство Р”; хP(x) – “существует предмет х, обладающий свойством Р”.

В квазиформуле P(x) переменная х является свободной. При записи перед ней одного из кванторов по данной переменной, эта переменная превращается в связанную. Та часть формулы, которая стоит после квантора, называется областью действия квантора по данной переменной. Так, например, в формуле x(P(x)  yQ(x, y)) областью действия квантора всеобщности будет вся часть формулы в скобках, а квантора существования – только последняя подформула. Формула, в которой нет свободных вхождений индивидных переменных, называется замкнутой формулой. Кванторы, как и пропозициональные связки, являются логическими знаками; по своему рангу они слабее, чем связка отрицания.

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

x = y =_Df Р (P(x)  P(y)),

где =_Df означает “равно по определению”.

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

В последующем изложении мы будем иметь в виду только логику предикатов первого порядка, и поэтому предикатные символы будут использоваться как константы. Так, для того чтобы записать в виде формулы логики предикатов первого порядка высказывание “Все разумное действительно, все действительное разумно” (Гегель), нам потребуются два предикатных символа:

1) P – “быть разумным”;

2) Q – “быть действительным”.

x(P(x)  Q(x))  x(Q(x)  P(x)).

2. Для построения аксиоматической системы логики предикатов первого порядка дополним список аксиом системы пропозициональной логики аксиомами для формул с кванторами:

1. xP(x)  P(y)

2. P(y)  xP(x)

Правилами вывода системы будут следующие:

1. И, И  Б

Б – modus ponens.

2. И

x И(x) – правило обобщения.

3. Б  И(x) , И(x)  Б

Б x И(x) x И(x)  Б – правила Бернайса.

На правила Бернайса накладывается ограничение, что Б не содержит вхождений переменной х.

Система логики предикатов первого порядка может быть сформулирована и без правил Бернайса, если список аксиом расширить за счет еще двух:

3. x(А  P(x))  (А  xP(x))

4. x(P(x)  А)  (xP(x)  А)

Ограничение то же самое: А не содержит вхождений переменной х.

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

yР(x, y)  z Q(x, z)

1. yР(a, y)  z Q(a, z) – результат подстановки а вместо индивидной переменной x;

2. yР(y, y)  z Q(y, z) – результат подстановки переменной y вместо переменной х;

3. yР(х, y)  y Q(x, y) – подстановка переменной y вместо переменной z.

Первая подстановка является правильной, а вторая – нет, поскольку переменная x в исходной формуле является свободной, а в результате подстановки на ее место переменная y оказывается связанной. Подстановка в третьем примере является тривиальной, поскольку выполнена по отношению к связанной переменной. То есть, для правильной подстановки вместо переменных необходимо соблюдать два условия:

1) Свободные переменные подставляемой формулы должны отличаться от связанных переменных исходной формулы, а связанные переменные подставляемой формулы – от свободных переменных исходной формулы;

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

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

х (P(x)  Q(x))  (P(y)  Q(y))

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

3. Теоретико-функциональная интерпретация элементарных формул вида P(а) аналогична интерпретации формул в пропозициональной логики: формула имеет значение “истинно” или “ложно” в зависимости от того, обладает или нет некоторым свойством предмет, обозначенным именем “а”. Для того чтобы дать теоретико-функциональную интерпретацию квазиформуле P(x) предположим, что существует некоторая логическая функция lx, которая принимает значения “истина” или “ложь” относительно некоторой предметной области D. Так при D = a, b логическая функция lx будет задаваться следующей матрицей. (Количество столбцов матрицы определяется по формуле 2ⁿ, где n – количество предметов в области D.)

x	l1x	l2x	l3x	l4x
a	и	и	л	л
b	и	л	и	л

Формулы с кванторами будут определяться следующим образом:

P(x)	хP(x)	xP(x)
l1x	и	и
l2x	л	и
l3x	л	и
l4x	л	л

Формула хP(x) будет иметь “истинно” тогда и только тогда, когда соответствующая P(x) логическая функция lx принимает значения “истинно”, и будет иметь значения “ложно”, когда lx принимает хотя бы одно значение “ложно”.

Формула xP(x) будет иметь значение “ложно” тогда и только тогда, когда соответствующая P(x) логическая функция lx принимает значения “ложно”, и будет иметь значение “истинно”, когда lx принимает хотя бы одно значение “истинно”.

При заданной конечной предметной области D = a₁, ..., а_n формула с квантором всеобщности может быть определена через конъюнкцию элементарных формул

хP(x) =_Df Р(а₁) & Р(а₂)  ... & Р(a_n),

а формула с квантором существования через дизъюнкцию элементарных формул

xP(x) =_Df Р(а₁)  Р(а₂)  ...  Р(a_n).

Применение операции отрицания к формуле Р(x) изменяет в матрице значение “истинно” на “ложно”, а “ложно” – на “истинно”. Тогда при заданной области D = a, b формулы хP(x) и xP(x) будут иметь следующие таблицы истинности.

P(x)	хP(x)	xP(x)
l1x	л	л
l2x	л	и
l3x	л	и
l4x	и	и

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

1. хP(x)  xP(x)

2. xP(x)  хP(x)

3. xP(x)  хP(x)

4. хP(x)  xP(x)

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

х P(x)  xP(x).

Допустим хP(x) имеет значение “истинно”. Возможно ли, чтобы xP(x) было бы ложным? хP(x) истинно при l₁x и ложно во всех остальных случаях (то есть при любом lx, кроме l₁x). При l₁x формула xP(x) имеет значение “ложно”, а ее отрицание будет давать значение “истинно”. Оба члена эквивалентности имеют значение “истинно”, что дает нам “истинно” для всей формулы.

Допустим хP(x) имеет значение “ложно”. Возможно ли, чтобы xP(x) было истинным? х P(x) ложно при всех l_nx, кроме l₁x. Но формула xP(x) истинна во всех случаях, кроме l₁x. Тогда ее отрицание будет давать “ложно”. Ложность обеих членов эквивалентности дает нам “истинно” для всей формулы.

Допустим xP(x) – “истинно”. Возможно ли, чтобы в этом случае хP(x) было ложным? Если xP(x) истинно, то xP(x) – ложно. Но последняя формула имеет значение “ложно” только при l₁x; а при l₁x формула хP(x) имеет значение “истинно”. При “истинно” для xP(x) формула х P(x) будет также иметь значение “истинно”, что и дает нам “истинно” для всей эквивалентности.

Допустим xP(x) – “ложно”. Возможно ли, чтобы в этом случае хP(x) было истинным? Если xP(x) ложно, то xP(x) будет иметь значение “истинно”. Последняя формула имеет значение “истинно” при любых l_nx, кроме l₁x. Но и формула хP(x) имеет значение “ложно” при любых l_nx, кроме l₁x. Таким образом, из условия ложности xP(x) следует, что формула хP(x) также будет иметь только значение “ложно”. Оба члена эквивалентности имеют значение “ложно”, что дает значение “истинно” для всей формулы.

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

Для квазиформул вида P(x, y) при D = {a, b} логическая функция l(x, y) будет задаваться матрицей, содержащей шестнадцать столбцов.

x

y

l1

l2

l3

l4

l5

l6

l7

l8

l9

l10

l11

l12

l13

l14

l15

l16

a

a

и

и

и

и

и

и

и

и

л

л

л

л

л

л

л

л

a

b

и

и

и

и

л

л

л

л

и

и

и

и

л

л

л

л

b

a

и

и

л

л

и

и

л

л

и

и

л

л

и

и

л

л

b

b

и

л

и

л

и

л

и

л

и

л

и

л

и

л

и

л

Формулы с кванторами определяются следующим образом:

Формулы xyP(x, y) и xyP(x, y) имеют значение “истинно” при l₁ и значение “ложно” при столбцах с l₂ по l₁₆.

Формулы xyP(x, y) и xyP(x, y) имеют значение “истинно” при столбцах с l₁ по l₁₅ и значение “ложно” при l₁₆.

Найдем значение истинности формулы xyP(x, y) при столбце l₆. Эта формула эквивалентна xyP(x, y). Отрицание перед квазиформулой P(x, y) изменяет в столбце все значения “истинно” на “ложно”, а “ложно” на “истинно”. По квантору существования для данного столбца получаем значение “истинно”, а отрицание для все формулы дает нам значение “ложно”.

Общезначимость формул логики предикатов зависит от выбора предметной области D. Так при D = a, bпостроим таблицу истинности для формулы y(Р(y)  х(P(x)  А))

P(x)	А	х(P(x)  А)	y(Р(y)  х(P(x)  А))
l1x	и	и	и
l1x	л	л	и
l2x	и	и	и
l2x	л	л	и
l3x	и	и	и
l3x	л	л	и
l4x	и	и	и
l4x	л	и	и

Покажем процедуру нахождения истинностных значений для подформулы х (P(x)  А) на примерах четвертой и восьмой строк.

4. х(P(x)  А)

х(l₂x  л)

л

Окончательной значение находится с помощью вспомогательной таблицы

x	l2x  л	l2a  л	l2b  л
a	л	и  л	л  л
b	и	л	и

Поскольку во вспомогательной таблице имеются не только значения “истинно”, то для квантора всеобщности получаем значение “ложно”

8. х (P(x)  А)

х (l₄x  л)

и

Значение “истинно” получаем с помощью вспомогательной таблицы

х	l4x  л	l4a  л	l4b  л
а	и	л  л	л  л
b	и	и	и

Для получения итогового столбца таблицы нам необходимо рассмотреть строки 2, 4 и 6, в которых один из дизъюнктов имеет значение “ложно”.

2. y(Р(y)  л)

y(l₁y  л)

и

Значение “истинно” следует из вспомогательной таблицы

y	l1y  л	l1a  л	l1b  л
а	и	и  л	и  л
b	и	и	и

4. y(Р(y)  л)

y(l₂y  л)

и

Значение “истинно” получаем из вспомогательной таблицы

y	l2y  л	l2a  л	l2b  л
а	и	и  л	л  л
b	л	и	л

Поскольку во вспомогательной таблице имеется одно значение “истинно”, то для формулы с квантором существования получаем значение “истинно”.

6. y(Р(y)  л)

y(l₃y  л)

и

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

y	l3y  л	l3a  л	l3b  л
а	л	л  л	и  л
b	и	л	и

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

Универсально общезначимыми являются также следующие формулы:

5. хА  А

6. хА  А

7. хyP(x, y) yхP(x, y)

8. хyP(x, y)  yхP(x, y)

9. хyP(x, y)  хP(x, x)

10. хP(x, x)  хyP(x, y)

11. хP(x)  хP(x)

12. хyP(x, y)  yхP(x, y)

13. хP(x) & хQ(x)  х(P(x) & Q(x))

14. хP(x)  хQ(x)  х(P(x)  Q(x))

15. A & хP(x)  х(A & P(x))

16. A  хP(x)  х(A  P(x))

17. A & хP(x)  х(A & P(x))

18. A  хP(x)  х(A  P(x))

19. х(P(x) & Q(x))  хP(x) & хQ(x)

20. хP(x)  хQ(x)  х(P(x)  Q(x))

21. A  хP(x)  х(A  P(x))

22. A  хP(x)  х(A  P(x))

23. хP(x)  A  х(P(x)  A)

24. хP(x)  A  х(P(x)  A)

25. хP(x)  хQ(x)  х(P(x)  Q(x))

26. (хP(x)  хQ(x))  х(P(x)  Q(x))

В этих формулах x, y – произвольные различные переменные, P(x), Q(x), P(x, y) – произвольные формулы, а А – формула, в которую х не входит свободно. В формулах 9. и 10. P(x, x) является результатом подстановки х вместо свободных вхождений y в P(x, y), причем х свободно для у в P(x, y).

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

А  (В  А)

вместо А – xP(x), а вместо В –  xP(x) даст общезначимую формулу

xP(x)  ( xP(x)  xP(x)).

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

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

хР(х)  хQ(x)

Избавимся от импликации

хР(х)  хQ(x)

хР(х)  хQ(x) – по формуле 3.

х(Р(х)  хQ(x)) – по формуле 18.

х(Р(х)  уQ(у)) – подстановка у вместо х.

ху(Р(х)  Q(у)) – по формуле 18.

В 1920 году Т. Сколем показал, что любая формула системы логики предикатов дедукционно эквивалентна некоторой нормальной формуле, в которой все кванторы существования, если они имеются, предшествуют всем кванторам всеобщности. Эти формулы получили название сколемовских нормальных формул. Здесь под дедукционной эквивалентностью понимается следующее. Две формулы И и Б называются дедукционно эквивалентными в некоторой системе, если из аксиом этой системы и формулы И принятыми правилами вывода выводима формула Б, и обратно, если из аксиом системы и формулы Б посредством правил вывода выводима формула И. Из этого следует, что если формулы И и Б эквивалентны в системе, то они и дедукционно эквивалентны; но обратное неверно.

Результат, полученный Сколемом, позволяет доказать свойство семантической полноты системы логики предикатов; то есть проблема полноты в широком смысле для системы одноместной логики предикатов решаются положительно. Проблема формулируется как теорема Геделя о полноте (доказанная последним в 1930 году) (аналог МТ2. Пропозициональной логики для логики предикатов первого порядка).

Всякая общезначимая формула логики предикатов первого порядка является выводимой.

Для доказательства теоремы необходимо показать, что всякая общезначимая нормальная формула Сколема является выводимой в системе логики предикатов первого порядка. Но тогда в силу дедуктивной эквивалентности будет выводимой и произвольная общезначимая формула И, сколемовской нормальной формой которой является общезначимая формула И^*.

Доказуемой также является следующая теорема (аналог МТ1. Пропозициональной логики для логики для логики предикатов первого порядка):

В системе логики предикатов первого порядка всякая выводимая формула является общезначимой.

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

4. Для использования метода аналитических таблиц в логике предикатов сформулируем правила построения таблицы для формул с кванторами; то есть процедура построения таблицы применима только для замкнутых формул. К правилам для пропозициональных связок добавляем правила для редукции кванторов:

T	T xP(x)		F	F xP(x)
	T P(a)			F P(b)
T	T xP(x)		F	F xP(x)
	T P(b)			F P(a)

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

а) правила Т_ и F_ (правила без ограничения) – индивидную переменную можно заменять любой константой, в том числе и той, которая уже встречалась в данном столбце таблицы;

б) правила F_ и Т_ (правила с ограничением) – индивидную переменную можно заменять только такой константой, которая еще не встречалась в данном столбце таблицы.

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

Понятия замкнутого столбца и, соответственно, таблицы остаются прежними.

Рассмотрим пример для формулы

хуР(х, у) ухР(х, у)

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

F хуР(х, у) ухР(х, у)

1. Т хуР(х, у)

2. F ухР(х, у) F

3. Т уР(а, у) Т; 1

4. F хР(х, b) F ; 2

5. T Р(a, b) Т; 3

6. F Р(a, b) F; 4

+

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

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

Сформулированный метод аналитических таблиц имеет один существенный недостаток, который мы продемонстрируем путем построения таблицы для приведенной выше формулы.

F y(Р(y)  х(P(x)  А))

1. F Р(a)  х(P(x)  А) F_

2. F Р(a)

3. F х(P(x)  А) F_ , 1.

4. F P(b)  А F_ , 3.

5. T P(b)

6. F А F_ , 5

–-

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

Таблица не получила замыкание, потому что мы имеем разные элементарные формулы: 2. F Р(a) и 5. T P(b). Формула 4. была получена из формулы 3. применением правила ложности для квантора всеобщности, которое относится к группе “правил с ограничением”, что исключало возможность подстановки на аргументное место при предикатном символе вместо переменной x индивидной константы a.

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

T		F
T		F
T	{Т А  В} {T A},{T B}	F	{F А  В} {F A, F B}
T	{Т А  В} {T A, T B},{F A, F }	F	{F А  В} {T A, F B},{F A, T B}
T	{T А  B} {T A, F B},{F A, T B}	F	{F А  B} {T A, T B},{F A, F B}
T	{T A} {F A}	F	{F A} {T A}
T	{T xP(x)} {T P(a),{T xP(x)}}	F	{F xP(x)} {F P(b)}
T	{T xP(x)} {T P(b)}	F	{F xP(x)} {F P(a),{ F xP(x)}}

Правила для пропозициональных связок делятся на две группы: 1) правила, порождающие из одного множества означенных формул два (соответствующие “правилам с ветвлением” прежней формулировки), например, T_ и F_; 2) правила, согласно которым сохраняется одно множество означенных формул, например, F_ и T_. Правила для формул с кванторами также делятся на две группы: F_ и T_ также называются “правилами с ограничением” – их применение запрещает вместо индивидной переменной подставлять константу, которая уже имеется данном множестве означенных формул; а “правила без ограничения” T_ и F_ позволяют на место индивидной переменной подставлять любую константу, в том числе и уже имеющуюся в данном множестве означенных формул. Последние правила в заключении содержать в качестве подмножества то множество, к которому оно применялось, что позволяет неоднократно применять это правило внутри данного множества. Последнее означает, что таблица может быть и бесконечной.

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

Рассмотрим пример построения таблицы для формулы

y(Р(y)  х(P(x)  А)).

1. {F у(Р(у)  х(Р(х)  А))}

2.{F P(a)  х(Р(х)  А), {F у(Р(у)  х(Р(х)  А))}} F_

3.{F P(a), F х(Р(х)  А), {F у(Р(у)  х(Р(х)  А))}} F_

4. {F P(a), F (P(b)  А), {F у(Р(у)  х(Р(х)  А))}} F_

5. {F P(a), T P(b), F A, {F у(Р(у)  х(Р(х)  А))}} F_

6. {F P(a), T P(b), FA, F P(b)  х(Р(х)  А)), {F у(Р(y)  х(Р(х)  А))}} F_

7. {F P(a), T P(b), F A, F P(b), F х(Р(х)  А), {F у(Р(y)  х(Р(х)  А))}} F_

8. {F P(a), T P(b), F A, F (P(b), F Р(c)  А, {F у(Р(y)  х(Р(х)  А))}} F_

9. {F P(a), T P(b), F A, F (P(b), T Р(c), F А, {F у(Р(y)  х(Р(х)  А))}} F_

Здесь каждое ниже стоящее множество означенных формул возникает из выше стоящего применением правила, обозначение которого стоит справа от множества. На седьмом шаге в множестве означенных формул получили T P(b) и F P(b), что свидетельствует о том, что данное множество (и вся таблица) замкнуто. Очевидно, что процесс построения таблицы не может быть завершен и получить значение “истинно” для Р(а) невозможно. Хотя в следующем цикле можно получить F Р(c), но это приведет к введению новой индивидной константы. Таким образом, данная формула общезначима при предметной области, содержащей два и более предметов, но она не может быть универсально общезначимой.

Задачи и упражнения к теме 4.

1. Запишите следующие высказывания в языке логики предикатов:

а) Не все птицы могут летать.

б) Ни один политик не честен.

в) Всякий, в ком есть упорство, может изучить логику.

г) Некоторые остроумны, только когда пьяны.

д) Все происходит, и ничего не случается.

е) Либо каждый любит кого-нибудь, и ни один не любит всех; либо некто любит всех, и кто-то не любит никого.

ж) Мы все в это время любили кого-то, а значит любили и нас.

з) Если всякий парикмахер в Джонсвилле бреет всех тех и только тех, кто не бреется сам, то в Джонсвилле нет ни одного парикмахера.

2. В данных формулах укажите свободные и связанные переменные:

а) xP(x, y)  yQ(x, y)

б) x(yP(x, y)  Q(x, y))

в) xyP(x, y, z)  zQ(y, z)

г) yP(a, y)  x(P(x, b)  zP(x, z))

3. Постройте таблицы истинности для следующих формул логики предикатов при заданной предметной области D = {a, b}:

а) xP(x)  xP(x)  A

б) x(P(x)  A)  P(x)

в) A  P(x)  xP(x)

г) xP(x)  A  P(a)

д) x(P(x)  A)  P(x)

е) P(x)  A  xP(x)

ж) x(P(x)  A)  P(b)

з) xP(x)  A  P(x)

x	y	l13
a	a	л
a	b	л
b	a	и
b	b	и

4. Определите истинностное значение формул, если P(x, y) определяется при заданной предметной области D = {a, b} следующим столбцом матрицы истинности:

а) xyP(x, y)

б) xP(x, b)

в) xyP(x, y)

г) xP(x, a)

д) xyP(x, y)

е) yP(b,y)

5. Методом аналитических таблиц покажите, общезначимы или нет следующие формулы:

а) xyP(x, y)  yxP(x, y)

б) xP(x)  xQ(x))  x(P(x)  Q(x))

в) (xP(x)  xQ(x))  x(P(x)  Q(x))

г) x(P(x)  (xP(x)  Q(x))  x(P(x)  Q(x))

6. Методом аналитических таблиц покажите, являются ли данные формулы тождественно-ложными

а) x(P(x)  Q(x))  x(P(x)  Q(x))

б) xyP(x, y)  yxP(x, y)

в) x(P(x)  Q(x))  x(P(x)  Q(x))