В этом разделе мы интересуемся представлением произвольной булевой функции посредством формул специального вида, использующих только операции 
, 
и .
Пусть 
- это множество пропозициональных переменных. Введем для каждого i=1,...,n обозначения: 
и 
. Формула 
, в которой 
и все переменные разные, т.е. 
при 
, называется элементарной конъюнкцией (элементарной дизъюнкцией).
Определение 4.2. Формула 
называется дизъюнктивной нормальной формой (ДНФ), если она является дизъюнкцией элементарных конъюнкций, т.е. имеет вид 
где каждая формула 
- это элементарная конъюнкция. называется совершенной ДНФ, если в каждую из ее конъюнкций 
входят все 
переменных из 
Аналогично, формула 
называется конъюнктивной нормальной формой (КНФ), если она является конъюнкцией элементарных дизъюнкций, т.е. 
, где каждая формула Dj (j=1,...,r) - это элементарная дизъюнкция. Она является совершенной КНФ, если в каждую Dj входят все n переменных из
