Тупиковые ДНФ

Пусть булева функция задана совершенной ДНФ:
fx1x2x3x4=x1x2x3x4⋁x1x2x3x4⋁x1x2x3x4⋁x1x2x3x4⋁
⋁x1x2x3x4⋁x1x2x3x4⋁x1x2x3x4⋁x1x2x3x4.
Постанавливая значения переменных на различных наборах, можно убедится, что следующая дизъюнкция простых импликант покрывает все единицы заданной булевой функции.
fx1,x2,x3,x4=x2x4⋁x1x2x3⋁x1x3x4⋁x1x2x3⋁x1x3x4. (*)
Если в этой дизъюнкции мы удалим импликанту x2x4, то дизъюнкция оставшихся импликант снова будет покрывать все единицы функции f. Однако, удаление любой другой импликанты из выражения (*) приведет к получению дизъюнкции, которая не будет покрывать все единицы функции f.
Дизъюнкцию совокупности простых импликант функции fx1,x2,…,xn и такую, что удаление из нее любой импликанты приводит к тому, что дизъюнкция оставшихся импликант не покрывает все единицы функции, называют тупиковой ДНФ функции f

.
Важность понятия тупиковой ДНФ определяется следующим утверждением.
Теорема 2. Любая минимальная ДНФ булевой функции fx1,x2,…,xn является тупиковой ДНФ.
Предположим, что это не так.
Во-первых, предположим, что минимальная ДНФ есть дизъюнкция некоторых элементарных конъюнкций, которые не являются простыми импликантами функции fx1,x2,…,xn. Если данное предположение верно, то каждая такая элементарная конъюнкция имеет собственную часть, которая является простой импликантой функции fx1,x2,…,xn. Заменив в минимальной ДНФ каждую конъюнкцию простой импликантой, мы уменьшим ранг каждого члена этой ДНФ и, следовательно, уменьшим суммарный ранг минимальной ДНФ