Предыдущая страница реферата | 2  3  4  5  6  7  8  9  10  11  12 | Следующая страница реферата

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)

[pic]

Геометрическим местом 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 приведенная ДНФ не является минимальной.

Рекомендуем скачать другие рефераты по теме: реферат на тему менеджмент, класс.



Предыдущая страница реферата | 2  3  4  5  6  7  8  9  10  11  12 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки