Любая булева функция, кроме константы 0, представима совершенной дизъюнктивной нормальной формой, единственной для данной функции.
Алгоритм построения СовДНФ (по таблице истинности) вытекает из определения СовДНФ и состоит в циклическом выполнении следующих шагов:
Шаг 1: в векторе – столбце значений функции выбирается очередная единица. Если единицы исчерпаны, то идем на конец.
Шаг 2: по набору значений аргументов выбранной строки формируется конъюнкция всех аргументов с соблюдением следующего правила: если i – я компонента набора 0, то i – я переменная входит в конъюнкцию в степени 0 (с инверсией), иначе – в степени 1 (без инверсии). Полученная конъюнкция добавляется в формулу как очередное слагаемое. Идем на шаг 1.
Конец.
Пример.
Соединив полученные конъюнкции знаками дизъюнкции, получим:
14) Получение СовКНФ из разложения функции по переменным. Утверждение о существовании и единственности СовКНФ. Алгоритм построения СовКНФ по таблицк истинности.
Пусть дана функция f(x1, x2, ... , xn). Представим ее инверсию СовДНФ:
Инвертируем обе части этого равенства:
По законам двойного отрицания и де Моргана имеем:
[заметив, что 
, так как при c = 0 `x = x, а при c = 1`x =`x , получим ]
Определение.Совершенная дизъюнктивная нормальная форма функции
f(x1, x2, ... , xn), или СовКНФ, — это формула вида:
Сформулируем утверждение с очевидностью вытекающее из СовКНФ.
