LectLog12 (Модели для логических программ) - Прошлогодняя лекция (1158004)
Текст из файла
Основыматематическойлогики и логическогопрограммированияЛЕКТОР: В.А. ЗахаровЛекция 12.Хорновские логическиепрограммы: синтаксис.Декларативная семантикалогических программ.ХОРНОВСКИЕ ЛОГИЧЕСКИЕ ПРОГРАММЫПАРАДИГМЫ ПРОГРАММИРОВАНИЯИмперативное программирование : программа — это описаниепоследовательности операторов (команд).Языки: Assembler, Pascal, C, Java.Функциональное программирование : программа — это системауравнений, описывающая вычисляемую функцию.Языки: Lisp, ML, Haskel, Hope.Логическое программирование : программа — это множествоформул, описывающих условия решаемой задачи.Языки: Prolog, Datalog, Godel.ХОРНОВСКИЕ ЛОГИЧЕСКИЕ ПРОГРАММЫСинтаксис логических программПусть σ = hConst, Func, Predi — некоторая сигнатура, вкоторой определяются термы и атомы.«заголовок» ::= «атом»«тело» ::= «атом» | «тело», «атом»«правило» ::= «заголовок» ← «тело»;«факт» ::= «заголовок»;«утверждение» ::= «правило» | «факт»«программа» ::= «пусто» | «утверждение» «программа»«запрос» ::= | ? «тело»ХОРНОВСКИЕ ЛОГИЧЕСКИЕ ПРОГРАММЫПримерыПравило: L(паша, Y ) ← L(Y , X ), L(паша, X );|{z}|{z}заголовоктелоФакт: L(даша, саша);Запрос (целевое утверждение ):? Умный(X ), Добрый(X ), Красивый(X ), Любит(X , меня)|{z} |{z} |{z} |{z}подцельподцельЗдесь X — целевая переменная .подцельподцельХОРНОВСКИЕ ЛОГИЧЕСКИЕ ПРОГРАММЫТерминологияПусть P — логическая программа, D — программноеутверждение, а θ — подстановка.
ТогдаIDθ — пример программного утверждения D,Iесли θ — переименование, то Dθ — вариант программногоутверждения D,Iесли VarDθ = ∅, то Dθ — основной пример программногоутверждения D,I[D] — множество всех основных примеров программногоутверждения D,I[P] — множество всех основных примеров всехутверждений программы P.ХОРНОВСКИЕ ЛОГИЧЕСКИЕ ПРОГРАММЫТерминологияПусть G =?C1 , C2 , . . . , Cm — запрос. ТогдаIIатомы C1 , C2 , .
. . , Cm называются подцелями запроса G ,mSVarCi называются целевымипеременные множествапеременными ,i=1Iзапрос называется пустым запросом ,Iзапросы будем также называть целевыми утверждениями .Для удобства обозначения условимся в дальнейшем факты A;рассматривать как правила A ←; с заголовком A и пустымтелом.ХОРНОВСКИЕ ЛОГИЧЕСКИЕ ПРОГРАММЫПримеры.Пусть D = elem(X , Y Z ) ← elem(X , Z ); — программноеутверждение. Тогда.D 0 = D{X /Y , Z /nil} = elem(Y , Y nil) ← elem(Y , nil);пример программного утверждения D,.D 00 = elem(X 0 , Y 0 Z 0 ) ← elem(X 0 , Z 0 );вариант программного утверждения D,.D 000 = D{X /1, Y /2, Z /nil} = elem(1, 2 nil) ← elem(1, nil);основной пример программного утверждения D,ХОРНОВСКИЕ ЛОГИЧЕСКИЕ ПРОГРАММЫПример логической программыsi_ro(Xs , Xs , V , A, nil) ← in(Xs , V , V1 );si_ro(Xs , Xd , V , A, Z ) ← in(Xs , V , V1 ), in(Xd , V1 , V2 ),R(Xs , Xd , V2 , A, Z );. .
... .. ...R(Xs , Xd , V , A, (Xs Xd nil) nil) ← in(Xs Xd nil, A, A1 );R(Xs , Xd , V , A, (Xs Y nil) Z )← in(Y , V , V1 ),in(Xs Y nil, A, A1 ),R(Y , Xd , V1 , A1 , Z );.. .in(X , X Y , Y );in(X , Z Y , Z V ) ← in(X , Y , V );и запроса к ней.... .. . .. . .. . .. .? si_ro(4, 2, 1 2 3 4 nil, (1 2 nil) (2 3 nil) (2 4 nil) (3 1 nil) nil, Z )Что же вычислит программа в ответ на этот запрос?ХОРНОВСКИЕ ЛОГИЧЕСКИЕ ПРОГРАММЫКак нужно понимать логические программы?Главная особенность логического программирования —полисемантичность : одна и та же логическая программа имеетдве равноправные семантики, и поэтому человек–программисти компьютер–вычислитель имеют две разные точки зрения напрограмму.Программисту важно понимать, ЧТО вычисляет программа.Такое понимание программы называется декларативнойсемантикой программы.Компьютеру важно «знать», КАК проводить вычислениепрограммы.
Такое понимание программы называетсяоперационной семантикой программы.ХОРНОВСКИЕ ЛОГИЧЕСКИЕ ПРОГРАММЫКак нужно понимать логические программы?Декларативная семантикаОперационная семантикаПравило A0 ← A1 , A2 , . . . , An ;Если выполнены условия Чтобы решить задачу A0 ,A1 , A2 , . . . , An , то справедли- достаточно решить задачиво и утверждение A0 .A1 , A2 , . . . , An .Факт A0 ;Утверждение A0 считается Задача A0 объявляется реверным.шенной.Запрос ?C1 , C2 , . .
. , CmПри каких значениях целевых Решитьсписокзадачпеременных будут верны все C1 , C2 , . . . , Cm .отношения C1 , C2 , . . . , Cm ?ХОРНОВСКИЕ ЛОГИЧЕСКИЕ ПРОГРАММЫПример истолкования логической программы..P : elem(X , X L);elem(X , Y L) ← elem(X , L);Декларативная семантика1. Всякий предмет X входитв состав того списка, заголовком которого он является2. Если предмет X содержится в хвосте списка, то X содержится и в самом списке.Операционная семантика1. Считается решенной задача поиска предмета X в любом списке, содержащем X вкачестве заголовка.2. Чтобы обнаружить предметX в списке, достаточно найтиего в хвосте этого списка.ДЕКЛАРАТИВНАЯ СЕМАНТИКАБолее строгое описание семантик требует привлеченияаппарата математической логики.Логические программы и логические формулыКаждому утверждению логической программы сопоставимлогическую формулу:Правило: D 0 = A0 ← A1 , A2 , .
. . , An ;0D = ∀x1 . . . ∀xk (A1 &A2 & . . . &An → A0 ), где {x1 , . . . , xk } =n[i=0Факт: D 00 = A;D 00 = ∀x1 . . . ∀xk A, где {x1 , . . . , xk } = VarAЗапрос: G = ? C1 , C2 , . . . , CmVarAiДЕКЛАРАТИВНАЯ СЕМАНТИКАС точки зрения декларативной семантики, программныеутверждения D и запросы G — это логические формулы,программа P — это множество формул (база знаний),а правильный ответ на запрос — это такие значенияпеременных (подстановка), при которой запрос оказываетсялогическим следствием базы знаний.Определение (правильного ответа)Пусть P — логическая программа, G — запрос к P смножеством целевых переменных Y1 , .
. . , Yk .Тогда всякая подстановка θ = {Y1 /t1 , . . . , Yk /tk } называетсяответом на запрос G к программе P.Ответ θ = {Y1 /t1 , . . . , Yk /tk } называется правильным ответомна запрос G к программе P, еслиkSP |= ∀Z1 . . . ∀ZN G θ,где {Z1 , . . . , ZN } =Varti .i=1Теперь вопрос: как искать правильные ответы?ДЕКЛАРАТИВНАЯ СЕМАНТИКАПусть σ = hConst, Func, Predi — некоторая сигнатура.РассмотримIIIHσ — эрбрановский универсум сигнатуры σ (множествоосновных термов);Bσ — эрбрановский базис сигнатуры σ (множествоосновных атомов);эрбрановские интерпретации сигнатуры σ:I ⊆ Bσ ,I = {A : A ∈ Bσ , I |= A}Определение (модели для логической программы)Пусть P — логическая программа, I — H-интерпретация.Тогда I называется эрбрановской моделью для программы P,если для любого программного утверждения D, D ∈ P, верноI |= D(сокращенная запись I |= P).ДЕКЛАРАТИВНАЯ СЕМАНТИКАЛемма (о модели для логической программы)Эрбрановская интерпретация I является моделью длялогической программы P тогда и только тогда, когда длялюбого основного примера программного утвержденияD 0 = A00 ← A01 , .
. . , A0n , D 0 ∈ [P] верно{A01 , . . . , A0n } ⊆ I ⇒ A00 ∈ IДоказательство.(Необходимость) Пусть D ∈ P и D 0 = Dθ — основнойпример. Тогда I — модель для P ⇒ I |= D ⇒ I |= D 0 ⇒I |= A01 & . . . &A0n → A00 ⇒ если I |= A01 & . . . &A0n , то I |= A00 ⇒если I |= A01 , . . . I |= A0n , то I |= A00 ⇒если {A01 , . . .
, A0n } ⊆ I , то A00 ∈ I .(Достаточность) Сами.ДЕКЛАРАТИВНАЯ СЕМАНТИКАСледствиеКаждая хорновская логическая программа P имеет хотя быодну эрбрановскую модель.Доказательство.Самостоятельно. (Покажите, что в качестве одной из моделейвсегда можно взять максимальную интерпретацию I = BP ).Пример.ПрограммаP(X , f (X )) ← R(X );R(f (Y )) ← P(Y );имеет H-модель I = ∅.ДЕКЛАРАТИВНАЯ СЕМАНТИКАЛемма (о пересечении моделей)Если H-интерпретации I1 и I2 являются моделями длялогической программы P, то H-интерпретация I0 = I1 ∩ I2также является моделью для P.Доказательство.Воспользуемся леммой о модели для логической программы.Пусть D 0 = A00 ← A01 , . .
. , A0n , D 0 ∈ [P]. Тогда{A01 , . . . , A0n } ⊆ I0⇒{A01 , . . . , A0n } ⊆ I1⇒{A01 , . . . , A0n } ⊆ I2A00 ∈ I1⇒ A00 ∈ I0A00 ∈ I2ДЕКЛАРАТИВНАЯ СЕМАНТИКАТеорема (о наименьшей модели)Всякая хорновская логическая программа P имеетнаименьшую эрбрановскую модель.Доказательство.1. Каждая хорновская логическая программа P имеет хотябы одну эрбрановскую модель.2. Рассмотрим множество IP всех H-моделей логическойпрограммы P. Как было показано, I 6= ∅. Поэтому,согласноTлемме о пересечении H-моделей, интерпретацияMP =I также является H-моделью программы P.I ∈IPПри этом для любой H-модели I верно MP ⊆ I . Такимобразом, MP — это наименьшая эрбрановская модель дляпрограммы P.ДЕКЛАРАТИВНАЯ СЕМАНТИКАТеорема (характеристическое свойствонаименьшей модели)Пусть G =?A — запрос к хорновской логической программе P.Пусть A0 = Aθ — основной пример атома A. ТогдаP |= A0 ⇐⇒ A0 ∈ MP .Доказательство.Допустим P = {D1 , .
. . , DN }. ТогдаP |= A0 ⇐⇒ |= (D1 & . . . &DN ) → A0 ⇐⇒S = {D1 , . . . , DN , ¬A0 } — противоречивая система ⇐⇒S не имеет H-моделей (теорема о H-интерпретациях ) ⇐⇒для любой H-интерпретации I : I |= P влечет A0 ∈ I ⇐⇒TA0 ∈I = MP (теорема о наименьшей модели )I ∈IPДЕКЛАРАТИВНАЯ СЕМАНТИКАТеорема (об основном правильном ответе)Пусть G =?C1 , C2 , . . . , Cm — запрос к хорновской логическойпрограмме P. Пусть Y1 , . . . , Yk — целевые переменные,t1 , .
. . , tk — основные термы.Тогда подстановка θ = {Y1 /t1 , . . . , Yk /tk } являетсяправильным ответом на запрос G к программе P тогда итолько тогда, когда {C1 θ, . . . , Cm θ} ⊆ MP .Доказательство.Самостоятельно. (На основании характеристического свойстванаименьшей модели).ДЕКЛАРАТИВНАЯ СЕМАНТИКАИТОГИIЛогическая программа P — это база знаний, состоящая иззаконов (фактов и правил), описывающих устройствонекоторого математического мира (задачи).IВ этом математическом мире истинным считается то итолько то, что удовлетворяет законам базы знаний —ничего лишнего.IЭтот математический мир — наименьшая эрбрановскаямодель MP .IПравильным ответом на запрос к базе знаний считаетсятакой ответ, который логически следует из базы знаний(программы).IВсе правильные ответы на любые запросы к логическойпрограмме P нужно искать в наименьшей модели MP .ДЕКЛАРАТИВНАЯ СЕМАНТИКАТеперь ясно, каков смысл логических программ, какие ответына запросы к программ считаются правильными, и гденаходятся правильный ответы.
Математику этого достаточно,для того чтобы создавать программы.Но этого совершенно недостаточно вычислительномуустройству, для того чтобы вычислять ответы на запросы кпрограммам.Теперь нам нужно выяснить,КАК ВЫЧИСЛЯТЬ ОТВЕТЫ НА ЗАПРОСЫ?КОНЕЦ ЛЕКЦИИ 12..
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
