Нормальные формулы (ДНФ и КНФ)

Назовём элементарной дизъюнкцией (суммой) дизъюнкцию простых компонент и их отрицаний. Аналогично, элементарной конъюнкцией (произведением) назовём конъюнкцию простых компонент и их отрицаний. Дизъюнктивной нормальной формулой (формой) назовём дизъюнкцию элементарных конъюнкций (сумму элементарных произведений) и обозначим ДНФ. И аналогично КНФ - это конъюнкция элементарных дизъюнкций (произведение элементарных сумм).

Теорема. Для всякой формулы логики высказываний существуют равносильные ей ДНФ и КНФ.

Это следует из законов дистрибутивности и из предыдущих теорем.

Пример. Для формулы F= ®ae построить равносильные ей ДНФ и КНФ.

Сначала избавимся от импликаций Fº Úaeº(()Ú`cÚ`d)Úaeº(`aÚ`b)Ú`cÚ`dÚaeº`aÚ`bÚ`cÚ`dÚae - это и есть ДНФ. Теперь применив правило 3, получим Fº(`aÚ`bÚ`cÚ`dÚa)Ù(`aÚ`bÚ`cÚ`dÚe)º`aÚ`bÚ`cÚ`de - это одновременно и ДНФ и КНФ. Здесь `aÚ`bÚ`cÚ`dÚaº1

Замечание. Данный пример показывает, что равносильные ДНФ и КНФ не единственны. Однако, существуют единственные (с точностью до порядка) ДНФ и КНФ, называемыми совершенными ДНФ и КНФ (СДНФ и СКНФ).