упражнения 2 (1162151), страница 6
Текст из файла (страница 6)
Тогда каждая эрбрановская интерпретация I сигнатуры полностью определяется множеством всех тех основных атомов сигнатуры σ, которые выполняются в интерпретации I. В последующих упражнениях будет использоваться теоретико-множественныйспособ представления эрбрановских интерпретаций, при котором эрбрановская интерпретация I отождествляется с тем множеством основных атомов, которые в ней выполняются,т. е.I = {A : A ∈ Bσ , I |= A}.Тогда I называется эрбрановской моделью для хорновской логической программы P, если длялюбого программного утверждения D, D ∈ P, представленного в виде логической формулы,верноI |= D1.10.
Хорновские логические программы. Декларативная и операционная семантики.27Для обозначения того факта, что эрбрановская интерпретация I является моделью для программы P будет использоваться сокращенная запись I |= P.Упражнение 1.98. Докажите, что H-интерпретация I является моделью для хорновскойлогической программы P тогда и только тогда, когда для любого основного примера программного утверждения D0 = A00 ← A01 , . . .
, A0n , D0 ∈ [P] верно{A01 , . . . , A0n } ⊆ I ⇒ A00 ∈ I.Упражнение 1.99. Докажите, что каждая хорновская логическая программа P имеет хотябы одну эрбрановскую модель.Упражнение 1.100. Докажите, что H-интерпретация BH является моделью для любойхорновской логической программы P. Приведите пример программы, моделью которой является интерпретация I = ∅. Как должна быть устроена программа P для того, чтобы интерпретация I = ∅ была ее моделью?Упражнение 1.101. Докажите, что если H-интерпретации I1 и I2 являются моделямидля хорновской логической программы P, то H-интерпретация I0 = I1 ∩ I2 также являетсямоделью для P.Упражнение 1.102.
Рассмотрим множество IP всех эрбрановскихмоделей для логичеTской программы P. Докажите, что H-интерпретация MP =I является наименьшей (поI∈IPотношению теоретико-множественного включения) моделью для программы P.Упражнение 1.103. Рассмотрим множество IP всех эрбрановскихмоделей для огическойTпрограммы P. Докажите, что H-интерпретация MP =I является наименьшей (по отноI∈IPшению теоретико-множественного включения) моделью для программы P.Упражнение 1.104. Докажите, что MP = ∅ тогда и только тогда, когда хорновская логическая программа P не содержит ни одного факта.Упражнение 1.105.
Докажите, что для любого основного атома A0 и для любой хорновской логической программы P справедливо следующее соотношение:P |= A0 ⇐⇒ A0 ∈ MP .Упражнение 1.106. Пусть t1 , t2 , . . . , tk — это некоторый набор основных термов.Докажите, что подстановка θ = {Y1 /t1 , . . . , Yk /tk } является правильным ответом на запросG =?C1 , C2 , . . . , Cm к хорновской логической программе P тогда и только тогда, когда {C1 θ, .
. . , Cm θ} ⊆MP .Упражнение 1.107. Докажите, что для любых хорновских логических программ P1 и P2справедливо включениеMP1 ∪ MP2 ⊆ MP1 ∪P2 .28Глава 1. УПРАЖНЕНИЯПриведите пример программ P1 и P2 , для которых указанное включение является строгим.Каким из трех теоретико-множественных отношений ⊆, =, ⊇ связаны эрбрановские интерпретации MP1 ∩ MP2 и MP1 ∩P2 ?1.11Теоремы корректности и полноты для хорновских логических программ.Упражнение 1.108. Сохранят ли справедливость теоремы корректности и полноты дляхорновских логических программ, если в определении правила SLD-резолюции вместо наиболее общего унификатора разрешить использовать произвольный унификатор выделеннойподцели запроса и заголовка активизированного программного утверждения?Упражнение 1.109. Оператором непосредственного следования TP для хорновской логической программы P называется отображениеTP : 2BP → 2BP ,сопоставляющее каждой эрбрановской интерпретации I, I ⊆ BP , эрбрановскую интерпретацию I 0 = TP (I), I 0 ⊆ BP , удовлетворяющую следующему соотношению:I 0 = {A0 : D = A0 ← A1 , .
. . , Ak ∈ [P], {A1 , . . . , Ak } ⊆ I}.Докажите, что для любой эрбрановской модели I для хорновской логической программы Pинтерпретация TP (I) также является моделью для программы P.Упражнение 1.110. Пусть задана хорновская логическая программаP: P(f(X)) ← P(X);сигнатуры Σ = hConst = {c}, F unc = {f }, P red = {P }i, состоящая из одного-единственногопрограммного утверждения.Какие эрбрановские интерпретации являются значениями оператора непосредственного следования TP (∅) и TP (BP ?Упражнение 1.111. Пусть задана хорновская логическая программаP: P(X) ← R(X), P(c);R(b) ← P(a);R(a);P(c);Вычислите значения оператора непосредственного следования TP (∅), TP (TP (∅)), TP (TP (TP (∅)))?Упражнение 1.112. Докажите, что для любой хорновской логической программы P оператор непосредственного следования TP обладает свойством монотонности, т.
е. для любыхэрбрановских интерпретаций I, J справедливо соотношение1.12. Стратегии вычисления логических программ.29I ⊆ J =⇒ TP (I) ⊆ TP (J) .Упражнение 1.113. Докажите, что эрбрановская интерпретация I является моделью дляхорновской логической программы P в том и только том случае, когда TP (I) ⊆ I.Упражнение 1.114. Условимся n-кратную композицию оператора непосредственного следования обозначать TPn , т.
е. TPn (I) = TP (TP (. . . TP (I) . . . )).|{z}n разДокажите, что для любой хорновской логической программы P имеет место следующая цепочка включенийTP0 (∅) ⊆ TP1 (∅) ⊆ TP2 (∅) ⊆ · · · ⊆ TPi (∅) ⊆ TPi+1 (∅) ⊆ . . . ⊆ MP .Упражнение 1.115. Докажите, что эрбрановская интерпретациялью для хорновской логической программы P.∞Si=0TPi (∅) является моде-Упражнение 1.116.
Докажите, что для любой хорновской логической программы P имеет∞Sместо равенство MP =TPi (∅).i=0Упражнение 1.117. Докажите, что для любой хорновской логической программы P илюбого основного атома A запрос ?A к программе P имеет успешное SLD-резолютивное вычисление тогда и только тогда, когда A ∈ MP .Упражнение 1.118. Докажите, что для любой хорновской логической программы P запросG =?C1 , C2 , . .
. , Cn с множеством целевых переменных Y1 , Y2 , . . . , Ym , обращенный к программе P имеет хотя бы одно успешное SLD-резолютивное вычисление в том и только том случае,когда имеет место логическое следствие P |= ∃Y1 ∃Y2 . . . ∃Ym (C1 &C2 & . . . &Cn ).Упражнение 1.119. Верно ли, что для любой хорновской логической программы P иатома A логическое следствие P |= ∀Y1 ∀Y2 . . . ∀Ym A имеет место тогда и только тогда, когдавыполняется включение [A] ⊆ MP ?1.12Стратегии вычисления логических программ.Упражнение 1.120. Постройте дерево SLD-резолютивных вычислений для запроса G= ?P(X,b), обращенного к программе P, используя стандартное правило выбора подцелей.P: P(X,Z) ← Q(X,Y),P(Y,Z);P(X,X) ← ;Q(a,b) ← ;30Глава 1.
УПРАЖНЕНИЯПредположим, что в теле первого программного утверждения P(X,Z) ← Q(X,Y),P(Y,Z);программист поменял местами атомы Q(X,Y) и P(Y,Z). Как изменится в этом случае деревоSLD-резолютивных вычислений запроса G?Упражнение 1.121. Постройте дерево SLD-резолютивных вычислений для запроса G= ?R(Y),P(Z), обращенного к программе P, используя стандартное правило выбора подцелей.P: R(Y) ← P(Y),Q(Y);P(a) ← ;P(b) ← ;Q(a) ← ;Q(f(X)) ← Q(X);Предположим, что в теле первого программного утверждения R(Y) ← P(Y),Q(Y); программист поменял местами атомы P(Y) и Q(Y).
Как изменится в этом случае дерево SLD-резолютивныхвычислений запроса G?Упражнение 1.122. Имеет ли запрос G= ? P(a,c), обращенный к программе P, хотя быодно успешное SLD-резолютивное вычисление?P: P(a,b) ← ;P(c,b) ← ;P(X,Z) ← P(X,Y),P(Y,Z);P(X,Y) ← P(Y,X);Покажите, что в том случае, если из указанной программы удалить хотя бы одно программноеутверждение, то запрос G не будет иметь ни одного правильного ответа.
Покажите, что руководствуясь стандартной стратегией вычислений нельзя вычислить ни один ответ на запросG, обращенный к программе P. Какой должна быть стратегия вычислений, позволяющаявычислить хотя бы один ответ на запрос G к программе P.Упражнение 1.123. Приведите пример такой хорновской логической программы P и такого запроса G, для которых существуют два успешных вычисления, но при этом никакоеправило выбора подцелей не позволяет построить, руководствуясь процедурой поиска в глубину с возвратом, оба успешных вычисления.Упражнение 1.124.
Cоздайте хорновские логические программы, которые решают следующие задачи.1. Программа порождает всевозможные перестановки элементов заданного списка L. Обращение к программе должно имет вид ? permut(L,X).2. Программа порождает всевозможные префиксы заданного слова L, представленногосписком букв. Обращение к программе должно имет вид ? all_prefixes(L,X).1.13. Алгоритмическая полнота и алгоритмическая неразрешимость.313. Программа порождает всевозможные суффиксы заданного слова L, представленногосписком букв.
Обращение к программе должно имет вид ? all_suffixes(L,X).4. Программа порождает список всех букв заданного конечного алфавита A = {a1 , a2 , . . . , an },содержащихся в списке L однократно. Обращение к программе должно имет вид ?single(L,X).5. Программа порождает список всех букв заданного конечного алфавита A = {a1 , a2 , . . . , an },содержащихся в списке L многократно. Обращение к программе должно имет вид ?multiple(L,X).6. Программа порождает список всех букв заданного конечного алфавита A = {a1 , a2 , . .
. , an },содержащихся в списке L1 и не содержащихся в списке L2 . Обращение к программедолжно имет вид ? filter(L1,L2,X).7. Программа порождает всевозможные сочетания элементов заданного бесповторного списка L1 . Обращение к программе должно имет вид ? combination(L1,X).8. Программа порождает всевозможные сочетания элементов заданного бесповторного списка L1 , длина которых равна длине заданного списка L2 .
Обращение к программе должноимет вид ? combination2(L1,L2,X).9. Программа порождает всевозможные сочетания c повторением элементов заданного бесповторного списка L1 , длина которых равна длине заданного списка L2 . Обращение кпрограмме должно имет вид ? combination_repit(L1,L2,X).1.13Алгоритмическая полнота и алгоритмическая неразрешимость.Упражнение 1.125. Возьмите ленточную конфигурацию α0 , представленную на рис. ??, ипостройте дерево SLD-резолютивных вычислений для запроса ? P (lef t(α0 ), right(α0 ), X, Y ),обращенного к логической программе Pπ , представленной на рис. ??.Упражнение 1.126. Какое устройство имеют деревья SLD-резолютивных вычислений запросов ? P (lef t(α), right(α), X, Y ), обращенных к логическим программам Pπ , соответствующим детерминированным программам машин Тьюринга.Упражнение 1.127.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
