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

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

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

Пример 2.8. Для функции f ⁴(X) определить, являются ли ее 0-кубы (0101) и (0001) соседними и, если являются, то выполнить операцию их склеивания.

Заданные кубы являются соседними, так как они различаются только по одной координате. Результатом их склеивания является 1-куб (0Х01).

Координата, отмечаемая символом Х, называется свободной (независимой, несвязанной), а остальные (числовые), координаты называются зависимыми (связанными).

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

Пример 2.9.Для функции f ⁴(X) определить, являются ли ее 1-кубы (0Х01) и (0Х11) соседними и, если являются, то выполнить операцию их склеивания.

Заданные кубы являются соседними, так как они различаются только по одной координате. Результатом их склеивания является 2-куб (0ХХ1).

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

Замечания.

1. Размерность куба определяется количеством свободных координат.

2. В соседних r-кубах (r > 0) все свободные координаты являются одноименными.

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

Так, для примера 2.8 0-кубу (0101) соответствует терм , а 0-кубу (0001) – терм . Эти термы склеиваются по переменной х₂. Результат склеивания: в котором отсутствует переменная х₂, отождествляется с 1-кубом (0Х01).

Аналогично, для примера 2.9 1-кубу (0Х01) соответствует терм , а 1-кубу (0Х01) – терм . Эти термы склеиваются по переменной х₃. Результат склеивания: , отождествляется с 2-кубом (0ХХ1).

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

Пример 2.10. Получить кубический комплекс функции

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

K(f)=K⁰(f) U K¹(f) U K²(f). Естественно, что в комплексе K²(f) останется только один куб (Х1Х).

Пояснения. Получение 1-кубов осуществляется на основе попарного сравнения 0-кубов с целью выявления всевозможных пар соседних 0-кубов и образования 1-кубов из каждой пары. Для сокращения числа попарных сравнений можно учесть следующий факт: соседними могут являться только такие два 0-куба, в которых число единичных координат отличается ровно на единицу. В связи с этим целесообразно разделить 0-кубы на группы, различающиеся числом единичных координат, и проводить попарные сравнения только для 0-кубов, принадлежащих соседним группам.

Замечания.

1. Для данного примера в записи 0-кубов в кубическом комплексе K⁰(f) в порядке возрастания их десятичных эквивалентов уже присутствует их упорядочеие и разделение на группы.

2. При полном попарном сравнении пяти 0-кубов потребовалось бы выполнить 4!=24 операции сравнения, а при целенаправленном (сравниваются только кубы из двух соседних групп) – число операций сравнения равно шести.

3. Подобный принцип рационального сравнения кубов можно распространить и на кубы большей размерности. При этом добавляется еще одно условие: два r-куба могут быть соседними, если все r их независимых координат являются одноименными.

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

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

Множество максимальных кубов функции f обозначается Z(f). Это множество является окончательным результатом операции склеивания кубов. Из кубов этого множества (и только из них) строится минимальное покрытие булевой функции.

В примере 2.10 максимальными кубами являются кубы