Минимальные конъюнктивные нормальные формы

Как было отмечено, для получения минимальной формы функции нужно построить как МДНФ так и МКНФ.

Рассмотрим построение МКНФ.

В основном методы получения МКНФ аналогичны методам получения МДНФ и поэтому сформулируем лишь правила получения МКНФ:

1. Представить ФАЛ в СКНФ. Если она задана таблицей, то произвести запись функции по нулям, как это было сформулировано ранее. Если дана СДНФ, то из нее легко получить СКНФ:

   f(x1x2x3) = x1x2x3

   
   x1x2x3
   
   x1x2x3
   
   x1x2x3
   
   x1x2x3

   = (x1

   
   x2
   
   x3) (x1
   
   x2
   
   x3) (x1
   
   x2
   
   x3),

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

2. При задании функции в произвольной конъюктивной форме, применяя

   формулы развертывания:

   x = (x

   
   y)(x
   
   y) = xx
   
   xy
   
   yx
   
   yy (x
   
   y) = (x
   
   y
   
   z)(x
   
   y
   
   z)

   . . . . . . . . . . . .,

   получить СКНФ.

3. Выполнить все операции неполного склеивания:

   (x

   
   y)(x
   
   y) = x(x
   
   y)(x
   
   y)

   и поглощения: x(x

   
   y) = x, получить сокращенную КНФ.

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

     По возможности отбросить одновременно несколько членов, поступить как и при минимизации функции ДНФ.

   • При использовании диаграмм Вейча ищутся правильные конфигурации, образованные нулями.
   • При применении метода импликантных матриц поступают как и в случае ДНФ, только колонкам присваивают имена конституент "0" функции, записанной в СКНФ, а горизонтальным рядам – простых импликант. Далее ищут оптимальное покрытие.