2009 экзамен вариант 9 (другое) (Старые варианты экзамена)

ВариантЗадача 0 (6 баллов). Точка на плоскости задается списком из двух действительных чисел. Всякаятройка точек, не лежащих на одной прямой, образует треугольник. Построить логическую программу,которая для заданного бесповторного списка L точек на плоскости вычисляет список X всех троекточек из списка L, образующих треугольники.

Запрос к программе должен иметь вид ?G(L, X).Задача 1 (3 балла). Используя константные, функциональные и предикатные символы алфавита(см. Приложение 1), построить замкнутую формулу логики предикатов, соответствующую следующемуутверждению.«Ни одну сходящуюся последовательность действительных чисел нельзя представить в виде суммыдвух сходящихся последовательностей действительных чисел»Задача 2 (3 балла). Для заданной формулы ϕ выяснить, применяя метод семантических таблиц,является ли эта формула общезначимой.ϕ = ∃y(∀xP (y, f (x)) → ∀xR(x)) → ∀x(¬∃yP (y, f (x)) ∨ R(x))Задача 3 (3 балла). Для заданной формулы ϕ выяснить, применяя метод резолюций, является лиэта формула общезначимой.ϕ = ∀x(¬∃yP (x, y) ∨ R(x)) → ∃x∃y(P (x, y) → R(x))Задача 4 (3 балла).

Для заданного запроса G =? A(Y, X), not(A(X, Y )) к заданной логическойпрограмме P построить на основе стандартной стратегии вычислений (с использованием операторовотсечения и отрицания) дерево SLD-резолютивных вычислений и определить множество вычисленныхответов. Примечание: заглавными буквами начинаются имена переменных и предикатов, а строчнымибуквами — имена констант и функций.P : A(X, c)A(X, Y )B(g(X))B(X)E(b)D(c)←←←←←←E(X), !, not(B(X));D(X), B(g(Y ));!, D(X);B(g(X));;;Задача 5 (2 балла). Какая формула ϕ называется логическим следствием множества предложенийΓ? Приведите пример замкнутой формулы ϕ, которая не является логическим следствием множеcтвазамкнутых формул Γ = {∃xP (x), ∀x¬P (x)}?Задача 6 (2 балла).

Что называется эрбрановским универсумом заданной сигнатуры σ? Сколькоразличных элементов содержит эрбрановский универсум сигнатуры σ, состоящей из одного одноместного предикатного символа P , одного одноместного функционального символа f и из одной предметнойконстанты c ?Задача 7 (2 балла). Приведите определение SLD-резольвенты запроса G и программного утверждения D. Выпишите все SLD-резольвенты запроса ? P (X, c), P (c, f (X)) и программного утвержденияP (X, X) ← R(X).Задача 8 (2 балла).

Что называется стратегией вычисления логических программ? Зависит лиответ на запрос G =? not(P (x)) от того, какая именно стратегия вычисления применяется?Задача 9 (2 балла). Как определяется интерпретация интуиционистской логики высказываний?Является ли формула p → ¬¬p общезначимой в интуиционистской логике высказываний?Задача 10 (3 балла). Известно, что некоторая модель для формулы ϕ не является моделью дляформулы ψ. Какие из приведенных ниже утверждений всегда верны для любых замкнутых формул ϕиψ?1.

Формула ϕ является логическим следствием формулы ψ, потому что...2. Формула ψ является логическим следствием формулы ϕ, потому что...3. Не существует успешного табличного вывода из таблицы T 0 = h{ψ}, {ϕ}i, потому что...4. Не существует успешного табличного вывода из таблицы T = h{ϕ}, {ψ}i, потому что...5. Все приведенные выше утверждения в общем случае неверны, потому что...Задача 11 (3 балла). Выберите и мотивируйте правильные продолжения следующего утверждения.«Формула ϕ логики предикатов первого порядка выполнима тогда и только тогда, когда...»1.

В любом дереве табличного вывода для исходной таблицы T = h{ϕ}, ∅i каждая ветвь завершаетсяаксиомой, потому что ....2. В любом дереве табличного вывода для исходной таблицы T = h{ϕ}, ∅i хотя бы одна ветвь завершается аксиомой, потому что ....3. Хотя бы в одном дереве табличного вывода для исходной таблицы T = h{ϕ}, ∅i каждая ветвьзавершается аксиомой, потому что ....4. Хотя бы в одном дереве табличного вывода для исходной таблицы T = h{ϕ}, ∅i хотя бы однаветвь завершается аксиомой, потому что ....5.

Ни одно из приведенных выше продолжений утверждения не верно, потому что....Задача 12 (3 балла). Известно, что запрос ? P (x) к программе P имеет успешное SLD-резолютивноеопровержение, в результате которого в качестве ответа вычисляется подстановка {x/f (y)}. Какие изприведенных ниже утверждений будут всегда справедливы, независимо от программы P и атома P (x)и модели I? Ответ обосновать.1.

P |= ∀x P (x), потому что...2. P |= ∃x P (x), потому что...3. P |= ∀y P (f (y)), потому что...4. P |= ∃y P (f (y)), потому что...5. Ни одно из приведенных выше утверждений в общем случае не верно.Задача 13 (3 балла). Какие из приведенных ниже утверждений справедливы и почему?1. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей хорновской логической программы с использованием стандартной стратегии вычисления, потому что...2. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей логической программой, но лишь с использованием нестандартной стратегии вычисления, потому что...3. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей логической программы с использованием стандартной стратегии вычисления, но лишьпри добавлении операторов is и not, потому что...4.

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