Если х — логическая переменная, δ {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. Совершенные дизъюнктивные и конъюнктивные
нормальные формы
Пусть (х1,..., хn) — набор логических переменных, Δ=(δ1,…,δn) — набор нулей и единиц. Конституентой единицы набора Δ называется конъюнкт К1(δ1,…,δn)=x1δ1∧x2δ2∧…∧xnδn. Конституентой нуля набора Δ называется дизъюнкт К0(δ1,…,δn)=x11-δ1∨x21-δ2∨…∨xn1-δn.
Отметим, что K1(δ1,δ2,…,δn)=1 (K0(δ1,δ2,…,δn)=0) тогда и только тогда, когда x1=δ1, x2=δ2,…, xn=δn.
Совершенной ДНФ называется дизъюнкция некоторых конституент единицы, среди которых нет одинаковых, совершенной КНФ называется конъюнкция некоторых конституент нуля, среди которых нет одинаковых. Таким образом, СДНФ (СКНФ) есть ДНФ (КНФ), в которой в каждый конъюнкт (дизъюнкт) каждая переменная хi из набора {х1,...,хп} входит ровно один раз, причем входит либо сама хi, либо ее отрицание ¬xi.
Пример 12. Формула x1∧¬x2∧x3 есть конституента единицы K1(1,0,1), формула x∨y∨¬z есть конституента нуля K0(0,0,1), формула (x1∧¬x2)∨(¬x1∧x2) – СДНФ, формула (x∨y∨¬z)∧(¬x∨¬y∨z)∧(¬x∨y∨z) – СКНФ, а формула (x1∧¬x2∧x3)∨(¬x1∧x2∧x3)∨(x1∧¬x2∧x3) не является СДНФ.
Теорема 3. Для любой не тождественно ложной (не тождественно истинной) формулы φ АВ существует единственая СДНФ (СКНФ) ψ АВ такая, что φ≡ψ.
Заметим, что единственность формулы в формулировке теоремы понимается с точностью до порядка следования конъюнктивных сомножителей и дизъюнктивных слагаемых в этой формуле.
Опишем алгоритм приведения формулы к СДНФ.
1. Приводим данную формулу к ДНФ.
2. Преобразовываем ее конъюнкты в конституенты единицы с помощью следующих действий:
а) если в конъюнкт входит некоторая переменная вместе со своим отрицанием, то мы удаляем этот конъюнкт из ДНФ;
б) если в конъюнкт одна и та же литера xδ входит несколько раз, то удаляем все литеры хδ, кроме одной;
в) если в конъюнкт x1δ1∧…∧xkδk не входит переменная у, то этот конъюнкт заменяем на эквивалентную формулу (x1δ1∧…∧xkδk∧y)∨(x1δ1∧…∧xkδ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).
Описание алгоритма приведения формулы к СКНФ аналогично вышеизложенному описанию алгоритма приведения формулы к СДНФ и оставляется читателю в качестве упражнения.