Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 13
Текст из файла (страница 13)
Такая замена часто используется при программировании, поскольку представление двоичных векторов и поразрядные операции над ними в ЭВМ реализуются очень просто. Рассмотрим теперь множество Р,(т) всех логических функций гп переменных хь ..., х . Оно замкнуто относительно операций Й, ~/ (результат их применения к функциям нз Рз(т) снова дает функцию из Рз(т) ) и, следовательно, образует конечную булеву алгебру (Р,(т); ~/, й, ), являющуюся подалгеброй булевой алгебры логических функций. Теорема 3.5. Если (У(= 2, то булева алгебра множеств (З (Ц; (), Ц, -) изоморфна булевой алгебре функций (Р (т); ~, Ь, ). Прежде всего отметим, что эти две алгебры равномощны и содержат 2' элементов. Кроме того, поскольку все множества одинаковой мощности порождают изоморфные булевы алгебры множеств (см. пример 2.2,д), то теорему достаточно доказать для какого-либо конкретного У, удовлетворяющего условию ~ У~ =2"'. В качестве такого У возьмем множество В и, следовательно, будем доказывать изоморфизм между (ю(В ); (), Д, — ) и (Рз(т); ~/, Ь, ).
Обозначим через М~ множество единичных наборов функции Г"; тогда набор а из В„, принадлежит Мь если и только если Г(о) =1. Соответствие Г(1) =М~ между функциями н их единичными множествами является взаимно однозначным соответствием между Р,(т) и ю(В ), поскольку различным функциям соответствуют различные множества, и наоборот.
(Функцию Г, единичным множеством которой служит М, называют характеристической функцией множества М.) Покажем, что Г является изоморфизмом, Для этого достаточно проверить условие (2.1), которое в данном случае сводится к трем равенствам Г (1 / д) = М, () М;, ГУйй) =М~й Ме; Г(Г) =М, для любых функций 1" и я т переменных. Докажем первое из них. Г1усть аенГ ((~/й). Тогда Г(о) ~/д(о) =1, следовательно, Г(о) =1 или а(а) =1 и, значит, оеиМ~ или аяМе, откуда следует, что аев (М~()М ). Обратный случай: аев (М~()Ме).
Тогда аенМ~ илн аевМе и, следовательно, Г(а) =1 или д(а) =1. Поэтому Г(о) ~/д(о) =1 н аевГ()~/й), Аналогично доказываются и остальные два равенства. Замечание. Во избежание путаницы обращаем внимание читателя на различия объектов в доказанных нами теоремах. 1, В теореме 3.4 фигурировали алгебры со следующими основными множествами: Г/=(аь ..„а ) — множество произвольной природы и любой конечной мощности а; ю (Г/)— множество подмножеств Г/ мощности 2', „— множество двоичных векторов длины и также мощности 2".
В теореме 3.5 участвовали: то же множество Г/, но с дополнительным условием а=2~ (т — любое натуральное число);  — конкретное множество Г/ с этим же условием; )В ~ =2; множество Р,(т) логических функций т переменных; ~Ре(т) ~ =2'; (В ) — множество подмножеств В; 1'ю(В ) ) =2з 2. Множества В, и В, хотя и имеют одну и ту же природу (состоят из двоичных наборов), использовались в теоремах 3.4 и 3.5 по-разному. В теореме 3.4 была использована структура элементов В„, благодаря чему над ними оказались возможными поразрядные логические операции. Подмножества В„не рассматривались. В теореме 3.5 дует, что, булевы операции над функциями, заданнымн таблицами, сводятся к поразрядным логическим операциям над столбцами значений функций.
Пример приведен в табл. 3.4, содержащей две О О о О О 1 о ! о О 1 1 о о 1 О 1 1 ! О 1 1 1 о О 1 ! о о о 1 О 1 1 О О О ! О О 1 1 ! О ! О 1 о о о о 1 ! О о о 1 О ! функции ( и д и результаты булевых операций над ними. В завершение отметим еще один факт, связывающий логические функции с основными понятиями теории множеств: если ((->д)= — 1, то М!ыМа.
Действительно, если (~ — >В) = — 1, то из определения импликации (табл. 3.3, функция ф!з) следует, что ни для какого набора и не может быть одновременно ((с.) =! и д(о) =О, Поэтому если ((о) =1, то п(о) =(, т. е. если оепМь то оепМз и, следовательно, М>~Ма. В таком случае говорят, что функция ) имплицирует функцию д. При этом если ( — элементарная конъюнкция, то ( называется импликангом д, а если после удаления буквы (вхождения переменной) ~ перестает быть импликантом д, то ( называется простым импликантом и. Например, для функции х(у~>>а) конь!онкции ху и ха— простые импликанты, а хуг — импликант, но не простой. Отметим, гго любая конъюнкция любой ДНФ данной функции является импликантом этой функции.
ДНФ, интервалы и покрытия. Теоретико-множественная интерпретация булевой алгебры функций оказывается очень удобным языком для изучения дизъюиктивных нормальных форм (ДНФ) и построения методов их упрощения. Рассмотрим кратко основные понятия, связанные с ДНФ, структура элементов В„ые учитывалась, само В„было выбрано только для естественности и наглядности, зато рассматривалась 6(В„) — система подмно>кеств В,. Теоремы 3.4 и 3.5 указывают на тесную связь между множествами и логическими функциями н позволяют переходить от операций над множествами к операциям над функциями и обратно. В частности, они дают возможность непосредственно производить операции над функциями, заданными не формулами, а таблицами или единичными множествами.
Из теорем 3А и 3.5 сле- Если функция ((хь ..., х ) представляется элементарной конъюнкцией всех т переменных, то М1 содержит ровно один элемент множества В . Если же 1 — элементарная конъюнкция й переменных„где й(т, то М1 содержит 2 ' двоичных наборов (так как пг — й переменных, не вошедших в эту конъюнкцию, несущественны для 1 и могут принимать любые 2» значений, не изменяя 1). Множество Мт такой функции 1" называется интервалом.
Например, ,цлЯ пг=4 и 1 (хь хг, хг, х») =хгх4 М1=(0100, 0110, 1100, 11!О) и ~М1 ~ =2'=4. В этом случае говорят, что конъюнкция хгх4 (точнее, интервал М„-„) покрывает множество М1 (и все его подмножества). Представление 1 в виде ДНФ соответствует представлению ее единичного множества в виде объединения интервалов; в совокупности все конъ1онкции ДНФ покрывают все единичное множество ). Верно и обратное: если все элементы некоторого интервала М» принадлежат Мы то существует ДНФ функции 1, содержащая конъюнкцию й. В частности, СДНФ функции 1' соответствует просто перечислению элементов Мь Отношение покрытия между конъюнкциями ДНФ и элементами М1 наглядно задается таблицей покрытия, строки которой соответствуют конъюнкциям (т.
е, интервалам), столбцы— элементам Мь а на пересечении строки 1 со столбцом 1 стоит какая-либо отметка (например, 1), если 1-я конъюнкция покрывает 1-й элемент Мь Например, ДНФ Р=ха'ч' ~!уа'1/ху соответствует таблица покрытия (табл. 3.5). Из табл, 3.5 видно, что интервал М „покрывается объе- Таблица З.б динением интервалов М„, и М„-,.
Поэтому исключение ху из г" не изменит единичного множества данной функции и полу. чится теоретико-множестненное доказательство соотношения (3.19). Еще более очевидное О1О 1О1 хг и? хк обоснование имеет закон поглощения х~ 'ху=х: интервал М„и всегда покрывается интервалом М,. Этот закон в терминах ДНФ можно переформулировать следующим образом: »побой импликант й ДНФ, не являющийся простым, можно заменить простым импликантом йы покрывающим й; импликант йг получается, из й вычеркиванием некоторых букв. Таким образом, для любой функции 1 существует ДНФ Р, состоящая только из простых импликантов. Ясно, что ДНФ Е~/й, где й — простой имплнкант Г, не содержащийся в Р, также представляет ), Поэтому дизъюнкция всех простых нмплнкантоз ), называемая сокращенной ДНФ, также будет представлять ).
Методы упрощения ДНФ (а нх в настоящее время известно довольно много) состоят, как правило, из двух этапов На первом этапе получают список всех простых нмпликантов, т. е. сокращенную ДНФ. Это можно сделать, например, при помощи эквивалентных преобразований. На втором этапе, используя таблицу покрытия (или аналогичные методы), удаляют «лишние» импликанты, покрываемые другими импликантами. ДНФ, из которой нельзя удалить ни одного импликанта, называется тупиковой.
3.3. ПОЛНОТА И ЗАМКНУТОСТЬ В $3.1 рассматривались два способа задания логических функций — табличный и формульный. Таблица задает функцию непосредственно как соответствие между двоичными наборамн и значениями функции на этих наборах, Этот способ универсален, т. е. пригоден для любой функции, однако громоздок.
Формула — гораздо более компактный способ задания функции, однако она задает функцию через другне функции. Поэтому для любон системы функций Х возникает естественный вопрос: всякая ли логическая функция представима формулой над Х? В 5 3.2 был получен УтвеРдительный ответ длЯ системы Хо=(х, 'чт, ) (теорема 3.2). В настоящем параграфе будет показано, как решать этот вопрос для произвольной системы Х. Функционально полные системы. Система функции Х называется функционально полной системой, если любая логическая функция может быть представлена формулой над Х, т.
е. является суперпозицией функций из Х. Из теоремы 3.2 следует, что система Хо=(х, 'т/, ) функционально полна, Функционально полной будет и любая система Х, через функции которой можно выразить дизъюнкцию, конъюнкцию и отрицание, Действительно, для любой логической функции ( представляющую ее формулу над Х можно построить так: взять булеву формулу для ) (по теореме 3.2 такая формула обязательно найдется) и все булевы операции в ней заменить' формулами над Х, представ- ' Такую замену следовало бы описать более точно.
Мы этого не делаем из-за громоздкости, надеясь, что она будет ясна из примеров. лающими эти операции, Аналогично доказывается и более общее утверждение: если все функции функционально полной системы Х" представимы формулами над системой Х, то Х также функционально полна. В этом случае будем говорить, что Х сводится к Х"'. Такое сведение широко используется в дальнейшем. Пример 3.6.. а. Системы Х1 — (а, -) и Хз=(з/, ) функционально полны. Действительно, из законов де Моргана н двойного отрицания следует, что в каждой из этих двух систем недостающая до Х, функция выражается через остальные две: х, '/ х, = х, Ь х„х, й х, = х, з/ х, .
(3.24) Булева формула х,х~з/хз (хзз/хз) в системе Х, перейдет в формулу х1хзхзхзхм а в системе Хз — в формулу хК хз з/хзз/хз '4хз. С точки зрения функциональной полноты систему Хз можно считать избыточной: она сохраняет свойства полноты и при удалении из нее дизъюнкции или конъюнкции. Отметим, правда, что, как видно из примера, за неизбыточность систем Х, и Хз приходится платить избыточностью формул: ведь каждая замена одной операции на другую по соотношению (3.24) вносит в формулу лишние отрицания. б, Системы Х,=(1) (штрих Шеффера) и Х,=(() (стрелка Пирса) функционально полны, так как из (3.2), (3.3) следует, что х=х) х=х4х; х1з/хз=х1(хз= (х1 эхз) э (х4хз); х~хз=х~)хз —— (х,1хз) ) (х1)хз), следовательно, Хз сводится кХь а Хз — кХз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
