Логическая равносильность формул

Понятие равносильности формул

Определение 4.1. Формулы \(F(X_1,X_2,\ldots,X_n)\) и \(H(X_1,X_2,\ldots,X_n)\) алгебры высказываний называются равносильными (эквивалентными), если при любых значениях входящих в них пропозициональных переменных логические значения получающихся из формул \(F\) и \(H\) высказываний совпадают. Для указания равносильности формул используют обозначение \(F\cong H\) . Определение равносильности формул можно записать символически для любых конкретных высказываний \(A_1,A_2,\ldots,A_n:\)

\(F\cong H\quad\Leftrightarrow\quad \lambda \bigl(F(A_1, A_2,\ldots,A_n)\bigr)= \lambda\bigl(H(A_1,A_2,\ldots,A_n)\bigr).\)
(4.1)

Не следует думать, что в обе формулы \(F\) и \(H\) непременно входят одни и те же переменные. Некоторые из переменных \(X_1,X_2,\ldots,X_n\) могут фактически отсутствовать в любой из них. Проверим, например, равносильность формул \(\lnot X_1\) и \(\lnot X_2\land (X_2\lor\lnot X_1)\) . Для этого составим таблицы истинности обеих формул и убедимся, что значения истинности получающихся из них высказываний одинаковы для любых одинаковых наборов значений пропозициональных переменных \(X_1\) и \(X_2:\)

\(\begin{array}{|c|c||c|c|c|}\hline \lambda(X_1)& \lambda(X_2)& \lambda(\lnot X_1)& \lambda(X_2\lor\lnot X_1)& \lambda(\lnot X_1\land (X_2\lor\lnot X_1))\\\hline 0&0&1&1&1\\ 0&1&1&1&1\\ 1&0&0&0&0\\ 1&1&0&1&0\\\hline \end{array}\)

Проверьте самостоятельно справедливость равносильностей

\(X_1\lor\lnot X_1\cong X_2\lor\lnot X_2,\qquad X_1\land\lnot X_1\cong X_2\land\lnot X_2.\)

Выписывание в предыдущем определении в формулах \(F\) и \(H\) одних и тех же пропозициональных переменных обусловлено стремлением сделать записи и рассуждения более краткими и лаконичными. Это замечание следует иметь в виду и далее.

Для лучшего усвоения понятия равносильности формул алгоритм проверки на равносильность двух формул \(F(X,Y,Z)\) и \(G(X,Y,Z)\) можно представить в виде условной схемы (приведена в тексте). Формулы \(F(X,Y,Z)\) и \(G(X,Y,Z)\) заданы своими таблицами значений:

\(\begin{array}{|c|c|c||c|c|}\hline X& Y& Z& F(X,Y,Z)& G(X,Y,Z)\\\hline 0&0&0& \alpha_0& \beta_0\\ 0&0&1& \alpha_1& \beta_1\\ 0&1&0& \alpha_2& \beta_2\\ 0&1&1& \alpha_3& \beta_3\\ 1&0&0& \alpha_4& \beta_4\\ 1&0&1& \alpha_5& \beta_5\\ 1&1&0& \alpha_6& \beta_6\\ 1&1&1& \alpha_7& \beta_7\\\hline \end{array}\)

Алгоритм проверки формул на равносильность


Проанализируйте работу данного алгоритма и сопоставьте ее с определением понятия равносильности формул.


Признак равносильности формул

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

Теорема 4.2 (признак равносильности формул). Две формулы \(F\) и \(H\) алгебры высказываний равносильны тогда и только тогда, когда формула \(F\leftrightarrow H\) является тавтологией:

\(F\cong H\quad \Leftrightarrow\quad \vDash F\leftrightarrow H.\)
(4.2)

Доказательство. Если \(F\cong H\) , то по определению 4.1 \(\lambda\bigl(F(A_1,\ldots,A_n)\bigr)= \lambda\bigl(H(A_1,\ldots,A_n)\bigr)\) для любых высказываний \(A_1,\ldots,A_n\) . Тогда (по определению 1.9 операции эквивалентности) \(\lambda\bigl(F(A_1,\ldots,A_n)\bigr)\leftrightarrow \lambda\bigl(H(A_1,\ldots,A_n)\bigr)=1\) , откуда на основании соотношения (1.5) заключаем, что \(\lambda\bigl(F(A_1, \ldots,A_n) \bigr)\leftrightarrow \lambda\bigl(H(A_1,\ldots,A_n)\bigr)=1\) для любых \(A_1,\ldots,A_n\) . Последнее означает по определению тавтологии, что \(\vDash F\leftrightarrow H\) . Обратными рассуждениями доказывается утверждение: если \(\vDash F\leftrightarrow H\) , то \(F\cong H\) . Итак, теорема доказана.

Отметим, что равносильность формул — это не (логическая) операция над формулами, а отношение между формулами логики высказываний. Это означает, что если \(F\) и \(G\) — формулы, то выражение \(F\cong G\) уже не является формулой алгебры высказываний; оно — утверждение о некотором взаимоотношении между формулами \(F\) и \(H\) , лишь сокращенная (символическая) запись утверждения (высказывания) " \(F\) равносильна \(G\) " об этих формулах. Это утверждение либо истинно, либо ложно, т.е. \(F\) и \(G\) либо находятся в отношении равносильности, либо нет. В приведенном далее следствии из теоремы 4.2 устанавливаются некоторые свойства этого отношения между формулами алгебры высказываний.

Следствие 4.3. Отношение равносильности между формулами алгебры высказываний:

а) рефлексивно: \(F\cong F\) ;
б) симметрично: если \(F_1\cong F_2\) , то \(F_2\cong F_1\) ;
в) транзитивно: если \(F_1\cong F_2\) и \(F_2\cong F_3\) , то \(F_1\cong F_3\) , т.е. отношение равносильности является отношением эквивалентности.

Доказательство. Рефлексивность следует непосредственно из тавтологии теоремы 3.3, о и теоремы 4.2.

Для доказательства симметричности отношения \(\cong\) предположим, что \(F_1\cong F_2\) , т.е. на основании признака равносильности (теорема 4.2) \(\vDash F_1\leftrightarrow F_2\) . Тогда по тавтологии теоремы 3.3, пункт п) заключаем: формула \(F_2\leftrightarrow F_1\) принимает всегда те же самые значения, что и формула \(F_1\leftrightarrow F_2\) , т.е. только истинные значения. Следовательно, \(\vDash F_2\cong F_1\) или (по признаку равносильности) \(F_2\cong F_1\) . Симметричность доказана.

Наконец, если \(F_1\cong F_2\) и \(F_2\cong F_3\) , т.е. \(\vDash F_1\leftrightarrow F_2\) и \(\vDash F_2\leftrightarrow F_3\) , то на основании определения конъюнкции заключаем, что: \(\vDash (F_1\leftrightarrow F_2)\land (F_2\leftrightarrow F_3)\) . Привлекая теперь тавтологию из теоремы 3.3, пункт р) и правило заключения для получения тавтологий (теорема 3.5), получаем \(\vDash F_1\leftrightarrow F_3\) , или (по теореме 4.2) \(F_1\cong F_3\) . Следовательно, отношение \(\cong\) транзитивно.

Таким образом, отношение \(\cong\) есть отношение эквивалентности, что и требовалось доказать.

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


Примеры равносильных формул

В теореме 4.4 перечисляются некоторые основные равносильности. Они получаются из тавтологий, приведенных в теоремах 3.1–3.4, на основании признака равносильности формул.

Теорема 4.4. Справедливы следующие равносильности:

\(\begin{array}{lll}\begin{aligned}&{\scriptstyle{\mathsf{1)}}}~~ \lnot\lnot P\cong P\,;\\ &{\scriptstyle{\mathsf{2)}}}~~ P\to Q\cong\lnot Q\to\lnot P\,;\\ &{\scriptstyle{\mathsf{3)}}}~~ P \leftrightarrow Q\cong\lnot P\leftrightarrow\lnot Q\,;\\ &{\scriptstyle{\mathsf{4)}}}~~ P\to(Q\to R)\cong (P\land Q)\to R\,;\\ &{\scriptstyle{\mathsf{5)}}}~~ (P\to R)\land(Q\to R)\cong (P\lor Q)\to R\,;\\ &{\scriptstyle{\mathsf{6)}}}~~ P\land P\cong P\,;\\ &{\scriptstyle{\mathsf{7)}}}~~ P\lor P\cong P\,;\\ &{\scriptstyle{\mathsf{8)}}}~~ P\land Q\cong Q\land P\,;\\ &{\scriptstyle{\mathsf{9)}}}~~ P\lor Q\cong Q\lor P\,;\\ &{\scriptstyle{\mathsf{10)}}}~~ P\land (Q\land R)\cong (P\land Q)\land R);\\ &{\scriptstyle{\mathsf{11)}}}~~ P\lor (Q\lor R)\cong (P\lor Q)\lor R\,;\\ &{\scriptstyle{\mathsf{12)}}}~~ P\land (Q\lor R)\cong (P\land Q)\lor (P\land R);\\ &{\scriptstyle{\mathsf{13)}}}~~ P\lor (Q\land R)\cong (P\lor Q)\land (P\lor R);\end{aligned} &\quad \begin{aligned} &{\scriptstyle{\mathsf{14)}}}~~ P\land (P\lor Q)\cong P\,;\\ &{\scriptstyle{\mathsf{15)}}}~~ P\lor (P\land Q)\cong P\,;\\ &{\scriptstyle{\mathsf{16)}}}~~ \lnot(P\land Q)\cong \lnot P\lor\lnot Q\,;\\ &{\scriptstyle{\mathsf{17)}}}~~ \lnot(P\lor Q)\cong \lnot P\land\lnot Q\,;\\ &{\scriptstyle{\mathsf{18)}}}~~ P\leftrightarrow Q\cong Q\leftrightarrow P\,;\\ &{\scriptstyle{\mathsf{19)}}}~~ P\to Q\cong \lnot P\lor Q\,;\\ &{\scriptstyle{\mathsf{20)}}}~~ P\to Q\cong\lnot P\land \lnot Q\,;\\ &{\scriptstyle{\mathsf{21)}}}~~ P\land Q\cong\lnot (P\to\lnot Q);\\ &{\scriptstyle{\mathsf{22)}}}~~ P\lor Q\cong\lnot P\to Q\,;\\ &{\scriptstyle{\mathsf{23)}}}~~ P\leftrightarrow Q\cong (P\to Q)\land (Q\to P);\\ &{\scriptstyle{\mathsf{24)}}}~~ P\lor\lnot P\cong 1,~~ P\land\lnot P\cong 0\,;\\ &{\scriptstyle{\mathsf{25)}}}~~ P\lor1\cong1,~~ P\land1\cong P\,;\\ &{\scriptstyle{\mathsf{26)}}}~~ P\lor 0\cong P,~~ P\land 0\cong0\,.\end{aligned} \end{array}\)

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

Лемма 4.5 (о замене). Если \(G(Y_1,\ldots,Y_s)\cong H(Y_1,\ldots,Y_s)\) , то для любой формулы алгебры высказываний \(F(X_1,\ldots,X_{i-1},\,Y,\,X_{i+1},\ldots,X_n)\) имеет место равносильность

\(F\bigl(X_1,\ldots,X_{i-1},\, G(Y_1,\ldots,Y_s),\, X_{i+1},\ldots,X_n\bigr)\cong F\bigl(X_1,\ldots,X_{i-1},\, H(Y_1,\ldots,Y_s),\, X_{i+1},\ldots,X_n\bigr).\)

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

Доказательство. Поскольку формулы \(G(Y_1,\ldots,Y_s)\) и \(H(Y_1,\ldots,Y_s)\) принимают всегда одинаковые значения при одинаковых значениях пропозициональных переменных \(Y_1,\ldots,Y_s\) , то формулы

\(F\bigl(X_1,\ldots,X_{i-1},\, G(Y_1,\ldots,Y_s),\, X_{i+1},\ldots,X_n\bigr)\) и \(F\bigl(X_1,\ldots,X_{i-1},\, H(Y_1,\ldots,Y_s),\, X_{i+1},\ldots,X_n\bigr)\)

принимают одинаковые значения при любых одинаковых наборах значений переменных \({ X_1,\ldots,X_n}\) и \(Y_1,\ldots,Y_s\) Следовательно,

\(F\bigl(X_1,\ldots,X_{i-1},\, G(Y_1,\ldots,Y_s),\, X_{i+1},\ldots,X_n\bigr)\leftrightarrow F\bigl(X_1,\ldots,X_{i-1},\, H(Y_1,\ldots,Y_s),\, X_{i+1},\ldots,X_n\bigr),\)

то есть \(F\bigl(X_1,\ldots,X_{i-1},\, G(Y_1,\ldots,Y_s),\, X_{i+1},\ldots,X_n\bigr)\cong F\bigl(X_1,\ldots,X_{i-1},\, H(Y_1,\ldots,Y_s),\, X_{i+1},\ldots,X_n\bigr)\) , что и требовалось доказать.

Например, на основании этой леммы и равносильности из теоремы 4.4 (пункт п), формула

\(\bigl(\lnot X_1\to (Y_1\lor (Y_1\land Y_2))\bigr)\lor X_2\) равносильна формуле \((\lnot X_1\to Y_1)\lor X_2\) .

Общая формулировка леммы о замене может быть конкретизирована в соответствии с индуктивным определением формулы следующим образом. Пусть имеется формула \(\lnot F\) . Если \(F\cong G\) , то \(\lnot F\cong\lnot G\) . Далее, пусть исходная формула имеет следующее строение: \(F_1\land F_2\) . Если \(F_1\cong G_1\) , то \(F_1\land F_2\cong G_1\land F_2\) . Если, кроме того, \(F_2\cong G_2\) , то

\(F_1\land F_2\cong G_1\land F_2\cong G_1\land G_2\) , то есть \(F_1\land F_2\cong G_1\land G_2\) .

Об этом свойстве говорят, что отношение равносильности формул стабильно относительно операции конъюнкции. (Предыдущее свойство означает стабильность относительно отрицания.) Аналогично, отношение равносильности стабильно и относительно остальных логических операций — дизъюнкции, импликации и эквивалентности. Это означает, что если \(F_1\cong G_1\) и \(F_2\cong G_2\) , то

\(F_1\lor F_2\cong G_1\lor G_2,\qquad F_1\to F_2\cong G_1\to G_2,\qquad F_1\leftrightarrow F_2\cong G_1\leftrightarrow G_2.\)

Равносильные преобразования формул

Используя лемму о замене и приведенные в теореме 4.4 равносильности, можем от одной формулы переходить к равносильной ей формуле. Такой переход называется равносильным преобразованием исходной формулы. Равносильные преобразования формул применяются прежде всего для упрощения формул.

Пример 4.6. Упростим формулу \(\lnot(X_1\to\lnot X_2)\land\lnot (X_2\to\lnot X_1)\) , используя равносильности из теоремы 4.4:

\(\begin{aligned}\lnot(X_1\to\lnot X_2)\land \lnot(X_2\to\lnot X_1)& \cong \lnot(\lnot X_1\lor\lnot X_2)\land \lnot(\lnot X_2\lor \lnot X_1)\cong\\[4pt] &\cong\lnot (\lnot X_1\lor \lnot X_2) \land\lnot (\lnot X_1 \lor \lnot X_2)\cong\\[4pt] &\cong\lnot (\lnot X_1\lor\lnot X_2)\cong \lnot\lnot X_1\land\lnot\lnot X_2\cong\\[4pt] &\cong X_1\land X_2\,.\end{aligned}\)

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

Замечание 4.7. Отметим, что если некоторая формула является тавтологией, то и всякая равносильная ей формула также является тавтологией:

\(\vDash F\) и \(F\cong H~ \Rightarrow~ \vDash H\) .

Сделанное замечание позволяет обнаружить еще одну сферу применения равносильных преобразований: доказательство тождественной истинности тех или иных формул. Для этого данную формулу нужно равносильными преобразованиями свести к формуле, очевидно, являющейся тавтологией.


Равносильности в логике и тождества в алгебре

Можно провести параллель между понятием логической равносильности формул в алгебре высказываний и известным понятием тождества школьной алгебры. Равносильность формул \(F(X_1,\ldots,X_n)\) и \(H(X_1,\ldots,X_n)\) — это не что иное, как их тождественное равенство с точки зрения школьной алгебры, с той лишь разницей, что тождественность рассматривается относительно различных базисных множеств: в школьной алгебре — относительно множества \(\mathbb{R}\) всех вещественных чисел, а в алгебре логики — относительно двухэлементного множества \(\{0;1\}\) .

Ввиду конечности базисного множества алгебры логики проверить справедливость той или иной равносильности можно механическим перебором всех возможных наборов значений (пропозициональных) переменных, входящих в равносильность, и вычислением на них значений левой и правой частей равносильности. В школьной алгебре бесконечность базисного множества \(\mathbb{R}\) не позволяет доказать ни одно тождество методом перебора всех значений входящих в него переменных. Для этого разработан метод тождественных преобразований алгебраических выражений, опирающийся на основные свойства арифметических операций над вещественными числами. Этими свойствами являются перестановочность (коммутативность) и сочетательность (ассоциативность) сложения и умножения, распределительность (дистрибутивность) умножения относительно сложения и т. п. Правда, ввиду нестрогости введения понятия вещественного числа в школьном курсе математики сами эти свойства принимаются без доказательства.

Подобно тому как в школьной алгебре понятие тождества (тождественного равенства) приводит к понятию тождественного преобразования алгебраических выражений, так в алгебре логики понятие равносильности формул естественным образом приводит к понятию равносильного преобразования формул логики высказываний. Здесь важно уяснить, что равносильные преобразования формул основываются на лемме 4.5 о замене. Равносильные преобразования используют основные равносильности, приведенные в теореме 4.4.

Полезно сравнить свойства логических операций, выраженные в основных равносильностях, со свойствами арифметических операций, помня, что некоторые логические операции имеют претензии на аналогию с некоторыми арифметическими операциями. Так, конъюнкция нередко называется логическим умножением, а дизъюнкция — логическим сложением. Наиболее разительны отличия в следующих свойствах: идемпотентность конъюнкции и дизъюнкции (это означает, что невозможны степени и "умножения" на натуральные числа), дистрибутивность дизъюнкции относительно конъюнкции, законы поглощения. Таким образом, мы приходим к некой новой алгебре, необычной по сравнению со школьной алгеброй, основанной на вещественных числах. Это и есть алгебра логики или алгебра высказываний. Равносильные преобразования в ней, как и в школьной алгебре, предназначены для приведения логических выражений (формул) к определенному виду.

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: