Математическая логика и теория алгоритмов. Галуев Г.А. - 13 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 13 из 64
© 2003 Галуев Геннадий Анатольевич
Доказательство.
Пусть В
1
,…,В
n
есть вывод из Г ∪ {А} (множество содержащее элементы из Г и
формулу А), где В
n
есть В.
Индукцией по i докажем, что Г├А→В
i
, i=1,…,n.
Рассмотрим случай i=1. Формула В
1
должна быть либо элементом Г, либо аксио-
мой теории L, либо совпадать с А. По схеме аксиом АК1 формула В
1
→(А→В
1
) есть ак-
сиома. Поэтому в первых двух случаях Г├А→В
1
по правилу МР
В
1
, В
1
→(А→В
1
)
А→В
1
В третьем случае, когда В
1
есть А, в соответствии с (***) (т.е. ├А→А) имеем
├А→В
1
и поэтому Г├А→В
1
. Тем самым базис индукции при i=1 доказан.
Делаем теперь индуктивное предположение: Г├А→В
к
для любого к<i и попыта-
емся доказать, что тогда и Г├А→В
i
. Для В
i
имеем следующие 4 возможности: 1. В
i
есть
аксиома.
2. В
i
∈Г. 3. Вi есть А. 4. В
i
следует по правилу МР из некоторых В
j
и В
m
(j<i, m<i) и В
m
имеет вид В
j
→B
i
.
В первых трёх случаях Г├А→В
i
доказывается также как и для случая i=1. В по-
следнем четвёртом случае применим индуктивное предположение, согласно которому
Г├А→В
j
и Г├А→В
m
, т.е. Г├А→(В
j
→B
i
). Подставляя в схему аксиом АК2 В
j
вместо В и В
i
вместо С имеем: ├(А→(В
j
→B
i
))→((A→B
j
)→(A→B
i
)). Следовательно, по правилу МР по-
лучаем из второго индуктивного предположения (Г├А→В
m
или Г├А→В
j
→B
i
т.к. В
m
есть
В
j
→B
i
).
Г├(А→В
j
)→(A→B
i
), откуда из первого индуктивного предположения (А→В
j
) по
правилу МР имеем Г├А→В
i
.
Таким образом доказано, что для любого i справедливо Г├А→В
i
, откуда при i=n
получаем требуемое утверждение.
Следствие. Если А├В, то ├А→В.
Теорема о дедукции позволяет облегчить процедуры доказательств. Например,
докажем для любых А, В, С справедливость (****) А→В, В→С├
L
А→С.
1. А (гипотеза)
2. А→В (гипотеза)
3. В (по правилам МР из 1 и 2)
4. В→С (гипотеза)
5. С (по правилам МР из 3 и 4, когда А есть В и В есть С).
Следовательно А→В, В→С, А├С, откуда по теореме о дедукции А→В, В→С
├А→С.
Приведём ещё один пример. Докажем, что А→(В→С), В├А→С (*****)
1. А (гипотеза
2. А→(В→С) (гипотеза)
3. В→С (по правилу МР из 1 и 2 где А есть А и В есть В→С)
4. В (гипотеза)
5. С (по правилу МР из 4 и 3
где А есть В и В есть С)
Следовательно А→(В→С), А, В├С, откуда по теореме о дедукции А→(В→С),
В├А→С.
Докажем два важных для исчисления высказываний утверждения.
Утверждение 1.
Если Г, А├В и Г, А├⎤В, то Г├⎤А. Это утверждение называют «Reductio ad
absurdum» -
приведение к абсурду.
Доказательство.
1. Г├А→В (по теореме о дедукции)
2. Г├А→⎤В (по теореме о дедукции)
3. (⎤⎤А→⎤⎤В)→((⎤⎤А→⎤В)→⎤А) (из схемы АК3 с ⎤А вместо В и ⎤В вместо А)
Теперь, если доказать выводимость ⎤⎤А→⎤⎤В и ⎤⎤А→⎤В
из А→В и А→⎤В, то восполь-
зовавшись дважды правилом МР, из 3 можно вывести ⎤А. Покажем, что А→В├⎤⎤А→⎤⎤В.
Для этого сначала убедимся, что ⎤⎤А→А.
(1)

Страницы