Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Конъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма
|
|
Элементарной дизъюнкцией п переменных называется дизъюнкция переменных или их отрицаний.
Конъюнктивной нормальной формой (КНФ) формулы А называется равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций.
Для любой формулы алгебры логики путем равносильных преобразований можно получить ее КНФ, причем не единственную.
Например, для формулы А = Ø (х Ú у) º х Ù у имеем:
А = (Ø (х Ú у) ® х Ù у) Ù (х Ù у ® Ø (х Ú у)) =
= (х Ú у Ú х Ù у) Ù (Ø (х Ù у) Ú Ø (х Ú у)) =
= (х Ú х Ú у) Ù (х Ú у Ú у) Ù (Ø х Ú Ø у Ú Ø х) Ù (Ø х Ú Ø у Ú Ø у), то есть
КНФ А = (х Ú х Ú у) Ù (х Ú у Ú у) Ù (Ø х Ú Ø у Ú Ø х) Ù (Ø х Ú Ø у Ú Ø у).
Но так как х Ú х = х, у Ú у = у, Ø х Ú Ø х = Ø х, Ø у Ú Ø у = Ø у, то
КНФ A = (х Ú у) Ù (х Ú у) Ù (Ø х Ú Ø у) Ù (Ø х Ú Ø у).
А так как (х Ú у) Ù (х Ú у) = х Ú у, (Ø х Ú Ø у) Ù (Ø х Ú Ø у) = (Ø х Ú Ø у), то
КНФ A = (х Ú у) Ù (Ø х Ú Ø у).
КНФ А называется совершенной конъюнктивной нормальной формой формулы А (СКНФ А), если для нее выполнены условия:
- Все элементарные дизъюнкции, входящие в КНФ А, различны.
- Все элементарные дизъюнкции, входящие в КНФ А, содержат все переменные.
- Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит двух одинаковых переменных.
- Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит переменную и ее отрицание.
Можно доказать, что каждая не тождественно истинная формула имеет единственную СКНФ.
Один из способов получения СКНФ состоит в использовании таблицы истинности для формулы Ø А. Действительно, получив с помощью таблицы истинности СДНФ Ø А, мы получим СКНФ А, взяв отрицание Ø (СДНФ Ø А), то есть СКНФ А = Ø (СДНФ Ø А).
Другой способ получения СКНФ, использующий равносильные преобразования, состоит в следующем:
- Путем равносильных преобразований формулы А получают одну из КНФ А.
- Если в полученной КНФ А входящая в нее элементарная дизъюнкция В не содержит переменную хi, то, используя закон В Ú (xi Ù Ø xi) = В, элементарную дизъюнкцию В заменяют на две элементарные дизъюнкции В Ú xi и В Ú Ø xi, каждая из которых содержит переменную xi.
- Если в КНФ А входят две одинаковых элементарных дизъюнкции В, то лишнюю можно отбросить, пользуясь законом В Ù В = В.
- Если некоторая элементарная дизъюнкция, входящая в КНФ А, содержит переменную xi дважды, то лишнюю можно отбросить, пользуясь законом xi Ú xi = xi.
- Если некоторая элементарная дизъюнкция, входящая в КНФ А, содержит переменную 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).
Date: 2015-04-23; view: 679; Нарушение авторских прав