2008 экзамен вариант 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 балла).

Пусть A(X) — атом, P — хорновская логическая программа, I — эрбрановскаямодель для логической программы P. Какие из приведенных ниже утверждений всегда справедливыи почему?1. Если I |= ∃X A(X), то запрос ? A(X), обращенный к программе P, имеет хотя бы одно успешноевычисление, потому что...2. Если все вычисления запроса ? A(X), обращенного к программе P, являются успешными, тоI |= ∀X A(X), потому что...3. Если хотя бы одно вычисление запроса ? A(X), обращенного к программе P, является успешным,то I |= ∃X A(X), потому что...4. Если I |= ∀X A(X), то все вычисления запроса ? A(X), обращенного к программе P, являютсяуспешными, потому что...Задача 12 (3 балла).

Пусть ϕ — замкнутая формула логики предикатов, а ψ — ее сколемовскаястандартная форма. Какие из приведенных ниже утверждений всегда верны и почему?1. Если формула ϕ общезначима, то ψ также общезначима, потому что...2. Какова бы ни была интерпретация I, если I |= ϕ, то I |= ψ, потому что...3. Какова бы ни была интерпретация I, если I |= ψ, то I |= ϕ, потому что...4. Если формула ψ общезначима, то ϕ также общезначима, потому что...5. Все приведенные выше утверждения неверны.Задача 13 (3 балла). Докажите, что существует алгоритм, проверяющий общезначимость формуллогики предикатов, предваренная нормальная форма которых имеет вид∀x1 ∀x2 .

. . ∀xn ϕ(x1 , x2 , . . . , xn ).Каков этот алгоритм?.