Дизъюнктивная
(конъюнктивная) нормальная форма называется совершенной, если все её
элементарные конъюнкции (дизъюнкции) являются конституентами единицы
(соответственно нуля).
Любая логическая функция имеет одну и только
одну совершенную дизъюнктивную нормальную форму (СДНФ) и одну и только одну
совершенную конъюнктивную нормальную форму (СКНФ).Например :
Функцию
f = х
+ у
можно записать в СДНФ в виде f=x(отрицание)у+ху(отрицание у)+ху.
От любой нормальной формы можно перейти к
совершенной нормальной форме при помощи равносильных преобразований. Такой
переход называется развертыванием.
Для этого необходимо :
- ввести
недостающие переменные в каждое произведение умножением его на равносильность
вида
х+х(отрицание)=1, где х – недостающая переменная;
- раскрыть
скобки, применяя коммутативный закон (ху
= ух);
- избавиться
от повторяющихся произведений на основании закона тавтологии (х + х = х).Пример
Рассмотрим нормальную форму: f=xy(отрицание)z+xz(отрицание)
.
Преобразуем её:
f=xy(отрицание)z+xz(отрицание)*(у+у(отрицание))=xy(отрицание)z+xyz(отрицание)+xyz(два последних отрицание)
.
Аналогично можно перейти и к совершенной
конъюнктивной нормальной форме.
Совершенные нормальные формы обладают
следующими особенностями:
1) Если при каком-либо наборе значений
переменных функция равна единице, то в СДНФ только один из её членов принимает
единичное значение.
2) Если функция равна нулю, то в СКНФ только один из её членов
принимает нулевое значение.
Комментариев нет:
Отправить комментарий