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

Формулы исчисления высказываний можно интерпретировать, как формулы алгебры высказываний для этого будем трактовать свободные переменные исчисления высказываний как переменные алгебры высказываний, то есть переменные принимающие значения истина и ложь. Операции конъюнкции, дизъюнкции и отрицания определим так же как в алгебре высказываний; тогда всякая формула при любых значениях переменных сама будет принимать одно из значений истина или ложь, вычисляемое по правилам алгебры высказываний.

Определение 1:

Логическое исчисление непротиворечиво, если в нем не выводимы никакие две формулы, из которых одна является отрицанием другой.

Непротиворечивое исчисление это такое исчисление, что, какова бы ни была формула α, никогда формулы α и не могут быть одновременно выведены из аксиом этого исчисления с помощью указанных в нем правил. Если в исчислении обнаруживаются выводимые формулы вида α и , то такое исчисление называется противоречивым (так как все формул выводимы и нет различия между истиной и ложью такое исчисление не ценно).

Теорема 1:

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

Доказательство:

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

Покажем, что если формула α(A) тождественно истинна, то и формула α(β), полученная с помощью правила подстановки, также тождественно истинна. В самом деле, α(A) при всех значениях переменных высказываний принимает значение «истина», т.е. α(И)≡И и α(Л)≡И. Но и формула β при любых значениях переменных высказываний может иметь только значение «истина» или «ложь». Отсюда ясно, что α(β) всегда будем принимать значение «истина».

Теперь докажем, что если формулы α и α→β тождественно истинны, то формула β также тождественно истинна.

α – тождественно истинна, следовательно, всегда принимает значение «истина». Так как формула α→β также всегда принимает значение «истина», то формула β не может принять значение «ложь» ни при каких значениях переменных высказываний, иначе по определению импликации в алгебре высказываний формула α→β приняла бы значение «ложь».

Итак, мы показали, что: 1) все аксиомы тождественно истинные формулы, 2) применяя к тождественно истинным формулам правила вывода, мы получаем тождественно истинные формулы. Отсюда следует, что все выводимые в исчисление высказываний формулы являются тождественно истинными в алгебре высказываний. В этом случае ясно, что если формула α выводима в исчислении высказываний, то формула не может быть выводима, так как α – тождественно истинная формула, а - тождественно ложная формула. Непротиворечивость исчисления высказываний доказана.

Доказывая, что исчисление высказываний непротиворечиво мы показали, что всякая формула, выводимая в исчислении высказываний, является тождественно истинной в алгебре высказываний. Возникает обратный вопрос: будет ли всякая тождественно истинная формула алгебры высказываний выводима в исчислении высказываний?

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

Теорема 2:

Всякая тождественно истинная формула алгебры высказываний выводима в исчислении высказываний.

[Доказательство см. П.С.Новиков Элементы математической логики].

Для всякого исчисления возникает вопрос о независимости его аксиом. Вопрос ставится следующим образом: Можно ли какую-нибудь аксиому вывести из остальных, применяя правила вывода данной системы?

Если оказывается, что некоторую аксиому можно таким образом вывести из остальных, то ее можно вычеркнуть из списка аксиом, и логическое исчисление при этом не изменится, т.е. запас его выводимых формул останется тот же.

Определение 2:

Аксиома, не выводимая из остальных аксиом, называется независимой от этих аксиом, а система аксиом, в которой ни одна аксиома не выводима из остальных, называется независимой системой аксиом. В противном случае система аксиом называется зависимой.

Теорема 3:

Система аксиом исчисления высказываний независима.

Метод доказательства этой теоремы аналогичен доказательству непротиворечивости исчисления высказываний [П.С.Новиков Элементы математической логики].