Дизъюнктивные и конъюнктивные нормальные формы в алгебре высказываний

Если х — логическая переменная, δ {0, 1}, то выражение

называется литерой. Литеры х и х называются контрарными.

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

Пример 8. Формулы x∨ y∨ z и x∨ y∨ x∨ x — дизъюнкты, формулы x∧ y∧ z и x∧ y∧ x — конъюнкты, а x является одновременно и дизъюнктом, и конъюнктом.

Дизъюнкция конъюнктов называется дизъюнктивной нормальной формой (ДНФ); конъюнкция дизъюнктов называется конъюнктивной нормальной формой (КНФ).

Пример 9. Формула (x∧ y)∨ (y∧ z) — ДНФ, формула (х∨ z∨ y)∧ (x∨ z)∧ y — КНФ, а формула x∧ y является одновременно КНФ и ДНФ.

Теорема 2. Для любой формулы φ АВ существует ДНФ (КНФ) ψ АВ такая, что φ ≡ ψ;.

Опишем алгоритм приведения формулы к ДНФ.

1. Выражаем импликацию, участвующую в построении формулы, через дизъюнкцию и отрицание, используя эквивалентность φ → ψ ≡ φ ∨ ψ;.

2. Используя законы де Моргана, переносим все отрицания к переменным и сокращаем двойные отрицания пользуясь законом двойного отрицания.

3. Используя закон дистрибутивности φ ∧ (ψ ∨ χ)≡ (φ ∧ ψ)∨ (φ ∧ χ), преобразуем формулу так, чтобы все конъюнкции выполнялись раньше дизъюнкций.

В результате применения пп. 1-3 получается ДНФ, эквивалентная исходной формуле.

Пример 10. Привести к ДНФ формулу φ ((x→ y)∨ (y→ z)).

Решение. Выразим логическую операцию → через ∨ и: φ ≡ ((x∨ y)∨ (y∨ z)). Воспользуемся законами де Моргана и двойного отрицания: φ ≡ (x∨ y)∧ (y∨ z)≡ (x∧ y)∧ (y∨ z)≡ (x∧ y)∧ (y∨ z). Используя закон дистрибутивности, приводим формулу к ДНФ: φ ≡ (x∧ y∧ y)∨ (x∧ y∧ z). Упростим полученную формулу: (x∧ y∧ y)∨ (x∧ y∧ z)≡ (1) (x∧ y)∨ (x∧ y∧ z)≡ (2) x∧ y (для преобразования (1) использовался закон идемпотентности, для (2) – закон поглощения). Таким образом, формула φ эквивалентными преобразованиями приводится к формуле x∧ y, являющейся одновременно ДНФ и КНФ.

Приведение формулы к КНФ производится аналогично при­ведению ее к ДНФ, только вместо п. 3 применяется п. 3':

3'. Используя закон дистрибутивности φ ∨ (ψ ∧ χ)≡ (φ ∨ ψ)∧ (φ ∨ χ), преобразуем формулу так, чтобы все дизъюнкции выполнялись раньше, чем конъюнкции.

Пример 11. Привести к КНФ формулу φ (x→ y)∧ ((y→ z)→ x).

Решение. Преобразуем формулу φ к формуле, не содержащей →: φ ≡ (x∨ y)∧ ((y∨ z)∨ x). В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания: φ ≡ (x∨ y)∧ ((y∧ z)∨ x)≡ (x∨ y)∧ ((y∧ z)∨ x). Используя закон дистрибутивности, приводим формулу к КНФ φ ≡ (x∨ y)∧ (x∨ y)∧ (x∨ z). Упростим полученную формулу: (x∨ y)∧ (x∨ y)∧ (x∨ z)≡ (1)(x∨ (y∧ y))∧ (x∨ z)≡ (2)x∧ (x∨ z)≡ ≡ (3)x (для преобразования (1) использовался закон дистрибутивности, для (2) – эквивалентность 1 утверждения 1, для (3) — закон поглоще­ния). Таким образом, формула φ эквивалентными преобразованиями приводится к формуле x, являющейся одновременно ДНФ и КНФ.

 

2.1.5. Совершенные дизъюнктивные и конъюнктивные

нормальные формы

 

Пусть (х₁,..., х_n) — набор логических переменных, Δ =(δ ₁, …, δ _n) — набор нулей и единиц. Конституентой единицы набора Δ называется конъюнкт К¹(δ ₁, …, δ _n)=x₁^{δ 1}∧ x₂^{δ 2}∧ …∧ x_n^{δ n}. Конституентой нуля набора Δ называется дизъюнкт К⁰(δ ₁, …, δ _n)=x₁^{1-δ 1}∨ x₂^{1-δ 2}∨ …∨ x_n^{1-δ n}.

Отметим, что K¹(δ ₁, δ ₂, …, δ _n)=1 (K⁰(δ ₁, δ ₂, …, δ _n)=0) тогда и только тогда, когда x₁=δ ₁, x₂=δ ₂, …, x_n=δ _n.

Совершенной ДНФ называется дизъюнкция некоторых конституент единицы, среди которых нет одинаковых, совершенной КНФ называется конъюнкция некоторых конституент нуля, среди которых нет одинаковых. Таким образом, СДНФ (СКНФ) есть ДНФ (КНФ), в которой в каждый конъюнкт (дизъюнкт) каждая переменная х_i из набора {х₁,..., х_п} входит ровно один раз, причем входит либо сама х_i, либо ее отрицание x_i.

Пример 12. Формула x₁∧ x₂∧ x₃ есть конституента единицы K¹(1, 0, 1), формула x∨ y∨ z есть конституента нуля K⁰(0, 0, 1), формула (x₁∧ x₂)∨ (x₁∧ x₂) – СДНФ, формула (x∨ y∨ z)∧ (x∨ y∨ z)∧ (x∨ y∨ z) – СКНФ, а формула (x₁∧ x₂∧ x₃)∨ (x₁∧ x₂∧ x₃)∨ (x₁∧ x₂∧ x₃) не является СДНФ.

Теорема 3. Для любой не тождественно ложной (не тождественно истинной) формулы φ АВ существует единственая СДНФ (СКНФ) ψ АВ такая, что φ ≡ ψ;.

Заметим, что единственность формулы в формулировке теоремы понимается с точностью до порядка следования конъюнктивных сомножителей и дизъюнктивных слагаемых в этой формуле.

Опишем алгоритм приведения формулы к СДНФ.

1. Приводим данную формулу к ДНФ.

2. Преобразовываем ее конъюнкты в конституенты единицы с помощью следующих действий:

а) если в конъюнкт входит некоторая переменная вместе со своим отрицанием, то мы удаляем этот конъюнкт из ДНФ;

б) если в конъюнкт одна и та же литера x^δ входит несколько раз, то удаляем все литеры х^δ , кроме одной;

в) если в конъюнкт x₁^{δ 1}∧ …∧ x_k^{δ k} не входит переменная у, то этот конъюнкт заменяем на эквивалентную формулу (x₁^{δ 1}∧ …∧ x_k^{δ k}∧ y)∨ (x₁^{δ 1}∧ …∧ x_k^{δ k}∧ y);

г) если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставляем только одну из них.

В результате получается СДНФ.

Пример 13. Найти СДНФ для ДНФ φ (x∧ x)∨ x∨ (y∧ z∧ y).

Решение. Имеем φ ≡ x∨ (y∧ z)≡ (x∧ y)∨ (x∧ y)∨ (x∧ y∧ z)∨ (x∧ y∧ z)≡

≡ (x∧ y∧ z)∨ (x∧ y∧ z)∨ (x∧ y∧ z)∨ (x∧ y∧ z)∨ (x∧ y∧ z)∨ (x∧ y∧ z)≡

≡ (x∧ y∧ z)∨ (x∧ y∧ z)∨ (x∧ y∧ z)∨ (x∧ y∧ z)∨ (x∧ y∧ z).

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