Математическая логика. Шапорев С.Д (1019113), страница 17
Текст из файла (страница 17)
Сначала ~ — АлВ лл — ) (хауах)м~ — Ал О-т А Теперь по правилу контрпознпнн *г Дано Р~- А — ь О, Г(- О. Возьмем аксиому (х -+ у) -ь (у -ь х) а проведем следуюшую замену переменных. лл / ((х — з у) — г (ту — з х))н ~- (А -+ В) — ь (В -ь А). Дпв достижения *У конечного результата необходимо двюкды применить правило прссюго ! — А-+ В;) — (А-ь В) а(В -ьА) (-В;)-В-+А заюпоченнв — — и ) — В -з А ~- А Пример 4, Докююь, юа Г= (А -ь В)~ — (С' — ь А) -з (С -ь В). Дано г( — А-чВ. Используем первую аксиому х — ь(у — ьх). л в,с Подстановка — ) (х ь (у — ь х)) ° ~ — (А-ь В)-ь (С вЂ” ь (А -ь В)). По правияу простого заключения ~ — А — ь В; ~-(А -ь В) — ь (С -ь (А — ь В)) ~ — С -ь (А — + В) Чеаш а Мегемвпш акал лоп кл ~-Ал  — ьЛ вЂ” наконец, по правилу — А е Ал В ~- А.1 — А -з А л В ! — АлВ простого заключенна 2.3.
Теорема дедукции и другие законы исчисления высказываний Теорема дедукции Докажем зту теорему подробно методом математичеакой индукции па длине вывода. Пусть Г С = гА,. ц,..., А„з — вывод из исходной совокупности формул. Сначала покажем, что лл» любога подобного вмвода справедлива Г1 — Се А, . В дальнейшем в роли Аь, которве может быть получена прн выводе из Г,С любым дозволенным методом, может выступать А . При и =1 вывод формулы А из Г,С имеет вид Г,С~ — Аш т.е. формула Л совпалает а А, Согласно определению вмвода возможны трн случая: П А,пГ. 2. ч — докюуемал формула из множества Г. 3. А, мС.
В первых двух случавх имеем Г1 — гч . Тогда вывод из Г можно написать е виде Г; х, А, е(с — ь А,~ С вЂ” ь А, . таким обрезом, р ~' (г,ц-л,Ап л,) — С е х . В третьем случае имеем зч =— С, и надо доказать, что г~ — с -е с, но формула с ь с доюшуема в любой совокупности формул. Правило введение импликации носит название лмаремы дедуегии и имеет Г,С~-А следующий внд: ' Д-С-ьА' бшш г.
Иом пенис высказываний гот ггействитсльно,~- С,(- х-+ (у -з «).(- С -ь(С -з С) )-С;~-С- (С- С) (-С-ь С 44усть тспеРь теоРема спРаведлиеа пРи г < и — 1; докажом, что оиа щграведлива н при г = н . Здесь вывод из исходного множества формул нмсег иид Г, С = (Ло Л,..., Л, ). Однако теперь лля формулы А„появнлиш. дополнительныс возможности, а имюшо. она может определяться как: В .4„еГ; 2.
˄— доказуолтя формула; 3. А„мС; 4 А, получавтся по правилу простогп закшпчени» из любых двух ~- ~;~-А,- Л„ предшествующих ей бюрьгул, т. е,, причем вторая ~ — Л„ формула в правияе простого заклю ~ения гобозиачим ес Л,'г лолзкна нмшь вид Л, = 4 -з Л„. Дяя первых трех случаев доказательство гголиосггио аналогично уже рассиотрешюму, только индекс "едипнпа" иапо замсншь на а. В четвертом случае Л„получено по правилу простого заключенна из А, и А =г4 -з А„.
При зтом вывод из Г может быть таким Г = (г~, А,,..., Ль): Л,, А„..., г~„Л вЂ” з (С вЂ” з Л,), С -ь Л Р ~ (г>Я~ 4- (с 4) глиюсг Воследняя формула в выводе имеет такой вид в силу лопущенай пункта 4. т.к ~ — С-+А,,аА =А,-гд„. Возьмем теперь вторую аксиому (х -+ (у -ь х)) — г ((х -з у) — з ( т -ь х)) и г.л„х„ спелаем в ней подстановку (((х О (у — з С)) з ((х г у) г (х ь Г))) И со 1 Ма гсма пг ческая полые Получим доказуемую формулу ~ — (С -ь (г( -+ А„))-+ ((С вЂ” ь 4) ь (С вЂ” ь А„)). Тогда по правилу сложного заключения /-С-э (;/-С-е((- (,Ц-(С-ь(,(-эА„)). ((С-е.()- (С-э ~,)) ~-С-е Д Итак, доказано, что Г~- С-ь г(,, причем А, может определяться четырьмя указанными способами, Вернемся теперь к началу теоремы. Пусть Г, С) — А.
Тогда Г,с;л(,А„...,э(, иА, т.е. роль,(, играет А. Тогда ло предыдущему доказательству Г)- С вЂ” э А и теорема дедукции доказана. Обобщение теоремы дедукции ф,А„А„..., Ц-А Справедлива формула,... Докажем ее. ~-л( — ь(А, -«(А, -е...(г(, — ь А).. Итак, Г = (г(, А,..., Ь', д Г! — А. Но Г = ( д, А,..., г(ч ) гз (А„) = Гч „А, и Гс мА„~-А. Тогда по теореме дедукции справедливо Г,,~ — А„-е А. Ангщогично множество Гьч можно представить в виде Г„, =Ге „А,, тогда Г ~ — (,, -э(А, -+А) и т.д Применив зту процелуру и раз, получим ~ — г( -ь (А, — э (А, — ь ..(А„-ь А)..)). ~~- А В час.:ном случм при и =! получим Эза же формула ~-,~ -+ А получается и из простой теоремы ледукции, воли Г,С= (д), Закон перестановки посылок ~- (А — ь ( — С)) -+ ( — з (А — э С)) .
Рассмотрим множестпо формул Г = (А — э (В -э С), А, В). Из этой совокупности формул после применения дважды правила просюго Пмю 2 Исчисленю вьмкязнюнчв Нключеиия находим: Г: А ь ( — ь С) А, В,  — з С , С . Теперь применим обобщенную Ив г Ис й4ч1-" теорему лелукпии; -г"-ы-а)-(л-(л-с)) ИЗ закона перестановки посылок следует правило перестановки посылок в ~-л-ь(в-ь с) доиазуемых формулах,, которое получается по правилу ~- В -+ (А ю С) ' пргитого заключения из формул ! — А е ( — ь С) и )- (А ь (В -+ С))ь ( — г (А -е С)).
Закон соединения посылок ~-(Л-ь(В- С)) (Лл  — ь С). Пусть множеств> исходных формул Г = (А — ь (В-+ С) Ал В). Получим вывод всек необходимых нам формул из этого множества Г:А-+(В-+С)АлВАлВ-+А,лл — еВ, В ~-мЦ-л в в .сппз ' .еппз' ' ппз '-л вб-л В л (-Арл (В с1 ~-В,)-е с Ил- с Ис Отсюда на основании обобщенной теоремы лелукцин полу ~иьк л, А -ь (В -э С) А л  — С Из этого закона при уловки, что 'йем У. Дтагемапнеемсг логика по (и А -+ ( — у С), по правилу простого заключения немедленна получается (- А -У (В -У С) правило соединении посылок ~-Алв — ус Закон разъединения посылок ~- (А л В -У С) -У (А -+ (В -ь С)).
Рассмотрим систему формул Г= (Ал В-+ С,А,В) и сначала покажем, что из иее выводима формула Ал В. Пусть Я вЂ” любая выводимая формула, тогда Г ' А — + (В -+ С) А, В, Я, Я, А-у(Я-уА), Я вЂ” +Л,(Я вЂ” «А) — у((Я вЂ” уВ)-у(Я вЂ” уАлВ)), И) л. б ы) ппз л,) Ъ,) <В л,я ) )УУЧ-л Е л) ) к л ) (Углам',;(и л КЯ+в) )в л в)) .У г:,у  — у (Я вЂ” у В),Я вЂ” у В, (Я вЂ” у В) — у (Я -+ А л В) ппз и-. улы вн= л Ыя-ув) ~л- л я) Я вЂ” уАлВ , АлВ ппз ' „ппз 'Гя- л)-)я в) )л л л) ыл)-л л в )-я- л в )-л в Итак, формула Ал В выводима из формул Ал  — ь С,А,В. Прололжиьу вывод до применении теоремы дедуки и; Г: А л В, С,(А л В -+ С) — ь (А -у (В -у С)). Отсюда следует н юсупа е в л у умлу )-л в)-л л-е л лв слв(-с ))-и )л л-с) ~л )в сб ')- А л В У С правило разъединения посылок ,ибо ~- А — У (В -У С) ~ — А л В -у С,)- (А л В -у С) — у (А — у ( — у С)) ~- А-У (В-+ С) Рассмотрим теперь несколько примеров на докаюгельство формул исчисления вьусквзываний с использованием всех ранее рассматренньй теорем.
Плавя д. мс«иалсиие емскаэнеаннй гг! Пример П Доказать допустимость следу!ащего правила вывода; Г,Т(- А — правило для доказательства теорем от противного. Г,+В Пример 2. Вывести следующую сскленцшо (А -л В, В -л Сб — А — л С . Итак, Г= (А-с В В ь С). следователю!о, Г) — Ао Ву) — В-т С. ~- А †В,(- В -л С Тогда по правилу силлогизма ( — А — лС Пример 3. Вывести следующую ссквенцню (А — л ( — л С) —  — л (А — л С).
Из исходного множества результат следует немедленно, сопи ~ — А-л(В-л С) ~- В -л (А — у Г) вгюпользоваться правилом нереста! онк по ылок Пример 4. Вывести следу!ощую секвспцпю ~ — Ао А — закон исключенного третьегО. Исходное множество не задано, следовательно, оно может быть произвольным. Выведем сначала две вспомогательные формулы При лаказательстве новых правил, естественно, могут использоваться уже известные правила вывода. Пусть А= (А), тогда очевидно, что + А Воспользуелшя уже рассмотренным прашшом расширения А~ — А — ' —.
По условию Г, Ь) — А, по правилу сведения к противоречшо Г,+А' Г,~- А;Г,~- А Г, Ь| — А, Г, + А в июнем случае получим, ибо Го!;)- Г,В,+ ГоГ =Г,В,А=ГцгВчэА. Последнее необходимое правило Г.А,б(- удаления отрицания †-г- . В нашем случае ' . Итак, доказано 1)- А ' Г, (- В ' Г, Г) — А походное правило вывода г,+в' г!2 Чясм Г. Магемагячесюялгкняа х-э (х-+ у) и хо у — > хл у, Воспользуемся патой, девятой и шестой аксиомами.
Итак, замена в пятой аксиоме чу. ) ((з -э х)-+ ((х — э г) — э (3 — э х л у))) и ~- ((х ч у — э х) — ь чу. — ь(Гхчу-ту)-+ (хчу — ь хну))),теперь вдеватой — ) ((х-ь у)-+ ~ — ь х))м~-(х — ь хну)-е (хч у — ь х) . У Применим правило простого заключения и шестую аксиому в качестве посьшки теперь сделаем подстановку в доказанной формуле — ) (хч у -ь х)и~ в ххо у — э у, наколем применим правило сложного заключения, получим: ~ — х и у -э х;~ — х ч у -ь у ~„— (х ч у — э х) — э ( ч у — ь у) — (х и у -+ х л у)) -хчуехлу Таким образом, доказана одна из двух вспомогательных формул.
Докажем теперь вторую из пик. Ддя этого используем ггервую и девятую аксиомы, сделав в них следующие замены переменных: — ) (х -+ (у -э х)) и ~ — х -ь ~ — ь х) и — ) ((х-ь у) — ь(З вЂ” эх))— н — (» — эх)-ь ~-» у). .г Теперь применим несколько известнык правил вывода. По правилу ~ — А — ьВ, — эС силлогизма получим ~ — А — эС па рива 2 Исчлсл нл вмсызивллна В дальнейшем доказательстве используются две полученные вмводпмые формулы. Сначала сделаем в них подстановки — ) (х -ь (х ь у))— = ( — х -ь (х — ь у).
~ — А -ь (В -+ С) Затем применим закан соединение посылок , ~отде ~ — Ал В-ь С ~- х ь (х-+ у) ! — А — ь В;  — + С . По правилу силлогизма 1- получим — хох — ау ~- А -+ С вЂ” х о х -ь х л х; х л х ь у ~ — Аь В ; правило «антрпознции , даст — хох-ь у ~- — ьА — х о х -ь у Правило снятия ~-уч хох двойного отрицание ~ — Ае В ~- А-ь(В-+ С) по правилу соединения посылок в нашем случае ) — Ал В-+С вЂ” х-ь (х-е у) ~-А — ьВ 1- ; по правилу снятия двойного отрицания — хох — ту ~-А-ь В будем иметь ~ — хо х — Ь у; наконец, по правилу разъединения посылок 1САЛ — ь С получим доказуемость второй вспомогательной ~ — А-+( — ьС) — хл ха у формулы ' Г" 7" ДЗ !тл Ча и! Мягемагячесяая логика — у-ь хох позяоллег получить доказуемую «юрмулу ~- у -+ х о х Воспользуемся теперь правилом удаления импликации Г )- А -+ В; Г,~- А Пусть Г, = (Вб где Л вЂ” любая локазуемая г„ г,)- в формула.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
