Гильберт, Аккерман - Основы теоретической логики (947372), страница 18
Текст из файла (страница 18)
В зтпй формуле выра>кение (х) 0(х) — о (х) Р(х) нижет быть преобразовано, путем использования формулы (б), в (х)Р(х]-х(х)6(х). Так как (х]Р(х). (Ех] Е(х), (х)0 (х) (Ех) 0(х), то искомая фпрмула доказана. Формуле (34) соответствует следующее правило: Если Я (х) — х ю (х) доказуема, то можно вывести так>не (Ех) М (х) — (Ех) сЕ (х). Именна, нз И(х) — хсЕ(х) по правилу,' получаеьп (х] (К (х) и ю (х)) не используя (34), (Ех) Ж (х) -и (Ех) 5 (х). Точно же так, как из (3() выводится формула (32), получаем из (34) формулу: (34') (х) (Р (х) 0 (х)) — ((Ех) Р (х) (Ех) 0(х)).
Формула(33)с (х)(Р(х]-- А) ((Ех)Р(х) А). Доказательствое (х) (Р (х) — А) есть сокращение дзш (х) (Е(х) Ъ' А). Далее имеет места формула: (х) (Р (х) ]у А] .(х) Р (х) Ч Л, которая доказывается подобно формуле (2б). (х) Р(х) = (Ех) Е(х), (х) Р(х) ', А (Ех) Р(х] ',с Л. Если теперь снова напишем сокращение —, то полу- чим (35]. Формула (Зб)с (Ех) (у) Р (х,у) — и (у) (Ех) Р (х, у). Это уже упоминавшаяся прежде формула переста- новки, о котпрой было также отмечено, что отношение следования справедливо в ней толькп в одну сторону. Одра>вел«не крвтеввнелкжявкти юв !08 узкое ккккслкяев преаикекнк Доказательство: Е(х, у) —. (Ез) Р(в, у) [подстановка в аксиому /) н правило 3'[, (у)(Р(х,у) — «(ЕВР(в, у)) [правило «'], Используя формулу (31), получаем: (у) Р(х~ у) — «(у) (Ев) Р(в у) (Ех) (у) Г(х у) — «(у) (Ех) Р(х, у) [по правилам т) и 3)).
б т, Провело замены; оарззевеняе аретявонокожяоегя Лзя некоторой форнуеы После того, как мы вывели ряд тождественных формул, останопимся елее на некоторых общих правилах, особенно важных для получения обзора всей системы тождественных формул. В качестве первого правйла мы имеем некоторое расширение правила ЧЕ Последнее гласило, что высказывания, которые находятся во взанмпои отношении следовлния и, таким образом, являются эквивалентными, могут быть заменены друг друтом.
Мы расширим это правила замены следующим образом. Прааила Х: Пусть >Д(х,у,..., и) и 6(х, у, ...,и) какие-нибудь формулы, которые содер>кат снобгдные переменные х, у,..., и и никаких других свободных псременных не имеют. Пусть, далее, 6 (х, у,..., и) 6(х,у,...,и) доказуемая формула. Если имеем теперь некоторую фориулу 6, в которой в качестве составной ее части один нлн несколько раз фигурирует Й (...) с какими-нибудь переменнымн вместо х, у,..., и, и если 2 есть формула, получающаяся нз В путем замены в ней л" (...) в некоторых нли во чсех местах на 6(...) в смысле нашего правила а3), то 6 2 является также доказуемой формулой.
Так как правило»'! мы уже имеем, то дсстаточно показать, что по обеим сторонам эквивалентности л (х, у, ..., и) = В (х, у, ...,и), перед л (х, у, ...,и) н перед 6 (х, у,... и) можно поставить одинаковые квапторы,(т, е., например, можно написать: (Ех)(у) л(х,у,...,и) (Ех)(у)6(х,у,...,и)). Достаточно показать это для одного квантора. Итак, покажем, что в наших предположениях формулы: (х) й (х, у,..., и) (х) В (х, у, и), (Ех)6(х,у,..., и) (Ех)Я(х,у,...,и) доказуемы. Из 4 (х,у,..., и)- 6(х, у,..., и) получаем по правилу Т': (х) (Я (х, у„, и) ° 6 (х, у,..., и)).
Затем, нспользун формулу (3?), имеем: (х) й (х, у,..., и) (х) 6 (х, у,..., и) и. точно так же, на основании формулы (34')> (Ех) й (х,..., и) (Ех) 6 (х,. -, и). В качестве дальнейшего результата к этому примыкает правило образования противоположности для формулы. Правило ХИ Из некоторой формулы, в катерли не встречается сокращений — «и, лротивоиололслая вй формула вбразутлся следующим образом: во-первых, знаки.вкв>би)ности заменяются знаками гуцвгтвавания, и наоборот; ва-вторых, знаки й и '/заменяются друг другом; в-третьих, злаки высказываний и знаки лреаикатав замвляютсл их атрибаниями.
Доказательство этого предложения происходит следующим образом. Для случая, когпа соответствующая формула не содержит знаков общности и существования, мы уже доказали это предложение в исчислении высказываний. Используя его теаерь н рассматривая комбинацию из кнанторов и их области действия как неразрывное целое, мы всегда можем достичь того, что отрицание всего выражения будет перенесено на самые наружные кванторы.
Если все выражение стояло пол одним кванторои, то зто уже с само- Папичкл Овогэстсенносллс Узкш игчлсленпс кдевпккыов 110 го начала имеет место. Изформул (33) получаем далее: (х) Ж (х) . (Ех) 9( (х), (Ех) 9! (х) - (х) фз! (х). Используя эти эквивалентности, мы можем передви- ' нуть отрицание с каэнтора иа область его действия.
С этими областями действия мы поступаем затем так же, как и со всеи выражением, пока, наконец, не дойдем повсюду до знаков выскааываний или предикагов. Описанный метод преобразования поясним примером. Пусть требуется получить соответствующее нашей теореме представление для формулый (х) (Еу) (Г(х, у) Эу (Ес) 6(х, у, г)). Из формул (33) сначалз следует, чгос (х)(Еу)(Г(х, у) э/ (Ег)6(х, у,г)) (Ех)(Еу)(Г(х,у) Ч (Ег)6(х, у, г)). Дальше получаем эквивалентное выражение: (Ех) (у)Р(х, у) у (Ег) 6 (х, у, г). Применяя частный случай нашего предложеняя, относящийся к нсчислениэо высказываний, н нранилэ Х, получаем: (Ех) (у) (р (х, у) й (Ег) 6 (х, у, г)) и, наконец, (Ех) (у) (р (х, у) й (г) 6 (х,'у, г)!. Это и есть н точности соответствующее нашему правилу представление.
5 а. Растнрвппыи пркпцпп дпоастпвпностм; пормальпыв фовмы Из правила Х! предыдущего параграфа можно вывесив принцип двойственности, который мы можем понимать, как расширение принципа двойственности, ' Черта сосрку кад формулоа--зто зкэк ее огрппзппя. (Прап Рсзд выведенного прежде для исчисления высказывчний Этот прнниип гласит: Из доказуелсой формулы, имеющей форму импликации илп уравнения, в членах которой не встречаются знаки — ь и, получается снооа доказуемая формула, если заменить повсюду знаки общности адношпенными зна.
коми-существования и наоборот, и, кроме того, обменять друг на друга знаки й и 'эг. Е случае импликоции нужно еще, помимо этого, переставить оба ее члена, ,йоказательство: Если 9( — Ю есть доказуемая формула, то Š— ь 9( также доказуема; вместе с формулой Е и' доказуема и формула 9( 6. Преобразуем теперь Ж и В по правилу Х! предыдущего параграфа.
Мы взаимно обмениваем, следовательно. друг на друга знаки общности и существования, равно как н знаки й и ',, и заменяем знаки для высказываний и предикатов их отрицаниями. Однако, так как речь идет о доказуемой формуле, то последняя замена может быть снова снята путем замены, по правилу подсг ановки, всех знаков высказываний и предикатов их отрицаниями. расширенный принцип двпйственностн дает нам сразу большое число тождественных формул, получаемых посредством такого дуэльного преобразования из ранее выведенных формул. Упомянем здесь важнейшие '. Формула(26'): (Ех) (Ай р(х)) Аб (Ех) р(х). Формула(29'):(Ех)(А!у Р(х)) АУ (Ех) Р(х).
Формула(29'): (Ех) (Еу) Г(х,у) (Еу) (Ех) р(х, у). Форму та (30'): (Ех) (р (х) э,с 6 (х)) (Ех) Г (х) '„' (Ех) 6(х). Формулы (29) н (29'), в связи с правилом Х, дают пам следующее правило: П р а ь и л о Х)1: Формула переходит в эквивалентную, если переставить в ней по произволу два или несколысо непосредственно следующих друг за другом знаков г нумсраикк формул выбрана так, чтобы опа указы.
вала, пэ какой Ранее доказзккоа то'кдественкоа формучн получается, по пркпдппу дооассвспностк, соответствующая формула. 1!2 у>те исв.юлелпе прс>ш:втвв Нврл>льиис авами общности, имеющих одинаковую область действия. Соответствующее правило спраседливо и для знаков существования. При рассмэтре>ши исчисления высказываний было показано.
что все сложные высказывания можно привести к общей нормальной форме, Мы можем представить сложные высказывания либо как конъюнкцию простыхадизъюнкпий, либо' как дизъюнкцию элементарных конъюнкций. Определенная нормальная форлса существует н в исчислении преднкатов. А именно, моэкно калсдсе выражение заменить токио, в котором все встречающиеся квапаоры саояа неоарицоемыми е начале, не будучи отделены скобками, так что все их области действия простираюпкя до конца формулы'.
пуля этой нормальной формы употребительно название влредвареннсй (ргдпехе) нормальной формыв. Преимущество этого 'нормально>.о представления основано на том, что выра>кение, стоящее за кванторами, вполне может рассматривтться, как принадлежащее исчислению высказываний. Приведение к нормальной форме происходит следующим образом. Прежде всего мы заменяем в рассматриваемом выра. женин сокращения — ь и их значениями. Применяя затем несколько раз правило Х( предыдущего пара. графа, мы легко достигнем того, что отрицания окажутся стоящими только над переменными высназываниями и переменньщн предикагами. После этого мы меняем обозначения связанных переменных таким образом, чтобы все кианторы принадлежали различным переменным.
Вь>есле (х) Р (х) я г(х) 6 (х) мы пишем, следовательно: (х) Р (х) ~Г (у) 0 (у) н т. д. ' Квп и в исчислении выс>свзыивипа, твт способ првлствв. ленив осиюпь ие олпвзиввви. Из возникшего таким образом логического выраже- ния мы получаем нормам,ную форму, ставя в начало формулы все кванторы в той гюследовательности, в которой они встречаются в формуле, а все остальное оставляя без изоенения.
Области действия всех кван- торов будут тогда простиратьсн до конца формулы. Допустимость последнего преобразования доказы- вается следующим образом. Пусть справедливость этого преобразования уже доказана для случая, когда рас- сматриваемое оыражение содержит меньшее число кваи- тпров. Если кванторы отсутствуют, то наше утвержде- нна тривиально. Если все выражение стоит йод одним квэнтором, то утверждение вытекает нз предположения: в таком случае мы должны сделать преобразование лишь для области действия этого квантора, содержащей уже меньшее число квэнторов. В противном случае мы берем первый кввнтор пщиего выражения. Он сем пе находится в области действия какого-нибудь другого квантора.
Применяя выведенные формулы: А я/ (х) Г (х) (х)(А ',/ р (х)), (х) р (х) уг А (х)(Г (х) >и' А), А й (х) р (х] (х)(А й р (х)), (х) Р (х) й А (х)(Р (х) й Л), или соответствующие форяяулы для знака существова- ния, мы можем достичь того, что этот квантор передви- нется в начало формулы, а область его действия будет простираться на всю формулу. Таким образом, мы приходим к предыдущему случаю, и справедливость преобразования этим доказпна вообще. Предпаренная нормальная форма обладает тем пре- иьсущестпом, что при обишхнсследованиях в исчислении преднкатов блзя.адара Ей 1<РУт подлежащих Рассмотре. нию формул может быть значительно ограничен.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
