Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]


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

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


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


Определение 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.


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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved