18c0693f

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


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

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

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

  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" функции, записанной в СКНФ, а горизонтальным рядам – простых импликант. Далее ищут оптимальное покрытие.





Все публикации раздела