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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

Свойство 1) означает, что A
1
, . . . , A
n
` A
i
(1 6 i 6 n), что,
очевидно, верно.
Далее, 2) означает, что можно добавить к списку гипотез совер-
шенно произвольные формулы. Вывод при этом останется прежним,
просто новые гипотезы в нем не будут участвовать.
Транзитивность доказывается реконструкцией выводов. В выводе
B из списка гипотез ∆: B
1
, B
2
, . . . , B
m
(= B) содержатся аксиомы, ги-
потезы A
i
∈ ∆ и формулы, полученные по правилу MP. Заменим в нем
гипотезы A
i
на их вывод из Γ, т.е. вместо B
1
, . . . , A
i
, . . . , B
m
запишем
B
1
, . . . , A
1i
, . . . , A
ki
(= A
i
)
| {z }
A
i
Γ
, . . . , B
m
(= B), в результате построим вывод B
из Γ.
Теорема 3. Если Γ ` A ⇒ B, то Γ, A ` B.
Пусть C
1
, . . . , C
m
(= (A ⇒ B) ) — вывод из Γ. Добавим к нему еще
два шага вывода:
1. C
1
.
.
.
.
.
.
m. A ⇒ B
m+1. A (гипотеза)
m+2. B (MP, m+1, m)
В результате мы построили требуемый вывод.
В качестве следствия получаем, что если ` A ⇒ B, то A ` B.
Пример 4. Покажем, что A, B, A ⇒ (B ⇒ C) ` C. Согласно
теореме 2(1), A ⇒ (B ⇒ C) ` A ⇒ (B ⇒ C). Применим теорему 3:
A ⇒ (B ⇒ C), A ` B ⇒ C; еще раз: A ⇒ (B ⇒ C), A, B ` C.
Упражнение 1. Постройте вывод непосредственно, не обращаясь к теоремам
2 и 3.
3. Теорема дедукции
Утверждение теоремы 3 допускает обращение, которое дает хо-
рошо известный метод рассуждения: «Чтобы установить импликацию
A ⇒ B, введем допущение A и докажем B».
Теорема 4. Если Γ, A ` B, то Γ ` A ⇒ B.
Пусть B
1
, . . . , B
n
(= B) — вывод B из Γ ∪ {A}. Построим вы-
вод A ⇒ B из Γ. Таким выводом была бы последовательность A ⇒
B
1
, . . . , A ⇒ B
n
, но каждую формулу A ⇒ B
i
нужно еще вывести.
Построим выводы формул A ⇒ B
i
(1 6 i 6 n) индукцией по i.
40

Страницы