Математическая логика. Шапорев С.Д (1019113), страница 23
Текст из файла (страница 23)
х — связанная переьшниая, у — свободная; в> УхР(х)м Ууй(х, у) не является формулой, ибо в персон логическом слагаемом х — связанная псрсменнвж а во мором слагаемом свсболная. Пример 2. Даны утверждения А(и): "число и делится на 3", В(л); "число л делится на 2". С(л), "число я делится на 4", О(гг); "число л делится на б". Е(л). "число л делится на 12". Указать.
какие из слслуюших утверждений истинны, а какие .ю;кны. 1. Ул(А(л) о В(и) — э Е(п)). Рассмотрим составлянэщнс части этой формуяы. А(л)л В(л): "~испо и делится на б", А(л)л В(л) — э Е(л): щг Чесгь Г Маг мвпгч я ялмищ "если число л делится на 6, то оно делится на»2". При л =6 импликапня ложна, следователыю, исходная формула в общем ложна. 2. Лл(В(п) л С(п)-+ 3(п)).
Поступаем аналогично В(п) л С(л): "число дсяится на 4", В(п) л С(п)-» О(л): "если число дщится иа 4, то оно не делится на 6". Таксе может быть, например, при и =16. Следовательно, В(л)л С(л) — » О(п) — не тождественно ложная формула, а тогда Ел(В(п) л С(п) — » О(н)) — истинная формула алгебры предикатов. Пример Э. Большая теорема Ферма' угверпщает, что дпя любого целого п > 2 не существует натуральных чисел х, у,г, удовлетворяющих равенству х" .» у" = г" .
Если этому равенству поставить в соответствие предпкат Р(х, у,г,п), истинный тогда п только тогда, когда оно выполняется, а через М(х) обозначить предикат (х — натуральное число ), то теорема Ферма формулируется так; Мхцту» Рн(М(х)л М(у)л М(г)л М(п)л (л >2) — » Р(х,удбп)). Пример 4. ЗхР(х, у) — » з»хР(х, у) — формулщ содержащая свободную переменную у . Пусть Р(х, у) и»пер»»ретируется как х й у на 44 = [и, Ь).
Если Ь > у > а, то посылка истинна, а заключение ложно и формула ложна. Если взять у = а, то и левая, и правая части истинны и вся формула истинна, следовательно, формула выполнима в данной интерпретации Если Р(х,у) интерпретируется как х> у, ЬТ =(а,Ь), толевая часть будет всегда истинна гпр»г любом у), а правая — всегда ложна, следовательно, формула тождественна ложна в данной интерпретации. пример 5. Формула »Ух(Р(х)ч Р(х)) содержит только связанную переменную х. Эта формула является тождественно истинным высказыванием в любой интерпрпгации.
Напротив, формула Зх(Р(х)л Р(х))— тождественно лажная формула в любой интерпретации. Пмро сг ь»1601 — 144»» - фр нятз «Я и ь Раааа 3 Ловка лреднквгое 3.4. Практическое занятие Мя 7. Логические и кванторные операции над предикатами 3,44. Найти области истинносги сведуюгник предикатов: х +Эх+2 а) г х'+ех+3 х — !Эх+40>0 б) (' 2хг+х+30<0; в) з)их=к)ну; г) 13 х = 1й у.
3.4.2. Изобразить на диаграммах Эйлера-Венна области истинности длв слелующих предикатов: а) Ргх)ь-ь Ях), б) Р1х)-ь(фх)нЩ); в) Р(х)л фх) — г Ятх). 3.4.3. Записать предикатм, полученнме в результате логических операпнй над предикатами Р1х), фх) и Я1х), области истинности котормх заштрикованм на рис. ЗА-ЗЛ, ) ! рнс.
зн часов м тсыаючесяаллоия еде Рнс. З.Д Р с 3.4 Рит. Ъ.т 3.4.4 Установить, какие из следующих выскюывений истинны, а какие ломсны, при условии, что область определения предикатов М совпадает с ь: а) Ух((х' — бхь8д0)о(хт-бхь8< 0)); б) Лх(х' е хе 0.5 = О); Нала я Л яяа лредняаюе я) )Гх(х~ — 5хеб>0); г) Ях((л ц (2,5)) — > (х' -бх ч-8 = О)). з 3 ~4.5. Пусть >' — одноместный, 8 — двухместный, /г — трехмсстный функциональные символы Явля>отса ли термами следующие выражения? а) > (8 (х„х,)); б) 8'()ч(х>) 7>'(х,,х„,~)); ) У'(8'(Д Ф('5')) 3.4.6. Пусть уч, 8', ))' те жс, что и в предыдущей задаче, Р' — одноместный, Д вЂ” трехмсстный прсдикатные символы.
Явллютсв ли формуламн следующие выражения? а) Р (х„) — > )Г я (> > (х„.5, хз ) л ?Я ~ '(х„х ))); б) а'(Р'(;)?ч(5),.т'(;)): в) а'( „.7'(5) 6'( „.~,х>)) 3.4,7. Какие вхождения переменных являются свободными, а какие связанными в следующих формулах: а) З)х, (Р(д„х, ) — > з?х Д(д )); б) 55Щхз, хз) л Н(У(щ, х,)). 348. Пусть 5 (хух)=(хну= ), Р(худ)=(л у= я), х ухи Ф. Записать формулу с одной свободной переменной х, истинную тогда и только тогда, когда: а) х=0; б) х=2; в) х — четно.
3.4.9 При исходных данных задачи 3.4.8 записать формулу, выражающую: а) коммутатнвиость сложения; б) ассоциативность сложения; в) бесконечность множества простых чисел. я з„чзм Чамь 1. Ывгямвщч ся ел гняв !лв 34.10. Привести примеры таких значений а, для которых ленное высказывание: 1. Истинно 2. Ложно (М= Л). а) Ел<0(хз оплел =О); б) Ехн (а,о ь1йхл — х — 2<0). Записать, введя необходимые предикаты, в зиле формулы логики предикатов следующие рассуждения. 3 4.!!. Если всякий разумный философ — циник, и только женщины явл»- ются разумными философами, то озгдж если существуют рязумныс философы, некоторые из женщин — ~анники.
3.4.12. Все политики — лицедеи. Некоторые лицедеи — лицемеры. Значит, некоторые политики — лицемеры. 3.4.13. Глупец был бы способен на это. Я на зто не способен. Значит я нс глупец. 3.4.14. Друг моего друга — мой друг. 3.4.15. Каждый я~сбит свм себя. Значит, кого-то кто-нибудь любит. 3.5. Равносильные формулы логики лредикатов Две формулы вогнки предикатов А н В уояносняьны а данной июлеряремолин, если на любом наборе значений свободных переменных они принимают одинаковые значения, т, е.
формулы выражают в данной интерпретации один и тат же предихат. Две формулы логики предикатов А н В называются ргмнос~аьнымн но ооласти М, если они принимают одинаковые логические значения при всех входящих а ник переменных, отнесенных к области М . Две формулы логики предикатов называются ровасснльдыми, если они равносильны на всякой области. Все равносильности алгебры высказываний будут верны, если в инх вместо переменных высказываний полсзааить формулы алгебры преднкатов. Кроме того, имеются равнасияьиости самой логики оредикатов, связанные с кван- !лаю э Л гикал днк ов торами.
Пусть А(х) В(х) — переменные прсдикаты, а С вЂ” переменное вы. Скалывание. Тогда имеют место следующие формулы. 1. ЗУхА(т)м ВхА(х), читается, "высказывание "не верно, 'по дл» вюбого х А(х) истинно" эквивалентно высказыванию "найдется х, для которого А(х) ложно"". 2. БА~х)м зУхА(х). 3, !Ухб(х) = — ЗхА(х). 4. эхА(х) — = зУхА(х). 5. ЧхА(х)ау!хв(х)м'Ух(А(х)лВ(х)), т.е. квантор всеобщности можно вносить и выносить за скобки в коныонкции. 6 СлХгхв(х)мэУх(сов(х)).
С о ВхВ(х) и эУх(с о В(г)). б. С-ээУхВ(х)и Рх(С- В(х)). Я. эУх(в(х)-» С)м !Утв(х) — э С. Для формул б — 9 справедливо утверждение, постоянное вьюкэзывацие можно вносить под знак «вантора всеобщности и выносить из-под знака этого кваитора в конъюнкции, дизъюнкции и импликации 10.
йхб(х)о Вхв(х) и лх(А(х)зг В(з)) — квантар суцгествования мегино вносить и вышюить за скобки в дизъюнкции. !1. С л ЗхВ(х) и Бх(С л В(х)). 1г. СчЬхВ(х) Вх(соВ(х)). !З. Сэв В(х)мВх(С-э В(х)). !4 Зх(в(х) — + С) — Эхв(х)-э С. Дли формул !! — 14 справедлива утвержлоние пощояннос высказывание можно выносить и вносьпь под знак квантора существования и выггоспзь изпод этого квантора в конъюнкции, дизъюнкции и имплнкации. 15. БхА(х)л Вхв(х)и Бхву(А(х)л В(у)). !б. Вхд(х) ч У!хв(х) = ьххтУФ Мх) г В(у)).
Ч гьгХГаг ме ч яаялоок Все приведенные равносильности могут быть доказаны. Первые две формулы назьзваютс» ириеилами лерглоса кяонморов через оягрнцаяне. Докажем, наприьгер, первую из них. Пусть хохз,...,х, — множество сможет и пустое) всех свободных переменных формулы А, отличных от х. Пусть М = (М, З ) — произвольная интерпретация. Рассмотрим произволмгмй набор значений свободных переменных аоаз„,а„е М и исследуем, какие логические значения при этом наборе примут формулм 9хдч(х) н ЗхА(х) Здесь возможны два случая: 1.
Длялюбогоэлемента аб М А(хб, =1. 2. Для некоторого элемента осб М А(х) =О В первом случае лля любого элемента об М АЦ = О. Отсюда по определению ЗхА(х) = О. Ио с другой стороны, чхА(х) =1, 3- т. к. 1Уа и М А(х1 = 1, отсюда ч'хг1(х ( = О, т. е. ЧйГх) и В А(х). Во втором случае дяв ие б М А(х) = 1, отсюда ЧАИ = 1. С другой стороны, в этом случае 1гхА(х1 =О. Следовательно, З1йЯ = 1.
Таким образом, исходная равносильность полностью доказана. Обратим внимание на формулы 5, 1О, 15 и 1б. Видно, что, например. пхА(х)л нхВ(х) и Лх(А(х)л В(х)). для квантора всеобщности такая формула нмееюя. Здесь же ВзА(х)л ИхВ(х) и Лхд(х) л ЛуВ(у) =— =— Ь (А(х) л ЗуВ(у)) = — ВхВу(А(х) л В(у)) — формула 15 Аналогично, гухА(х)чьухВ(х)и гул(А(х)ч В(х)). Так же получим зухА(х)чтухВ(х)и и тУхА(х) ч 1ууВ(у ) н 1Гх(А(х) ч 'буВЯ) и ЧхВу(А(х) ч В(у)). В заключение упомянем правила переименования связанных переменим». Очевидно, заменяя связанную переменную формулы А другой переменной, не входящей вату формулу, в кванторе и всюду в области действия квантора получаем формулу, равносильную А .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
