2.2 Совершенные нормальные формы.

Разложение Шеннона.

Любая БФ , не равная тождественно нулю, единственным образом представима в виде прямого разложения Шеннона:

,

где n – количество переменных ,

– знак отрицания, если , или его отсутствие, если на j-м наборе,

– значение функции на j-м наборе.

(СДНФ)

Конъюнкция всех переменных с соответствующими знаками (отрицания или его отсутствия) на единичном ( ) наборе функции называется конституентой единицы функции.

Дизъюнкция всех переменных с противоположными знаками над ними на нулевом ( ) наборе функции называется конституентой нуля функции.

Любая БФ , не равная тождественно 0, единственным образом представима в виде обратного разложения Шеннона:

.

(СКНФ), в данном случае совпадает с ДНФ).