Проблема разрешимости исчисления высказываний

Обновлено: 22.12.2024

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

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

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

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

Очевидно, проблема разрешимости алгебры логики разрешима.

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

Однако практическое использование таблицы истинности для произвольной формулы A(x1, x2, . xn) при больших n затруднительно.

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

том, будет ли формула A выполнимой.

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

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

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

Доказательство

Необходимость. Пусть элементарная дизъюнкция тождественно истинна, но в нее одновременно не входит некоторая переменная и ее отрицание. Придадим каждой переменной, входящей в элементарную дизъюнкцию без знака отрицания, значение ложь, а каждой переменной, входящей в элементарную дизъюнкцию под знаком отрицания – значение «истина». Тогда, очевидно, вся элементарная дизъюнкция примет значение ложь, что противоречит условию.

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

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

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

Доказательство

Необходимость. Пусть A – тождественно истинна. Тогда и КНФ A – тождественно истинна. Но КНФ A º A1&A2&. &An, где Ai – элементарные дизъюнкции (i = 1,2. n). Так как КНФ A º 1, то Ai º 1 (i =1,2. n). Но тогда по теореме, только что доказанной выше, каждая элементарная дизъюнкция Ai содержит переменную и ее отрицание.

Достаточность. Пусть любая элементарная дизъюнкция A, входящая в КНФ A, содержит переменную и ее отрицание. Тогда по теореме 1 Ai º 1 (i = 1,2. n). При этом и КНФ A º 1.

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

Так как , то ясно, что каждая элементарная дизъюнкция, входящая в КНФ A, содержит переменную и ее отрицание. Следовательно, A º 1.

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

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

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

Читайте также: