В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 16
Текст из файла (страница 16)
В первой из формул (1.5) формула А называется областью действия нвантора Ух, а во второй — областью действия пвантора Ях. 5. Слово в алфавите логики преднпатов ! — 5 является формулоб только в том случае, если вто следует нз правил 1 — 4. Заметим, что по определению формулы никакая перемен!!ам не может быть одновременно свободной и свезанггой. Оставим в силе принятое в равд.
1.!.1 соглашение об опускании скобок. Пример 1.28. 1. Следугашгге аырзжснвя являются фоРмулами логики пре-! динатовг А!"з(кь «ь хт) — атомариаи формула, в потароп «ь( хз, хт — свободные перемевиыс; (ух~) (я«з)Аыгг(кь кз. хз)шз ш (ухг)дшг(кь кь! — формула. в которой кь хз — связанныед а кь хч — свободные переменные. 2. Выражение (Яхг) (Ухз]дыгг(кь к,) ЬАЫгз(х, «з) ие явля-~ ется формулой. Значение формулы определено лишь тогда, когда задана~ какая-нибудь интерпретация ахадяших в нее символов. Под интерпретацией понимают систему М <М, )), состоящую нз нспустого множества М н соответствяя >, сопсстав.~ ляюшего каждому преднкатному символу А!о! определеинмд, т4 бместный предикат (будем обозначать аредикеты, ноставленцмс в соответствие прсдикатным снмволаы, теми же символами).
Прн заданной интерпретации считают, что прелметные переменные пробегают множество М, а символы — 1, г/, й, ю, — п символы квзаторов имеют свой обычный смысл. Для данной в~перпретацнн каждая формула без свободных аеремсннмк представляет собой высказывание, которое иоганна илц ложна, а всякая формула со свободными переменными выражает некоторый прсдикат нз множестве М, который истцнен прн одних значсинях переменных нз этого множества и ложен при других.
Поределом значение формулы в данной интерпретации, следуя индуктивным шагам определения формулы. Значение формулы г на наборе <аь ..., а >, а, ее М, своих свободных переменных «г, ...., хг обозйачим символом Р) <, „> . 1. Формула Р— атомарная формула Агат(х;,,..., хй).
Пусть х, ..., х. — асс различные саоболные переменные втой формулй, выписанные в опрсаелснном порядке. Значением формулы Р на наборе <аь ..,, а,>, от еп М, называется значеняе г-местного предцката, сопоставленного символу Аг'г; при соответствующем замещении его переменных элементзмн аь ..., а,. 2. Формула Р имеет внд -1А. Пусть значение формулы А на наборе <аь..., а >, аспМ есть а Тогда Р(<е, „> —— = )з 3. Формула Р имеет знд Ат/В, АЬВ, АюВ или А-В. Значение формулы Р иа наборе <аь.... а„> значений своих свободных переменных есть саотаеютвенно е~ 1/ ць а, Йзь е, ю =1еь э~ еь где э~ — значение формулы А, а ез — значение формулы В на этом набора 4.
Формула Р имеет внд (т'х)А. Если кй,..., хг — совокуп. ность всех свободных пеРемениыа фоРмУлы Р, то х, хн...., х; — все свободные переменные формулы А. Значение (Ух)А( <а, р„> — — И тогда и только тогда, когда дла любого а щ М А( <к а, е > — — И б. Формула Р имеет внд (Ях)А. Если кй .. „хг — соаокрпность всех свободных псРеменных фоРмУлы И то х, хг,.. х~ — асс свободные переменные формулм А.
Значение (ох)А(<аз а „>=И тогда и только тогда, когда для не. "старого аеаМ А), > И Пример 1,29. Рассмотрим тря формулы: 1) Амй(кь «з); 2) (тгхт)Агп,(хь кг); 3) (Яхт) (тг~~)Аю~ (хг, х1), Возьмем в качестве обдаст~7 интерпретации множество целых положительных чисел и интерпретируем Аац(х. Р) как 75 х<д. Тогда первая формула — вто преднкат х,<х«, который принимает истинное шачение для всех пар а.
Ь целых положительных чисел таких, что а<Ь. Вторая формула выражает савв««во: «лля каждого целого положительного числа у х<д», которос выполняется только при х = 1. Наконец, третья форму. ла — зто истпиное высказывание о сушествоваинн наименьшего целого положительного числа.
Если бы в качестве области интерпретации мы рассматривали множество целых чисел, то третья формула была бы ложным высказыванием. Пример 1.30. Пусть М = <й, 1>, где Ьà — множество натуральных чисел,[ — соответствие, сопштавляюпГсе прслакатпым символам Зи)(х, у, х), Р<п(х, д, х) следуюшне преднкатыг 5Р~(х, д, х);х + д = х; Р"г(к, д,к); к.д =- з. Запишем формулы, истинные в М тогда и только тогда, когда выиолнсны следую(цне условии: а) х = 0; 6] х = 1г в) х — четное число; г) х — простое число; д),т = дг е) х<д; ж) к делит д; з) конмутагнввость сложения.
Ответы: а) Г, (х) = (Уд)5'гг(х, д, д), так как х ж у =- д для любого д тогда и только тогда, когда х 0; 6) Р,(х) [уд)Рш(х, д д); в) Р,(х) - (яд)ув(д, д, х); г) Р,[х) = -[РАЙ(х) й (Уд) (7х) (Р~«г(д, г, х) ю (Рз(д) т/Р» (х))), где Рь Р,— формулы, определенные в пи.
«а» и «бж д) Рг(х) = = (Ух)(фл)(Я~«~[х, х, и) г«У»'(д, х, и)); е) Р«(х, д) = = (Бх]бдв(х, х, д); ж) Рт(х, д) [Зх)РМ(х. х, д); з] [ух) Х х [уд)(ух)(5и [д д, ] Зшфд х, П. Пример 1.31. Пусть )(х) — «рок»вольная фиксированная функция, заданная на отрезке [а. ЕЬ !. Рассмотрим интерпретацию М <М, [,>, где М вЂ” множество дсйствптепьиык чисел; [, — соответствие, сопоставляюшес прсдикатпым снмволан Р(х. Ц, Я(х, е) и ][(е) прслнкать» Р[т, Ы: ]х — х«]<6, Я(х, е): [](х) — я[<«; Р(е):е>0. Здесь х, — фнкснрованныд злемеат отрезка [а, Ь); А — некоторое финсврованное действительное число, Тогда утвгрвгденне о тон.
что чнсло А — предал функции ](х) при х хь записывается. формулой (Уе) (ЯМ (Ух) ( [[[(з) й Р (х, 6) ) ш 9 (х, е) ). 2. Рассмотрим интерпретацию М=<М, ]т>, где М вЂ” множество действительных чисел, 1« — соответствие, сопогтзвлаю-' шее преднкатнын символам Р[х, 6], Я(е), 5(х, е) предпкаты[ Р(х,б): [х — х«(<6, й(к):к>0, 5(х, е): ([(х) — [(х«)[<к Злесь х« — произвольный фиксированный злемент отрезка (а. Ь] Тогда утверждение о гоч, что функция ](х) непрерывна в точке хи записывается формулод (т«)(ЯЦ(дх) ((Р(е) 6 Р(х, 6))ш5(х. е)). 3.
Рассмотрим пнтерпретацвю М <М, [«>, где Л[ — множество действительных чисел; [« — соответствие, сопостааляюшее вредикатным символам Р (х, хь Ь), )[(е), 5(х, хь 6), В(х» 76 ирсдикаты Рг(х, х„й):(х — х~( <Ь; )7(з):з>0; 5,(х, хь е) г ° ()(х) — ((ж) ( < е; О(х) ге си«а, В].
Тогда утверждение о то». что фунажя )(х) ненрерывна на отрезке «и, ь), жпнсываечсн формулой (Ухг) Руа)(АЬ)((гх)((О(х)йй(е)ЬР,(х, хь М)>б,(х,хг,е)). 1.42. Равносильность формул Пусть формулы Р о С имеют одно м то же множества свободяых переменнык (в частности, пустое). Формулы Р н О Равносильны е дсхнай янтсрггрсгпцнн, если на любом наборе значеяий свободных переменных они принимают одинаковые значения (т. е. если фарнулм выражают в данной интерпреташги одна н тот же прсдикат). Формулы Г н О раеяосихькм на множестве М, если онм равносильны во всех ввтерпретакнях.
заданных гга мнакестве М. Формулы Г н О Равносильны (в логике предпкапю), если енн равносильны на всех множсствак (тогда дулен писать Г О). йр р !.Ьй. 1. На множестве М = (и, Ь) зададим преднкаты Р,(х, р) я Р,(г, р) (см. табл. 1.!9 и (.Ю). Рассмотрим лве формулы: Аог~ (хь хП 6дгиг(»ь хз); Аю,(хь х,) Ьдгп,(хь х,) Тзсз н гхо та н Мп Р 1, х) И Л Л И Если облагтью ннтерпрстапнн служит множество М и формула Анг, интерпретируется квк преднкат Рь то формулы (1.6) и (1.7) равносильны в втой вмтерпретадии, так как припекают значение И только на двух наборах свободных переменных <а.а,а> н <Ь, Ь,Ь>.
Если областью пнтерпретанни япляется то же мважсства М, ио формула А<ей интернретируется иак преднкат Р» то форму. лы П.б) н (1.7) не равносильны, так как нз наборе <л, Ь, Ь> ф~рмула (1.6) принимает значение И, а формул» (1.7) — значение Л. 77 2 формулы (ух,)Аггг,(х,) и (ях,)А<гг,(х,) равцосильиы иа оанозлеиснтном мвогкествг. Цег]сгантельна, сели область иитерпретацви является олиоэлементиым множес~вом, та какой б» предвчат мы не взяли в качестве интерпретации А'», на этом множеств», он ирниимяет только адис значение: И илл Л. В первом случае обе формулы «рпнпмают значение И, ва втором — Л, и.
следовательно, пни равносильны на этом множ стае. С вру~ой стороны, на дюкэлеиеитнои ынажсстве (а, Ь) этп 3П мулы ие равносильны. Достаточно в качестве интерпретации '", расгчатреть предикат Р такой, что Р(а) = И, Р!Ц = Л. Уиажел! несколько прапил переходи ст одних формул к другиж ои равносильным (во всех интерпретациях). Очевидно, что для формул логики преднквтов сохраняются нсс рависсильисюи и привила равносильных про»бразпваинй логики высьазывзнпй. Крозге тата, можно доказать саедуюнпс правила: 1. Г!ереиос келигора чер э гиряцлиис. Пусть А — формула.
с держащая свободную иереченную х. Уогда справедливы равносильности -Птгх)А(х] (Як)-1А(х)! (1.8) -1(ях)д(к) (ух) -1 А(х). (1.9) Докажем сиаяал» равносильность (1.8). Пусть хл...., к!— множество (быть иажет, пустое) всех свабадпык переменных формулы А. отличных от х. Пусть М <М, (> — прои*воаьиая интерпретация. Докажем, что иа набам писаре зяачепмй своих свободнык переменных <с„..., а„>, а юМ, формулы 1(у. )А (х) и [ях] -1 А(х) принимают одинаковые истинно<таис значемпя.
Возможны два случаи: 1) дла любсга злсмснти аюМ А(х)]<,, э„> — — И; 2) ллв и коюржо элеыснта атглМ А(х) ]<а, я„> — — Л. В первом случае для любого элемента о ж М )АП)]< , ,„„> л. Отсюла па оирслеленяю (ях] 1 Ак(х) ( <, > =л. с другой сюроны. в этом случае (у.)А(х]]<, „> — — И. Отсюда )(ух)А(х)] > Л. Во взорам случае какэлемента исжм -1 А (х) ] <,, „> = П.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
