Xφ≡X(φ)xφ≡X(φ)

5. используя закон дистрибутивности

φ∧(ψ∨χ)≡(φ∧ψ)∨(φ∧χ),

преобразуем формулу ψ к дизъюнктивной нормальной форме.

Пример 10. Формулу χxyφ(x,y)→xyψ(x,y) привести к ПНФ, считая формулы φ и ψ атомарными.

Решение. Избавившись от импликации, получаем

χ≡¬(xyφ(x,y))∨xyψ(x,y).

Переносим отрицание к атомарной подформуле φ(x,y):

χ≡xy¬φ(x,y)∨xyψ(x,y).

Так как в формуле xyψ(x,y) переменные х, у являются связанными, то по пп. 2΄, 3΄ утверждения 2 имеем

χ≡xy(¬φ(x,y)∨xyψ(x,y)).

Пусть u, v ‑ некоторые новые переменные. Тогда по пп. 4, 4΄ утверждения 2 получаем

χ≡xy(¬φ(x,y)∨uv ψ(u,v)),

откуда по по пп. 2΄, 3΄ утверждения 2

χ≡xyuv(¬φ(x,y)∨ψ(u,v)).

Формула ¬φ(x,y)∨ψ(u,v) является дизъюнктивной нормальной формой, а значит, формула xyuv(¬φ(x,y)∨ψ(u,v)) является ПНФ.