Кубическое представление булевых функций

В кубическом представлении булевой функции от n переменных все множество из 2ⁿ наборов ее аргументов рассматривается как множество координат вершин n-мерного куба с длиной ребра равной 1. В соответствии с этим наборы аргументов, на которых булева функция принимает значение равное 1 принято называть существенными вершинами.

Существенные вершины образуют так называемые ноль-кубы (0-кубы). Между 0-кубами существует отношение соседства и определена операция склеивания. Два 0-куба называются соседними, если они отличаются только по одной координате.

Пример: n=4 0101 - два соседних 0-куба

0001

результат склеивания: 0Х01 (*)

Склеивание 2-х соседних 0-кубов дает в результате 1-куб. Координата, отмечаемая символом Х, называется свободной (независимой, несвязанной), а остальные (числовые), координаты называются зависимыми (связанными). Аналогичное отношение соседства существует между 1-кубами, в результате склеивания которых получается 2-куб.

0Х01 - два соседних 1-куба

0Х11

0ХХ1 (**)

В продолжение аналогии: два r-куба называются соседними, если они отличаются только по одной (естественно зависимой) координате. r-куб содержит r независимых и n-r зависимых координат. В результате склеивания 2-х соседних r-кубов образуется (r+1)-куб содержащий r+1 независимую координату.

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

Пример : для склеивания (*)

0101 0001 0Х01

для склеивания (**)

0Х101 0Х01 0ХХ1

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

Пример получения кубического комплекса:

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Х1.