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

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

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

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

Какая семантическая таблица T = hΓ, ∆i называется выполнимой? Может ливыполнимая таблица содержать только невыполнимые формулы?Задача 6 (2 балла). Какова формулировка теоремы об эрбрановских интерпретациях? Сколькоэрбрановских моделей в сигнатуре σ = hConst = {c}, F unc = ∅, P red = {P }i имеет формула ϕ =∃xP (x)&¬P (c)?Задача 7 (2 балла). Какова формулировка теоремы полноты операционной семантики хорновскихлогических программ относительно декларативной семантики? Верно ли, что из этой теоремы полнотыследует, что для любого основного атома A, являющегося логическим следствием программы P, любоевычисление запроса ?A, обращенного к программе P, является успешным?Задача 8 (2 балла). Какова формулировка теоремы Черча о проблеме общезначимости в классической логике предикатов? Существует ли алгоритм, проверяющий противоречивость конечных множеств замкнутых формул логики предикатов?Задача 9 (2 балла).

Как определяется отношение выполнимости I, s0 |= Fψ в темпоральной логикеPLTL? Являются ли формулы F(ψ1 &ψ2 ) и Fψ1 & Fψ2 равносильными?Задача 10 (3 балла). Известно, что выполнимые замкнутые формулы ϕ и ψ не имеют ни однойобщей модели. Какие из приведенных ниже утверждений всегда верны и почему?1. Существует формула χ, логическим следствием которой являются обе формулы ϕ и ψ, потомучто ...2. Существует формула χ, являящаяся логическим следствием обеих формул ϕ и ψ, потому что ...3. Не существует ни одного успешного табличного вывода из семантической таблицы h{ϕ}, {ψ}i,потому что ...4.

Все приведенные выше утверждения верны.Задача 11 (3 балла). Известно, что из множества непустых дизъюнктов S = {D1 , D2 , . . . , DN } можно построить резолютивный вывод пустого дизъюнкта . Какие из приведенных ниже утвержденийвсегда справедливы и почему?1. Семантическая таблица T = h∅, {D1 &D2 & . . . &DN }i имеет успешный табличны вывод, потомучто...2. Семантическая таблица T = h∅, {D1 &D2 & . . .

&DN }i не имеет успешного табличного вывода, потому что...3. Семантическая таблица T = h{D1 &D2 & . . . &DN }, ∅i имеет успешный табличны вывод, потомучто...4. Семантическая таблица T = h{D1 &D2 & . . . &DN }, ∅i не имеет успешного табличного вывода, потому что...5. Ни одно из приведенных утверждений в общем случае неверно.Задача 12 (3 балла). Пусть P0 , P1 и P2 — три хорновские логические программы и при этомP0 = P1 ∪ P2 . Пусть θ — некоторый ответ на запрос G.

Какие из приведенных ниже утвержденийверны и почему?1. Если подстановка θ является правильным ответом на запрос G, обращенный к программе P0 , толибо θ является правильным ответом на запрос G, обращенный к программе P1 , либо θ являетсяправильным ответом на запрос G, обращенный к программе P2 , потому что...2. Если подстановка θ является правильным ответом на запрос G, обращенный к программе P0 , то θявляется правильным ответом на запрос G, обращенный как к программе P1 , так и к программеP2 , потому что...3. Если подстановка θ является правильным ответом на запрос G, обращенный к программе P0 ,но не является правильным ответом на запрос G, обращенный к программе P1 , то запрос Gθ,обращенный к программе P2 , имеет успешное вычисление, потому что...4.

Ни одно из приведенных выше утверждений в общем случае не является верным, потому что...,Задача 13 (3 балла). Из логической программы P (содержащей операторы отсечения и отрицания)с запросом G были удалены все операторы отсечения, в результате чего образовалась новая программаP 0 . Какие из приведенных ниже утверждений будут всегда верны и почему?1. Всякое успешное вычисление запроса G к программе P будет также являться успешным вычислением запроса G к программе P 0 , потому что...2.

Всякое успешное вычисление запроса G к программе P 0 будет также являться успешным вычислением запроса G к программе P, потому что...3. Всякий вычислимый ответ на запрос G к программе P будет также являться вычислимым ответомна запрос G к программе P , потому что...4. Всякий вычислимый ответ на запрос G к программе P 0 будет также являться вычислимым ответом на запрос G к программе P, потому что...5. Ни одно из приведенных выше утверждений в общем случае неверно..