Тупиковая ДНФ

Выбрасывание ЭК из ДНФ, в том числе и из сокращенной, можно осуществлять по следующему правилу.

Пусть оно остается покрытием, т.е. Тогда , т.е. конъюнкция может быть удалена из ДНФ. В противном случае т.е. нельзя удалить из ДНФ.

Если же после применения этого приема несколько раз получится ДНФ, из которой нельзя удалить ни одной ЭК, то получится ДНФ, называемая тупиковой. Соответствующее покрытие интервалами называется неприводимым. Ясно, что мин. ДНФ тупиковая. Рассмотрим ДНФ .

Здесь Удаляем

Для имеем поэтому удаляем Получим тупиковую ДНФ .

Ей соответствует покрытие (рис. 8.2).

Если бы мы выбрали другую последовательность удаления ЭК из ДНФ, то могли бы получить другую тупиковую ДНФ Мы имеем

Соответствующее этой ДНФ неприводимое покрытие иллюстрируется рис. 8.3.