Сборник задач для самостоятельных занятий, страница 6

subset(X, Y ) : Список X состоит только из элементов, содержащихся в списке Y ;26Глава 1. УПРАЖНЕНИЯ11. concat(X, Y, Z) : Список X является конкатенацией (последовательным соединением)списков Y и Z;12. reverse(X, Y ) : Список X является обращением списка Y , т. е. X состоит из тех жеэлементов, что и список Y , но в списке X эти элементы следуют друг за другом вобратном порядке;13.

palindrome(X, Y ) : Список X является палиндромом Y , т. е. X одинаково прочитываетсяслева направо и справо налево;14. delete(X, Y ) : Список X образован из списка Y удалением одного или нескольких подрядидущих элементов;15. subsequence(X, Y ) : Последовательность X является подпоследовательностью последовательности Y ;16. summ(X, Y, Z) : Длина списка X равна сумме длин списков Y и Z;17. product(X, Y, Z) : Длина списка X равна произведению длин списков Y и Z;18. dif f er(X, Y, Z) : Длина списка X равна абсолютной разности длин списков Y и Z;19. multiple(X, Y ) : Длина списка X кратна длине списка Y ;20. nonmultiple(X, Y ) : Длина списка X не кратна длине списка Y ;21. period(X, Y ) : Список X является периодической последовательностью, полученной врезультате многократного повторения списка Y ;22.

stuttering(X) : Список X образован в результате неоднократного повторения некоторогодругого списка;23. power2(X) : Длина списка X является степенью числа 2;24. prime(X) : Длина списка X является простым числом;25. progression(X) : Все элементы списка X — это списки, длины которых (в порядке следования элементов в списке X) образуют арифметическую прогрессию;Пусть σ = hConst, F unc, P redi условимся обозначать Hσ эрбрановский универсум (множество основных термов) сигнатуры σ, а Bσ — эрбрановский базис сигнатуры (множествоосновных атомов) σ. Тогда каждая эрбрановская интерпретация 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.