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

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

1) тождественно истинные,

2) тождественно ложные,

3) выполнимые.

Определения тождественно истинной и тождественно ложной формул даны выше.

Определение 1. Формулу А называют выполнимой (опровержимой), если она принимает значение «истина» («ложь») хотя бы на одном наборе значений входящих в неё переменных и не является тождественно истинной (тождественно ложной).

В связи с этим возникает задача: к какому классу относится данная формула?

Эта задача носит название проблемы разрешимости.

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

Однако практическое использование таблицы истинности для формулы при больших n затруднительно.

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

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

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

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

Теорема 1 выражает критерий тождественно истинной дизъюнкции. С его помощью получается критерий тождественно истинной произвольной формулы алгебры логики.

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

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

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

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