И.А. Пушкарев логика

101

Осталось рассмотреть случай, когда формула имеет вид Eyp или Ayp , причём для формулы р уже всё доказано. При этом интересен только случай, когда ч

является параметром формулы р(иначе х не является также и параметром

формул Eyp и Ayp , так что, например, Eyp(t x)= Eyp , и доказывать нечего). В

этом случае, по определению корректной подстановки, переменная y не входит

в терм t, поэтому корректной является и подстановкаp(t x). Осталось

воспользоваться определением истинности: [Ayp(t x)](p )= [Ay(p(t x))](p )=1 Û

"x Î I (p , x)	[p(t		x)](x )=1.	Заметим,	что
I (p , x)= I (p + (x a [t](p )), x)= I (x, x)= I (x + (x a [t](p )), x)					"x Î I (p , x),

поскольку значение оценки π на переменной х не учитывается, а ничем больше

рассматриваемые оценки не отличаются. По индукционному предположению

[p(t x)](x )= [p](x + (x a [t](p ))) "x Î I (p , x). Отсюда окончательно получаем:

"x Î I (p + (x a [t](p )), x) [p](x + (x a [t](p )))=1 Û [Ayp](p + (x a [t](p )))=1.

Для другого квантора рассмотрение проводится аналогично.

QED

Теперь можно завершить доказательство общезначимости аксиом (А14) и

(А15). Например, левая часть импликации Ax p(x)® p(t x) истинна на оценке π

тогда	и только тогда, когда "x Î I (p , x)					[p](x )=1. В	частности, поскольку
оценка	p + (x a [t](p ))	тоже	является			элементом	множестваI (p , x), то
[p](p + (x a [t](p )))=1. Но		тогда	и [p(t		x)](p )= [p](p + (x a [t](p )))=1, поэтому

если левая часть импликации истинна, то истинна и правая. Следовательно,

импликация является общезначимой. Общезначимость второй аксиомы(и,

кстати, соответствующая часть доказательства леммы10.3) доказывается аналогично (и объявляется несложным, но изнурительным упражнением,

обязательным для выполнения J).

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

		102
рассмотрение первого правила Бернайса(рассмотрение второго					правила
завершает решение самостоятельного упражнения).
Пусть	формула p ® q(x)	общезначима.	Формула	p ® Axq(x)	может
оказаться	ложной только на	оценках, на	которых	истинна формула.

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

Поэтому для любой оценкиπ, на которой истинна формула,				верно
утверждение: "x Î I (p , x) [p](x )=1. Следовательно, в			силу общезначимости
формулы p ® q(x),	"x Î I (p , x)	[q](x )=1, что по	определению	означает:
[Axq(x)](p )=1. Из	истинности	левой части импликацииp ® Axq(x)		всегда

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

QED

3. Выводы и выводимость в исчислении предикатов

Напомним: вывод отличается от доказательства только тем, что наряду с

аксиомами в нем можно использовать и посылки– произвольные формулы,

возможно, не являющиеся общезначимыми. Это приводит к появлению

неприятного ограничения на использование первого правила Бернайса.
Действительно, предположим, что			в	качестве посылки			использована
формула r(x), содержащая		свободную		переменнуюх.		Эта		формула
соответствует некоторому свойству объекта, который мы							имеем право
подставлять вместо переменной х. Поэтому если мы вывели формулу p ® q(x),
использовав	посылку, то мы,	формально	говоря, опирались			на	упомянутое
свойство, и в отсутствие этого свойства выведенная формула								может быть
неверна. Само по себе это не страшно: в формуле p ® q(x)					переменная х (как
ссылка на упомянуто свойство) присутствует. Однако она отсутствует формуле
p ® Axq(x),	которая, получается, формулирует свойство				общего			характера.
Вообще говоря, неверное J.

103

Соответственно, следует запретить применение первого правила Бернайса

(а, вследствие этого – и правила обобщения) по любой переменной, свободно входящей в некоторую посылку.

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

Лемма 10.4. (p ® q)f (Øq ® Ø p).
Доказательство.	Импликация (p ® q)® (Øq ® Ø p)	является

пропозициональной тавтологией (нетрудно проверить таблицей), поэтому, по теореме о полноте исчисления высказываний, выводима в этом исчислении, и,

следовательно, выводима в (более общем) исчислении предикатов. После того,

как к посылке p ® q приписано её доказательство (не использовавшее правила Бернайса), остаётся воспользоваться МР.

		QED
Лемма 10.5. {p ® q, q ® r}f (p ® r ).
Доказательство.	Аналогично	предыдущей , леммедостаточно
воспользоваться тем, что	формула (p ® q)® ((q ® r )® (p ® r )) является

пропозициональной тавтологией.

QED

Лемма 10.6. f(Axp(x)® Exp(x)).

Доказательство. Подстановка переменной на место самой себя всегда допустима, поэтому формулы Axp(x)® p(x) и p(x)® Exp(x) являются

аксиомами. Осталось воспользоваться предыдущей леммой.

			QED
Лемма 10.7. f (EyAxp(x, y)® AxEyp(x, y)).
Доказательство.	Из аксиом Axp(x, y)® p(x, y) и		p(x, y)® Eyp(x, y)	и
леммы 10.5 следует, что f (Axp(x,		y)® Eyp(x, y)). Заметим, что левая часть не
имеет параметра х, а	правая –	параметра y. Кроме	того, речь идёт	о
доказательстве, а не	о выводе, поэтому (посылок нет)		с применением ПБ1

104

проблем не возникнет. Поэтому правила Бернайса можно применять оба и в

любом	порядке,	получив		поочерёдно (например)				теоремы
Axp(x,	y)® AxEyp(x, y) и EyAxp(x, y)® AxEyp(x,					y).
								QED
Лемма 10.8. f (p ® q) Þ f (Axp ® Axq)
Доказательство. Добавим к выводу формулы p ® q аксиому Axp ® p и
получим при помощи леммы10.5 теорему					Axp ® q . Левая часть			не	имеет
параметра х, поэтому можно воспользоваться ПБ1.
								QED
Замечание. Однако в силу сделанных выше замечаний пока нельзя
утверждать, что (p ® q)f (Axp ® Axq). ПБ1					использовалось по переменной х,
которая в содержательной ситуации однозначно свободно входит в посылку.
Лемма 10.9. (p ® q)f (Еxp ® Еxq).
Доказательство		аналогично		предыдущему, используются				аксиома
q ® Exq и ПБ2.
								QED
Лемма 10.10. f (Axp(x)® Ayp(y)).
Доказательство.		Применим	к		аксиомеAxp(x)® p(y)			ПБ1	по
переменной y (которая не входит свободно в левую часть импликации).
								QED
Определение 10.3. Формулы				p	и	q	называются	доказуемо

эквивалентными (обозначаем p « q ), если выводимы обе импликации p ® q и

q ® p .

Лемма 10.11. Если p(x)« q(x), то Ax p(x)« Ax q(x) и Ex p(x)« Ex q(x).

Доказательство. Достаточно сослаться на леммы 10.8 и 10.9.

QED

105

Лемма 10.12. Если p(x)« p1 (x) и q(x)« q1 (x), то Ø p(x)« Ø p1 (x),

(p(x)Ù q(x))« (p1 (x)Ù q1(x)), (p(x)Ú q(x))« (p1 (x)Ú q1(x)) и (p(x)® q(x))« (p1 (x)® q1 (x)).

Доказательство.		Достаточно		воспользоваться	доказательствами
подходящих	пропозициональных			тавтологий(например,		такой:
((a ® b)Ù (c ® d ))® ((a Ù c)® (b Ù d )))			так	же точно, как	в доказательстве
леммы 10.5.
						QED
Лемма 10.13. p « ØØ p .
Доказательство.		И снова достаточно воспользоваться				теоремой о
полноте исчисления высказываний и пропозициональными тавтологиями, на
этот раз такими: a ® ØØa и ØØa ® a .
						QED
Лемма 10.14. Замена подформулы на доказуемо эквивалентную даёт
доказуемо эквивалентную формулу.
Доказательство.		Индукция	по	формулам. Атомарные		формулы

доказуемо эквивалентны, если совпадают, поэтому база тривиальна. Переход состоит в применении двух предыдущих лемм.

QED

Лемма 10.15 (1) Ax p(x)« ØExØ p(x);

(2) Ex p(x)« Ø AxØ p(x).

Доказательство. (а) Докажем

импликацию Ex p(x)® Ø AxØ p(x).

Достаточно вывести импликацию p(x)® Ø AxØ p(x), остальное за нас сделает

ПБ2. Вспомним, что (a ® Øb)® (b ® Øa) (правило контрапозиции) является

пропозициональной тавтологией, поэтому, аналогично доказательству леммы

10.5, достаточно доказать формулу AxØ p(x)® Ø p(x), то есть – заметить, что это – аксиома J.

106

(б) Подставим в только что доказанную формулу вместоp(x) формулу

Ø p(x).

Получим

новую

теоремуExØ p(x)® Ø AxØØ p(x)

(доказательство

которой копирует доказательство исходной теоремы). Согласно леммам 10.13 и

10.14. эта формула доказуемо эквивалентна

формулеExØ p(x)® Ø Axp(x).

Снова использовав правило контрапозиции, получаем ещё одну из требуемых

формул Axp(x)® ØExØ p(x).

(в) Выведем формулу ØExØ p(x)® Ax p(x). Достаточно вывести формулу

ØExØ p(x)® p(x),

остальное за нас сделает ПБ1 (посылок нет). Но правило

контрапозиции (правда, на

сей раз в

форме(Øa ® b)® (Øb ® a))

обращает

требуемую формулу в аксиому Ø p(x)® ExØ p(x).

(г)

Четвёртая

формула получается

из

третьей

так,

какже

вторая

из

первой.

QED

Вернёмся к отмеченному выше ограничению на использование ПБ1. Оно

многое

осложняет. Например,

аналог

леммы 2.3

(о

транзитивности

выводимости)

становится

намного

менее

тривиальным. Действительно

(рассмотрим

простейшую

ситуацию),

пусть р f q , q f r . Тогда

логично

предположить, что

р f r . Однако просто объединив соответствующие выводы

в один, можно получить в этом объединении нарушение рассматриваемого

ограничения:

при

выводе r

из q

могло

произойти

использование первого

правила Бернайса по переменной, свободно входящей в р.

Разумеется,

можно

вообще

запретить

использование

, посылок

содержащих свободные переменные. Однако мы тем самым запретим себе

сказать

в

геометрическом

рассуждении

«рассмотримфразу

пару

пересекающихся прямых». Поэтому нам придётся ещё немного потрудиться.

107

Теорема 10.16. (транзитивность выводимости)

Пусть Р, Q и R – произвольные множества формул, s – формула, "q ÎQ

P f q и Q È R f s . Тогда P È R f s .
Доказательство.	Назовём коллизией ситуацию,	когда в выводеs из
Q È R используется	первое правило Бернайса по	переменнойх, входящей

свободно в некоторую посылку p Î P . Покажем, как можно избавиться от	этой
коллизии, не создав новых. Тем самым теорема будет доказана, так	как

объединение выводов может содержать только конечное число коллизий.
Поскольку	рассматриваемая		последовательность					формул		является
выводом, переменная х не входит свободно ни					в одну формулу, входящую					в
Q È R . Рассмотрим последовательность формул					выводаs из Q È R ,				которая
завершается применением правила			g ® h(x)		и	является	доказательством
		g ® Ax h(x )
формулы g ® Ax h(x). Отметим в			этой последовательности					все	вхождения
переменной х и заменим их все на вхождения переменной x1 , не входящей ни в
один из двух выводов. При этом вывод					останется		выводом, формулы
множества Q È R	не изменятся, а коллизия исчезнет. Но будет							доказана		не
совсем та формула, которая требуется. Для того чтобы получить нужную,
достаточно применить лемму10.5 к доказанной						формулеg ® Ax1 h(x1 )				и
частному случаю Ax1 h(x1 )® Ax h(x) леммы 10.10.

QED

Теорема 10.17. (Лемма о дедукции для исчисления предикатов)

Для любого множества формул Р и формул q и r равносильны:

(1)P f (q ® r );

(2)P È q f r .

Доказательство есть небольшое развитие соответствующего

утверждения для исчисления высказываний. Собственно, осталось только добавить к доказательству импликации (2) Þ (1) случай использования одного

108

из правил Бернайса,

например от выводимости изР формулы q ® (u ® w(y))

перейти к

выводимости

формулыq ® (u ® Ay w(y)),

при

этом y

не

является

параметром формулы u.

Для

случая

ПБ1 достаточно заметить, что

(a ® (b ® c))® ((a Ù b)® c)

является пропозициональной тавтологией(поэтому

– теоремой

исчисления

высказываний

и

т.д как

обычно…). Поэтому

из

формулыq ® (u ® w(y))

выводима

формула (q Ù u)® w(y). Переменная

y

не

является

параметром

формулы

u, и, как

в

доказательстве

транзитивности

выводимости, можно

считать, что

не

является

параметром

формулыq.

Следовательно,

она не

является и параметром формулы (q Ù u). Поэтому можно воспользоваться ПБ1

и	получить	формулу(q Ù u)® Ay w(y). Осталось	воспользоваться
пропозициональной тавтологией ((a Ù b)® c)® (a ® (b ® c)).

Вслучае 2.ПБпридётся воспользоваться пропозициональными

тавтологиями (a ® (b ® c))® ((a Ù b)® c) и ((a Ù b)® c)® (b ® (a ® c)), из

которых следует ещё одна	тавтология: (a ® (b ® c))® (b ® (a ® c)). Поэтому
от формулы q ® (u(y)® w)	можно перейти к формулеu(y)® (q ® w), затем

при помощи ПБ2 перейти к Ey u(y)® (q ® w), и, наконец, снова использовав ту же тавтологию, перейти к q ® (Ey u(y)® w).

QED

В заключение этого параграфа отметим ещё два свойства выводимости,

которые нам понадобятся в дальнейшем.

Теорема 10.18. (Лемма о свежих константах)

Пусть p(x) – формула, с – константа, не использованная ни в формуле р,

ни в посылках (если они есть). Если выводима формула p(c x), то выводима и формула p(x).

Доказательство. Возьмём «свежую» переменную y, не задействованную нигде в выводе, и заменим все вхождения константы на вхождения переменной y. Кванторов по новой переменной ,нетв посылках она не

109

участвует, поэтому вывод останется выводом. Отсюда следует, что выводима и формула p(y x). Из этого следует, что по правилу обобщения выводима и формула Ay p(y x). Применим аксиому Ay p(y x)® (p(y x))(x y). Подстановка в правой части корректна и даёт формулу p(x).

QED

Теорема 10.19. (теорема о расширении сигнатуры)

Пусть р – формула сигнатуры s Í s ¢– содержащейся в другой сигнатуре,

и формула р выводима в исчислении предикатов над сигнатуройs ¢. Тогда р

выводима и в исчислении предикатов над сигнатурой s .

Замечание. Эта теорема позволяет говорить о выводимости формулы

безотносительно к рассматриваемой сигнатуре.

Доказательство. Рассмотрим вывод формулы р в сигнатуре s ¢. Заменим

в этом выводе:
а) Все	константы изs ¢, не	входящие	вs (назовём такие объекты
лишними) на «свежие» переменные.
б) Все	термы вида f (...), где f	– лишняя	функция, – тоже на «свежие»

переменные.

в) Все атомарные формулы видаs(...), где s – лишний предикат, – на любую замкнутую формулу (одну на все случаи).

При этом вывод останется выводом.

QED

110

§11. Полнота исчисления предикатов

В этом параграфе мы докажем важную теорему: всякая общезначимая

формула выводима в исчислении предикатов(теорема Гёделя о полноте

исчисления		предикатов). Большая часть работы				и эскиз		доказательства«
целом»	уже		готов (и	называется «теорема		о	полноте		исчисления
высказываний»).			Более	того,	недостающая (в	доказательстве			полноты
исчисления		высказываний) идея тоже уже встречалась–					в	доказательстве
теоремы		Лёвенгейма-Сколема			о понижении	мощности, Осталось			только

собрать все ингредиенты в нужном месте. При этом не будем бояться повторов

J.

Определение 11.1. Пусть σ – некоторая сигнатура.

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

(2)Теорию Т называется противоречивой, если Т f O . Для того, чтобы доказать, что теория противоречива, достаточно показать, что есть формула р, такая, что Т f р и Т f Ø р .

(3)В противном случае теорию называется непротиворечивой.

(4)Непротиворечивая теория Т называется полной, если для любой

формулы р рассматриваемой сигнатуры либоT f p , либо T f Ø p .

Как мы уже видели, добавляя выводимые формулы прямо в теорию,

можно, не умаляя общности, писать: p ÎT либо Ø p ÎT .

(5)Интерпретация М называется моделью теории Т, если все формулы Т истинны в М.

(6)Теория Т называется совместной, если она имеет модель.

(7)В противном случае теорию Т будем называть несовместной и писать:

T > O (подразумевая: уж если в некоторой интерпретации истинны все формулы теории Т, то там истинна и формулаО; следовательно,

таковой интерпретации не существует).