variant-sev2 (Варианты контрольных работ и экзамена)

ВариантЗадача 1. Слово — это конечный непустой список букв фиксированного конечного алфавита. Текст— это конечный непустой список слов. Построить логическую программу, которая для заданного текстаL вычисляет два бесповторных списка X и Y . Список X состоит из всех тех слов текста L, которыевстречаются в нем ровно один раз, а список Y — из всех остальных слов текста L. Запрос к программедолжен иметь вид ? G(L, X, Y ). При составлении программы разрешается использовать встроенныефункции и отношения, а также предикаты elem и concat.Задача 4.

Для заданного запроса G =? A(Y, X), not(A(X, Y )) к заданной логической программеP построить на основе стандартной стратегии вычислений (с использованием операторов отсеченияи отрицания) дерево SLD-резолютивных вычислений и определить множество вычисленных ответов.Примечание: заглавными буквами начинаются имена переменных и предикатов, а строчными буквами— имена констант и функций.P : A(X, c)A(X, Y )B(g(X))B(X)E(b)←←←←←E(X), !, not(B(X));B(g(X)), E(Y );!;B(g(X));;Задача 3. Опишите известный Вам алгоритм вычисления наиболее общего унификатора двух атомарных формул.Задача 4.

Что называется SLD-резольвентой G0 запроса G и программного утверждения D? Верноли, что запрос G является логическим следствием программного утверждения D и SLD-резольвентыG0 ?Задача 5. Какой ответ на запрос G к хорновской логической программе P называется правильным?Каковы известные Вам необходимые и достаточные условия того, что ни один запрос к хорновскойлогической программе P не имеет ни одного правильного ответа?Задача 8. Что называется стратегией вычисления логических программ? Зависит ли ответ на запросG =? not(P (x)) от того, какая именно стратегия вычисления применяется?Задача 6.

Как определяется частичная корректность программы π относительно предусловия ϕ ипостусловия ψ в интерпретации I?Является ли программа while X > 0 do X + + od частично корректной относительно предусловияϕ = (X > 0) и постусловия ψ = (X < 0) в стандартной интерпретации арифметики целых чисел?Задача 7. Пусть P — это хорновская логическая программа, а S — множество всех дизъюнктов,соответствующих программным утверждениям программы P. Известно, что для наименьшей эрбрановской модели MP программы P выполняется соотношение MP = ∅. Какие из приведенных нижеутверждений будут при этом всегда верны и почему?1. Система дизъюнктов S выполняется в каждой эрбрановской интерпретации, потому что...2.

Из системы дизъюнктов S нельзя вывести ни одной резольвенты, потому что...3. Система дизъюнктов S является противоречивой, потому что...4. В каждом дизъюнкте из системе S есть хотя бы один атом со связкой отрицания ¬, потому что...5. Все приведенные выше утверждения всегда неверны, потому что...Задача 8. Какие из приведенных ниже утверждений справедливы и почему?1. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей хорновской логической программы с использованием стандартной стратегии вычисления, потому что...2.

Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей логической программой, но лишь с использованием нестандартной стратегии вычисления, потому что...3. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей логической программы с использованием стандартной стратегии вычисления, но лишьпри добавлении операторов is и not, потому что...4. Существуют арифметическая функция, вычислимая на машине Тьюринга, для вычисления которой нет логической программы даже в случае использования операторов is и not, потому что....