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

Обозначим через множество всех наборов из 0 и 1. Его можно рассматривать как множество всех вершин единичного -мерного куба, который в дальнейшем будем называть просто -мерным кубом, а наборы – вершинами куба. На рис. 1. представлена проекция 3-мерного куба на плоскость.

° 111

011 ° ° 101 °110

001° ° 010 ° 100

° 000

Рис. 1

Пусть – фиксированная система чисел из 0 и 1 такая, что . Множество всех вершин куба таких, что

,

называется -мерной гранью, то есть имеем подмножество :

.

Очевидно, что -мерная грань является -мерным подкубом куба .

Число -мерных граней куба равно .

Число называют рангом грани и обозначают . Таким образом, сумма размерности и ранга грани равна . Размерности граней куба (ранги) могут изменяться в пределах от 0 до . Нульмерные грани () – это вершины куба ; одномерные грани называют ребрами; грань размерности – это сам куб .

Куб и совокупность его граней образуют топологический объект, называемый кубическим комплексом. Относительно этого достаточно сложного объекта многие вопросы остаются нерешенными до настоящего времени. Например, неизвестно каково минимальное множество вершин, обладающим тем свойством, что в этом множестве есть по крайней мере один представитель от каждой -мерной грани (задача Лупанова о «протыкании» граней).

Сопоставим каждой функции алгебры логики подмножество вершин , в которых эта функция равна 1:

.

При этом булевым операциям над функциями будут соответствовать теоретико-множественные операции над подмножествами . Следующая таблица устанавливает соответствие между аналитическими и геометрическими объектами.

Таблица 1. Соответствие аналитических и геометрических объектов

Аналитический объект	Геометрический объект
Двоичные слова длины	Вершины -мерного куба
Булева функция	Подмножество вершин
Элементарная конъюнкция	-грань куба
Формулы	Соотношения
Д. н. ф.	Объединение граней
Представление функции д. н. ф.	Покрытие гранями

Из таблицы следует, что каждому представлению булевой функции в виде ДНФ соответствует покрытие подмножества вершин гранями. Например, двум ДНФ и функции из рассмотренного выше примера соответствуют покрытия множества , представленные на рис. 2.

Рис. 2

Первое покрытие состоит из четырех точек (нульмерных граней) и ребра (одномерной грани), второе – из трех ребер (одномерных граней).

Пусть . Число будем называть рангом покрытия. Для любого покрытия множества гранями, очевидно, что число переменных в соответствующей этому покрытию д. н. ф. будет равно сумме рангов граней, то есть рангу покрытия. Следовательно, МДНФ отвечает покрытие с наименьшим рангом.

Сформулируем геометрическую задачу о покрытии, эквивалентную задаче о минимизации булевой функции.

Дано подмножество вершин единичного -мерного куба. Найти покрытие этого подмножества содержащимися в нем гранями с наименьшим рангом.

Переход от аналитического к геометрическому языку в ряде случаев помогает быстро найти МДНФ. Например, для функции из рассмотренного выше примера гранями, содержащимися в , являются одномерные (покрывают две вершины) и нульмерные (покрывают одну вершину) грани. Множество состоит из 6 вершин, поэтому его покрытие включает не менее трех граней. Следовательно, ДНФ – минимальная.