Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
1. Форма А1 Ú А2 Ú... Ú Аn, где Аi, - элементарное высказывание или отрицание элементарного высказывания (литерал), называется элементарной дизъюнкцией .
2. Форма B1 × B2 ×... × Bn, где Bi - литерал, называется элементарной конъюнкцией .
3. Форма D1 × D2 ×... × Dn, где Dj - элементарная дизъюнкция, называется конъюнктивной нормальной формой (КНФ).
4. Форма K1 Ú K2 Ú... Ú Kn, где Kj - элементарная конъюнкция, называется дизъюнктивной нормальной формой (ДНФ).
Всегда истинное (на любых наборах значений входящих в него элементарных высказываний) сложное высказывание называется тавтологией.
Всегда ложное (на любых наборах значений входящих в него элементарных высказываний) высказывание называется противоречием.
Совершенной КНФ (СКНФ) называется такая КНФ, что каждая входящая в нее элементарная дизъюнкция содержит все элементарные высказывания прямо или с инверсией строго по одному разу. Нет повторяющихся дизъюнкций. Любое сложное высказывание, кроме тавтологии, имеет единственную СКНФ.
Совершенной ДНФ (СДНФ) называется такая ДНФ, что каждая входящая в нее элементарная конъюнкция содержит все элементарные высказывания прямо или с инверсией строго по одному разу. Нет повторяющихся конъюнкций. Любое сложное высказывание, кроме противоречия, имеет единственную СДНФ.
Дата публикования: 2014-11-03; Прочитано: 336 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!