Лекции В.А. Захарова, страница 27

PDF-файл Лекции В.А. Захарова, страница 27 Математическая логика и логическое программирование (53065): Лекции - 7 семестрЛекции В.А. Захарова: Математическая логика и логическое программирование - PDF, страница 27 (53065) - СтудИзба2019-09-18СтудИзба

Описание файла

PDF-файл из архива "Лекции В.А. Захарова", который расположен в категории "". Всё это находится в предмете "математическая логика и логическое программирование" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 27 страницы из PDF

?R(b) t6?t?t?Q(V ), R(b)@I@@@@@@R t?R(b)@6?tДерево SLD-резолютивных вычисленийПрограмма P:P(X , Y ) ← R(X ), !, Q(Y );P(X , X ) ← Q(X );R(b) ←;Q(c) ←;Q(b) ←; ?P(U, V ), R(U)t@ ?Q(U), R(U)Rt@∗(1)(2)(3)(4)(5)!?t?R(U), , Q(V ), R(U)t?!, Q(V ), R(b)∗?6Сработал оператор отсечения.Построение деревавычислений завершено. ?R(b) tПри этом часть ветвейбыла отсечена.6?t?t?Q(V ), R(b)@I@@@@@@R t?R(b)@6?tОПЕРАТОР ОТСЕЧЕНИЯПрограммное утверждениеA0 ← A1 , . . .

, Ak , !, Ak+1 , . . . , An ;содержащее оператор отсечения можно прочитывать двояко:IЧтобы решить задачу A0 нужно найти только первоерешение задач A1 , . . . , Ak и далее решать задачиAk+1 , . . . , An . Если решение задач A1 , . . . , Ak найти неудается, то воспользоваться альтернативнымипроцедурами решения задачи A0 .IЧтобы решить задачу A0 нужно проверить условияA1 , .

. . , Ak . Если эти условия выполнены, то приступить крешению задач Ak+1 , . . . , An и не обращаться к другимвариантам решения задачи A0 . Если же эти условия невыполнены, то обратиться к альтернативным способамрешения задачи A0 .ОПЕРАТОР ОТСЕЧЕНИЯТаким образом, оператор отсечения позволяет удобноиспользовать в логическом программировании стандартныеконструкции императивного программирования.IВетвление. S0 : if P then S1 else S2 fiPif −then−else : S0 ← P, !, S1 ;S0 ← S2 ;IИтерация. S0 : while P do S1 odPwhile−do : S0 ← P, !, S1 , S0 ;S0 ←;ОПЕРАТОР ОТСЕЧЕНИЯС введением в логические программы оператора отсечениятеорема полноты операцинной семантики относительнодекларативной семантики перестают быть справедливыми.ОПЕРАТОР ОТСЕЧЕНИЯПрограммы P1 и P2 вычисления гласных буквP1Elem_Vow (X , XElem_Vow (X , ZVowel(a) ←;Vowel(e) ←;Vowel(i) ←;Vowel(o) ←;Vowel(u) ←;Vowel(y ) ←;..P2Y ) ← Vowel(X );Y ) ← Elem_Vow (X , Y );..!Elem_Vow (X , X Y ) ← Vowel(X ), ;ElemV ow (X , Z Y ) ← Elem_Vow (X , Y );Vowel(a) ←;Vowel(e) ←;Vowel(i) ←;Vowel(o) ←;Vowel(u) ←;Vowel(y ) ←;равносильны в декларативной семантике , и запрос...G :?Elem_Vow (X , o n e nil)для обеих программ имеет два правильных ответа θ1 = {X /o}и θ2 = {X /e}.ОПЕРАТОР ОТСЕЧЕНИЯПрограммы P1 и P2 вычисления гласных буквP1Elem_Vow (X , XElem_Vow (X , ZVowel(a) ←;Vowel(e) ←;Vowel(i) ←;Vowel(o) ←;Vowel(u) ←;Vowel(y ) ←;..P2Y ) ← Vowel(X );Y ) ← Elem_Vow (X , Y );..!Elem_Vow (X , X Y ) ← Vowel(X ), ;ElemV ow (X , Z Y ) ← Elem_Vow (X , Y );Vowel(a) ←;Vowel(e) ←;Vowel(i) ←;Vowel(o) ←;Vowel(u) ←;Vowel(y ) ←;но неравносильны в операционной семантике : запрос...G :?Elem_Vow (X , o n e nil)к P1 вычисляет θ1 = {X /o} и θ2 = {X /e},а тот же запрос к P2 вычисляет только θ1 = {X /o}.ОПЕРАТОР ОТСЕЧЕНИЯС введением в логические программы оператора отсечениятеорема полноты операцинной семантики относительнодекларативной семантики перестает быть справедливыми.Поэтому оператором отсеченияосторожно.! нужно пользоваться оченьА что еще полезного и удобногоможно встроить в логические программы?КОНЕЦ ЛЕКЦИИ 16.Основыматематическойлогики и логическогопрограммированияЛЕКТОР: В.А.

ЗахаровЛекция 17.Отрицание в логическомпрограммировании.Оператор not.Встроенные предикаты ифункции.Оператор вычисления значений.Модификация баз данных.ОТРИЦАНИЕ В ЛОГИЧЕСКОМПРОГРАММИРОВАНИИОтрицание ¬ — это очень полезная логическая связка. Частомы обращаемся с вопросами, используя отрицание.ПримерP : птица(орел) ←;птица(воробей) ←;птица(пингвин) ←;летает(орел) ←;летает(воробей) ←;летает(самолет) ←;Сформулируем вопрос: какая птица не летает?G : ? птица(X ), ¬летает(X )Какой ответ мы ожидаем получить на этот запрос?ОТРИЦАНИЕ В ЛОГИЧЕСКОМПРОГРАММИРОВАНИИПримерС точки зрения декларативной семантики, для полученияответа на этот запрос нужно выяснить, выполняется лилогическое следованиеP |= ∃X (птица(X )&¬летает(X )),где P = {птица(орел), птица(воробей), птица(пингвин),летает(орел), летает(воробей), летает(самолет)}Оно не выполняется, т.

к.BP |= P, BP 6|= ∃X (птица(X )&¬летает(X )).Значит, ответ на этот запрос должен быть отрицательным:такой птицы нет .ОТРИЦАНИЕ В ЛОГИЧЕСКОМПРОГРАММИРОВАНИИПримерОднако в обыденной жизни мы в таких случаях даем совсемдругой ответ.Обнаружив, что в нашей базе знаний Pесть сведение птица(пингвин) инет никаких сведений о том, что летает(пингвин),мы отвечаем:«Насколько позволяет судить наша база знаний, нелетающаяптица — это пингвин».В юрипруденции такой подход к решению вопроса о виновностичеловек называется презумпцией невиновности :в случае отсутствия свидетельств виновностичеловек считается невиновным.ОТРИЦАНИЕ В ЛОГИЧЕСКОМПРОГРАММИРОВАНИИМы можем распространить принцип презумпции невиновностии на логические программы.Допущение Замкнутости МираПусть имеется некоторое непротиворечивое множествозамкнутых формул Γ (например, хорновская логическаяпрограмма) и замкнутая формула ϕ (например, запрос илиотдельная подцель).Тогда формула ¬ϕ является логическим следствием множестваΓ в допущении замкнутости мираΓ |=CWA ¬ϕ,если неверно, что ϕ логически следует из Γ, т.

е. Γ 6|= ϕ.Здесь CWA — аббревиатура C losed W orld A ssumption.ОТРИЦАНИЕ В ЛОГИЧЕСКОМПРОГРАММИРОВАНИИСуть Допущения Замкнутости Мира (CWA) состоит в том, чтопри извлечении CWA-логических следствий из базы знаний Γ(|=CWA ) нужно рассматривать не все модели для Γ, а толькотакую минимальную модель, в которой истинными являютсяодни лишь классические следствия (|=) из Γ.Такая минимальная модель существует, вообще говоря, невсегда (например, если Γ = {A ∨ B}).Но в случае хорновских логических программ, минимальноймоделью для программы P является наименьшая эрбрановскаямодель MP .ОТРИЦАНИЕ В ЛОГИЧЕСКОМПРОГРАММИРОВАНИИОбратимся к орнитологическому примеру.ПримерP = {птица(орел), птица(воробей), птица(пингвин),летает(орел), летает(воробей), летает(самолет)}ϕ= птица(пингвин) & ¬летает(пингвин)ТогдаP |=CWA птица(пингвин), поскольку MP |= птица(пингвин),P |=CWA ¬летает(пингвин), поскольку MP 6|= летает(пингвин).Значит, P |=CWA птица(пингвин) & ¬летает(пингвин).ОПЕРАТОР notИтак, теперь к логическим программам можно обращаться сзапросами, содержащими отрицания подцелей, идекларативная семантика умеет разумно обращаться с такимотрицательными подцелями.Нам остается научить этому обращению компьютер, т.

е.ввести в операционную семантику правила для обработкиотрицательных подцелей.Однако здесь нас ожидает неприятный сюрприз.ОПЕРАТОР notПредположим, что имеется запрос G : ?¬C0 к программе P.Чтобы получить утвердительный ответ на запрос G (т. е.доказать, что P |=CWA ¬C0 ), интерпретатор должен проверить,что MP 6|= C0 .Для этого интерпретатор должен убедиться, что запросG 0 : ?C0 к программе P не имеет ни одного успешноговычисления.Но эта задача является алгоритмически неразрешимой(почему? ).Да потому, что к ней сводится проблема останова машинТьюринга.Следовательно, никакой интерпретатор логических программне может гарантировать получение утвердительного ответа назапрос G : ?¬C0 даже в том случае, если этот ответ существует.ОПЕРАТОР notАлгоритмическая неразрешимость проблемы существования(отсутствия) успешного вычисления логических программ —это непреодолимое препятствие на пути создания такойоперационной семантики, которая была бы адекватнадекларативной семантике в рамках Допущения ЗамкнутостиМира.Можно лишь построить такой интерпретатор (операционнойсемантики), который как можно лучше соответствует CWA приобращении с отрицательными подцелями ¬C0 .Для этого в язык логического программирования был введенспециальный (встроенный) оператор not.ОПЕРАТОР notАргументами оператора not являются атомы.Для вычисления ответов на запрос ? not(C0 ) вводится правилоSLDNF-резолюции (N ot as F ailure), которое определяетсяследующим образом.Правило SLDNF-резолюцииПусть имеется запрос G0 : ? not(C0 ), C1 , .

. . , Cn к программе P.Для вычисления SLDNF-резольвенты G11. формируется запрос G 0 : ? C0 к программе P;2. проводится построение (обход) дерева вычислений Tзапроса G 0 : ? C0 ;3. в зависимости от устройства дерева T возможен один изтрех исходов.ОПЕРАТОР notПравило SLDNF-резолюцииВариант 1: Успех.Дерево T конечно, и все его ветви (SLD-резолютивныевычисления) являются тупиковыми.Тогда запрос G0 : ? not(C0 ), C1 , .

. . , Cn имеетSLDNF-резольвенту G1 = ? C1 , . . . , Cn , которая получается сиспользованием пустой подстановки ε.G 0 : ? C0t@T @t⇒@failureG0 : ? not(C0 ), C1 , . . . , Cn@ε?tG1 : ? C1 , . . . , CnОПЕРАТОР notОперационная семантика оператор notВариант 2: Неудача.При построении (обходе) дерева T было обнаруженоуспешное вычисление.Тогда запрос G0 : ? not(C0 ), C1 , . . . , Cn не имеетSLDNF-резольвент, и вычисление этого запроса являетсятупиковым .G 0 : ? C0G0 : ? not(C0 ), C1 , . . . , Cnt@T @t⇒@@failureR@failureОПЕРАТОР notОперационная семантика оператор notВариант 3: Бесконечное вычисление.Дерево T бесконечно и при его построении (обходе) небыло обнаружено успешных вычислений.Тогда запрос G0 : ? not(C0 ), C1 , .

. . , Cn не имеетSLDNF-резольвент, и вычисление этого запроса являетсябесконечным («сингулярная бесконечность»).G 0 : ? C0t@T @t⇒@failureG0 : ? not(C0 ), C1 , . . . , Cn@R∞@∞ОПЕРАТОР notОперационная семантика оператор notВариант 3: Бесконечное вычисление.Дерево T бесконечно и при его построении (обходе) небыло обнаружено успешных вычислений.Тогда запрос G0 : ? not(C0 ), C1 , .

. . , Cn не имеетSLDNF-резольвент, и вычисление этого запроса являетсябесконечным («сингулярная бесконечность»).Условие существования бесконечного вычисления запросаnot(C0 ) описано не вполне строго, поскольку обнаружениеуспешного вычисления существенно зависит от стратегииобхода дерева SLD-резолютивных вычислений. Так, например,стандартная стратегия обхода в глубину может не обнаружитьсуществующего успешного вычисления (почему? ).ОПЕРАТОР notТеорема (корректности SLDNF-резолюции)Если запрос G : ? not(C0 ) к хорновской логической программеP имеет успешное SLDNF-резолютивное вычисление, тоP |=CWA ¬∃y C0 .ДоказательствоСамостоятельно .А вот обратное утверждение (теорема полноты) дляSLDNF-резолютивного вычисления будет уже неверно.ОПЕРАТОР notПример.Рассмотрим программу поиска всех тех букв X слова L0 ,которые не содержатся в слове L00 .P : S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ← ;E (X , Y L) ← E (X , L);..и обратимся к ней с запросом..

..G0 : ? S(X , a b nil, b c nil)...S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ←;E (X , Y L) ← E (X , L);.. ..?S(X , a b t nil, b c nil)(1)(2)(3)..S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ←;E (X , Y L) ← E (X , L);(1)(2)(3).. ..?S(X , a b t nil, b c nil)(1).. ..?t?E (X , a.b .nil),not(E (X , b .c .nil))θ1 = {X1 /X , L0 /aL00 /bbcnil,nil}..S(X , L0 , L00 ) ← E (X , L0 ), not(E (X , L00 ));E (X , X L) ←;E (X , Y L) ← E (X , L);(1)(2)(3).. ..?S(X , a b t nil, b c nil)..

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5034
Авторов
на СтудИзбе
461
Средний доход
с одного платного файла
Обучение Подробнее