Элементы математической логики. Фролов И.С. - 47 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

1
0
. A ⇒ C (гипотеза 1).
2
0
. B ⇒ C (гипотеза 2).
3
0
. A ∨ B (гипотеза 3).
4
0
. (A ⇒ C) ⇒ ((B ⇒ C) ⇒ (A ∨ B ⇒ C)) (аксиома 8).
5
0
. (B ⇒ C) ⇒ (A ∨ B ⇒ C) (MP, 1
0
,4
0
).
6
0
. A ∨ B ⇒ C (MP, 2
0
,5
0
).
7
0
. C (MP, 3
0
,6
0
).
Совершенно аналогично доказывается введение ¬ (правило при-
ведения к абсурду):
1. Γ, A ` B (гипотеза 1).
2. Γ, A ` ¬B (гипотеза 2).
3. Γ ` A ⇒ B (введ.⇒, 1).
4. Γ ` A ⇒ ¬B (введ.⇒, 2).
5. A ⇒ B, A ⇒ ¬B ` ¬A (по аксиоме 9).
6. Γ ` ¬A (транзитивность, 3,4,5).
Докажем удаление ¬ (правило противоречия):
1. A, ¬A, ¬B ` A (рефлексивность).
2. A, ¬A, ¬B ` ¬A (рефлексивность).
3. A, ¬A ` ¬¬B (прив. к абсурду, 1, 2).
4. ¬¬B ` B (удал.¬¬).
5. A, ¬A ` B (транзитивность, 3, 4).
В дальнейшем выводы, аналогичные последнему, будем записы-
вать в более компактной форме:
A, ¬A, ¬B ` A
A, ¬A, ¬B ` ¬A
¾
A, ¬A ` ¬¬B ` B.
Пример 1. Докажем секвенцию A ∨ B ` ¬A ⇒ B:
1. A, ¬A ` B (удал.¬).
2. A ` ¬A ⇒ B (введ.⇒).
3. B, ¬A ` B (рефлексивность).
4. B ` ¬A ⇒ B (введ.⇒, 3).
5. A ∨ B ` ¬A ⇒ B (разбор случаев, 2, 4).
3. Полнота исчисления высказываний
При доказательстве теоремы о полноте исчисления высказываний
нам потребуется ряд лемм.
46

Страницы