Минимизация нормальных форм
Выше было сказано, что произвольная булева функция может быть представлена формулой в дизъюнктивной и конъюнктивной нормальной форме. Равносильными преобразованиями можно получить формулу, содержащую меньшее, чем исходная, число переменных.
Определение. Минимальной ДНФ (МДНФ) функции 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.
предыдущаяследующая