Алгоритм построения конъюнктивной совершенной нормальной формы

Конъюнктивная совершенная нормальная форма

Любая таблично заданная ФАЛ f(x₁, x₂, …, x_n) (кроме тождественной единицы) может быть представлена в следующем аналитическом виде:

Представление ФАЛ в таком виде называется конъюнктивной совершенной нормальной формой этой функции (КСНФ).

 

1. Выбрать в таблице все наборы аргументов, на которых функция обращается в 0.

 

2. Выписать дизъюнкции, соответствующие этим наборам аргументов. При этом, если аргумент x_iвходит в данный набор как 0, он вписывается без изменения в дизъюнкцию, соответствующую данному набору. Если x_i входит в данный набор как 1, то в дизъюнкцию вписывается его отрицание.

 

3. Полученные дизъюнкции соединить знаком конъюнкция.