1 - Булевы функции. Булевы алгебры. Булевы функции. ДНФ и КНФ. Критерий Поста. Минимизация ДНФ (1059972), страница 6
Текст из файла (страница 6)
Такое произведение можноТаблица 1.5изобразить таблицей, в которой каждая строка соответствует вер00 01 11 10шине куба Bk , а каждый столбец — вершине куба Bl . Существенным00моментом является такой порядок строк и соответственно столбцов,01при котором соседним строкам и столбцам отвечают соседние вершины соответствующего булева куба. А именно, при k, l = 1, берем11естественный порядок 0, 1. при k, l = 2 используем порядок 00, 01,1011, 10 (табл. 1.5).В такой таблице соседние клетки соответствуют соседним вершинам четырехмерного булевакуба. Если представить, что эта шахматная доска“ склеена по горизонтали и вертикали, т.е.”соседними, например, являются (00, 11) и (10, 11), а также (01, 00) и (01, 10), то соседние надоске будет в точности соответствовать соседним на кубе.На карте Карно ребро — это пара соседних (в том числе и через край“) клеток.
Легко”изобразить на карте Карно и двумерные грани, состоящие из 4-х вершин. это либо квадратиз двух примыкающих пар клеток, либо одна строка, либо один столбец. Трехмерная грань —это две соседние строки или два соседних столбца.К сожалению, при увеличении размерности такаяТаблица 1.6простая интерпретация исчезает. Например, для пятимерного куба (табл. 1.6), соседние клетки (включая000 001 011 010 110 111 101 100соседство через край“) будут соответствовать со00”седним вершинам. Но, кроме того, и другие пары01клеток, например (01, 001) и (01, 101), не будучи со11седними в таблице, соответствуют соседним верши10нам.
Причина в том, что на карте Карно у каждойклетки четыре соседних, в то время как в n-мерномкубе каждая вершина имеет n соседних вершин, которые получаются, если в булевом вектореизменить одну компоненту из n возможных.Рассмотрим два приема, с помощью которых из имеющейся ДНФ можно получить болеепростую ДНФ (и в смысле длины, и в смысле сложности).ÌÃÒÓÔÍ-12ÌÃÒÓ14ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. БУЛЕВЫ ФУНКЦИИÌÃÒÓ11*00Рис. 1.5Другой метод построения сокращенной ДНФ — методБлейка, в котором в качестве исходной можно взять любуюДНФ. В этом методе на первом этапе многократно выполняется операция обобщенного склеивания, при которой суммаÌÃÒÓ1ÔÍ-12ÔÍ-1210ÌÃÒÓПример 1.6.
Рассмотрим функцию, заданную картой Карно на рис. 1.5. Первый этапсклейки по методу Квайна приведет к ребрам 1∗00, 10∗0, ∗010, а также четырем ребрам двумерной грани 0∗∗1 и четырем ребрам двумерной грани 0∗1∗.0**1*010Всеисходные импликанты будут удалены как избыточные.x3 x400011110На втором этапе мы получим две двумерные грани 0∗∗1x1x20*1*и 0∗1∗. При этом будут удалены 6 ребер, входящих в эти11100грани. Поскольку склеить две эти грани нельзя, процесс вы11101явления простых импликант на этом завершится. Сокращенная ДНФ будет содержать пять импликант, соответствую11110*0щих граням 0∗∗1, 0∗1∗, 1∗00, 10∗0, ∗010. #ÔÍ-12Построение сокращенной ДНФ. Один из методов построения сокращенной ДНФ — этометод Квайна — МакКлоски.
Его суть в следующем. В качестве исходной выбираетсясовершенная ДНФ. На первом этапе проводится склейка импликант совершенной ДНФ в ребра,которые добавляются в ДНФ. После того как проведены все склейки вершин, из ДНФ удаляютсявсе избыточные вершины, т.е. те, которые подчиняются добавленным ребрам. На втором этапепроводится склейка всех ребер в четырехмерные грани, которые добавляются к ДНФ. Послепроведения всех склеек между ребрами удаляются ребра, подчиненные двумерным граням. Натретьем этапе выполняется склейка двумерных граней и удаление избыточных двумерных граней.
Процесс останавливается, когда между гранями соответствующей размерности не удаетсяпровести ни одной склейки. Результатом этих преобразований и будет сокращенная ДНФ.ÔÍ-12ÌÃÒÓÔÍ-12Избыточные импликанты. В сокращенной ДНФ одна из импликант может накрыватьсяостальными. Такую импликанту можно удалить из формулы, уменьшая и длину, и сложность ДНФ. Рассмотрим, например, функцию, представлен0*1ную картой Карно на рис. 1.4. У этой функции максимальx2 x300 01 11 10x1ными являются шесть импликант 1∗0, 10∗, ∗01, 0∗1, 01∗,01*∗10. Их сумма даст сокращенную ДНФ.
Но из рисунка видно,1110*10что, например, импликанта 10∗ накрывается двумя импли1111кантами 1∗0 и ∗01. Значит, эту импликанту можно из ДНФ1*0удалить.10**01Импликанта в ДНФ, подчиненная сумме остальных имРис. 1.4пликант этой ДНФ, называется избыточной. Если из сокращенной ДНФ удалить избыточные импликанты, то получим тупиковую ДНФ. По определению, тупиковая ДНФ — это ДНФ, состоящая из простых импликант, ни одна из которыхв этой ДНФ не является избыточной. Например, на рис. 1.4 тупиковую ДНФ образуют импликанты 1∗0, ∗01, 01∗.Основной целью каждого метода минимизации ДНФ является выявление всех тупиковыхДНФ.
Именно среди них находится минимальная и кратчайшая формы.ÌÃÒÓÌÃÒÓуровне единицы функции. Этим граням соответствуют максимальные импликанты функции(максимальные относительно введенного порядка 6 на импликантах функции). Такие импликанты называются простыми импликантами. ДНФ данной функции, в которую входятвсе простые импликанты, называют сокращенной ДНФ.Отметим, что если исходная ДНФ не является совершенной, то склейка может и не привестик сокращенной ДНФ. Так, если на рис. 1.3 выбрать грани ∗0∗0, 01∗1, 0001, 0100, получимпокрытие уровня единицы функции.
В соответствующей ДНФ x2 x4 +x1 x2 x4 +x1 x2 x3 x4 +x1 x2 x3 x4нельзя склеить какие-либо грани, но эта ДНФ не является сокращенной, так как два последнихслагаемых не являются простыми импликантами.ÌÃÒÓÔÍ-12ÌÃÒÓ15ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. БУЛЕВЫ ФУНКЦИИÌÃÒÓK2 = 0∗1∗,K3 = 1∗00,K4 = 10∗0,K5 = ∗010.P = K1 (K1 + K2 )(K2 + K5 )K1 (K1 + K2 )K2 K3 (K3 + K4 )(K4 + K5 ).Используя дистрибутивность и идемпотентность, приходим к ДНФ:P = K1 K2 K3 (K4 + K5 ) = K1 K2 K3 K4 + K1 K2 K3 K5 .Таким образом, рассматриваемая функция имеет две сокращенные ДНФ, описываемые двумясписками склеек K1 , K2 , K3 , K4 и K1 , K2 , K3 , K5 .
В результате получимD2 = x1 x4 + x1 x3 + x1 x3 x4 + x2 x3 x4 .Видно, что у обоих сокращенных ДНФ есть общая часть — первые три конъюнкции. Этоядро, входящее в каждую сокращенную ДНФ. Его можно исключить из рассмотрения, рассматривая условия накрытия только для тех вершин, которые не накрываются склейками ядра. Вданном случае это единственная вершина 1010. При этом функция Патрика будет иметь видÔÍ-12D1 = x1 x4 + x1 x3 + x1 x3 x4 + x1 x2 x4 ,ÌÃÒÓУпростив согласно идемпотентности операций и тождествам поглощения (x(x + y) = x), получимP = K1 K2 K3 (K4 + K5 ).ÔÍ-12Тогда функция Патрика для 9 вершин уровня 1 при их нумерации по строкам будет иметьследующий вид:ÌÃÒÓÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓПример 1.7.
У функции, представленной на рис. 1.5 диаграммой Карно, имеется пятьпростых импликант. Введем обозначения:ÌÃÒÓВыявление всех тупиковых ДНФ. Создать список всех тупиковых ДНФ можно, используя следующий прием. Обозначим все простые импликанты символами K1 , K2 , . . . , Km . Перенумеруем все вершины уровня единицы функции. Пусть первая вершина накрывается склейками Ki1 , Ki2 , . . .
, Kip . Тогда элементарная дизъюнкция Ki1 + Ki2 + . . . + Kip задает условие,что первая вершина уровня единицы функции накрывается одной из простых импликант. Составив конъюнкцию из указанных элементарных дизъюнкций по всем вершинам уровня единицы функции, мы получим КНФ, представляющее собой логическое условие того, что весьуровень единицы функции накрыт простыми импликантами. Эта КНФ называют функциейПатрика. Преобразуем КНФ в ДНФ, пользуясь свойствами булевых операций (дистрибутивностью, коммутативностью, идемпотентностью).
В ДНФ каждая элементарная конъюнкциябудет описывать набор простых импликант, целиком покрывающих уровень единицы функции, т.е. набор, описывающий конкретную тупиковую ДНФ рассматриваемой функции. Можнопоказать, что таким образом можно выявить все тупиковые ДНФ.Среди простых импликант рассматриваемой функции есть те, которые входят в любую тупиковую ДНФ. К таким относится любая импликанта, для которой среди накрываемых вершинесть хотя бы одна, не накрываемая никакой другой импликантой. Например, на рис.
1.5 вершина 1100 накрывается единственной простой импликантой 1∗00. Эта импликанта должнавходить в любую тупиковую ДНФ. Импликанты, удовлетворяющие описанному условию, называются ядровыми импликантами. Совокупность ядровых импликант — ядро — постоянная часть всех тупиковых ДНФ. Например, на рис. 1.5 ядро составляют импликанты 0∗∗1,0∗1∗, 1∗00, а импликанты ∗010 и 10∗0 неядровые. При выявлении тупиковых ДНФ ядровыеимпликанты и накрываемые ими вершины из функции Патрика можно исключить.ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ16ÌÃÒÓÌÃÒÓÔÍ-12xK1 + xK2 заменяется суммой xK1 + xK2 + K1 K2 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
