4.6. Равносильность логических формул

 

Рассмотрим следующую логическую формулу (А®В) Ù (В®А). Построим таблицу истинности данной формулы.

 

 

Если мы сравним построенную таблицу истинности формулы (А®В) Ù (В®А) с таблицей истинности эквивалентности А«В, то окажется, что при одних и тех же значениях переменных А и В значения одинаковы. Такие логические формулы называются равносильными. Равносильность формул обозначается с помощью знака º :

А«В º (А®В) Ù (В®А).

Таким образом, эквивалентность довольно просто выражается через комбинацию двух импликаций, соединенных операцией конъюнкция.

 

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

 

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

Легко показать равносильность А®В ºÚ B, заменяющую операцию импликации на дизъюнкцию высказываний  и B.  Такое определение операции импликация рассматривалось еще в Древней Греции в IV в. до н.э. логиком Филоном из Мегары и было исключительно плодотворным.

Выше мы показали, что эквивалентность выражается через операции импликации и конъюнкцию, а импликация, в свою очередь, через дизъюнкцию и отрицание. Таким образом, любую логическую формулу можно заменить на равносильную, в которой используются только операции отрицания, дизъюнкции и конъюнкции. Это особенно важно для использования математической логики в электротехнике, где элементная база построена на применении трех булевых операций.

 

Пример 4.2. Доказать равносильность логических формул: АÚѮ и (А®В)Ù(С®В).

Решение. Построим таблицы истинности для каждой формулы:

Из таблиц истинности видно, что при любых значениях переменных А, В и С соответствующие значения и левой, и правой формул одинаковы.

Значит, АÚѮ º (А®В)Ù(С®В).

 

Равносильность логических формул аналогична тождествам, которые изучаются в курсе алгебры средней школы: ,   и т.д. И там тождество означает равенство правой и левой формул при любых значениях переменных x и y. Однако равносильность формул логики можно проверить, непосредственно перебрав все комбинации значений переменных. В элементарной алгебре так поступить нельзя, потому что алгебраические формулы определены для бесконечного множества действительных чисел. Правда, если в логические формулы входит много переменных, то число наборов значений переменных быстро растет. Как было отмечено ранее, для 10 переменных число наборов значений более тысячи, для 20 – более миллиона. Вычисление всех значений истинности таких формул, а в приложениях логики высказываний число переменных, как правило, велико, очень трудоемкая задача. Поэтому также как и в элементарной алгебре для установления тождественных равенств формул в логике используются законы: ассоциативный, коммуникативный, дистрибутивный и многие другие. Они позволяют преобразовывать одни логические формулы в другие, равносильные им.

 

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

АÚВº ВÚА,	АÙВº ВÙА	Коммутативные законы
АÚ(ВÚС)º (АÚВ) Ú С,	АÙ(ВÙС)º (АÙВ) Ù С	Ассоциативные законы
АÚ(ВÙС)º (АÚВ) Ù (АÚС),	АÙ(ВÚС)º (АÙВ) Ú (АÙС)	Дистрибутивные законы
А Ú А º А,	А Ù А º А	Законы идемпотентности
АÚ(АÙВ)º А,	АÙ(АÚВ)º А	Законы поглощения
,		Законы де Моргана
А Ú 0 º А,	А Ù 1 º А	Операции с константами
А Ú 1 º 1,	А Ù 0 º 0

 

Приведенные выше законы, во-первых, можно рассматривать как свойства операций отрицания, дизъюнкции и конъюнкции. А, во-вторых, эти законы служат для упрощения сложных логических формул. Так, коммутативный закон позволяет переставлять выражения, связанные операциями дизъюнкции Ú и конъюнкции Ù, и выполнять их в любой последовательности (Вспомним из элементарной математики: «От перемены мест слагаемых сумма не меняется»):

B Ú Ú (С Ú B) º (С Ú B) Ú B Ú º B Ú (С Ú B) Ú .

Согласно ассоциативному закону можно опускать скобки между любым числом членов, связанных одинаковыми операциями Ú или Ù:

(B Ú ) Ú (С Ú B) º B Ú Ú С Ú B.

Законы идемпотентности дают возможность одинаковые выражения, связанные конъюнкцией или дизъюнкцией, заменять одним:

B Ú Ú С Ú B º B Ú B Ú Ú С º B Ú Ú С.

С помощью дистрибутивных законов можно раскрывать скобки при выполнении операций Ú или Ù. Дистрибутивность конъюнкции относительно дизъюнкции в логике аналогична соответствующему закону алгебры: a × (b+c) = a× b + a× c. Для дизъюнкции подобную аналогию провести нельзя.

 

Из рассмотренных тождеств можно заметить, что знаки Ú и  Ù симметричны. Каждому тождеству со знаком Ú соответствует аналогичное со знаком Ù.

Рассмотрим формулы, в которых содержатся лишь операции отрицания, дизъюнкции и конъюнкции. Как было показано выше, любую формулу можно привести к такому виду. Для таких формул можно сформулировать так называемый закон двойственности.

 

Закон двойственности. Если в двух равносильных формулах заменить дизъюнкцию  конъюнкцией, единицу нулем и наоборот, то полученные формулы будут также равносильны.

 

Из законов Моргана вытекает еще одно важное свойство. Оказывается, что операцию дизъюнкция можно выразить через отрицание и конъюнкцию, и наоборот. Действительно, рассмотрим формулу . На основании закона Моргана получим: . А знаки двойного отрицания можно убрать º А и º В. Следовательно,

АÚВº. Аналогично доказывается  равносильность АÙВº, выражающая конъюнкцию через отрицание и дизъюнкцию.

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

Подобно этому, в элементарной алгебре степень с целочисленным показателем можно выразить через произведение одинаковых множителей: , а произведение, в свою очередь, заменить сложением 5×a=a+a+a+a+a. Ясно, что избыточность в определениях и обозначениях не всегда является недостатком.

Роль связок ® и ~ отнюдь не ограничивается краткостью записи логических формул. Эти операции эффективно используются при описании закономерностей логических заключений.

        

         Основы логики высказываний в какой-то мере аналогичны обычной элементарной алгебре, хотя и имеют свои характерные закономерности. Поэтому эта часть логики еще называется булевой алгеброй в честь английского математика Джорджа Буля (1815 – 1864). Логическое исчисление Буля было изложено в его работах «Математический анализ логики, или Опыт исчисления дедуктивных умозаключений» (1847 г.), «Логическое мышление» (1848г.), «Исследование законов мышления, на коих основаны математические теории логики и вероятностей» (1854г.). Идеи Дж. Буля были развиты Огастесом де Морганом, Чарльзом Пирсом и др.

Предыдущая | Главная | Глава 4 | Следующая