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

Все формулы алгебры логики делятся на три класса:

1.Тавталогии

2.Тождественно ложные

3.Выполнимые

Формулу А называют выполнимой,если она принимает значение единицы хотя бы на одном наборе входящих в нее переменных и не является тождественно истинной.

Вопрос, к какому классу формул относится текущая формула А, и называется проблемой разрешимости, которая элементарно решается с помощью таблицы истинности, однако для больших формул таблицы очень громоздки и их использование затруднительно.

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

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

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

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

Например,

Теорема 2.Для того, чтобы элементарная конъюнкция была тождественно ложной, необходимо и достаточно, чтобы в ней содержалась переменная и ее отрицание.

Теорема 3.Для того, чтобы формула алгебры логики А была тождественно истинна, необходимо и достаточно, чтобы любая элементарная дизъюнкция, входящая в КНФ А, содержала переменную и ее отрицание.

Теореме 4.Для того, чтобы формула алгебры логики А была тождественно ложной, необходимо и достаточно, чтобы любая элементарная конъюнкция, входящая в ДНФ А, содержала и ее отрицание.

Пример.

Получить СДНФ и СКНФ с помощью таблицы истинности и путем элементарных преобразований.

Составим таблицу истинности ( табл. 20 ). Из таблицы сразу получаем

СДНФ .

Таблица 20

x	y

Из таблицы также видно, что формула А – выполнимая формула. Найдем теперь СКНФ по формуле

СКНФ А = ,

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

- сразу ДНФ и СДНФ.

СДНФ – дизъюнкция элементарных конъюнкций. В ней только одно слагаемое ху, других нет.

Найдем теперь СКНФ. Для этого нужна хоть какая – то КНФ. Например, ху – КНФ, так как х и у можно считать элементарными.