3.5. Теорема компактности для исчисления высказываний

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

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

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

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

L B1 & B2 &…& Bn, ® q.

Применяя теорему о дедукции, мы получили бы в этом случае B1&B2&…&BnLq и из A1 & A2 &…& An L Øq выводимость:

A1, …, Am, B1, …, Bn L q & Øq,

из которой вытекала бы невыполнимость множества { A1, …, Am, B1, …, Bn }, противоречащая конечной выполнимости множества å. Следовательно, множество {B1,…,Bn,Øq} выполнимо для любых B1,…, Bn Î å. Таким образом, если å È {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, то å – выполнимо. Теорема доказана.