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

множества А, множества функциональных символов и множества формул,

который, в свою очередь, равен максимальной из трёх мощностей: множества

подмоделью, то есть для любой формулы p(x1, x2 , ..., xm ) и для любой оценки,

в которой в эту формулу подставляются элементы подмножества, истинность

формулы не зависит от ,тогонад множеством или над подмножеством рассматривается формула.

Данное утверждение легко доказывается индукцией по множеству формул. Если формула – атомарная, то это утверждение очевидно. Оно так же очевидно, если формула является логической комбинацией одной или двух формул, для которых утверждение уже доказано. Осталось доказать данное утверждение для формул вида Ex p(x, y1, y2 , ..., ym ) и Ax p(x, y1, y2 , ..., ym ). Как

всегда, достаточно рассмотреть только один из этих вариантов(так как A – то же самое, что NEN ). Но справедливость этого утверждения в первом случае есть, попросту, экзистенциальная замкнутость!

QED

92

Замечание. В силу замечаний, сделанных по ходу рассуждения, в

множества формул (если множество конечно – то не более, чем счётную; это и есть общая формулировка теоремы Лёвенгейма-Сколема об элементарной

интерпретация, но в ней у бесконечного счётного множества множество всех подмножеств – тоже счётно (что противоречит теореме о царе-бюрократе!).

Вдействительности, данное утверждение содержит массу пробелов,

например: слова «произвольное подмножество» следует заменить на текст

«произвольное подмножество, для которого можно указать формулу» (иначе нет веских оснований считать, что оно вообще существует). А формул – счётное количество. Если же обеспечить каждое подмножество формулой, то множество формул сразу станет несчётным.

93

§10. Исчисление предикатов

1. Основные положения

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

формул, описывающих различные реалистичные модели. В нескольких

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

Исчисление предикатов устроено примерно так, какже исчисление

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

Роль тавтологий в исчислении предикатов играют так называемые

общезначимые формулы.

Определение 10.1. (1) Формула р (возможно – не замкнутая, т.е. с

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

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

подстановку терма вместо переменной. Почему, собственно, использование

этого способа не приведёт к появлению некоторых новых формул, т.е. к тому,

что некоторые слова, не являвшиеся формулами в смысле, определённом в §6,

после этого окажутся формулами (и придётся, строго говоря, переделывать всё изложение J).

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

кванторов может привести к забавному эффекту, когда одной и той же буквой

входящая в формулу р – свободной, поэтому это просто не может быть одна и та же переменная!

95

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

дизъюнкцией или конъюнкцией две формулы, в одну из которых некоторая

переменная входит свободно, а в другую – как связанная. Однако после этого

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

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

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

Содержательным способом выхода из описанного затруднения является

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

свободные (не попавшие в области действия ранее появившихся кванторов)

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

которые проще показать на примере, чем описывать словами. Так и сделаем J.

Осталось заменить единственное свободное вхождение переменной х термом:

Ax1Eyq(x1, y, x1 )Ù (Eu r(f (k, g(l, u)), y, u)Ú Ax2 s(x2 )). После этого можно (если

Осложнение состоялось: переменная u, входящая в терм, попала в то, что

естественно считать областью действия квантораЕu. Более того, если бы мы

сначала подставили термt в формулу r(x, y, u), а затем навесили бы на неё

квантор, то переменная u действительно попала бы в область действия этого квантора. При этом смысл формулы был бы совсем иным. Это приводит нас к необходимости всё-таки сформулировать некоторое ограничение, связанное с подстановкой терма вместо переменной.

Определение 10.2. Подстановка терма t на место переменной х в формулу

называется корректной, если в ходе применения этой подстановки никакая

переменная, входящая в t не попадает в область действия одноимённого квантора.

С этого момента все подстановки терма на место переменной считаются

корректными. В рассмотренном же примере следовало, например,

заблаговременно переименовать связанную переменную u (позднее вопрос о переименовании переменных будет рассмотрен подробнее), входящую в р, и

получить формулу AxEyq(x, y, x)Ù (Ew r( f (k, g(l, u)), y, w)Ú Ax s(x)).

Возвращаясь к вопросу, поставленному первым, можно сказать, что

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

Поэтому при проведении (корректной!) подстановки можно считать, что терм

входящие в терм, попадают в области действия кванторов автоматически.

97

(2) В двух случаях подстановка заведомо корректна: в подставляемом терме вообще нет переменных(там есть только константы) или когда в терм входит только та переменная, которую мы и заменяем на терм.

После приведённых утомительных рассуждений мы, при условии, что подстановки являются корректными, можем объявить формулы (А14) и (А15)

двумя новыми аксиомами исчисления предикатов. Нужно ли добавить к исчислению высказываний что-либо ещё?

Да. Внесённые к настоящему моменту изменения допускают, кроме

истинной (и желательной) интерпретации ещё и такую: формула Ax p(x) всегда ложна, а формула Ex p(x) – всегда истинна (при этом аксиомы (А14) и (А15)

обращаются в частные случаи аксиом(А12) и (А13) соответственно). Тем

самым, эти изменения не описывают достаточно «феномен квантора». Для того

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

предоставляет способа учесть такие свойства). Аналогично, во втором правиле,

если уж доказана формулаq(x)® p , то единственный способ сделать так,

чтобы формула р не обязана была бы быть общезначимой, – сделать формулу q(x) всегда ложной: "x Øq(x), или, что то же самое, Ø$x : q(x).

использования свойств х, то оно верно для любого х.

Лемма 10.1. Правило обобщения выводима из первого правила Бернайса

(по правилам исчисления высказываний).

Доказательство. Рассмотрим последовательность формул:

(1)q (в качестве формулыq подойдёт любая выводимая формула без параметров, например, аксиома);

(2)p(x) (посылка);

(3)p(x)® (q ® p(x)) (аксиома (А1));

(4)q ® p(x) ((2)+(3)+МР);

(5)q ® Ax p(x) ((4)+ПБ1);

(6)Ax p(x) ((1)+(5)+МР).

QED

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

Оказывается, что сделанных добавлений(две аксиомы и два правила Бернайса) достаточно для того, чтобы доказать любую общезначимую формулу

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

2. Теорема об адекватности для исчисления предикатов

Теорема 10.2. (теорема об адекватности)

Всякая формула, являющаяся теоремой исчисления предикатов,

общезначима (формально: f p Þ > p ; сравните с теоремой 2.2.).

99

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

корректности, оправданность аксиоматизации (и, возможно, как-нибудь ещё).

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

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

обозначим другую оценку, получающуюся из оценкиπ заменой значения,

которое она принимает на переменной х на значение, которое она принимает на терме t. В терминах §6 (p + (x a [t](p )))Î I (p , x).

Лемма 10.3. (1) Пусть u и t – терм. Тогда [u(t x)](p )= [u](p + (x a [t](p ))).

(2) Пусть р – формула, t – терм, подстановка t на место х в р корректна.

Тогда [p(t x)](p )= [p](p + (x a [t](p ))).

Доказательство. Оба приведённые утверждения совершенно очевидны.

Действительно, значение функции sin(cos x) (аналог формулы p(t x), t = cos x )

при x = 2 (аналог оценки π) равно значению функции sin y (аналог формулы р)

при y = cos 2 (аналог оценки p + (x a [t](p ))).

Тем не менее, формально доказательство надлежит проводить индукцией по термам (1) или по формулам(2). Проведём его аккуратно(в целях показательного устрашения J).

= [f (y1 (t x), ..., y1 (t x))](p )= [f ](p )([y1 (t x)](p ), ..., [yk (t x)](p ))=

= [f ](p + (x a [t](p )))([y1 ](p + (x a [t](p ))), ..., [yk ](p + (x a [t](p ))))= = [f (y1, ..., yk )](p + (x a [t](p )))= [u](p + (x a [t](p ))).

Переходы от первой строчки ко второй и от третьей к четвёртой суть

следствия очевидного ( f (y1, ..., yk ))(t x)= f (y1 (t x), ..., yk (t x)) (сама по себе буква

(2) База. Если формула есть О или I, то утверждение очевидно.

Для атомарной формулы рассуждение практически буквально повторяет

[(s(y1, ..., yk ))](p + (x a [t](p )))=1.

Переходы от формулы р к формуле Ø p , и от формул р и q к формулам

[p](p + (x a [t](p )))=1.