Приведение к дизъюнктивной нормальной форме

Ранее определено, что всякая функция алгебры логики, отличная от 0, может быть представлена совершенной дизъюнктивной нормальной формой

Однако СДНФ обычно допускает упрощения, в результате которых получается формула, также реализующая , но содержащая меньшее число символов (термов).

Рассмотрим методы представления функций алгебры логики простейшими формулами в классе так называемых дизъюнктивных нормальных форм (ДНФ).

Введем ряд определений. Назовем выражение

элементарной конъюнкцией.

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

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

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

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

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

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