Логическая равносильность формул
Понятие равносильности формул
Определение 4.1. Формулы и алгебры высказываний называются равносильными (эквивалентными), если при любых значениях входящих в них пропозициональных переменных логические значения получающихся из формул и высказываний совпадают. Для указания равносильности формул используют обозначение . Определение равносильности формул можно записать символически для любых конкретных высказываний
(4.1)
Не следует думать, что в обе формулы и непременно входят одни и те же переменные. Некоторые из переменных могут фактически отсутствовать в любой из них. Проверим, например, равносильность формул и . Для этого составим таблицы истинности обеих формул и убедимся, что значения истинности получающихся из них высказываний одинаковы для любых одинаковых наборов значений пропозициональных переменных и
Проверьте самостоятельно справедливость равносильностей
Выписывание в предыдущем определении в формулах и одних и тех же пропозициональных переменных обусловлено стремлением сделать записи и рассуждения более краткими и лаконичными. Это замечание следует иметь в виду и далее.
Для лучшего усвоения понятия равносильности формул алгоритм проверки на равносильность двух формул и можно представить в виде условной схемы (приведена в тексте). Формулы и заданы своими таблицами значений:
Алгоритм проверки формул на равносильность
Проанализируйте работу данного алгоритма и сопоставьте ее с определением понятия равносильности формул.
Признак равносильности формул
Сущность признака состоит в выявлении тесной связи между понятием равносильности формул и понятием тавтологии.
Теорема 4.2 (признак равносильности формул). Две формулы и алгебры высказываний равносильны тогда и только тогда, когда формула является тавтологией:
(4.2)
Доказательство. Если , то по определению 4.1 для любых высказываний . Тогда (по определению 1.9 операции эквивалентности) , откуда на основании соотношения (1.5) заключаем, что для любых . Последнее означает по определению тавтологии, что . Обратными рассуждениями доказывается утверждение: если , то . Итак, теорема доказана.
Отметим, что равносильность формул — это не (логическая) операция над формулами, а отношение между формулами логики высказываний. Это означает, что если и — формулы, то выражение уже не является формулой алгебры высказываний; оно — утверждение о некотором взаимоотношении между формулами и , лишь сокращенная (символическая) запись утверждения (высказывания) " равносильна " об этих формулах. Это утверждение либо истинно, либо ложно, т.е. и либо находятся в отношении равносильности, либо нет. В приведенном далее следствии из теоремы 4.2 устанавливаются некоторые свойства этого отношения между формулами алгебры высказываний.
Следствие 4.3. Отношение равносильности между формулами алгебры высказываний:
а) рефлексивно: ;б) симметрично: если , то ;в) транзитивно: если и , то , т.е. отношение равносильности является отношением эквивалентности.
Доказательство. Рефлексивность следует непосредственно из тавтологии теоремы 3.3, о и теоремы 4.2.
Для доказательства симметричности отношения предположим, что , т.е. на основании признака равносильности (теорема 4.2) . Тогда по тавтологии теоремы 3.3, пункт п) заключаем: формула принимает всегда те же самые значения, что и формула , т.е. только истинные значения. Следовательно, или (по признаку равносильности) . Симметричность доказана.
Наконец, если и , т.е. и , то на основании определения конъюнкции заключаем, что: . Привлекая теперь тавтологию из теоремы 3.3, пункт р) и правило заключения для получения тавтологий (теорема 3.5), получаем , или (по теореме 4.2) . Следовательно, отношение транзитивно.
Таким образом, отношение есть отношение эквивалентности, что и требовалось доказать.
Как и всякое отношение эквивалентности, отношение = разбивает множество, на котором оно задано, на непересекающиеся классы эквивалентных элементов. В данном случае множество всех формул алгебры высказываний распадается на попарно непересекающиеся классы, в каждом из которых находятся равносильные между собой формулы. Один класс, например, образуют все тавтологии, другой — все тождественно ложные формулы; имеется и много других классов.
Примеры равносильных формул
В теореме 4.4 перечисляются некоторые основные равносильности. Они получаются из тавтологий, приведенных в теоремах 3.1–3.4, на основании признака равносильности формул.
Теорема 4.4. Справедливы следующие равносильности:
Сформулируем и докажем лемму о замене, которая служит основанием для равносильных преобразований и упрощения формул.
Лемма 4.5 (о замене). Если , то для любой формулы алгебры высказываний имеет место равносильность
Другими словами, если в формуле некоторую ее подформулу заменить на равносильную ей формулу, то полученная формула будет равносильна исходной.
Доказательство. Поскольку формулы и принимают всегда одинаковые значения при одинаковых значениях пропозициональных переменных , то формулы
и
принимают одинаковые значения при любых одинаковых наборах значений переменных и Следовательно,
то есть , что и требовалось доказать.
Например, на основании этой леммы и равносильности из теоремы 4.4 (пункт п), формула
равносильна формуле .
Общая формулировка леммы о замене может быть конкретизирована в соответствии с индуктивным определением формулы следующим образом. Пусть имеется формула . Если , то . Далее, пусть исходная формула имеет следующее строение: . Если , то . Если, кроме того, , то
, то есть .
Об этом свойстве говорят, что отношение равносильности формул стабильно относительно операции конъюнкции. (Предыдущее свойство означает стабильность относительно отрицания.) Аналогично, отношение равносильности стабильно и относительно остальных логических операций — дизъюнкции, импликации и эквивалентности. Это означает, что если и , то
Равносильные преобразования формул
Используя лемму о замене и приведенные в теореме 4.4 равносильности, можем от одной формулы переходить к равносильной ей формуле. Такой переход называется равносильным преобразованием исходной формулы. Равносильные преобразования формул применяются прежде всего для упрощения формул.
Пример 4.6. Упростим формулу , используя равносильности из теоремы 4.4:
Равносильные преобразования формул применяются также для приведения формул к специальному виду или к специальной форме (к так называемой совершенной нормальной форме), имеющей исключительно важное значение как в самой алгебре высказываний, так и в ее приложениях. Об этом речь пойдет в следующей лекции.
Замечание 4.7. Отметим, что если некоторая формула является тавтологией, то и всякая равносильная ей формула также является тавтологией:
и .
Сделанное замечание позволяет обнаружить еще одну сферу применения равносильных преобразований: доказательство тождественной истинности тех или иных формул. Для этого данную формулу нужно равносильными преобразованиями свести к формуле, очевидно, являющейся тавтологией.
Равносильности в логике и тождества в алгебре
Можно провести параллель между понятием логической равносильности формул в алгебре высказываний и известным понятием тождества школьной алгебры. Равносильность формул и — это не что иное, как их тождественное равенство с точки зрения школьной алгебры, с той лишь разницей, что тождественность рассматривается относительно различных базисных множеств: в школьной алгебре — относительно множества всех вещественных чисел, а в алгебре логики — относительно двухэлементного множества .
Ввиду конечности базисного множества алгебры логики проверить справедливость той или иной равносильности можно механическим перебором всех возможных наборов значений (пропозициональных) переменных, входящих в равносильность, и вычислением на них значений левой и правой частей равносильности. В школьной алгебре бесконечность базисного множества не позволяет доказать ни одно тождество методом перебора всех значений входящих в него переменных. Для этого разработан метод тождественных преобразований алгебраических выражений, опирающийся на основные свойства арифметических операций над вещественными числами. Этими свойствами являются перестановочность (коммутативность) и сочетательность (ассоциативность) сложения и умножения, распределительность (дистрибутивность) умножения относительно сложения и т. п. Правда, ввиду нестрогости введения понятия вещественного числа в школьном курсе математики сами эти свойства принимаются без доказательства.
Подобно тому как в школьной алгебре понятие тождества (тождественного равенства) приводит к понятию тождественного преобразования алгебраических выражений, так в алгебре логики понятие равносильности формул естественным образом приводит к понятию равносильного преобразования формул логики высказываний. Здесь важно уяснить, что равносильные преобразования формул основываются на лемме 4.5 о замене. Равносильные преобразования используют основные равносильности, приведенные в теореме 4.4.
Полезно сравнить свойства логических операций, выраженные в основных равносильностях, со свойствами арифметических операций, помня, что некоторые логические операции имеют претензии на аналогию с некоторыми арифметическими операциями. Так, конъюнкция нередко называется логическим умножением, а дизъюнкция — логическим сложением. Наиболее разительны отличия в следующих свойствах: идемпотентность конъюнкции и дизъюнкции (это означает, что невозможны степени и "умножения" на натуральные числа), дистрибутивность дизъюнкции относительно конъюнкции, законы поглощения. Таким образом, мы приходим к некой новой алгебре, необычной по сравнению со школьной алгеброй, основанной на вещественных числах. Это и есть алгебра логики или алгебра высказываний. Равносильные преобразования в ней, как и в школьной алгебре, предназначены для приведения логических выражений (формул) к определенному виду.
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.
|