2009 экзамен вариант 2 (Старые варианты экзамена)

ВариантЗадача 0 (6 баллов). Слово — это конечный непустой список букв фиксированного конечногоалфавита. Словарь — это конечный непустой список попарно различных слов. Построить логическуюпрограмму, которая для заданного словаря L разбивает множество слов L на два такихнепересекающихся словаря X и Y = L \ X, что никакие два слова w1 ∈ X и w2 ∈ Y не имеют ниодной общей буквы. Запрос к программе должен иметь вид ? G(L, X, Y ).Задача 1 (3 балла).

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

Для заданной формулы ϕ выяснить, применяя метод семантических таблиц,является ли эта формула общезначимой.ϕ = ∃y(∃xP (y, x) → ∀xR(x)) → ∀x(¬∀yP (y, f (x)) ∨ R(x))Задача 3 (3 балла). Для заданной формулы ϕ выяснить, применяя метод резолюций, является лиэта формула общезначимой.ϕ = ∀x(P (x, x) → ∀x(R(x) → ∃x(∃xP (x, x) & R(x))))Задача 4 (3 балла). Для заданного запроса G =? A(Y, Y ), not(A(X, Y )) к заданной логическойпрограмме P построить на основе стандартной стратегии вычислений (с использованием операторовотсечения и отрицания) дерево SLD-резолютивных вычислений и определить множество вычисленныхответов. Примечание: заглавными буквами начинаются имена переменных и предикатов, а строчнымибуквами — имена констант и функций.P : A(c, Y )A(X, b)B(c)B(g(X))E(b)←←←←←B(g(Y )), E(Y );E(X), !, not(B(X));!;B(X);;Задача 5 (2 балла).

Сформулируйте теорему компактности Мальцева. Следует ли из этой теоремыутверждение: «Если бесконечное множество предложений Γ не имеет модели, то хотя бы однопредложение множества Γ является противоречивым»?Задача 6 (2 балла). Какие формулы логики предикатов называются равносильными? Докажите,что два предложения ϕ и ψ являются равносильными тогда и только тогда, когда множествологических следствий формулы ϕ совпадает с множеством логических следствий формулы ψ?Задача 7 (2 балла). Какой ответ на запрос G к хорновской логической программе P называетсявычисленным? Существуют ли такие правильные ответы на запрос G к хорновской логическойпрограмме P, которые не могут быть вычислены?Задача 8 (2 балла).

Что такое допущение замкнутости мира? Верно ли, что ϕ ∨ ψ |=CW A ¬ϕ?Задача 9 (2 балла). Как определяется отношение выполнимости I, s0 |= ϕUψ в темпоральнойлогике PLTL? Являются ли формулы ϕU(ψ1 &ψ2 ) и ϕUψ1 & ϕUψ2 равносильными?Задача 10 (3 балла). Известно, что для семантической таблицы T = h{ϕ}, {ψ}i нельзя построитьни одного успешного табличного вывода.

Какие из приведенных ниже утверждений всегда верны длялюбых замкнутых формул ϕ и ψ ?1. Таблица T = h{ϕ}, {ψ}i не является выполнимой, потому что...2. Для таблицы T 0 = h{ψ}, {ϕ}i также не существует ни одного успешного табличного вывода,потому что...3. Формула ϕ не является логическим следствием формулы ψ, потому что...4. Формула ψ не является логическим следствием формулы ϕ, потому что...5.

Все приведенные выше утверждения в общем случае неверны, потому что...Задача 11 (3 балла). Предположим, что в правило резолюции было внесено следующее изменение:резольвентой дизъюнктов D1 = D10 ∨L1 и D2 = D20 ∨¬L2 объявляется всякий дизъюнкт D0 = (D10 ∨D20 )η,где η — некоторый унификатор (необязательно наиболее общий) литер L1 и L2 . Какие из приведенныхниже утверждений будут справедливы и почему?1. После такого изменения и теорема корректности резолютивного вывода и теорема полнотырезолютивного вывода уже будут неверны, потому что...2. После такого изменения теорема корректности резолютивного вывода остается верной, а теоремаполноты резолютивного вывода уже будет неверна, потому что...3. После такого изменения теорема полноты резолютивного вывода остается верной, а теоремакорректности резолютивного вывода уже будет неверна, потому что...4.

После такого изменения и теорема корректности резолютивного вывода и теорема полнотырезолютивного вывода остаются верными, потому что...Задача 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 балла). Известно, что запрос ? P (x) к логической программе P не имеет успешныхвычислений. Каким может быть ответ на запрос ?not(P (c)) к логической программе P ? Выберите изпредложенных вариантов ответа на этот вопрос правильные и обоснуйте их.1. Ответ на запрос ? not(P (c)) всегда будет положительный независимо от программы P, потомучто....2. Ответ на запрос ? not(P (c)) всегда будет отрицательный независимо от программы P, потомучто....3.

Ответ на запрос ? not(P (c)) может быть как положительным, так и отрицательным, взависимости от программы P, потому что.....4. На запрос ? not(P (c)) может быть вообще не получено никакого ответа, потому что.....