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

Для уяснения смысла аксиом и правил вывода введем понятие интерпретации языка и исчисления α.

Определение 9.25. Под Интерпретацией языка исчисления α понимают любое множество М с зафиксированным отображением u сигнатуры σ во множество операций и предикатов, определенных на М, при котором символу N-арной операции F из σ соответствует N-арная операция FU, определенная на множестве М, а символу N-арного предиката Р из σ N-арный предикат РU на М. Образ множества σ при отображении u обозначим через σu. В частности, образом констант из σ при u будут нуль-арные операции на М, т. е. некоторые элементы из М.

Если (М, u) — интерпретация языка α, то, заменив в любой формуле языка α константы, символы операций и символы предикатов их образами при u и условившись переменным из Х придавать значения из множества М, мы получим формулу АU алгебры предикатов на алгебраической системе М(σu), и можно говорить о выполнимости, истинности или ложности этой формулы на системе М(σu).

Определение 9.26. Формула А исчисления предикатов называется Выполнимой, истинной, ложной в интерпретации (М, u), если соответственно выполнима, истинна, ложна формула АU на алгебраической системе М(σu).

Определение 9.27. Формула А исчисления предикатов α называется Тождественно истинной, если она истинна во всех интерпретациях исчисления α.

Естественно возникает вопрос о соотношении между классами доказуемых и истинных формул исчисления предикатов. Ответ на этот вопрос можно получить из следующих теорем.

Теорема 9.28. Если каждая формула множества формул Т истинна в некоторой интерпретации (М, u) исчисления α и T├─ A, то А — истинна в (М, u).

Доказательство. Для простоты записей условимся считать, что операции и предикаты на М обозначены теми же буквами, что и соответствующие им символы операций из σ. Тогда u — тождественное отображение и в записи АU индекс u можно опускать.

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

А) все аксиомы истинны;

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

Истинность аксиом первых четырех групп аксиом доказывается одним методом. Проиллюстрируем его на аксиоме I1: A ® (B ® A).

Заменив в А, В свободные вхождения переменных элементами из М, получим высказывания, имеющие вполне определенные значения £ и ß (каждое из £, ß есть «и» или «л»). Перебирая всевозможные наборы значений «и» и «л» для £, ß мы непосредственной проверкой (пользуясь определением операции ®) убедимся в том, что при любых £, ß £ ® (ß ® £) º И.

Отсюда следует, что аксиома I1 истинна в интерпретации (М, u).

Докажем теперь истинность аксиомы

V1 : "X A(X) ® A(T),

Где T — терм, свободный для Х в А(Х). Пусть Х, Х1, …, ХN суть все переменные, имеющие свободные вхождения в А(Х) и XI1, …, XIm — все переменные, участвующие в образовании терма T. Так как T свободен для Х в А(Х), то все вхождения переменных XI1, …, Xim в терм T останутся свободными при подстановке T вместо Х в формулу А(Х). В связи с этим запишем:

A(T) = A(T(XI1, …, XIm), Х1, …, ХN).

Допустим, что формула V1 не истинна в интерпретации (М, u). Это означает, что при некотором наборе значений переменных Х1 = A1, …, ХN = AN, XI1 = AI1, …, Xim = AIm формула "X A(X) принимает значение «И», а формула A(T) — значение «Л». Если обозначить через B значение терма T при XI1 = AI1, …, XIm = AIm, то будем иметь: с одной стороны, A(Х0, A1, …, AN) является истинным высказыванием при любом значении Х0 ΠМ, а с другой стороны, высказывание A(B, A1, …, AN) — ложно. Полученное противоречие и доказывает наше утверждение.

Аналогично доказывается, что правила вывода позволяют из истинных формул в интерпретации (М, u) получать снова истинные формулы, т. е.:

1) если истинны формулы А и А ® В, то истинна и формула В;

2) если истинна формула В ® А(Х) и Х не имеет свободных вхождений в В, то истинна формула В ® "Х А(Х);

3) если истинна формула А(Х) ® В и Х не имеет свободных вхождений в В, то истинна и формула $Х А(Х) ® В.

Теорема доказана.

Следствие 9.29. Всякая доказуемая формула исчисления предикатов α является истинной в любой интерпретации (М, u) исчисления α.

Замечание. Теорема и следствие теряют силу, если в аксиомах V1 и V2 не накладывать ограничений на терм T или в правилах "-введения и $-удаления разрешить свободные вхождения Х в В. Приведем соответствующие примеры.

1. Пусть множество натуральных чисел N, A(X) = $Y (X < Y) и T = X + Y — терм, не свободный для Х в А(Х), поскольку свободное вхождение буквы Х в А(Х) находится в области действия квантора $ по букве У, входящий в терм T. Нетрудно видеть, что формула "X A(X) ® A(T), или подробнее, "X($Y(X < Y)) ® $Y(X + Y < Y) ложна в арифметике.

2. В той же интерпретации, положим B = (X £ Y), A = (X £ Y + 1). Тогда имеем: формула В ® А истинна на N, а формула В ® "XА ложна, поскольку, например, при Х = 2, У = 3 имеем (2 £ 3) º И, "X (X £ 4) º Л.

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

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

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

Теперь естественно возникает вопрос: не слишком ли мало аксиом и правил вывода мы взяли при построении исчисления предикатов? Так, из доказательства предыдущей теоремы видно, что если бы нашлась формула А, не доказуемая в исчислении предикатов, но истинная в любой его интерпретации, то, присоединив А к системам аксиом, мы получили бы более сильное и непротиворечивое логическое исчисление. Однако ниже будет показано, что такой формулы А не существует, а именно имеет место следующая теорема Геделя о полноте исчисления предикатов.

Теорема 9.31. Если формула исчисления предикатов истинна во всех его интерпретациях, то она доказуема в исчислении предикатов.

Для Доказательства этой теоремы введем сначала некоторые понятия и докажем одно общее утверждение (см. теорему 9.7.11).

Определение 9.32. Множество формул Т исчисления α называется Противоречивым, если существует такая формула А языка α, что Т├─ . В противном случае Т называется непротиворечивым.

Определение 9.33. Множество формул Т исчисления α называется Выполнимым, если существует интерпретация, в которой все формулы из Т принимают истинное значение хотя бы при одной (общей для всех формул из Т) замене переменных.

Определение 9.34. Множество формул Т исчисления α называется Полным, если для каждой замкнутой формулы языка α имеет место Т├─ А или Т ├─ .

Теорема 9.35. Всякое непротиворечивое множество S замкнутых формул исчисления α выполнимо.

Доказательство. Добавим к множеству символов языка α еще счетное множество констант (символов нуль-арных операций) ß = {B0, B1, B2, …}.

Получим новый язык α1 в сигнатуре σ1 = σ È ß. Заменяя в аксиомах и правилах вывода исчисления α формулы языка α1, мы получим новое логическое исчисление, которое обозначим той же буквой α1. Из определения языка α1 видно, что все доказанные факты об исчислении α (в частности, все доказанные формулы и дополнительные правила вывода) сохраняются и в α1. Так как язык α1 включает в себя α, то S можно рассматривать как множество предложений языка α1. Легко видеть, что S будет непротиворечивым и в исчислении α1. Действительно, если в α1 из S выводима формула , то, заменив в формулах вывода из S все константы из ß переменными, не участвующими в этом выводе, мы получим вывод в α из S формулы , где В получается из А указанной заменой констант. Чтобы убедиться в этом, достаточно заметить, что указанная замена аксиомы переводит в аксиомы и сохраняет свойство формулы быть непосредственным следствием предыдущих формул. Таким образом, S непротиворечиво в α1.

Теперь расширим определенным образом множество S. Для этого занумеруем все замкнутые формулы исчисления α1: А0, А1, А2, …

По формуле А0 и системе S построим множество формул S0, положив:

Где BI0 — символ с наименьшим номером из ß, не встречающийся в А0. Из определения S0 имеем: S ΠS0 и S0 ├─ А0 или S0 ├─ .

Покажем, что S0 непротиворечиво. Допустим, что в α1 S0 ├─ . В соответствии с определением S0 рассмотрим три случая.

1. S ├─ `А0. Тогда S0 = S È {} и из (9.5) имеем: S, `А0 ├─. Отсюда по следствию из теоремы дедукции получаем S ├─ , что невозможно в силу непротиворечивости S.

2. невыводима из S и А0 не имеет вида $Х В0(Х). Тогда S0 = S È {А0} и мы точно так же, как и в случае «а», получим S ├─ , что противоречит условию.

3.  невыводима из S и А0 = $Х В0(Х). Тогда S0 = = S È {А0, B0, (BI0)}, и потому S, А0, B0, (BI0) ├─ . Так как формула B0 (BI0) замкнута, то тем же приемом, что и выше, получим S, А0 ├─ . Так как BI0 не входит в А0 и в формулы из S, то, повторив весь вывод с заменой BI0 на переменную XJ, не входящую в участвующие в выводе формулы, мы получим S, А0 ├─ , или S ├─ А0 ® . Дополним вывод А0 ®  из S формулами:

А0 ® "XJ	(правило "-введения)
"XJ ®	(аксиома)
А0 ®	(правило силлогизма)
А0 ® "X	(правило "-введения)
"X ®	(правило $-отрицания)
А0 ®	(правило силлогизма)

Поскольку $XB0(X) = А0, то мы получили вывод из S формулы А0 ® , т. е. S, А0├─ `А0. А так как S, А0 ├─ А0, то по правилу умножения формул S, А0├─ А0. Отсюда следует: S├─ А0, и мы снова пришли к противоречию с условием. Тем самым мы закончили доказывать непротиворечивость множества формул S0.

Далее, по А1 и S0 мы аналогично построим непротиворечивое множество S1 такое, что: S0 Ì S1, S1├─ А1 или S1├─ .

Продолжая этот процесс, мы получим последовательность непротиворечивых множеств формул S0 Ì S1 Ì S2 Ì … таких, что SI├─ АI и SI├─. Следовательно, Есть непротиворечивое и полное множество формул.

Теперь построим интерпретацию исчисления предикатов α, в которой истинны все формулы из α. В качестве основного множества возьмем множество М термов языка α1, в которых нет предметных переменных — это так называемые замкнутые термы языка α1. Определим на М операции FU и предикаты РU, соответствующие символам операций F и предикатов Р из α.

Если А — символ 0-арной операции из σ, то положим АU = А. Если F — символ N-арной операции из σ, P — символ N-арного предиката и T1, …, TN — термы из М, то положим FU (T1, …, TN) = F(T1, …, TN):

Тем самым определена интерпретация (М, σ) исчисления α1, а потому и α.

Теперь индукцией по рангу формулы А докажем, что для любой замкнутой формулы языка α1:

Т├─ А в α1 Û АU º И в (М, σ). (9.7)

Для упрощения записи верхний индекс u у формул будем опускать. Если А = Р(T1, …, TN) — элементарная формула, то (9.7) верно по определению предиката Р.

Пусть А — замкнутая формула ранга R > 0. В зависимости от последней операции в А возможны шесть случаев.

1. А = А1А2. Используя определение конъюнкции, предположение индукции и правила умножения и разделения формул, получим: А º И Û А1 = И, А2 = И Û Т├─ А1, Т├─ А2 Û Т├─ А1А2.

2. А = А1 Ú А2. Если А1 Ú А2 º И, то А1 = И или А2 = И. Тогда по предположению индукции Т├─ А1 или Т├─ А2, а поэтому и Т├─ А1 Ú А2. Обратно, пусть Т├─ А1 Ú А2. Если Т├─ А1 или Т├─ А2, то по предположению индукции А1 º И или А2 º И, а потому и А º И. В противном случае, в силу полноты системы Т имеем: Т├─, Т├─ . Тогда по правилам умножения формул и де Моргана получим: Т├─ `, Т├─ . Итак, имеем: Т├─ А1 Ú А2, Т├─ , что невозможно в силу непротиворечивости Т.

3. А =`А1. Учитывая предположение индукции и полноту системы формул Т, получим: А º И Û А º Л Û Т├─ `А1 Û Т├─ А.

4. А = А1 ® А2. В этом случае, используя предположение индукции и правила введения посылки, контрапозиции и двойного отрицания, получим: А º И Û А1 º Л или А2 º И Û Т├─ `А1, или Т├─ `А2 Û Т├─ `А2 ®`А1 или Т├─ А2 ® А1 Û Т├─ А.

5. А = "ХА1(Х). Если А º И, то А1(T) º И при любом T ΠM. Тогда по предположению индукции Т├─ А1(T) для всех T ΠM. Допустим, что T ├─. Тогда по правилу "-отрицания T ├─ и по построению множества Т в Т существует формула при некоторой константе B ΠM. В итоге мы получили: Т├─ А1(T) при любом T ΠM и Т├─ А1(B) при B ΠM, что невозможно в силу непротиворечивости Т. Следовательно, T ├─ "ХА1(Х). Обратно, пусть T ├─ "ХА1(Х). Если "ХА1(Х) ¹ И, то А1(T) º Л при некотором T ΠM. Тогда по предположению индукции Т├─ . Отсюда по аксиоме V2 и по правилу "-отрицания получим T ├─ и T ├─ , что невозможно в силу непротиворечивости Т.

6. А = $ХА1(Х). Если А º И, то А1(T) º И при некотором T ΠM и по предположению индукции Т├─ А1(T). Отсюда, используя аксиому V2, получим T ├─ $ХА1(Х), т. е. Т├─ А. Обратно, если Т├─ А, то в силу непротиворечивости Т получим, что не выводима из Т. Тогда, по построению Т, в Т содержится формула А1(B) при некотором B ΠM. По предположению индукции А1(B) º И, а потому и $ХА1(Х) = И.

Таким образом, все замкнутые формулы языка α, выводимые из Т, истинны в интерпретации (М, u). А так как S Ì T, то и все формулы из S истинны в (М, u), т. е. множество S выполнимо и теорема доказана.

Теперь можно доказать и теорему Гёделя о полноте исчисления α. Пусть А — формула исчисления предикатов α и А º И в любой интерпретации исчисления α. Если Х1, …, ХN суть все переменные, имеющие свободные вождения в А, то формула В = "Х1, …, ХNА также истинна в любой интерпретации α, а потому формула`В ложна в любой интерпретации α. Отсюда следует, что множество формул невыполнимо.

Тогда по теореме о выполнимости множество противоречиво, т. е. существует формула С языка α, такая, что ├─.

Но тогда по следствию из теоремы дедукции ├─ B. Теперь, применяя n раз аксиому V1 и правило заключения, получим ├─ A, что и доказывает теорему Гёделя.

В качестве других следствий теоремы о выполнимости докажем так называемую теорему о совместной выполнимости и локальную теорему Мальцева.

Теорема 9.36 (о совместной выполнимости). Если замкнутая формула А исчисления α истинна в любой интерпретации α, в которой истинны формулы некоторого Т замкнутых формул, то Т├─ А.

Доказательство. Из условия видно, что множество формул Т U  невыполнимо. Значит, по теореме о выполнимости множество противоречиво, т. е. T, ├─ для некоторой формулы В. Отсюда по следствию из теоремы дедукции Т├─ А.

Теорема Мальцева (9.37). Множество замкнутых формул S исчисления α выполнимо тогда и только тогда, когда выполнимо любое его конечное подмножество.

Доказательство. Выполнимость конечных подмножеств выполнимого множества формул очевидна. Докажем обратное утверждение. Допустим, что выполнимо любое конечное подмножество формул множества S, а само S невыполнимо. Тогда по теореме о выполнимости оно противоречиво, т. е. найдется такая формула А, что S├─ .

Но тогда выводима лишь из конечного подмножества S1 Ì S формул, участвующих в выводе формулы из S. Следовательно, нашлось противоречивое конечное множество формул из S. Если бы S было выполнимым, то по теореме 9.28 нашлась бы интерпретация α, в которой была бы истинной формула , что невозможно. Полученное противоречие и доказывает теорему.

< Предыдущая		Следующая >