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).

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