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