Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
я*-с[/*1, ...л*].
Для формул над множеством ф = {0, 1, х, х] & х2, #1V #2} принцип двойственности может быть сформулирован так: для получения формулы %*, двойственной к формуле §1, нужно в формуле 8С всюду заменить
О на 1, 1 ка 0, & на V, V на &.
ГЛ. і. АЛГЕБРА ЛОГИКИ
25
Или, если & = С[0, 1, х, хх & х2, х1 V яг], то
51* = С[1, 0, я, х1V х2, x^ & дгг]-
Пример 8.
1) Й! (хг, х2) = хх & х^й1 (я,, х2) = х1 V яа;
^2) 5=1 V'^'1*^2» ^2 (*^1» ^2) == (^1 V *^2) (*^1 V "^2^*
Из принципа двойственности вытекает, что если
51 (<Г1( * * «I *?п) ® (*^1) • • •) ^п) |
то
51* (ж1р ..хп) — 25* (хи ..., хп).
Пр имер 9. Из тождества я, &х2 — х 4 Vхг вытекает тождество х{ У хг — хх & хг.
Принцип двойственности позволяет почти в два раза сокращать усилия на вывод тождеств при рассмотрении свойств элементарных функций. Другие применения принципа двойственности -будут даны ниже.
§ 4. Разложение булевых функций по переменным. Совершенная дизъюнктивная нормальная форма
Говоря о языке формул, мы сознательно не касались весьма важйого вопроса. Если в качестве ф допустить некоторый запас элементарных функций, то всякая ли функция алгебры логики может быть выражена в виде формулы? Ближайшие рассмотрения направлены на решение этого вопроса.
Введем обозначение
/ = ад\/ а;с,
где о — параметр, равный либо 0, либо 1. Очевидно, что ст \х при а = О,
Я? |
Ух При 0=1.
Легко видеть, что х° = 1 тогда и только тогда, когда х — о, т. е. значение «основания» равно значению «показателя».
Теорема 3 (о разложении функций по переменным). Каждую фумжцшо алгебры логиш Дяц *„) при любом т (1Кт^п) можно представить в
26 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ следующей форме:
/ (?^'1* ? ? * > ’ ^11+1» ? * ? > Ял)
= & * ? * & » о«, ^тп+н • * м *„), (*)
где дизъюнкция берется по всевозможным наборам значений переменных хт.
Это представление называется разложением функции по т переменным х<, ..хт.
Доказательство. Рассмотрим произвольный набор значений переменных ..,, ап) и покажем, что левая и правая части соотношения (*) принимают па нем одно и то же значение. Левая часть дает /(... ..., ак). Правая —
(о^.У.о^ 0,11 &?•••&? атт * • - > Ст, ат+1г- . . ., 0СП) ==»
= С2ц1 & * - - & 0Стт & f (с^, . . ., ССщ, Клг4_1, - - Кл) ^
~ / (®11 ? * * I ®п)*
В качестве следствий получаем два специальных случая разложения.
1) Разложение по переменной:
. . ., Хп— ], хп)
== Хп & Хп—1, 1) V Xп & / (*^1) ? ? ч Хп~1, 0).
Функпии Цри ..., аг«-*, 0) и /(д:1т. ...» хп-1л 1) называются компонентами разложения. Данное разложение полезно, когда какие-либо свойства булевых функций устанавливаются по индукции.
2) Разложение по всем п переменным:
/ (Яц ? • • 1 &п) = {01У^п) XI1 & ... & Хпп & / (Оц ? • •, Огг).
При ${хи ..., оно может быть преобразовано:
V гГ1 & . . . & Хп11 & / {а±, . . . , СГ/г) =
= V #1* & • • ? & хпп.
(СГ11--. >°л)
ГЛ. 1. АЛГЕБРЛ логики 27
В результате окончательно получим
1 К, . . . , Хп) => V & • * ? & г«"* (**)
(°1>‘ ?*>°л)
/(^1..он)=1
Такое разложение носит название совершенной дизъюнктивной нормальной формы (совершенной д. н. ф.).
Непосредственно к понятию совершенной д. н. ф. примыкает следующая теорема.
Теорема 4. Каждая функция алгебры логики может быть выражена в виде формулы, через отрицание, конъюнкцию и дизъюнкцию.
Доказательство. 1) Пусть }(хи ..д;п)^0. Тогда, очевидно,
]{хи ..., хп) = х1&хи
2) Пусть /(Хц ..хп)Ф 0. Представим ее в совершенной д. н. ф.:
/ (^гт ? ? • 1 хп) = V Ъ1 & ? ? ? & хпп.
(°1>- >°л)
До 1 оп)=1
Таким образом, в обоих случаях функция / выражается в виде формулы через отрицание, конъюнкцию и дизъюнкцию.
Итак, оказалось, что любую булеву функцию можно задать формулой над взяв в качестве $ множество, состоящее из трех функций: отрицания, конъюнкции и дизъюнкции.
Данная теорема носит конструктивный характер, так как она позволяет для каждой функции фактически построить формулу, ее реализующую (в виде совершенной д. н. ф.): в таблице для функции }(хи ..хп) (/ ^ 0) отмечаем все строки (сь ..., о„), в которых /((Ц, ..., оп) = = 1, для каждой такой строки образуем логическое произведение
& . . . & Л#1*
и затем все полученные конъюнкции соединяем знаком дизъюнкции.
Пример 10. 1) Найти совершенную д. н. ф. для функции Х1 -* Хь
28 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
Мы имеем три набора (0, 0), (0, 1) и (1, 1), на которых эта функция равна 1 (см. табл. 3). Поэтому
Х1 & х2 V V я! & Х\ =*
*= Х1 & Х2 V Х1 & #2 V Х1 & Х'1*
2) Найти совершенную д. н. ф. для функции, заданной табл. 7.
Имеем
/(дч, г2, ЗГ3) = Х^2Хз У Х&гХэ V ХхХ&% V Х^Х*.
Совершенная д. п. ф. есть выражение типа 2П, т. е. логическая сумма произведений х®%. Спрашивается, нельзя ли для булевых функций получить разложение типа
Таблица 7
*1 X, я. Л*„ ж,, жа)
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 0 0
1 1 1 1
П2? Покажем, что при / Ф 1 это возможно, для чего разложим функцию /* {очевидна,. /* Ф 0) в совершенную д. н. ф.:
/* [х2, . . . л Х7[) = \/ ^1 & • 1 1 & Хп »
Г°1..°п)
>*(«1....°п)" 1
Возьмем тождество для двойственных формул
