Конспект лекций по дискретной математике
=x1x2Ъx1x2x4Ъx1x2x3Ъx2x3x4=x1x2Ъx1x2x3Ъx2x3x4=x1(x2Ъx2x3)Ъx2x3x4=
_ _ _ _
=x1(x2Ъx3) Ъx2x3x4=x1x2Ъx1x3Ъx2x3x4 (КДНФ)
Замечания:
1) В общем случае любая Булева функция может иметь несколько КДНФ, отличающихся либо количеством термов, либо количеством букв в этих термах.
2) При построении комбинационной схемы, реализующей данную функцию по ее нормальной форме предпочтительней та, которая обладает наименьшим числом термов и наименьшим количеством букв в этих термах.
3) По сравнению со схемой, построенной по ДНФ, схема, построенная по скобочной форме (*), является более предпочтительной т.к. при одном и том же числе логических элементов (И, ИЛИ) содержат меньшее число входов (9 вместо 10).
Задача преобразования нормальной формы Булевой функции в скобочной форме называют задачей фактеризации.
4) Сущность конструктивного подхода при получении ДНФ состоит в следуюшем:
а) преобразование операций не-Булевого базиса к операциям Булевого базиса (см. последние строки таблицы)
б) снятие отрицаний над выражениями с применением законов двойственности
в) раскрытие скобок с применением дистрибутивного закона
г) упрощения выражения с применением закона поглощения
Приведение произвольных нормальных форм Булевой функции к каноническим
Для приведения произвольной ДНФ к КНФ необходимо использовать правило дизъюнктивного развертывания применительно к каждому из неполных конъюнктивных термов.
_ _
P=P(xiЪxi)=PxiЪPxi, где P-неполный конъюнктивный терм (ранг этого терма
меньше n), а xi - недостающий в терме аргумент.
Пример:
_ _ _ _ _ _ _ _ _ _
y=x1Ъx2x3(ДНФ)=x1(x2Ъx2)(x3Ъx3) Ъx2x3(x1Ъx1)=x1x2x3Ъ x1x2x3Ъ
_
_ _ _ _ _ _ _ _
Ъx1x2x3Ъx1x2x3Ъ x1x2x3Ъ x1x2x3 (КДНФ)
Замечание:
После раскрытия скобок могут получиться одинаковые термы, из которых нужно оставить только один.
y=
(0,1,2,3,5)=f3
Преобразование КНФ к ККНФ реализуется путем применения правила конъюнктивного развертывания к каждому неполному дизъюнктивному терму.
_ _
P=PЪxixi=(PЪxi)(PЪxi)
_ _ _ _ _ _ _ _ _ _
y=x1Ъx2x3(ДНФ)=(x1Ъx2)(x1Ъx3)(КНФ)=(x1Ъx2Ъx3x3)(x1Ъx3Ъx2x2)=
_
_ _ _ _ _ _ _
=(x1Ъx2Ъx3)(x1Ъx2Ъx3)(x1Ъx2Ъx3)(x1Ъx2Ъx3)(ККНФ)
y=
(4,6,7)
Минимизация булевых функций на картах Карно(см. Практику).
Метод Квайна-МакКласски базируется на кубическом представлении булевых функций.
Кубическое представление булевых функций.
В кубическом представлении булевой функции от n переменных все множество из 2n наборов ее аргументов рассматривается как множество координат вершин n-мерного куба с длинной ребра равной 1. В соответствии с этим наборы аргументов, на которых булева функция принимает значение равное 1 принято называть существенными вершинами.
Существенные вершины образуют так называемые ноль-кубы (0-кубы). Между 0-кубами существует отношение соседства и определена операция склеивания. Два 0-куба называются соседними если они отличаются только по одной координате.
Пример : n=4 0101
0001 - два соседних 0-куба
результат склеивания : 0x01 (*)
Склеивание 2-х соседних 0-кубов дает в результате 1-куб. Координата, отмечаемая символом х, называется свободной (независимой, несвязанной), а остальные (числовые) координаты называются зависимыми (связанными). Аналогичное отношение соседства существует между 1-кубами, в результате склеивания которых получается 2-куб.
0х01
0х11 - 0хх1 (**)
В продолжении аналогии два r-куба называются соседними если они отличаются только по одной (естественно зависимой) координате. r-куб содержит r независимых и n-r зависимых координат. В результате склеивания 2-х соседних r-кубов образуется (r+1)-куб содержащий r+1 независимую координату.
Операция склеивания над кубами соответствует применению закона склеивания к конъюнктивным термам, отождествляемым с этими кубами.
Пример : для склеивания (*)
_ _ _ _ _ _ _
х1х2х3х4Ъ х1х2х3х4= х1х3х4
(0101) (0001) (0х01)
_ _ _ _
для (**) х1х3х4Ъ х1х3х4= х1х4
(0х01) (0х11) (0хх1)
Определения.
Кубическим комплексом K0(f) булевой функции f называется множество 0-кубов этой функции. В общем случае кубическим комплексом Kr(f) булевой функции f называется объеденение множеств кубов всех размерностей этой функции
m
k(f)=UKr(f) m-максимальная размерность кубов функции f.
r=0
Пример получения кубических комплексов
f3(x)=V(1,2,3,6,7) |001 (1) |0x1 (1-3) (1)
(f=1) |010 (2) |01x (2-3) (2)
K0(f)=|011 (3) K1(f)=|x10 (2-4) (3) K2(f)=|x1x (2-5)
|110 (4) |x11 (3-5) (4)
|111 (5) |11x (4-5) (5)
K3(f)=пустому множеству
K(f)=K0(f)UK1(f)UK2(f)
Для получения кубического комплекса K(f) необходимо провести всевозможные операции склеивания над 0-кубами, 1-кубами и т.д. до тех пор пока на очередном шаге не получится Kr+1(f)=пустому множеству. При склеивании 1-кубов 2-кубы представлены в 2-х экземплярах как результаты склеивания 2-х различных пар 1-кубов.
Распространяя этот принцип можно утверждать, что r-кубы как результат склеивания (r-1)-кубов получаются в r-кратном количестве экземпляров.
Куб, входящий в состав кубического комплекса K(f) называется максимальным, если он не вступает ни в одну операцию склеивания.
В приведенном примере максимальными кубами являются х1х и 0х17.
Геометрическая интерпретация кубов малой размерности. Графическое представление булевых функций.
Подобный подход носит ограниченный характер и как правило является наглядным для булевых функций от 2-х и 3-х переменных.
F3(x)=V(1,2,3,6,7)
(f=1)

Геометрическим местом 0-куба является точка, представляющая существенную вершину.
Два соседних 0-куба являются концами какого-либо ребра.
Геометрическим местом 1-куба является ребро, замыкаемое склеивающимися 0-кубами, образующими данный 1-куб.
Два параллельных ребра, образующих грань, являются образами склеивающихся 1-кубов. В соответствии с этим геометрической интерпретацией 2-куба является грань, образуемая парой параллельных ребер. Так как любую грань можно определить одной из пар параллельных ребер, 2-куб может быть получен как результат склеивания двух различных пар 1-кубов, то есть представляется в двух экземплярах.
Геометрическим образом 3-куба можно считать 3-х мерный куб. Так как он может быть образован 3-мя способами как пара параллельных граней, то при склеивании он получается в трех экземплярах.
Покрытия булевых функций.
Между кубами различной размерности, входящих в кубический комплекс K(f), существует отношение включения или покрытия. Принято говорить, что куб А меньшей размерности покрывается кубом Б большей размерности, если куб А включается в куб Б. Это означает, что при образовании куба Б хотя бы в одном склеивании учавствует куб А.
Отношение включения (покрытия) между кубами принято обозначать АМБ. В теории множеств отношение включения связывает между собой некоторое множество и его подмножества.
Для рассмотренного примера отношения включения имеют место между 001М0х1; 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). Этому покрытию соответствует КДНФ.
Для примера покрытием является также
|0x1
|01x
c1(f)=K1(f)=|x10
|x11
|11x
этому покрытию соответствует ДНФ вида
_ _ _ _ _ _ _ _ _ _
f=x1x3vx1x2vx2x3vx2x3vx1x2 приведенная ДНФ не является минимальной.
В качестве минимальной еще одного покрытия можно использовать множество максимальных кубов
|0x1
c2(f)=|x1x
Действительно, куб 0х1 покрывает существенные вершины 0х1Й(001, 011), а куб x1xЙ(010, 011, 110, 111).
Множество максимальных кубов булевой функции всегда является ее покрытием.
Покрытие c2(f) соответствует ДНФ вида х1х3vx2. Эта ДНФ является минимальной. Покрытие булевой функции, которое соответствует минимальной ДНФ называется минимальным покрытием.
Минимальное покрытие должно состоять только из максимальных кубов.
В частном случае все множество максимальных кубов является минимальным покрытием. Это справедливо для нашего примера. В общем случае множество максимальных кубов является избыточным и для получения минимального покрытия достаточно взять некоторое его подмножество.
Пример : f3(x)=V(0,1,4,6,7)
(f=1)
|000 (1) |00x (1-2)
|001 (2) |x00 (1-3)
K0(f)=|100 (3) K1(f)=|1x0 (3-4)
|110 (4) |11x (4-5)
|111 (5)
Для данного примера множество максимальных кубов совпадает с комплексом K1(f). Z(f)=K1(f)
Минимальными покрытиями являются
|00x |00x
с1(f)=|11x c2(f)=|11x
|x00 |1x0
Из анализа покрытия существенных вершин максимальными кубами из комплекса K1(f) следует :
Куб 00х должен обязательно включаться в покрытие, так как только он покрывает существенную вершину 001, аналогично 11х покрывает 111.
Множество максимальных кубов без которых не может быть образовано покрытие булевой функции называется ядром покрытия T(f)=|00x
|11x
Так как ядром покрытия кроме существенных вершин 001 и 111 покрываются также существенные вершины 000 и 110, то не покрытой ядром остается только существенная вершина 100. Для ее покрытия достаточно взять 1 из оставшихся максимальных кубов (х00 или 1х0).
Выводы :
Задача получения минимальной ДНФ сводится к задаче получения минимального покрытия.
Получение минимального покрытия реализуется в таком порядке : а) Находится множество максимальных кубов б) Выделяется ядро покрытия в) Из максимальных кубов, не вошедших в ядро, выбирается такое минимальное подмножество, которое покрывает существенные вершины, не покрытые ядром.
Цена покрытия.
Цена r-куба представляет собой количество несвязанных координат. Sr=n*r
Для оценки качества покрытия используют два вида цены покрытия :
m
Sa=еSrNr, где Nr - количество r-кубов, входящих в по-
r=0
крытие, m - максимальная размерность куба. Цена Sa представляет собой сумму цен кубов, входящих в покрытие.
Sb=Sa+k, где k - количество кубов, входящих в покрытие
m m
Sa =е(n-r) Nr ; Sb=е(n-r)(Nr+1)
r=0 r=0
Под минимальным покрытием понимают покрытие, обладающее минимальной ценой Sa по сравнению с любым другим покрытием этой функции.
Можно показать, что покрытие, обладающее минимальной ценой Sa обладает также и минимальной ценой Sb.
Пример : f3(x)=V(0,1,4,6,7)
(f=1)
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 представляет собой количество букв, входящих в ДНФ, которая соответствует данному покрытию.
Цена Sb представляет для ДНФ сумму количества букв и количества термов.

Цена покрытия хорошо согласуется с ценой схемы по Квайну, которая строится по нормальной форме, соответствующей этому покрытию.
Для приведенной схемы цена по Квайну SQ=9=Sb (9-число входов).
В принципе, между SQ и ценами Sa и Sb существует соотношение Sa Ј SQ Ј Sb Это неравенство имеет место при следующих допущениях по комбинационной схеме :
Схема строится по нормальной форме (ДНФ или КНФ).
Схема строится на элементах булевого базиса (И, ИЛИ).
На входы схемы можно подавать как прямые, так и инверсные значения входных переменных, представляющие собой значения аргументов булевой функции (схема с парафазными входами). Элементы НЕ (инвертора в схеме отсутствуют.
Нулевое покрытие булевой функции и получение минимальной КНФ.
Выше было рассмотрено покрытие булевой функции на наборах аргументов для которых функция равна единице.
Такие покрытия можно назвать единичными. Наряду с единичными покрытиями существуют и нулевые, для которых покрываются наборы аргументов, на которых функция равна нулю, то есть покрытие реализуется для существенных вершин, но не самой функции, а ее отрицания (инверсии).
Нулевое покрытие строится также как и единичное, но только для отрицания исходной функции.
f3(x)=V(0,1,4,6,7) f3(x)=&(2,3,5)
(f=1) (f=0) _ |010
K0( f )=|011
_ _ |101
C0( f )= K0( f ) Sa=9 Sb=12
_ _ _
K1( f )=|01x Z( f )=Cmin( f )=|01x Sa=5 Sb=7