![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
I. .Это правило следует из того простого рассуждения, что если мы можем получить формулу A из совокупности Н, то из расширенной совокупности Н, W мы тем более получим формулу А.
II. Это почти очевидное правило мы, тем не менее, докажем. Так как по условию из совокупности формул Н, С выводима формула А, то существует вывод из Н, С, последней формулой которого является А:
(1)
Так как по условию из совокупности формул Н выводима формула С, то существует вывод из Н, последней формулой которого является С:
(2)
Если в выводе (1) отсутствует формула С, то он является выводом
только из совокупности Н и, значит, А выводима из H.
Если же в выводе (1) одна из формул есть формула С, например формула , то, вставив между формулами
и
вывод формулы (2), являющейся выводом из Н, в результате получим вывод из Н, С
(3)
Так как в вывод (3) входит вывод (2) из Н, а в оставшуюся часть вывода
(4)
Формула С не входит, то вывод (4) является выводом только из Н.
На основании же свойства 2 вывода вывод (3) тоже будет выводом только из Н. Поэтому и в этом случае формула А выводима из Н, что и требовалось доказать.
Ш.
Доказательство. Так как , то по правилу I имеем
Так как
то также по правилу I имеем
.
Используя теперь правило II, получаем
Для правил выводимости II и III можно предложить более простые и компактные доказательства. Докажем правило II, воспользовавшись следующими соображениями. Запись означает, что для того, чтобы вывести С, нужно иметь совокупность формул Н. Значит, в записи
одну формулу С можно заменить на совокупность формул Н, поэтому можно записать:
. Но дважды используемое одно и то же множество Н есть, очевидно, одно множество Н. То есть верна формула
, а это и требовалось доказать.
Правило выводимости III доказывается аналогичным образом с той лишь разницей, что здесь не приходится заменять дважды используемое одно и то же множество на одно множество. Заменим в множество С на W, тогда
что и требовалось доказать.
Подобным образом можно доказать также частный случай для правила выводимости III, т.е.
III
Доказательство. Заменим в множество С на Н, W, тогда
Но совокупность множеств Н, Н есть одно множество Н, т.е.
что и требовалось доказать.
IV.
Доказательство. Так как из Н выводима формула , то существует вывод из Н, конечной в котором является формула
:
(1)
Присоединим теперь к совокупности формул Н формулу С. Получим совокупность формул Н, С. Добавляя на основании пункта 1 понятия вывода к выводу (1) формулу С, мы получим вывод
,
(2)
который является выводом из Н, С.
Но в конец вывода (2) можно дописать формулу А, которая получается из формул С и согласно ПЗ (пункт 3) понятия вывода. Отсюда имеем вывод из совокупности Н, С
,
последней формулой которого является формула А. Значит, , что и требовалось доказать.
V. − теорема дедукции (ТД).
Ввиду громоздкости доказательства приводить его не будем. Отметим лишь, что теорема дедукции по форме является обратной по отношению к правилу IV.
VI. − обобщенная теорема дедукции (ОТД).
Словесную формулировку этой теоремы можно записать так: если формула А выводима из совокупности формул то доказуема формула
.
Доказательство. Обозначим через совокупность формул
т.е.
По условию, или, что то же самое,
. Но тогда согласно теореме дедукции справедливо утверждение
. Так как
, то справедливо утверждение
.
Опять, используя теорему дедукции, получим
Проделав эту процедуру k раз, мы придем к утверждению
Но из пустого множества выводимы только доказуемые формулы, т.е.
VII. – правило введения конъюнкции.
Доказательство. По условию
(1)
(2)
Как было показано ранее (см. подразд. 2.5), из совокупности формул выводима конъюнкция
т.е.
(3)
Используя правило выводимости I, можно записать:
(4)
(5)
Теперь, используя правило II выводимости, из (4) и (5) получаем
(6)
Таким же образом по правилу II из (1) и (6) получаем искомое: .
VIII. − правило введения дизъюнкции.
Доказательство. Из условий и
по теореме дедукции имеем
(1)
(2)
Возьмем аксиому . Она выводима из совокупности Н как доказуемая формула, т.е.
(3)
Применяя к формулам (1), (2) и (3) правило сложного заключения, получим
Используя теперь правило выводимости IV, получим , что и требовалось доказать.
Дата публикования: 2015-01-10; Прочитано: 857 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!