Логические и арифметические основы и принципы работы ЭВМ

       

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


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

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

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

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



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