Элементарной конъюнкцией \(n\) переменных называется конъюнкция переменных или их отрицание.
Элементарная конъюнкция \(n\) переменных может быть записана в виде:
$$x^{\delta ^{1}}_{1} \wedge x^{\delta ^{2}}_{2} \wedge ... \wedge x^{\delta ^{n}}_{n},$$
где \(x_{k}^{\delta _{k}}=\)\(\begin{cases} x_{k}, \text{ если } \delta _{k}=1, \\ \bar{x_{k}}, \text{ если} \delta _{k}= 0. \end{cases}\)
Дизъюнктивной нормальной формой (ДНФ) формулы А называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций.
Для любой формулы алгебры логики путем равносильных преобразований можно получить ее ДНФ, причем не единственную.
Например, для формулы \(A \equiv x \wedge ( x \rightarrow y)\) имеем:
\(A \equiv x \wedge ( \bar{x} \vee y ) \equiv ( x \wedge \bar{x}) \vee ( x \wedge y) \equiv x \wedge y\), то есть
ДНФ \(A \equiv ( x \wedge \bar{x}) \vee ( x \wedge y),\)
ДНФ \(A \equiv x \wedge y .\)
Среди многочисленных ДНФ \(A\) существует единственная ДНФ \(A\), для которой выполняются четыре свойства совершенства (свойства (С)).
Такая ДНФ \(A\) называется совершенной дизьюнктивной нормальной формой формулы \(A\) (СДНФ \(A\)).
Как уже указывалось, СДНФ \(A\) может быть получена с помощью таблицы истинности.
Другой способ получения СДНФ формулы \(A\) основан на равносильных преобразованиях формулы и состоит в следующем:
1. Путем равносильных преобразований формулы \(A\) получают одну из ДНФ \(A\).
2. Если в полученной ДНФ \(A\) входящая в нее элементарная конъюнкция \(В\) не содержит переменную \(x_{i }\), то, используя равносильность \(B \wedge ( x_{i} \vee \bar{x_{i}}) \equiv B\), элементарную конъюнкцию \(B\) заменяют на две элементарных конъюнкций \(( B \wedge x_{i} )\) и \(( B \wedge \bar {x_{i}} )\), каждая из которых содержит переменную \(x_{i}\).
3. Если в ДНФ \(A\) входят две одинаковых элементарных конъюнкций \(В\), то лишнюю можно отбросить, пользуясь равносильностью \(B \vee B \equiv B.\)
4. если некоторая элементарная конъюнкция \(В\), входящая в ДНФ \(А\), содержит переменную \(x_{i}\) и ее отрицание \(\bar{x_{i}}\), то \(B \equiv 0\), и \(B\) можно исключить из ДНФ \(А\), как нулевой член дизъюнкции.
5. Если некоторая элементарная конъюнкция, входящая в ДНФ \(А\), содержит переменную \(x_{i}\) дважды, то одну переменную можно отбросить, пользуясь равносильностью \(x_{i} \wedge x_{i} \equiv x_{i}\).
Ясно, что после выполнения описанной процедуры будет получена СДНФ \(A\).
Например, для формулы \(A \equiv x \vee y \wedge ( x \vee \bar{y} )\) ДНФ \(A \equiv x \vee x \wedge y \vee y \wedge \bar{y} .\)
Так как элементарная конъюнкция \( В \equiv x\), входящая в ДНФ \(A\), не содержит переменной \(у\), то, пользуясь равносильностью \(B \equiv B \wedge ( y \vee \bar{y} ) \equiv x \wedge ( y \vee \bar{y} ) \equiv x \wedge y \vee x \wedge \bar{y},\) заменим ее на две элементарных конъюнкции \(x \wedge y\) и \(x \wedge \bar{y }\). В результате получим ДНФ \(A \equiv x \wedge y \vee x \wedge \bar{y} \vee x \wedge y \vee y \wedge \bar{y} .\)
Так как элементарная конъюнкция \(y \wedge \bar{y}\) содержит переменную \(y\) и ее отрицание \(\bar{ y }\), то \(y \wedge \bar{ y } \equiv 0\), ее можно отбросить как нулевой член дизъюнкции.
Таким образом, получаем:
$$СДНФ A \equiv x \wedge y \vee x \wedge \bar{y}.$$
