КНФ и ДНФ лекция

1. Канонические виды формул

2.

Канонические виды формул
Формула, которая есть пропозициональная переменная или отрицание
переменной, называется литералом.
Некоторая формула называется элементарной конъюнкцией (или конъюнктом),
если она является конъюнкцией литералов, то есть конъюнкцией переменных и
отрицаний переменных.
Примеры элементарных конъюнкций
Не Х1; Х2; Х1 не Х2; не Х1 Х2 Х1 Х3
Элементарная конъюнкция называется совершенной, если каждая из
пропозициональных переменных входит в нее ровно один раз, со знаком
отрицания или без него.

3.

Канонические виды формул
Дизъюнктивной нормальной формой (ДНФ) называется произвольная
дизъюнкция элементарных конъюнкций.
Примеры элементарных конъюнкций
Не Х1; Х2; Х1 не Х2; (не Х1 Х2) (Х1 не Х2)
Каждую логическую формулу можно привести эквивалентными
преобразованиями к ДНФ (т. е. для любой формулы A можно найти такую
формулу B, находящуюся в ДНФ, что A ≡ B).

4.

Порядок
преобразований к
ДНФ
4) Постоянно избавляются от
двойных отрицаний

5.

Каждую выполнимую логическую формулу можно привести эквивалентными
преобразованиями к СДНФ.

6.

Правила преобразования ДНФ в СДНФ
скобки внутри каждой такой элементарной конъюнкции, применяя
закон дистрибутивности.

7.

Правила преобразования ДНФ в СДНФ (продолжение)

8.

Конъюнктивные нормальные формы
Произвольная дизъюнкция литералов называется элементарной
дизъюнкцией (или дизъюнктом).
Конъюнктивной нормальной формой (КНФ) называется произвольная
конъюнкция дизъюнктов.
Конъюнктивные нормальные формы можно получить из ДНФ путем
замены в них знаков ∨ на &, а & на ∨.
Символы & и ∨ называются двойственными друг другу.
Известно, что каждую логическую формулу можно привести
эквивалентными преобразованиями к КНФ.

9.

10.

11.

Конъюнктивные нормальные формы