Основные правила выводимости

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, получим , что и требовалось доказать.