Разрешимости

Определение 1.3. Формула называется тождественно-истинной (тавтологией), если для любых наборов переменных она принимает значение И.

Определение 1.4. Формула называется тождественно-ложной, если для любых наборов переменных она принимает значение Л.

Определение 1.5. Формула называется выполнимой, если для некоторых наборов переменных она принимает значение И.

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

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

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

Следовательно, приведя формулу равносильными преобразованиями к КНФ, можно установить, является ли она тождественно-истинной, а приведя ее к ДНФ, можно установить, является ли она тождественно-ложной.

Пример 1.20.

Доказать, что формула F = (А É B) É ((C Ú А) É (C Ú B)) является тождественно-истинной.

Последовательно применяя равносильные преобразования, приведем нашу формулу к КНФ:

(А É B) É ((C Ú А) É (C Ú B)) º Ø(А É B) Ú ((CА) É (C Ú B)) º (А &Ø B) Ú Ø(C Ú А) Ú (C Ú B) º (А &Ø B) Ú (Ø C &Ø А) Ú (C Ú B) º (А Ú Ø C)& (А Ú Ø А) &(Ø B ÚØ C) &(Ø B ÚØ А) Ú (C Ú B) º (А ÚØ C)&(Ø B ÚØ C)&(Ø B ÚØ А) Ú (C Ú B) º (А ÚØ C Ú C Ú B)&(Ø B ÚØ C Ú C Ú B)&(Ø B ÚØ А Ú C Ú B).

В первую дизъюнкцию входят C и Ø C. Во вторую – B и Ø B, C и Ø C. в третью – B и Ø B. Следовательно, на основании теоремы 1.1 можно утверждать, что исходная формула является тождественно-истинной.

Так как всякой формуле соответствует таблица истинности, то тождественная истинность или тождественная ложность формулы может быть установлена двумя путями:

1) приведением с помощью равносильных преобразований к КНФ или ДНФ;

2) составлением таблицы истинности.

Пример 1.21.

Установить, является ли тождественно-истинной данная формула логики высказываний: F (A, B) = (А &(А É B)) É B.

1) Последовательно применяя равносильные преобразования, приведем нашу формулу к КНФ:

(А &(А É B)) É B º (А &(Ø А Ú B) É B º Ø(А &(Ø А Ú B) É B º Ø А ÚØ(Ø А Ú B)Ú B º Ø А Ú(А &Ø B)Ú B º (Ø А Ú B) ÚА&Ø B º (Ø А Ú B ÚА)&(Ø А Ú B ÚØ B).

В первую дизъюнкцию входят A и Ø A. Во вторую – B и Ø B, поэтому формула является тождественно истинной, F (A, B) º И.

2) Составим таблицу истинности F (A, B) (таблица 1.7):

Таблица 1.7

Из таблицы 1.7 видно, что F (A, B) º И.