Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 33
Текст из файла (страница 33)
(Чх (А (х) — ~ В (х)) »- ЗхВ (х)). Теперь применим схему (р); переставив еще раз посылки, получим искомую формулу (12). В формулах, которые мы выводили до сих пор, формульные переменные встречались всегда не более чем с одним аргументом, а фигурировавшие в них кванторы всеобщности и существования всегда стояли отдельно друг от друга.
Формулы, следующие далее, будут касаться того случая, когда упомянутые кванторы появляются в паре. Формула (13): ЧхЧуА (х у) ЧуЧхА (х у). Из обеих импликаций, на которые распадается эта эквивалентность, нужно вывести только одну: (13а) ЧИЧУА (х, у) — ~ ЧуЧхА (х, у), так как вторая получается из нее переименованием связанных переменных и подстановкой А (Ь, а) вместо А (а, Ь).
Для того чтобы получить (13а), мы будем исходить иэ формулы ЧуА (а, у) -»- А (а, Ь), которая получится из формулы (а), если в ней вместо именной формы А (с) подставить формулу А (Ы, с), что даст ЧхА (Н, х)-+. А (д, а); а затем здесь надо подставить Ь вместо а, далее, а вместо а и, наконец, переименовать переменную х в у. Применение правила (6) даст нам ЧхЧуА(х, у) — ~ЧхА(х, Ь). Теперь снова подставим а вместо Ь и переименуем в правой части переменную х в з; тогда получится ЧхЧуА(х, у) — ~-ЧеА(е, а); применив схему (а), мы получим формулу ЧхЧуА(х, у)-».ЧхЧзА(з, х). Теперь, чтобы получить (13а), достаточно переименовать переменные в правой части, а именно: сначала х в у, а затем з в х.
Формула (14): ЧхЧуА(х, у)-+ ЧхА(х, х). Как и при выводе формулы (13а), сначала получим формулу ЧуА (а, у)-+. А (а, Ь). Затем подставим в нее а вместо Ь: ЧуА (а, у) »- А (а, а). Теперь, применив правило (6), получим формулу (14). Можно построить двойственные переводы выводов формул (13) и (14), и это даст нам следующие две формулы: (Формула 13'): ЛхЛуА(х, у) ЗуЗхА(х, у) (Формула 14'): ЗхА(х, х)-»-ЗхЛуА(х, у). (Формула 15а): ЧИЧу (А (х) А В (у)) (ЧхА (х) А ЧуВ(у)).
Эту формулу мы получим, воспользовавшись формулой (6); сначала мы переименуем в ее обеих частях х в у: Чу(Ад«В(у)) АЬЧуВ(у). Теперь подставим А (а) вместо А и переставим в правой части члены конъюнкции; это даст нам Чу (А (а) й В (у)) ЧуВ (у) х А (а), а затем, применив правило (6'), получим ЧхЧу (А (х) й В (у)) Чх (ЧуВ (у) А А (х)).
С другой стороны, из формулы (6), подставляя сначала С вместо А, затем А (а) вместо В (а) и, наконец, Чу В(у) вместо С, мы получим Чх(ЧуВ(у) дсА(х)) ЧуВ(у)8~ ЧхА(х), откуда, переставив в правой части члены конъюнкции, получим формулу (15а). Совершенно тем же способом, каким мы вывели формулу (15а), можно вывести формулы, получающиеся из (15а) путем замены квавторов Чх, Чу одним из наборов Зх, 3у, или Чх, Зу, или 3х. Чу, а также и те четыре формулы, которые получатся из них, если конъюнкцию заменить дизъюнкцией.
Для вывода, наряду с формулой (6), необходимо привлечь формулы (10), (5) и (8) и воспользоваться правилом (6') с квантором всеобщности или же с квантором существования, в зависимости от обстоятельств. Все зти восемь формул мы будем называть «формулами (15)». ВопРОсы систематики »57 1гл. гт исчисление пгедикатов Перечислим — без указания вывода — еще ряд формул: (16а) 7х (А (х) -». В) (ЛхА (х) — ~ В), (16Ь) Зх(А(х)-»В) (ЧхА(х)-» В), (17а) зх (А (х) В (х)) -» (1зхА (х) ° 'ФхВ (х)), (17Ь) 'Фх (А (х) В (х)) — 1- (ЗхА (х) ЗхВ(х)), (16) Зх7уА(х, у)-».7уйхА(х, у). Наметим также вкратце выводы двух формул, представляющих собой известные аристотелевские фигуры силлогизмов ЪагЬага и дагй. Формула (19): )7х(В(х) — 1-С(х)) — » ('Фх(А(х)-» В(х)) — з-Ух(А(х)-» С(х))).
Формула (20): Чх (В (х) -~ С (х)) -». (Зх (А (х) дс В (х)) -»- Зх (А (х) й С (х))). Для вывода формулы (19) мы будем исходить из тождествен- ной формулы (В-»- С)-» ((А-». В)- (А-» С)). Подставим в нее А (а) вместо А, В (а) вместо В, С (а) вместо С; затем, применив правило (б), получим 7х (В (х) — ». С (х)) »»7х ((А (х) -». В (х)) -» (А (х) »- С (х))), С другой стороны, из формулы (11) подстановкой получается ~х ((А (х) — » В (х))-~ (А (х) — » С (х)))-».
(~х (А (х) -» В (х)) — 7х (А (х) -». С (х))); полученные формулы в сочетании друг с другом дают по правилу силлогизма искомую формулу (19). Совершенно аналогично проте- кает и вывод формулы (20); единственно лишь вместо использован- ной выше тождественной формулы нам куя<но будет взять другую формулу: ( — » С) -э (А й В -»- А 8~ С), а вместо формулы (11) использовать формулу (12). 4 4.
Вопросы систематики 1. Понятия 1-тождественной формулы и формулы, тождественной в конечном; дедуктивная аамкнутость совокупности тождественных формул; непротиворечивость исчисления предикатов; вопросы полноты. Обилие представленных здесь формул не требует для своего запоминания никаких особых усилий со сто- роны памяти, поскольку зги формулы выражают всего лишь ту мысль, что с обобщенными конъюнкциями и дизъюнкциями, кото- рые изображаются кванторами всеобщности и существования, можно обращаться в точности так же, как и с обычными конъюнк- циями и дизъюнкциями.
Эту мысль можно сделать особенно отчетливой, если отнести формулы (1) — (20) к индивидной области, состоящей только из двух индивидов (мы обозначим их символами 1 и 2). Будем вместо А (1), А (2), В (1), В (2) и т. д. писать Аг» Аз» Вп Вз,..., а вместо А (1,1), А (1,2),... Аы, А„,... Тогда формулы (1) — (20) перейдут, как легко убедиться, в тоз» дестееннме формулы исчисления высказываний, в которых Ап Аз, Вп Вз, Аы, Аы,... будут играть роль независимых формульных переменных.
Например, формула (2) перейдет в формулу 1(А»дсАз) "А, ~/ 1Аз которая соответствует правилу замены для отрицания; форму- ла (5) перейдет в (А Ч В,) й (А ~/ Вз) А ~/ (В, 8» Вз), которая является одной из формул закона дистрибутивности; формула (7) перейдет в (Аз й В,) й (Аз А В,) ° (А, 8~ Аз) Ь (В1 <~ Вз)~ формула (11) в (А»'В») я" (Аг-~ Вз) -».(А18с Аз-~ В» й Вз) ° а формула (14) в (А,» АА,з) 8с (Аг» й Агз) -» (А,» й Азз). Этот факт не должен нас удивлять. Ведь формулируя нашу систему основных правил, мы выбрали формулы и схемы для кванторов всеобщности и существования как раз таким образом, чтобы они получались из формул и правил для конъюнкции и диаъюнкции путем перехода от конечного числа членов к некоторому продолжению на произвольную, конечную или бесконечную, индивидную область.
Поэтому, если мы применим формулы исчисления предикатов к индивидной области с заданным конечным число индивидов, то аффект произведенного предельного перехода ликвидируется и мы снова вернемся к формулам исчисления высказываний. ВОПРОСЫ СИСтЕМАтИКИ 159 игл исчисление пРедикАтОВ Это рассуждение, вместе с его итогом, мы хотели бы сформулировать более точно. С атой целью мы введем понятие 1-тождественной формулы для конечного, отличного от нуля числа 1. Формулу исчисления предикатов мы будем называть 1-тождественной, если она, будучи естественным образом проинтерпретирована в индивидной области, состоящей из 1 объектов, при любой подстановке вместо входящих в нее свободных индивидных переменных (если таковые имеются) переходит в тождественную формулу исчисления высказываний. Эта интерпретация предикатных формул осуществляется следующим образом.
Рассмотрим 1-элементную индивидную область, элементы которой обозначены цифрами 1,2,...,1. Выражение ЧхЯ (х) будем понимать как коныонкцию Я (1) йЯ (2) ~ ... б~ Я(1) ° а лхЯ (х) — как диаъюнкцию Я (1) ~/ Я(2) ~/ ... ~/ Я(1). Ревультирующая формула должна быть тождественной в том смысле, что всевозможные элементарные формулы, встречающиеся в ней, такие, например, как А, А (1), А (1, 2), В (2, 3), ..., д олжны рассматриваться как независимые формульные переменные. При подстановке вместо свободных индивидных переменных в качестве их допустимых значений должны рассматриваться только индивиды 1,2, ...,1; в случае, если формула содержит только связанные индивидные переменные, никакой подстановки производить не требуется.
Рассмотрим в качестве примера формулу чхА (х) '/ 1 А (а). \Т О является 1-тождественной, но не 2-тождественнои. Деиствительно, если рассмотреть эту формулу в одноэлементной инди дной области, то получится формула А (1) ~/ 1 А (1), которая является тождественно истинной, в то время как в двух- элементной индивидной области получаются две формулы: (А (1) & А (2)) ~/ Ч А (1) (А (1) Ж А (2)) ~/ ~ А (2), которые обе не являются тождественно истинными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
