Формулы логики предикатов. Равносильность формул

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

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

К новым формулам логики предикатов относятся следующие выражения:

2. Если x, y, z, ... – предметные переменные, то предикаты P(x), Q(x, y), ... , а также выражения с кванторами "xP(x), $xR(x), "x$yQ(x, y), ... есть формулы.

3. Если A и B – формулы, то ØA, AÚB, A&B, AÉB, A~B есть формулы, в которых свободные переменные формул A и B остаются свободными, а связанные переменные формул A и B остаются связанными.

4. Ничто, кроме указанного в пунктах 1 – 3, не есть формула.

Пусть A – формула, содержащая свободную переменную x. Тогда "xA, $xA – формулы, причем в первом случае A является областью действия квантора общности, а во втором – областью действия квантора существования.

Пример 2.5.

1. Следующие выражения являются формулами логики предикатов:

а) A & B É C, где A, B, C – высказывания.

б) "x$yQ(x, y, z) & "x$yP(x, y, u).

Проанализируем последовательно это выражение.

Предикат Q(x, y, z) – формула;

Выражение "x$yQ(x, y, z) – формула; переменные x, y – связанные, переменная z – свободная.

Предикат P(x, y, u) – формула.

Выражение "x$yP(x, y, u) – формула; переменные x, y – связанные, переменная u – свободная.

Выражение "x$yQ(x, y, z) & "x$yP(x, y, u) – формула; переменные x, y – связанные, переменные z, u – свободные.

2. Выражение "x$yP(x, y, z) É Q(x, y, z) формулой не является. Действительно, выражение "x$yP(x, y, z) есть формула, в которой переменные x и y связанные, а переменная z свободная. Выражение Q(x, y, z) также формула, но в ней все переменные x, y, z свободные.

Определение 2.3. Формулы F и G, определенные на некотором множестве М, называются равносильными на этом множестве, если при любых подстановках констант вместо переменных они принимают одинаковые значения.

Определение 2.4. Формулы, равносильные на любых множествах, будем называть просто равносильными.

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

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

Пример 2.6.

а) $x(A(x) É "yB(y)) º $x(ØA(x) Ú "yB(y)).

б) "xA(x) É (B(z) É"xC(x)) º Ø("xA(x)) Ú ØB(z) Ú "xC(x).

в) ($xA(x) É"yB(y)) É C(z) º Ø($xA(x) É "yB(y)) Ú C(z) º Ø(Ø($xA(x)) Ú "yB(y) Ú C(z) º $xA(x) & Ø("yB(y)) Ú C(z).

2. Перенос квантора через отрицание.

Пусть A – формула, содержащая свободную переменную x. Тогда

Ø("xA(x) º $x(ØA(x)). (2.1)

Ø($xA(x)) º "xØ(A(x)). (2.2)

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

Справедливость равносильностей (2.1) и (2.2) вытекает из смысла кванторов. Так, левая часть (2.1) может быть прочитана следующим образом: “Неверно, что для всякого x имеет место A(x). В правой же части (2.1) утверждается: “Существует x, для которого A(x) не имеет места”. Очевидно, что оба утверждения одинаковы. В левой и правой частях (2.2) соответственно содержатся одинаковые утверждения: “Неверно, что существует x, для которого имеет место A(x)” и “Для всех x не имеет места A(х)”.

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

Пример 2.7.

Ø($x(A(x) É"yB(y)) º Ø($x(ØA(x) Ú "yB(y)) º "x(Ø(ØA(x) Ú "yB(y))) º "x(A(x) & Ø"yB(y)) º "x(A(x) & $yØB(y)).

3. Вынос квантора за скобки.

Пусть формула A(x) содержит переменную x, а формула B не содержит переменной x, и все переменные, связанные в одной формуле, связаны в другой. Тогда

"xA(x)ÚB º"x(A(x)ÚB). (2.3)

"xA(x)&B º"x(A(x)&B). (2.4)

$xA(x)ÚB º$x(A(x)ÚB). (2.5)

$xA(x)&B º$x(A(x)&B). (2.6)

Докажем формулу (2.3). Пусть формула "xA(x) Ú B истинна на некотором множестве изменения переменных М и при некоторых фиксированных значениях свободных переменных. Тогда либо формула "xA(x), либо формула B истинна. Если истинна формула "xA(x), то формула A(х) истинна для всякого х, принадлежащего М и, следовательно, формула A(x) Ú B тоже истинна для всякого х из М. Но тогда истинна формула "x(A(x)ÚB).

Если формула "xA(x)ÚB ложна, то ложны формулы "xA(x) и B. Следовательно, так как B не зависит от х, для всякого хÎМ формула A(x) Ú B ложна. Но тогда ложна формула "x(A(x) Ú B).

Равносильности (2.4) – (2.6) доказываются аналогично.

4. Дистрибутивность квантора общности относительно конъюнкции и квантора существования относительно дизъюнкции.

Пусть формула B, так же, как и формула A, зависит от х. Тогда

"xA(x) & "xB(x) º "x(A(x)&B(x)). (2.7)

$xA(x) Ú $xB(x) º $x(A(x)ÚB(x)). (2.8)

Докажем (2.7). Пусть правая часть (2.7) истинна, т. е. "x(A(x) & B(x)) = И. Тогда для любого х₀ÎМ истинно значение A(x₀) & B(x₀). Поэтому значения A(x₀) и B(x₀) одновременно истинны для любого х₀. Следовательно, истинна формула "xA(x) & "xB(x).

Если же правая часть (2.7) ложна, то для некоторого х₀ÎМ либо значение A(x₀), либо значение B(x₀) ложно. Значит, ложно либо"xA(x₀), либо"xB(x₀). Следовательно, "xA(x) & "xB(x) ложно.

Равносильность (2.8) доказывается аналогично.

Дистрибутивные законы для квантора общности относительно дизъюнкции и квантора существования относительно конъюнкции, вообще говоря, не имеют места, т. е. формулы

"xA(x) Ú "xB(x) и "x(A(x) Ú B(x)), а также $xA(x) & $xB(x) и $x(A(x) & B(x))

не являются равносильными, хотя они могут быть равносильными на некоторых множествах М.

Пример 2.8.

Показать, что формулы "x(A(x) Ú B(x)) и "xA(x) Ú "xB(x)) не равносильны.

Пусть М – множество натуральных чисел, A(х) = “х – четное число”, B(х) = “х – нечетное число”. Тогда

"x(A(x) Ú B(x)) = “Всякое натуральное число четное или нечетное” = И.

"xA(x) = “Всякое натуральное число – четное” = Л,

"xB(x) = “Всякое натуральное число – нечетное” = Л,

"xA(x) Ú "xB(x) = “Всякое натуральное число четное или всякое натуральное число нечетное” = Л,

т. е. формулы "x(A(x) Ú B(x)) и "xA(x) Ú "xB(x) не равносильны.

Пример 2.9.

Показать, что формулы $x(A(x) & B(x)) и $xA(x) & $xB(x) не равносильны.

Пусть A(х) = “У х голубые глаза”, B(х) = “У х черные глаза”. Тогда

$x(A(x) & B(x)) = “У некоторых голубые и черные глаза” = Л,

$xA(x) = “У некоторых голубые глаза” = И,

$xB(x) = “У некоторых черные глаза” = И,

$xA(x) & $xB(x) = “У некоторых голубые, и у некоторых черные глаза” = И

т. е. формулы $x(A(x) & B(x)) и $xA(x) & $xB(x) не равносильны.

5. Перестановка одноименных кванторов.

"x"yA(x,y) º "y"xA(x,y). (2.9)

$x$yA(x,y) º $y$xA(x,y). (2.10)

Разноименные кванторы переставлять, вообще говоря, нельзя.

Пример 2.10.

Пусть М – множество натуральных чисел, A(x, y) = “x > y”.

а) "x"yA(x, y) = “Для всех x и y имеет место x > y” = Л;

"y"xA(x, y) = “Для всех у и х имеет место х > y” = Л;

"x"yA(x, y) º "y"xA(x, y).

б) $x$yA(x, y) = “Существуют такие х и у, что х > y” = И;

$y$xA(x, y) = “Существуют такие y и x, что х > y” = И;

$x$yA(x, y) º $y$xA(x, y).

в) $x"yA(x, y) = “Существует такое х, что для всякого у имеет место x > y” = Л (утверждается существование максимального числа на множестве натуральных чисел);

"y$xA(x, y) = “Для всякого y существует такое х, что x > y” = И;

$x"yA(x, y) ¹ "y$xA(x, y).

г) A(х, у) = “Книгу х читал человек у”.

"x$yA(x, y) = “Каждую книгу читал кто-нибудь” = И (например автор книги читал свою книгу);

$y"xA(x, y) = “Существует человек, который читал все книги” = Л;

"x$yA(x, y) ¹$y"xA(x, y).

6. Переименование связанных переменных.

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

Пример 2.11.

A = "xF(x) É $xG(x).

Заменяя связанную переменную x на y в первом члене импликации и на z во втором, получим равносильную формулу:

B = "yF(y) É $zG(z).

A º B.

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

Рассмотрим теперь случай, когда закон дистрибутивности, вообще говоря не применим. Сначала рассмотрим формулу "xA(x) Ú "xB(x) и применим правило переименования переменных. Получим

"xA(x) Ú "xB(x) º "xA(x) Ú "yB(y). (2.11)

Так как "yB(y) не зависит от x, справедлива равносильность (2.3), причем B = "yB(y). Поэтому в соответствии с (2.3) можно вынести за скобки "x:

"xA(x) Ú "yB(y) º "x(A(x) Ú "yB(y)). (2.12)

Так как A(x) не зависит от y, справедлива равносильность (2.3), причем на этот раз B = A(x). Поэтому в соответствии с (2.3) можно вынести за скобки "y :

A(x) Ú "yB(y) º "y(A(x) Ú B(y)) (2.13)

Учитывая (2.11), (2.12), (2.13), получим:

"xA(x) Ú "xB(x) º "x"y(A(x) Ú B(y)). (2.14)

Таким образом за скобки выносятся два квантора "x и "y, а выражение в скобках не содержит знаков квантора.

Проведем аналогичные выкладки для формулы $xA(x) & $xB(x):

$xA(x) & $xB(x) º $xA(x) & $yB(y) º $x(A(x) & $yB(y)) º $x$y(A(x) & B(y)). (2.15)

Аналогично можно доказать следующие равносильности:

"xA(x) Ú $xB(x) º "x$y(A(x) Ú B(y)). (2.16)

"xA(x) & $xB(x) º "x$y(A(x) & B(y)). (2.17)