Игошин Математическая логика и теория алгоритмов (1019110), страница 11
Текст из файла (страница 11)
До казател ьот в о. Поскольку формулы 6()ь ..., У,) и Н()'ь ..., У,) принимают всегда одинаковые значения при одинаковых значениях пропозициональных переменных 1;, ..., У„то формулы Р(Хь ...,Х ь 6()ь ..., Т), Х„, ...,Х) и Р(Х„..., Х ь Н(Уь ..., У,), Х;„, ..., Х) 42 принимают одинаковые значения при любых одинаковых наборах значений переменных Хь ..., Х„, )и ..., У,. Следовательно, ~ Р'(Хп ...„Х „6()п ..., У), Х;„„..., Х„) ьь <-+ Е(Хп ..., Х.
„Н()п ..., У), Хин ..., Х„), т е. Р'(Хп ..., Х и 6() ь ..., );), Х. и ..., Х„) н Г(Хь ..., Х, и Н() и ..., У,), Хп и ..., Х„), что и требовалось доказать. П Например, на основании этой леммы и равносильности из теоремы 4.4, и, формула ( Х, -ь (У, ч (Уг л Уг))) ч Х, равносильна формуле (. Х, — > У1) ч Х,.
Общая формулировка леммы о замене может быть конкретизирована в соответствии с индуктивным определением формулы следующим образом. Пусть имеется формула ~Е Если Гн 6, то Гн 6. Далее, пусть исходная формула имеет следующее строение: У; п Р~. Если У; н б„то Г, л гг н 6, и гг. Если, кроме того, Гг и 6,, то Г, п Р~ и 6, п Рг н 6, л 6г, т.е.
Г, л Гг н 6, л 6г. Об этом свойстве говорят, что отношение равносильности формул спгабильпо относительно операции конъюнкции. (Предыдущее свойство означает стабильность относительно отрицания.) Аналогично, отношение равносильности стабильно и относительно остальных логических операций — дизъюнкции, импликации и эквивалентности. Это означает, что если Р; и 6, и Рг н 6г, то Г, ч гг н :— 61 ч бг, ~'~ -+ Гг = 61 — > 6г, ь'1 ь-» Рг = 6~ «-ь 6г. Равносильные преобразования формул. Используя лемму о замене и приведенные в теореме 4.4 равносильности, можем от одной формулы переходить к равносильной ей формуле. Такой переход назгявается равносильным преобразованием исходной формулы. Равносильные преобразования формул применяются прежде всего для упрощения формул.
Пример 4.б. Упростим формулу -(Х~ — ь - Хг) л -(Хг -+ . Хг), используя равносильности из теоремы 4.4: -(Х, — > Лг) л - (Хг — г -ь -Л|) = -(- Х~ ч Хг) л -( Хг ч -чХ~) и -(-Л'~ ч Хг) п -(-Л~ ч ч - Хг) н +,Х, ч †,Хг) н †,- Хг п — — Хг н Хг л Хг. Равносильные преобразования формул применяются также для приведения формул к специальному виду или к специальной форме (к так называемой совершенной нормальной форме), имеющей исключительно важное значение как в самой алгебре высказываний, так и в ее приложениях.
Об этом речь пойдет в следующем параграфе. Замечание 4.7. Отметим, что если некоторая формула является ~автологией, то и всякая равносильная ей формула также является тавтологией: Ри ГнН=ь Н. Сделанное замечание позволяет обнаружить еше одну сферу "рименения равносильных преобразований: доказательство тожде- 43 ственной истинности тех или иных формул. Для этого данную формулу нужно равносильными преобразованиями свести к формуле, очевидно, являющейся тавтологией (см. Задачник, № 1.60, 1.61).
Равносильности в логике и тождества в алгебре. Можно провести параллель между понятием логической равносильности формул в алгебре высказываний и известным понятием тождества школьной алгебры. Равносильность формул Г(Х„ ..., Х„) и Н(Хь ..., Х„) — это не что иное, как их тождественное равенство с точки зрения школьной алгебры, с той лишь разницей, что тождественность рассматривается относительно различных базисных множеств: в школьной алгебре — относительно множества Я всех вешественных чисел, а в алгебре логики — относительно двухэлементного множества (О, Ц.
В алгебре логики В школьной алгебре Равносильность (Р л О) в Р о —,0 означает, что левая и правая его части принимают одинаковые логические значения при всех значениях пропозициональных переменных Р, Д е (О, Ц Тождественное равенство (тождество) (а + Ь)' = — аз+ 2аб+ аг означает, что выражения в левой и правой его частях принимают одинаковые значения при всех значениях вещественных переменных а, Ь и Я 44 Ввиду конечности базисного множества алгебры логики проверить справедливость той или иной равносильности можно механическим перебором всех возможных наборов значений (пропозициональных) переменных, входящих в равносильность, и вычислением на них значений левой и правой частей равносильности.
В школьной алгебре бесконечность базисного множества г( не позволяет доказать ни одно тождество методом перебора всех значений входящих в него переменных. Для этого разработан метод тождественных преобразований алгебраических выражений, опирающийся на основные свойства арифметических операций над вещественными числами. Этими свойствами являются перестановочность (коммутативность) и сочетательность (ассоциативность) сложения и умножения, распределительность (дистрибутивность) умножения относительно сложения и т. п.
Правда, ввиду нестрогости введения понятия вещественного числа в школьном курсе математики сами эти свойства принимаются без доказательства. Подобно тому как в школьной алгебре понятие тождества (тождественного равенства) приводит к понятию тождественного преобразования алгебраических выражений, так в алгебре логики понятие равносильности формул естественным образом приводит к понятию равносильного преобразования формул логики высказываний.
Здесь важно уяснить, что равносильные преобразования формул основываются на лемме 4.5 о замене. Равносиль- ные преобразования используют основные равносильности, приведенные в теореме 4.4. Полезно сравнить свойства логических операций, выраженные в основных равносильностях, со свойствами арифметических операций, помня, что некоторые логические операции имеют претензии на аналогию с некоторыми арифметическими операциями. Так, конъюнкция нередко называется логическим умножением, а дизъюнкция — логическим сложением. Наиболее разительны отличия в следующих свойствах: идемпотентность конъюнкции и дизъюнкции (это означает, что невозможны степени и «умножения» на натуральные числа), дистрибутивность дизъюнкции относительно конъюнкции, законы поглощения.
Таким образом, мы приходим к некой новой алгебре, необычной по сравнению со школьной алгеброй, основанной на вещественных числах. Это и есть алгебра логики или алгебра высказываний. Равносильные преобразования в ней, как и в школьной алгебре, предназначены для приведения логических выражений (формул) к определенному виду.
й 5. Нормальные формы для формул алгебры высказываний Для каждой формулы алгебры высказываний можно указать равносильную ей формулу, содержащую из логических связок лишь отрицание, конъюнкцию и дизъюнкцию. Для этого нужно, используя равносильности теоремы 4.4, у, ч, выразить все имеющиеся в формуле импликации и эквивалентности через отрицание, конъюнкцию и дизьюнкцию. Так, для формулы ( Хл (Х вЂ” «У)) — > У равносильной ей формулой, не содержащей логических связок — > и ~->, будет, например, формула ~( Х л ( Хч У)) ч К Выразить данную формулу через отрицание, конъюнкцию и дизъюнкцию возможно не одним способом, а многими. К примеру, рассматриваемая формула равносильна также следующим формулам, содержащим из логических связок лишь —, н и ч: Х ч У Х ч У, (Х ч У) л (.
У ч У), (Х л — У) ч У (Х л -1У) ч ((Х ч -1Х) л У), (Хн У) ч (Хл У) ч ( Х», У). Среди всевозможных выражений данной формулы через конъюнкцию, дизъюнкцию и отрицание некоторые играют важную роль как в алгебре высказываний, так и в ее приложениях. Рассмотрение таких выражений, называемых совершенными нормальными формами, и составляет цель настоящего параграфа. Понятие нормальных форм.
Хоныоннтивным одночленом от не- Ременных Х„Хъ ..., Х„называется конъюнкция этих переменных или их отрицаний. Здесь «или» употребляется в неисключающем смысле, т.е. в конъюнктивный одночлен может входить одновременно и переменная, и ее отрицание. Приведем несколько при- 45 меров конъюнктивных олночленов: Х, д Х„Х, д Хт л Х,, Х, л л-~Х1 п Хз л -»Хт п Хы Х1 л Хт л -~Х~ д Хз л Х|1. Диэьюнктивным одночленом от переменных Х„Хъ ..., Х„называется дизъюнкция этих переменных или их отрицаний (и здесь союз «или» употребляется в неисключающем смысле). Приведем примеры дизъюнктивных одночленов: — Х1 м Х, м Хз, Хт м Хт, Х, м м Хт м Хз м -1Х| м Х4 м Хъ -~Ха м Х| м -1Х4 и Х| и Х4~.
Диэьюнктивной нормальной формой называется дизъюнкция коньюнктивных одночленов, т.е. выражение вида К, м Кт ы ... м Кр, где все Кп 1 = 1, 2, ..., р, являются конъюнктивными одночлейами (не обязательно различными). Аналогично коньюнктивной нормальной формой называется конъюнкция дизъюнктивных одночленов Р, д Р, л ... д Р,, где все Рл ) = 1, 2, ..., а, являются дизъюнктивными одночленами (не обязательно различными). Будем также называть дизъюнктивной (конъюнктивной) нормальной формой указанные выражения при р = ! (а = 1). Нормальную форму, представляющую формулу Г(т.е. равносильную г"), будем называть просто нормальной формой этой формулы.
Нетрудно понять, что всякая формула обладает как дизъюнктивной, так и конъюнктивной нормальными формами. В самом деле, всякую формулу можно выразить через конъюнкцию, дизъюнкцию и отрицание. Используя законы де Моргана (теорема 4.4, р, с) и свойство дистрибутивности конъюнкции относительно дизъюнкции (теорема 4.4, м), можем преобразовать равносильным образом полученное выражение к дизъюнкции конъюнктивных одно- членов (к дизъюнктивной нормальной форме). Если же к исходному выражению применить свойство дистрибутивности дизъюнкции относительно конъюнкции (теорема 4.4, н), то его можно свести к конъюнкции дизъюнктивных одночленов (к конъюнктивной нормальной Форме).
Очевидно, что у данной формулы Гсуществует неограниченно много как дизъюнктивных, так и конъюнктивных нормальных форм. Одни из них более громоздкие и сложные, другие — более простые (см. Задачник, )хе 2.1, 2.2). Здесь мы можем продолжить до некоторого момента аналогию со школьной алгеброй. В школьной алгебре выражения типа ах, худ, (а + Ь)ио (последнее действие в них — умножение) называются одночленами, а выражения типа а + Ь, ох + Ь, ху + ио+ р (последнее действие — сложение) называются многочленами. В алгебре логики логическое умножение (конъюнкция) и логическое сложение (дизъюнкция) равноправны по своим свойствам.
Поэтому выражения типа Х д г', Х л г'д Х называются конъюнктивными одночленами, а выражения типа Хм 1; Х м 1' м У— ' Ввиду ассоциативности конъюнкции и дизъюнкции (теорема 4.4, к, л) скобки внутри каждого из данных одночденов не пишутся. ' См. предыдушую сноску. 46 дизъюнктивными одночленами. Образования из одночленов выражений типа (Х л У) ч (Р л 0 л А), (Р ч 0) л (Х ч У ч У) называются не многочленами, а нормальными формами. На этом аналогия заканчивается. Дапее вводятся понятия совершенных нормальных форм — дизъюнктивной и конъюнктивной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
