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

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

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

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

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

f(x1x2x3) = x1x2x3
x1x2x3
x1x2x3
x1x2x3
x1x2x3

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

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

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

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

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

получить СКНФ.
Выполнить все операции неполного склеивания:

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

и поглощения: x(x
y) = x, получить сокращенную КНФ.
Применить любой из методов минимизации: испытание членов, диаграммы Вейча, метод импликантных матриц.
- При выполнении метода испытания членов необходимо каждый конъюктивный член приравнять нулю. Найти значения аргументов, которые обращают его в нуль, удалить его из выражения функции и найти значение функции при найденных значениях аргументов. Если функция обратится в нуль, то конъюктивный член является лишним.
  
  По возможности отбросить одновременно несколько членов, поступить как и при минимизации функции ДНФ.
- При использовании диаграмм Вейча ищутся правильные конфигурации, образованные нулями.
- При применении метода импликантных матриц поступают как и в случае ДНФ, только колонкам присваивают имена конституент "0" функции, записанной в СКНФ, а горизонтальным рядам – простых импликант. Далее ищут оптимальное покрытие.

Содержание раздела