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

Эквивалентные преобразования являготся мощным средством доказательства эквивалентности формул, как правило, более эффективным, чем их вычисление на наборах значений переменных. Рассмотрим некоторые основные эквивалентные преобразования в булевой алгебре и новые соотношения, получаемые с их помощью из (3.7) — (3.16). При этом будем иметь в виду, что в булевой алгебре принято опускать скобки в следующих двух случаях: а) при последовательном выполнении нескольких конъюнкций или дизъюнкций (например, вместо (хтхз)хз пишут х~хзхз) — это не вызывает неоднозначности ввиду ассоциативности этих операций (3.7); б) если они являются внешними скобками у конъюнкции: например, вместо (х,(хз~/хз) ) /(к х,) пишут х,(хз',/хт) '/ т/хахз.

Оба соглашения совершенно аналогичны общепринятому опусканию скобок для умножения в арифметических формулах '. 1. Упрощение формул (т. е, получение эквивалентных формул, содержащих меньшее число символов). а) Поглощение: (8.13а), (3.9), (3.13в) и (3.13аЦ: х '/ ху к й 1 ~/ ку = х(1 ~/ у) = х й 1 = х.

Второе равенство доказывается с помощью (3.9), ,"(3.11) и первого равенства: х(х ~/у) хх'/ку =х'/ху =х. б) Склеивание: (3.18) ху '/ ху =х, Доказательство: ху~/ху=х(уч/у) =хй!=х. в) Обобщенное склеивание: хг '/ уг ~/ ху = хг ',' у г. (3.19) Доказывается с помощью расщепления, т. е. применения (3.18) в обратную сторону и поглощения (3.17): к« / уз'/ку = кг'/ уг /хуз'/хуз = хг'/ уг. г) х /ху =х' ' у, (3.20) Доказательство: х~/ху = ху /ху'/«у=«у~/ху'/ху'/ '/«у = х~/у. д) Обобщением равенств (3.17а) и (3.20) является равенство «а'/Р(ка «а" в к») =-ха'/!'(О, ха, ..., «»), (3.21) При доказательстве используется разложение по хь '(3.17а) и (3.20): ха '/ 7 (х„х,, ..., х„) = х, Ч х ! (О, х„..., х„) '/ ха7(1«аруха)ха~/7(0~«»~ух») 2.

Приведение к дизъюнктивной нормальной форме '(в том числе к СДНФ). Элементарными конъюнкциями называются конъюнкции переменных или их отрицаний, в которых каждая переменная встречается не более одного раза, Дизъюнктивной нормальной Формой (ДНФ) называется формула, имеющая вид дизъюнкцни элементарных конъюнкций. Соотношение (3.19) показывает, что ДНФ функции может быть не единственной. Приведение к ДНФ делается так.

Сначала с помощью (3.12) и правил де Моргана (3.14) все отрицания «спускаются» до переменных. Затем раскрываются скобки, с помощью (3.11), (3.15) и (3.16) удаляются лишние конъюнкции и повторения переменных в коныонкциях, а с помощью (3.13) удаляются константы. Пример 3.2. ху'/х(у'/хг) (х(у~/г) ~/уг) =ху~/(ху~/ ~/ххг) (х~/(ф/г) ) уг = ху~/ху (х~/уг) (у~/г) = ху~/ 'ьгху (ху' /ууг' /к24уг) =ху~/хуг='у (х~/хг) =ху~/уг. Всякую ДНФ можно привести к СДНФ расщеплением конъюнкций, которые содержат не все переменные, например: ху 1/ хуг = хуг ',' хуг '/ хуг.

Если из формулы Р, с помощью некоторых эквивалент- ных соотношений можно получить формулу Рь то Р1 мож- но получить из Рм используя ге же эквивалентные соот- ношения; иначе говоря, всякое эквивалентное преобразо- вание обратимо. Это позволяет доказать следующую теорему, Теорема 3.3. Для любых двух эквивалентных формул Р1 н Р, существует эквивалентное преобразование Р, в Рг с помощью соотношений (3.7) — (3.16). Действительно, преобразуем Р~ и Рг в СДНФ. Пос- кольку Р, и Рз эквивалентны, то их СДЙФ совпадают.

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

Формулу х,~/..Л/х,„приведем к ДНФ й;~/...~/й' . Тогда Р=И1' /.. .'~й =й1' /.. ' /й = й1йт...й'. По правилу де Моргана отрицания элементарных конь- юнкцнй преобразуются в элементарные дизъюнкцин, что и даст КНФ. пр р з.з. *~у*р~*г *гч*у~*:~ ~р~й~*,~ то ~*ча=* ч* *=ю~а ~*чино Аналогом СДНФ является СКНФ вЂ” совершенная конъ«онктивная нормальная форма, каждая элементарная дизъюпкция которой содержит все переменные. Единст- венная функция, не име«ощая СКИФ, — константа 1. Двойственность. Функция 1«(х„..., х„) ш«зыаается двой- ственной к функции )э (х«, ..., х ), если )«(х«, ..., х„) = =7«(х,, ..., х„). Беря отрицание над обеими частями ра- венства н подставляя х«,..., х„вместо х«, ..., х„, получаем 1«(х«, „,, х,) «э (хь ..., х ) =~, (х«,, х„), т.

е. )э двойст- венна к 1«. Таким образом, отношение двойственности между функциями симметрично. Из определения двойст- венности ясно, что для любой функции двойственная фун-, кция определяется однозначно, В частности, может ока- заться, что функция двойственна самой себе. В этом случае она называется са»юдвойственной. Пример 3.4. Дизъюнкция двойственна конъюнкции (в си- лу правил де Моргана); константа 1 двойственна О; отри- цание самодвойственно. Еще один традиционный пример самодвойственной функции — ху«/хг~/уг. Пользуясь определением двойственности, нетрудно (прямой выкладкой) доказать следующее утверждение, называемое принципом двойственности: е с л и в ф о р- муле г, представляющей функ цию 1, все знаки функций заменить соответственно на знаки двойственных функций, то по- лученная формула г* будет представлять функцию 1", двойственную 1.

В булевой алгебре принцип двойственности имеет более конкретный вид, вы- текающий из ранее приведенных примеров: если в форму- ле Р, представляющей функцию 1, все конъюнкции заме- нить ««а дизъюнкции, днзъюнкции — на конъюнкции, 1 на О, О на 1, то получим формулу Р*, представляющую функ- цию 1', двойственную 1. Если функции равны, то н двойственные им функции также равны. Это позволяет с помощью принципа двойст- венности получать новые эквивалентные соотношения, пе- реходя от равенства Р«=Р, с помощью указанных замен к равенству г""«=г;,. Примером парь«соотношений, полу- чаемых друг нз друга по принципу двойственности, явля- ' ются два равенства (3.!7).

Булеза алгебра н теория множеств. В примере 2.!,в были описаны булевы алгебры множеств. Общий термин «булева алгебра» для алгебр множеств и логических функ- ций не случаен, Всякая алгебра типа (2, 2, 1) назгявается булевой алгеброй, если ее операции удовлетворяют соотношениям !З.у) — Р16). В алгебре множеств элементами являются подмножества фиксированного («универсального») множества (/ (напомним, что система всех подмнбжеств У обозначается через З (У)), операции й соответствует пересечение, операции ~/ — объединение, операции соответствует дополнение; единицей является само множество У, нулем — пустое множество.

Справедливость соотношений (3.7) — (3.16) для алгебры множеств можно показать непосредственной их проверкой. Для этого нужно рассмотреть переменные в них как множества, знаки й, ~/ заменить на П, () и показать, что если какой-либо элемент принадлежит множеству из левой части равенства, то он принадлежит правой части, и наоборот. Эту проверку мы предоставляем читателю. В предыдущих главах утке отмечалось и использовалось (см, теорему 1.2) взаимно однозначное соответствие Г между множеством а (У), где У=(аь ..., а„), и множеством В„ двоичных векторов длины и: каждому подмножеству М:-(/ соответствует двоичный вектор Г(М) =а= =(аь ..., а,), где а,=1, если а;енМ, и а;=О, если а;фМ.

Вулева алгебра (В„; ~,/, й, ) на множестве В„определяется следующим образом: для любых векторов а= = (аь ..., а„) и т= (ть ..., т,) а ~/ т = (а1 '„~ ти аг ~/ т» " а '/ т )! айт = (а,й т„а,йт,, ..., о„йт„); (3.22) а = (а„ам ..., а„). Поскольку компоненты (разряды) а; и т~ векторов а и т принимают значения 0 и 1, то указанные операции над компонентами — это просто логические операции над двоичными переменными; операции над векторами естественно назвать покомпонентными 1поразрядными) логическими операциями над двоичными векторами. Такие операции (наряду с логическими операциями над переменными) входят, в частности, в систему команд любой современной ЭВМ, Выполнение их очень просто: вектор а~/т содержит единицы во всех разрядах, в которых есть 1 либо в а, либо в т, вектор айт — в тех разрядах, в которых есть 1 и в а и в т; вектор а содержит единицы в тех разрядах, в которых а содержит нули. Например, если а=01011, т=11010, то а~/т= 11011, айт=010!О,а= 10100.

5 — 750 65 Теорема 34. Если (У(=и, то булева алгебра (ЗЗ (У); Д, (), ) изоморфна булевой алгебре (В„, ~/, й, -). Взаимно однозначное соответствие Г между подмножествами 0 и векторами из В, было описано ранее. Остается показать, что à — нзоморфизм, т. е. что для него выполнено условие (2.1), которое в данном случае сводится к трем равенствам: если Г(М~) =а, а Г(Мэ) =т, то Г (М~ Ц МД = а ~/ т; Г'(Мг 1-1 М,) = а й т; (3.23) Г(М~) = о.

Справедливость нх вытекает непосредственно из (3.22): если а;енМ,()Мм то 1-й разряд вектора Г(М~()Мэ) =1; с другой стороны, это означает, что а;енМ~ или а;енМм т. е. о;=1 или т;=!, и, следовательно, 1-й разряд вектора о~/т равен 1. Если же а;ЯМ,()Мь то 1-й разряд Г(М~()Мэ) равен О. Но тогда а;фМ, и а~Мм следовательно, 1-й разряд о'/т также равен О. Аналогично доказываются остальные два равенства. П Эта теорема позволяет заменить теоретико-множественные операции (объединение, пересечение, дополнение) над системой подмножеств поразрядными логическими операциями над двоичными векторами.