 |
|
Нормальные формы булевых функций
В булевой алгебре для представления функций используются специальные формы, называемые нормальными формами. В качестве элементов в выражениях булевых функций используются буквы. Под буквой понимается или сама буква, или буква со знаком отрицания, или константа. Для представления некоторой обобщенной буквы, которая может иметь или не иметь отрицание, используются обозначения вида: ã.
Для построение нормальных форм булевых функций используются простейшие выражения, называемые элементарно конъюнкцией или термом, или элементарной дизъюнкцией (дизъюнктивным термом). Элементарной конъюнкцией называется выражение, представляющее собой конъюнкцию любого конечного множества попарно различных букв или состоящее из одной буквы.
Элементарной дизъюнкцией называется выражение, представляющее собой дизъюнкцию любого конечного множества попарного различных букв или состоящее из одной буквы.
Различают две нормальные формы представления булевых функций: дизъюнктивная и конъюнктивная.
Дизъюнктивной нормальной формой (ДНФ) является дизъюнкция любого конечного множества элементарных конъюнкций.
Конъюнктивной нормальной формой (КНФ) называется конъюнкция любого конечного множества элементарных дизъюнкций.
Любую булеву функцию можно привести к КНФ и ДНФ, используя для преобразования произвольной формы функции законы булевой алгебры. Для булевых функций от n переменных вводятся следующие понятия:
- элементарные конъюнкции (соответственно, элементарные дизъюнкции) называются конституантами единицы соответственно нуля, если они содержат все переменные функции
-
для функции n переменных конституанты единицы и нуля имеют вид соответственно:
Для представления булевых функций широко используются канонический конъюнктивные и дизъюнктивные формы. КНФ (ДНФ) называется канонической, если все её элементарные дизъюнкции (соответственно, конъюнкции) являются конституантами нуля (соответственно), единицы. Любая булева функция имеет одну и только одну конъюнктивную каноническую форму, одну и только одну дизъюнктивную каноническую форму. Канонические формы иначе называются совершенными формами.