Минимальные конъюнктивные нормальные формы
Как было отмечено, для получения минимальной формы функции нужно построить как МДНФ так и МКНФ.
Рассмотрим построение МКНФ.
В основном методы получения МКНФ аналогичны методам получения МДНФ и поэтому сформулируем лишь правила получения МКНФ:
- Представить ФАЛ в СКНФ. Если она задана таблицей, то произвести запись функции по нулям, как это было сформулировано ранее. Если дана СДНФ, то из нее легко получить СКНФ:
f(x1x2x3) = x1x2x3
x1x2x3 x1x2x3 x1x2x3 x1x2x3
= (x1
x2x3) (x1x2x3) (x1x2x3),
т.е. нужно функцию представить в виде конъюнкции недостающего числа дизъюктивных членов с соответсвенно расставлеными отрицаниями.
- При задании функции в произвольной конъюктивной форме, применяя
формулы развертывания:
x = (x
y)(xy) = xxxyyxyy (xy) = (xyz)(xyz)
. . . . . . . . . . . .,
получить СКНФ.
- Выполнить все операции неполного склеивания:
(x
y)(xy) = x(xy)(xy)
и поглощения: x(x
y) = x, получить сокращенную КНФ.
- Применить любой из методов минимизации: испытание членов, диаграммы Вейча, метод импликантных матриц.
Содержание Назад Вперед
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий