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

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

Теорема 1 (о дедукции). Пусть φ₁,…,φ_m,φ,ψ – формулы ИВ. Тогда φ₁,…,φ_m,φ⊢ψ φ₁,…,φ_m,⊢φ→ψ.

Пример 4. Покажем, что φ→ψ⊢¬ψ→¬φ;

Решение. По теореме о дедукции

φ→ψ⊢¬ψ→¬φ φ→ψ, ¬ψ⊢¬φ.

Строим вывод формулы ¬φ из формул φ→ψ,¬ψ:

1) φ→ψ (гипотеза);

2) ¬ψ (гипотеза);

Пример 5. Покажем, чтоφ→(ψ→χ)⊢ψ→(φ→χ)

Решение.По теореме о дедукции

φ→(ψ→χ)⊢ψ→(φ→χ)φ→(ψ→χ),ψ⊢(φ→χ)φ→(ψ→χ),ψ,φ⊢χ.

Строим вывод формулы χ из формул φ→(ψ→χ),ψ,φ:

1) φ→(ψ→χ) (гипотеза);

2) φ (гипотеза);

3) ψ (гипотеза);

4) ψ→χ (к пп. 2 и 1 применили правило вывода);

5) χ (к пп. 3 и 4 применили правило вывода).