Математическая логика. Шапорев С.Д (1019113), страница 47
Текст из файла (страница 47)
Составим множество дизъюиктов Г и цримеиим теорему 2.10. Г, (АчССч В,ВчААВС ). Вывод нуля из Г,' может быть, например, таким.' 1) гез„(АчС,А)=С; 2) гез(С,С)=0. Итак, фора«ула А — «( — «С) выводима из исходного множества; Часы д. О в ы, Лемеекц'указание б) проводим вычисления анвюгинно ««унк«у (а): Г = (Ач С вЂ” «В С вЂ” «Ач В ВС вЂ” «А ч В) — В -ь С, Г, = йдчВ~СчВ~)дчВчС,АчВчСВС))-, Г« =)йдчВ А.чВ~, А ч В ч С, Ач В ч С В С !' †. Найдем все )жзольвенты множсстаа Г,': П гез„')А ч В, А ч Вч СС).= В ч С; 2) гез (Ач Я чС,Ач Вч С~= АчС; 3) гела(Ач ВчС,В)= АчС; 4) кета')Ач В,дчС)= ВчС. Дыьнейшнй резолютивный вывод невозможен„т. е формула  — «С не выводима из исходного мнвк<встав Г; в) Г = ~С, А ч В )- ( — «С) — «А . Г =)СдчВ ~В» С))~А~=)С,АчВ,Ао(ВчС))(-, Г,' = «С, А ч В, А В ч С~.
!) гез„(Ач В,А)= В; 2) гез (В, В ч С) = С; 3) гез(С,С)=0, Формула ( — «С)-ь А выводима из Г. 2 9.)5. а) Г=(АчВчСчОВ,АчдчС,СВчО). Применим к этому множеству описанный в разделе 2.7 алгоритм проверки противоречивости множеспю хорновских дизьюнктов После найденной очередной резольвенты укажем состав множества хорновских лизъюнктов. !) гез„(В А ч В ч С ч О) = А ч С ч О, (А ч Сч ОВА чВчССВч О ) 2) гез (С,АчСчО)= АчО, 'узч О,В,С,Ач Вч С,Вч Р~); 3) гезв(ВВ г Р)= Р,~)у";,Ач О В САчВчС)); Глава 7.
Исмклеьне ем»ха»мамина 4) ге»с (О А ч Р) = А, ~~А, О, Я С А ч Яч С~'; 5) геях)А,Ач ЯчС)= ВчС, )ВчС,А,О,В,6'') 6) гатт)С,ВчС)=В, (В,С,А,О3 Во множестве (В,С,А,О) нет дизъюпхтов необходимого вида дл» составления резольвент. Следовательно, походное множество Г непротиворечиво, б) Г= )г)чВчС,А,В.С). !) геях)А,Ач ВчС '= Вч С, )Вч С,А,В,С); 2) гелЯС,В'г С)= В, )В,А,В,С»; 3) гез(В,В)= О.
Исходное множество Г противоречиво; в) Г= б.чО г Е,ЕчЕ,С,Р,А7). Р геьс[С,СчОчЕ)=ОчЕ, ргчЕ С,Е гЕ,Р,А 7); 2) уех,рчЕ,О)=Е, )Е,С,ЕчЕ,А,Е); 3) тех, (ЕЕчГ)= Е, 'Г,ЕСО А Е); 4) гехарт,Я~=0. Множество Г противоречиво. Глава 8 Логика предикатов 8.1. Ответы и решения практического занятия рбз т ЗЯИ хз-!Зх+40>0, (х<5 нли х>8, б), 'ее~ ' 1а=о; 2х +а+30<0. ~ И. х+у. х — > в) япх=япу,2соз — яп =О 2 2 х+у !) сов — =О, х+у=п+2лп; 2 2) яп — =О, х-у=2лн.
х — у 2 Итак, 1 область истин(х-у =2нп)л(хч-> =л-ь2лп) * пб2 насти предиката изображена на рис. 8.1 х 43хь2 а) л" ч-4з:+ 3 числа корни х +Зх+2=0, х' + 4х ч 3 = О, Следует найти «орли числнтелл и исключить из ик знаиеиатслл, если они совпадут. Итак, х,= — 2,хз=-); х| = -3, хз = — 1. Следовательно, 1ь = ( — 2); Ча ы д Онытн, рснзс~ нл, уна Рвс. а.т х т) 13 х = 1б у, х > О, у > 0. — = 1, х = у .
у Рн В.т Зх02. Области истинности заданных нрсднкатов нзображсны нарос. 8.3. Глава В Пегикв предика в г, Ри Рис. Вд 34.3 а3 (Р(х)гз фл))зг (Р(х) л Я(х)); б) Р(х)мД(х); ) 11 сХгЗ.ЕТ3 ( Ььс() Ы И*) сом ЬВ: г) Р(х)<Д(х) 3.4 4 в) Чх((х — бхе880)ч(х -бхеб<0)). л — бхе8=0, з, =2, х, =4. Если л. — бхе880, то л >4 или х<2, сопи же х' — бхеб<О,то 2 <х<4,т.е. хп ((-,2]ьз(4,+ ))ьз((2,4)). Таким образом, Чтей исходнсс высказывание истинно; 83 Ех~х' е х + — = 0 . х т хе — =О, лб з = — — ь ] — — — . Дсйстсн- 2 2 3з4 2 тельных корней нет Так как область определения предиката совпадаез с Я,товысказывание Зх х ехе — =0) ложна; 2 в) Чх(л' — 5х об > 0). х' — 5х е б = О, х, = 2, х, = 3. пз- ги аев Часть Л. Огееги кннйя ухеввмив 3.4.5. а) да; б) да; в) нет, 3.4.6.
а) да; б) нет; в) да. 3.4<0 а) хс — связаннав, х, — свободнал; б) хт — связаннаа, х, н хз — свободные переменные. 3.4,8. А = 'Фуб(х,у,у): 8 =5т(УУР(т у у)лб(тыпх)); С = 575(у,у,х). а) б) в) 3.4.9. „„~,(5(,, ) 5(у,, )). а 5(у,х,т)=(У+к< 4)' Ч7хЧ ы ьгитуттгж((5(х,у,и)пб(и,т,в)пб(у,г ы)) ( ' Эта вьпекаег из следующих рассуждений: 5(х,у,и)= (х+ у — «) 5(и,т,т)=(нег=и), 5(у,т,ы)=(у+а=и)* 5(х,и,т)=(хти =и), т, е. ((х+ у)+ т = т) п (у + т = и ) — ь (х + и = т), (х+ у)+ т = и = х+ (у + т); а) б) зУх н ((х < 2)ч (х > 3)). Так как на интервале 2 < х < 3 неравенство не выпопняетсв, то высказывание ложно; г) Лх((хн (25Э вЂ” ь(х' — бх+8=0)). х' — бх+8=0, х, =2, хз =4. Эх((хб (2,5Э-з (хб (2,4)))= Эх(хб (2,5)ч хи (2,49.
Высказывание истинно при х = 2. Глав В. Логика лредикагаа 3.4.10 в) аналогично предыдущему пункту: гухгУуЗГхгУигУггУи(Р(х, у, и) л Р(и, х, т) л Р! у,, н ) — г Р(», и, г)); г) ЛхЛу(П(у)ох< у), где П(т) =Е(х) тУгтУх(Р(ух,х) — з -+ (Е(у)о Е( ))), Е(л) = гУуР(х 1, у) ..т < у = 5хб (хе, у), Р и 5 из задачи 3.4.В. Формула Этб(хобу) с двумя свободнылги переменными х и у истинна тогда, когда х < у, действительно, если пзп дг(лье = у), то х < у. Предикат Е(х)= тУуР(ху у)= зУР(х у)= у нстинеп при х = 1 Преликат П(х) истинсн, если х — простое чиоло. Зго можно продемонстрировать н» простом примере, например при х = 4 и х = 5. П(5) = чуРР(5, г, у)» зГМ (Р(г, хб) -е (т1гР(гпб г)ч гУггР(згогг))) = = 'ч! (5 у = у) о ЗУузУх((у г = 5) — з (1Гг (у г = и ! м тУи (х и = и ))) = =(ун1)о ((у=5,к =1) — г (у=1)п( =1))=1.
П(4) = 1ГуР(4, у, у) и тУутУВ(Р(у, О4) — г (ьУеР(у, г, г ) м гУиР(з, и, н ))) = = туу~4. у = у)п тУутУа((у а =4) — з (гУт(у т =з )ч гугг(т и =и)))= ((например, ~ = (у и 1) п — г (у = !) о (т = 1) = О. ~~у=г,х=г~ т. к. простое число делится только на едннипу и пп самого себя, а у составного чила нсскояькоделителей.
Таким образом, бесконечность многкества простых чисел вырвгкается Формулой Лги(П(у)о к < у), г. е, лля ыобаго хп дг найдетс» гаков простое уп 1т', что простое т и вюбое з ие болыпс у При подстановке предиката П(у) в исколную формулу, получим зУхЛу (5тб (П (у ) и х, т, у )) = 'У тЛу (ЭзЬ Яу)о туг г гУы(Р(н, и, у ) — ь — ь (Е(и)о Е(ы)))о х, т, у)) = гУхЗу(5тб(Мому,и,и о о гУигУи(Р(н, и, у) — ь (Е(н) о Е(и ))) о х, т, у)).
— а х.1а — 4и а1 х ч-пх.ьи=О, х = —. Эх<0 подразумсваетдейьг ствительный корень Корни квадратного уравнемн» действительны. Ча«п я. Отвею, решения, яаяаняя если аэ-4а>0, т е а<0 или а>4. Таким образом, высказывание истинно, если ап ( —,0]!э[4,.ь ), и ложно, если ап (04); б) Зхп [а,а+1[(х' — х — 2<0). хг — х — 2<0, — 1<х<2. Следовательно, если а и [- 2,2), то х будсг попадал на отрезок [-1,2). Тогда исходное высказывание истинно при а и [-2,2[ и ложно, если а > 2 или а < — 2. 4! 1. Рассужпение можно разбить на ряд посылок: ! ! Любой разумный философ — циник; 2) Любой разумный философ — зкенщина; 3) Если разумныс философы существугот, то существуют яшнщнны, которые являю~ся циниками. Введем сяедующи» прсдиьаты: Р(х) = (х шляется разумным философом ), мз(х)=(х является гксншиной ), «(х)=(х являегся циником ).
Тогл» обшш формула, сселиняющая в себе все посылки, имеет вид (ьгх(Р(х) — э И(х))л Мх(Р(т) — г !2(х))) — г (Зхр(х) — э Зх(фх) л И(х))) . 4.12. Введем три одноместных предиката: Р(х)=(х — погштик й(х)=(т — лицедей ) и й(х)=(х — лицемер ). Тогда все три предложения исходною рассуждения могут бьггь представлены в виде формул зУх(Р(х) — ь цт(х)), Зг(!3(х) — э й(х)) и Зх(Р(х) — ь Я(х)), а "перевод" всей фразьг на язык логики предикатов будет иметь вил (тУх(Р(х) — г Д(х))л Зхф(х) — ь Л(х))) — ь Зг(Р(х) — г Л(х)). 4.13. пусть одноместный предикат Р(х) = (х — глупец ), а преликаг дг(х) описывает действие; гу(х)= (х способен совершить чтою ). Тогда высказывание Зхйг(х) моящо интерпретировать. что некто (аозьгожно в) не может совершить этого дейсшия, а высказывание ЗхР(х) овна шет, что некто не глупец. В целом исходная фраза могкет быль передана следующей формулой: (тх(Р(х) — ь дг(х))лзхйг(х)) — ь згР(х).
4.!4. Это утверждение заключает в себ» много неопределенностей, связанных с отношениями субъектов н их свойствами. При обозначении прслякатов будем интерпретировать эти свойства и отношения самы» прастыьз и понятиыьг способом Введем двухместный предикат ВЩ Глава В. Логика редияаюв Р(к, г)=(» и у - друзья). Будем считать, гщ Р(щ у)= Р(у,х), т.с. если х — друг у,то у — Лруг к.
Тогда угверждеиие, заключающееся в том, что длв любой пары друзей иайдется щкой чсяовек, чзо если ои дружит со вторым из этой пары, то ои дружит и с первьщ, запищсщя так. ''УТВл(Р(к, ) (у,х)) (.,к) 34.!5. Введем двухмес1пый предикат Р(к,у)=(х любит у). Тогда первая часть прсдложеиив выражается вьюкюываиием»УХР(х,к), а вторая — ЛИТР(х,у). Общая формула тхР(х,х) — г ЗХЗуР(к, у). 8.2. Ответы и решения практического занятия 1!88 8 37! а! Мк(Г(к) — з 6(к)) и як) л 6(х))—= = »Укггг(х) г 6(к))л Эг(Р(к)л 6(х))м ! 7огла (зУХ(РГл!с 6(х))==1, ( Зхуп(к)л6(х))м 1.
Перейдем к адиатипиым кваиторам в обоих тождествах. ! т' Ггх)стУ6(У)=-1, (зУХР(к)лУлу6(у)м1, ЗХГ(х)л 336(у) и 1, (лхР(х) л Луб(у) и 1, -( М )лзу6Гу)жб, ВХГ~к ! л ЛуС(у) и 1 Или ( УлхГ(х)о»736(к)м 1, ( ЗУхРГх)о»Уу6(к) и!, ВхГГ»х) 376(х)м!, (а»ГГХХ)оЛу6(х) »Уху (хт о ту 6 (к) и 1, Улку(х) . 736(у) и! Обоим получеииым системам удовлетворяет еяелующее !жспслокмиие области истиииосги предикаюв Р(х) и 6(х).
Таким образом, 1, щ 1 (рис. 8.41; Чв м д Опмп», ренмиив, кивание Рис. 8.4 )артс) с а ВЬ» сваи'Фх(Р(х)об(х))л ПЯк)ч б(х))м!. и и »Ух~~чбГх))ю1, (»Ухи ГЧх)ч»УубЯи1, -~~..(.))'и -~-..-(,)н.- 'УхЁ(х) ч 'Ууб1у) 1, РМТК Р~х) ч»УубтЯ вЂ” 1, Птр'(х) л Пхб(х) =- 1, (ЧтхУ(х) л»Ухб(х) н О. Итак, 1г = »с», 1о — любое подмиожесп»о 88 (Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
