XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 65
Текст из файла (страница 65)
В том случае, когда в каждую конъюнкцию К; для каждого номера у = 1, и входит в точности один из литералов ху, ДНФ называется совершенной дизъюнктпивной норма.ланой формой (СДНФ). Двойственным образом, т.е. с использованием принципа двойстивенносгпи для булевых алгебр, определяются конъюнктпивная нормальная форма (КНФ) и совершенная коньюнкгпивная нормальная форма (СХНФ). Теорема 6.2. Любая булеза функция, отличная от константы 0 (соответственно от константы 1) представима в виде СДНФ (соответственно в виде СКНФ). а Докажем первое ю двух (взаимно двойственных) утвержде-' ний теоремы. Для функции у Е Рз,„, не равной тождественно О, рассмотрим множество С~У = Я: ~(Н) = 1). Каждый набор из С~1 называется констшпуенпьой единицы функции у.
Так б.б. Дизъювктиивые и коиъювктввиые иормеиьвые формы 407 как по условию у ф 0 тождественно, то множество С~1 не пусто. Каждому набору а Е С~У поставим в соответствие элементарную конъюнкцию Кн = х~ 'хаг'... ха", которую также называют конституентой единицы функции ~. Ясно, что Ка обращается в единицу только на наборе Н. Тогда искомой СДНФ для функции ~ будет У= ~/ Кн.
аЕС) Согласно принципу двойственности, СКНФ для той же функции будет иметь вид ~= ЛРн аеС~~ где множество наборов С~~ — — (а: ~(а) = 0), и каждый набор а кз Суе называют констпипзрентоб н1ьа,и фУнкции ~; пРи этом элементарная дизъюнкция Рн сопоставляется конституенте нуля се по следующему правилу: Ра х11 Чхге Ч Чх т.е.
если в наборе е-я компонента равна О, то в .Р- ставим само переменное х;, если иначе — отрицание переменного х; (таким образом, диэъюнкция Ра обращается в нуль только на наборе а). 1и Из доказанного следует, что любая булеза функция может быть представлена в виде формулы над стандартным базисом (СДНФ или СКНФ), и, значит, стандартный базис есть полное множество булевых функций. Рассмотрим в качестве примера построение СДНФ и СКНФ для ыахсоритиапзриоб фуюсиии (см. 6.1).
Конституентами единицы для нее служат наборы: оч = (О, 1, 1), аг = (1, О, 1), «ез = (1, 1, 0) и ае = (1, 1, 1). Им соответствуют элементарные конъюнкции: Ка = х|хгхз, Кн = хзхгхз, Кн = х1хгхз, 408 Е. БУЛЕВЫ ФУНКЦИИ Кн = х1хзхз. Тогда СДНФ, представляющая мажоритарную функцию, имеет вид х1хзхз Ч х1хзхз Ч х1хзхз Ч х1хзхз. (6.9) Для получения СКНФ для той же функции выпишем все конституенты нуля данной функции: (О, О, 0), (О, О, 1), (О, 1, 0), (1, О, 0).
Сопоставим им элементарные дизъюнкции: х1 Ч хз Ч Чхз, х1Чха Чхз, хз Чха Чхз и Из ЧхаЧха соответственно. В результате получим СКНФ для мажоритарной функции в виде (хз ЧхзЧхз)(х1ЧхзЧхз)(х1ЧхзЧхз)(х|ЧхгЧхз) (6.10) Заметим, что если в формуле СКНФ (6.10) мы раскроем скобки и преобразуем полученное выражение согласно законам булевой алгебры, проведя тем самым эквивалеюиные преобразования СКНФ, то придем к формуле СДНФ (6.9) .
6.6. Построение минимальных ДНсй СДНФ, которы строится по таблице булевой функции, зачастую оказывается весьма сложной, т.е. она содержит достаточно много эламенгпарных конъюнкций и литпералов. Необходимо уметь находить в определенном смысле минимальную ДНФ, предспзавллюи4ую исходную функцию. Уточним задачу. Определение 6.5. Булеву функцию д называют илепликанпзой' булевой функции у, если для любых наборов значений переменных из д = 1 следует у = 1. Замечание 6.7.
Напомним, что функции у и д можно рассматривать как функции от одного и того же числа переменных (см. 6.3). Обозначая это число через и, можно так уточнить 'Иногда унотребллют и термин „имнликент" (мужского рода). б.б. Построевве мвввмвльвых ДНО понятие импликанты: функция д б Рз,„есть импликанта функции У Е Рз,в, если для каждого набора Н 6 В" из д(а) = 1 следует у(а) = 1. Термин „импликанта" естественным образом ассоциируется и с логической связкой, называемой импликацией, и с одноименной булевой функцией.
Действительно, если д импликанта у, то из (д -+ у) = 1 и д = 1 следует, что и у = 1, т.е. истинно высказывание (Уо Е В )((д(Н) = 1) =ь (У(Н) = 1)). Если функция у представлена СДНФ, то любая ее элементарная конъюнкция (нонсиишденща единицы функции у) будет ее импликантой. Полезно заметить также, что если д~ и дз— импликанты у, то дизъюнкция д~ Ч дз также является импликантой ~.
Действительно, если д~ Ч дг = 1, то д~ = 1 или дг = 1. Но тогда, поскольку каждая из этих функций есть импликанта у, и д~ Ч дг есть импликанта,1. Из определения 6.5 и понятия равных бдлеоых функций (см. определение 6.2) следует, что булевы функции у и д равны, если и только если каждая из них служит импликантой другой: у =1еьд=1.
Определение 6.6. ДНФ называют минимальной, если она содержит наименьшее число лишералов среди всех ДНФ, эквивалентных ей. Обратим внимание на то, что под числом литералов в ДНФ понимают число всех подформул этой ДНФ, которые являются литералами. Так, СДНФ (6.9) содержит 12 литералов (по три литерала в каждой из четырех элементарных конъюнкций). Пример 6.10. ДНФ хатха Ч х~хз не является минимальной, так как ее можно преобразовать к эквивалентной ДНФ, не содержащей ни одного из литералов х~.
хатха Чх~хз = (х~ Ч х~)хз = хз. б. БУЛЕВЫ ФУНКЦИИ 410 Вместо четырех литералов в исходной ДНФ получаем ДНФ, состоящую из одного литерала. Определение 6.7. Длпмоб ДНФ называют число входящих в нее элементарных конъюнкций. ДНФ называют крагпчабшеб, если она имеет наименыпую длину среди всех эквивалентных ей ДНФ. Заметим, что кратчайшая ДНФ не обязана быть в то же время минимальной среди всех ДНФ, эквивалентных исходной функции. Но поиск минимальных ДНФ, как мы сейчас увидим, проводится среди кратчашпих ДНФ. Наша задача состоит в том, чтобы описать метод построения минимальной ДНФ, эквивалентной заданной булевой функции.
Мы рассмотрим простейший метод такого рода, основанные на аагоритме Кеайна — Мок-Клоски. Этот алгоритм исходит обязательно из СДНФ, которая строится по таблице функции так, как это было описано ранее (см. 6.5). Опишем последовательно этапы, составляющие алгоритм Квайна — Мак-Клоски.
1. Склейка. Пусть К~ и Кз — две элементарные коньюнкции, входящие в исходную СДНФ Ф, которая представляет функцию ~, причем для некоторого переменного х и некоторой элементарной конъюнкции К выполняются равенства К~ = хК и Кз =хК. Тогда имеем, согласно тождествам булевой алгебры, К~ЧКэ =хКЧхК=(хЧх)К=К.
Мы получаем элементарную конъюнкцию К, которая содержит на один литерал меньше, чем К~ и Кз, и является, как и обе конъюнкции К~ и Кз, импликантой у. Образно говоря, мы „склеили" две импликанты в одну, в которой число литералов на единицу меньше. Операцию получения К по К~ и Кз, описанную вьппе, можно провести и для любых двух элементарных конъюнкций подоб- 411 б.б. Построение минимальных ДНФ ного вида, составляющих любую ДНФ, эквивалентную исходной функции. Такую операцию называют простпоб склейкой импликант К1 и Кз по переменному х. Установим геометрический смысл простой склейки' (с точки зрения структуры, или „геометрии", булава куба, см.
6.1). Из доказательства теоремы о представлении булевой функции в виде ДНФ (см. теорему 6.2) мы знаем, что существует взаимно однозначное соогаае1пс1ввие между множеством элементарных конъюнкций СДНФ, представляющей функцию у, и множеством С~~ ее конституент единицы.
Это соответствие, напомним, таково, что кажДомУ набоРУ Н = (а1> ..., ао) Е С~У отвечает элементаРнаЯ конъюнкциЯ Ко = хо' ... х'„"", пРинимающая значение 1 только на наборе Н. Тогда простая склейка может быть применена только к таким двум элементарным конъюнкциим КИ и Кд, соответствУющим набоРам Н, ~3 Е С~У, что для некоторого 1 (1 < 1 < п) Се = (С11» С1>-1> ОЛ> Се>+1» Сто)> Р = (О1> ", СЕ>-1 > СЕ>> ОЛ+1> ", Сто) Это значит, что наборы а,,О таковы, что один из них домимируе1в над другим (они различаются значением только одной компоненты), т.е.
они образуют ре6ро булеза куба Во. Следовательно, простой склейке, применяемой к элементарным конъюнкциям исходной СДНФ, представляющей функцию у, подлежат те и только те элементарные конъюнкции, которые соответствуют элементам какого-либо ребра булеза куба, на котором функция у принимает единичное значение.
Образно говоря, две соседние вершины куба, на которых функция равна 1, „склеиваются" в ребро, их „соединяющее". С алгебраической же точки зрения мы из двух элементарных конъюнкций Ки и К-, получаем новую элементарную о; > о>е> конъюнкцию хо' ... х; ' 'х;++' ... х'„"", лишенную литерала хо'. 'Подробно о геометрической сути минимизации смс Ябеонскиб С.В.
412 а.вултыоункции Итак, применяя простую склейку к исходной СДНФ Ф, получаем новую ДНФ Ф1, к ней также применяем простую склейку — получаем ДНФ ФЗ, продолжаем выполнять эту операцию до тех пор, пока не окажется, что для некоторого к в ДНФ Фь уже нельзя склеить никакие две элементарные конъюнкции. Такое к всегда найдетсл, так как СДНФ Ф состоит ю конечного числа элементарных конъюнкций, а они, в свою очередь, состоят из конечного числа литералов.
Полученную в результате ДНФ Фз называют сокрапЗеккой ДНФ функции у, а ее элементарные конъюнкции — проспзыми пмзьаикакпзами булевой функции 1. Замечаиие 6.8. Понятие простой импликанты определено через процедуру многократного повторения простой склейки. Иногда простую импликанту булевой функции у определяют независимо от понятия о склейке как такую элементарную конъюнкцию в составе некоторой ДНФ, представляющей функцию ~, что удаление из нее любого литерала лишает ее свойства „быть импликантой". Например, конъюнкция х1хзхз не является простой импликантой мажорцпзарноб функции, так как ю ее СДНФ (6.9) можно удалить литерал хз и получить конъюнкцию х1ХЗ, которая будет снова импликантой функции, но уже, как будет показано далее, простой. Можно доказать, что эти два определения простой импликанты равносильны.
ф Геометрия описанного вьппе многократного повторения простой склейки, как можно показать, состоит в дальнейшем „склеивании" каждой пары соседках ребер (граней размерности 1), на которых значение функции равно 1, в грани размерности 2, соседних граней размерности 2 в грани размерности 3 и т.д. Разбираемый ниже пример поясняет зту идею. Пример 6.11. Зададим функцию ~ от трех переменных следующей СДНФ: У = Х1ХЗХЗ ЧХ1ХЗХЗ ЧХ1ХЗХЗ ЧХ1Х2ХЗ. (6.11) о.о. Построение мииимельиые ДНФ 413 Подвергнем простой склейке первую и третью, а также вторую и четвертую элементарные конъюнкции в (6.11): (6.12) У =Хгхз Ч*гхз. 100 Пример 6.12. Рассмотрим СДНФ мажоритарной функции (6.9).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
