Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров, страница 11

Например, при п=4, го=2 разложение (3.4) имеет вид: ) (х„х„х„х4) =- х~ х, Г (О, О, л;, х4) ~у х, х, Г Ь (О, 1, хм х4) '/ х1 х21 (1, О, х, х ) ~„/ х хз ( (1, 1, х, х ). Теорема доказывается подстановкой в обе части равен- ства (3.4) произвольного набора (оь ..., о, о „ь ..., о,) всех п переменных. Так как х"=1, только когда х=а, то среди 2'" конъюнкций х,1, ..., х" правой части (3.4) в 1 обратится только одна — та, в которой а~=оп ..., а =о, Все остальные конъюнкции равны О.

Поэтому получим: е в Г(о„..., о„) = о1 ... о ~(~о ..., о, о +,, ..., а„) =1(о,...., о„), т. е. тождество. П При ад=1 из (3.4) получаем разложение функции по одной переменной (хд~ хз д д хдд) хддг (О хз д хдд) дд хд Г(1~ хз д х1д) (3.6) Ясно, что аналогичное разложение справедливо для любой из и переменных. Другой важный случай — разложение по всем п переменным (т=п). При этом все переменные в правой части (3.4) получают фиксированные значения и функции в коньюнкциях правой части становятся равными О или 1, что дает: (3.6) 1(х„..., х„) = '/ хд' ... х„", д(аг ...,сд„)=д где дизъюнкция берется по всем наборам (од, ..., а,), на которых 1=1.

Такое разложение называется совершенной дизъюнктивной нормальной. формой (СДНФ) фушсцни ). СДНФ функции 1 содержит ровно столько конъюнкций, сколько единиц в таблице 1; каждому единичному набору (оь ..., о,) соответствует конъюнкция всех переменных, в которой хд взято с отрицанием, если о,=О, и без отрицания, если о,=1. Таким образом, существует взаимно однозначное соответствие между таблицей функции 1(хь ..., х ) и ее СДНФ, и, следовательно, СДНФ для всякой логической функции единственна (точнее, единственна с точностью до порядка букв н конъюнкций: это означает, что ввиду коммутатнвности дизъюнкции и конъюнкции— см. далее (3.8) — формулы, получаемые из (3.6) перестановкой конъюнкций и букв в конъюнкции, не различаются и считаются одной и той же СДНФ), Например, функция, заданная табл.

3.1, имеет СДНФ х~ хз хз д/ хд хз хз ~/ хд хд хз. Единственная функция, не имеющая СДНФ,— это константа О. Формулы, содержащие, кроме переменных (и, разумеется, скобок), только знаки функций дизъюнкции, конъюнкции и отрицания, будем называть булевьдми форлддлаидд (напомним, что знак конъюнкции, как правило, опускается). Соотношение (3.6) приводит к важной теореме.

Теорема 3,2. Всякая логическая функция может быть представлена булевой формулой„т. е. как суперпозиция конъюнкции, дизъюнкции и отрицания. Действительно, для всякой функции, кроме константы О, таким представлением может служить ее СДгтф. Константу О можно представить булевой формулой хх 1см.далее равенство (3.15)). П Булева алгебра функций и эквивалентные преобразования в ней. Пусть функция )1 задана формулой Рь а функция 1з — формулой Ез.

Подстановка Ег и Ез в дизъюнкцию х,~ч/хз дает формулу Е,~/Ез. Если взять формулу Еь эквивалентную Е, (т. е. тоже представляющую ~~), и Ез, эквивалентную Ез, то получим формулу ЕЯгз, эквивалентную Е,~/Ех (доказательство эквивалентности можно провести стандартным методом (см. 5 3.1); рекомендуем читателю его проделать). Таким образом, дизъюнкцию можно рассматривать как бинарную операцию на множестве логических фУнкций, котоРаЯ кажДой паРе фУнкций ~ь гз независимо от вида формул, которыми они представлены, одн значно ставит в соответствие фУнкцию 1,~/)з. Аналогично этому можно рассматривать конъюнкцию Как бинарную операцию, а отрицание — как унарную операцию над функциями.

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

классы формул, представляющих одну и ту же функцию. Результатом, напри. мер, дизъюнкции классов К~ и Кг считается класс всех формул, эквивалентных Р~~/Рг, где Р,спКь г",щКь Так, определенная алгебра классов формул называется алгеброй Линденбаума — Тарского. Она изоморфва булевой алгебре функций. Этот нзоморфнзм настолько очевиден, что часто — особенно в прикладных работах — возникает смешение понятий формулы н функции. Следует ясно представлять себе, что, например, логическая схема на своем выходе реализует функцию от входов; когда же речь идет об эквивалентных преобразованиях, об упро- х,(х, / х,) =х,х, /х,х,.

(3,0) Дистрибутивность дизъюнкцин относительно конъюнкции: х, ~/ (х, ха) = (х 1/ хв)(хт ~/ х,). Идемпотентность: а) хх=х; б) х'/х=-х. Двойное отрицание: (3.10) (3,11) х =х. (3 12) Свойства констант: а) хеи1=х; б) хееО г) х'/О =х; д) 0 = Правила де Моргана: а) х, х, = х, т/ х,; Закон противоречия: =0; в) хт/1=1; 1; е) 1=0.

(3.13) б) х, /х = х|хт. (3.14) хх = О. (3.15) Закон «исключенного третьего»; х'/х = 1. (3. 16) Соотношения (3.7) — (3.!б) можно . проверить указанным ранее стандартным методом — вычислением обеих частей равенств на всех наборах значений переменных. Ясно, что результат вычисления не зависит от того, как получены значения переменных, входящих в зти равенства, т.

е. от того, являются ли эти переменные независимы- 59 щении и т.д., то нмеютея в виду преобразования формул, реализующих одну и ту зие функцию. Рассмотрим теперь основные свойства булевых операций. Ассоциативность: а) х,(х х,) = (х, х,) хз; б) (х, '/ х,) '/ хв = хт '~/ (хв '/ ха). (3.7) Коммутатнвносттн а) х х, = х, х,; б) х, ~/ х, = х, '/ хъ (3,8) Дистрибутивность конъюнкции относительно дизъюнкцин: ми или, в свою очередь, получены в результате каких-то вычислений. Поэтому равенства (3,7) — (3.16) остаются справедливыми при подстановке вместо переменных любых логических функций и, следовательно, любых формул, представляющих эти функции Важно лишь соблюдать следующее правило подстановки формулы вместо переменной: при подстановке формулы Р вместо переменной х все вхождения переменной х в исходное соотношение должны быть одновременно заменены формулой Р.

Например, соотношение Р~/Р=1, полученное из (3.16), верно для любых Р, а соотношение Р~/х=1 получено из (3.16) с нарушением правила подстановки и для некоторых Р может оказаться неверным, Правило подстановки позволяет получать из соотношений (3.7) — (3.16) новые эквива. лентные соотношения. Зачем нужны эквивалентные соотношепияу Во всякой алгебре (в том числе и в булевой алгебре функций) равенство Гч — — Рз означает, что формулы Р, и Рз описывают один и тот же элемент алгебры, в данном случае одну и ту же логическую функцию (ь. Следовательно, если какая-либо формула Р содержит Р, в качестве подформулы, то замена Р~ на Рэ не изменяет элемента булевой алгебры 1, над которым производятся операции в формуле Р; поэтому Р', полученная из Г такой заменой, эквивалентна Р.

Это утверждение представляет собой правило замены подформул, которое позволяет, используя эквивалентные соотношения, получать формулы, эквивалентные данной. Подчеркнем разницу между правилами подстановки и замены. При подстановке переменная заменяется иа формулу; формула может быть любой, но требуется одновременная ее подстановка вместо всех вхождений переменной. При замене подформул может быть заменена любая подформула, однако не на любую другую, а только на эквивалентную ей. Г1ри этом замена всех вхождений исходной подформулы не обязательна Пусть имеется эквивалентность Р,=Рм где Р, и Рз содержат переменную х.

Если вместо всех вхождений х в Р1 и Рэ подставить произвольную формулу Р, то получаются новые формулы Р; и Рз, причем не обязательно Р1 — — Р1, Ре=р~, однако между собой новые формулы будут эквивалентны: Р; =- =Рз. Если же в Р, какую-либо подформулу заменить на эквивалентную ей, то получится новая формула Р;, эквивалентная Рь бо (3.17а) (3, 17б) х'/ху = х; х (х / у) = х. Докажем подробно первое равенство [для его доказательства используются последовательно соотношения ' Внимательный читатель должен был обратить внимание на то, что зти два соглашения, а также соотношения (3.13) использованы уже в формуле (3.4).

61 Пример 3,1. Возьмем первое из соотношений (3.14) и подставим х,хз вместо хь Получим х,хзхз =багха'т/хз, т. е. две формулы, неэквивалентные исходным, но эквивалентные между собой, Если же в правой части нового соотношения хгхз заменить формулой х,~/хз, эквивалентной ей в силу (3.14), а в полученной подформуле к, заменить на эквивалентную ей в силу (3.12) формулу хь то все формулы в построенной цепи преобразований хгхзхз=ькгкзт/ т/кз=ох,т/кз'/кз=ехг'/хзт/кз эквивалентны, Такие преобразования, использующие эквивалентные соотношения (запас которых можно расширять с помощью правила подстановки) и правило замены, называются эквивалентными преобразованиями.