Формы представления булевых функций (СДНФ, СКНФ, СПНФ)

Любую булеву функцию y=f(a,b) можно представить как комбинацию областей:

Тогда в зависимости от значения функций и заданных , которые именуются констинтуентами, получим 16-ть конечных операций, которые в общем виде можно записать:

Такая форма представления называется СДНФ (совершенно-дизъюнктивная нормальная форма)

В ней констинтуенты – коньюнты соединяются с помощью дизъюнкции.

В логике Буля действует принцип двойственности, который говорит, если одновременно заменить все конъюнкции на дизъюнкции, или наоборот (все ^ на v), замене символов (конъюнкция на дизъюнкцию и 0 на 1), то все логические равенства остаются в силе.

Такая форма представления логических функций называется СКНФ (совершенная коньюктивная нормальная форма). В ней констинтуенты – дизъюнкты, соединяются с помощью конъюнкции.

Существует также третья форма представления логических функций СПНФ – совершенная полиномиальная нормальная форма. Ее можно получить из СДНФ путем следующей замены:

Так как СДНФ все констинтуенты не пересекаются, то можно записать: