Исчисление высказываний

Теорема 18 (О полноте ИВ). Всякая тавтология есть теорема исчисления высказываний.

Мы предложим несколько альтернативных доказательств этой теоремы. Но прежде всего мы должны приобрести некоторый опыт построения выводов и использования аксиом.

Лемма 1. Какова бы ни была формула $$D$$, формула $${(D\to D)}$$ является теоремой.

Докажем лемму, предъявив вывод формулы $$(D\to D)$$ в исчислении высказываний.

Как видно, вывод даже такой простой тавтологии, как $$(D\to D)$$, требует некоторой изобретательности. Мы облегчим себе жизнь, доказав некоторое общее утверждение о выводимости.

Часто мы рассуждаем так: предполагаем, что выполнено какое-то утверждение $$A$$, и выводим различные следствия. После того как другое утверждение $$B$$ доказано, мы вспоминаем, что использовали предположение $$A$$, и заключаем, что мы доказали утверждение $$A\to B$$. Следующая лемма, называемая иногда "леммой о дедукции", показывает, что этот подход правомерен и для исчисления высказываний.

Пусть $$\Gamma$$ — некоторое множество формул. Выводом из $$\Gamma$$ называется конечная последовательность формул, каждая из которых является аксиомой, принадлежит $$\Gamma$$ или получается из предыдущих по правилу MP. (Другими словами, мы как бы добавляем формулы из $$\Gamma$$ к аксиомам исчисления высказываний — именно как формулы, а не как схемы аксиом.) Формула $$A$$ выводима из $$\Gamma$$, если существует вывод из $$\Gamma$$, в котором она является последней формулой. В этом случае мы пишем $$\Gamma\vdash A$$. Если $$\Gamma$$ пусто, то речь идет о выводимости в исчислении высказываний, и вместо $$\varnothing\vdash A$$ пишут просто $$\vdash A$$.

Лемма 2 (о дедукции). Пусть $$\Gamma$$ — множество формул. Тогда $$\Gamma\vdash A\to B$$ тогда и только тогда, когда $$\Gamma\cup\{A\}\vdash B$$.

В одну сторону утверждение почти очевидно: пусть $$\Gamma\hm\vdash (A\to B)$$. Тогда и $$\Gamma, A\vdash(A\to B)$$. (Для краткости мы опускаем фигурные скобки и заменяем знак объединения запятой.) По определению $$\Gamma, A\vdash A$$, откуда по MP получаем $$\Gamma, A\vdash B$$.

Пусть теперь $$\Gamma,A\vdash B$$. Нам надо построить вывод формулы $$A\to B$$ из $$\Gamma$$. Возьмем вывод $$C_1,C_2,\ldots,C_n$$ формулы $$B=C_n$$ из $$\Gamma, A$$. Припишем ко всем формулам этого вывода слева посылку $$A$$:$$(A\to C_1), (A\to C_2),\dots,(A\to C_n).$$ Эта последовательность оканчивается на $$(A\to B)$$. Сама по себе она не будет выводом из $$\Gamma$$, но из нее можно получить такой вывод, добавив недостающие формулы, и тем самым доказать лемму о дедукции.

Будем добавлять эти формулы, двигаясь слева направо. Пусть мы подошли к формуле $$(A\to C_i)$$. По предположению формула $$C_i$$ либо совпадает с $$A$$, либо принадлежит $$\Gamma$$, либо является аксиомой, либо получается из двух предыдущих по правилу MP. Рассмотрим все эти случаи по очереди.

(1) Если $$C_i$$ есть $$A$$, то очередная формула имеет вид $$(A\hm\to A)$$. По лемме 1 она выводима, так что перед ней мы добавляем ее вывод.

(2) Пусть $$C_i$$ принадлежит $$\Gamma$$. Тогда мы вставляем формулы $$C_i$$ и $$C_i\to(A\to C_i)$$ (аксиома 1). Применение правила MP к этим формулам дает $$(A\to C_i)$$, что и требовалось.

(3) Те же формулы можно добавить, если $$C_i$$ является аксиомой исчисления высказываний.

(4) Пусть, наконец, формула $$C_i$$ получается из двух предыдущих формул по правилу MP. Это значит, что в исходном выводе ей предшествовали формулы $$C_j$$ и $$(C_j\hm\to C_i)$$. Тогда в новой последовательности (с добавленной посылкой $$A$$ ) уже были формулы $$(A\to C_j)$$ и $$(A\to(C_j\hm\to C_i))$$. Поэтому мы можем продолжить наш $$\Gamma$$ -вывод, написав формулы

$$((A\to(C_j\to C_i))\to((A\to C_j)\to (A\to C_i))$$ (аксиома 2);

$$((A\to C_j)\to (A\to C_i))$$ (modus ponens);

$$(A\to C_i)$$ (modus ponens).

Итак, во всех четырех случаях мы научились дополнять последовательность до вывода из $$\Gamma$$, так что лемма о дедукции доказана.

20. Докажите, что для любых формул $$A,B,C$$ формула$$(A\to B)\to((B\to C)\to (A\to C))$$ выводима в исчислении высказываний. (Указание: используйте лемму о дедукции и тот факт, что $${A\to B}, {B\to C}, A \hm\vdash C$$.)

21. Докажите, что если $$\Gamma_1\vdash A$$ и $$\Gamma_2,A\vdash B$$, то $$\Gamma_1\hm\cup\Gamma_2\hm\vdash B$$. (Это свойство иногда называют "правилом сечения" (cut);говорят, что формула $$A$$ "отсекается" или "высекается". Сходные правила играют центральную роль в теории доказательств, где формулируется и доказывается "теорема об устранении сечения" для различных логических систем.)

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

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

Другие аксиомы описывают свойства логических связок. Аксиомы $$3$$ и $$4$$ говорят, какие следствия можно вывести из конъюнкции ( $$A\land B \vdash A$$ и $$A\land B \vdash B$$ ). Напротив, аксиома 5 говорит, как можно вывести конъюнкцию. Из нее легко следует такое правило: если $$\Gamma\vdash A$$ и $$\Gamma\vdash B$$, то $$\Gamma\vdash(A\land B)$$ (применяем эту аксиому и дважды правило MP). Часто подобные правила записывают так:$$\frac{\Gamma\vdash A \qquad \Gamma\vdash B}{\Gamma\vdash A\land B}$$ (над чертой пишут "посылки" правила, а снизу — его "заключение", вытекающее из посылок).

23. Докажите, что формула $$(A\hm\to{(B\to C)})\hm\to ({(A\land B)}\hm\to C)$$, так же как и обратная к ней формула (в которой посылка и заключение переставлены), являются теоремами исчисления высказываний. Докажите аналогичное утверждение про формулы $${(A\land B)}\hm\to{(B\land A)}$$ и $$((A\land B)\land C)\hm\to (A\hm\land{(B\land C)})$$.

Аксиомы 6-7 позволяют утверждать, что $$A\vdash A\lor B$$ и $$B\vdash A\lor B$$. Аксиома 8 обеспечивает такое правило:$$\frac{\Gamma, A \vdash C \qquad \Gamma,B\vdash C}{\Gamma, A\lor B\vdash C}$$ Оно соответствует такой схеме рассуждения: "Пусть выполнено $$A\lor B$$. Разберем два случая. Если выполнено $$A$$, то $$\hole$$ и потому $$C$$. Если выполнено $$B$$, то $$\hole$$ и потому $$C$$. В обоих случаях верно $$C$$. Значит, $$A\lor B$$ влечет $$C$$."

Обоснование: дважды воспользуемся леммой о дедукции, получив $$\Gamma\hm\vdash (A\hm\to C)$$ и $$\Gamma\hm\vdash(B\hm\to C)$$, а затем дважды применим правило MP к этим формулам и аксиоме $${(A\to C)}\hm\to ({(B\to C)}\hm\to ({(A\lor B)}\hm\to C))$$. Получив формулу $${(A\lor B)}\hm\to C$$, опять применим правило MP к ней и формуле $$(A\lor B)$$.

24. Докажите, что следующие формулы, а также обратные к ним (меняем местами посылку и заключение) являются теоремами исчисления высказываний:$$\begin{align*} ((A\lor B)\to C)\to ((A\to C)\land(B\to C)),\\ ((A\land C)\lor (B\land C))\to ((A\lor B)\land C),\\ ((A\lor C)\land (B\lor C))\to ((A\land B)\lor C). \end{align*}$$

У нас остались еще три аксиомы, касающиеся отрицания. Аксиома 9 гарантирует, что из противоречивого набора посылок можно вывести что угодно: если $$\Gamma\vdash A$$ и $$\Gamma\vdash\lnot A$$, то $$\Gamma\vdash B$$ для любого $$B$$. Аксиома 10, напротив, объясняет, как можно вывести отрицание некоторой формулы $$A$$: надо допустить $$A$$ и вывести два противоположных заключения $$B$$ и $$\lnot B$$. Точнее говоря, имеет место такое правило:$$\frac{\Gamma, A\vdash B\qquad \Gamma, A\vdash\lnot B} {\Gamma \vdash \lnot A}$$ (в самом деле, дважды применяем лемму о дедукции, а затем правило MP с аксиомой 10).

Аксиомы 9 и 10 позволяют вывести некоторые логические законы, связанные с отрицанием. Докажем, например, что (для любых формул $$A$$ и $$B$$ ) формула$$(A\to B)\to(\lnot B\to\lnot A)$$ ("закон контрапозиции") является теоремой исчисления высказываний. В самом деле, по лемме о дедукции достаточно установить, что$$(A\to B), \lnot B \vdash \lnot A.$$ Для этого, в свою очередь, достаточно вывести из посылок $$(A\hm\to B), \lnot B, A$$ какую-либо формулу и ее отрицание (в данном случае формулы $$B$$ и $$\lnot B$$ ).

25. Выведите формулы $$A\to\lnot\lnot A$$ и $$\lnot\lnot\lnot A\to\lnot A$$ с помощью аналогичных рассуждений.

Последняя аксиома, называемая "законом исключенного третьего", и иногда читаемая как "третьего не дано" (tertium non datur в латинском оригинале), вызвала в первой половине века большое количество споров. (См. раздел об интуиционистской логике,в которой этой аксиомы нет.)

Из нее можно вывести закон "снятия двойного отрицания", имеющий вид $$\lnot\lnot A\to A$$. В самом деле, достаточно показать, что $$A\lor \lnot A, \lnot\lnot A \vdash A$$. По правилу разбора случаев, достаточно установить, что $$A, \lnot\lnot A \vdash A$$ (это очевидно) и что $$\lnot A, \lnot\lnot A \vdash A$$ (а это верно, так как из двух противоречащих друг другу формул выводится что угодно с помощью аксиомы 8).

26. Докажите, что формула $$(\lnot B\to\lnot A)\to(A\to B)$$ является теоремой исчисления высказываний. (Указание: используйте закон исключенного третьего.)

27. Исключим из числа аксиом исчисления высказываний закон исключенного третьего, заменив его на закон снятия двойного отрицания. Покажите, что от этого класс выводимых формул не изменится.

28. Докажите, что при наличии аксиомы исключенного третьего (11) аксиома (10) является лишней — ее (точнее следовало бы сказать: любой частный случай этой схемы аксиом) можно вывести из остальных аксиом.

Теперь уже можно доказать теорему о полноте: всякая тавтология выводима в исчислении высказываний. Идея доказательства состоит в разборе случаев. Поясним ее на примере. Пусть $$A$$ — произвольная формула, содержащая переменные $$p,q,r$$. Предположим, что $$A$$ истинна, когда все три переменные истинны. Тогда, как мы докажем,$$p,q,r \vdash A.$$ Вообще каждой строке таблицы истинности для формулы $$A$$ соответствует утверждение о выводимости. Например, если $$A$$ ложна, когда $$p$$ и $$q$$ ложны, а $$r$$ истинно, то$$\lnot p, \lnot q, r \vdash \lnot A.$$ Если формула $$A$$ является тавтологией, то окажется, что она выводима из всех восьми возможных вариантов посылок. Пользуясь законом исключенного третьего, можно постепенно избавляться от посылок. Например, из $$p,q,r\hm\vdash A$$ и $$p,q,\lnot r\vdash A$$ можно получить $$p,q,(r\lor\lnot r)\vdash A$$, то есть $$p,q\vdash A$$ (поскольку $$(r\lor\lnot r)$$ является аксиомой).

Проведем это рассуждение подробно. Для начала докажем такую лемму:

Лемма 3. Для произвольных формул $$P$$ и $$Q$$$$\begin{align*} P,Q\vdash (P\land Q); P,Q\vdash (P\lor Q);\\ P,\lnot Q\vdash \lnot (P\land Q); P,\lnot Q\vdash (P\lor Q);\\ \lnot P,Q\vdash \lnot (P\land Q); \lnot P,Q\vdash (P\lor Q);\\ \lnot P, \lnot Q;\vdash \lnot (P\land Q) \lnot P, \lnot Q\vdash \lnot (P\lor Q);\\[1.5ex] P,Q\vdash (P\to Q);\\ P,\lnot Q\vdash \lnot (P\to Q); P\vdash \lnot (\lnot P);\\ \lnot P,Q\vdash (P\to Q); \lnot P\vdash \lnot P.\\ \lnot P, \lnot Q\vdash (P\to Q); \end{align*}$$

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

После предпринятой нами тренировки доказать эти утверждения несложно. Например, убедимся, что $$\lnot P\hm\vdash\lnot(P\land Q)$$. Для этого достаточно вывести два противоположных утверждения из $$\lnot P, (P\land Q)$$ — ими будут утверждения $$P$$ и $$\lnot P$$.

Проверим еще одно утверждение: $$\lnot P, \lnot Q\vdash\lnot (P\lor Q)$$. Нам надо вывести два противоположных утверждения из $$\lnot P, \lnot Q, (P\lor Q)$$. Покажем, что из $$\lnot P, \lnot Q, (P\lor Q)$$ следует все, что угодно. По правилу разбора случаев достаточно убедиться, что из $$\lnot P, \lnot Q, P$$ и из $$\lnot P, \lnot Q, Q$$ следует все, что угодно — но это мы знаем.

Утверждения, касающиеся импликации, просты: в самом деле, мы знаем, что $$Q\vdash (P\to Q)$$ благодаря аксиоме 1, а $$\lnot P\vdash (P\to Q)$$ благодаря аксиоме 9.

Остальные утверждения леммы столь же просты.

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

Лемма 4. Пусть $$A$$ — произвольная формула, составленная из переменных $$p_1,\ldots,p_n$$. Тогда для каждой строки таблицы истинности формулы $$A$$ имеет место соответствующее утверждение о выводимости: если $$\varepsilon_1,\dots,\varepsilon_n, \varepsilon\hm\in\{0,1\}$$, и значение формулы $$A$$ есть $$\varepsilon$$ при $$p_1=\varepsilon_1,\dots,p_n\hm=\varepsilon_n$$, то$$\lnot_{\varepsilon_1} p_1,\dots,\lnot_{\varepsilon_n} p_n \vdash \lnot_{\varepsilon A},$$ где $$\lnot_u \varphi$$ обозначает $$\varphi$$ при $$u=1$$ и $$\lnot \varphi$$ при $$u=0$$ (напомним, что $$1$$ обозначает истину, а $$0$$ — ложь).

Лемма очевидно доказывается индукцией по построению формулы $$A$$. Мы имеем посылки, утверждающие истинность или ложность переменных, и для всех подформул (начиная с переменных и идя ко всей формуле) выводим их или их отрицания с помощью леммы 3.

Если формула $$A$$ является тавтологией, то из всех $$2^n$$ вариантов посылок выводится именно она, а не ее отрицание. Тогда правило разбора случаев и закон исключенного третьего позволяют избавиться от посылок: сгруппируем их в пары, отличающиеся в позиции $$p_1$$ (в одном наборе посылок стоит $$p_1$$, в другом $$\lnot p_1$$ ), по правилу разбора случаев заменим их на посылку $$(p_1\lor\lnot p_1)$$, которую можно выбросить (она является аксиомой). Сделав так для всех пар, получим $$2^{n-1}$$ выводов, в посылках которых нет $$p_1$$ ; повторим этот процесс с посылками $$p_2$$, $$\lnot p_2$$ и т. д. В конце концов мы убедимся, что формула $$A$$ выводима без посылок, как и утверждает теорема о полноте.

Второе доказательство теоремы о полноте

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

Начнем с такого определения: множество формул $$\Gamma$$ называется совместным,если существует набор значений переменных, при которых все формулы из $$\Gamma$$ истинны. Заметим, что формула $$\varphi$$ является тавтологией тогда и только тогда, когда множество, состоящее из единственной формулы $$\lnot \varphi$$, не является совместным. Для случая одной формулы есть специальный термин: формула $$\tau$$ выполнима, если существуют значения переменных, при которых она истинна, то есть если множество $$\{\tau\}$$ совместно. Тавтологии — это формулы, отрицания которых не выполнимы.

Множество формул $$\Gamma$$ называется противоречивым, если из него одновременно выводятся формулы $$A$$ и $$\lnot A$$. Мы знаем, что в этом случае из него выводятся вообще все формулы. (В противном случае $$\Gamma$$ называется непротиворечивым.)

Теорема 19 (корректность исчисления высказываний, вторая форма). Всякое совместное множество формул непротиворечиво.

В самом деле, пусть совместное множество $$\Gamma$$ противоречиво. Так как оно совместно, существуют значения переменных, при которых все формулы из $$\Gamma$$ истинны. С другой стороны, из $$\Gamma$$ выводится некоторая формула $$B$$ и ее отрицание. Может ли так быть?

Оказывается, что нет. Мы уже видели, что всякая выводимая формула истинна при всех значениях переменных (является тавтологией). Справедливо и несколько более общее утверждение: если $$\Gamma\vdash A$$ и при некоторых значениях переменных все формулы из $$\Gamma$$ истинны, то и формула $$A$$ истинна при этих значениях переменных. (Как и раньше, это легко доказывается индукцией по построению вывода $$A$$ из $$\Gamma$$.)

В нашей ситуации это приводит к тому, что на выполняющем наборе значений переменных для $$\Gamma$$ должны быть истинны обе формулы $$B$$ и $$\lnot B$$, что, разумеется, невозможно.

Мы называем это утверждение другой формой теоремы о корректности исчисления высказываний, поскольку из него формально можно вывести, что всякая теорема является тавтологией: если $$A$$ — теорема, то множество $$\{\lnot A\}$$ противоречиво (из него выводятся $$A$$ и $$\lnot A$$ ), потому несовместно, значит, $$\lnot A$$ всегда ложна, поэтому $$A$$ всегда истинна.

Теорема 20 (полнота исчисления высказываний, вторая форма). Всякое непротиворечивое множество совместно.

Нам дано непротиворечивое множество $$\Gamma$$, а надо найти такие значения переменных, при которых все формулы из $$\Gamma$$ истинны. (Вообще говоря, множество $$\Gamma$$ может быть бесконечно и содержать бесконечное число разных переменных.)

Пусть есть какая-то переменная $$p$$, встречающаяся в формулах из семейства $$\Gamma$$. Нам надо решить, сделать ли ее истинной или ложной. Если оказалось так, что из $$\Gamma$$ выводится формула $$p$$, то выбора нет: она обязана быть истинной в тех наборах, где формулы из $$\Gamma$$ истинны (как мы видели при доказательстве корректности). По тем же причинам, если из $$\Gamma$$ выводится $$\lnot p$$, то в выполняющем наборе переменная $$p$$ обязательно будет ложной.

Если оказалось так, что для любой переменной $$p$$ либо она сама, либо ее отрицание выводятся из $$\Gamma$$, то выполняющий набор значений определен однозначно, и надо только проверить, что он действительно будет выполняющим. А если для каких-то переменных нельзя вывести ни их, ни их отрицание, то мы пополним наш набор $$\Gamma$$ так, чтобы они, как теперь модно говорить, "определились".

Проведем это рассуждение подробно. Рассмотрим все переменные, входящие в какие-либо формулы из множества $$\Gamma$$ ; обозначим множество этих переменных через $$V$$. Зафиксируем это множество и до конца доказательства теоремы о полноте будем рассматривать только формулы с переменными из множества $$V$$, не оговаривая этого особо.

Назовем непротиворечивое множество $$\Gamma$$ полным, если для любой формулы $$F$$ имеет место либо $$\Gamma\vdash F$$, либо $$\Gamma\vdash \lnot F$$ (одновременно этого быть не может, так как $$\Gamma$$ непротиворечиво).

Утверждение теоремы о полноте очевидно следует из двух лемм:

Лемма 1. Всякое непротиворечивое множество $$\Gamma$$ содержится в непротиворечивом полном множестве $$\Delta$$.

Лемма 2. Для всякого непротиворечивого полного множества $$\Delta$$ существует набор значений переменных (из $$V$$, напомним), при котором все формулы из $$\Delta$$ истинны.

Доказательство леммы 1. Основную роль здесь играет такое утверждение: если $$\Gamma$$ — непротиворечивое множество, а $$A$$ — произвольная формула, то хотя бы одно из множеств $$\Gamma\cup\{A\}$$ и $$\Gamma\cup\{\lnot A\}$$ непротиворечиво. В самом деле, если оба множества $$\Gamma\cup\{A\}$$ и $$\Gamma\cup\{\lnot A\}$$ противоречивы, то $$\Gamma\vdash\lnot A$$ и $$\Gamma\vdash\lnot\lnot A$$, но множество $$\Gamma$$ предполагалось непротиворечивым.

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

Для случая произвольного набора переменных $$V$$ рассуждение можно завершить ссылкой на лемму Цорна: рассмотрим частично упорядоченное множество, элементами которого будут непротиворечивые множества формул, а порядком — отношение "быть подмножеством". Рассуждение предыдущего абзаца показывает, что всякая цепь в этом множестве имеет верхнюю границу (объединение линейно упорядоченного по включению семейства непротиворечивых множеств является непротиворечивым множеством). Следовательно, для любого непротиворечивого множества найдется содержащее его максимальное непротиворечивое множество. А оно обязано быть полным (иначе его можно расширить, добавив $$A$$ или $$\lnot A$$ ).

Лемма 1 доказана.

Доказательство леммы 2. Пусть $$\Gamma$$ — непротиворечивое полное множество. Тогда для каждой переменной (из множества $$V$$ ) ровно одна из формул $$p$$ и $$\lnot p$$ выводима из $$\Gamma$$. Если первая, будем считать переменную $$p$$ истинной, если вторая — ложной. Тем самым появляется некоторый набор $$\nu$$ значений переменных, и надо только проверить, что любая формула из $$\Gamma$$ при таких значениях переменных истинна. Это делается так: индукцией по построению формулы $$A$$ мы доказываем, что$$\begin{align*} A\text{ истинна на наборе }\nu\Rightarrow\Gamma\vdash A,\\ A\text{ ложна на наборе }\nu\Rightarrow\Gamma\vdash\lnot A. \end{align*}$$ Базис индукции (когда $$A$$ — переменная) обеспечивается определением истинности переменных. Для шага индукции используется та же лемма, что и при доказательстве полноты с помощью разбора случаев. Пусть, например, $$A$$ имеет вид $$(B\land C)$$. Тогда есть четыре возможности для истинности $$B$$ и $$C$$. В одном из них (когда $$B$$ и $$C$$ истинны на $$\nu$$ ) по предположению индукции мы имеем $$\Gamma\vdash B$$ и $$\Gamma\vdash C$$, откуда $$\Gamma\vdash (B\land C)$$, то есть $$\Gamma\vdash A$$. В другом ( $$B$$ истинна, $$C$$ ложна) предположение индукции дает $$\Gamma\vdash B$$ и $$\Gamma\vdash \lnot C$$, откуда $$\Gamma\vdash\lnot(B\land C)$$, то есть $$\Gamma\vdash\lnot A$$. Аналогично разбираются и все остальные случаи и логические связки. Лемма 2 доказана, и тем самым завершено доказательство теоремы 20.

Мы доказали, что всякое непротиворечивое множество формул совместно. Отсюда легко следует, что всякая тавтология является теоремой. В самом деле, если $$\varphi$$ — тавтология, то множество $$\{\lnot\varphi\}$$ несовместно, поэтому из $$\lnot\varphi$$ выводится противоречие, поэтому $$\vdash \lnot\lnot\varphi$$, и по закону снятия двойного отрицания $$\vdash\varphi$$.

Кроме того, теорема о полноте во второй формулировке имеет такое очевидное следствие:

Теорема 21 (теорема компактности для исчисления высказываний). Пусть $$\Gamma$$ — множество формул, всякое конечное подмножество которого совместно. Тогда и все множество $$\Gamma$$ совместно.

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

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

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

Для случая счетного числа переменных можно воспользоваться компактностью (в топологическом смысле слова) канторовского пространства. Его элементами являются бесконечные последовательности нулей и единиц. Если две последовательности отличаются в $$n$$ -й позиции, а все предыдущие члены совпадают, то расстояние между ними считается равным $$2^{-n}$$. Это метрическое пространство компактно.

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

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

Для счетного набора переменных теорема компактности связана с так называемой леммой Кенига. Конечные последовательности нулей и единиц (включая пустую последовательность) мы называем двоичными словами. Двоичным деревом мы называем множество двоичных слов, которое вместе со всяким словом содержит все его начала (начальные отрезки). Бесконечной ветвью двоичного дерева $$T$$ мы называем бесконечную последовательность нулей и единиц, любое конечное начало которой принадлежит $$T$$.

Теорема 22 (лемма Кенига). Любое бесконечное дерево имеет бесконечную ветвь.

Говоря о бесконечности дерева, мы имеем в виду, что соответствующее множество бесконечно. Отсюда следует, что оно содержит слова сколь угодно большой длины. Пусть $$p_1,p_2,\dots$$ — счетное множество переменных, которые принимают значения $$0$$ или $$1$$. Для каждого $$n$$ рассмотрим формулу $$\varphi_n$$, которая утверждает, что слово $$p_1p_2\dots p_n$$ принадлежит дереву $$T$$ (это возможно, так как любая булева функция выразима формулой). Поскольку $$T$$ — дерево, $$\varphi_i$$ влечет $$\varphi_j$$ при $$j<i$$. Любое конечное множество формул вида $$\varphi_i$$ равносильно, таким образом, одной формуле с максимальным $$i$$ и потому совместно. Следовательно, и множество всех формул $$\varphi_i$$ совместно, и выполняющий набор определяет бесконечную ветвь.

(Конечно, мы "бьем из пушек по воробьям": достаточно индукцией по $$i$$ строить слово длины $$i$$, которое имеет бесконечное число продолжений в дереве $$T$$.)

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