![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Элементарной конъюнкцией n переменных называется конъюнкция переменных или их отрицаний.
Дизъюнктивной нормальной формой (ДНФ) формулы А называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций.
Для любой формулы алгебры логики путем равносильных преобразований можно получить ее ДНФ, причем не единственную.
Например, для формулы А = х Ù (х ® y) имеем:
А = х Ù (Ø х Ú y) = (х Ù Ø х) Ú (х Ù y) = х Ù y, то есть
ДНФ А = (х Ù Ø х) Ú (х Ù y) и
ДНФ А = х Ù y.
Среди многочисленных ДНФ А существует единственная ДНФ А, для которой выполняются перечисленные выше четыре свойства совершенства. Такая ДНФ А называется совершенной дизъюнктивной нормальной формой формулы А (СДНФ А).
Как уже указывалось, СДНФ А может быть получена с помощью таблицы истинности.
Другой способ получения СДНФ формулы А основан на равносильных преобразованиях формулы и состоит в следующем:
Ясно, что после выполнения описанной процедуры будет получена СДНФ А. Например, для формулы А = x Ú y Ù (x Ú Ø y) ДНФ А = x Ú (x Ù y) Ú (y Ù Ø y). Так как элементарная конъюнкция В = х, входящая в ДНФ А, не содержит переменной у, то заменим ее на две элементарных конъюнкции (x Ù y) и (x Ù Ø y), В результате получим ДНФ А = x Ù y Ú x Ù Ø y Ú x Ù y Ú y Ù Ø y.
Так как теперь ДНФ А содержит две одинаковых элементарных конъюнкции x Ù y, то отбросим лишнюю. В результате получим ДНФ A = x Ù y Ú x Ù Ø y Ú y Ù Ø y.
Так как элементарная конъюнкция y Ù Ø y содержит переменную у и ее отрицание, то y Ù Ø y = 0, и ее можно отбросить как нулевой член дизъюнкции.
Таким образом, получаем СДНФ А = x Ù y Ú x Ù Ø y.
Дата публикования: 2014-12-08; Прочитано: 315 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!