СКНФ строится по таблице истинности, но если таблица задана формулой, ее СКНФ можно получить, преобразуя формулу, без построения таблицы истинности.
Построение СКНФ осуществляется в два этапа. Сначала строится КНФ, затем КНФ превращается в СКНФ.
Чтобы превратить формулу в КНФ, нужно выполнить следующие действия.
1. Преобразовать формулу так, чтобы в ней остались только операции причем отрицания должны стоять только над отдельными аргументами.
2. Воспользоваться законом дистрибутивности и превратить формулу в КНФ.
3. Упростить получившуюся КНФ.
4. Преобразовать КНФ в СКНФ.
Все ПЭД нужно превратить в полные ПЭД, для чего поступить так. Если в ПЭД не входит, например, переменная y, нужно прибавить логически к этой ПЭД выражение и воспользоваться законом дистрибутивности . Повторить операцию столько раз, сколько нужно, чтобы все ПЭД стали полными. Если появятся одинаковые ППЭД, нужно убрать повторения, так как .
Пример. Построим СКНФ формулы из параграфа 2.3. СКНФ этой формулы такова: , так как функция равна 0 на двух наборах — (0,0,0) и (0,1,1).
Преобразуем формулу. Как уже было показано
.
Тогда
.