Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 12
Текст из файла (страница 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-й разряд о'/т также равен О. Аналогично доказываются остальные два равенства. П Эта теорема позволяет заменить теоретико-множественные операции (объединение, пересечение, дополнение) над системой подмножеств поразрядными логическими операциями над двоичными векторами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
