6. Дизъюнктивная и конъюнктивная нормальные формы
Структуру булевых функций наиболее просто анализировать, когда они приведены к одной из так называемых нормальных форм: конъюнктивной или дизъюнктивной.
Дизъюнктивная нормальная форма представляет собой некоторую дизъюнкцию конъюнкций, причем, членами конъюнкций является либо аргументы, либо их отрицания, например
Конъюнктивная нормальная форма представляет собой некоторую конъюнкцию дизъюнкций, например
Для записи конъюнкций и дизъюнкций применим сокращенную запись:
Введем также обозначение:
Теорема 1 (о разложении функции). Каждую булеву функцию 
можно представить в виде
где 
причем, разным значениям 
соответствуют различные наборы 
Такое представление функции называется разложением функции по к переменным.
Доказательство. Очевидно, что конъюнкция
равна единице тогда и только тогда, когда 
Следовательно, в правой части формулы (1.10) все конъюнкции 
будут равны нулю, за исключением той конъюнкции, для которой набор 
совпадает с набором аргументов 
Следовательно, дизъюнкция (1.10) имеет вид
и, согласно свойству 13° (гл. 1,5), равна 
Пример 1. Разложить функцию
по переменным и 
В соответствии с (1.10) получим
Замечая, что
находим
Следствием теоремы 1 является теорема 2.
Теорема 2. Каждая булева функция может быть представлена в дизъюнктивной нормальной форме.
Для осуществления такого разложения в формуле (1.10) надо взять к 
т. е. разложить функцию по всем аргументам. Получим
Так как 
равняется либо 1, либо 0, то формулу (1.17) можно переписать так:
где операция дизъюнкции производится по всем наборам 
для которых 
Пример 2. Представим функцию
в дизъюнктивной нормальной форме.
Составим таблицу значений функций 
Тогда, по формуле (1.18) получим
Пример 3. Представим в дизъюнктивной нормальной форме функцию 
заданную в табл. 3. Используя 2,5 и 6-ю строки табл. 3, получим
Таблица 3
Аналогично можно приводить булевы функции к конъюнктивной нормальной форме.
