2.4. Совершенные дизъюнктивные и конъюнктивные нормальные формы.

Дизъюнктивная (конъюнктивная) нормальная форма называется совершенной, если все её элементарные конъюнкции (дизъюнкции) являются конституентами единицы (соответственно нуля).

Любая логическая функция имеет одну и только одну совершенную дизъюнктивную нормальную форму (СДНФ) и одну и только одну совершенную конъюнктивную нормальную форму (СКНФ).Например :

Функцию  f = х + у  можно записать в СДНФ в виде f=x(отрицание)у+ху(отрицание у)+ху.

От любой нормальной формы можно перейти к совершенной нормальной форме при помощи равносильных преобразований. Такой переход называется развертыванием.

Для этого необходимо :

-                  ввести недостающие переменные в каждое произведение умножением его на равносильность вида  х+х(отрицание)=1, где  х – недостающая переменная;

-                  раскрыть скобки, применяя коммутативный закон (ху = ух);

-                  избавиться от повторяющихся произведений на основании закона тавтологии  (х + х = х).Пример

Рассмотрим нормальную форму: f=xy(отрицание)z+xz(отрицание)                    .

Преобразуем её:

              f=xy(отрицание)z+xz(отрицание)*(у+у(отрицание))=xy(отрицание)z+xyz(отрицание)+xyz(два последних отрицание)       .

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

Совершенные нормальные формы обладают следующими особенностями:

1) Если при каком-либо наборе значений переменных функция равна единице, то в СДНФ только один из её членов принимает единичное значение.

2) Если функция равна нулю, то в СКНФ только один из её членов принимает нулевое значение.