![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Пусть
(*)
– высказывательные переменные.
Элементарной дизъюнкцией (ЭД) называется дизъюнкции любых переменных из (*) или их отрицания
. Например, если
и набор (*) имеет вид
, то
– элементарные дизъюнкции. Если в элементарной дизъюнкции участвует все переменные из (*) (либо сама, либо её отрицание), то она называется полной элементарной дизъюнкцией (ПЭД). Например, в случае
, перечислим всех полных элементарных дизъюнкций:
,
,
,
,
,
,
,
.
Элементарной конъюнкцией (ЭК) называется конъюнкции любых переменных из (*) или их отрицания
. Например, если
и набор (*) имеет вид
, то
– элементарные конъюнкции. Если в элементарной конъюнкции участвует все переменные из (*) (либо сама, либо её отрицание), то она называется полной элементарной конъюнкцией (ПЭК). Например, в случае
, перечислим всех полных элементарных конъюнкций:
,
,
,
,
,
,
,
.
Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкции произвольного количества элементарных конъюнкций. Схематично ДНФ имеет вид:
(ЭК)Ú (ЭК)Ú (ЭК)Ú ….
Если все входящие в ДНФ элементарные конъюнкции являются полными, то она называется совершенной дизъюнктивной нормальной формой (СДНФ). Схематично СДНФ имеет вид:
(ПЭК)Ú (ПЭК)Ú (ПЭК)Ú ….
Конъюнктивной нормальной формой (КНФ) называется конъюнкции произвольного количества элементарных дизъюнкций. Схематично КНФ имеет вид:
(ЭД)Ú (ЭД)Ú (ЭД)Ú ….
Если все входящие в КНФ элементарные дизъюнкции являются полными, то она называется совершенной конъюнктивной нормальной формой (СКНФ). Схематично СКНФ имеет вид:
(ПЭД)Ú (ПЭД)Ú (ПЭД)Ú ….
Для каждой формулы, не являющейся тождественно истинной и тождественно ложной, существуют равносильные СДНФ и СКНФ.
Дата публикования: 2014-11-03; Прочитано: 354 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!