Логика булевых функций

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


Определение 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

А B	АB	А&(АB)	(А&(АB))B
Л Л Л И И Л И И	И И Л И	Л Л Л И	И И И И

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