Математическая логика и теория алгоритмов. Сергиевская И.М. - 14 стр.

UptoLike

ВУЗ: 

ПГУТИ | Самара

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

Рубрика: 

19
Доказательство. Построим вывод формулы
A
A
→ .
1.
()
AAA →→ . А1 с подстановкой вместо
B
–
A
.
2.
()()
AAAA →→→ . А1 с подстановкой вместо
B
–
A
A
→ .
3.
()()()
(
)()
(
)()
AAAAAAAAA →→→→→→→→
А2 с подстановкой вместо
C
–
A
, а вместо
B
–
A
A
→ .
4.
()()
(
)
AAAAA →→→→ . МР 2,3.
5.
A
A
→ . МР 1,4.
Что и требовалось доказать.
Теорема дедукции. Пусть
Γ
– множество формул,
A
,
B
– формулы. Тогда
Γ
,
A
├
B
⇒
Γ
├
B
A
→ .
В частности, если
∅=
Γ
, то если
A
├
B
⇒
├
B
A
→ .
Доказательство. Пусть
1
B
,
2
B
, …,
BB
n
=
, – вывод из
Γ
и
A
. Методом
математической индукции докажем, что
Γ
├
i
BA → , ni ,...,2,1
=
.
1)
Проверим, что утверждение
Γ
├
i
BA → справедливо при 1
=
i , то есть
Γ
├
1
BA → .
Для
1
B возможны три варианта:
Γ
∈
1
B ,
1
B – аксиома, AB =
1
.
а) Пусть
Γ
∈
1
B или
1
B – аксиома. Построим вывод:
1.
1
B .
2.
()
11
BAB →→
. А1 с подстановкой вместо
A
–
1
B
, вместо
B
–
A
.
3.
1
BA → . МР 1, 2.
Таким образом,
Γ
├
1
BA → .
б) Пусть AB
=
1
. По лемме, ├
=
→
A
A
1
BA → . Таким образом,
Γ
├
1
BA → .
2)
Пусть утверждение
Γ
├
i
BA → верно при
i ,...,2,1
=
, n
k
≤ . Докажем
утверждение для 1
+=
k
i , то есть
Γ
├
1+
→
k
BA .
Для формулы
1+k
B есть следующие возможности:
Γ
∈
+1k
B ,
1+k
B – аксиома,
AB
k
=
+1
, которые рассматриваются аналогично предыдущему пункту, и новая
возможность:
1+k
B получается из предыдущих формул
1
B ,
2
B , …,
k
B , по правилу
Modus ponens. Последний случай рассмотрим подробно.
Среди формул
1
B
,
2
B
, …,
k
B
есть формулы (может быть, и не одна) вида
j
B ,
k
j
≤≤1, такие, что имеет место формула
1+
→
kj
BB (которая также присутствует в
выводе), поэтому и возможно применение правила Modus ponens.
По предположению индукции,
Γ
├
j
BA → ,
Γ
├
(
)
1+
→→
kj
BBA .
Построим вывод:
1.
j
BA → .
2.
(
)
1+
→→
kj
BBA .
3.
(
)
(
)
(
)
(
)
(
)
11 ++
→→→→→→
kjkj
BABABBA . А2 с подстановкой вместо
B
–
j
B , вместо
C
–
1+k
B .
4.
(
)
()
1+
→→→
kj
BABA . МР 2, 3. 
          Доказательство. Построим вывод формулы A → A .
1.   A → ( A → A) .               А1 с подстановкой вместо B – A .
2.   A → (( A → A) → A) . А1 с подстановкой вместо B – A → A .
3.   ( A → (( A → A) → A)) → (( A → ( A → A)) → ( A → A))
            А2 с подстановкой вместо C – A , а вместо B – A → A .
4.   (( A → A) → A) → ( A → A).                           МР 2,3.
5.   A → A.                                               МР 1,4.
          Что и требовалось доказать.

       Теорема дедукции. Пусть Γ – множество формул, A , B – формулы. Тогда
Γ , A├ B ⇒ Γ ├ A → B.
       В частности, если Γ = ∅ , то если A ├ B ⇒ ├ A → B .
       Доказательство. Пусть B1 , B2 , …, Bn = B , – вывод из Γ и A . Методом
математической индукции докажем, что Γ ├ A → Bi , i = 1,2,..., n .
       1) Проверим, что утверждение Γ ├ A → Bi справедливо при i = 1 , то есть
Γ ├ A → B1 .
       Для B1 возможны три варианта: B1 ∈ Γ , B1 – аксиома, B1 = A .
       а) Пусть B1 ∈ Γ или B1 – аксиома. Построим вывод:
1. B1 .
2. B1 → ( A → B1 ) . А1 с подстановкой вместо A – B1 , вместо B – A .
3. A → B1 .                                              МР 1, 2.
       Таким образом, Γ ├ A → B1 .
       б) Пусть B1 = A . По лемме, ├ A → A = A → B1 . Таким образом, Γ ├ A → B1 .
       2) Пусть утверждение Γ ├ A → Bi верно при i = 1,2,..., k , k ≤ n . Докажем
утверждение для i = k + 1 , то есть Γ ├ A → Bk +1 .
       Для формулы Bk +1 есть следующие возможности: Bk +1 ∈ Γ , Bk +1 – аксиома,
Bk +1 = A , которые рассматриваются аналогично предыдущему пункту, и новая
возможность: Bk +1 получается из предыдущих формул B1 , B2 , …, Bk , по правилу
Modus ponens. Последний случай рассмотрим подробно.
       Среди формул B1 , B2 , …, Bk есть формулы (может быть, и не одна) вида B j ,
1 ≤ j ≤ k , такие, что имеет место формула B j → Bk +1 (которая также присутствует в
выводе), поэтому и возможно применение правила Modus ponens.
       По предположению индукции, Γ ├ A → B j , Γ ├ A → (B j → Bk +1 ) .
       Построим вывод:
1. A → B j .
2. A → (B j → Bk +1 ) .
3. (A → (B j → Bk +1 )) → ((A → B j ) → ( A → Bk +1 )).   А2 с подстановкой вместо B –
     B j , вместо C – Bk +1 .
4. (A → B j ) → ( A → Bk +1 ) .                             МР 2, 3.



                                                19

Страницы