Нормальные формы

Пусть

(*)

– высказывательные переменные.

Элементарной дизъюнкцией (ЭД) называется дизъюнкции любых переменных из (*) или их отрицания . Например, если и набор (*) имеет вид , то – элементарные дизъюнкции. Если в элементарной дизъюнкции участвует все переменные из (*) (либо сама, либо её отрицание), то она называется полной элементарной дизъюнкцией (ПЭД). Например, в случае , перечислим всех полных элементарных дизъюнкций: , , , , , , , .

Элементарной конъюнкцией (ЭК) называется конъюнкции любых переменных из (*) или их отрицания . Например, если и набор (*) имеет вид , то – элементарные конъюнкции. Если в элементарной конъюнкции участвует все переменные из (*) (либо сама, либо её отрицание), то она называется полной элементарной конъюнкцией (ПЭК). Например, в случае , перечислим всех полных элементарных конъюнкций: , , , , , , , .

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкции произвольного количества элементарных конъюнкций. Схематично ДНФ имеет вид:

(ЭК)Ú (ЭК)Ú (ЭК)Ú ….

Если все входящие в ДНФ элементарные конъюнкции являются полными, то она называется совершенной дизъюнктивной нормальной формой (СДНФ). Схематично СДНФ имеет вид:

(ПЭК)Ú (ПЭК)Ú (ПЭК)Ú ….

Конъюнктивной нормальной формой (КНФ) называется конъюнкции произвольного количества элементарных дизъюнкций. Схематично КНФ имеет вид:

(ЭД)Ú (ЭД)Ú (ЭД)Ú ….

Если все входящие в КНФ элементарные дизъюнкции являются полными, то она называется совершенной конъюнктивной нормальной формой (СКНФ). Схематично СКНФ имеет вид:

(ПЭД)Ú (ПЭД)Ú (ПЭД)Ú ….

Для каждой формулы, не являющейся тождественно истинной и тождественно ложной, существуют равносильные СДНФ и СКНФ.