Математическая логика. Шапорев С.Д (1019113), страница 51
Текст из файла (страница 51)
Иссведуеи тго мззожество на выполнимость с помощью метода ре- золюций, воспоаьзовавшись обозпалениями раздела Др, Найдем гес(С,,С,). С, = В(н,и,н) ч А(у, у„.), С, =В(в,с,гг)чд(и,и.и), О, =(и(эг), С О, чС О, =В(гггггг)чА(у у г)ч В(п с и)ч А(п и и), О, = ~!и), С О Ог чСзО От —— 0(с с с)чА(у уз) г В(с с с)ч А(ссс)= = А(у, у,. )ч А(с,с,с) Вычислим теперь склейку этого диэъюнк- та О, = (с(у,сЯ. Склейка гез(СзСэ) равна А(с с с) = С,.
ггг(СоС,)= т С, = А(б,п,б) г В(Ь,г,г), С = А(с,с.с). О, = (с(Ь,с(а), С,О, чС,О, = А(с,с,с)ч В(с, с)чА(с,г.,с), гез(С,,С,)= С, = В(с,г,г). ггб Ча и ||. Огвегм венин, |мгаюм гег(С|,С„)=Р С, =В(А,~,г), С =В((,г,г), О, =(~)г), С„О, чС О, = В(с,с,г)чВ(с,г,г), От =(ф), гег(С„,С )=О. Множества формул Г противоречиво, такил| обратом, исходив| формула Г истинна. б) доказательство проводитсн по схеие пункта в. В = (чнВвА(Ь,и,в)ч В(с,с,с)ч Ъчт|иА(и,с,в)ч УвВ(Ь в и))л (УвЗнВ (в и, а )) е (гид(и, сп) л Зг 3вб( в и, в)) ч (пг пвВ(Ь, г, в) л л год(г с х) л пх се В( у х и)) = (с | л Рг ) -+ (с| ' ' Р4 ).
Г, =УибвА(Ь,н,тг)ч В(с,с,с)ч Ввй1нА(н,с,в)ч т|вВ(Ь,в,те)= = Вв(УиА(Ь и,в)ч В(с се)ч Угад(тт,с в)ч т|г|В(Ын|)) = = ЪюУ~И|тх|т (А(Ь и в)ч В(с с с)ч А(тг,с в) ч В(Ь ||,|)), н = А, Е = А(Ьи,д)ч В(ссс)ч А(г„сА)ч В(Ын|, ). Уг = УвОнВ(в,и,л), и = Г(в), Рт =В(в,У (в)а). Е,чу =Р;луе, Гт = ЛиА(и,са)л ВтВвВ(вгв)м т|иА(и,са)чУнУвВ(в тв)и и т|иУиУв(А(и с л)ч В(в н в)), Рт~ = А(н с а)ч В(в т в). сг — — ВчЭв Ь,к,в лЛгд|,с,г лЭхУуВ у,ха мУкУвВ(Ьрлв)ч чт|гА(г с г)ч т|хнуВ(уг а) мЗу(чнУ|кВ(Ьчв)ч УгА(х сг)ч ч УхВ(у х а)) и ~уУнт|вт|гтбхГВ(Ьн, в)ч А~г сг)ч В(у, та)), у = |, Е' = В(Ь и в)ч А(гсг)ч ВОха).
Г =(Агут,н,3)ч А(тг.с,А)ч В(с,с,с)ч В(Ь,г„|,) В(в,~(в)а), А(ис а)ч В(иств) В(Ьнбв)чА(г с, )ч В(г',га))= «СнСмСмС ). Упростим формулы множества Г, найде их склейки. С) =А(ЬиА)чА(„сА)чВ(с,с,с)чВ(Ь!„г,), О, =(|(гг), СО,=АЛ,В,А) А(Ь,ОА)чВ(с,с,~) В(Ы,Г,), О,=~/н), СОО = А(ЬсА)чА(ЬсА)ч В(сс,с)ч В(Ынг,), От — -ЦЬс!|,),Склейка равна А(се А)чВ(ссс). Гинее а Нс т кение и енотов згг С, = В1Ь е,те)ч А(т с г)ч В(1 к а), 8, = (Ь11), С„8, еВ(б,е,те)чА(г,с,т)чВ(Ь,.т,а), 8 =Цт), С 8 8, =В(бете)чА(т с т)ч В1Ьх а), 8, =(а/в), С 88,8, = В(Ьха) ч Л(т,с,т)ч В(Ька) = Р('„,сг)ч В(бх,о) еек(СнСг) е? С, = А(с,с,т»)ч В(с,с,с), С, = А(и с а) ч В(н е и ), 8, = ~!гт), С 8, ч С 8, = А(с с т!) ч В(с с с) г А(с с о)ч В(те е ие); 8, = (а!А), Сга,8т ч С,О,Ог = А(с,с,а)ч В(с,с,с)ч А(с,с,а)ч В(т,е,а), Ог =рте,с~~), еек(С„С,)=В(с,с,с)гВ(с,с,с)=0.
Исходная формуне Р истинна. в) В = (3иА(и,б,с) — е (ЭеЛтеВ(е,е,ие) — е ВеА(б,е,е)))л л (к»В(а, у,о)ч е»хА(Ь, к,.т)чт»хеуггВ(х и,б)) — е ((еукА(х,к.с) — е ЗуВтА(Ь у г) ч В(а а б))) = (Ь; л Гг) е (Гт ч Ге). Р; = 3ыА~~~Ьс)ч ЗХаВ чете)ч ВтА(Ь т,е) — = Миан бе)ч ч'ееФтеВ(ее н)чЗеА(бее)ич»тгА(тЬ с)ее»ге»теВ(г г,те)ч ч ЬА(Ь е е) ж ЭЯт»гтА(н Ь с)ч к»тк»егВ(г,т,те)ч А(Ь е,е))—= — = 3~ Мат»Я т»ГА(гт, Ь, с) ч В т, т, ег) ч А(Ь, е, т )), е = А, Р",' = А(и,1г,с)ч В(т,г,те)ч А(б,ту,гу). Г, с ВуВ(иуа1ч т»кА(бхх)ч тукЧиВ(кнб) и Ву(В1а»а)ч МхМЬ кх)ч етт»иВ(гтгф=-Вуехк1г»818(ткуа1 чА(бх х)ч В(ти Ь)), у =1, Ег' = В(о,1,а)ч А»Ь,к,х)ч В(т,и,Ь).
я= Ж* Т еГ к,кт=с и*.н. и.е от»хеут»г(А(х кс)лА(Ьух)), Г,' = А(х х с)л А(Ь, у,г). ск =Г, = В(а,а,Ь), Г = (А(и б с) ч В(г,г ег)ч А1Ь т1 т11 81 а 1 о) ч А Ь х х)ч В(т и б) гга Чясц г. Огвепг шелия унв няя А(х,к,с~!А(Ь,у,г),В(а,а,б))= (СофффС,). Найдем все склейки формул. С, = А(и Ь с)ч В(гсй и )ч А(Ь А с?), О, = (Ь!и фб)с), СО, = А(б Ь Ь)ч В(г,г,в)ч А(Ь Ь Ь)= В(г г,в), С, = В(а 1 а) ч г?(Ь х х)ч В(г и б), О, = )гаг!г 1) г а~б), Сгй, = В(а,!,и)ч А(Ь,к,х?ч Л(п,?,и)= А(Ь,«,х)ч В(а,!,а).
гиг(А(бхх)ч В(а,1,а) В(гг,в))=? Ог ='!а!Оа~!,гг)в), сел = А(Ь,х,х)ч В(а,а,а)ч В(а,а,а)= А(Ь,х,х). гез(А(Ь,«,л),А(Ь,у,г))=? О, =(л!у,к1г), тел= А(Ь,х,х)чА(б,.к,х)=0. В этом примере походная формула дана в виде нмиликации, причем следствие импликации равно единице, т. е. В и! независимо от посылки.
действительно, з ев(А(х, л', с)ч, А(Ь, у, г)) =? О, = гб(лб!у,с(г), зев = А(ЬЬ с)ч А(ЬЬ с)= 0. г) Р = (гхь?уЗгВ(хуг))л (агт?уз?«А(ггху)ч зй«3«В(хаг))л (ЧгВ«В(г,а,к) — вь?иВгь?вВ(и, ч, в)) — з Лийиз?и А(и, з', и ) п лЗтЭв'Уий(в,ци) = Ргл Гз пуз — э Ьо Р; =Ллз?уйгВ(ху, ), «=Ь, г=);(!). Р =В(Ь,у,?;(у)). б; = Лизйуц«А(и,«у)ч В«ЗгВ(х,а,х) айг суМкА(и, ",у) ч ч ВкОиВ(ха, ) аВи(т?у? л4(и,«у?ч э?«В(хаи)) и а Зи(цуь?хА(зг,«1 )ч угВ(г,а, и)) и ЪМуьухь?1(А(и;х у) ч ч В(г, а, и)), и = с, ГГ = А(с х, у) ч В(та, с) уз =э?гВ«В(г,а,х) — з??иЗсз?зтВ(гг,цп)= — 3 т?«В(г,а,к)ч "ЧИВгь?ЯВ?и, т, н) = — г«Ч«В(г а л) ч з?ийг чвВ(и, г, и ) и = — Вг!ту«В(г, а, л)ч з?ггь?в В(и, г, зз )) и Вгз?кз?ггь?зс?В(го, х) г чВ(и,,в)), а =А, Г,' =В(й,а,х)чВ(иА,в).
Глава 9 Исч сп н а днев ов 379 Ь; = З»З»г/ттЛ(ы,е,и)лЗгЗттЧиЛ(ю,»и)— = Оит/»ЗчЛ(п,»,и) г г '»98»З» Л(ю, т,~г) — = т/ит/»З»Л(», т; и )» т/хн/уЗ» Л(у, т, и ) и изи(т/ггтг»Я(гг,тьи)»чхчуд(у, т,и))и и Зтгт/гге/»Ото/е(А( г, и, ге)» А(у,к, иг~), и =1, !'„' = А[и, и/) г А(у,к,/). Г=(8(Ьу, / (у)) я(ах у)и В(гас) В(г!ак) »8(»г!тг) Я(»,т»1)» А(у,х,/)). Ссиейкидитъюивтов. 8(Л,».х) В(гг,й,гг), О, = (г!!ге/!гг,к)и Ь В(г!, Ик)» В(г/,дк) = 8(Л,г/,х). Я(ие /)» А(ук /), О, =)у!»ху Ь А(и, » 1)» Я(у,х 1) = А(у, х 1).
гет(В(Ь у,г (у)),8(Л,Л,х))=т/, О> =(Ь1Л,Ь(уу В(Ь у, / (у)) О, » В(в В к) О, = В(Ь Ь, В (!г)) ч 8(Ь Ь. т), О = (/ (Ь)к). гев = 8(Ь Ь / (Ь))» В(Ь Ь Г (Ь)) = О . Огорвгуггв В ивгиюгв гО Г = (У»090иЛ(и» и)» ЧхЗуВ(кЬу)» т/ггт/г С(и»Ь))л л (ЗкЛ(к, и,Ь)»т/уЗкВ(а, у, ) м '4»ОггС(е,гг, гг))л (т/и В! »,Ь, и )) — г -е (еггЗ»З» С(ы,и, и)лЗхт//ЗвС(л.у,в))= Г л/т л Г, — г Г,. Г, =т/ггт/гт/иЛ(и,е,и)»ЧхЗуВ(к,Ь,у)»т/ггт/»С(гг,и!г) =— и Зу(т/ит/гвОггЛ(», г;и ) гт/тих Ь у) и 41 т/г С(г»г,,Ь)) и и ЗуЧггт/»Ч»т// т//т (Л(и, и гг) г В(х,Ь, у/г С(1»/„Ь)), у =В, Г; = А(и,гте)и В(х Ь у/»С(г,,г„Ь) Г, = Зтд(к а Ь)» тЬЗкВ(а у г/ г т/гт/»С(г,п а) и йт(Л(к а Ь)» Ч у В(а, у, х)» т/от/и С(гав, а)) и иЗтт/ут/ т/Н(Я(ХГГ,Ь) Г 11 О,у,х)И С(» П,и)), х = 1, Г,' = А (1, и, Ь) м В (а, у, ( )» С(е, и, а ) Г, = тгиВ(а,Ь,гг), Г,' = 8(а,Ь,и) йдт, ! иийей..ти- и., ! Чаев З.
Сгвегм ения кезлякя ы з1хЗуз1гС(т, у, г) = Зи(сучстзеС(и, я ю)ч чхсргС(хи, г)) в в Зис1ксУсемхзУгй. (и, ч,'е) ч с(х, и, г)), и = 2с, Ус' =С(д,к,ю1ыС(х,й,г). Г=)ЬА(икв)ч В1х Ьсу)ЧС(сисзф) А(1аЬ)ч В(ау 1)чС(к иа), В(а,Ь,в)С(Ь,к в)ч С(хд,г))в (С„Сз,Сз,Сс). Склейка пооледнесо днзмонксз нз мнакеатее Г: О, = Цх,д(», г1и ), С(1с,к,в)О, ч С(х lс,г)О, = С(Ь,Ь,г). гез(Сс,Сз)в2 О, = «1с лак 12зк) СсО, ч СзОз — — А(1 а Ь) ч В(х Ьй)ч С(тстгЬ) ч ч А(1,а,Ь)ч В(а, у 1)чС(а,1,а)= = В(к,Ьх1)ч С(А,сз,Ь)ч В(а, у 1)ч С(а,1,а) О,=(+ф,ф~, СОВ, ы С Осйз = В(а Ьсу)ч С(тоС„Ь)ч В(а Ь а)ч С(а! а)= =В(аьс1)чС(с„с,,ь)ч С(а1а), О, = Ис,,11(з,ф), СОВ~О ч С О Озйз — — В(а,а,с1)ч С(а,l,а)ч С(а,1, и) = = В(а,а,с1)ч С(а,1,а). тез(В(а,а,с1)чС(а,1,а)С,)в 2 О, = (а~Ь,с1)м~), тез = В(а,аА)ч С(а,1,а)ч В(а,а, й) = С(а,1,и).
тез(С(а,1, а) С(ЬЯ, г)) =? Ос —— ~а11Ь, а~, ас1г), тез = С(а,а,а) ч С(а,а,а) = О. е — носнннвс формула. е) Р = (ЗусйгВ~у,а,г) е зУизУчА(Ь,к,сс))л (сУис1кА(к,и,а)ч .' сууВизУгВ(и, т, г)) л (зУгВ(г, г, г)) — з -+ ((Зуд(а, у, Ь) л ЗхйуЗгА(х, у, г)) ч 'ы Зи'УкЗФА(и,с,к))= Е) луг л Ез — 3 Ес ч Ез. Р; =ЗузУгВ(йа,г) — з ВиУа4(Ь,ы,и)в ыуЗхВ(у,а,г)ы ч сйисучА(Ь,к,и)=— Зг(ыуй(у,а,г)ч суизучА(Ь,к,и))в в 3гсУу сриЗУк (В (у, а, г) ч А (Ь з, и)), Сяава 9. Ио»испание п сан»ею» г=с, Г,' =В(у,а,с)оА(Ь,»,и). Гз ю згизг»А(азз,а)из?уйМгВ(зз,уг)ю ю 31(кгиЮА(о, зз, а) о згузгкВ(г, у, г)) ю юВ»згзгзгозгучг(А(»,и,а)ч В(г,у,г)), г = и, Г,' = А(о,иа)оВ(зг,у, ). Г, =зггВ(г,г,г), Уз =В(г,г,г).
о згхчузггА(х, у,г)ю 3~~му В(а, у ь)озгкзггА(к г, г))=— ю згзгузгхзггГВ(и, у, ь) о А(х,г, г)), г =1, Г„' = В(а, у Ь) о А(х 1, г). зр .1е »Знн; К =зЗО. Г, '= А(и,1; (и) ю). Г= )В(у,п,с)ч А(Ь,»,и)А(»,зъа)ч В(ану, )В(г,г,гЪВ(п,у,Ь)о о А(»,1,») А(и,1;(и) ю) ю (СнС»,С»,С»,С,). зю(СнС»)ю? О, = Цгз,сг)а,сЦ, 1 СО, чС О, =В(к,г?с)о А(Ьмзз)о А(» и а)о о В(И,к?,с)ю А(Ь,»,и)ил(о,зна), О, =Ц~Ь~н1, С О О о С,О,О» — — А(Ь,Ъ,Ь)о А(Ь,Ь,а), О, =(?~а), кез(СнС»)= А(1»ЬЬ). кок(СмС»)=? ' — ооню» ноременне», заменим г на С» = В(ггг), Сз =В(ауЬ)ч А(кгс)О, = уса~„.,а~уа~Ь), СО, оС О, =В(п а а)о В(и и а)оА(»1 г)юА(х1 г).
кек(А(Ь,Ь,Ь)А(кг,г))=? О, =)Ь(к,lф,Ь(г», зек = А(Ь,Ь,Ь)' А(Ь,Ь,Ь)=0. Исхолная формула à — нстннна. Глава 10 Теория алгоритмов 10.1. Ответы и решения практического занятия Мй 11 5А.1. функция 4« пояуяпегся суперпозицией нз ! и 1„: «р(хох„...л„) =. ! (у,, (х„х„...,х„) 1;,(хох„,х„), 1,",(тих„,л;,) 1„(хохз., «;)) функция Ф вЂ” суперпозиция ! и 1„', гр(х,,«л,,х„,)= = 2.(1,',м(...„.„а) 1,',,(.. х, .„,)....1,',,'(.Р.„...,.ям)). я) 61 542 61 в1 ! (х)= х»-т», функция ! (х) — суперпозиция функций Л(х); ! (х) = (((х+1)+1)»....
+1)= ЩА(х)..)); в я у(х)= и, Функция у(х) — суперпозиция функций Л(х) и О(л); г(х) = (((От!)»-1)+ ..-ь1)= Х(У(.З(0(х))..)); т г(л, у) = «»- у Применим схему примитивной рекурсии функции Г(,0)= р(л) двух перемсннмт . . . , Роль »р(х) ь»ожет ( ! (ц У -- 1) = М , у, Г( , у)) игрвть функция 1,(т) = л, раль йг(х,убт)=л(!'(х,у,т))= к+1=1+»'(х,у), те, г(хО)=л =х «О, !(«1)= 4«(хО у(хО))= 1ьу(х0)=1» л., у(х2)=дг(«,!,Дх1))=1ь г(х1)=2-';х ит.д 'Ма»ь »1 0»веш, нне, еяння Вес 5.4.3. а) функцию (х — у( можно легко выразить через усеченную разность. (х-у,хйу, (х-у,х>0, Действительно, ~х — у(= а х — у= То~у — хх<у, ~ Ох<0, (-и-)-( .,',::;:;::; следовательно, (х-)(= х — у 4 у —.т, Функция (х-у( примитивно рекураивна, ибо представляет собой суперпозицию примитивно рекурсивных функций; б) т(х) — число делншлей числа х, т(0)= О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
