Математическая логика. Шапорев С.Д (1019113), страница 32
Текст из файла (страница 32)
Исходное множество дизъюнктов противоречиво. Пример 4. Г~ — 'гУ ф~Р (х) л Р (х)) — з Лт(Р (з, у) д Р (у))),'чт(Р (т) — з Р (т)), лх(Рз (х) а Р (х)л тУУ(Рз (х у) е Рз (у)))). Проверим ла противщ рееивссть зта множество, прелварительно приведя все формулы к 'У-форме. ЬЬЬ,ЬЗ Ыаа, Ьеойащ.рви,хвд гну(Рз(ху)дР (у)))и тдхЗу((Р(х) и Р (х) г Р (х у)), (Р (х). Рт(х) г ч Р, (у))) Квантер существования опустим, введя скулемовскую функнию у = у (х), которая по всякому т найлет лля него шипение у Тозда получим зу-формугзу ьгх((Р(т)ч Рз~(х)ч Р(хДх)))л (Р(х)ч Рз(х) Р (4(т)))) Честь С Мемметьчесмм лопни Теперь опуотим знак квеитора всеобщности, предполагя», нто докюательство будет проведено для всякого фиксированного х.
Аналогично, Р", = Лх(уз(х)л Р(х) и тУу(Рз(ху) — ь Р(у))) ° и ЗхьУу~з (х) л Р(х)л (Рз (х у) ч Рз(у) ). Опустим знак кванторв суще- ствования, стоящий перед всей формулой, предположив, ято доказа- тельство будет проведено для некоторого фиксирамнного .т = а, но т. к. х — любое значение, то оно будет справедливо лля всех случаев. Тогда Му(Рз(а)з Р(а У (Рз(а, у)чР (у)). Отбросим теперь квантор всеобщности, рассуждая как в предыдущем случае, Г, ='Ох(рз(х)-+ Р (х) мтУх(Рз(х)ч РЯх)) Таким обрезом, множество дизьюнктов имеет вид Г = ~(х) ч Р (х)ч Р (к, Ях)) Р (х) ч Р (х) ч Р (х) РЯа) Р (а) РЯа, у)ч ч Рз(у) Р(х)ч Рз(х)?= ф, Гз,Гм Гюрз,Гь).
Исслеяуем это множест- во не выполнимость с помощью методе резолюций. Найдем гез(ÄÄ) А, =РЯх) "Ч=Р,(х) О=(аЦ ГО ч Г В = Р (а)ч Р(а)ч Рз(а,((а))ч Р(а), Г, =гез(ГмГ,)=Р(а)чРз(а, Г(а)); ггз(Äà )=? А, = Р (а,у) ~ =Рз(а,У(а)) О=(Г(а1у) ГзбчГО =Р (а,у(а))чР(((а))ч Р(а)чР (а,)(а)). Гь = гсз(Гз,Ет)= Рз(а)ЧРз(т(а)) гез(ГыГ,)=? А =Р(х) А, =Р,(а) В=Цх?, Г О чу'„О= Рз(а)ч Рз(т (а))ч Р, (а)ч Рз(а), ' = *( „Г,)=,( ) Ю( )): гез(ЄЄ)=? т~ =Р(х), А, =Р,(а) О=(а/х), Гтбч Г В = Р (а) ч Рз (а) ч Р Яо)) ч Р (а), Гн = ггз(Г,,Гь)= Рт(а)ЧР (г(а)) гез(Гь, Рз) = А, = Р,(х) А, = Р,(а) О = фф], Главах Исчг л ниеп дика в Е О г Е В = РЯа ) г Рл (а) ч Р (а) ч Рз (Г(а)), Рп = гех(Еь,Гз)= Р (а)чР (Р(и)); гех(Е„Е,)=? А, = Р,(г) А, =Р,(у), 8=-(х1у), Г О г Еьб = Рз(и х)ч Р (х1 г Р (л)ч Рз(х), Гп — - гез(Гг Еь)= Р,(к)чР,(а,х); тех(Г,,Гп)= Р А, =Р(ху А, = Р(п), 8=(гг)х).
Гбч 1', О =Рг(а)чр(ал (а))ч Р(к)чР(аа), Гп = тех(Е,, Рп) = Р (па) г Рз(ГХ(а)). Нахождение други» резольвент икжс не дает вывод нуля, слеаовательно, исходное множество выполнимо, т е в сиг натуре Х = (Ро Рз, Р,, Р,Ры ),а) формулы из множества Г, истинны Пример 5. Дока кем правильность рассуждения 3.4 11.
(Чк(Р(к) — ь 1т(х)) о зУх(1 (т) — ь 11(х))) — г (йхР(к) — ь Ьт((Г(л)л й(х))) . По методу резолюпий,чтобы й лА, л...лА„— г А=1, необходимо, чтобы (А„Аз,..., А„, А)1- Преобразуем посыяку и следствие основной формульг. (гУх(Р(т)ч Мк))л тУх(Р(х) ч Я~х)))м(Мк(Р(т) ч Р(х))г (Трк) ч фл))). ЗкР кх)ч Лх(Й(к) л 11(х)) и ГУкР 8)ч Зх(ьУ(х) о й(х)) м ьУкр (х)ч г Лу(П(у) л й(у)) и ьУхЬ (Р(т) ч (фу) л й(у))) Найлсм теперь отрипвние слелствия импли капни ~~() "ЬГ)ев й ('ЬГ.661"Мй)) Квантер существования отбросим, подставив вместо предметной переменной х констангу а Отбросив теперь в посьщке и следствии кванторы всеобщности и предпсяожнв, что доказательство проводится лля любых значений предметных переменп, получим многкестео дизьюнкгов Г, = (Р(к)ч й(х) Р(х)ч Д(к) Р(гг)0(у) ч Р(у)~ (ум Ел,Ег,Е, » гго Ч гь 1.
Ыагемагнчеыаллсп ка Для того чтобы доказать, чю исходное рассуждение правильно, необходима из Г, получить резолютивный вывод нуля: Р, = гсз(Р„Р,) = Я(п), Г, = сз(Р„Рг)- Ц~), Г, =- (;.Р,)= Ртп), гсз (Г,, Г, ) = 0. 4.10. Практическое занятие 1)бй 10. Унификация формул. Метод резолюций в исчислении предикатов 4.10.1. Построить все попарные композиции 0,0, подстанавок 0, =(Р(у~х,р,(х,ф,с,')г), 0 =(Р,(Р(х)у)х,Р(с,)у Р(г)г), О, =(Рз(с)хат~ух(г) и О, =(у~х,г)ух>г) сигнатуры 4.!Обй Определить, унифицируемо ли множества Г. В случае унифицируеиасти найти наиболее абгций унификатор: а) Г=(Р(с,х,Р,(Р(у)))Р(г,Р,(г) Рз(н))); > =(ж(М(х)) (>Ч ))1 в) Г = (Р(с,х) Р(с,с)); г) Г = (Р(с, х, Р (х)) Р(с, у, у)); д) Г = (Р (и, Р (х, у))Р(у, г) Р(п, ГЧ (с, г))).
4,100. Определить, имеют ли склейки следующие днзьюнкты. Если склейки имеются, найти их: а) Р(х)ч Р(Р(у))ч Р,(г); б) Р (х) ч Р (у)ч Р (Г(х)); в) Г (х)чРз(»)чР,(Рз(с))чР,(г)чР,(г) Глава Е. Исии ленив л ди«мюв гзз Найти все возможные резал ьвенты следующих пар дию«онхз он 4Л04 а) Р«(к) и Р (к) Р (с)ч Р (х); б) Р (х)н Рз(к,х)Ра(с,Р(с)); в) Р(и)н Ц(к,Ь) Р(х)н фЬ,») 4.!0.5. Проверить, выполнимо ли множество формул; Р = УХУ»(Р«(к,у) — «Рз(х,у)) а) Рз =УХУ»(Рз(х,у) — «Рз(т,у)) ) з ЗХЗ»Р~ (х у)' Г, = Р,(с,, Г(сз) з"(сз)) = ) г(с«) Рз з= Р, (х, к, » (х)) рз = з«(х у' г)н)з(» г) Гз = Рз(з)н Р«(н,си) «)з(х и)н Р (л,У)н Рз(х, ) Рь —— Рз (си сз ); б) а) ()У гВ(Ь, г, г) и Зн А(Ь ы Ь)) л (УиВ(и, и, и) и УуУгЛ(у, у, г))) — « — «((ЗиВ(ю,с,ю)лЗиА(и,и,и))н(ЗмУиВ(Ь,и,ю)лЗХУхВ(х,с,г))); б) ((УиЗ«»А(Ьи,ж)ч В(с с с)н З«ыУиА(и,сю) «Уыб(би,ю))л л (У«ыЗиВ(в,и,а))) — «(ЗнА(и,с,а)л ЗнЗюВ(ж,ы,ы))н н((З»З«»В(Ь,н,м)лЗХЛ(г,с, )лЗХУ»В(у,х,а))) в) (Зм4(и Ь с) — «(ЗнЗи В(«, ты) — «З 1(Ь н «)))л (ЗуВ(а у а) и нУХАЬ,х,к)н УхУиВ(х,и,Ь))-«((УтА(х,кзс)-«З»Зг4Ь,у,г))н нВ(и,а,Ь)); т) (ЗхУуЗгВ(х, у, г)) л (ЗиУ»Ухд(и, лз у) и УХЗ ХВ(к, а, г)) л л (Уг ЗхВ (г, и, х) — «УиЗнУ и В(и, н, и )) — «ЗиЗ«У«ыЛ(и, «, ы) л л ЗнЗ«ыУиА(в,н,и); в) Р; = Ух Р(х) — «Уу Р(у) — «(х)-«Д(у) чУгр(г) 4Л0,6.
Проворить истинность следующих формул методом резолюций Часть Г. Мвгем ги есяаягюгию 2Г2 д) (МизгттгвА(и, и, в)ч тгхЗуВ(х,б, у) и зУизггс(и, и,ь))л л (Зтд (х, а, Ь ) и тгуЗ 2 В (а, у, г) и згзг згиС(г, и, а)) л л (1 в В(п, Ь, в)) — з (тгггЗиЗ в С(и, и, в) л ЗхсуЗгС(х, у, г)); ег (Зузггз(у,а,г) — «згггзгтА(б,и,и))л л (тат тА (г, и, а) и Ч уЗийгВ (и, у, г)) и (т 2 В(г, г, г)) -з — з (Зуб(а, у, гз) л ЗхзгуЗгА(х, у, г)) ч ЗитггЗвА(н, и, и ). 4.11. Некоторые проблемы аксиоматического исчисления преййикатов Разрешимость Пробдема, заключающаяся в отыскании алгоритма, решающего ту или иную серию однотипных задач, иазыаастся шггоригпиичесхой ираблелгой разрешимосгви Неразрешимость алгоритмической проблемы означает, что такой алгоритм невозможен Просшйший пример проблемы разрешимости — проблема разрешимости алгебры логики, которая состоит в отыскании алгорнгма, позволяющего дия любой формулы алгебры логики установить, яаляеюя лн она тождественно истинной, тождеспюнно лшкной или вьшолниьгой.
Для югсбры логики этв проблема решена. Проблеча рюрешимости для исчисления преднкатов, в отличие аг исчисления высказываний, оказалась связанной с серьезными трудностями, зависящими от точного определения понатия алгоритма. После появяеиия точного определения алгоритма появилась возможность докюать, что проблема разрешимости для исчисяения предикатов неразрешима, т е.
необходиьгый в этой проблеьге алгоритм невозможен гси, теорему З.В). Непротиворечивость и независимость Пратиаоречиеым назьгвются такое исчисление, в котором какая-либо формула доказуема вместо со своим отринаниеьь Эга проблема для исчисления преликатов решается в положительном смысле. Для доказательства непротиворечивости достаточно обнаружить какую-нибудь невыводимую формулу в исчислении прсдикатов. Можно показать, что всякой выводимой формуле исчисления предикатов соответствует выводиьзая формула исчисления высказываний, дл» которою Глава 4. Исчисление лредяшгав лгэ проблема непротиворечивости ренмиа.
Отсюда немедленно следует непротиворечивость исчисления предикатов. В свмом деле, если бы исчисление предикатов было противоречиво, то в нем всякая формула была бы выводимой. В частности, была бы выводима форнула А, состоящая нз одной буквы. Но югда А бмла бы выводима и в исчислении высказываний, что не верно Помимо непротиворечивости возникает вопрос о выводимоши каждой аксиомы из остальных. Эго вопрос независимсюти системы аксиом. Система аксиом исчисления предикатов — независимая система Независимость аксном пзворит а том, что в системе нет лишних аксиом.
Эту независимость можно установить посредством интерпретации. Дцстод игперпретаций, олнако, приложим к вопросам независимости только в известных границах. В разделе 2.б обсуждался вопрос независимости аксиом исчисления высказываний. Вопрос о независимости аксиом обычна ставится лля непротиворечивых систем. В этом случае ограничивмотся сведением независимости к вопросу о непротиворечивости данной системы аксиом. Полноте в узком смысле Логическа» система называется полной в узком смысле, если нельзя без противоречия присОединить к ее аксиомам в качестве новой аксиомы никакую не выводимую в ней формулу так, чтобы полученная при згоьг система была бы непротиворечивой.
В отличие от исчисления выскаияваний, исчисление предикатов оказывается неполным в узком сммсле. К его аксиомам можно присоединить без противоречия недоказуемую в нем формулу Эхл(х) — з цхр(х). Все предметы тождественны — таков содержательный смысл этой формулы Приведем лля доказательства лишь соображения, носящие общий карактер. Кюкдая выводимая формула исчисления высказываний имеет выводимый аналог в исчисяении цредикатов и может быть присоединена к аксиомам этого исчисления. Например, такая: А — з А. Она выводима в исчислении высказываний. Если область определения М предиката Р(х) сошоит из одного элемента х, то А-з А превращается в исчислении преликатов в формулу лхлзх) — з уухргх).
которая будет истинной Она не будет истинной, если М солержит больше, чем один элеиеит. Однако из общелогических положенид нельзя заключить, что область М содержит более одного элемента Таким образом, исчисление предикатов неполно в узком смысле. лге Часгь Г Магсмапм кая логика Полнота в широком смысле Логическая система плана в широком смысле, если любая тождественно истинная формула в нем доказуема. На основании теоремы Геделя проблема полноты в широком смысле решается для исчисления предикатов полоисительиым образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
