Следствие 2. Совершенная конъюнктивная нормальная форма

Любая функция f может быть представлена в следующей форме:

Таким образом, любая булева функция может быть представлена суперпозицией конъюнкции, дизъюнкции и отрицания. Разложение по всем переменным в дизъюнкцию называется совершенной дизъюнктивной нормальной формой функции, а в конъюнкцию – совершенной конъюнктивной нормальной формой. Совершенная дизъюнктивная и конъюнктивная нормальная формы дают способ представления булевой функции через суперпозицию конъюнкции, дизъюнкции и отрицания.

Чтобы получить совершенную дизъюнктивную нормальную форму, надо взять все наборы, на которых значение функции равно 1, и записать для каждого из них конъюнкцию переменных и их отрицаний. Если в наборе значение переменной равно 0, то переменную надо взять с отрицанием, если 1 – без отрицания. Из получившихся конъюнкций надо построить дизъюнкцию.

Чтобы получить совершенную конъюнктивную нормальную форму, надо взять все наборы, на которых значение функции равно 0, и записать для каждого из них дизъюнкцию переменных и их отрицаний. Если в наборе значение переменной равно 0, то переменную надо взять без отрицания, если 1 – с отрицанием. Из получившихся дизъюнкций надо построить конъюнкцию.