2008 экзамен вариант 3 (Старые варианты экзамена)

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

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

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

Как формулируется теорема компактности Мальцева? Следует ли из теоремыкомпактности теорема Эрбрана?Задача 7 (2 балла). Какой ответ на запрос G к хорновской логической программе P называетсяправильным? Сколько правильных ответов может иметь запрос G =?A, обращенный к хорновскойлогической программе P, в том случае, если A — основной атом?Задача 8 (2 балла). Что означает алгоритмическая универсальность хорновского логического программирования? Верно ли, что для любой логической программы с операторами отсечения и отрицаниясуществует такая хорновская логическая программа (без отсечений и отрицаний), которая вычисляетточно такое же множество ответов?Задача 9 (2 балла). Как определяется отношение выполнимости I, w |= ϕ в модальной логике?Верно ли, что для любой модели Крипке I и для любого состояния w если I, w 6|= ¬p, то I, w |= ♦p ?Задача 10 (3 балла).

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

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

Какие из приведенных ниже утверждений справедливы ипочему?1. Интерпретация I = ∅ является моделью программы P, потому что....2. Программа P не имеет ни одной модели, потому что...3. Любая эрбрановская интерпретация I является моделью программы P, потому что...4. Исходное условие неосуществимо, то есть не существует ни одной такой хорновской логическойпрограммы P, для которой выполнялось бы указанное предположение, потому что ...5. Ни одно из указанных утверждений не верно, потому что...Задача 13 (3 балла).

Известно, что формула PLTL ϕ имеет длину n, а конечная модель (LTS) Mимеет m состояний. Тогда система Хинтикки для формулы ϕ и LTS M представляет собой ориентированный граф, в котором содержится самое большее1. O(nm ) вершин, потому что....2. O(mn ) вершин, потому что....3. n2O(m) вершин, потому что....4. m2O(n) вершин, потому что....5. 2O(nm) вершин, потому что.....