Метод нахождения тупиковых ДНФ

Для изложения метода нахождения тупиковых ДНФ нам потребуется одно свойство ДНФ монотонных функций.

Утверждение 6.3. Минимальная ДНФ монотонной функции совпадает с её сокращённой ДНФ.

Доказательство. Сначала покажем, что все простые импликанты монотонной функции не содержат переменных с отрицаниями. Действительно, в противном случае наряду с простой импликантой функция имела бы импликанту (в силу её монотонности). Склеивая эти две импликанты, получаем противоречие с простотой импликанты .

Покажем теперь, что все простые импликанты входят в минимальную ДНФ. Пусть — простая импликанта. Тогда на наборе импликанта принимает значение 1. Все остальные импликанты должны быть равны на этом наборе нулю, так как в них обязательно должны входить переменные из множества . Следовательно, импликанта должна входить в минимальную ДНФ, поскольку иначе функция f на этом наборе будет равна 0. Утверждение доказано.

Дата добавления: 2014-12-29