Верещагин Н.К., Шень А. - Языки и исчисления, страница 11

Нам надо решить, сделать ли её истинной или ложной. Если оказалось так, что из Γ выводится формула p, то выборанет: она обязана быть истинной в тех наборах, где формулы из Γистинны (как мы видели при доказательстве корректности). По темже причинам, если из Γ выводится ¬p, то в выполняющем наборепеременная p обязательно будет ложной.Если оказалось так, что для любой переменной p либо она сама,либо её отрицание выводятся из Γ, то выполняющий набор значенийопределён однозначно, и надо только проверить, что он действительно будет выполняющим. А если для каких-то переменных нельзявывести ни их, ни их отрицание, то мы пополним наш набор Γ так,чтобы они, как теперь модно говорить, «определились».Проведём это рассуждение подробно.

Рассмотрим все переменные, входящие в какие-либо формулы из множества Γ; обозначиммножество этих переменных через V . Зафиксируем это множествои до конца доказательства теоремы о полноте будем рассматриватьтолько формулы с переменными из множества V , не оговаривая этого особо.Назовём непротиворечивое множество Γ полным, если для любойформулы F имеет место либо Γ ` F , либо Γ ` ¬F (одновременноэтого быть не может, так как Γ непротиворечиво).Утверждение теоремы о полноте очевидно следует из двух лемм:Лемма 1. Всякое непротиворечивое множество Γ содержится внепротиворечивом полном множестве ∆.Лемма 2. Для всякого непротиворечивого полного множества ∆существует набор значений переменных (из V , напомним), при котором все формулы из ∆ истинны.Доказательство леммы 1.

Основную роль здесь играет такое утверждение: если Γ — непротиворечивое множество, а A — произволь-50Исчисление высказываний[гл. 2]ная формула, то хотя бы одно из множеств Γ ∪ {A} и Γ ∪ {¬A} непротиворечиво. В самом деле, если оба множества Γ ∪ {A} и Γ ∪ {¬A}противоречивы, то Γ ` ¬A и Γ ` ¬¬A, но множество Γ предполагалось непротиворечивым.Если множество переменных V конечно или счётно, то доказательство леммы 1 легко завершить: множество всех формул тогдасчётно, и просматривая их по очереди, мы можем добавлять к Γ либо саму формулу, либо её отрицание, сохраняя непротиворечивость.Получится, очевидно, полное множество.

Чуть менее очевидна егонепротиворечивость: оно было непротиворечиво на каждом шаге,но почему предельное множество (объединение возрастающей последовательности) будет непротиворечиво? Дело в том, что в выводедвух противоречащих друг другу формул может быть задействованотолько конечное число формул из Γ (по определению выводимости:вывод есть конечная последовательность формул). Поэтому все этиформулы должны появиться на некотором конечном шаге конструкции, а это невозможно (на всех шагах множество непротиворечиво).Для случая произвольного набора переменных V рассуждениеможно завершить ссылкой на лемму Цорна: рассмотрим частичноупорядоченное множество, элементами которого будут непротиворечивые множества формул, а порядком — отношение «быть подмножеством».

Рассуждение предыдущего абзаца показывает, что всякаяцепь в этом множестве имеет верхнюю границу (объединение линейно упорядоченного по включению семейства непротиворечивыхмножеств является непротиворечивым множеством). Следовательно, для любого непротиворечивого множества найдётся содержащееего максимальное непротиворечивое множество. А оно обязано бытьполным (иначе его можно расширить, добавив A или ¬A).Лемма 1 доказана.Доказательство леммы 2. Пусть Γ — непротиворечивое полноемножество. Тогда для каждой переменной (из множества V ) ровноодна из формул p и ¬p выводима из Γ.

Если первая, будем считатьпеременную p истинной, если вторая — ложной. Тем самым появляется некоторый набор ν значений переменных, и надо только проверить, что любая формула из Γ при таких значениях переменныхистинна. Это делается так: индукцией по построению формулы Aмы доказываем, чтоA истинна на наборе ν ⇒ Γ ` A,A ложна на наборе ν ⇒ Γ ` ¬A.[п. 2]Второе доказательство теоремы о полноте51Базис индукции (когда A — переменная) обеспечивается определением истинности переменных. Для шага индукции используется таже лемма, что и при доказательстве полноты с помощью разбораслучаев.

Пусть, например, A имеет вид (B ∧ C). Тогда есть четыре возможности для истинности B и C. В одном из них (когда B иC истинны на ν) по предположению индукции мы имеем Γ ` B иΓ ` C, откуда Γ ` (B ∧ C), то есть Γ ` A. В другом (B истинна,C ложна) предположение индукции даёт Γ ` B и Γ ` ¬C, откудаΓ ` ¬(B ∧ C), то есть Γ ` ¬A. Аналогично разбираются и все остальные случаи и логические связки. Лемма 2 доказана, и тем самымзавершено доказательство теоремы 20.

Мы доказали, что всякое непротиворечивое множество формулсовместно. Отсюда легко следует, что всякая тавтология являетсятеоремой. В самом деле, если ϕ — тавтология, множество {¬ϕ} несовместно, поэтому из ¬ϕ выводится противоречие, поэтому ` ¬¬ϕ, ипо закону снятия двойного отрицания ` ϕ.Кроме того, теорема о полноте во второй формулировке имееттакое очевидное следствие:Теорема 21 (теорема компактности для исчисления высказываний).Пусть Γ — множество формул, всякое конечное подмножество которого совместно. Тогда и всё множество Γ совместно. Как мы знаем, несовместность равносильна противоречивости,а вывод противоречия по определению может использовать лишьконечное число формул.

Поскольку в формулировке теоремы компактности нет упоминания об исчислении высказываний (речь идёт лишь об истинностиформул, а не о выводимости), возникает вопрос, нельзя ли её доказать непосредственно.29. Дайте прямое доказательство теоремы компактности для случая,когда переменных в множестве V конечное число. (Указание: любое несовместное множество имеет несовместное подмножество мощности не больше 2|V | .)Для случая счётного числа переменных можно воспользоватьсякомпактностью (в топологическом смысле слова) канторовского пространства.

Его элементами являются бесконечные последовательности нулей и единиц. Если две последовательности отличаются в n-йпозиции, а все предыдущие члены совпадают, то расстояние между ними считается равным 2−n . Это метрическое пространство компактно.Пусть V содержит счётное число переменных. Последователь-52Исчисление высказываний[гл. 2]ность значений переменных будем рассматривать как точку канторовского пространства; формуле соответствует область, состоящаяиз точек, где формула истинна. Поскольку формула содержит лишьконечное число переменных, эта область является замкнутым и открытым множеством одновременно. Пусть имеется множество формул, любое конечное подмножество которого совместно. Это значит,что соответствующие формулам подмножества канторовского пространства образуют, как говорят, центрированную систему (любоеконечное их число имеет общую точку).

А в компактном пространстве любое центрированное семейство замкнутых множеств имеетобщую точку (иначе их дополнения образуют открытое покрытие, укоторого нет конечного подпокрытия). Эта их общая точка и будетнабором значений, на котором все формулы истинны.То же самое рассуждение годится и для несчётного множествапеременных, но тогда возникает несчётное произведение двухточечных пространств, которое является топологическим пространством(но не метрическим); надо заметить, что это пространство компактно по теореме Тихонова, после чего наше рассуждение проходит.Для счётного набора переменных теорема компактности связана с так называемой леммой Кёнига. Конечные последовательностинулей и единиц (включая пустую последовательность) мы называем двоичными словами. Двоичным деревом мы называем множестводвоичных слов, которое вместе со всяким словом содержит все егоначала (начальные отрезки).

Бесконечной ветвью двоичного дерева T мы называем бесконечную последовательность нулей и единиц,любое конечное начало которой принадлежит T .Теорема 22 (лемма Кёнига). Любое бесконечное дерево имеет бесконечную ветвь. Говоря о бесконечности дерева, мы имеем в виду, что соответствующее множество бесконечно. Отсюда следует, что оно содержит слова сколь угодно большой длины.

Пусть p1 , p2 , . . . — счётноемножество переменных, которые принимают значения 0 или 1. Длякаждого n рассмотрим формулу ϕn , которая утверждает, что словоp1 p2 . . . pn принадлежит дереву T (это возможно, так как любая булева функция выразима формулой). Поскольку T — дерево, ϕi влечётϕj при j < i. Любое конечное множество формул вида ϕi равносильно, таким образом, одной формуле с максимальным i и потомусовместно.