ФОРМУЛЫ ЛОГИКИ ПРЕДИКАТОВ. РАВНОСИЛЬНОСТЬ ФОРМУЛ

Определение 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-м – областью деяния квантора существования.

Пример 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)) = И. Тогда для хоть какого х0ÎМ поистине значение A(x0) & B(x0). Потому значения A(x0) и B(x0) сразу истинны для хоть какого х0. Как следует, истинна формула "xA(x) & "xB(x).

Если же правая часть (2.7) неверна, то для некого х0ÎМ или значение A(x ФОРМУЛЫ ЛОГИКИ ПРЕДИКАТОВ. РАВНОСИЛЬНОСТЬ ФОРМУЛ0), или значение B(x0) неверно. Означает, неверно или"xA(x0), или"xB(x0). Как следует, "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 во 2-м, получим равносильную формулу:

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)


fotosinteziruyushie-strukturi-nizshih-eukarioticheskih-i.html
fototerapiya-i-terapevticheskaya-fotografiya.html
foundations-of-excursion-guidance.html