Нормальные формы являются синтаксически однозначным способом записи формулы, реализующей заданную функцию.

Если х — логическая переменная, а σ∈{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) — это КНФ