П. 2.3. Проблема разрешимости

Все формулы алгебр логики делятся на три класса: тождественно истинные (тавтологии), тождественно ложные, выполнимые.

Вопрос, к какому классу формул относится текущая формула А, называется проблемой разрешимости.

Алгоритм А: Для каждой формулы может быть составлена таблица истинности, содержащая строк, если в формулу входит и исходит высказывательная переменная.

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

Алгоритм В: Рассматривается формула А. Если , то задача решена. Если это не так, то рассматривается формула . Если , то и задача решена. Если это не так, то А – выполнимая формула.

Установление тождественной истинности формулы А основано на теоремах 2.1. и 2.2.

Например: Приведением к нормальным формам установить, является ли формула – тождественно истинной, тождественно ложной или выполнимой.

Решение:

– приведенная формула. Обозначим ее за В и приведем ее к одной из нормальных форм ДНФ или КНФ.

1) ДНФ, обозначим – , – :

Будем иметь . На основании теоремы 2.2. можно утверждать, что формула А не является тождественно ложной.

2) КНФ, – ,– :

.

Тогда . Согласно теореме 2.2. формула А не является тождественно истинной. Следовательно формула А – выполнима.

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