2.2.1 Основные определения.
— конечный алфавит из переменных.
Рассмотрим слово:
Экспоненциальные обозначения: 
— элемент конъюнкции.
S – длина элемента конъюнкции.
ДНФ – дизъюнкция нескольких различных элементарных конъюнкций.
Любая булева функция может быть представлена как ДНФ
2.2.2 Теорема о совершенной ДНФ.
Любая булева функция 
тождественно не равная 0 может быть разложена в ДНФ следующего вида:
Опр: Носитель булевой функции 
.
Лемма: 
1) 
это элементарно 
2) 
возьмем набор 
а) 
б) 
Доказательство: 
, будем доказывать, что
.
1) Докажем, что . Возьмем 
он попадает в число суммируемых наборов и по нему будет проводиться сумирование.
2) Докажем, что 
. Возьмем другой набор из 
Следовательно 
2.2.3 Некоторые другие виды ДНФ.
Опр: 
— называется минимальной ДНФ, если она имеет 
— наименьшую возможную длину из всех ДНФ данной функции.
Опр: 
— называется тупиковой ДНФ, если из неё нельзя выбросить ни одного слагаемого с сохранением булевой функции.
(Легко понять, что любая минимальная ДНФ является тупиковой, а обратное не верно.)
Опр: К-мерной гранью называется такое подмножество 
, которая является носителем некоторой элементарной конъюнкции длины: n-k.
Опр: Предположим дана функция 
и есть 
. Грань называется отмеченной, если она целиком содержится в носителе Т.
Опр: Максимальная грань – это такая грань, которая не содержится ни в какой грани более высокой размерности.
Предложение: Любую отмеченную грань можно вложить в максимальную грань.
Предложение: 
(Носитель любой функции можно разложить в объединение нескольких граней разной размерностей)
Предложение: Носитель любой функции разлагается в объединение всех своих максимальных граней. 
Опр: Элементарная конъюнкция называется минимальной, если её носитель является максимальной гранью. Следовательно всякая булева функция разлагается в дизъюнкцию всех своих элементарных конъюнкций.
Опр: Сокращенная ДНФ – разложение данной булевой функции в соответствующие ДНФ, которые соответствуют объединению её максимальных граней.
Теор: Минимальная ДНФ может быть получена из сокращенной отбрасыванием некоторого количества слагаемых, возможно пустого.