Алгоритм перехода от сокращенной ДНФ к тупиковой

Для перехода от сокращенной ДНФ к тупиковой надо уметь проверять условие . (4)

Не ограничивая общности, можно считать, что имеет непустое пересечение с Действительно, если пусто, то от такого интервала не зависит, выполнено ли условие (4). Если т.е. , то интервалы должны быть предварительно исключены из (4). Так как , то общие для и переменные входят в них в одинаковых степенях. Удалим из всех переменные, общие с . Например, если , то удалим из переменную . Оставшиеся в сомножители образуют конъюнкцию С. Если все сомножители входят в , то полагаем

ТЕОРЕМА (критерий поглощения)

Доказательство. Следовательно, существует набор значений переменных такой, что

Если

Переменные из не входят в . Рассмотрим набор, составленный из Обозначим такой объединенный набор через

Тогда . Противоречие.

Но тогда

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

Пример. Рассмотрим булеву функцию, заданную в виде сокр. ДНФ (см. предыдущий пример), Проверяем конъюнкцию . Так как то необходимо проверить условие в ДНФ следует поставить . Аналогичный результат дает проверка . Для испытания остается две конъюнкции . Мы имеем . Удалив , придем к тупиковой ДНФ Проведя испытания в другом порядке, можно получить и другую тупиковую ДНФ