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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

1.B (гип.2) 1
0
. B ⇒ (A ⇒ B) (акс.1).
2
0
. B (гип.2).
3
0
. A ⇒ B (MP,2
0
,3
0
).
2.A (гип.3) 4
0
. . . . 5 шагов вывода A ⇒ A.
. . .
8
0
. A ⇒ A
3. A ⇒ (B ⇒ C) 9
0
. (A ⇒ (B ⇒ C)) ⇒ (A ⇒ (A ⇒ (B ⇒ C))) (акс.1).
(гип.1) 10
0
. A ⇒ (B ⇒ C) (гип.1).
11
0
. A ⇒ (A ⇒ (B ⇒ C)) (MP,2
0
,3
0
).
4. B ⇒ C 12
0
. . . . эти шаги необязательны,
(MP,2,3) 13
0
. . . . т.к. 14
0
совп. с гип.1.
14
0
. A ⇒ (B ⇒ C)
5.C (MP,1,4) 15
0
. (A ⇒ (B ⇒ C)) ⇒ ((A ⇒ B) ⇒ (A ⇒ C)) (акс.2).
16
0
. (A ⇒ B) ⇒ (A ⇒ C) (MP,14
0
,15
0
).
17
0
. A ⇒ C (MP,3
0
,16
0
).
Пользуясь теоремой дедукции, можно сразу без проведенного вы-
ше громоздкого построения вывода из A ⇒ (B ⇒ C), B, A ` C заклю-
чить о выводимости A ⇒ (B ⇒ C), B ` A ⇒ C.
Заметим, что, применяя теорему дедукции еще раз, мы получим
A ⇒ (B ⇒ C) ` B ⇒ (A ⇒ C) (правило перестановки посылок).
Пример 6. Докажем правило контрапозиции: A ⇒ B `
` ¬B ⇒ ¬A. Согласно теореме дедукции, для этого достаточно по-
строить вывод A ⇒ B, ¬B ` ¬A:
1. ¬B (гипотеза 2).
2. ¬B ⇒ (A ⇒ ¬B) (аксиома 1).
3. A ⇒ ¬B (MP, 1, 2).
4. A ⇒ B (гипотеза 1).
5. (A ⇒ B) ⇒ ((A ⇒ ¬B) ⇒ ¬A) (аксиома 9).
6. (A ⇒ ¬B) ⇒ ¬A (MP, 4, 5).
7. ¬A (MP, 3, 6).
Упражнение 2. Постройте полный вывод правила контрапозиции аналогично
примеру 5, пользуясь конструкциями из доказательства теоремы дедукции.
42

Страницы