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

Что подобное выражение представляет собой истинное высказывание при любых значениях основных высказываний, следует и непосредственно из определения отрицания н связей сн» и силн>. Но это н единстненные выраже. ния, которые всегда истинны. Ибо если в каком-нибудь конъюнктивном члене некоторой нормальной формы, имеющем, конечно, форму дюъюнкцни, каждое основ. нос высказывание содержи>ся в начес>ве либо только неотрицаемого, лнГ>о только отрицаемого множителя, то зтуднзъюнкцню можно превратить в ложное высказывание, если подставить на место неотрицаемых знаков высказываний ложные выс><азынания, а на место отрицаемых — истинные.

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

!.Х Х. Преобразуя согласно правилу а4)з получаем> ХХВЛХ. Последнее выражение в норзщльной форме содержит в кэждом конъюнктизном члене основное высказынанне и противоположное ему; следовательно, оно истинно. 2. ХВУ вЂ”. Х. Преобразуя, получаем: ХЙУ '„~ Х [по а4)[, ХУХ [по аЗ)).

Последняя дизъюнкция содержит Х н Х; следовательно, онн истинна. 3. [Х д> [Х вЂ” » У)) — » У. 3 о т р с»те ы ° Иккяклеяае выккаянвягшй дояыянкашвяяя я>р. яякн ~я р> ряча Получаем: Х й ХУ '~> У (двукратным применением а4)], Х(ХЙУ)У (по аЗ)], ХХУй ХУУ (гю а!]], ХХУ й ХУУ (по а2) ]. Первая дизыонкция содержит Х и Х, а вторая— У и У. Таким образои, сложное высказывание (Х й (Х-+ У)) -> У является всегда-истинным. б 5. иринина леоаетзенноетн Одно существенное замечание, характеризующее наше исчисление, связано с правилом аЗ).

Из этого правила следует, что для вира>квии, которое образуется аз основных высказываний и их отрицаний с помощью толька коньюиктивнвй и дизьюнктививй связей, противоположное ему получается путем обмела местами знаков й и >у и за.тены ос>говных высказываний их отриг)алиями. Мы можем исгюльзовать это следующим образом. Пусть установлена всегда-истинность некоторого выражения вида к)! 6, или, как мы иногда буден говорить, логического уравнения. (Мы употребляеи немецкие буквы для обозначения сложных высказынаний, точный формальный вид которых остается неопределен.

ным, а также иногда для сокращения.) Так как кй 6 равнозначно с П 6, то мы получаем снова истинное выражение, отрицая обе части уравнения. Если обе части уравнения образованы из основных высказываний и их отрицаний путем нрииеиения только коныонкций и дизыонкций, то мы пажем применить указанное выше правила. Мы получаеи при зтоьг формулу, которан возникает из первоначального уравнения П 6 посредством обмена местами знаков й н >у и замены основ- ных высказываний протившюл>ш.иымн нм. Так как зто уравнение всегда истинно, то мы мо>кеи заменить в нем каждое основное высказывание нротиаополо>кным.

Этим мы устраняем выполненную нами предварительно замену основных высказываний нх отрицаниял>и. Таким образом, получается следующий лр>>лиан дввйсглвви>гости> из всегда-истин>юй формулы кй 6, ойв стороны которой образованы из агнввиых высказываний и их отрицаний путем использования конаюиктививй и диэыолхтиаиой связей'., лвлучаен снова истинное уравнение, меняя местами знаки й и ку, ' Так, Х(уйй)-ХуйХ2 всегда истинно.

Это формула первого закона днстрибутввности. Из нее ио принципу двойственности получаем формулу: ХйУЯ (ХЬУ) (ХЕЕ), которая также истинна и выражает в>арой закон дистрибутивности. Точно так >ке истинной формуле: (ХЖХ)У У согласно принципу двойственности соответствует истинная формула: ХХ бгу.

У. б а. днзъюннтнвнея нярмезьнэн форма лая зогнчееннз выражений Правило образования отрицания иожно применить с болызой пользой для дела. Мы видели, что каждое логическое выражение может быть приведено к нормальной форме. Эта нгрмальная форма состоит из коньюнкции дизъюнкций, где каждый дизъюнктиапый член представляет собой отрицасиас илн неатрнцаемое основное высказывание. Преобразование выражения к нормальной форме происходит путем применения зя Исшслсиие внсхсзнвлюза Дйнвгзсбрвзас слсжнсп высхазывазсо 3> правил а()-а4).— Наряду с указанной формой существует егце втврая иормальнал форма, которая состоит из дизъюнкции конъюик>шй. Каждый конь>оп>с>явный член является отрицаемым или иеотрицаемым основным высказыванием.

Мы называем эту нормальную форму сдизьюиктивной>, а ранее усгановленную в оган. чие — схоньюлктив>звйз. Преобразование выражение к дизъюиктивной нормальной форме происходит следующим образом: отри. лаем первоначальное выражение и приводим его к конъюнктивной нормальной форме, а затем вновь огрицасм полученное выражение согласно нашему правилу. Можно воспользоваться идем обстоятельством, что по о>ношению к правилам а!) — а4) коньюнкция и дизъюнкцин вполне двойстнснны. Подобав тому, как из коньюиктивной нормальной формы можно вачитать, являгтгя ли некоторое вы. ражеиие всегда-истинным или нвт, так с помои)ь>в дихьюнктилнвй нормальной формы .кожно установить, явгягтгя ли оио всегда-люкиын. Последнее имеет место в том и только в том случае, если каждый дпзъюнктианый член одновременно с каким-нибудь основным высказыванием содержит и противоположное ему высказывание.

Локаза>ельство э~ого получим сразу, если учтем, что отрицание дизъюнктивпой нормальной формы выражается кон ьюнктивной нормальной формой, а также, что формула в том и только в том случае всегда ложна, когда противоположная ей формула всегда истинна. В качестве примера применения дизъюнктивной нормальной формы рассмотрин сложное высказывание; ХУйУгй ХД7. Пршхеняя второй закон днстрибутивности, получаем нормальную форму: (ХйГйХбХ) ~ (ХйгйХб4>7 (УбсубХб>7) ',' ()'й7.йХй У'ч Здесь каждый дизъюнктивный член содержит какое-нибудь основное высказывание вместе с его отрицанием: первые два Х н Х, третий )' и Р и четвертый Е и Е.

Таким образом, высказывание Х У бс У Л бг Х й Е является всегда ложным. Дизъюнктивная нормальная форма имеет преимушество особой обозримости. Отдельные дизъюнктивные члеяы выражают различные возможности, при наличии которых данное сложное высказывание является истинным. Так, дизъюнктнвиач нормалы>ая форма для выражения Х )' будет (ХЬУ) (Хб>Г), а зто дает возможность установить,.что если Х У доля<но бы>ь истинным, то Х и У должны быть либо оба истинны, либо оба ложны.

й т, Многообразие слонвых высказывании, которые когут быть образованы нз денных оснвнных высхххывенна Еще одно важное замечание об исчислении относится к многообразию высказываний, которые могут быть образованы с помощью комбинации конечного числа основных высказыв>ний Х„ Х„ ..., Хл.

Мы будем при этом рассматривать как раззнчньш только такие высказывания, которые логически не эквивалентны. В этом предположении указанное многообразие состоит лишь из конечного числа высказываний. Как мы ранее упомянули, высказывание, образованное из Х„ Х„ ..., Х„, эквивалентно другому того же рода высказыванию в том и только в том случае, если оба высказывания для любых значений Х„ , Х„ имеют одинаковое значение истины или лжи. Мы имеем прежде осего 2" возможных распределений нс>инности или ложности основных высказываний, хак юис каждое о>дельное высказывание Х„ Хз,..., Х„может быть как ис>инным, так и ложным. Составленное нз Х„ Х„ ..., х„ высказывание олре- М«осо«брате с ««»кньх вискозы«внаа ,о Итшленое вот«энввкоа деляется теперь теч, что для каждого из 2" случаев устаианливае>ся, истинно ли оно в этом случае или ложно.

Существтег поэтому точно 2<в "> различных высказывавпй, лоторые могут быть образованы из х„ха ..., х„. 4 различных выскашввання, образуемых с помощью одного только Х, суть: Л; Х; Х <у Х; Х б< Х. !б различных высказываний, которые могут быть образованы нз Х и У суть: Х; У; Х <к У< Х <у У< Х вЂ” У; У вЂ” Х; Х У; Х<УХ н их отрицания: Х; У; Х','У; Х«йу; Хг<У< Уб<Х< Х.

У; ХйХ Среди 2<о«> высказываний два занимают особое положение; именно, всегда-истианос высказывание, которое выражается, например, в виде Х, 'х< Х, (или в виде Х, Х„), н всегда ложное, которое можно выразить в виде Л',й Х,. Формальнь<й обзор различных высказываний, которые могут быть образованы из Х„Х„..., Х„получаем с помощью следующего предложения: Каждое выражение, образованное из основных высказываний Х„Х«, ..., Х„, эквивалентно некоторой кон<.юнкции из часто множества всех членов развернутого но первому дистрибутивномузакону выражению (х, й х,) у (х«б Х«) '„: ...

у (х„й л'«). Исключением являются только всегоо-истинные выражен<аж Однако можно и их не исключать, если несобственную частичную конъюнкцию, катару<о мы получим, не беря ни одного члена, рассмагринзть как всегда-испшное высказывание. Конъюнктнвные члены приведенного выше, но развернутого выражения Шредер называет конституено<оми от Х„Х„,..., Х„, Доказательс~во этот> утверждения получаем следующим образом; сначала выражение, образованное из Х„..., Хо, приводим к конъюнктивной нормальной форме.

Так как значение истинности или лшкности высказывания остается неизменным, если отбросить истинный конъюнктивный член, то можно не записывать ге конъюннгивные члены, в которых в»<осте с Х содериси< си Х. Если, далее, используем правило, позволяющее вместо Х ',' Л' писать Х, то каждый из еще остающихся конъюнктивных членов становится дизъ<онкцией только различных членов ряда х„,, х„, х„..., х„. Если в нскоторой дизыонкции отсу<ствует как Хо так и Х<, то мы мажем эту дизъюнкцию расширить, приписав к ней всегда-ложный член (Х<б<Х<) и применив первый дистрибутивный закон, что не изменяет истинное>и или ложности высказывания. В результате каждый копъюнктивный член для любого < будет содержать идн Хо нлн Х<.