Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 113
Текст из файла (страница 113)
Таким образом, для выводов, осуществляемых с помощью схем (В!) — (В4) в рамках как угодно ограниченной совокупности формул, содержащей импликацию и конъюнкцию, действует теорема о посылках. Используя этот факт, можно сравнительно просто доказать, что с помощью схем (5!) — (ВЕ), применяемых к 1-К-формулам, может быть выведена любая позитивно тождественная 1-К-формула.
Искомое доказательство распадается на три части. В ходе этого доказательства выводи мость мы всегда будем понимать как выводимость при помощи схем (В!) — (54), применяемых к 1-К-формулам, 1)) По теореме о посылках каждая 1-К-формула вида (зч Я))- ((Я- Е)-.(6- 6)) выв !дима С другой стороны, как мы знаем, выводима схема формул Л -«(Е -«6), и у нас в распоряжении имеется схема заключения.
Тем самым по полученной нами в 5 1 дедуктивной характеризации совокупности позитивно тождественных импликативных формул каждая позитивно тождественная импликативная формула выводима с помощью схем (Б!) — (54), а благодаря производности схемы выводима и любая конъюнкция позитивно тождественных нмпликативных формул. Таким образом, трансформация любой позитивно тождественной 1-К-формулы выводима. Поэтому задача нашего доказательства сводится к установлению того, что если выводима трансформация какой-либо 1-К-формулы, то выводима и сама эта формула. Мы сейчас покажем, что любая 1-К-формула дедуктивно равна своей трансформации (прн этом две 1-К-формулы мы будем называть дедуктивно равными, если каждая из них выводима из другой с помощью схем (5!) — (В4), применяемых к 1-К-формулам).
ПОЗИТИВНО ТОЖДЕСТВЕННЫЕ ! К-ФОРМУЛЫ 529 ПРИЛОЖЕНИЕ пп 2)) Из теоремы о посылках следует, что если 1-К-формулы Й и 6 дедуктивно равны, то выводимы обе импликации Я-«е) и 6 -« 9! !), Отсюда, далее, получается, что если 1-К-формулы Я и е) дедуктивно равны, то для произвольной 1-К-формулы 6 формула 6-«Я дедуктивно равна формуле 6 — «З, формула Й-«6 дедуктивно равна формуле д)- 6, формула Л8(6 дедуктивно равна формуле е)8) 6, а формула 6 8( Я дедуктивно равна формуле 6,8(чт. Так как две формулы, порознь дедуктивно равные третьей, дедуктивно равны и между собой, то из только что приведенных соотношений вытекает, что любая 1-К-формула при замене любой ее составной части формулой, дедуктивно равной этой части, переходит в дедуктивно равную ей формулу.
Таким образом, для доказателъатва того, что всякая 1-К-формула дедуктивно равна своей трансформации, нам остается показать, что процедура построения трансформации распадается на такие элементарные шаги, которые состоят из замены какой-либо 1-К-формулы (отдельно взятой или фигурирующей в качестве составной части другой формулы) формулой, дедуктивно ей равной. 3)) Процедура построения трансформации 1-К-формулы может быть разложена на следующие элементарные шаги: а) замена формулы Й 8((е) 8) 6) соответствующей ей формулой (Й Й 3) сс 6, вместо которой можно писать и короче: Я8(д)8(6; б) замена формулы Я8(6 — 6 формулой Я вЂ” «(д) — «6); в) замена формулы 6-«38(6 формулой ()Л-«дт) 8((Я-«6). С помощью установленных нами ранее выводимостей можно непосредственно убедиться, что в каждом из этих трех случаев происходит замена формулы дедуктивно равной ей формулой.
Тем самым искомое доказательство закончено, а значит, обосновано и утверждение о том, что совокупность позитивно тождественных 1-К-формул совпадает с совокупностью тех формул, которые могут быть выведены с использованием схем (3!) — (3,), применяемых к 1-К-формулам. Наше доказательство заодно позволяет утверждать, что теорема о посылках справедлива и для выводов, пРоизводимых пУтем пРименениЯ схем (5 — (5а) к пРоизвольным формулам, содержащим нмпликацию и конъюнкцию. Отсюда мы можем, в частности, получить два обещанных нами следствия, В самом деле, ввиду справедливости теоремы о посылках для выводов с помощью схем (5!) — (3в) и с учетом того факта, что схема заключения входит в число этих схем, получается, что каждая непосредственно тождественная 1-К-формула выводима с помощью схем ($!) — (Бз), применяемых к 1-К- ') То, что зто предложение, ие имекпцее места в ооычиом дедуктивном псчислеиви высказывавия, здесь оказывается верным, связано с тем, что е рассматриваемом дедуктивном формализме отсутствует правило подстановки, фоРмулам, а отсюда следует, что каждая такая формула является позитивно тождественной.
Теперь заметим, что если в выводе какой-либо 1-К-формулыт производимом с помощью схем (3)) — (Бз), какую-либо формульную переменную повсеместно заменить произвольной 1-К-формулой, то снова получится вывод, производимый с помощью тех же самых схем. Отсюда следует, что из позитивно тождественных 1-К-формул в результате подстановок, а тем самым и в результате подстановок и применений схемы заключения, снова получаются позитивно тождественные 1-К-формулы. К сказанному мы сделаем несколько дополнительных замечаний. Первое из них будет касаться вопроса о независимости схем (3!) — (3в) Независимость схемы заключения (5,) от остальных схел( (3)), (3в), (3з) и (Яа) вытекает из того, что в результате применения каждой из этих четырех схем всякий раз получаются формулы, имеющие вид импликаций.
Поэтому, например, формула (Я-«Я) 8((Я-+.Я), которая является позитивно тождественной и, следовательно, выводится с помощью указанных пяти схем, не может быть полу- чена без использования схемы заключения. То, что ни одна из схем (3!), (3я), (3з) и (3в) тоже не является излишней, следует из того, что в рамках выводов, производимых с помощью подстановок и схемы заключения, соответствующие этим схемам формулы А 8( — «А, А 8)В-«В, (АйВ-«С)- (А-«(В«С)) н (А — «(В -)-С)) — ). ((А — «В)-«(А -«С)) не зависят друг от друга.
Соответствующие доказательства могут быть получены с ис- пользованием разработанного в гл. П1 т. 1 метода оценок'). Для Установления независимости первых трех формул достаточно вос- пользоваться теми оценками, с помощью которых мы в свое время доказали независимость трех формул 1 1), 2) и 3) в рамках системы формул 1 — Ча).
Естественно, в рассматриваемых оценках должны "Риниматься в расчет лишь определения значений для имплика- ции и конъюнкции. Независимость формулы (А (В с)) ((А а) (А св ') ~ . ') См, т, 1, с, 98 — 97 и !08 — !! !. ПРИЛОЖЕНИЕ пн г) См. т. 1, с, 108. устанавливается с помощью следующей оценки с тремя значениями а, р и у: во-первых, должны выполняться ос н он н ыа р а в е н с т в а ') А — «А=и, А-«и=а, ()-«А=и, 1 ' 1 при любом значении А, АйА А, Айа=А, Ай()=РР ) А й В В й А при любых значениях А н В, а кроме того, — дополнительные равенства и-«р=р, а — «у у, у-«р=у.
При этой оценке первые три нз рассматриваемых формул, а также любые формулы, выводимые нз них с помощью подстановок и схемы заключения, всегда принимают значение а. Четвертая из указанных формул этим свойством не обладает. Действительно, (у-«(у-«р))-«((у-«у)-«(у-«р)) (у-«у) «(а — «у) и-1-у у.
Проведенное рассмотрение заодно показывает, что при выводах с помощью подстановок и схемы заключения указанные четыре формулы образуют систему аксиом, достаточную для получения всех позитивно тождественных 1-К-формул. Такого рода систему аксиом для позитивно тождественных 1-К-формул образуют н формулы ! 1) — 3) и !! 1) — 3) из при- веденнои в т. 1 н только что упоминавшейся системы аксиом для исчисления высказываний. Напомним эти формулы: А- (В-«А), (А- (А-«В))-«(А- В), (А -«В) -«(( — С) «(А -«С)), Ай В-«А, А й В -1- В, (А — В) -«((А -«С) -«(А -«В й С)).
Чтобы убедиться в достаточности этой системы формул для вывода всех позитивно тождественных 1-К-формул, нам нужно только установить, что по отношению к этой системе (при исполь- зовании подстановок и схемы заключения) схемы формул (31) и (31) в нх применении к 1-К-формулам оказываются выводимыми,, а схемы вывода (Ьг) и (31) — производными. Для схем ($1) и (31) зто очевидно. Для схемы (31) мы это доказали в 8 1; кроме того, ' там уже было установлено, что из формул ! 1) — 3) с помощью подстановок и схемы заключения выводима любая позитивно тож- дественная импликативная формула. Но с помощью позитивно позитивно тождественные 1-к формулы тождественных импликатнвных формул и формы (А -«В) — ((А -«С) -«(А -«В й С)) из 1-К-формулы Яй6-«6 легко вывести формулу Я- (8 Я) так что схема (3г) тоже оказывается производной схемой Вчесто системы формул ! 1) — 3) и 11 1) — 3) можно также взять систему, состоящую нз формул 1 2), 3), 11 1), 2) н формулы А — «1В -«А й В) .
действительно, для этой системы схемы формул (31) и (31) опять- таки оказываются выводимыми, а схема вывода (3,) — производной, (последияя — согласно доказанному в 5 1). То же самое верно и. в отношении схемы силлогизма. Осталось еще показать, что схема вывода (Ьг), т. е. схема Яйб-«5 Я -«(5 -«(1) тоже является производной схемой. Это делается следующим образом, Формула А -«(В -«А й В) дает нам схему формул Я вЂ” (е -ь. Я й 3), а тем самым и схему вывода З 21-«Зйр! С другой стороны, нз схем (31), ($г), ($,) и схемы силлогизма мы получаем схему е! -«(Е -«(1) ЗйЯ вЂ” «5 так что в итоге, применив еще раз схему силлогизма, мы получаем схему вывода Я «(5-«6), З Я-«6 Из э з этой схемы в сочетании со схемой формул (Я -«О) «((9-«6) -«(Я -«6)), получающейся из формулы ! 3), мы получаем схему Е:, (1 ТОЖДЕСТВЕННЫЕ ЬК.Н.ФОРМУЛЫ пн 4 3! ПРИЛОЖЕНИЕ Теперь, если дважды применить эту схему к формуле Я3с6-+.(1, то получится формула (Я (6 Я й 6)) (Я (6-.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
