5.2 Дизъюнктивная нормальная форма и совершенная дизъюнктивная нормальная форма (ДНФ и СДНФ)

         Определение 1. Элементарной конъюнкцией n переменных называется конъюнкция переменных или их отрицаний.

            Определение 2. Дизъюнктивной нормальной формой (ДНФ) формулы А называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций.

            Определение 3. Совершенной дизъюнктивной нормальной формой (СДНФ) формулы А называется ДНФ А, обладающая свойствами (С).

            СДНФ А можно получить двумя способами:

            а) с помощью таблицы истинности;

            б) с помощью равносильных преобразований.

            Правило получения СДНФ из формулы А  с помощью равносильных преобразований.

1.      Для формулы А получаем ДНФ А.

2.      Из ДНФ А путем равносильных преобразований получаем СДНФ, последовательно добиваясь выполнения четырех свойств СДНФ А:

1)      Пусть В есть слагаемое ДНФ А, не содержащее . Тогда надо заменить слагаемое В в ДНФ А на слагаемое  (т.к. B)

2)      Если в ДНФ А встретится два одинаковых слагаемых , то лишнее нужно отбросить, так как .

3)      Если в некоторое слагаемое В в ДНФ А переменная  входит дважды, то лишнюю переменную надо отбросить так как .

4)      Если слагаемое В в ДНФ А содержит переменную и ее отрицание , то В можно отбросить, т.к.  и следовательно  (в силу равносильности ).

Create by Barshay Natalia © 2005-2007