Проблема разрешимости исчисления высказываний
Обновлено: 16.05.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.
Аналогично можно установить критерий тождественной ложности формулы алгебры логики, используя ее ДНФ.
Теорема. Для того чтобы элементарная конъюнкция была тождественно ложной, необходимо и достаточно, чтобы в ней содержалась переменная и ее отрицание.
Теорема. Для того чтобы формула алгебры логики А была тождественно ложной, необходимо и достаточно, чтобы любая конъюнкция, входящая в ДНФ А, содержала переменную и ее отрицание.
Читайте также: