Математическая логика. Шапорев С.Д (1019113), страница 48
Текст из файла (страница 48)
85). 3758 а) выполнимн если г(х) — нетожлестаенноложный предикат; 6) невыполнима. Пусть л(х = а)п М такой, что выполнима форе»ула тгу1й(п,п)лы(л,у)). Тогда выполнима и формула й(а,л) л ы(л,а). Но Д(п,а)л Ян,а) = О. Получено противоречие. Следовательно, исходнав формула невыполнима; в) формула может быть выполнима на д», например, когда предикать» й и Л выражают следуююие отношения порвдка й(х,у)=. (х> у), й(х,у,х)=(хе у > л). Пусть л(к=а)н дг, что выполнима формула»Уу((а > у)-»'Ут(а ч-у > л)). Тогда, если Глава В. Логи«в л дина«ов 333 ЗЛ<й у = х = а, то (л > а) -з (а ж а > а) = 1 — ь ! = 1, т е исходная фор- мула вьщслвииа.
а1 нет Формула ложна на множестве Д«, если, например, Р(к) = (х— иегисе число ). Тогда Лхр(к) — ь Чхр(х)=1 — « 0=0; б1 'Чкр(к) -+ АР(х) и Чхррб)ч ЛхР(х) и Зхрр)ч лхР(х) и милок)ч Р(х))м 1; в) АР(к) ч ЗхД(х) оь Лк(Р(х) ч Д(к)) — (Ь«Р(х) ч ЛхД(к) — з — з ж (Р(х) и Д(х))) л (лх(Р(к) ч Д(х )) -е ВАР(х) ч ж«Д(х)) —= и Зх(Р(х) ч Д(х)) -+ Лх(Р(х) ч Д(х)) и 1, ибо высказывание лт(Р(к)чД(к)) принимает значение 0 или 1, а 1-+1=1 или 0 — «0=1; г) пусть Д(х,у)=(лбу)х,уб Ч, Тогда высказывания йхЧУД(х,у)= ( существуе«натуральное число х такое, ито дв» всякого натуры«ьного у истинно «< з' ) и Чу3хД(к,у)=( для всякого натурального у' найдется не превосходящее его натуральное х ) истинны иа ДГ .
Таким образом, формула лхЧУД (х, у )-з ЧУЧхД (л, у ) тожлссз асино истинна; д1 нет. Формува ложна на дг, если Р(к)= (х — просюс число ). тогда Р(х) ' ЧУР(у)=1 — «0=0; е! «(Р(к) л (г — ь Д(х))) — + (Чх(Р(к) — з Д(х)) — з г) и ь йР(ТТ лы1.73«з "ср1. - =. Гзз !"лзй!)- ч (лк(Р(х) л фх)) ч г) и Чх Р(х) ч (г л ЧУД(у)) ч (г ч Зхр(к)) л л (г г Буфу))м Чар(к)ч ((го ЧУД(у))ч (г ч йхР(х)))л г, ((г л ЧУД(у))ч (! ч ЗУД(у))) Но г л ЧУДЯ и г и ЧуД(у) и = гч ЛуД(у).
Тогда (гоЧУД(у))ч(гчЛуД(у))м 1 и бкзр««ула улрощается ЧхР(х)ч( лЧуДЯ)ч (гчЗлр(х))= — (Чл%х)чЗ«Р(х))ч г « г ДОвепч , уюаання ч (г о )УРИЯ). Однако тУхР (х)м~дхРгх) и Вхр х). Тогда 1 ч г ч (г гь тгуЯу)) и 1, т. е, исходная формула такдественно истинна. 3.7.4. а) пусть иа некотором множестве М данная формула ложна. Тогда Вхртхч)=1, )!лР Рхх)= О, т е. ВхР(х)= О, ЗУхР(х) =1, что не может быль, осли М и И. Получено противоречие, следовательно, формула ЪР7л) — з тхр рхх) тождественно истинна; пусть на М даннаа формуяа логкна. Тогда на М *1 Ы ар))= ° Р) Ч7о* =а. 1)= гУхйг(х)=1 Выберем (х=а)б М такое, что Р(х)=1 В атом случае Р(а)ейга)=1, т.е.
)й(а)=! и )х(а)=0, что противоречит Тгх!)(х) =! . Таким образом, исходная формула тождественно истинна; б) в) доказательство полностью аналогично приведенному в предыдущем пункте. Пусть иа М формула тх(Р(х) — зйГх ) — (чх РлхлВхЕхл) ложна. Это значит, что Ух(Р(х) — зь)(х))=1, а ьУхР(х)=1 и Лх)г(х)=1. тогда должно быть Р(а)зЯа)=1, т.е. Р(а)=0, что преп иворечит )Гхр(х)= 1. 3.7 а) !) 3гапМ Р(х) =1, 2) Лаоп М Р(х) =О. "о "|лг -' В первом случае Чаи М Р(х~! =1, тогда по определению ЛхР(х) =1 и ВхР(х! =О.
С другой стороньь т.к. .5. доказательство аналогично приведенному в разделе 3.5 для формулы 'тлг1(х)— м ВхА(х). Рассмотрим на М мне-костас значений связанной переменной х и свободных переменных х„х,,...,х„преликвта Р и выясним, какие значения принимают формулы ~~л и зУлР(х) на произвольном наборе свободных переменных аоа„...,а„е М .
Глава а. Лог ка и едвкагав 'УаР(х ! =1, то УхР(х) =0 Таким образом, «тр(х)ю Ухутх). Если юе «осп М Р(х) =О, то «хР(х'! =О. тогда * юлх...)= *Ь ечГУ,,;1, «" Ууу(х у > п «хУ»фх, у) — = «хУ» Р(х, у) п «х Ууфх, у) = — ' и «т«я(У»Р(х > ) „УуД(х, у)) ю «х«хУ»(Р(х, у) и )х(х, у)), «тУ»Р(х> )и «хУ»1 г(х,у) ю «х(УуР(т,>)у Ууй(х,у)) ю ю«х(Уур(х у) ч Узфйх)) —= . «хУуУх(Р(т, у)м фх х)): «тУуР(ху) — ь «хУ»фх>) ю«АР Ву! ч «хУуу(ху)=- и Ух«»Р(т, у) г «тУ»й>(х у) ю Ух«у>х(х, у) т «хУпфх,гг) и == Ух«у«зря (Р(х, у) " .й(з, и)); б) А) г1 «хР(х) = 1, т. е, неверно, что найдется такай х, для которого Р(х) истинно.
Эго равпосильнотому, что для всякого т истинно Р)х), т. е. Ухр(х) =1, Сяедовательно, опять «тр Гх) ю Ух Р Гх) б) УхР(х)оС ю У4Р(х)г, С). Упростим пример и рассмотрим случай, когда список свободнык переменных предиката Р пустой. Здесь возможны опять два случая 1) Уан М Р(х)=1, С=! или С=О, 2) Угг и М Р(х) = О, С ю 1 или С ю 0 В первом случае Ухр(т)=1, если Гю!, то 'УхР(х)пГ=1, если зкс С=О, то УхР(х)оС= О. гбормугга в правой мсти примет анавогичнь~е значения. Действительно, если УхР(х)=1, то Р(х)— ю 1.
Тогда Ух(Р(х)оС)=1, если С=! и Ух(Р(х)пС)юО, если С=О Вгорой случай рассмгпривае~ся аналогично. Желающие могут повторить показательство с нспустым спискам свободных переменных прсдиката Р. Ча ек бей ааааа, аааанаа 3.7.7. а) к)к3у~Я(х, у) — а 3хууфк, у) и МйуЯ Гх, у~ч ч 'Фх3уфх, у) — = 3х7)уЯх, у) ч 3хУуД(х, у) е ийх(Му~~к, уу)ч 'ФкД(л, к))е — = 3к'Фу'Фк(ЯХ, у) ч фк, к)); 3к(Р(х) — а (куак у) а 'Ук)?(ха))) е и 3к(Рх) ч ~~у(Як,у))ч Мкл(х, к) '))и е 3хгР(х) ч (ЗуЯк, у) ч Чх))(к, к))) и и 3хгР(х) ч 377)к)~Як, у ~ч )7(х, х))) е и3к3уа)Як)чфк, у)ч)7(х,х)).
б) 3.7.8 Мк(Р(х) — ч Д(х)) а (МхР(к) а 'с'хД(х)) е и М~Р ( ) ~(х)Я~Зх~~ ч ЧкД(х)) е 3х(Р(к) л Д(к))ч ч (3хРГх)ч ~хфх)) е 3к Р~к)) ч (Р(к) л Ях))) ч ЧхЯ(х)— и 3кгР(х) ч Ях)) ч 1к)3(х) — 3х Р Гк)ч 3х0гх) ч 1к)2(к) =- и 3кР Гк) ч 7)хЯх) ч )7хд(к) = — ! ч 3к Р(х) = 1; ух(Р(к) а фх)) а (3хР(х) — а 3кфх)) е 3х(Р(х) л Ях)) ч ч а)хР 8) ч 3хД(к) и 3х(Д(х)ч (Р(к) л Ят)))ч МхР б))е е 3к(Д(х) ч Р(х))ч УхРгк) — 3х)к(х)ч3кР(к) ч 3кут~х) — ); Х)к(3-а Р(к)) аа (д -а МхР(к)) и и (Чх(д -а Р(х))-а (д — э ЧхР(х))) л б) в) е 3х)(( (Р(х) ч фу) ч ДД ч Р(к))) и 3кХ)у((Р(х) л ЯЯ) ч ч (Д(у) л Р(к))); У (Р(х) — ь 3уД(у)) е ~х(Р(х) ч 3уД(у)) е К3уЦРх)ч Д(у)).
злг Пива 5. Лопаю л диявюв о ((д -ь 3«хР(х)) ь(>7х(7 — «Р(х)))) и 7>ох!)9 л Р7к))г д ч «ухР(х)) о л ((д л П кРГк ) ч д ч «УкР(к) и ((д ч д) л (д г Вх Р~к ) ч «УхР(к)) и и (д ч ЧхР~.,хх) ч >ухР(к)) =— до 1 и ! . 3.7.9. Пхну((Р(х) — «Р(у)) л (Р(х) — «Р (и)) л Р(х)) и — = Вх ЯР (к)ч Р(у)) л ГРи) ч Р( «)) лР(х)) и БхВу((Р(к) ч Р(у)) г лЯРб )л Р(к))ч ГР>у)л Р(х))))вЗкЬу((Рх)ч Р(у)) РЯл Р(х))и и Зх3 у(ГР кх ) л Р («)) ч (Р(у) л Р (у)) л Р(х)) и и ЗкДу ГР кх) л Р(у) л Р(х)) и О. 3.7.!О. Рассмотрим сначала простой пример фориулы А и продемонстрируем механизм преобразования формулы к требуемому зилу Пусть Л =ЗкРЯх)л (чуР (у) ««Ухр (х)) и йгр«(г)от!фг(рг)у)ч Рз(г)).
теперь вынесем всс лванторь«в начало формулы и кванторы всеобщности преобразуем в аваиторы существованив с помощь«о соатветству«ощих эквивалентностей А=ЬкР(х)о«уу«уггр(у)ч РЯ)мат1уч)4Р~(к)л~РХу)чР(г)))и б!*«.ртз».;««)е >мы)б'%и «3З-' В оба«ем слуяа», если подфорь«ула Л, формулы Л ««ь«ею вил п(3!)уА (кох„...,яму), то необходимо привести А (х,,х„...,.т„,>) к виду ч(л Ае ) или О(ч Л, ) . где каждое А, начинается с кваптора «г или имев«вид Р(и) или Р(а) для некоторого Р и«о и переменной л.
Далее, используя необходимые завиеале«пности, «юлу «ась«форм>лу В 8.3. Ответы и решения практического занятия 3>(я 9 3.9.! !) «Ухе Вт)у е В~~ к у)ч (у л к)); 2) «уае АВх е В(а <«:;„), 3) М«! Е М «Укг Е М...«Ухг Е М Ва, Е Вйпг Е В .Даг Е Част В. Отвела ешен»»»азвп»» 5) 6) 7) 8) 9) 1О 3.9? . е ))((а» + а, + ... + а, и 0) л (а, х, + и, х, + .. + о, х, = О)), Мое ))'»УЬе ))'(Т»,Ь)= 0); И» п х, = х с» )»е > 0337 (к) > 0»ул е М ((л > М (е))-» [т„— х) < к); Мне Ь»(х„н > х„); 9к >0337(к) > О»)п) > Ф(к)()ха -х») < к); 3ТЕ )))(ОфхЕ М((х2Т)л(~(хЕТ)= )'(х))); )»х»е МЗ)х,е М((х, <хз)с(7(х»)<у(хз))) ) У.>03Лф)>09 е М((х>М(е))- [)(х)-Д[<е). 2) 3) 4) 5) Признак имеет стандартную структуру М»Е М (Р(х)» )2(х)). Посылка и заключение импликации имеют вид (х„> х„и >0)л( !!тх» =0~ и ) (-1)»х„=б Вислом признак можно записать так: »У»з е Ь»(х» > хн» 2 0) л ~ 1пп х„= 0 — » 35 е,) (-1)н'.»„= Ь' .
) Выраженно 11»их» = 0 можно расписать подробны, например, зак, как зто сдевано е ззлаче 3.9.1 !! 0) Му е [абфк > 038 > 0)»хе М (О <[х — )( с б с[7 (х) — ~(у~[< к)) — » — » 3»ре й»»хе [п,б»[»)»" (х) < Ь»). ((»Ууп [а 1ф/к>038 >0»)хеМ(0 <[х — 3( <б — »[У(х) — Г(У) <с))) л л(»ухе(аЬ)3у~(х)н )л(~(п)=7(Ь)) — »3се(л,Ь)(Т'(с)»0).
»Уу Е [а,Ь)(Ме > !Нб > 0»ЕХ Е М(0 < [х — Я < б — » ~ Г(х) — Т(У) < е)) — » Ть — » 3с Е [о, ~ ) )' (х)2т =) (с) Ь вЂ” а)). (((»ук > 038»(а) > О))л е М((п > М(к)) — » )х„— ь) < е)) — » )х, — х[ < з) — » Гла В Логика предикагов — «(Хэс > ОЛР7(с)> 0«эп,1 > Дг(в)(~х„— х«1< с))) п и ((«Уе > ОЗД«(е) > ОДГ«г,1 > Д7(вф г„-х, / < е))-«(ЬУе > ОЗД7(в) > 0«Ул > Ф ((и > У(с)) — «!х„— х( < е))).
1) Исход««ос утасржцепие имеет вид «Уэ' ц Р(Р(1 ) — «Д(~ )). где РО' ) -- преднкат. вырюкающий и~пегрируемость г (х) на отрезке [гг,б[, а ЬГ(/ ) определяет свойство монотонности этой функции па [П.Ь) Перейдем к противоположному выражению г т«(г«'аТ7 )ии "1 «г«.е«г«) чтобы доказать несправедливость нс.годного угвер«клелия. необходимо привести пример яюгюй функции, которая была бы непрерывной на [и,б), но немонотоннай на этом отрезке Таку«о функцию наВ и негрудно, например, у = х на отрезке [ — 1,1) удовлетворяет залвнным требованиям 1рис 8.б).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
