практикум по мат

Теорема о замене в исчисления высказываний

Формулы φ и ψ назовем эквивалентными (обозначим φ≡ψ), если

φ⊢ψ и ψ⊢φ.

Замечание 2. Для любых формул φ и ψ ИВ

φ≡ψ⊢φ→ψ и ⊢ ψ→φ.

Утверждение 1. Отношение ≡ является отношением эквивалентности на множестве формул ИВ, т.е. для любых формул φ, ψ, χ ИВ:

а) φ≡φ;

b) φ≡ψψ≡φ;

с) φ≡ψ, ψ≡xφ≡x.

Утверждение 2. Для любых формул φ, ψ, φ₁, ψ₁, φ₂, ψ₂ ИВ таких, что φ₁≡ψ₁ и φ₂≡ψ₂, имеют место эквивалентности:

φ₁∧φ₂≡ψ₁∧ψ₂, φ₁∨φ₂≡ψ₁∨ψ₂, φ₁→φ₂≡ψ₁→ψ₂, ¬φ₁≡¬ψ₁.

Теорема 2 (о замене). Пусть φ ‑ формула ИВ, ψ ‑ ее подформула, φ' получается из φ заменой некоторого вхождения ψ на формулу ψ' ИВ и ψ≡ψ'. Тогда φ≡φ'.

Содержание