Автор работы: Пользователь скрыл имя, 06 Ноября 2013 в 19:56, лекция
Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые: ¬X&X; X&¬Z; ¬ X&Y& ¬Z ; Всякую дизъюнкцию элементарных конъюнкций назовем дизъюнктивной нормальной формой (ДНФ): (X &X &¬Y) Ú(¬X&Z).
Cовершенной ДНФ называется ДНФ, в которой нет одинаковых элементарных конъюнкций и все конъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно с отрицанием)X&Y&¬ZVX&Y& Z.
Совершенная
дизъюнктивная нормальная форма и
совершенная конъюнктивная
нормальная форма
СДНФ и скнф.
Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые: ¬X&X; X&¬Z; ¬ X&Y& ¬Z ;
Элементарной дизъюнкцией называется дизъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые: ¬XVX; XV¬ Z; ¬X V Y V¬Z ;
Всякую дизъюнкцию элементарных конъюнкций назовем дизъюнктивной нормальной формой (ДНФ): (X &X &¬Y) Ú(¬X&Z)
Всякую конъюнкцию элементарных дизъюнкций назовем конъюнктивной нормальной формой (КНФ): (X VX V¬ Y)&(¬XVZ)
Cовершенной ДНФ называется ДНФ, в которой нет одинаковых элементарных конъюнкций и все конъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно с отрицанием)X&Y&¬ZVX&Y& Z
Cовершенной КНФ называется КНФ, в которой нет одинаковых элементарных дизъюнкций и все дизъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно с отрицанием) (¬ X VY V Z)&(X V¬Y V Z.
Любую функцию, кроме констант 0 и 1, можно представить в виде СДНФ и СКНФ
СДНФ и СКНФ можно получить двумя способами:
а) с помощью таблицы истинности;
б) с помощью равносильных преобразований.
Правило получения СДНФ из формулы А с помощью равносильных преобразований.
1. Для формулы А получаем ДНФ А.
2. Из ДНФ А путем равносильных преобразований получаем СДНФ, последовательно добиваясь выполнения четырех свойств СДНФ А.
Алгоритм получения СДНФ по таблице истинности
Пример 1. Найти СДНФ для формулы .
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Алгоритм получения СКНФ по таблице истинности
Пример 2. Найти СКНФ для формулы .
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
Задания для самостоятельной работы
I. Найти СДНФ для формулы
1)
2)
3)
4)
II. Найти СКНФ для формулы
1)
2)
3)
4)
III. Найти СКНФ и СДНФ для формулы
1)
2)