Разрешимость, непротиворечивость, полнота, независимость аксиом

Проблема разрешимости для любого аксиоматического исчисления, в том числе и для исчисления высказываний, состоит в существова­нии алгоритма, который по любой формуле устанавливает, является она в этом исчислении доказуемой или не является. Если такого ал­горитма не существует, то аксиоматическое исчисление алгоритмиче­ски неразрешимо.

Исчисление высказываний алгоритмически разрешимо. Разрешающий алгоритм состоит в проверке для данной формулы, является ли она тождественно истинной. Если да, то формула доказуема в ИВ; если нет, то формула в ИВ не доказуема.

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

Определение. Аксиоматическое исчисление непротиворечиво, если в нем нет формулы А, для которой ├ А и ├ ù А одновременно.

Исчисление высказываний непротиворечиво, ибо если допустить существование в ИВ формулы А, для которой ├ А и ├ ù A одновремен­но, то получим, что формулы А и ù А тождественно истинны, что не­возможно.

Определение. Аксиоматическое исчисление внутренне полно, если добавление к нему недоказуемой формулы в качестве аксиомы приво­дит к противоречивому исчислению.

Теорема. Исчисление высказываний внутренне полно.

Доказательство. Пусть А(р₁,р₂,...,p_n) - недоказуемая в ИВ фор­мула и р₁,р₂,..., p_n - полный список переменных этой формулы. До­бавим формулу А к исчислению высказываний в качестве аксиомы; по­лучим исчисление К. Тогда
├ _K A (т.е. А доказуема в К). Формула А не является тождественно истинной, иначе она была бы доказуема в ИВ. Поэтому существует набор а = (a₁,a₂,…,a_n) из 0 и 1, для ко­торого Р_а (А) = 0. Зададим формулы

Формула С = A (B₁,В₂,...,В_n) тождественно ложна; тогда формула ù С тождес-твенно истинна и потому ├ ù C, а, следовательно, ├ _K ù C. Так как ├ _K A(р₁,р₂,.., p_n), то ├ _K А(B₁,В₂,...,В_n) как подстановка в доказуемую формулу, т.е. ├ _K С и
├ _K ù С, откуда следует, что исчисление К противоречиво. Теорема доказана.

Заметим, что в противоречивом исчислении доказуема любая фор­мула (и потому в смысле выводимости противоречивое исчисление тривиально). В самом деле, пусть В - произвольная формула в акси­оматическом исчислении (которое противоречиво) и А - такая форму­ла в нем, что ├ А и ├ ù A одновре-менно. Тогда ├ А & ù А и ввиду ├ А & ù А ® В по правилу заключения полу-чаем ├ В для любой формулы В.

Определение. Независимой в системе аксиом называется аксиома, не выводимая из остальных аксиом.

Теорема. Все аксиомы исчисления высказываний независимы.

Доказательство. Покажем, что аксиома A3 р & q ® р независима от осталь-ных аксиом. Пусть L - система аксиом, включающая в себя все аксиомы ИВ, кроме A3. Определим дизъюнкцию, импликацию, отрицание обычным образом, а конъюнкцию определим, положив р & q = q. При таком определении конъюнкции аксиома A3 р & q ® р на наборе (0,1) принимает значение 0; ос-тальные аксиомы тождественно равны 1,

Утверждение. Все формулы, выводимые из системы аксиом L при выше определенных логических операциях тождественно равны 1.

Доказательство. Индукция по длине k вывода.

БАЗИС. k = 1. Непосредственной проверкой убеждаемся, что все аксиомы из L при выше определенных логических операциях тождест­венно равны 1.

ПРЕДПОЛОЖЕНИЕ ИНДУКЦИИ. Допустим, что все формулы, выво­димые из L с длиной вывода меньше k, тождественно равны 1.

ШАГ ИНДУКЦИИ. Покажем, что всякая формула, выводимая из L с длиной вывода k, тождественно равна 1 (при выше определенных ло­гических операциях). Пусть ├ _L А и A₁,A₂,...,A_k есть доказатель­ство длины k в системе L формулы А. Возможны следующие случаи.

1. А_k - аксиома из L. Тогда A_k тождественно равна 1 (случай базиса).

2. А_kполучена подстановкой формулы С в А_i(р) в доказательстве А₁,А₂,.., А_i(р),..., A_k, т.е. А_k = А_i(С). Так как длина доказа­тельства формулы А_i(р) меньше k, то по предположению индукции формула А_i(р) тождественно равна 1, и потому формула А_i(С) тожде­ственно равна 1.

3. Формула А_k получена из формул А_i и А_i ® А_kв доказатель­стве A₁,...,А_i,.., А_i ® А_k,..., А_kс помощью правила заключения.

Так как длины доказательств А₁,...,А_k и A₁,..., А_i,...,А_i ® A_k формул А_i и А_i ® А_k меньше k, то по предположению индукции формулы А_i и А_i ® А_k тождественно равны 1. Так как операция ® оп­ределялась обычным образом, то формула А_k тождественно равна 1.

Утверждение доказано. Продолжим доказательство теоремы.

Допустим, что аксиома A3 р & q ® p выводима из остальных акси­ом. Тогда по утверждению она тождественно равна 1 (при выше опре­деленных логических операциях). Противоречие. Следовательно, ак­сиома A3 независима от остальных аксиом.

Независимость остальных аксиом системы П.С.Новикова доказыва­ется по такой же схеме.