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

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

( при )

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

Выражение

( при ),

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

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

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

.

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

.

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

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

,

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

,

,

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

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

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

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

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

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

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

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

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

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

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

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