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

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

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

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

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


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

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


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


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


[math]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).[/math]
(4.1)

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


[math]\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}[/math]

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


[math]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.[/math]

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


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


[math]\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}[/math]


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



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




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


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


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


[math]F\cong H\quad \Leftrightarrow\quad \vDash F\leftrightarrow H.[/math]
(4.2)

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


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


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


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

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


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


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


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


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




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


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


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


[math]\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}[/math]


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


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


[math]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).[/math]

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


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


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

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


[math]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),[/math]

то есть [math]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)[/math], что и требовалось доказать.


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


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

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


[math]F_1\land F_2\cong G_1\land F_2\cong G_1\land G_2[/math], то есть [math]F_1\land F_2\cong G_1\land G_2[/math].

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


[math]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.[/math]



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


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


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


[math]\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}[/math]

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


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


[math]\vDash F[/math] и [math]F\cong H~ \Rightarrow~ \vDash H[/math].

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




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


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


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


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


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


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


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

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