Гильберт, Аккерман - Основы теоретической логики (947372), страница 17
Текст из файла (страница 17)
Тогда гюлучаем в качестве новой выведенной формулы й — ь (х) 5 (х), у2) При тех же самых условиях относительно вида й и. 5(х) получаем из формулы В(х) — ой новую формулу (Ех) 5 (х) — й '. е) Правило переименования связдниых переменных Связанную предметную переменную, встречающуюся в формуле, »южно заменять другой связанной пере. менной. Эту замену следует производить одновременно во всех местах области действия и в соответствующем знаке общности или существования.
При этом предполагается, что после такой замены вообще снова получается формула. Если переменная, которая должна быть заменена, встречается одновременно в нескольких кванторах (с различными областями действия), то замену следует производить только относительно одной области. ' Иепользееииизя здесь система лкеиом для «еее» и чеуиееетпуетч. кагерея выражается фчриулзми ек П, » еж»же препилами 7, бича предзеи сиз Бериздеом.
7 с|О узкое отселение прыиеетее 1о! Сжтеиа тежаестеснныс 'формул й 6. Система тожаествеиныз феэмув Теперь посмо~рим, как с помощью приведенных основных логических формул и правил вывода строится вся система вби(вжачимых или, как лсы говорим также, тождественных форллул исчисления предикатов.
С одной частичной систелюй этих формул мы уже знакомы, именно с той частью, в которой встречаются только переменные высказывания. Для этой частичной системы мы раньше вывели формулы (1) — (20) и правила 1 — ЧП1. Мы называем эту частичную систему системой псожаегтсеииых формул шчисвеиия васказызаний. Прежде всего, на различных примерах мы изложим метод, которолсу нужно следовать при выводе формул. Эатем, как и раньше в исчислении высказ,шаннй, мы получим еше н новые правила вывода.
При этом используются выведенные раньше формулы и правила исчисления высказываний. Правило 1'. Пусть мы доказали некоторую Яор. мулу 6 (х), которая тгержит савбадиую переменную х. В таком свучсе доказуема также фврлсула (х) й (х) Доказательствое Из %(х), применяя привила П и Ш, получаем: х Ч х лз 21 (х), Х лу Х лу (х) 6 (х) [(по правилу Т)], Х лу Х [формула (3)], (х) а (х) (схема заклсочения). Правило З': Все свободные и связанные предметные переменные, встречающиеся в формуле, можно заменять другими переменными, если только следить за тем, чтобы в местах, в которых стояли одинаковые переменные, и после замены оказались одинаковые переменные, и в местах, в которых находились различные переменные, после замены оказались также Различные переменные.
Доказательство получаем, приченяя несколько раз правила ай) и а). Например, из основной формулы е) получаем формулу (у) Р(у) — » Р (х) следующим образом: (х) Р (х) — «Р (у), (х) Р(х) — «Р(в) (по правилу а2), (у) Р(у] — » Г(з) (по правилу е), (у) Р(у) — »Р(х) (по пращцЗЧ а2). Из правила З' следует, что правило .() остаегся в,силе, если в формулировке этого правила вместо х употреблять всегда у вли какое-нибудь другое пере- менное. Формула (21); (х) (Г (х) ~/ Р (х)) .. Доказательсглвос Х л»» Х [формула (3)], Р (х) л/ Р (х) (посредством подста. нонки), (х) (Г(х) л/Р(х)) (по правилу 1').
Формула (22)с (х) Р(х)- (Ех) Р (х). Доказательство: (х) Р(х) — » Р(у) [аксиома е)], Р(у) — »(Ех] Р(х) [аксиома 1)], (х) Р(х) — «(Ех) Р(х) (правило Ч), Формула (23): (х) (А л/ Р (х))-«А«Г (х) Р(х). доказательство: (у)(А Л/ Р(у))-«А ЛГ Г(х) [под- становка н аксиому е) н правило Гу], (у) (А»«г Р(у)) — »А л«' Р(х) (замена А на А). Используя сокращение — », мы можем написать также: (у) (А ЛЗ Р (у)) — » (А — » Р (х)), [(у) (А лу Р(у))де А] — »Р (х) (по правилу ЧП), [(у)(А л/ Р(у)) аА] .
(х) Г(х) [правило 1]; Утес нс моление предав«мое 102 асс мено мс«хдесмеенних Ьгд>с с> с 1ОЗ с помощью правила ЧП и правила 3 мы преобразуем зто выражение в (х)(А Ч Р (хИ вЂ « А Ч (х) Р (х). Формула (24): (х) (А — «Р'(х))--«(Л-.«(х) Р(х)). Доказательство: Эта формула получается из предшествующей посредством подстановки А на место А. П р а вил о [Х Ясли р>ормула 9(-- (6 — «>Ь (х)) доказуема, то доказуема и Формула сд — (6 — (х) 6(х)). При этом 'й и В не должны содержать переменной х.
Это правило является расширением правила 21). Вместо двух посылок можно взять так>не любое другое конечное число посылок. При этом доказательство вполне аналогично таковому для настоящего случая. Доказательство: м-«(5 — + 6(х)), >д — «(х) (ю — «6(х)) [правило 2)]. Отсюда, применяя формулу (24) н правило Ч, получаем искомую формулу.
Формула (25)1 А — «(х) (А Ч Р(х)). Доказательствое А — «А Ч В [аксиома(Ь)]. А — «А Ч Р(х) (посредством подстановки), Л вЂ” -. (х)(А Ч Р(х)) [по правилу 2)]. Формула (2б)с (х)(А'х/Р(х)) А~/(х) Р(х). Доказательство: Так как формула (23) доказана, то достаточно показать правильность обращения: А Ч (х) Р(х) . (х)(А ' Г(х)).
(у)Р(у)- Р(х) [из е) по правилуб'], А Ч (у) Р (у) — «А««сР (х) (по правилу 1Ч), Ахнс(х) Р(х) — «(х) (АЧР(х)) [по правилам1) из)]. Формула (27Д (х)(А — «Р(х)) (А — «(х) Р(х)). Доказательствое Эта формула получается из (26) таким же образом, как (24) нз (23). Формула (2ВД (х)(А6Р(х)) Ай[х)Г(х]. Доказательство: Сначала мы доказываем: 1. (х) (ЛйР(х)) —:Ай(х) Р(х). (у)(ЛйР(у]) . АйР(х)е Лй Г (х) Р(х) [формула (13)), (у) (А й Р (у)) — Р (х) (правило Ч).
(х)(АйР(х)) (х)Р(х) [правила 2) н Е)], ЛйР(х) — - Л, (х)(АйР(х)) —. А [правила Ч и 6)]. Путем использования форе>улы исчисления высказыва- ний (Х У) — ЦХ вЂ” 2) (Х- 1 й2]) и двукратного применения схемы заключения мы по- лучаем затем из последней и предпредпоследней фар>суп формулу 1.
11. А й (х) Р (х) †« (х) (А й Р (х)), (у) Р (у) -« Р (х). Отсюда получаем согласно исчислению высказываний: А й (у) Р (у)- А й Р (х), Л й (х) Р (х) †« (х] (Л й Р (х]) [правнла Т) и о)]. Из формул 1 и П получается искомая формула. Формула (29)с (х) (у) Р(х, у) (у) (х) Р(х, у). Доказательство> (г) (и) Р (г, а) — (и] Р (х, и) [подстановка в аксиому е) и правило о!], (а) Р(х, и) — «Р(х, у) [подстановка в аксиому е) и правило о'], (г) (и) Р(г, и) — «Р (х, у) (по правилу Ч), (г)(и)Р(г,и) . (х)Р(х,у) [прааило т)], (х) (у) Р (х, у) — «(у) (х) Р (х, у) [правила у) и 6)].
Так же почучается (у) (х) Г (х у) — «(х) (у) Р(с у) а поэтому и (29). Формула [ЗО)с (х) (Р(х) йб(х]) (х) Р(х) й(х) 0(х). системе те«кдеетеенник реомун еоз Узкое исчисление нкедккомье Доказательство: Сначала докажем: а) (х) (Р (х) й 6 (х)) — «(х) Р (х) й (х) 0 (х), (у)(Р (у) й 6 (у)) †« Р (х) й С (х), Р (х) й 6 (х] †« Р (х), Р (х) й 6 (х) — 6 (х), (у) (Р(у) й 6(у)) —. Р(х) (по правилу «е), (у)(Р(у)йО(у)) — «0(х) (по правилу Ъ'). по правилам у) и 3) последние две формулы можно преобразовать в (х) (Р (х) й 0 (х)) — «(х) Р (х), (х) (Р (х) й 0 (х)) — «(х) 0 (х).
Из обеих вместе получаем затеи: (х) (Р (х) й 6 (х)) — (х) Р (х) й (х) 6 (х). Ь) Доказательство формулы (х) Р (х) й (х) 0 (х) — « (х) (Р (х) й 0 (х)): (у] Р (у)-- Р (х), (у) С (у) †« 6 (х), (у) Р (у) й (у) 6 (у) †> Р (х) й 0 (х), (х) Р(х) й(х) 0(х)-«(х) (Р (х) йО(х)) [правила у) и б)], Из а) н Ь) получаем искомуео формулу. Формула (31]е (х)(Р(х) — «0(х)) — »((х)Р(х)- (х) 6 (х)). Доказательствое (у) (Р (у) — «О (у)) — «(Р (х) . 6 (х)), Р(х)-«((у)(Р(у) — «6(у)) — >6(х)) (по правилу Ч11], (у) Р (у) « Р (х) (у) Р (у) — «((у) (Р (у) — «6 (у)) -«О (х)) (правило Ч), (у) Р (у) й (у) (Г (у) — «О (у)) — > 0 (х) (пра вило «е!1), (х) Р(х) й(х) (Р(х) — «6(х)) — «(х) 6(х) [правила у) из)], (х) (Р (х) — > 6 (х)) — «Ях) Р (х) — «(х) 6 (х)) (правило 611). Формула [32]е (х)(Р(х) -С(х)) — ((х]Р(х) (х) 6 (х)). Доказательствое (х)(Г(х) .6(х)) есть сокращение для (х)[(Г(х) — >0(х))й(6(х) Р(х))].
Путем подстановки в формулу (30) получаеи: (х) [(Р (х) — '0(х)) й (0(х) — Р(х))] (х) (Р(х) — >6(х))й (х) (6 (х) — Р (х)). По формуле (31): (х)(Р(х) — >0(х)) . ((х)Р(х) — «(х)6(х)), (х)(6 (х) — Р (х)) †>((х) 0 (х) -« (х) Р (х)). Мы имеем, таким образом, три формулы вида: 6 Фйб, и>- (Ь вЂ” 6), 6 — «(6 —.%1). Отсюда можно вывести вд . (В .6). Но зто и есть наше утверждение, если мы заменим т(, еб, 6 их зна- чениями. Формула (33)с а) (Ех) Р (х) (х) Р (х), Ь) (Ех) Р (х) (х) Р (х), с) (Ех) Р (х) (х) Р (х), б) (Ех) Р (х) (х) Р(х). Доказательство (ЗЗа]е (у) Р (у) Г (х], Р(х)«(у) Р(у) [по формуле (б)], Р (х) — «(у) Г (у) [заиена Г (х) на Р (х)], (Ех)Р(х)- (х) Г(х) [по правилам 1) и З)]. Это есть наполовину формула (33а).
Их) (Еу) Р(у) [из аксиоьеы ])], (Еу) Г(у) — Г(х) [по формуле (б)], Системе тождественных фоямул !от Узкое и численно иуедииотое 1 па (Ех) Г(х) . (х) рт(х] [ссравила 7) и б)[, (х) ус(х) — (Ех) Г(х) [па формуле (б)[, (х) Р(х) — х(Ех) Р(х),[замена (Ех) Е(х) па (Ех) Р(х][. Это вторая половина (ЗЗа). Доказательство (33Ь)с Л Л: Р(х) ° ]с(х) (ссутем подстановки), (х] (Р(х) Р(х)) [правило 7')].
Используя формул> (32), получаем отсюда: (х) Р (х) (х) ут(х), (х) Е(х) (х) Р(х) [путем использования (Х У] —: (Х У), (ср. формулу (2б), стр. 27). Путем подстановки в (ЗЗа) получаем: (Ех) Е(х) (х) ев(х), следовательно: (х) Р(х) (Ех) Е(х). Это и есть формула (ЗЗЬ). Из (ЗЗа) и (ЗЗЬ) получаем также формулы (334) и (ЗЗс), так как нз И ю можно получить т] ю. ФОрМуяа (37)с (х)(Р(х) .
0(х)) — ((Ех)Р(х] — (Ех)0(х)). Даказплгельсшвпс Из формулы исчисления высказы- ваний (А-и В) — о (Ви А) получаем путем подстансвки ( Г (х) . 0 (х)) — и (0 (х) — и Р (х)), (х) [(Е(х) 0(х)) (0(х) Е(х))) [пп правитУ 7'П. Из последней формулы получаем, используя форму- лу (31): (х) [Р(х) — о0(х)) — >(х) [0(х) — Р(х)1ы Прн вторичном использовании формулы (3! ) и правила Ъ' получаем отсюда; (х) (Е(х) — 0(х))- ((х) 0 (х) (х) Р(х)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
