Тема 8. Конъюнктивная нормальная форма(кнф)
▪ Элементарная конъюнкция.
▪ Конъюнктивная нормальная форма.
▪ Минимальная КНФ. Два правила поглощения.
▪ Совершенная конъюнктивная нормальная форма(СКНФ).
▪ Два способа получения КДНФ.
Определение 1. Элементарной дизъюнкцией п переменных называется дизъюнкция переменных или их отрицаний.
Определение 2. Конъюнктивной нормальной формой (КНФ) формулы А называется равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций.
Для любой формулы алгебры логики путем равносильных преобразований можно получить ее КНФ, причем не единственную.
Например, для формулы имеем:
, то есть
КНФ A .
Но так как х˅х = х, у ˅ у = у, , то КНФ А = .
А так как ,,
то КНФ A=.
Определение 3. КНФ А называется совершенной конъюнктивной нормальной формой формулы А ( СКНФ А ), если для нее выполнены условия:
-
Все элементарные дизъюнкции, входящие в КНФ А, различны.
-
Все элементарные дизъюнкции, входящие в КНФ А , содержат все переменные.
-
Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит двух одинаковых переменных.
-
Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит переменную и ее отрицание.
Каждая не тождественно истинная формула имеет единственную СКНФ.
Один из способов получения СКНФ состоит в использовании таблицы истинности для формулы .
Действительно, получив с помощью таблицы истинности СДНФ , мы получим СКНФ А , взяв отрицание , то есть СКНФ А = .
Другой способ получения СКНФ, использующий равносильные преобразования, состоит в следующем:
Путем равносильных преобразований формулы А получают одну из КНФ А.
Если в полученной КНФ А входящая в нее элементарная дизъюнкция В не содержит переменную xi,то, используя равносильность , элементарную дизъюнкцию В заменяют на две элементарные дизъюнкции В ˅ xi и , каждая из которых содержит переменную xi.
-
Если в КНФ А входят две одинаковых элементарных дизъюнкции В, то лишнюю можно отбросить, пользуясь равносильностью В˄ В = В .
-
Если некоторая элементарная дизъюнкция, входящая в КНФ А, содержит переменную xi дважды, то лишнюю можно отбросить, пользуясь равносильностью xi ˅ xi = xi.
-
Если некоторая элементарная дизъюнкция, входящая в КНФ А , содержит переменную xi и ее отрицание, то = 1 и, следовательно, вся элементарная дизъюнкция имеет значение 1, а поэтому ее можно отбросить, как единичный член конъюнкции.
Ясно, что после описанной процедуры будет получена СКНФ А.
Конъюнктивная нормальная форма(КНФ)
В результате изучения курса математической логики учащиеся должны:
- знать определение «элементарной конъюнкции», «конъюнктивной нормальной формы», «минимальной КНФ», «совершенной конъюнктивной нормальной формы(СКНФ)», два правила поглощения, два способа получения СКНФ;
- уметь находить КНФ, минимальную КНФ, СКНФ по заданной формуле и выполнять проверку полученного результата с помощью таблицы истинности.
- Тема 1. История возникновения логики.
- Тема 4.Формула алгебры логики. Таблица истинности.
- 1.Основные равносильности
- 2.Равносильности, выражающие одни логические законы через другие:
- З.Равносильности, выражающие основные законы алгебры логики:
- Тема 7.Дизъюнктивная нормальная форма(днф)
- Тема 8. Конъюнктивная нормальная форма(кнф)
- Тема 9.Приложение алгебры логики в технике (релейно-контактные схемы)
- Тема 10.Применение аппарата алгебры логики к решению содержательных задач.