Обвивки на булеви функции
Конспект на лекции по дискретна математика
Геометричният образ на 3-куб може да се счита за 3-измерен куб. Тъй като може да се оформи по 3 начина като двойка успоредни лица, при залепване се получава в три екземпляра.
Булева функция обхваща.
Между кубове с различни размери, включени в кубичния комплекс K(f), съществува връзка на включване или покритие. Прието е да се казва, че куб A с по-ниско измерение се покрива от куб B с по-високо измерение, ако куб A е включен в куб B. Това означава, че куб A участва в поне едно залепване, когато се формира куб B.
Съотношението на включване (покритие) между кубчетата обикновено се означава като AÌB. В теорията на множествата връзката на включване свързва определено множество и неговите подмножества.
За разглеждания пример отношенията на включване се осъществяват между 001Ì0x1; 011Мx11Мx1x . всяко 1-кубче покрива 2 0-кубчета, 2-кубче покрива 4 0-кубчета и 2 1-кубчета, 3-кубче покрива 8 0-кубчета, 12 1-кубчета и 6 2-кубчета.
Покритие на булева функция f е подмножество от кубове от кубичния комплекс K(f), което покрива всички основни върхове на функцията.
Поради факта, че всеки куб от комплекса K(f) може да бъде свързан с конюнктивен член, за всяко покритие може да се представи някаква ДНФ на булева функция.
Частен случай на покритие на булева функция е кубичният комплекс K0(f), покритието c0(f)=K0(f). Това покритие отговаря на KDNF.
Например, покритието също е
това покритие съответства на DNF на формата
_ _ _ _ _ _ _ _ _ _
f=x1x3vx1x2vx2x3vx2x3vx1x2 намалената DNF не е минимална.
Наборът от максимални кубчета може да се използва като минимално още едно покритие
Наистина, кубът 0x1покрива основните върхове 0x1É(001, 011) и куба x1xÉ(010, 011, 110, 111).
Множеството от максимални кубове на булева функция винаги е нейното покритие.
Покритието c2(f) съответства на DNF от формата x1x3vx2. Този DNF е минимален. Покритието на булевата функция, което съответства на минималната DNF, се нарича минимално покритие.
Минималното покритие трябва да се състои само от максимални кубчета.
В конкретен случай цялото множество от максимални кубове е минимално покритие. Това е вярно за нашия пример. В общия случай множеството от максимални кубове е излишно и за да се получи минимално покритие е достатъчно да се вземат някои от неговите подмножества.
K0(f)=100 (3) K1(f)=1x0 (3-4)
За този пример множеството от максимални кубове съвпада с комплекса K1(f). Z(f)=K1(f)
Минималните покрития са
От анализа на покритието на съществени върхове с максимални кубове от комплекса K1(f) следва, че:
1) Куб 00x задължително трябва да бъде включен в покритието, тъй като само той покрива основния връх 001, по същия начин 11x покрива 111.
Наборът от максимални кубове, без които не може да се формира покритието на булевата функция, се нарича ядро на покритието T(f)=00x
2) Тъй като в допълнение към основните върхове 001 и 111, съществените върхове 000 и 110 също са покрити от ядрото на покритието, само основният връх 100 остава непокрит от ядрото.За да го покриете, е достатъчно да вземете 1 от останалите максимални кубове (x00 или 1x0).
Проблемът за получаване на минимална DNF се свежда до проблема за получаване на минимално покритие.
Получаването на минималното покритие се осъществява в следния ред: a) Намира се набор от максимални кубове b) Избира се ядрото на покритието c) От максималните кубове, които не са включени в ядрото,избира се такова минимално подмножество, което покрива основните върхове, които не са обхванати от ядрото.
Цената на r-куб е броят на несвързаните координати. Sr=n*r
За да се оцени качеството на покритието, се използват два вида цени на покритие:
1) Sa=åSrNr, където Nr е броят на r-кубовете, включени в
покритие, m - максималният размер на куба. Цената Sa е сумата от цените на кубовете, включени в покритието.
2) Sb=Sa+k, където k е броят на кубовете, включени в покритието
Sa =å(n-r) Nr; Sb=å(n-r)(Nr+1)
Минималното покритие е покритието, което има минималната цена Sa в сравнение с всяко друго покритие на тази функция.
Може да се покаже, че покритие, което има минимална цена Sa също има минимална цена Sb.
C0(f)=K0(f) ; Sa=5*3=15; Sb=Sa+5=20
C1(f)=K1(f) ; Sa=4*2=8; Sb=Sa+4=12
Cmin(f): Sa=3*2=6; Sb=9
Цена на покритие Sa е броят букви, включени в DNF, който съответства на това покритие.
Цената Sb представлява за DNF сумата от броя на буквите и броя на термините.
Цената на покритието е в добро съответствие с цената на схемата Quine, която е изградена според нормалната форма, съответстваща на това покритие.
За горната схема цената на Quine е SQ=9=Sb (9 е броят на входовете).
По принцип съществува връзка Sa £ SQ £ Sb между SQ и цените Sa и Sb. Това неравенство е валидно при следните комбинирани допускания:
1) Веригата е изградена според нормалната форма (DNF или CNF).
2) Веригата е изградена върху елементите на булевата база (И, ИЛИ).
3) Както директните, така и обратните стойности на входните променливи, които са стойностите на аргументите на булевата функция, могат да бъдат приложени към входовете на веригата (верига с двуфазни входове). Елементи НЕ(във веригата няма инвертори.
Нулево покритие на булевата функция и получаване на минималната CNF.
По-горе разгледахме покритието на булева функция върху набори от аргументи, за които функцията е равна на единица.
Такива покрития могат да се нарекат единични. Наред с единичните покрития има и нулеви, за които се покриват наборите от аргументи, по които функцията е равна на нула, тоест покритието се реализира за съществени върхове, но не за самата функция, а за нейното отрицание (инверсия).
Нулевият капак е конструиран по същия начин като капака на модула, но само за да отрича оригиналната функция.
C0( f )= K0( f ) Sa=9 Sb=12
K1(f)=01x Z(f)=Cmin(f)=01x Sa=5 Sb=7
Цената на минималното нулево покритие се оказа по-малка от цената на минималното единично покритие.
Тъй като е невъзможно да се предвиди предварително кое от минималните покрития на дадена функция, единица или нула, ще има по-ниска цена, препоръчително е да се реши проблемът с минимизирането и за двете покрития, за да се изгради схема, която има минимална цена според Куайн.