2008 экзамен вариант 2 (1162058)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

ВариантЗадача 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 ).Каков этот алгоритм?.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов ответов (шпаргалок)