Досконалі диз’юнктивна і кон’юнктивна нормальні форми
Як ми визначили вище, будь-яка формула має як ДНФ, так і КНФ.
Приклад. Знайдемо ДНФ і КНФ для формули .
– ДНФ
– КНФ.
Більше того, приведення деякої формули до ДНФ і КНФ не є однозначним. Для кожної формули існує нескінченне число рівносильних до неї ДНФ і КНФ. Дійсно, якщо приєднати до неповної ДНФ даної формули елементарні кон’юнкції вигляду і врахувати рівносильність , отримаємо нескінченну множину ДНФ, рівносильних до даної формули. Аналогічно, приєднуючи до деякої КНФ елементарні диз’юнкції вигляду і враховуючи рівносильність , отримаємо нескінченну множину КНФ, рівносильних до даної формули.
Серед множини ДНФ (КНФ), які має дана формула, існує унікальна форма, вона єдина для даної формули. Це – так звана досконала ДНФ (досконала КНФ).
Означення. Досконалою ДНФ (ДДНФ) називається диз’юнкція повних елементарних кон’юнкцій від змінних :
.
ПрикладДДНФ. ;
.
Означення.Досконалою КНФ (ДКНФ) називається кон’юнкція повних елементарних диз’юнкцій від змінних :