Математическая логика. Шапорев С.Д (1019113), страница 22
Текст из файла (страница 22)
Рассмотрим предикат Р(х), определенный на множестве М = (а„а„...,а„). содержащем конечное число элементов. Если Р(х) является тождественно истинным, то истинными будут высказывания Р(л,)Р(лз)..,Р(а„) При этом истиннымн будут высказывание тдхР(х) и конъюнкци» Р(а,)лР(а,)л,,лР(о„). Если же хотя бы дл» одного элемента а, б М Р(а,) = О, то ложными будут высказывание Ктр(х) и конъюнкция Р(а, ) л Р(а, ) л ... л Р(а, ). Следовательно, справедлива равносильность гУхР(х) — Р(л,)л Р(аз) л,, л Р(л„), О Калггторсэщясжеоятгия Б. Пусть Р(х) — предикат, хц М. Под выражением ЕхР(х) понимают высказывание, истинное, если существует элемент хб М, для которого Р(х) истинно, и лажное в противном случае, Символ 3 называется кеаюлором суюеслжоеллия текгзг — существовать).
Словесное выражение звучит так: лава Э Логика и икагол тсг "существуетх, при котором Р(х) истинно". Высказывание Ь:Р(х) уже не зависит от х, переменная х связана квантором Б. Аначогичные рассужпення, как н в предыдущем случае, позволя|от установить равносильность эхР(х) — = Р(а,)о Р(а,)м .. ч Р(л„). Ясна, что высказывание тхр(х) истинно только в том единственном случае, когда Р(х)— тождественно истинный предикат, а высказывание ЗхР(х) ложно только тогда, когла Р(х) — тождественно ложный предикат. Кванторные операции применяются и к многоместным предикатаьг. Применение кванторнай операции к предикату Р(х, у) по переменной х щавит в соответствие двухместному предикату Р(х, у) одноместный прсдикат тУхР(х, у) илн пхР(х, у), зависящий от у и не зависящий от,т. К двухместному предикату можно применить кванторные операции по обеим переменным. Тогда получим носемь высказываний: К тУхтУур(х, у); Ъ В Уур(х,у); 3.
ьУхЗуР(х, у); 4. ЗмЗуР(х, у); 5. УуУхР(х, у); б. ЗутУхР(х, у); 7. зУузхр(х,у); 8. ЗублР(х, у). В общем случае изменение порядка кщдаванна квантороа изменяю смысл вЫсказывания и его загическос зна синс, т.с например, высказывания тУхтУуР(х, у) и ьУугУхР(х, у) различны Пусть предикат М (х, у) означает, що ь является матерью лля у, тогда УупхМ(х,у) означает, что у каждого человека есть мать — истинное утверждение. ЭхЧуМ(х,у) означает, что существует мать всех людей ИстиннОсть этого утвержлення зависит ог множества значений, ко~орые могут принимать у, если это множество братьев и сестер, то оно истинно.
в противном случае оно ложно. Таким образом. перестановка квантаров все- Чаюь 1 Маг магич свая логика Гчл общнаатн и существования может излэенить сам смысл н значение вырюксния. Квантер существования Б можно вырази~ ь через квантар всеобщности применительно к предикату А(х), йхд (х) = лУхл(х) 1см. Рлэгз 3 5). Полезна выяснить теоретико-множественный смысл кванторов. Оказывается, квантары связаны с геоиетрнческой операцией проектирования.
Рассмотрим одноместный предикат Р (х)= 3ур (х, у). Пусть множество истинности предиката Р(х) — 1р:. Однако выражение ЗУР(х,у) истинно для данного конкретного хэ только тогда, когда существует такое у, что Р(х, у) истинно. Таким образом, функции Р(х, у) отвечает часть !р множестш М, х М, = М'. Тогда 1г состоит нз ваех тек элементов х области М„дяя которых найдена пара (х, у)е 1р. Если считать х, проекцией пары (хл, у), тогда 1р вать проекция 1 . Множество истинности 1р О М двунерного предиката Р(х, у) можно рассматривать «ак плоскость, а М, — как ось Ох этой плоскости.
Таким образом, множество 1р, являющееся областью истинности предикаш Р(х), совпадает с ортогональной проекцией множества 1р ивась Ох,т е. 13.2.1) 1г =пр,ур. Квантер всеобплиости можно выразить с помощью квантора существования 1см.разо 352 Пусть Р,(х)=ЛУуР(х, у), тогда УуР(х,у)=ЬуРгх,у). Операции отрицания соответствует теоретииэ-множественнмл операция дополнения. Следоватааьно, 1н = и 1 пр,(и 1 1,), 13.2 ай т.е. множество, отвечающее функции лУуР (х,у), есть дополнение к проекции на М, — дополнения к 1р. Пример 1.Установить истинность или ложность высказывания Эх(хи (25)-л (х -бха8= 0)). хз — бх+8=0, х,, =ЗдЯ вЂ” 8 =381, х, =2, х, =4. Исходное высказывание преобразуем к виду: Зх (х и (25) — л (х — 6х + 8 = О)) = йх~ Н (25 )ч (х' — бх + 8 = О)) и !40 Глава Э Ло нва лр длввгсв — Дл(хй (25)о хи (2 4)) ж Дх(хб )24)) Искоднас высказывание истинно Пример 2.
Установить истинность ю»и ложность высквэывацил Ух(х — 5х 4- 6 = О). Действуем аналогично 5 )25 24 5 ! хл — 5х ь 6 = 0 .т, 1 = — 4 ) — — — = — ф —, х! = 2. хл = 3 2 3»4 4 2 2 Но (хг -5х 46 = О) и Лх < 2 о л > 3), поэтому любым х не может бытц исходное «ыскаэьжание ложно. З.З.
Формулы логики предикатов В логике прсликатов пол ьэуютсв с»галу»ощей символикой: !. Символы Рл,пыг! — псРеменные выакаэь»ванна 2. Предметные переменные н прсдметныс константы хс,у»,хэ, ха,у,с! сМ. 3. Р, ',л, и Ч вЂ” предикатныс симеоны, Р; — л,-местный преднкатный символ 4. !"",п, б ьт — функцнональныс символы, !",ь — л -мсатный функцн» опальный символ. 5. Симам»ы логических операций л,у,-»,,4-» .
6 Символы кванторпых операций Ч,В 7. Вспомогательные символы, скобки, запятые. Множество прсдлкатньж букв вместе с множсстволг функциопатьных бука и коистанг называкися снгнагяурои язь»кв данной теории. 'герман сигнатуры языка логики предикатов явлжотся: !. Предмет ные переменные и прсдметныс люнстанты 2. Вели Р' — и-местный фУпкцнанвльный символ и !ог,,,! — тсРмы. то / "(го1г,...,г„) — теРм Часы т.
маг»мягки ока»»вика Лягохгиай тики атомарной) форнуюй политуры иазыеаетса выражение Р" (г„г„,,т„), где Р" — л-местный предикатиый символ, а гог,.,.,г„— термы. Формулой югики предика»зов называется »сякое выражение, содержащее символику 1 — 7 и удовлетворяющее следующим требованиям: О атомарная формула есть формула; О если А н  — формулы, то А л В, А ч В, А — э  — тоже формулы при условии, что одна и та же предметная переменная не являетс» » А свободной, а» В связанной или наоборот; О если А — формула, топ А - - тоже бюрмула; О если Л(х) — формула, то зУхА(х) и Бхй(х) являются формулами, при.
чем если в А(х) х — свободная переменна», то в чхд(х) и ЕхА(х) будет уже связанной переменной. Все предметные переменные атомарных формул с»ободные, саязанных переменных нет, Витерагьлымн нззыеаются формулы А или А, где А— атомарная формула. Из этого определения ясно, что всяка» формула алгебры высказываний является формулой логики предикатов. Если Р— символ предиката, а хнх,,...,х„ — символы предметных переменных, не обюательно различные, то Р(хох,,х„) — формула. Пусть А — формула, содержаща» свободную переменную х Тогда зУ»А и Ехд тоже формулы. В тхА формула А называется обласюыо действие к»а»тора 'ч', в Вхд областью дейст»и» к»актера 3.
бэормулв А называется эпик»умой формулой, если всякое вхождение переменной в А яеляетсл связанным. подслопо формулы А, «оторсе само «еляетс» формулой, называется лоы фармУ год формулы А Значение формулы определено лищь тогда, когда задана кака»-нибудь интерпретация »ходящих в нее символов. Под интерпретацией понимается система М = (М,Р), состояща» из мену»того множества М гобл»ать определения) и соответствия (функции) у, сопоставлящщега кюкдочу предикатиому символу Р определенный н -местный предикат Р(г,.,.,) При заданной интерпретации считают, что предметные переменные пробегают множество М, а символы л, щ-о,, т-е, Тг,й имеют слой обычный смысл. рлвва 3 Пшика лредиююя Для данной интерпреталин каждая формула без свободных персмснныч предсэагшяст собой высказывание.
которое истинно иэн полена, а всякая формула со своболными псременнымн выра»каст некоторый прсдиквт на множестве М, который истииси прн одних значениях переменных из э»ого множества и ложен при других О логическом значении формулы логики преликатов можно говорить лишь тогда. когда задано мноэкссэво М, на котором определены входящие в эту формулу преппкаты. Логичсскос значение формулы .»огики предикатов зависит от зна»сний трех видов переменных: значений переменных шасказываний, вход»»щг»х в формулу, значений свободных предметных псремсиньш из множества М , з. с т, у,..., и значений прсдикатных псрсменны» Р( )1'„>(г,...г).
Если фиксировать значения каждого из этих трез индов персменных, формула алгебры логики преликатов становится высказыванием, имеющим истинное ияи лоя»шэс значение. Исти»»ь»ссть или по»кипеть фориул логики предикатов маэкст быть проверена путем гриписывания сьгысла языковым консгрукпиям, т. с. их интерпретации, формула в зависимости от игггсрпрегации может быть истинной или ложной, но маэкет от нее и нс зависел . Дэя того чтоб»я определить ни гсрпрстацию, необходимо задать мнох»сство значений, которые ышут принимать свободные псремс»шыс, операции, приписываемые функпионачь»»ым символам, отношения для прсдикатньш оимвоэав.
Пример 1. Является ли данное выражение формулой логики прели-катив? а> (Р(х)» >2>(х))ьйу(У>В(у)) не является формулой, т.к. квантор сушссгвования употреблен для уэкс се»манной «вантором всеобщности переменной у; б> Р— Ь ЭУхь>(х, у) — формула алгебры предикатов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
