logo
Лекции ДМ

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

Формула , составленная для заданной таблицей истинности функции, по выше приведенному правилу обладает свойствами, которые называются свойствами совершенства. Перечислим их:

  1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию.

  2. Все логические слагаемые различны.

  3. Ни одно слагаемое не содержит одновременно переменную и ее отрицание.

  4. Ни одно слагаемое не содержит одну и ту же переменную дважды.

Каждой не тождественно ложной формуле соответствует единственная формула с такими свойствами.

Для одной и той же формулы можно составить множество равносильных ей ДНФ. Но среди них существует единственная ДНФ с перечисленными свойствами совершенства.

ДНФ, для которой выполняются свойства совершенства называется совершенной ДНФ (СДНФ).

Составленная формула по таблице истинности и является СДНФ формулы.

Если функция задана какой – либо формулой, то для получения СДНФ формулы необходимо составить таблицу истинности. Если формула содержит большое количество переменных высказываний, то этот способ практически не приемлем. В этом случае получают СДНФ формулы путем равносильных преобразований.

Приведем соответствующий алгоритм:

  1. Путем равносильных преобразований получить какую – либо ДНФ.

  2. Если какая-либо элементарная конъюнкция В не содержит переменную хi , то вводят ее, используя равносильность . И раскрывают скобки.

  3. Если в ДНФ входят две одинаковые конъюнкции В, то лишнюю отбрасывают, используя свойство идемпотентности ВV B  B.

  4. Если какая-либо конъюнкция содержит xi вместе с отрицанием, то В  0. И В исключают из ДНФ.

  5. Если какая-либо конъюнкция содержит переменную xi дважды, то одну из них отбрасывают, используя свойство xi xi  xi.

Примеры.

1. Составить СДНФ для формулы по таблице истинности и путем равносильных преобразований.

Составим таблицу истинности, которая содержит 4 строки.

х

у

1

2

3

4

0

0

1

1

0

0

1

0

1

1

0

1

0

1

0

0

0

0

1

1

0

1

1

1

Получим какую-либо ДНФА и преобразованиями доведем до совершенства:

  1. Аналогичное задание для формулы

Составим таблицу истинности, содержащую 8 строк.

a

b

c

1

2

3

4

1

1

1

1

1

1

1

1

1

0

0

1

1

1

1

0

1

0

0

1

1

0

1

1

1

0

0

0

0

0

1

0

0

1

0

0

1

0

0

0

1

0

1

0

0

0

0

1

1

0

0

0

0

0

1

0

Преобразуем формулу:

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