Нормальные формы для формул АВ. Лекция 4

1.

Лекция 4. Нормальные
формы.

2.

Нормальные формы для формул
АВ
Для каждой формулы АВ существует равносильная формула,
содержащая лишь отрицание, конъюнкцию и дизъюнкцию. Для
нахождения её достаточно используя равносильности у,ч Теоремы 4.4,
выразить импликации и эквивалентности через отрицание, конъюнкцию
и дизъюнкцию

3.

Понятие нормальных форм

4.

ТЗ: Привести по 3 примера ДНФ и КНФ

5.

Совершенные нормальные
формы

6.

Дополнительные обозначения для нормальных форм

7.

8.

9.

10.

11.

12.

13.

14.

ТЗ: Доказать 5.4 и 5.5

15.

16.

17.

18.

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

19.

ТЗ: написать алгоритм
получения СКНФ путем
равносильных
преобразований