 |
Приведение произвольных нормальных форм Булевой функции к каноническим
|
|
|
|
Для приведения произвольной ДНФ к КНФ необходимо использовать правило дизъюнктивного развертывания применительно к каждому из неполных конъюнктивных термов.
_ _
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-мя способами как пара параллельных граней, то при склеивании он получается в трех экземплярах.
|
|
|
