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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

I. Пусть i = 1. Формула B
1
— либо аксиома, либо принадлежит Γ,
либо совпадает с A.
Если B
1
— аксиома, то цепочка B
1
, B
1
⇒ (A ⇒ B
1
), A ⇒ B
1
является нужным выводом.
Если B
1
∈ Γ, вывод такой же, как в предыдущем случае.
Если B
1
= A, необходимый вывод формулы A ⇒ A можно взять
из примера 3.
II. Пусть построены цепочки выводов
. . . , A ⇒ B
1
; . . . ; . . . , A ⇒ B
i−1
(i > 1).
Построим вывод формулы A ⇒ B
i
. Проведем и здесь анализ случаев.
Возможны четыре случая: формула B
i
— либо аксиома, либо принадле-
жит Γ, либо совпадает с A, либо непосредственно выводится по прави-
лу MP из формул, предшествующих ей в исходном выводе. Первые три
случая совершенно аналогичны случаям, разобранным выше, а четвер-
тый необходимо рассмотреть отдельно.
Пусть B
i
получается применением правила MP к формулам B
j
и B
k
(j, k < i), причем B
k
имеет вид B
j
⇒ B
i
. По предполо-
жению индукции, уже имеются выводы из Γ формул A ⇒ B
j
и
A ⇒ (B
j
⇒ B
i
). Искомая цепочка теперь строится так:
(A ⇒ (B
j
⇒ B
i
)) ⇒ ((A ⇒ B
j
) ⇒ (A ⇒ B
i
)) (аксиома 2).
(A ⇒ B
j
) ⇒ (A ⇒ B
i
) (MP).
A ⇒ B
i
(MP).
Таким образом, существует вывод
. . . , A ⇒ B
1
, . . . , A ⇒ B
i
, . . . , A ⇒ B.
Пример 5. Имеем A ⇒ (B ⇒ C), B, A ` C. Построим вывод
для A ⇒ (B ⇒ C), B ` A ⇒ C.
41

Страницы