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

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

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

Например :

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

.

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

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

-        ввести недостающие переменные в каждое произведение умножением его на равносильность вида 

, где  х – недостающая переменная;

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

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

Пример

Рассмотрим нормальную форму:

.

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

.

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

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

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

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