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

Вариант 1Задача 0. Слово — это конечный непустой список букв фиксированного конечного алфавита. Текст— это конечный непустой список слов. Построить логическую программу, которая для заданного текстаL вычисляет два бесповторных списка X и Y . Список 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.

Сформулируйте теорему Левенгейма–Сколема. Верно ли, что из этой теоремы следует,что каждая выполнимая формула логики предикатов имеет модель, предметной областью которойявляется то или иное множество натуральных чисел? Ответ обосновать.Задача 6. Сколько существует различных эрбрановских интерпретаций в сигнатуре σ, состоящейтолько из одного одноместного предикатного символа P и из одной предметной константы c ? Ответобосновать.Задача 7. Верно ли, что если запрос G(x) к хорновской логической программе имеет хотя бы одноуспешное вычисление, то этот запрос имеет хотя бы один основной правильный ответ? Ответ обосновать.Задача 8.

Что такое допущение замкнутости мира? Верно ли, что ϕ ∨ ψ |=CW A ¬(ϕ&ψ)?Задача 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, потому что...Вариант 2Задача 0. Слово — это конечный непустой список букв фиксированного конечного алфавита.

Текст —это конечный непустой список слов. Построить логическую программу, которая для заданных текстовL1 и L2 вычисляет бесповторный список X, состоящий из всех тех слов текста L1 , которые имеютдлину 4 и не встречаются в списке L2 . Запрос к программе должен иметь вид ? G(L1 , L2 , X).Задача 1. Используя константные, функциональные и предикатные символы алфавита (см. Приложение 1), построить замкнутую формулу логики предикатов, соответствующую следующему утверждению.«Всякая неограниченная сверху последовательность действительных чисел не имеет предела.»Задача 2.

Для заданной формулы ϕ выяснить, применяя метод семантических таблиц, является лиэта формула общезначимой.∃x(∀xP (x, x) ∨ ∃x¬R(x)) → ∃x(R(x) → ∃yP (f (x), y))Задача 3. Для заданной формулы ϕ выяснить, применяя метод резолюций, является ли эта формулаобщезначимой.∀x(P (x, x) → (R(x) → ∀x(∀xP (x, x)&R(x))))Задача 4.

Для заданного запроса G =? P (Y, X), not(P (X, Y )) к заданной логической программеP построить на основе стандартной стратегии вычислений (с использованием операторов отсеченияи отрицания) дерево SLD-резолютивных вычислений и определить множество вычисленных ответов.Примечание: заглавными буквами начинаются имена переменных и предикатов, а строчными буквами— имена констант и функций.P : R(g(b))R(X)P (X, b)P (X, Y )Q(a)←←←←←!;R(g(X));Q(X), !, not(R(X));R(g(X)), Q(Y );;Задача 5. Сформулируйте теорему компактности Мальцева. Следует ли из этой теоремы утверждение: «Если множество предложений не имеет модели, то хотя бы одно предложение является противоречивым»? Ответ обосновать.Задача 6. Вычислите композицию подстановок {x/y}{y/z}{z/x}{x/y}.Задача 7.

Сформулируйте определение эрбрановской интерпретации. Что общего у всех эрбрановских интерпретаций заданной сигнатуры?Задача 8. Сформулируйте теорему полноты для хорновских логических программ. Существуют литакие правильные ответы на запрос G к хорновской логической программе P, которые не могут бытьвычислены? Ответ обосновать.Задача 9. Известно, что для семантической таблицы T = h{ϕ}, {ψ}i нельзя построить ни одногоуспешного табличного вывода. Какие из приведенных ниже утверждений всегда верны для любыхзамкнутых формул ϕ и ψ ?1. Таблица T = h{ϕ}, {ψ}i не является выполнимой, потому что...2.

Для таблицы T 0 = h{ψ}, {ϕ}i также не существует ни одного успешного табличного вывода,потому что...3. Формула ϕ не является логическим следствием формулы ψ, потому что...4. Формула ψ не является логическим следствием формулы ϕ, потому что...5. Все приведенные выше утверждения в общем случае неверны, потому что...Задача 10. Предположим, что в правило резолюции было внесено следующее изменение: резольвентой дизъюнктов D1 = D10 ∨ L1 и D2 = D20 ∨ ¬L2 объявляется всякий дизъюнкт D0 = (D10 ∨ D20 )η, где η— некоторый унификатор (необязательно наиболее общий) литер L1 и L2 .

Какие из приведенных нижеутверждений будут справедливы и почему?1. После такого изменения и теорема корректности резолютивного вывода и теорема полноты резолютивного вывода уже будут неверны, потому что...2. После такого изменения теорема корректности резолютивного вывода остается верной, а теоремаполноты резолютивного вывода уже будет неверна, потому что...3. После такого изменения теорема полноты резолютивного вывода остается верной, а теорема корректности резолютивного вывода уже будет неверна, потому что...4. После такого изменения и теорема корректности резолютивного вывода и теорема полноты резолютивного вывода остаются верными, потому что...Задача 11.

Пусть ϕ — формула логики предикатов в сколемовской стандартной форме. Какие изприведенных ниже утверждений верны и почему?1. Если формула ϕ выполнима, то ϕ выполнима хотя бы в одной эрбрановской интерпретации дляформулы ϕ,2. Если формула ϕ выполнима хотя бы в одной эрбрановской интерпретации для формулы ϕ, тоформула ϕ выполнима.3. Если формула ϕ выполнима в каждой эрбрановской интерпретации для формулы ϕ, то формулаϕ общезначима.4. Если формула ϕ не имеет эрбрановских моделей, то формула ϕ не имеет никаких моделей.5. Все приведенные выше утверждения верны.Задача 12.

Какие из продолжений следующего утверждения будут справедливы и почему ? «Перваяподстановка, которая будет вычислена программой P в качестве ответа на запрос G»1. «зависит только от стратегии обхода дерева SLD-вычислений программы P для запроса G».2. «зависит только от порядка расположения программных утверждений в программе P».3. «зависит только от порядка расположения подцелей в запросе G».4. «зависит только от порядка расположения атомов в теле процедур программы P».5.

«зависит от всех перечисленных выше факторов».6. «не зависит ни от одного из перечисленных выше факторов».Вариант 1Задача 0. Слово — это конечный непустой список букв фиксированного конечного алфавита. Текст— это конечный непустой список слов. Построить логическую программу, которая для заданного текстаL вычисляет два бесповторных списка X и Y .