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

Свойства выводимых и эквивалентных формул исчисления высказываний

Утверждение 3. Пусть φ,ψ, χ – формулы ИВ. Тогда

  1. ⊢φ→φ;

  2. φ∧ψ⊢φ;

  3. φ∧ψ⊢ψ;

  4. φ,ψ⊢φψ;

  5. φ→ψ, ψ→χ⊢φ→χ (свойство транзитивности);

  6. φ→(ψ→χ)≡ψ→(φ→χ) (свойство перестановочности посылок);

  7. φ→(ψ→χ)≡φ∧ψ→χ (свойство соединения и разъединения посылок);

  8. φ→ψ≡¬ψ→¬φ (свойство контрапозиции).

Доказательство. Пункты 1, 4, 6, 8 доказаны в примерах 13, 14, 16, 17.

Докажем пункт 7. Покажем, что φ→(ψ→χ)⊢φψ→χ. По теореме о дедукции

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

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

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

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

  3. φψ→φ (схема аксиом 3);

  4. φ (к пп. 2 и 4 применили правило вывода);

  5. φψ→ψ (схема аксиом 4);

  6. ψ (к пп. 2 и 5 применили правило вывода);

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

  8. χ (к пп. 6 и 7 применили правило вывода).

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

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

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

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

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

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

  4. φψ (к п.п. 2 и 3 применили свойство 4);

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

      1.