test_astana (1158060), страница 2
Текст из файла (страница 2)
Список X состоит из всех тех слов текста L, которыевстречаются в нем ровно один раз, а список Y — из всех остальных слов текста L. Запрос к программедолжен иметь вид ? G(L, X, Y ).Задача 1. Используя константные, функциональные и предикатные символы алфавита (см. Приложение 1), построить замкнутую формулу логики предикатов, соответствующую следующему утверждению.«Ни одна последовательность положительных действительных чисел не имеет ни одной отрицательной предельной точки»Задача 2. Для заданной формулы ϕ выяснить, применяя метод семантических таблиц, является лиэта формула общезначимой.∀y(∃y¬P (y) → ∃xR(x)) → ∀x∃y(P (f (x)) ∨ R(y))Задача 3.
Для заданной формулы ϕ выяснить, применяя метод резолюций, является ли эта формулаобщезначимой.∃x∃y(P (x, y) → R(x)) → ∀x(¬∃yP (x, y) ∨ R(x))Задача 4. Для заданного запроса G =? A(Y, X), not(A(X, Y )) к заданной логической программеP построить на основе стандартной стратегии вычислений (с использованием операторов отсеченияи отрицания) дерево SLD-резолютивных вычислений и определить множество вычисленных ответов.Примечание: заглавными буквами начинаются имена переменных и предикатов, а строчными буквами— имена констант и функций.P : A(X, c)A(X, Y )B(g(c))B(X)E(b)←←←←←E(X), !, not(B(X));B(g(X)), E(Y );!;B(g(X));;Задача 5.
Cформулируйте теорему о равносильной замене формул логики предикатов. Являются лиформулы логики предикатов P (x) и P (y) равносильными? Ответ обосновать.Задача 6. Какая формула логики предикатов называется выполнимой? Приведите пример выполнимой формулы логики предикатов, которая невыполнима ни в одной интерпретации, предметная областькоторой состоит только из одного элемента.Задача 7.
Верно ли, что если запрос G(x) к хорновской логической программе имеет хотя бы одноуспешное вычисление, то этот запрос имеет хотя бы один основной правильный ответ? Ответ обосновать.Задача 8. Что называется стратегией вычисления логических программ? Зависит ли ответ на запросG =? not(P (x)) от того, какая именно стратегия вычисления применяется?Задача 9. Известно, что некоторая модель для формулы ϕ не является моделью для формулы ψ.Какие из приведенных ниже утверждений всегда верны для любых замкнутых формул ϕ и ψ ?1.
Не существует успешного табличного вывода из таблицы T 0 = h{ψ}, {ϕ}i, потому что...2. Не существует успешного табличного вывода из таблицы T = h{ϕ}, {ψ}i, потому что...3. Формула ϕ является логическим следствием формулы ψ, потому что...4. Формула ψ является логическим следствием формулы ϕ, потому что...5. Все приведенные выше утверждения в общем случае неверны, потому что...Задача 10. Пусть задано некоторое непустое множество дизъюнктов S0 .
Пусть S1 — это множествовсех формул, резолютивно выводимых из множества дизъюнктов S0 . Какие из приведенных нижеутверждений всегда справедливы и почему?1. Если каждый дизъюнкт множества S0 выполним, то и каждый дизъюнкт множества S1 выполним, потому что....2. Если каждый дизъюнкт множества S1 выполним, то множество дизъюнктов S0 имеет модель,потому что....3. Если множество дизъюнктов S0 имеет модель, то множество дизъюнктов S1 имеет модель, потомучто....4. Все приведенные выше утверждения всегда верны, потому что...Задача 11. Пусть P — это хорновская логическая программа, а S — множество всех дизъюнктов,соответствующих программным утверждениям программы P. Известно, что для наименьшей эрбрановской модели MP программы P выполняется соотношение MP = ∅.
Какие из приведенных нижеутверждений будут при этом всегда верны и почему?1. Система дизъюнктов S выполняется в каждой эрбрановской интерпретации, потому что...2. Из системы дизъюнктов S нельзя вывести ни одной резольвенты, потому что...3. Система дизъюнктов S является противоречивой, потому что...4. В каждом дизъюнкте из системе S есть хотя бы один атом со связкой отрицания ¬, потому что...5. Все приведенные выше утверждения всегда неверны, потому что...Задача 12.
Какие из приведенных ниже утверждений справедливы и почему?1. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей хорновской логической программы с использованием стандартной стратегии вычисления, потому что...2. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей логической программой, но лишь с использованием нестандартной стратегии вычисления, потому что...3. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей логической программы с использованием стандартной стратегии вычисления, но лишьпри добавлении операторов is и not, потому что...4. Существуют арифметическая функция, вычислимая на машине Тьюринга, для вычисления которой нет логической программы даже в случае использования операторов is и not, потому что....
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
