Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 23
Текст из файла (страница 23)
А теперь для того, чтобы из Я, а тазже из упомянутых выше выводимых импликаций получить Я, нам остается лишь несколько раз применить схему заключения. Из проведенного рассуждения мы мон'ем извлечь и еще одну теорему о полноте, в которой понятие тоя1дественно истинного выражения вообще не фигурирует.
Именно, рассмотрим какое-нибудь выражение В, которое не выводимо из нашей системы. Согласно ранее доказанному, оно не является тождественно истинным. Рядом последовательных замен выражение В может быть преобразовано в конъюнктивную нормальную форму Я, которая в свою очередь не является тождественно истинной. Пусть этот ряд ведет от В к Вы от Вг к В„...
и, наконец, от В~ к Я. Тогда из нашей системы будут выводимы импликации В -+. ВО В, -~ Вв, ..., В~ -+- Я. Поэтому, если к нашей системе формул 1 — Ч мы присоединим формулу В, то, применив несколько раз схему заключения, мы сможем получить формулу Я, а затем, пользуясь формулами 11, мы сможем получить и каждый в отдельности член атой конъюнкции. Но так как Я не является тождественно истинной, то среди ее конъюнктивных членов (которые со своей стороны являются простымн дизъюнкциями) найдетсн по меньшей мере один такой, у которого каждая из числа входящих в него переменных встречается либо только со анаком отрицания, либо только без него.
Если мы теперь вместо переменных без знака отрицания подставим А, а вместо переменных со знаком отрицания подставим 1А, то получим дизъюнкцию, у которой каждый ее член есть либо А, либо 1 )А, а из нее, пользуясь формулами 1, 111 и Ч 3), можно будет вывести выражение, представляющее собой одну-едиествепную переменную А. А из переменной А подстановкой можно будет получить любое выражение.
Тем самым мы получили следующий результат: система формул 1 — Ч полна в том смысле, что для каждого выражения В, построенного из переменных с помощью рассматриваемых пяти свя- ЭОК-+., Сс, 'Ч', Н 1, ИМЕЕТ МЕСТО СЛЕдуЮщая аЛЬтЕрНатИВа: ЛИбО В выводимо из системы укааанных формул с помощью подстаповок и применений схемы заключения, либо в результате присоединения к этой системе формулы В в качестве исходной становится выводимым любое наперед заданное еыражение.
Эта теорема была бы малосодержательной, если бы любое выражение могло быть выведено унге из самой системы формул 1 — Ч. Но, как мы знаем, из этой снстемьг выводимы только тождественно истинные выражения. 3. Позитивная логика; регулярные импликативные формулы; позитивно тождественные импликативные формулы; возможные упрощения. Характеризуя эту систему формул 1 — Ч, заметим, что она устроена таким образом, что в формулах первой группы из логических связок встречается только импликация, а в последующих группах — только импликация и связка, вводимая атой группой. В выборе этих формул существенную роль играет то, что посредством формул групп ! — 1'Ч из области общей логики высказываний вычленяется так нааываемая позитиеная логика, представляющая собой формализацию тех способов логических умозаключений, которые не зависит от предположения о том, что для всякого высказывания имеется ему противоположное.
Этому вычленению позитивной логики способствует то обстоятельство, что группа формул 1 содержит лишь такие формулы, которь|е соответствуют правилам гипотетических умозаключений. Способ, которым формулы группы 1 выделены нами из числа остальных, может быть уточнен вполне математически '). С этой целью мы введем понятие р е г у л я р н о й и м и л ик а т и в н о й ф о р м у л ы. Выражение, построенное из переменных с помощью одной только импликации, мы будем называть импликативной формулой.
Имплнкативную формулу вида Я вЂ” +- (В-+-(... — +-(Ж вЂ” +- й) ...)), построенную нз вырансений Я, В, ..., Я, Й, у которых посылка кансдой импликации состоит из одной лишь переменной, мы будем называть р е г у л я р н о й и м и л и к а т и в н о й ф о рм у л о й, если и' либо само встречается среди выразкений Я, В,..., 6, либо может быть выведено из них путем применения схемы заключения (но без подстаяовок). Так, например, все три формулы группы 1 являются регулярными импликатнвными формулами.
В случае формулы А -э. (8 -э. А) этот факт очевиден непосредственно. Формула (А -+. (А -+. О')) — ~ (А -1 Л) ') Это выделение существенно отличается от того, которое предпринял Льюис, введя свое понятие с т р о г о й в м п л и к в ц в и (згг1сс ппр11саМсв): Ь е м 1 з С. 1. А звгтеу о1 зущЬО11с 1оя1с.— Вегле1еу, 1918. Теория строгой ямплвлацив нацелена вз то, чтобы вйлввть лря зксаоматвчесвом построения мвтематвческой логики различие между чисто материальным е необходямым.
!гл. Кн ИСЧИСЛКПИК ВЫСКАЗЫВАНИИ 1 а! дндуктивнля логикА ВыскАзыВАнии 101 имеет вид Я -» (>и -» 6), где в качестве Я, й) и б фигурируют выра>кения А — «(А — »В),А иВ; но В мо>г<ет быть получено из А — >- (А -» В) и А двукратным применением схемы заключения. Формула (А -+ В) -+. ((В -» С) -» (А ->- С)) имеет вид Я-+.
(й) — »(6-+. й>)), где в качестве Я, й), б и 'Э фигурируют выражения А->-В,В-»С, А иС; С может быть выведено нз А, А -+. В, В -» С двукратным применением схемы заключения '). Импликативная формула будет называться п о з и т и в н о т о ж д е с т в е н н о й, если она либо явлнется регулярной, либо получается из регулярной формулы путем подстановни, либо получается из уже полученных таким образом формул с помощью схемы заключения.
Например, по этому определению, формула ((А -» А) — » В) — >- В является позитивно тождественной импликативной формулой; действительно, опа получается с помощью схемы заключения из формул А — >- А, (А -» А)-+. (((А ->- А) -» В) -» В), первая из которых является регулярной импликативной формулой, а вторая получается из регулярной импликативной формулы А -» ((А -» В) -+.
В) с помощью подстановки. ') Регулярными импликативными формулами могут быть представлены все те обобщеяньге цепные заключения, которые Н. Герц рассматривает в своей теории систем предложений: Н е г хе Р. ПЬег Ахгеп>епвуввеп>е Ьйг Ье))еЬ~зе Затхвувгеше.— Ма>Ь., Апп., 1923, 89, № 1/2; 1929, 101, № 4. Именна, каждое из рассматриваемых в этой теории предложений имеет вид а>... а1-» Ь; заменим зто предложение соответствующим ему выражением А> -«(А в -«(., -» (А1-» В)...)); тогда каждому допустимому по правилам Герца ваключенню с посылками $г, ..., 2)г и заключительным предложением ю будет соответствовать регулярная имплииативиая формула Я>- (>ов- (".— (Яг- ю)-)).
Таким образом, понятие позитивно тождественной импликативной формулы определяется без привлечения каких-либо специальных исходных формул, с учетом одних только правил вывода. Мо>!<но показать, что совокупность позитивно тонгдественных импликативных формул совпадает с совокупностью тех тождественно истинных выражений, которые могут быть выведены иэ формул группы 1 с помощью подстановок и схем заключения.
Однако эта совокупность не содержит в себе все тождественно истинные импликативные формулы. Наоборот, среди тождественно истинных импликативных формул имеются и такие, которые не являются позитивно тохгдественными, например, ((А — В) — А) — «А. Относительно этой формулы можно показать '), что она не выводится из формул группы 1 с помощью указанных двух правил. Однако, если зту формулу взять в качестве исходной вместе с формулами 1 1) и 1 3), то этого уже будет достаточно для того, чтобы с помощью подстановок и схем заключения можно было получить все тождественно истинные импликативные формулы х). Что касается совокупности позитивно тождественных импликативных формул, то для них в качестве исходных формул достаточно взять следующие регулярные импликативные формулы: А -+.
(В -+. А), (А ->.(В -+. С)) ->. ((А -» В) -» (А ->. С)). Вторая из них может быть выведена иа следующих трех формул: (В -» С) -» ((А -» В) -» (А — «С)), (А -+. (В -» С)) -«(В ->. (А -» С)), (А -» (А -+- В)) -» (А -+. В).
Таким образом, мы пришли к системе исходных формул, которая состоит из следующих четырех: 1 1), 1 2), а также (А ->.(В -» С)) ->-(В -+.(А ->- С)) ') См. е. 1М. ') Систему исходных формул, достаточную для вывода всех тождественно истинных импликативных формул, впервые указал М. Шейнфиниель. А. Тарский показал, что в качестве исходных формул для атой совокупности достаточно взять уже следующие три формулы: 1 1), ! 3) и ((А -» В) -«С) -1- ((А -» С) -+- С). Здесь третью формулу можно заменить упоыянутой выше, которая является более простой. М. Вайаберг и Я. Луиасевич нашли целыи ряд формул таких, что каждая из них может быть взята в качестве единственной исходной формулы для вывода всех тождественно истинных импликативных формул.
В этой евязи ем, уже упоминавшийся ранее доклад Лукасевича и Тарского: Е и й аз > е >т ! с х !., Т а г в й! А. !)п1егвпейпп8ег> ййег беп А»вваяев)га)йй!.— С.З. Боа. Ъек тагват)е, 23, Г>гагвайап, 1930. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ [Гл. гн 102 В ь1 метОД ОЦенОк и ДоклзАтельстВА незАВисимОсти 103 И (В ->- С) -ь. ((А ->- В) -ь. (А ь. С)). В этой системе, как показал Я.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
