Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать неотразимый комплимент Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?

Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Дизъюнктивная нормальная форма и совершенная дизъюнктивная нормальная форма





 

Элементарной конъюнкцией n переменных называется конъюнкция переменных или их отрицаний.

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

Для любой формулы алгебры логики путем равно­сильных преобразований можно получить ее ДНФ, при­чем не единственную.

Например, для формулы А = х Ù (х ® y) имеем:

А = х Ù (Ø х Ú y) = (х Ù Ø х) Ú (х Ù y) = х Ù y, то есть

ДНФ А = (х Ù Ø х) Ú (х Ù y) и

ДНФ А = х Ù y.

Среди многочисленных ДНФ А существует единствен­ная ДНФ А, для которой выполняются перечисленные выше четыре свойства совершенства. Такая ДНФ А называется совершенной дизъюнктив­ной нормальной формой формулы А (СДНФ А).

Как уже указывалось, СДНФ А может быть получе­на с помощью таблицы истинности.

Другой способ получения СДНФ формулы А основан на равносильных преобразованиях формулы и состоит в следующем:

  1. путем равносильных преобразований формулы А получают одну из ДНФ А.
  2. если в полученной ДНФ А входящая в нее эле­ментарная конъюнкция В не содержит переменную xi, то, используя закон B Ù (xi Ú Ø xi) = B, элемен­тарную конъюнкцию B заменяют на две элементарных конъюнкции (B Ù xi) и (B Ù Ø xi), каждая из которых со­держит переменную xi.
  3. если в ДНФ А входят две одинаковых элементар­ных конъюнкции В, то лишнюю можно отбросить, пользу­ясь равносильностью В Ú В = В.
  4. если некоторая элементарная конъюнкция В, вхо­дящая в ДНФ А, содержит переменную xi и ее отрица­ние Ø xi, то, на основании закона xi Ù Ø xi = 0, В = 0 и В, таким образом, можно исключить из ДНФ А, как нулевой член дизъюнкции.
  5. если некоторая элементарная конъюнкция, вхо­дящая в ДНФ А, содержит переменную xi дважды, то одну переменную можно отбросить, пользуясь законом xi Ù xi = xi.

Ясно, что после выполнения описанной процедуры будет получена СДНФ А. Например, для формулы А = 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.

 






Date: 2015-04-23; view: 321; Нарушение авторских прав

mydocx.ru - 2015-2020 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию