Diskretnaya_matematika_1_semestr

Сокращенные днф.

Грань Nk называется максимальной для ф-ции f, если не существует грани Nk большей размерности, целяком лежащее в Nf. Nk⊂Nk’⊆Nf

Если такая грань Nk’существует, то Nk’называется расширением грани Nk.

Элементарная &, которая соответствует максимальным граням, называется простыми импликантами.

Любую грань можно расширить до максимальной грани.

Если решается задача минимализации по числу элементарных &, то расширение граней, входящих в минимальное покрытие не изменяет общее число граней, то есть индекс просто Lk. Если решается задача минимализации по числу букв, то тогда можно каждую грань расширить до максимальной, это может сменьщить суммарный ранг. Если число букв уменьшается, то общее покрытие не было минимальным.

ДНФ, состоящее только из простых импликант, называется сокращнной.

Алгоритм построения сокращенных ДНФ.

1)Находим произвольную КНФ, реализующую ф-ю f(можно взять СКНФ)

2)Перемножаем элементы дизъюнкции и переходим от КНФ к ДНФ

3)упрощаем полученное выражение, используя следующие отношения:

x·x=x

xVx=x

x·x=0

xVx=1

xVxy=x

Содержание