Свойства выводимых и эквивалентных формул исчисления высказываний
Утверждение 3. Пусть φ, ψ, χ – формулы ИВ. Тогда 1) ⊢ φ → φ; 2) φ ∧ ψ ⊢ φ; 3) φ ∧ ψ ⊢ ψ; 4) φ, ψ ⊢ φ 5) φ → ψ, ψ → χ ⊢ φ → χ (свойство транзитивности); 6) φ → (ψ → χ)≡ ψ → (φ → χ) (свойство перестановочности посылок); 7) φ → (ψ → χ)≡ φ ∧ ψ → χ (свойство соединения и разъединения посылок); 8) φ → ψ ≡ ψ → φ (свойство контрапозиции). Доказательство. Пункты 1, 4, 6, 8 доказаны в примерах 13, 14, 16, 17. Докажем пункт 7.Покажем, что φ → (ψ → χ) ⊢ φ φ → (ψ → χ) ⊢ φ Строим вывод формулы χ из формул φ → (ψ → χ), φ 1) φ → (ψ → χ) (гипотеза); 2) φ 3) φ 4) φ (к пп. 2 и 4 применили правило вывода); 5) φ 6) ψ (к пп. 2 и 5 применили правило вывода); 7) ψ → χ (к пп. 4 и 1 применили правило вывода); 8) χ (к пп. 6 и 7 применили правило вывода). Покажем, что φ φ Строим квазивывод формулы χ из формул φ 1) φ 2) φ (гипотеза); 3) ψ (гипотеза); 4) φ 5) χ (к пп. 4 и 1 применили правило вывода).
Основные эквивалентности исчисления
|
ψ;
φ → (ψ → χ), φ 
