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

Тождественно-истинные и тождественно-ложные формулы. Проблема

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

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

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

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

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

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

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

Пример 1.13.

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

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

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

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

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

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

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

Пример 1.14.

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

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

(А &(А É B)) É B º (А &(Ø А V B) É B º Ø(А &(Ø А V B) V B º Ø А VØ(Ø(А V B)V B º Ø А V(А & B)V B º (Ø А V B)VА&Ø B º (Ø А V B VА)&(Ø А V BV Ø B).

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

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

Таблица 1.6

А B	А É B	А &(АÉ B)	(А &(А É B))É B
Л Л Л И И Л И И	И И Л И	Л Л Л И	И И И И

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

Дата добавления: 2014-01-07