LK / Лекция 24

Баранов Виктор Павлович. Дискретная математика. Раздел 5. ДНФ и схемы из ФЭ.

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

Лекция 24. ПРОБЛЕМА МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ.

ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ

План лекции:

1. Понятие дизъюнктивной нормальной формы (ДНФ). Проблема минимизации

булевых функций.

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

1. Понятие ДНФ. Проблема минимизации булевых функций

Пусть задан алфавит переменных . Выражение

( при )

называется элементарной конъюнкцией, а число – ее рангом. По определению считаем константу 1 элементарной конъюнкцией ранга 0.

Выражение

( при ),

где – элементарная конъюнкция ранга , называется дизъюнктивной нормальной формой (ДНФ.).

Число различных элементарных конъюнкций над алфавитом равно .

Действительно, число конъюнкций ранга равно . Отсюда

.

Для каждой булевой функции существует ДНФ такая, что

.

Говорят, что функция представлена в виде ДНФ или ДНФ реализует функцию . Однако, представление функции в виде д. н. ф. не единственно. Число булевых функций от переменных равно , а число ДНФ – . Например, функция

может быть представлена совершенной ДНФ

,

а также следующими д. н. ф.

,

,

которые можно получить из совершенной, применяя булевы тождества.

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

Приведем примеры индексов простоты для ДНФ.

1. – число букв переменных, встречающихся в записи ДНФ .

Для предыдущего примера , , то есть в смысле этого индекса ДНФ проще, чем ДНФ .

2. – число элементарных конъюнкций, входящих в .

Для ДНФ и , , то есть в смысле этого индекса ДНФ проще, чем ДНФ .

3. – число символов, встречающихся в записи ДНФ .

Для ДНФ и , , то есть в смысле этого индекса ДНФ опять проще, чем ДНФ .

ДНФ, реализующая функцию и имеющая минимальный индекс , называется минимальной относительно (МДНФ относительно ).

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

Задача минимизации булевых функций состоит в построении минимальной ДНФ для произвольной функции алгебры логики .

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

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

 111

011   101 110

001  010  100

 000

Рис. 1

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

,

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

.

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

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

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

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

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

.

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

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

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

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

Рис. 2

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

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

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

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

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

4