Реферат: Логика высказываний

5) Правило введения эквивалентности:

?? φ→ ψ

6)Правило удаления эквивалентности:

УЭ ,

Прямое доказательство выражения φ₁ →(φ₂ →( φ₃ → …(φ_п-1 →φ_п )…) строится следующим образом:

1. В первых n-1 строках выписываются последовательно выражения φ₁ , φ₂ ,… φ_п-1 в качестве условий теоремы.

2. К доказательству можно присоединить:

a) ранее доказанные теоремы в качестве новых строк;

b) новые строки на основании уже имеющихся строк по правилам ПО, ВК, УК, ВД, УД, ВЭ, УЭ.

1. Доказательство закончено, если его последняя строка есть выражение φ_п. Последняя строка доказательства не нумеруется; тем самым отмечается, что доказательство закончено.

Косвенное доказательство выражения φ₁ →(φ₂ →( φ₃ → …(φ_п-1 →φ_п )…) строится следующим образом:

1. а) В первых n-1 строках выписываются последовательно выражения φ₁ , φ₂ ,… φ_п-1 в качестве условий теоремы.

b) В n-ой строке выписывается выражение`φ_п в качестве допущения косвенного доказательства.

2. К доказательству можно присоединить:

a) ранее доказанные теоремы в качестве новых строк;

b) новые строки на основании уже имеющихся строк по правилам ПО, ВК, УК, ВД, УД, ВЭ, УЭ.

3. Доказательство закончено, если в нем имеются две противоречащие строки. Окончание доказательства отмечается написанием в последней ненумерованной строке выражения «ПРТВРЧ» (сокращение слова «противоречие») с указанием справа номеров двух противоречащих строк.

Продемонстрируем приемы доказательства на ряде примеров. Их мы будем нумеровать с указанием слева Т_і ( теорема номері )

Т₁ (Закон гипотетического силлогизма)

(p→q)→(( q → r)→( p→ r))

Доказательство:

1) p→q

2) q → r íДопущенияý

3) р

4) q íПО : 1,3ý

r íПО : 2,4ý

Т₂ (Закон контрапозиции)

(`p→q)→( `q →р) (30)

1) `p→q íДопущенияý

2) `q