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

Если х — логическая переменная, δ{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, являющейся одновременно ДНФ и КНФ.