Все формулы алгебры логики делятся на три класса:
1) тождественно истинные;
2) тождественно ложные;
3) выполнимые.
Формула \(A\) называется тождественно истинной (или тавтологией), если она принимает значение 1 при всех значениях входящих в нее переменных.
Формула называется тождественно ложной(или противоречием), если она принимает значение 0 при всех значениях входящих в нее переменных.
Формула \(A\) называют выполнимой, если она принимает значение “истина” хотя бы на одном наборе значений входящих в нее переменных и не является тождественно истинной.
В связи с этим возникает задача получения ответа на вопрос: к какому классу относится данная формула?
Эта задача называется проблемой разрешимости.
Очевидно, что проблема разрешимости алгебры логики разрешима.
Действительно, для каждой формулы алгебры логики может быть составлена таблица истинности, которая и даст ответ на поставленный вопрос.
Однако практическое использование таблиц истинности для формулы \(A ( x_{1}, x_{2}, ..., x_{n})\) при больших \(n\) затруднительно.
Существует другой способ, позволяющий, не используя таблицы истинности, определить, к какому классу относится формула \(A\). Этот способ основан на приведении формулы к нормальной форме (ДНФ или КНФ) и использовании алгоритма, который позволяет определить, является ли данная формула тождественно истинной или не является. Одновременно с этим решается вопрос о том, будет ли формула \(A\) выполнимой.
Предположим, что мы имеем критерий тождественной истинности для формул алгебры логики. Рассмотрим механизм его применения.
Применим критерий тождественной истинности к формуле \(A\). Если окажется, что формула \(A\) – тождественно истинная, то задача решена. Если же окажется, что формула \(A\) не тождественно истинна, то применим критерий тождественной истинности к формуле \(\bar{A}\). Если окажется, что формула \(\bar{A}\) - тождественно истинная, то ясно, что формула \(A\) - тождественно ложная, и задача решена. Если же формула \(\bar{A}\) не тождественно истинная, то остается единственный возможный результат: формула \(\bar{A}\) выполнима.
Установим теперь критерий тождественной истинности произвольной формулы алгебры логики. С этой целью предварительно сформулируем и докажем критерий тождественной истинности элементарной дизъюнкции.
Теорема 1. Для того, чтобы элементарная дизъюнкция была тождественно истинной, необходимо и достаточно, чтобы в ней содержалась переменная и её отрицание.
Доказательство. Необходимость. Пусть элементарная дизъюнкция тождественно истинна, но в нее одновременно не входит некоторая переменная и её отрицание. Придадим каждой переменной, входящей в элементарную дизъюнкцию без знака отрицания, значение ложь, а каждой переменной, входящей в элементарную дизъюнкцию под знаком отрицания - значение истина. Тогда, очевидно, вся элементарная дизъюнкция примет значение ложь, что противоречит условию.
Достаточность. Пусть теперь элементарная дизъюнкция содержит переменную и ее отрицание. Так как \(x_{i} \vee \bar{x_{i}} \equiv 1\), то и вся элементарная дизъюнкция будет тождественно истинной.
Критерий тождественной истинности элементарной дизъюнкции позволяет сформулировать и доказать критерий тождественной истинности произвольной формулы алгебры логики.
Теорема 2. Для того, чтобы формула алгебры логики \(A\) была тождественно истинна, необходимо и достаточно, чтобы любая элементарная дизъюнкция, входящая в КНФ \(A\), содержала переменную и ее отрицание.
Доказательство. Необходимость. Пусть \(A\) - тождественно истинна. Тогда и КНФ \(A \equiv A_{1} \wedge A_{2} \wedge ...\wedge A _{n},\) где \(A_{i}\) - элементарные дизъюнкции \(( i = 1, 2, ..., n ).\) Так как КНФ \(A \equiv 1,\) то \(A_{i} \equiv 1\) \(( i = 1, 2, ..., n ).\) Но тогда по теореме 1 каждая элементарная дизъюнкция \(A_{i}\) содержит переменную и ее отрицание.
Достаточность. Пусть любая элементарная дизъюнкция \(A_{i}\), входящая в КНФ \(A\), содержит переменную и ее отрицание. Тогда по теореме 1 \(A_{i} \equiv 1\) \(( i = 1, 2, ..., n )\). При этом и КНФ \(A \equiv 1\).
Например, выясним, является ли формула \(A \equiv y \vee \bar{y} \wedge x \vee \bar{x} \wedge \bar{y}\) тождественно истинной.
Так как \(A \equiv y \vee \bar{y} \wedge ( x \vee \bar{x} ) \equiv ( y \vee \bar{y} ) \wedge ( y \vee x \vee \bar{ x} ),\) то ясно, что каждая элементарная дизъюнкция \(y \vee \bar{y}\) и \(y \vee x \vee \bar{x} ,\) входящая в КНФ \(A\), содержит переменную и ее отрицание. Следовательно, \(A \equiv 1\).
Аналогично можно установить критерий тождественной ложности формулы алгебры логики, используя ее ДНФ.
Теорема 3. Для того, чтобы элементарная конъюнкция была тождественно ложной, необходимо и достаточно, чтобы в ней содержалась переменная и ее отрицание.
Теорема 4. Для того, чтобы формула алгебры логики \(A\) была тождественно ложной, необходимо и достаточно, чтобы любая конъюнкция, входящая в ДНФ \(A\), содержала переменную и ее отрицание.
Пример Будет ли формула \(( x \rightarrow y) \rightarrow \bar{x} y \vee \bar{y}\) тождественно истинной, тождественно ложной или выполнимой.
Решение. Приведем формулу к какой - либо нормальной форме:
$$( x \rightarrow y) \rightarrow \bar{x} y \vee \bar{y} \equiv \bar{x} \vee y \rightarrow \bar{x}y \vee \bar{y} \equiv \overline{\bar{x} \vee y} \vee \bar{x} y \vee \bar{y} \equiv$$
$$\equiv x \bar{y} \vee \bar{x} y \vee \bar{y} .$$
Полученная ДНФ не является тождественно ложной, так как каждая элементарная коy конъюнкция не содержит переменную и ее отрицание. Следовательно, исходная формула тождественно истинна или выполнима. Преобразуем данную формулу к КНФ.
$$( x \rightarrow y) \rightarrow \bar{x}y \vee \bar{y} \equiv x\bar{y} \vee \bar{x} y \vee \bar{y} \equiv ( x\bar{y} \vee \bar{y}) \vee \bar{x}y \equiv \bar{y} \vee \bar{x}y \equiv$$
$$\equiv ( \bar{y} \vee \bar{x}) \wedge ( \bar{y} \vee y) \equiv \bar{y} \vee \bar{x}.$$
Это произведение не является тождественно истинным, так как элементарная сумма \(\bar{y} \vee \bar{x}\) не тождественно истинна. Таким образом, исходная формула не тождественно ложна и не тождественно истинна, следовательно, она выполнима.
