Реферат: Конспект лекций по дискретной математике

Операция склеивания над кубами соответствует применению закона склеивания к конъюнктивным термам, отождествляемым с этими кубами.

_ _ _ _ _ _ _

х₁ х₂ х₃ х₄ Ú х₁ х₂ х₃ х₄ = х₁ х₃ х₄

(0101) (0001) (0х01)

_ _ _ _

для (**) х₁ х₃ х₄ Ú х₁ х₃ х₄ = х₁ х₄

(0х01) (0х11) (0хх1)

Определения .

Кубическим комплексом K⁰ (f) булевой функции f называется множество 0-кубов этой функции. В общем случае кубическим комплексом K^r (f) булевой функции f называется объеденение множеств кубов всех размерностей этой функции

m

k(f)=UK^r (f) m-максимальная размерность кубов функции f.

r=0

Пример получения кубических комплексов

f³ (x)=V(1,2,3,6,7) |001 (1) |0x1 (1-3) (1)

(f=1) |010 (2) |01x (2-3) (2)

K⁰ (f)=|011 (3) K¹ (f)=|x10 (2-4) (3) K² (f)=|x1x (2-5)

|110 (4) |x11 (3-5) (4)

|111 (5) |11x (4-5) (5)

K³ (f)=пустому множеству

K(f)=K⁰ (f)UK¹ (f)UK² (f)

Для получения кубического комплекса K(f) необходимо провести всевозможные операции склеивания над 0-кубами, 1-кубами и т.д. до тех пор пока на очередном шаге не получится K^r+1 (f)=пустому множеству. При склеивании 1-кубов 2-кубы представлены в 2-х экземплярах как результаты склеивания 2-х различных пар 1-кубов.

Распространяя этот принцип можно утверждать, что r-кубы как результат склеивания (r-1)-кубов получаются в r-кратном количестве экземпляров.

Куб, входящий в состав кубического комплекса K(f) называется максимальным, если он не вступает ни в одну операцию склеивания.

В приведенном примере максимальными кубами являются х1х и 0х17.

Геометрическая интерпретация кубов малой размерности . Графическое представление булевых функций .

Подобный подход носит ограниченный характер и как правило является наглядным для булевых функций от 2-х и 3-х переменных.

F³ (x)=V(1,2,3,6,7)

(f=1)

Геометрическим местом 0-куба является точка, представляющая существенную вершину.

Два соседних 0-куба являются концами какого-либо ребра.