МИНИМАЛЬНЫЕ ДНФ

Представление б.ф. виде СДНФ в общем случае оказывается не компактнее, чем представление в виде табличного задания, поскольку для каждого набора значений переменных, на котором б.ф. f(x₁, . . . , x_n) равна 1, в СДНФ включается элементарная конъюнкция ранга n. То есть если f принимает значение 1 на значительной части всех наборов, то СДНФ этой функции по размерам сравнима с табличным заданием f.

ОПРЕДЕЛЕНИЕ

Дизъюнктивной нормальной формой (ДНФ) называется всякая формула вида D = K₁ . . . K_r , где K₁, . . . , K_r - это произвольные элементарные конъюнкции.

Дата добавления: 2014-11-15; просмотров: 209; Нарушение авторских прав

Мы поможем в написании ваших работ!