Дизъюнктивная и конъюнктивная нормальные формы

Пусть , будем считать, что , если и , если .

Конъюнкция и дизъюнкция являются ассоциативными операциями: и ). Поэтому определены выражения и , которые называются элементарной конъюнкцией и элементарной дизъюнкцией длины n соответственно. Заметим, что конъюнкция принимает значение 1 на единственном наборе значений переменных , а на всех остальных наборах значений переменных обращается в 0. Дизъюнкция же, напротив, принимает значение 0 на единственном наборе значений переменных, а на всех остальных наборах значений переменных равна 1.

Это позволяет каждую булеву функцию представить в виде

или в виде

&

которые называются соответственно совершенной дизъюнктивной нормальной формой (д.н.ф.) и совершенный конъюнктивной нормальной формы (к.н.ф.) для функции ƒ.

В совершенных д.н.ф. и к.н.ф. все элементарные конъюнкции (э.к.) и элементарные дизъюнкции (э.д.) имеют одинаковую длину, равную числу переменных n. Может, однако, оказаться, что у некоторых э.к. в совершенной д.н.ф. может быть опущена часть букв, а другие э.к. могут быть одновременно вообще удалены, причем полученная д.н.ф. (уже не сокращенная) будет представлять ту же самую функцию. Тем самым иногда удается существенно упростить представление булевой функции в виде д.н.ф.. Аналогично может быть упрощена и к.н.ф.. В процессе упрощения могут использоваться свойства 1) – 9) булевой алгебры.