XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 67
Текст из файла (страница 67)
Так, сокращенная ДНФ 420 б. БУДЕВН ФУНКЦИИ (см. рис. 6.14) содержит избыточные импликанты: импликанта, соответствующая прямоугольнику 10 х О, или импликанта, соответствующая прямоугольнику х 010, может быть удалена (но не обе сразу!). Это значит, что каждая из этих импликант является избыточной относительно сокращенной ДНФ, но удаление одной из них приводит к новой ДНФ, относительно которой вторая из упомянутых импликант уже не будет избыточной. В том случае, когда каждую элементарную конъюнкцию исходной СДНФ покрывает некоторая ядровая импликанта, импликанты, не вошедшие в ядро, можно удалить одновременно. Тогда можно представить процесс пошагового удаления избыточных импликант, начиная с сокращенной ДНФ, в результате которого получится некоторая ДНФ, уже не содержащая ни одной избыточной склейки.
Любую ДНФ, эквивалентную исходной СДНФ, содержащую все ядровые импликанты и не содержащую ни одной избыточной импликанты, называют пзуззпкое о41. Заметим, что в силу конечности множества всех импликант тупиковая ДНФ обязательно существует, т.е. в упомянутом вьппе процессе мы рано или поздно доберемся до такого момента, когда удаление хотя бы одной склейки приведет к тому, что „откроется" какая-то единичная клетка на карте Карно и тем самым будет потеряна эквивалентность полученной таким образом ДНФ исходной СДНФ. Для СДНФ, карта Карно которой приведена на рис.
6.14, имеются две тупиковые ДНФ: х1х4 Ч х1хз Ч Х1хз ° х4 Ч хгхзх4, х1х4 Ч х1хз Ч х1хз ' х4 Ч х1хз ' х4. Первые три конъюнкции соответствуют ядру. В общем случае для перечисления всех тупиковых ДНФ может быть использован следующий алгоритм. Мы изложим его в терминах карт Карно и, допуская вольность речи, будем отождествлять максимальные прямоугольники на карте Карно с соответствующими простыми импликантами. б.б. Построение минимальных ДНФ 421 Кг = хгхз(х01), Кз = хдхз (Ох1), Кз = хгхз ( х 10) > Кб = хд хз (1 х О) > Кд — -хдхг(10х), К4 = хдхг (01х), получим (Кд Ч Кз) Л (Кд Ч Кг) Л (Кг Ч Кз) Л Л (Кз Ч К4) Л(К4 ЧКз) Л(Кз ЧКз).
(6.13) Тем самым мы образуем вспомогательную функцию (представленную КНФ вида (6.13)), называемую фунндзиеб Папзрина. Раскрывая скобки в КНФ (6.13) и используя тождества булевой алгебры (в частности, тождество поглощения), получим ДНФ, в которой каждая элементарная конъюнкция соответствует некоторой тупиковой ДНФ и, наоборот, каждой тупиковой ДНФ может быть сопоставлена одна из этих коньюнкций.
Для нашего примера поступим так: вычислим конъюнкцию первой и второй скобки в выражении (6.13), а также третьей и четвертой, пятой и шестой скобок, после чего получим Кд 4КЗКг '4КЗКд ЧК4К2)Л Л (К2Кз Ч К2К4 Ч КЗ Ч КЗК4)Л Л (К4Кз Ч К4Кз Ч Кз Ч КзКз). (6.14) Присвоим каждой простой импликанте сокращенной ДНФ некоторое имя: т.е. обозначим их, например, как Кд, Кг, ..., К . Для любой единицы карты Карно, не покрываемой ядром, перечислим все простые импликанты, которые ее покрывают, записав их в виде элементпарноб дизъюнкции, в которой переменными считаются введенные вьппе имена простых импликант. Переменное, именующее данную простую импликанту, принимает, по определению, значение 1, если данная простая импликанта выбирается для покрытия рассматриваемой единицы карты Карно.
Записав все элементарные диэъюнкции, составим из них КНФ. Рассмотрим карту Карно на рис. 6.13. Обозначив 422 б. ВУЛЕВЫ ФУНКЦИИ Используя тождества поглощения, в первой скобке в формуле (6.14) мы можем удалить все члены, содержащие К1, во второй скобке — все члены, содержащие Кз, в третьей скобке — все члены, содержащие Кз. Проделав зто, раскрыв все три скобки и применив еще раэ поглощение, окончательно получим КЛзКз ч К1КзК4Кб '4 Ч К1Кз К4Кз Ч КгКзКзКб Ч КзК4Кб. (6.15) Элементарные конъюнкции в (6.15) определяют тупиковые ДНФ.
Более того, так как в данном случае отсутствуют ядровые импликанты, найденные конъюнкции исчерпывают тупиковые ДНФ. Первая тупиковая ДНФ состоит из конъюнкций К1, Кз и Кз, т.е. имеет вид х1хз Ч х1хз Чхгхз. Точно так же определяются остальные тупиковые ДНФ. Обоснование описанного выше алгоритма может быть получено иэ следующих соображений. Функция Патрика, представленная КНФ, принимает значение 1 тогда и только тогда, когда каждая элементарная дизъюнкция принимает значение 1. А элементарная дизъюнкция принимает значение 1 в том и только в том случае, когда хотя бы одно ее переменное принимает значение 1.
Согласно определению функции Патрика, это значит, что хотя бы одна простая импликанта выбрана для покрытия соответствующей единицы на карте Карно. Поскольку таким образом перебираютсл все не покрываемые ядром единицы карты Карно, то гарантируется эквивалентность искомой ДНФ исходной СДНФ. Однако, когда функция Патрика представле. на ДНФ и мы выбираем в точности одну из ее элементарных конъюнкций, полагая, что все входящие в нее переменные равны 1, мы тем самым из всех возможных вариантов покрытия каждой единицы на карте Карно выбираем в точности один вариант. Значит, полученная в результате такого выбора ДНФ 423 б.б.
Построение минимальных ДНФ для исходной (минимизируемой) СДНФ действительно будет тупиковой. Но нужно заметить, что перечисление тупиковых ДНФ является самым неприятным и трудоемким этапом всего алгоритма минимизации. Если число единичных клеток карты Карно, не покрываемых ядром, достаточно велико, то функция Патрика будет весьма сложной и ее упрощение сопоставимо по трудоемкости со всем процессом минимизации. 4. Отыскание среди тупиковых ДНФ кратчайших и минимальных.
Среди найденных тупиковых ДНФ находят кратчайшие и минимальные. Можно легко показать, что минимальная ДНФ всегда является кратчайшей, но обратное неверно. Так, х1хз Ч хз = х1 Ч хз и первая ДНФ кратчайшая, но не минимальная. Действительно, легко сообразить, что вторая из записанных ДНФ минимальна. Следовательно, представляемую ею функцию нельзя представить ДНФ, содержащей менее двух элементарных конъюнкций. Но в первой ДНФ три литерала, а во второй — два. Из пяти тупиковых ДНФ, соответствующих функции Патрика (6.15), кратчайшими являются две.
Каждая из них минимальна, так как обе они имеют одинаковое число литералов. Пример 6.14. Рассмотрим карту Карно на рис. 6.15. 00хх хОхО (К,) ОхОх 111х (К,) 1х10 (Ке) хООх (К~) хх01 (Кз) 11х1 (Ке) Рис. 0.15 424 б. БУЛЕВЫ ФУНКЦИИ В результате проведения склейки получим следующую сокращенную ДНФ'. Х1ХЗ Ч Х1Х2 Ч Х2Х4 Ч Х2ХЗ Ч ХЗХ4 Ч Х1Х2Х4 Ч Х1Х2ХЗ Ч Х1ХЗХ4.
Ядро составляют склейки (простые импликанты) х1хз и Х1хг. Шесть клеток, содержащих единицу, на карте Карно остаются непокрытыми ядровыми склейками. Для неядровых склеек (обозначенных К1, ..., КБ) составляем функцию Патрика в виде (кз ч к4) (к4 ч к5Нкз ч кбПк1 ч к2Нк2 ч кз Нк1 ч кб) Преобразуя ее аналогично функции (6.13), получаем К1кзк5 Ч К2К4кб Ч К2кзк5КБ Ч К1К2К4К5 Ч К1кзк4КБ. Имеем, следовательно, пять тупиковых ДНФ. Запишем их, для наглядности, так: хгх4 Ч хзх4 Ч х1х2хз) ХЗХЗ Ч Х1ХЗХ4 Ч Х1ХЗХ11 х1ХЗ Ч Х1хг Ч х2хз Чхзх4 Ч х1х2хз Ч х1хзх4) ядро Х2Х4 Ч Х2хз Ч х1х2х4 Ч хгх2хз хгх4 Ч хзх4 Ч х1хгх4 Ч Х1хзх4.
Иэ этих пяти тупиковых ДНФ кратчайшими являются первол и вторая. Из них, в свою очередь, минималыюй является первая, так как она содержит на один литерал меньше. В итоге получаем минимальную ДНФ в виде х1хз Ч Х1хг Ч хгх4 Ч хзх4 Ч х1хгхз. 'Обратим еще раз внимание на то, что каждый выделяемый прямоугольник на карте Карно имеет площадь, равную некоторой степени двойки. Поэтому, например, три соседние единичные клетки не могут быть обьединены в один прямоугольник, а ик „накроют" два прямоугольника площадью 2, пересекающиеся по одной клетке.
425 б.б. Построение минимаеьнасх ДНФ Б данном случае минимальная ДНФ оказалась единственной, хотя, как это мы видели в ранее разобранных примерах, в общем случае могут существовать несколько минимальных ДНФ Ф Техника карт Карно является удобным и наглядным (при определенных ограничениях на число переменных минимизируемой функции) способом реализации алгоритма Квайна— Мак-Клоски.
Но существуют и другие способы проведения склейки, т.е. получения сокращенной ДНФ для исходной функции. Одним из таких способов является чисто алгебраический метод Блейка, состоящий в том, что к любой ДНФ, представляющей функцию, применяются следующие тождества: хК~ Ч хКз = хК1 Ч хКз Ч К1Кз, (6.16) К1 Ч К1Ке = К1. Первое из тождеств (6.16) называют тождеством (или правилом) обоби4енного снлеиванил, второе — тождеством (или правилом) поглощения. „Технология" использования метода Блейка такова: применяют тождество обобщенного склеивания до тех пор, пока не перестанут появляться новые элементарные конъюнкции (вида К1Кз).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
