Разрешимость для логики высказываний

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

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

Теорема 2.6. Формула является тавтологией в том и только том случае, если в ее КНФ в любую из элементарных дизъюнкций в качестве дизъюнктивных членов входит какая-нибудь переменная и ее отрицание.

Доказательство. Достаточность. Пусть в каждую элементарную дизъюнкцию в качестве дизъюнктивных членов входят некоторые переменные вместе со своими отрицаниями, тогда каждая такая элементарная дизъюнкция является тавтологией и, следовательно, КНФ является также тавтологией.

Необходимость. Нам понадобится следующее вспомогательное утверждение: "Если элементарная дизъюнкция является тавтологией, то она содержит какую-нибудь переменную вместе с отрицанием".

От противного. Пусть элементарная дизъюнкция не содержит никакой переменной вместе с ее отрицанием. Выберем такое распределение истинностных значений, при котором эта элементарная дизъюнкция будет иметь ложное значение. Для этого любой переменной, входящей без отрицания, положим значение Л, а любой переменной, входящей с отрицанием, положим значение И. Тогда элементарная дизъюнкция есть дизъюнкция ложных значений и, следовательно, будет ложной.

Вернемся к доказательству необходимости. Для того, чтобы конъюнкция формул была тавтологией, необходимо, чтобы каждый конъюнктивный член был тавтологией. Иначе, мы сразу приходим к противоречию.

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

Двойственное утверждение справедливо и для противоречия (тождественно-ложной) формулы.

Теорема 2.7. Формула является противоречием в том и только том случае, если в ее ДНФ каждая элементарная конъюнкция одновременно содержит в качестве конъюнктивных членов какую-нибудь переменную и ее отрицание.

Доказательство. Пусть формула A равносильна формуле B, находящейся в ДНФ. Тогда легко показать, что ØB, используя законы де Моргана и снятие двойного отрицания, преобразуется в формулу С, находящуюся в КНФ. При этом преобразовании любая элементарная конъюнкция переходит в элементарную дизъюнкцию. Имеем ØAºC и по предыдущей теореме 2.6 формула ØA - тавтология тогда и только тогда, когда каждая элементарная дизъюнкция в C содержит какую-нибудь переменную и ее отрицание. Переходя от формул ØA и C к формулам A и B, мы получаем справедливость теоремы.

Пора чудес прошла, и нам

Подыскивать приходится причины

Всему, что совершается на свете.

В. Шекспир