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

Затеи нам остается лишь из коньюнктнвных членоо, которые отличаопся только различным расположением своих связанных знаком <<' членов, написать только один. Тогда выражение пркнимает желаемую форму. Таким образом, мы получим для каждого высказывания, образованного из Х„Х,«..., Х„, выра>кение в «совершенной» кон оонктивной нопмольнои форме. Эта нормальная форма (с точностью до порядка конъюпктивных вли дизъюнктнвных членов] однозначна в том смысле, что два эквивалентных сложных нысказынання выражаются одной н той же нормальной формой.

Действительно, существует лля Х„ ..., Л; точно 2«"> различных выражений в нормальной форме, т. е. столько же, сколько можно образовать различных высказываний из Мтислттс н слалиеалий Детллительлые вллталил Указанная совершенная нормальная форма может быть использована различным образом. Она может послужи~ь нрежде всего для отыскания при случае болев простого лреовглавленпл для данного сложного высказывания. С этой целью приводят выражение к совершенной нормальной форме и упрощают его затем, применяя в соответствующих случаях следующее правило исключения: Хсд й Хсй, то есть (Х й Х) У?( лквпввлвн!лнв 'л. В качестве примера рассмотрим сложное высказывание АйАВ. Чтобы получить разложение по А и В, заменяем конъюнктивный член А формулой Л У (ВйВ) и раскрываем скобки по первому дистрибутивному закону.

Если напишем встречающийся дважды член АВ только один раз, то получим совершенную нормальную фоРму: АВй АВ. Если здесь вынеселс за скобки общий множитель А, то получим А (Вй В) и, по указанному правилу исключения, А. Таким образом, А является самым простым выражением формулы Лй ЛВ, В качестве второго примера рассмотрим выражение Ай АВ. Нормальная форма здесь имеет вид; АВй АВй АВ.

Здесь можно объединить первый со вторым н первый с третьим члены. Чтобы осуществить оба исключения, первый член пишем дважды: (ЛВ й АВ) й (АВ й АВ) . В результате исключения получаем Ай В. Заметим далее, что использованная совершенная нормальная форма дает возможность решить вопрос: выразимо лп некоторое высказывалпв, составленное ив ВСНВВНЫХ ВЫСиазмеаиий Х„Хт..., Хл, блл ПриМЕНИ- нпя знака отрядная? Оно выразимо так в том и только в том случае, если в совершенной нормальной форме рассматриваемого высказывании отсутствует коныонктивный член Х,УХ,У ... сс'Х,. В самом деле, если имеем некоторое высказывание, которое построено из Х„Х„..., Х без применения знака гприцания, та это высказывание истинно всегда, когда вместо Х„Хл,..., Х„поДставлаютсЯ истинные высказывания. Высказывание же, которое содержит в качестве конъюнктнвного члена Х,УХ,У ...

У хм этим свойством не обладает. Таким образом, указанное условие необходимо. С другой стороны, оно достаточна, ибо каж;сый член совершенной нормальной фоРмы, не Равный Х, ',' Хе У ... У Х„, можно выРазить без отрицания. Например, пишем: Х,Х,Х,...Х, в видо (Х,йХ,й...йХ)-+Х„ Х,Х,Х,Х,Х,Х,... в виде (Хе й Х, й Х, й... ) —: Х, ч' Х, ~/ Х, ~/ ., и т. д. Вследствие этого ровно половина из 2(ет высказываний, которые могут быть образованы из выражаются без отрицания. й З. донаюттельиые замечания к араблеие нсегда.истинности н аыиелнииостн Установленную в предыдущем параграфе совершенную нормальную форму для выражения, которое состоит из основных высказываний Х„ Хе,..., Х„, мы будем также называть кратко разложением виражелил ло Х„Х„..., Хт вз Исюслеяие вотоливеяий Доаоляиюелнте лалилвсия Пусть теперь нам дано некоторое сложное высказывайис, в котором содержатся, нроме Х„Х„..., Х„ еще основные высказывания У„Уи,.,, У .

И вэтом случае мы можем ~сварить и извесп>оп смйсле о разложении по Х„..., Хл. А именно, можно представить выражение в виде ко>гъюнкц>ли, у которой каис. дый конъюнктивный член является дизъюнкцигй выражения, зависящего только от У„У„..., Улю и одной из коне>питуент от Х„Хл,, Х,. Доказательство очень простое.

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

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

У„..., )', Здесь У„..., )'„, пусть обозначают определенныс постоянные высказывания. Вознннает вопрос: каким условиям должны узовлетворять У„ )'„ ..., )'„„ чтобы прн любам выборе высказываний Х все выражение было истинным? И еще вопрос: каКим условиям должны удовлетворять У„У„..., У..., чтобы выражение было всегда ложным? При ответе на эти вопросы мы принимаем для простоты и равным 2. При произвольном и решение протекает вполне аналогичным образом. Пусть разложение выра>кения по Х, и Х, будет: (А) Ф,(У„..., У,„)Х,ХлйФ,(~„..., У„)Х,Х, й О>,( „°, У„)ХоХ,йа',(У„..., У )ХХ,.

Мы можем предположить, чта все О члена действительно встречаппся в разлп>кении. Если, например, член с Х,Х, отсутствует, то можно присоединить выражение Ф,(У„..., У,л) Х,Х,, в катаром Ф,(У„,.,, У ) — какао-нибудь всегда-исгипное сложное высказывание. Мы утверждаем теперь: для того чтобы формула (А) для любых Х, и Х, было истинной, пе>бходимо и достаточно, чтобы было истин>смм выскпзывонпе: Ф,(У,,..., У„) йФ,(У„..., )' ) бс Ф„(У„..., У ) йФ„(У„..., У„,). Ясно, что это условие является достаточным.

Но зто условие н необходимо, нбо если бы, нанрнмер, Ф, (У„)'„..., У ) ае было истинным, то мы могли бы заменить Хл >>сениным пысказыаяннеп, а Х,— ложным высказыванием. Тогда (Л) стало бы эквивалеятным Ф,(У„ ..., У ), т. е. не истинным. Соатвегственным образам получаел> решение двойственной проблемы. Выражение (А) в том и только в гам случае выполнима для Х,,..., Хел если Вечцеычие еыскееыеениа Обзор всех гледсювиз оз Ванных цееыых вб У„ ..., У„ так подобраны, что справедливо бй ()'„ ..., )'ч,) )/ Ф,()'„ ..., У ) >ь> 'Р.()' .

)'ы) Ъ' Ф.()'. " )' ). й 9. снстенетнчеекнн обзор есех ехедетнна нз ленных цееыеон В 9 4 мы получили метод, когорый дает нам возможность находи>ь все сложные высказывания, являющиеся истинными в силу чисто логических оснований, н для данного сложного высказывания решить, принадлежит оно к этому роду или нет. Теперь возникает следующая задача> из данных посылок (аксиом) вывесит все следствия, ласкальку это возможна сделать, рассматривая высказывания лишь как нерасчленекные иелые. Предположим, по нам дава определенное конечное число аксиому(„о(„..., б(„'. На вопрос атом, представляет ли собою некоторое другое определенное сложное высказывание 6 логическое следствие из этих аксиом, можно вполне ответить с помощью прежних средств.

Это высказывание будет логическим следствием аксиом в том и ~олька н том случае, если (й й>й й,, йб() >6 является всегда-истинной логической Формулой. Например, заключению от А и А-ь В к В соответствует всегда-истинность формулы: (Лй(А- В))-В. Однако мы не имеем еще систематического обзора всех следствий, которые можно взвлечь. Получить таконой мы можем лишь с помощью совершенной коныонктивпой нормальной формы. Пусть в наших аксиомах встречаются основные высказывания Х„ ..., Х,. Мы представляем себе все аксиомы соединенными знакои й и возникшее таким ' Относцтельно уцотаебзенце немецких букв сы.

6 з. образом сложное высказывание разложенным по Х„..., Х,. Возьмем теперь какую-нибудь конституенту от Х„Х„..., Х„, которая не встречается а качестве конъюнктивного члена в эгой совершенной нормальной форме. Путем подходящей замены Х„..., Х„ истинными, соотае>стнснно лажными, высказываниями, можно превратить зту консгитуенгу в дизъюпкпню сплошь ложных высказываний, т. е. в ложное высказывание. С другой стороны, благодаря этой замененаша совершенная нормальная форма переходит в истинное высказывание, ибо кюкдый из ее конъюнктивных членов отличается от взятой нами конституенты тем, что по крайней мере в сдном месте пека>орый дизъюпктивный член заменен ему противоположным.