Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма
Лекция, 06 Ноября 2013, автор: пользователь скрыл имя
Краткое описание
Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые: ¬X&X; X&¬Z; ¬ X&Y& ¬Z ; Всякую дизъюнкцию элементарных конъюнкций назовем дизъюнктивной нормальной формой (ДНФ): (X &X &¬Y) Ú(¬X&Z).
Cовершенной ДНФ называется ДНФ, в которой нет одинаковых элементарных конъюнкций и все конъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз (возможно с отрицанием)X&Y&¬ZVX&Y& Z.
Прикрепленные файлы: 1 файл
СКНФ и СКДФ.doc
— 136.50 Кб (Скачать документ)Совершенная
дизъюнктивная нормальная форма и
совершенная конъюнктивная
нормальная форма
СДНФ и скнф.
Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые: ¬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;
- Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке =1, то в конъюнкцию включают саму эту переменную, если =0, то ее отрицание;
- Все полученные конъюнкции связать в дизъюнкцию.
Пример 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 |
Алгоритм получения СКНФ по таблице истинности
- Отметить те строки ТИ, в последнем столбце которых стоят 0;
- Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке =0, то в дизъюнкцию включают саму эту переменную, если =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)