Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Совершенная конъюнктивная нормальная форма




Конъюнктивная нормальная форма и

 

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

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

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

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

А = (Ø (х Ú у) ® х Ù у) Ù (х Ù у ® Ø (х Ú у)) =

= (х Ú у Ú х Ù у) Ù (Ø (х Ù у) Ú Ø (х Ú у)) =

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

КНФ А = (х Ú х Ú у) Ù (х Ú у Ú у) Ù (Ø х Ú Ø у Ú Ø х) Ù (Ø х Ú Ø у Ú Ø у).

Но так как х Ú х = х, у Ú у = ух Ú Ø х = Ø ху Ú Ø у = Ø у, то

КНФ A = (х Ú у) Ù (х Ú у) Ù (Ø х Ú Ø у) Ù (Ø х Ú Ø у).

А так как (х Ú у) Ù (х Ú у) = х Ú у,(Ø х Ú Ø у) Ù (Ø х Ú Ø у) = (Ø х Ú Ø у), то

КНФ A = (х Ú у) Ù (Ø х Ú Ø у).

КНФ А называется совершенной конъюнктивной нормальной формой формулы А (СКНФ А), если для нее выполнены условия:

  • Все элементарные дизъюнкции, входящие в КНФ А, различны.
  • Все элементарные дизъюнкции, входящие в КНФ А, содержат все переменные.
  • Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит двух одинаковых переменных.
  • Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит переменную и ее отрицание.

Можно доказать, что каждая не тождественно истин­ная формула имеет единственную СКНФ.

Один из способов получения СКНФ состоит в исполь­зовании таблицы истинности для формулы Ø А. Действительно, получив с помощью таблицы истин­ности СДНФ Ø А, мы получим СКНФ А,взяв отрицание Ø (СДНФ Ø А), то есть СКНФ А = Ø (СДНФ Ø А).

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

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

Ясно, что после описанной процедуры будет получе­на СКНФ А. Например, для формулы А = x Ú y Ù (x Ú Ø y)КНФ А = x Ú (y Ù (x Ú Ø y)) = (x Ú y) Ù (x Ú x Ú Ø y). Так как обе элементарные дизъюнкции содержат все переменные (x и y), то первое и второе условие СКНФ выполнены. Элементарная дизъюнкция x Ú x Ú Ø y содержит переменную х дважды, но x Ú x = x, поэтому КНФ А = (x Ú y) Ù (x Ú Ø y); причем, ни одна из элементарных дизъюнкций не содержит переменную и ее отрицание. Значит, все условия СКНФ выполнены, и, следовательно, СКНФ А = (x Ú y) Ù (x Ú Ø y).

 

 




Поделиться с друзьями:


Дата добавления: 2015-04-24; Просмотров: 485; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.