XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 66
Текст из файла (страница 66)
Имеем следующие склейки: Х1ХЗХЗЧ Х1Х2ХЗ = Х2ХЗ, Х1ХЗХЗ У Х1Х2ХЗ = Х1ХЗ) Х1хгх3 Ч Х1ХЗХЗ = Х1хг. С геометрической точки зрения склейка первой и третьей коньюнкций в формуле (6.11) означает, что функция у принимает единичное значение на ребре (000,100] (рис. 6.6), а склейка второй и четвертой конъюнкций точ- 111 но так же определяет ребро 1001, 101], О Эти ребра являются соседними, и, кроме того, оказывается, что функция у 011 110 принимает единичное значение и на О другой паре соседних ребер: (000, 001] ОО1 О1О и [100, 10Ц.
Здесь сказывается существенное отличие „геометрии" булеза куба от классической: в булевом кубе ребро — это пара вершин, между которыми нет никаких „точек". Тогда любая пара соседних ребер образует грань размерности 2, любая пара соседних граней размерности 2 образует грань размерности 3 и т.д. Таким образом, если функция принимает единичное значение на двух соседних ребрах булева куба, то она равна 1 в любой точке образуемой ими грани размерности 2, если она равна 1 на двух параллельных соседних гранях размерности 2, то она равна 1 на соответствующей грани размерности 3 и т.д.
Применяя простую склейку к (6.12) (по переменному хз), получаем 1(хг,хг,хз) = хг. Побочным результатом склейки явилось и удаление фихвгивммх переменных функции х1 и хз. 414 б. БУЛЕВЫ ФУНКЦИИ В данном случае сразу получаем сокращенную ДНФ: Ф1=х1хгЧх1хзЧхгхз 1г Для булевых функций от трех и четырех переменных процедура склейки наглядно и просто выполняется на так называемых маршах Хармо. Форма карт Карно, представляющих собой прямоугольные таблицы, для функции от трех переменных показана на рис. 6.7, а для функции от четырех переменных— на рис. 6.8. На рис. 6.7 строки отмечены наборами значений переменного хз, а столбцы — хг, хз, а на рис. 6.8 строки— наборами значений переменных хм хг, а столбцы — хз, х4. Рис.
6.Т Рис. 6.8 Карта Карно есть не что иное, как форма таблицы для определения булевой функции. Каждал клетка карты задается своим набором значений переменных, причем в клетках, соответствующих конституентам единицы данной функции, ставится единица, тогда как остальные клетки остаются пустыми. Карта Карно устроена так, что наборы, определяющие любые две соседние клетки, различаются в точности в одной позиции (т.е. различаются значениями ровно одной компоненты), причем клетки (одной и той же строки вли одного и того же столбца), примыкающие к противоположным сторонам прямоугольника, также являются соседними в только что определенном смысле.
Это можно представить себе так, что карта 415 6.6. Построенне мвннмлльных ДНФ „закручивается" в „цилиндр" по обоим направлениям, т.е. в „тор". С геометрической точки зрения карта Карно есть способ изображения булева куба (размерностей 3 и 4)'. Любая пара соседних клеток (с учетом „закрученности" карты) определяет некоторое ребро булеза куба, а любой прямоугольник, состоящий из 2" клеток (или, как говорят, прямоугольник с площадью 2") для некоторого й, определяет грань размерности й. Пусть булеза функция у задана таблицей, представленной в форме карты Карно. Описанный выше итерационный процесс склейки, в результате которого получается сокращенная ДНФ, представляющая функцию У, проводится на карте Карно так: любые две соседние клетки, содержащие единицы, обводятся, и „поглотивший" их прямоугольник (он и есть обозначение результата склейки на карте) представляется словом, содержащим „0", „1" и е х" (екрестик"), причем „крестик" занимает позицию того переменного, по которому произведена склейка (рис.
6.9). х11 11х 1х1 Рмс. 6.9 С геометрической точки зрения такой прямоугольник площади 2 соответствует ребру булеза куба, в каждой вершине которого функция принимает значение 1. Запись прямоугольника в виде слова можно понимать как обозначение соответствующе- 'Можно построить карты Карно н длл размерностей 5 н 6, но онн нспользуззтсл весьма редко.
Может быть построена н простеюпел карта Карно длл функции от двух переменных, но длл таких функций не возникает нетрнвнальных задач построеннл минимальной ДНФ. 416 б. БУЛЕВЫ ФУНКЦИИ го ребра. Так, на карте, показанной на рис. 6.9, прямоугольник 11х обозначает ребро [110, 111], прямоугольники же 1х1 и х11 — ребра [101, 111] и [011, 111] соответственно. По таким обозначениям легко получить и ту импликанту, которая является результатом простой склейки: для этого достаточно записать литерал я, (соответственно я;), если в 1-й позиции стоит 1 (соответственно 0), и пропустить литерал х;, если в 1-й позиции стоит „крестик". Так, по слову 1хО получим импликангу ж$яз. Наличие на карте Карно двух прямоугольников площади 2, находящихся в соседних столбцах или строках, показывает, что функция принимает значение 1 на некоторой паре соседних ребер, т.е.
на некоторой грани размерности 2. Тогда они могут быть объединены в один большой прямоугольник площади 4 (рис. 6.10). Рис. 6.10 Этот прямоугольник можно записать в виде слова хОх, показывая тем самым, что соответствующая грань (размерности 2) образована любой нз двух пар соседних ребер: ( х00, х 01) (два вертикальных прямоугольника площади 2) или (00х, 10х) (два горизонтальных прямоугольника площади 2). Точно так же можно объединять в один прямоугольник площади 8 два соседних прямоугольника площади 4 (рис. 6.11).
Если такие большие прямоугольники находить сразу, то „поглощаемые" ими меныпие прямоугольники уже не рассматриваются. Тем самым, находя на карте Карно прямоугольники максимальной площади и не содержащиеся друг в друге, мы 417 6.6. Построевве мвввмаеьвых ДНФ ОхОх х1 ххОО хххО хх10 Рис. 6.12 Рис. 6.11 находим грани максимальных размерностей и максимальные по включению, такие, на которых заданнал функция принимает единичное значение.
Поскольку грань размерности и имеет 2" вершин, то выделяемые описанным способом прямоугольники могут состоять только из 2" клеток (для некоторого и, не превышающего числа переменных). Так, на карте, приведенной на рис. 6.12, получим два прямоугольника площади 4: хОхО и ОхОх, соответствующие граням размерности 2, и один прямоугольник 01 х 1, отвечающий ребру, которое не содержится ни в одной из указанных вьппе граней. Подчеркнем еще раз, что соседство клеток, прямоугольников и само выделение прямоугольников на карте Карно производится с учетом ее „закрученности". В этой связи интересен „прямоугольник" на карте, приведенной на рис.
6.12, обозначенный хОхО. Он образован двумя парами противоположных угловых клеток. Таким образом, если на карте Карно сразу выделлть все максимальные (в указанном вьппе смысле) прямоугольники площади 2" (для некоторого й > 0 и не превьппающего числа переменных), то тем самым мы „геометрически" реализуем описанный ранее алгебраический итерационный процесс склейки и в результате получаем все простые импликанты исходной функции (составляющие сокращенную ДНФ).
Эти импликанты восстанавливаются по записям прямоугольников точно так 418 Е. БУЛЕВЫ ФУНКЦИИ же, как описано вьппе для простой склейки. Так, для карты, приведенной на рис. 6.12, получим сокращенную ДНФ в виде ХЗХ4 Ч Х1ХЗ Ч И1ХЗХ4. 2. Определение ядра.
Говорят, что элементарная коньюнкция К покрывает элементарную конъюнкцию Ь (и пишут К )- Ь), если любой литерал, входящий в К, входит в Ь. Так, Х1Х2 «.Х1Х2ХЗ, Х1ХЗ ~-Х1Х2ХЗ,НО Х1ХЗ 4 Х1Х2ХЗ,ПОСКОЛЬКУ ВГО- рал конъюнкция содержит литерал хз, отсутствующий в первой конъюнкции. Легко понять, что если К >- Ь, то К Ч Ь = К (согласно п1ождесп4вам аоглоп4енил). Каждая входящая в сокращенную ДНФ простая импликанта покрывает некоторую элементарную конъюнкцию исходной СДНФ.
На карте Карно этому отвечает прямоугольник, „закрывающий" соответствующую единицу. Простую импликанту называют лдровой, если она покрывает некоторую элементарную конъюнкцию исходной СДНФ, не покрываемую никакой другой простой импликантой. На карте Карно прямоугольник, соответствующий ядровой импликанте, отыскивается очень просто: это такой прямоугольник, удалив который получим единицу, не закрытую никаким другим прямоугольником.
Тогда ни одна ядровая импликанта не может быть удалена иэ искомой минимальной ДНФ исходной функции, т.е. все ядровые импликанты обязательно войдут в минимальную ДНФ. Множество всех ядровых импликант (склеек) сокращенной ДНФ называют ядром. Пример 6.13. а. У мажоритарной функции все импликанты являются ядровыми. Напротив, у функции, изображенной на карте Карно на рис. 6.13, ядро пусто, т.е.
ядровых импликант нет вовсе. б. На карте Карно на рис. 6.14 в ядро попадают склейки Ох х1, Ох1х, 1хОО. Если все простые импликанты оказались в ядре, то сокращенная ДНФ и есть единственная минимальная и кратчайшая 419 6.6. Поетроевве мвввмаеьвмх ДНФ Охх1 10 1х Ох1 01х х10 хО 1хО 10х х01 1х00 Рис. 6.14 Рис. 6.13 ДНФ для данной функции. Именно так обстоит дело с мажоритарной функцией (см. пример 6.12). В противном случае смотрят, не эквивалентна ли ДНФ, построенная как дизьюнкция всех ядровых импликант, исходной СДНФ. Это будет иметь место тогда и только тогда, когда ядровые импликанты покрывают в совокупности все элементарные конъюнкции исходной СДНФ. На карте Карно тогда каждая клетка, содержащая единицу, должна быть закрыта прямоугольником, отвечающим некоторой ядровой импликанте. Если это так, то ДНФ, построенная по ядру, как описано вьппе, есть минимальная и кратчайшая (склейки ядра закрыли все единицы карты Карно).
При этом импликанты, не попавшие в ядро, все оказываются „избыточными", т.е. их удаление из сокращенной ДНФ не приводит к нарушению эквивалентности этой последней с исходной СДНФ. В остальных случаях переходят к отысканию так называемых тупиковых ДНФ. 3. Перечисление тупиковых ДНФ. Простую импликанту называют избыепочиоб (относительно некоторой ДНФ, содержащей только простые импликанты и эквивалентной исходной СДНФ), если ее можно удалить из этой ДНФ без потери эквивалентности ее исходной СДНФ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
