Алгоритм получения тупиковой д. н. ф.

1. По функции строят какую-либо д. н. ф. (с уверенностью можно говорить о построении хотя бы СДНФ). В д. н.

2. Просматривают слева направо д. н. ф. каждую элементарную конъюнкцию на предмет упрощения:

а) возможность удаления элементарных конъюнкций;

б) возможность удаления множителя.

3. Возврат в п.2а, проводя то же (не просматривая множители).

Например, для функции .

. Получили тупиковую д. н. ф. при данном порядке следования конъюнкций и букв.

Теорема (без доказательства). Пусть и – какая-либо ее тупиковая д. н. ф. Тогда существует такое упорядочение слагаемых СДНФ, что при помощи данного алгоритма получается .

Рассмотрим также геометрическую интерпретацию построения д. н. ф. на единичном кубе.