2009 экзамен вариант 2 (1162065)

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

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

ВариантЗадача 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 балла). Предположим, что в правило резолюции было внесено следующее изменение:резольвентой дизъюнктов D1 = D10 ∨L1 и D2 = D20 ∨¬L2 объявляется всякий дизъюнкт D0 = (D10 ∨D20 )η,где η — некоторый унификатор (необязательно наиболее общий) литер L1 и L2 .

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

Известно, что запрос ? P (x) к программе P имеет успешное SLD-резолютивноеопровержение, в результате которого в качестве ответа вычисляется подстановка {x/f (y)}. Какие изприведенных ниже утверждений будут всегда справедливы, независимо от программы P и атома P (x)и модели I? Ответ обосновать.1. P |= ∀x P (x), потому что...2. P |= ∃x P (x), потому что...3. P |= ∀y P (f (y)), потому что...4. P |= ∃y P (f (y)), потому что...5. Ни одно из приведенных выше утверждений в общем случае не верно.Задача 13 (3 балла).

Известно, что запрос ? P (x) к логической программе P не имеет успешныхвычислений. Каким может быть ответ на запрос ?not(P (c)) к логической программе P ? Выберите изпредложенных вариантов ответа на этот вопрос правильные и обоснуйте их.1. Ответ на запрос ? not(P (c)) всегда будет положительный независимо от программы P, потомучто....2. Ответ на запрос ? not(P (c)) всегда будет отрицательный независимо от программы P, потомучто....3. Ответ на запрос ? not(P (c)) может быть как положительным, так и отрицательным, взависимости от программы P, потому что.....4.

На запрос ? not(P (c)) может быть вообще не получено никакого ответа, потому что.....

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

Тип файла PDF

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

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

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