Нормальні і досконалі нормальні форми логічних функцій

Будь-яка логічна функція може бути представлена у вигляді диз’юнктивної нормальної форми (ДНФ – диз’юнкція елементарних кон’юнкцій) та кон’юнктивної нормальної форми (КНФ – кон’юнкція елементарних диз’юнкцій).

Елементарними кон’юнкціями називаються кон’юнкції будь-якого числа різних змінних, узятих з інверсіями або без них.

Аналогічно елементарними диз’юнкціями називаються диз’юнкції будь-якого числа змінних, узятих з інверсіями або без них.

Для усякої логічної функції можуть існувати декілька рівносильних ДНФ і КНФ.

Інверсія будь-якої логічної функції, записаної у вигляді Дні КНФ, може бути представлена, навпаки, у вигляді КНФ або ДНФ шляхом заміни операцій множення на складання та складання на множення.

- елементарні диз’юнкції;

- елементарні кон’юнкції.

ДНФ: ;

КНФ: .

Існує вид ДНФ та КНФ, у якому логічна функція може бути записана єдиним чином. Це досконала нормальна форма.

Досконалою диз’юнктивною нормальною формою (ДДНФ) э диз’юнкція елементарних кон’юнкцій, які містять всі змінні з інверсіями або без них.

Досконалою кон’юнктивною нормально формою (ДКНФ) є кон’юнкція елементарних диз’юнкцій, які містять всі змінні з інверсіями або без них.

ДДНФ записується по одиницям за допомогою таблиць істинності:

.

ДКНФ записується по нулям. До тієї ж таблиці:

.

КНФ ті ДНФ можна привести до ДДНФ та ДКНФ.