Файл: Matlog.doc

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

Определение 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).