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

ВариантЗадача 0. Слово — это конечный непустой список букв фиксированного конечного алфавита. Текст— это конечный непустой список слов. Построить логическую программу, которая для двух заданныхтекстов L1 и L2 вычисляет бесповторный список X, состоящий из всех тех слов текста L1 , в которыхесть хотя бы одна буква, не встречающаяся ни в одном слове текста L2 . Запрос к программе должениметь вид ? G(L1 , L2 , X).Задача 1. Используя константные, функциональные и предикатные символы алфавита (см.

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

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

Какая формула ϕ называется логическим следствием множества предложений Γ? Существует ли хотя бы одна такая формула, которая является логическим следствием любого множествапредложений Γ?Задача 6. Какова формулировка теоремы об эрбрановских интерпретациях? Верно ли, что каждаянепротиворечивая система дизъюнктов имеет хотя бы одну эрбрановскую модель?Задача 7. Какова формулировка теоремы корректности операционной семантики относительно декларативной семантики? Верно ли, что из этой теоремы следует, что для любого атома из наименьшейэрбрановской модели MP программы P запрос ?A, обращенный к программе P имеет успешное вычисление?Задача 8.

Какова формулировка теоремы Черча о проблеме общезначимости в классической логикепредикатов? Следует ли из этой теоремы, что не существует алгоритма, проверяющего выпонимостьформул логики предикатов?Задача 9. Как формулируется задача верификации моделей программ (model checking)? К какимзадачам теории графов сводится задача model-checking для темпоральной логики PLTL?Задача 10. Известно, что выполнимые замкнутые формулы ϕ и ψ не имеют ни одной общей модели.Какие из приведенных ниже утверждений всегда верны и почему?1. Существует формула χ, логическим следствием которой являются обе формулы ϕ и ψ, потомучто ...2.

Существует формула χ, которая является логическим следствием обеих формул ϕ и ψ, потомучто ...3. Не существует ни одного успешного табличного вывода из семантической таблицы h{ϕ}, {ψ}i,потому что ...4. Все приведенные выше утверждения верны.Задача 11. Известно, что из множества непустых дизъюнктов 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. Предположим, что для хорновской логической программы P выполняется соотношениеTP (∅) = ∅, где TP — оператор непосредственного логического следования для программы P. Какие изприведенных ниже утверждений справедливы и почему?1.

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

Из логической программы 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. Ни одно из приведенных выше утверждений в общем случае неверно..