Нормальные формы являются синтаксически однозначным способом записи формулы, реализующей заданную функцию.
Если х — логическая переменная, а σ∈{0,1} то выражение
| Xσ = { | x если σ=1 |
| ¬x если σ=0 |
или
| Xσ = { | 1 если x=σ |
| 0 если x≠σ |
называется литерой. Литеры x и ¬x называются контрарными. Конъюнктом называется конъюнкция литер. Дизъюнктом называется дизъюнкция литер. Например, формулы XY¬Z и XYX¬X являются конъюнктами, формулы XvYv¬Z и XvYv¬X — дизъюнктами, а формула ¬Z является одновременно и конъюнктом и дизъюнктом.
Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция конечного числа конъюнктов.
Конъюнктивной нормальной формой (КНФ) называется конъюнкция конечного числа дизъюнктов.
Более просто: ДНФ — это сумма произведений, а КНФ — это произведение логических сумм.
Примеры.
1. XYvYZvX — это ДНФ (сумма произведений).
2. (Xv¬Yv¬Z)(XvY)Z — это КНФ (произведение сумм).
3. ¬XvYvZv¬W — это ДНФ и КНФ (одновременно).
4. ¬XY¬ZW — это ДНФ и КНФ (одновременно).
5. (XvXvY)(YvZvX)Z — это КНФ.
6. XY¬Z и XYX¬X — это ДНФ.
7. X(XvYZ)¬(X¬YZ) — это не нормальная форма (не ДНФ и не КНФ).
Пусть функция f записана в базисе S1. Данная функция приводится к нормальной форме следующим путем:
1) используем законы де Моргана, чтобы преобразовать формулу к виду, в котором знаки отрицания относятся только к отдельным переменным;
2) применяем правило снятия двойного отрицания: ¬(¬X)=X
3) далее использовать законы дистрибутивности, причем необходимо использовать первый закон дистрибутивности для приведения к ДНФ
H1&(H2vH3)=(H1&H2)v(H1&H3),
и второй закон дистрибутивности для приведения к КНФ.
H1v(H2&H3)=(H1vH2)&(H1vH3).
Любая булева функция может иметь бесконечно много представлений в виде ДНФ и КНФ. Например, используя дополнительно законы инверсий и правила операций с константами можно добиться, чтобы в каждом отдельном конъюнкте или дизъюнкте любая переменная входила бы не более одного раза (либо сама, либо ее отрицание).
Пример: Для приведения к ДНФ используем 1-ый акон дистрибутивности.
X¬Y¬(XY¬vZ) = X¬Y(¬Xv¬Yv¬(¬Z))(YvZ) =
— это КНФ
=(0vX¬YvX¬YZ)(YvZ)=(X¬YvX¬YZ)(YvZ)=
— это другая КНФ
=X¬YYvX¬YZYvX¬YZvX¬YZZ = 0v0vX¬YZvX¬YZ = X¬YZvX¬YZ
— это ДНФ
Пример: Для приведения к КНФ необходимо использовать второй закон дистрибутивности.
XvY¬(XYv¬Z) = XvY(¬(XY)¬(¬Z)) = XvY(¬Xv¬Y)Z = XvYZ(¬Xv¬Y) = (XvYZ)(Xv¬Xv¬Y) =
=(XvY)(XvZ)(1v¬Y) = (XvY)(XvZ) — это КНФ