Рассмотрим исчисление высказываний L с произвольным множеством нелогических символов P. Множество всех формул обозначается через S. Логические символы дополняются связками , . Как было доказано в разд. 3.4, эти логические символы можно определить с помощью системы аксиом Клини.

Пусть å Í S – произвольное подмножество пропозициональных формул. Множество å называется выполнимым, если существует такая интерпретация e: S® I, что e(q) = 1 для всех q Î å. Множество å называется конечно выполнимым, если каждое его конечное подмножество выполнимо. Множество å называется полным, если для каждой формулы q оно содержит либо q, либо Øq. При этом q и Øq не могут принадлежать å одновременно.

Лемма. Если å – конечно выполнимо, то для любой формулы q Î S, либо åÈ{q}, либо åÈ{Øq}   конечно выполнимо.

Доказательство. Предположим, что å È {q} не является конечно выполнимым. Тогда существуют формулы A₁, A₂, …, A_m Î å, для которых множество {A₁, A₂, …, A_m, q} не выполнимо. Для любой интерпретации e: S® I, удовлетворяющей e(A_i) = 1 для всех 1 £ i £ m, значение e(q) будет равно 0. Значит, будет иметь место e(A₁& A₂&…& &A_m&q) = 0, откуда формула Ø(A₁& A₁&…&A_m&q), а вместе с ней и A₁& &A₂&…&A_m®Øq, будут тавтологиями. По теореме о полноте формула A₁& &…&A_m®Øq станет выводимой. Для любой другой последовательности B₁,…,B_n Î å невыполнимость множества {B1,…,Bn, Øq} приводит аналогичным образом к выводимости:

_L B₁ & B₂ &…& B_n, ® q.

Применяя теорему о дедукции, мы получили бы в этом случае B₁&B₂&…&B_nLq и из A₁ & A₂ &…& A_{n L} Øq выводимость:

A₁, …, A_m, B₁, …, B_{n L} q & Øq,

из которой вытекала бы невыполнимость множества { A₁, …, A_m, B₁, …, B_n }, противоречащая конечной выполнимости множества å. Следовательно, множество {B₁,…,B_n,Øq} выполнимо для любых B₁,…, B_n Î å. Таким образом, если å È {q} не является конечно выполнимым, то å È {Øq} – конечно выполнимо. Лемма доказана.

Замечание. Если å – конечно выполнимо, то для любой формулы A Î å формула ØA не принадлежит å, ибо в противном случае {A, ØA} не выполнимо.

Теорема (о компактности).  Пусть å – произвольное множество формул исчисления высказываний L. Тогда å выполнимо, если и только если å – конечно выполнимо.

Доказательство. Ясно, что если å – выполнимо, то оно конечно выполнимо. Докажем обратную импликацию. С этой целью рассмотрим множество всех конечно выполнимых å¢ Í S, содержащих å. Это множество частично упорядочено относительно отношения Í. Объединение цепи конечно выполнимых подмножеств å¢ Ê å будет конечно выполнимым и будет содержать å. По лемме Куратовского-Цорна существует å¢ Ê S, максимальное среди конечно выполнимых. Если для некоторого q Î S ни q, ни Øq не принадлежат å¢, то по лемме либо å¢ È {q}, либо å¢ È {Øq} конечно выполнимо. Это противоречит максимальности множества å¢. Стало быть, å¢ – полное.

Определим функцию е¢ : S ® I, полагая е¢(q) = 1 при q Î å¢, и е¢(q) = 0 в других случаях. Легко видеть, что е¢ будет интерпретацией, доказывающий выполнимость å¢. В самом деле, пусть A, B Î å¢. Так как å¢ – полное, то либо Ø(A & B) Î å¢, либо A & B Î å¢. Если Ø(A & B) Î å¢, то в силу конечной выполнимости å¢ существует ин

терпретация е¢¢, для которой имеют место равенства е¢¢(A) = е¢¢(B) = е¢¢(Ø(A & B)) = 1. Эти равенства приводят к е¢¢(A & B) = 1 и е¢¢(A & B) = 0, опровергающим принадлежность Ø(A & B) к множеству å¢. Следовательно, из A Î å¢ и B Î å¢ вытекает A & B Î å¢. Отсюда е¢(A & B) =  е¢(A) & е¢(B). Поскольку формула A ® B равна:  Ø(A & ØB), то (е¢(A ® B)) = (е¢(A) ®  е¢(B)). По построению , стало быть, е¢ – интерпретация. Поскольку  e’ | _å = 1, то å – выполнимо. Теорема доказана.