2.2.2. Минимизация нормальных форм

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

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

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

Каждый из рассмотренных ниже методов состоит из двух этапов:

· построение сокращенной ДНФ;

· построение матрицы покрытий. Построение МДНФ.

Определение. Если для всякого набора а = (а1, а2, …, an) значений переменных условие g(a) = 1 влечет f(a) = 1, то функция g называется частью функции f (или функция f накрывает функцию g). Если при этом для некоторого набора с = (с1, с2, …, сn)функция g(c)=1, то говорят, что функция g накрывает единицу функции f на наборе с (или что g накрывает конституенту единицы функции f).

Конституента единицы функции f есть часть функции f, накрывающая единственную единицу функции f.

Определение. Элементарная конъюнкция К называется импликантом функции f, если для всякого набора а = (а1, а2, …, an) из 0 и 1 условие К(а)=1 влечет f(a)=1.

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

Всякий импликант функции f есть часть функции f.

Теорема. Всякая функция реализуется дизъюнкцией всех своих простых импликант.

Определение. Сокращенная ДНФ функции f есть дизъюнкция всех простых импликант функции f.

Утверждение. Всякая функция f реализуется своей сокращенной ДНФ. Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ.

Теорема (Куайна). Если в СДНФ функции f провести все операции неполного склеивания, а затем все операции поглощения и удаления дублирующих членов, то в результате получится сокращенная ДНФ функции f.