Математическая логика. Шапорев С.Д (1019113), страница 50
Текст из файла (страница 50)
Гт(с, Д тлг,/У,х! Чаем гг Отееиа шяияя, ммеяия г В, =Г(с )их, =х, г О, =Гз(Г»(с)х)их, = У, г В, =с, их, =2; у, = х, =х, т.е. Г (с,)х вычеркиваем, у, = х, = у, с ~у вычеркива. ем, у, =х, =г, х)2 вычеркиваем. Тогда 0,0, =(Г(сДх,Г (Г (с,)х)у,с,Ц, 0,.0,:О, =(г,/х„г,(х„г,)х,)=(~(у)х,Г,(,21у,с,Д 0» =Й,~ум04Р»,0»,у»Г= 6(х,г(у,л(г), Отсюда В,О» = 'тзбйхз г»04мг г»Вя~хз 0»зуз 9»'зу»,0»зуз)= = 2Г (гЗх Г; (у х2 у с /2 у!х 2!ух(2) здесь г О, = Г (2)и х, = х, З»0» = Г» (У, х) Ф х» = У, г»0» = сз И хз = 2; Уз = хз = х, у~х вычеркиваем, у, = х» = у, с~у вычеркиваем, у, = х, = 2, х)2 вычеркиваем.
Следоват«льно, 0,0» =(ГзЦх,Г»(у,х1у,с,Ц О, 'Оз'Ог = згзЬз г»Ь»»зззуз)= (Гг(рз(х) Улзх Г(с,1У Гз(гя»2)* Оз = е»з(тз 0»зУ» ОззУ»)= »Г»(с!)х,с»)У х(гз. 0»0» =(»збз!хз г»0»~~г г»04~»Аз~Уз Чг!Уг О»~Уз)= =(Г.(Гз(Г(сз))с»)х,Гз(с,)У,Г»(21»,Г (сз1х,с ~У,х)2) »0, = Гз(Г,(Г,(с,))с,)их, =х, г О, = Г(с )их, = у, »,0, = Г;(х)мхз =2; У, =х, =х, Г»(сз(х вычеРкиваем, У» = х» = У, с»~У вычеРкиваем, У, = ха = 2, г(2 вычеРкиваем. Отеюд О О, =(Г (Г,(Г»(с,))сД~,Г,(с,)У,Г,(х12).
0» О„збг=(гз)уз»г)У»*ЦУ»)=(Г»М(х)У1х,~~(сзлу Гз(глг) В, =(0,(Умр,(У,,О,)У,)=(з(х,ЦУ, )»). 0»0, =(тб,~хи»,0,!х»,гзоз~х„рзЬмб»Ь Вз!Уз)= ~Р~(Р;(У)2(х,Г»(сз)у, Гз(х)2 У/х ~У х(2). » В, = Г» (Г»(у) 2) И хз и х, »,0, и Г; (с, ) И х, = У, !,О, = Г, (т) Ф х, = 2; у, = х, = х, у~х вычеркиваем, у» = х, = у, »~у вычеркиваем, у, = х, = 2, »12 вычеркиваем. Таким образом, Глава 9.
Исчисгмиие и диллгов зев Ввел =(Ге(Г,Яф,Г,(сДУ,Г,Цд. О, О,:О, =Ц»г,тг)»г,гг(»г)=(Гг(с,)к,сг)»,к(г), О = е1~)»п0~(У,В~)У )= (Угт,к)у,к!г) ОзОл —- (гг04кг ггВл1гтг ггОэ)тг г1г)уг Ог~уг Чг!Ут)= = (Гг(сг)к,сг(у, у)г, у!к, г!У,к!г). 10, =Г (с )ил, =к, 1 О, =с, ил, = у, г Ол = » и к, = г; У, = К, = К, У)К ВЫЧЕРКИВаЕМ, У, = Кг = У, г1У ВЫЧЕРКИВаЕМ, у, = кг = г,к!г вычеркиваем. Итоговвл подстановке 0,0, = (Г,(с,бк,сг)у,у(к). 4.10.2. а) воспользуемся алгоритмом унификации, описанным в Госдепе дб Р. =Г =(Р(дк. Гг(Г,(у)))Р(ОГт( ).
Г ( ))) ! 2=0, Ре — исходноемногкестео Оп=к, 2. Ре — неопиоэлемеитнос множество, Рл = »Г, Г); 3. сд сп 4. 0= (с!к), О, =-ОпО = У.')к), Р, = Р О, = !1Р(с к Г (Г (у))) Р(с Г (с! Г (и))); й =1, Р, — неодноэлемегпное множесгво, Ц = (т,Г.(г)) 2. кб Г,(с), 3. О=(Г,( )к), О, =О,О=()к,р;(с). ), Рг = РО =(Р(с,Гг(с),Гг(Гг(у))),Р(с,рг(с).Ггрг))), 1. 1г =-2, Е', — неолноэлелынтное множество, Р, = (!',(у),л); 2 ипГ(у); 3, В = (Г (у)н) В, = ОгО = ~!к, Гг (с) к, Г (у)и)1 Р, = 10 = (Р(г, Гг(с ВГг(Г(у))) Р(с Гг(с) Гг(Гг(и)))) = = (Р(с, Г,(с) Г,(Г(у))))! Р, — адноэлсментнсе множество, О, =(Г(!г,рг(с)жр(у)и]— !1ОУдля Г.
эуо Эисм 11 Огееиг, решения, «ежели б) Р„= Г=(РЩ,Рз(х)),Р~,у)). 1с = О, Р— ис«одное множеспю содержит два элемента, 0 = в; 3 В.=(Р()у)1 3, уцР(с); 4. О=(Р,(с)у), О, =ОЛО=(Р,(сЦ, Р~ — - РО, = (Р(Рг(с) Рт(х)), Р(Рг(с), Р<(с)))1 5. «=1, Р, — неодноэлементное множаатво, В~ =(Рт(х)Р,(с)), В, не содержит переменных; «онец алгоритма, исходное множеатво не унифицируемо. в) Р = Г=(Р(с,х)Р(с с)). 1. /с =О, Р— неоднозлементно, 0 =в; г. В.=(х,с); 3. хцс; 4. 0=ОД О, =Оде=((х), Р, =РО, =(Р(с,с)Р(с,с))=(Р(с,с)); 5, «=1, Р, — однозлементнаемиожеатво, О, ='61«) — НОУляя Г.
г) Р = Г=()г(сх,Р(х))Р(с,у,у)). 1. гг =О, Рэ — исхошюемиожеслюоэдержитдвеэвемента, Он = в; 2 В.=(.,у)1 3. хну; 4. О = (з(у), О, = 0 0 = («у), Р, = Р О, = (Р(с, х, Р(х)) Р(с, х, х)); 5. « =1, Рг — неодноэлемеитное множество, В, =(Р(х)х); 6. хб Р(х), исходное множество не унифицируемо. д) Р, = Г = (Р (и, Р, (х, у) Р(у, г )) Г (и, Р (с, т ))). 1. й =О, Р, — исходное множество содержит три элементе, Он = с; Глав 9 Ио~ слепце п дукатов г, О, =(и,у); 3. гтй у; 4. 8=()у$ О, =ОпО=Щ, Р, = РО, =(Р(и,Р(ки)) Р(гг, )Г(и, Г(г,к))); й =1, Р, — неодиоэлемеитиое лгножество, О, =(Р,(хи) г), 2, сй Г,(х,и); 3 8=(Р;(к,!гц 8,=8,8=(г(у,Р(к,и)к), Р = РО =(Р(гг,й;(х )) Г(гиР(х, ))Р(г,Р(с,й;(, ))))= = (Р(п,Р(х,и))Р(и,й*,(с,Г(х,и)))); й = 2, Р, — пеодноэлемектпге мнолгес гас, О.
= (х,г); 2. хйс; 3 О=(г(х), О,=О,О=(гт/у,Р(кгг)кс(к), Р, = Р О = (Р(и, Г (с, и)) Р(и, Р; (с, Р (х, и)))); к =3, Р, — пеодиоэлемепгпое мпожество. О, = (и,Р, (к и)). 2 ие Р (х и), исходное мвожество не уинфицируемо. 430 3 а) А= Р(х)чР~Яу)) Рт(к) Найлом НОУдлл псрвык двух ~левов формулы Л.
0 = (Р(удх], АО = Р(Р(у))ч Р(Г(у)) г Р (Г(у))= Р(Г(у))ч Р (Р(у)). АΠ— склейка А; б) А=У',(х)чрт(у)чР(Р(х)). 0=(Р(г)х), гп Г(г). Формулы Р,(х) п Р,(Р(х)) ие имеют НОУ, формула А не имеет склейкп; в) А=Г (к)чР (у)ч Г(Г (с))ч Р(х)чГН (х). 0=(Р (сйх), АО = Г (Р (с))чГ (у)чГ (г)чГ (к) — первая сюгейка А; О, =(Рт(с)с), АОО, =Р(Рг(с))ч Г,(у)чР (Р,(с)) — вторал склейка А, От — — (Рт(с)у), А00,8а = Р;(Р,(с))ч Г,(Га(с)) — тре- ть» склейка Л. згг чесп а. Опмпе шммя, элния 4А0.4.
а) В, =Р(х)чР(т), В» = Р (с)чР(х). Дщъюнюы имеют общую переменную х, звыеним ее на у, получим В( =Р(с)чР(у), Тогда А, = Р,(х), А = Р,(с), А = Р,(с), 8=8(х), В 8 ч В 8 = Р, (с)ч Рэ (с)ч Р (с) ч Р (у), геэ(„ )= Р,(с)ч Р,(у); б) В, =Р (х)чРэ(х,х), В, = Рз(с,Р(с)). Общих переменных в В, и В, щп. А, = Р (х х), А = Р (с Р(с)), 8 =ф!х), В Оч В О= Р(с)ч Р (с с)ч Р (с Р(с)), 8э =(Р(с1с), сб Р(с) Множество дизъюнктов (ВоВз ) не унифицируемо, следовательно, не имеет резсльвент; в? В,=Р(а)чй(х,Ь), В,=Р(х)чЯ>,у). 8=(а~х), В,бч В,О = Р(а)ч Яа,Ь)ч Р(п)ч й(Ь, у), гсз(В„Вэ)=фа,Ь)чэх(Ь, у). 4АОВ а) Ь; =У?х4У(Р(х,у) — э Ра(х У)) *ЭхМУ~Р(х У)ч Рз(х У)) Р, = эухМУ(Рэ (х, у)-е Р (х,у)) и эух8у(Рэ(х, у)ч Рэ(х, у)), Р, = ЗхЗУР,(х,у).
Отбросим кввнторы всеобщности, а переменным, связанным квэнтором существования, присвоим конкретны» значения: к=а, у=Ь, Рэ = Р(а Ь). Получим множество дизьюнктов Г эб(х, у)ч Рэ(х, у) Р (х, у)ч Р (к, у)Р (а,Ь)Ь которое надо проверить на противоречивость методом резал юлий. гез(Р (х, у) ч Рт (х, у) Р (а, Ь) =? О, = Ьа~х, ~ у), гез =Р (а,Ь)чРЯа,Ь)ч Р (а,Ь)= РЯа,Ь), гав (а,Ь) Р (к у)ч Р (х у))? О, = Цх Ь!у), гез = Р (аЬ)ч Р (аЬ) ч Р (а, Ь) = Р (а, Ь). Других резазьвент у множества Г = (Р,,ЄР) нет, поэтому резолютивный вывод нуля и» Г н» существует. Следовательно, исконное множество формул Г не противоречиво; Глава 9.
И чнслвннв л дммгов згз 6) Г=(Р(сиГ(сг)я' (сз))рг(с)Р(тхг(кЯ(ку, )чих,г)рг(к)ч г Р(у,г,и): Рз(к,и)ч Рз(х,у); РЯх,г) Рз(сися)Г =Ж ""г 1'з Ря Рз ° Рв). гег(Рг,р )= гез(Р,РгД~у))=? О, = 01' ~х), РгО, чуя~)у)6, =Рг(с,)чРг(с,)ч Р(г,г„и)ч чРз(спи)чРз(с„г)чР(сог)=Р(г ги)чр (сои) гР(сог)=?ю гек(Рмр,')=? О, =()г,У(к)и), РО, чРО, = Р(к,х,~(к)) Р(х,х,у(х))~ Р(с,,у(к)) ч Р (с,,к) = Рз(с,,~(х))ч Рз(спк) = Р' - (Р'Р.)4 о 0 =И ) 1;Огч Г О, = Рз(спс )ч Рз(сз,у (сз))ч Р (сос,)= Р (со) (с,)) = Г„. - (Р,,Рт)=? О, =Цх, Г(с,)гй Ь40, ч Рвб, = Р (со У,/(с~))ч Рз(сз, Г(сз)) Рт(сп?(сз)) = = Р(ему,у(сз))= Ьа. гез(ГЬ,Р, ) =? О, = (Г(с ) у), РО, ч Р, О, = Р(с,,~(с~) ~(с,))ч Р(с,,~(с, )~(с,))=01 в) Р, = Зх(Р(х) л пу (Р(у л ((Д(к) л фу)) л Игр(х))))) и мЗх(Р(х)лЛу(Р(у)лцз(х)лД(у)лЧгР( )))и и ЛхЛуЛг(Р(х) л Р(у)лС3 (х) г 0з(у) л Р(г)) х=а, у=Ь, г=с, Г = '1Р(а) Р(Ь) й(п) 1г(Ь) Р(с) 1 гез(Р(п) Р(сДп~с?= 0.
Исход- ная формула не выполнима. 4.!06 Метол резолюций в исчислении предикатов предетаалнет собой слщкную процедуру, состоящую из нескои ких зтаповг П Представление исходной формулы в виде множества дизъюнк юв. Час ь я. Опмги, ения, иыаиия 2 Докюательство противоречивости множества дизыоиктов, включающее в саби получение скулемовских форм исходных формул, унификацию формул, т.
е нахождение нужной подстановки, и доказательство противоречивости множества дизъюнктов в данном нонстантном частном случае. Первый этан основан иа том факте, чго есяи Г = (А„Лг,..., А„)~ — А, то фориула Л, л Аз л,. л А„— «А общезначима, т. е. истинна в любой интерпретации. Второй этап базируется на юм, что для того, чтобы доказать (А,, Аз... А„Я- 1, нулгно показать, что мнолмство формул Г, = Гс«(А)= (АпА,...,А„,А) противоречиво Противоречивость доказывается с помощью теоремы Эрбрана подбороьг конкретного константного частного случаа Механизм доказат зьства противоречиво сти мно«кесгва дизъюнктов похож на анилогичный в исчислении высказь«наний а2 рассмотрим первый пример Е = ((«гВ(Ьг, )и ВиА(бгЬ))л(«уиВ(ии,и)ч«ууьугА(гу,г))) — « -«((ВжВ(щс,и)««ВиА(зг,и,и))ч(пж«уиВ(Ь,и,ж) лж«УхВ(х,с,г)))= = (Р«л Рг) — «(гз о Г«) Получим по формуле А, л А л ...
л А„— «А множество )А«,А,...,Л„,А). В пашен случае (У«лГ ) — «(Г, ч Г,), т е. Л= Г«ч Г,, А= Уз лГ,. Тогда множество Г, будет иметь вид Г, = (Рп ГВ, Гм Р; ) г, =«угВ(Ьг,г)ч В~ А(Ь,г Ь) - =Ъ~А(Ь,г Ь)ч тугВ(Ьгг) м — Вг«УггА(Ь, г.,Ь)ч В(б,г,г)). Обоз«ганны значение г, которое существует в соотвезствии с первым кваитором, константой а, отбросив квантор существования. Тогда Г, = «77(А(ь,п,ь)о В(ь,,г)). Квантер всеобщноспз можно также отбросить в преаположенни, что доказательство проводится для всякого фиксированного Тогда Г,' = А(Ь,п,Ь)о В(Ь, гш).
Гмва В. Исллсл лне л длкагоа згз Аиавогиино Г, = ЗУиВ(лигг)чзУузУ А(у,у,г)и и эунэУуэУг(В(н, к, и) ч А(у, у,? )) или Р =В(и,н,и)чА(у,у,г). Г, =ЗиВ(эг,с,гг)лЗггА(гг,гг,гг), Р; = УвВ(в,с в)чОиА(и,и,ы) — = эУзгЭУгггВ(в с,в) ч А(и,ггдг)), Г,' =В(в,с,в)чА(л,н.н). Р'„=ЗггэУнВ(Ь,гт,гг)лЗгэУлВ(л.сщ), Рэ = эУвЗиВ(Ьгт,в)ч эУгЗтВ(л,с г)м и зУвЗыВ(Ь, ив) ч зУсЗпВ(ы, с, г) -= и Згг(эУэгВ(Ь,гг, в)чЭУгВ(н,с, ))и ЗиМизуггВ(Ь,н, и)ч В(л,с,г)) Обозначим значение и, кщ орое существует в соответщ вин с первым кввнтором, константой г! (н = 4), отбросив при этом «кантор существования.
Г, =ЭУвЭУг(В(Ь,гу,в)ч В(о',с, г)). Тогда Рэ' = В(Ь,гу, в)ч В(д, с, г) Таким образом, мно «ество Г, противоречивость которого необколимо проверит~, будет иметь вид Г=)А(гда,Ь)".В(б,г,г)В(н,гг,г г)'г А(у Иг)В(ос в)чд(ы н ы), В(бгу,в)ч В(д,с,г))=(СИСг,Сз,Св).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
