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

Автор работы: Пользователь скрыл имя, 06 Ноября 2013 в 19:56, лекция

Краткое описание

Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые: ¬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;
  2. Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке =1, то в конъюнкцию включают саму эту переменную, если =0, то ее отрицание;
  3. Все полученные конъюнкции связать в дизъюнкцию.

Пример  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


 

 

Алгоритм получения СКНФ по таблице истинности

  1. Отметить те строки ТИ, в последнем столбце которых стоят 0;
  2. Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке =0, то в дизъюнкцию включают саму эту переменную, если =1, то ее отрицание;
  3. Все полученные дизъюнкции связать в конъюнкцию.

Пример 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)


Информация о работе Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма