Гильберт, Аккерман - Основы теоретической логики (Гильберт Д. - Основания математики и прочие работы), страница 10

Доказагельство получаем из (11) н (12). Формула (гд): Х ( Я) — У (ХЯ). Дрказатдльствр: Я вЂ” оХЯ (из аксиоиы Ъ) путем пе. рестановки дизъюпктивных членов], УЯ вЂ” >У(ХЯ) [правило 1Ч], Х(УЯ) о Х(У(ХЯ)) [правило !Ч], Х (УЯ) — + (У(ХЯ))Х*[коммутативпость дизъю~кции], Х вЂ” иЯХ (из аксиомы Ь) путем перестановки дсшьюнктивных членов], Хя- у(Хя) [подстановка в предыдущую фоРмулУ) Х-+У(ХЯ) [правило Ч], (У(ХЯПХи(У(ХЯ)) (У(ХЯ)) (правило 1Ч], (!'(ХЯ)) Х У(ХЯ)оо (замена сдЧ'д на 5). Из (*) и (оо) получаем по правилу Ч: Х (УЯ) У (ХЯ).

Формула (Щ: Х(УЯ) — ~(ХУ)Я. Доказательство: Х(УЯ) —.Х(ЯУ) [закон коммутативпости]. Х (ЯУ) — и Я (ХУ) (формула (14)], Х(УЯ) — Я(ЛУ) [правило Ч]. Отсюда, применяя закон коммутативности, получаем формулу (15). Формула ()б); (ХУ) Я Х(УЯ). Доказательство: Я (УХ) р (ЯУ) Х [подстановка в (15)]. Приогеняя закон коммутативнссти, можно я 1!'Х) заменить на (ХУ) Я, а (лгу) Х на Х(УЯ). На основании формул (15) и (16) и правила Ч! за- ключаем, что не галька последовательность дизъюнк- тивных членов, по н их сочетания в группы можно по произволу изменять. Таким образом, мы вывели ассрблатпвньа! закон для дизъюнктинноб связи. Формула (!2)с Хй(уйб) — (Хйу)йЯ, (Х й !') й Я вЂ” о Х й (У й Я).

Доказитвльство: Х й (У й Я) является сокращением для ХУ Я, а (Хйу) йЯ для ХУЯ. Однако оба вы- ражения, согласно нашим предшествуюп!нм правилам, эквивалентны и по прсизнолу могут залсенять друг друга. формула (!б): Х->(УДакпзательства: (ХУ) ХУ (порстаноека в (3)]. Иначе сочетая дизъюнктивные члены, получаем Х(УХУ). Это и есть искомая формула. Пранило ЧП: 2( — р(т — б) маркет быть за- менено на 9 — -(сд — рб) изина (с)(йт) иб. Доказательстно сразу получается из наших правил, если заменить сокращения — и и й их значениями. Правило ЧПП 2! (а — оВ) можно заменить на 2( — > т.

доказательство: гл'(т!9) лгожно заьоснить на (6 сд)ю или на са9. Фориула (гр): Х(уйЯ)-.ХУй ХЯ. Доказательства; У й Яму [формула (!2)]. Х(уйб)- ХУ (правило 1Ч]. Точно так же получаем из формулы (13) Х(УйЯ) — иХЯ, напыление высказывлыаа Нкорвтивврекоы>скы сипкемы вксквм ХУ вЂ” >(Х2 — «ХУ йХ7) [формула (18Ц, Х (?' й 7) — «(Х7 — «ХУ й Х2) [по правилу Н], Х2 — >(Х(Уй 2) — «ХУйХ2) [по правилу Н!Ц, Х(Уйг) — >(Х(Уйг) — «ХуйХ2) [правило Н], Х (У й 2) — «ХУ й Х2 [правило НИЦ. Формула (гр): ХУйХ2- Х(? й2).

Двказательслгво: У вЂ” «(7 — > ?' й 2) [формула (!8)1, (2->Уй 1) — >. (Х 2 Х(Уй 7)) [аксиома б)], У вЂ” >(Х7 — >Х(Уй 2)) [правила Н[, Х7 — «(У вЂ” «Х(Уйг)) [правило Н!Ц, (? — >Х(Уй2)) — «[Х?'- Х(Х(Уйг)Ц [подстановка в аксиому дЦ, Х7 — «[ХУ вЂ” >Х(Х (?'й 2Ц) [правило Н], Х(Х(Уйг)) можно заменить на (ХХ)(УЙ2) и затем на Х(Уй2).

Х7 — > (ХУ вЂ” «Х (?' й 2)). Отсюда, согласно правилу НП, получаем формулу (20). Формулы (19) н (20) вместе с правилом Н! дают доказательство закона дистрибутнвносги. Дальнейший выпад формул и правил оказывается певун<пыли. Действительно, мы обнаружили, чта пра- вила аЦ вЂ” а4), вЦ вЂ” вЗ), которые мы раньше ус>ано- вилн, выводятся нз аксиом как пропзводные правила.

Отсюда следует, что все выводы, которые мы сделали раньше на основе этих правил. например те, которые касались принпипа двойственности и нормальной фор- мы, могут быть получены также аксиоматическн. По. этому не нужно каждый раз возвращаться к анена. мам, чтобы установись эоказуемасть некоторой фор. мулы. Ибо формула исчисления высказываний дока- зуема из аксиом в том и только в том случае, когда в принадлежащей ей конъюнктивной нормальной форме каждая дизыонкцня содержит два члена, из которых один является прогивоиолажнашью друго~о.

$ >2. Неоратываречывоеть сыстеыы окском Аксиоматическае построение исчисления высказывзний дает вазможность ставить в исчислении выска- зываний такие вопросы, которые присущи аксиомагическому методу. Важнейшими нз них являются: лелротиворвчиввстгы ыезввисимашль и полнота сис>емы аксиом. Сначала мы рассиотрим вопрос о непрщиваречивастн аксиом. Вопрос о непротиворечивости может быть здесь поставлен а переносном смысле. 2?ы называем аксиомы непротиворечивыми, если неваэмо>кно с помощью исчисления вызесги два ело>нных высказывания, находящиесн друг к другу в отношении противоположности, т.

е. получающиеся из пары высказываний Х, Х, если в каждое из них вместо Х подставить одна и то же выражение, Это определение непротиворечивости делает необходимым следугощее пояснение. Здесь как будто выдвигается на первый план по сравнению с осталь. ными один определенный логический принцип: закон противоречия. В действительности >ке дело обстоит так, чго появление формального противоречия,то есть доказуемость двух формул бЦ >й, осудило бы все исчисление на бессмысленность; ибо мы уже раньше заметили, что если доказуемы два высказывания вида >й и 6, то доказуеь>о и каждое другое высказывание.

Непротиворечивость исчисления в смысле нашего определения, таким образом; равнозначна с тем, что не каждая формула доказуема. Чтобы установить непротиворечивость исчисления, мы поступаем следующим образом. Будем понимать знаки высказываний Х, У, 2,... как арифметические переменные, для ко>арых в рассмогрепие входят только значения: О, 1, ХНУ мы истолковываем как арифметическое произведение, а Х определяем так: 0 равно 1 и Т равно О. На основании такай интерпретации каждое сложное выска.

Исгисзсппе высеезыввпиа Незвпгспмвсжь п гызпвпгв спсжемвг зывание представляет собой некоторую арифметиче. скую функцию основных высказываний, которая может принимать только значенил О или 1. Если эта функция тождественна равна нулю, то для краткости мы будем говорить и о семом силзволическом выражении, что оно тождественно равно О, Это истолкование дает возможность укгзать теперь некоторое общее свойство всех тех формул, которые могут быть выведены из наших аксиом. А именно, для любой, из подлежащих рассмотрению, системы значений переменных выводимые из аксиом формулы в нашем арифметическом истолковании дают значение О, т. е.

тождественно равны О. Этии свойством, прежде всего, обладают аксиомы а) — и); мы устанавливаем эта следующим образом. Путем испытаний убеждаемся, что Х ДГ Х все~да имеет значение О. Отсюда следует, что и Х~'Хл/Х [аксиома а)[ также всегда равно О, потому что Х~'Х имеет то же саиоезначепие, что и Х.— Долее, Х(ХУ) [аксиома Ь)) имеет то же самое значение, чга и (ХЛуХ) у, в силу ассошзативности арифметического произведения.

Оно, следовательно, всегда равно О, так как Олг"г' равно О, тэк как гглух всегда имеет та же значение, что и Х'„г)г, то Хз)УЛ)(УЖАХ!, как частный случай для Х'„'Х, всегда ранна О. Таким образам, формула с) всегда имеет значение О. Накпнец, убезкдаемся в исгинностн сказанного и по отношению к формуле б): действизельно, лри 2=0 агин саино. житель =О, при Я=! выражение йлггХ имеет то же значение, что и Х, а и','У вЂ” то же значение, что и У! итак, в случае й = 1 формула в целом оказывается ииеющей та же самое значение, что и Х)'ХУ, чтоснова есть частный случай для ХХ.

Таким образам, все четыре аксиомы действительно обладают указанным свойсгвои. Прн использовании обоих подлежащпх рассмотрению правил, применяемых наии длл вывода новых формул, а именно пра- вила подстановки и схемы заключения, эта свойство всегда сохраняется. В самом деле, что касается перного пРавила, та Ясно, что пУтем погбстанавки некоторого выражения вместб перемениога запас зпачениг для этого переменного во всяколг случае ие может быть расширен. И если иы с помощью второго правила из двух формул вй и где вывалим формулу 5 то свойство допеть всегда значение О переносится с обеих этих формул на выведенную формулу; ибо так как формула зй дает всегда значение О, та й всегда имеет значение 1; таким образом, гй5 имеет то же самос значение, что и 6, а поэтому ю также, как й5, всегда имеет значение О.

Мы видим, что дейстнительно с помощью нашего исчисления получаются толька такие формулы, которые при арифметическом истолковании дают всегда значение О. Но установив это, иы фактически заканчиваем наше доказательство. В самом деле, две формулы, которые возникают из Х и Х заменой Х оба раза теи же самым сложным выскаэываниеи, очевидно, не могут обе обладать свойством всегда быть равными О; если одна из пих всегда имеет значение О, то другая всегда илзеет значение 1. 5 13. Иеввонснмость н полноте сметены К вопросу непротиворечивости, на который в птношении нашей системы аксиом мы могли ответить утвердительно, примыкает другой вопрос: являются ли все аксиомы лезавпсплгыми друг от друга, или же без тай или другой из этих аксиом можно обойтись".

Ответ гласит, что наша система аксиом дейстннтельно удовлетворяет требованию независимости. ' Этот вопрос а пеэвпнспмосгн системы вксном также решен и цнтпропвнпой пв стр. Я работе: Вегпвув Р., Ах1птвпюне Оп1егвпсэппа.,, Исчисление онсттзиоаний Сначала мы покажем, что формула а) Х~ХГгХ не может быть выведена из остальных аксиом, и притом если даже иы присоединим в качестве аксиомы формулу Х>уХ; таким образом, мы одновременно докажем, что формул> а) не может быть заменена в нашей сисзеие аксиом более простой формулой ХХ. Для других аксиоьз доказательство независимости также проведено в расширенном смысле, г.

е. одновременно будет показано, что соответствующая аксиома не может быть заменена аксиомой Х>ь>Х. Доказательст>зо снова выполняется с помощью некоторой арифметической интерпретации. Мы берем в качестве значений для . переменных Х, У, 2,... классы вычетов О, 1, 2 по модулю 4. Знак «'ггз пусть снова означает обычное умножение, а Х определяем следузощим образом: 0 означает 1, Т означает О, 2 означает 2. Можно проверить теперь, что формулы Х)уХ, Ь), с), д) при указанном истолковании переменных выражают всегда вычет О, и это свойство переносится при применении обоих праннл на все формулы, выведенные из этих 4 формул.

Мы это устанавливаем таким же способом, как и при доказательстве непротиворечивости. Г!оэтому, если бы формула а) могла быть выведена нз Ь), с), б] и Х','Х с помощью наших правил, то выражение ХХ>уХ для каждого допустимого значения Х должно было бы дать вычет О. Однако этого мы не имеем. В самом деле, если мы подставим вместо Х значение 2, то получим: 2~/2Г/2 =0>о>2 = !АЗ = 2, т. е. не нулевое значение. Незаьнсимость аксиомы Ь) Х>,'(Х'„~У) от остальных аксиом и формулы Х~,'Х мы покамсем следующни образом. Снова Х, у, 2 рассьзагривасм как переменные, которые могут принимать значения О, 1, 2, 3, Згезаоисииость и нолн>та систеин Но теперь мы определяем связь ~/ для этих переменных череа: 0>>0 =0>з! =0»2 =0>зЗ= О; 1>,'! = 1',/2 =1>>3=1; 2 '>г 2 = 2; 3 >,> 3 —.