Методы доказательств.

Существует 2 метода доказательств: прямое и косвенное: рассмотрим схему прямого доказательства.

Есть n посылок, в самом общем случае посылки могут себя дополнить. В общем случае на основании n посылок нам надо доказать φ.

Методы доказательства:

1. записываем n посылок φ ₁, φ ₂, φ ₃ … φ _n,

2. все посылки тождественно истины.

3. в качестве n+1 строки записываем новое утверждение с применением рассмотренных правил {ПО, ПРК, ВД, УД, ВК, УК, ВЭ, УЭ, ТД}

правила АПР-1:

Либо записываем вспомогательное утверждение ранее записанное и доказываем в истинность.

Доказательство считается законченным, если в какой-то строке n+k мы получаем непосредственное выражение φ.

Пример:

(p→ q)→ [(q→ r)→ (p→ r)]

φ ₁ φ ₂ φ ₃

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

1. p→ q φ ₁

2. q→ r φ ₂

3. p φ ₃

4. q {ПО: 1, 3}

5. r {ПО: 2, 4}

Рассмотрим схему обратного доказательства.

рассмотрим схему 1:

φ ₁→ (φ ₂→ (φ ₃→ …→ (φ _n-1→ (φ _n→ r)))).

По схеме обратного доказательства в качестве n строк записываем исходных посылок и в качестве n+1 строке записываем отрицание того, что следует получить, в данном случае. Далее начиная с (n+2) строки записываем новое утверждение с применением { ПО, ПРК, ВД, УД, ВК, УК, ВЭ, УЭ, ТД }

Доказательство считается законченным, если получены 2 противоречащих строки.

Пример:

(p→ q)< => (q→ p) – доказать

(p→ q)~(q→ p) – разбив на 2

a) (p→ q)→ (q→ p), т.е. φ ₁→ (φ ₂→ φ)

b) (p→ q)← (q→ p)

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

а) 1. p→ q

2. q

3. р – {введение косвенного допущения}

4. q {ПО: 1, 3}

противоречие {2 и 4}.