Совершенная конъюнктивная нормальная форма (СКНФ)

Формула вида , называется элементарной дизъюнкцией.

Всякая конъюнкция элементарных дизъюнкций называется, конъюнктивной нормальной формой

Элементарная дизъюнкция, называется правильной, если в нее каждая переменная входит не более одного раза (включая ее вхождение под знаком отрицания).

Правильная элементарная дизъюнкция, называется полной относительно переменных х₁…х_n, если в нее входит каждая их этих переменных причем только один раз (может быть и пол знаком отрицания).

Совершенной конъюнктивной нормальной формой относительно переменных х₁…х_n, называется КНФ, в которой нет одинаковых элементарных дизъюнкций и все элементарные дизъюнкции правильны и полны относительно переменных х₁…х_n.

Теорема 3: всякую функцию f можно представить в СКНФ

, (4)

где символ означает, что конъюнкция берется по тем наборам, которые находятся под ним.

3.2.1 Алгоритм преобразования формулы в СКНФ