Mathlog_Answers (Экзаменационные варианты)

Задача 10. Известно, что некоторая модель для формулы φ не является моделью для формулы ψ. Какие из приведенных ниже утверждений всегда верны для любых замкнутых формул φ и ψ?

1. Не существует успешного табличного вывода из таблицы T' = <{ψ}, {φ}>, потому что…

2. Не существует успешного табличного вывода из таблицы T = <{φ}, {ψ}>, потому что… (По условию существует интерпретация, в которой формулы φ верны, а ψ - не верны. Следовательно, в этой интерпретации не существует успешного табличного вывода из таблицы T = <{φ}, {ψ}, так как она является выполнимой)

3. Формула φ является логическим следствием формулы ψ, потому что…

4. Формула ψ является логическим следствием формулы φ, потому что…

5. Все приведенных выше утверждения в общем случае неверны, потому что…

Задача 11. Известно, что для семантической таблицы T=<{φ}, {ψ}> нельзя построить ни одного успешного табличного вывода. Какие из приведенных ниже утверждений всегда верны для любых замкнутых формул φ и ψ?

1. Таблица T' =<{φ}, {ψ}> не выполнима потому что…

2. Не существует успешного табличного вывода из таблицы T = <{ψ}, {φ}>,, потому что…

3. Формула φ не является логическим следствием формулы ψ, потому что…

4. Формула ψ не является логическим следствием формулы φ, потому что… (φ=1 -> ψ=0)

5. Все приведенных выше утверждения в общем случае неверны, потому что…

Задача 11. Пусть задано некоторое непустое множество дизъюнктов S0. Пусть S1 – это множество всех формул, резолютивно выводимых из множества дизъюнктов S0. Какие из приведенных ниже утверждений всегда справедливы и почему?

1. Если каждый дизъюнкт множества S0 выполним, то и каждый дизъюнкт множества S1 выполним, потому что…

2. Если каждый дизъюнкт множества S1 выполним, то множество дизъюнктов S0 имеет модель, потому что… из s1 не вывели пустой диз -> s0 имеет модель

3. Если множество дизъюнктов S0 имеет модель, то множество дизъюнктов S1 имеет модель, потому что… так как s0->s1

4. Все приведенные выше утверждения всегда верны, потому что…

Задача 12. Пусть Р – это хорновская логическая программа, а S – это множество всех дизъюнктов, соответствующих программным утверждениям программы Р. Известно, что для наименьшей эрбрановской модели МР программы Р выполняется соотношение МР = ø. Какие из приведенных ниже утверждений будут при этом всегда верны и почему?

1. Система дизъюнктов S выполняется в каждой эрбрановской интерпретации, потому что…

2. Из системы дизъюнктов S нельзя вывести ни одной резольвенты, потому что…

3. Система дизъюнктов S является противоречивой, потому что…

4. В каждом дизъюнкте из системы S есть хотя бы один атом со связкой отрицания ¬, потому что… (в этой программе нет фактов, так как если в ней есть хотя бы одитн факт, то мэм !=0 -> a0<-a1,…,an переходит в а0 или не а1 или … не аn)

5. Все приведенные выше утверждения всегда неверны, потому что…

Задача 13. Какие из приведенных ниже утверждений справедливы и почему?

1. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей хорновской логической программой с использованием стандартной стратегии вычисления, потому что…

2. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей логической программой, но лишь с использованием нестандартной стратегии вычисления, потому что…

3. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей логической программой с использованием стандартной стратегии вычисления, но лишь при добавлении операторов is и not, потому что…

4. Существует арифметическая функция, вычислимая на машине Тьюринга, для вычисления которой нет логической программы даже в случае использования операторов is и not, потому что…

1 верно, потому что хорновские программы могут моделировать машины Тьюринга (теорема Чёрча - для любой программы на машине Тьюринга существует соответствующая хорновская программа) остальные неверны, потому что противоречат 1му. Но вообще-то объяснений неверным пунктам можно и не давать (алгоритимческая универсальность хорновского логического программирования)

Задача 14. Пусть Г – некоторое множество замкнутых формул логики предикатов. Верно ли, что Г является непротиворечивым множеством тогда и только тогда, когда всякая дизъюнкция вида , где , не является общезначимой?

1. Верно, потому что…

2. Неверно, потому что…

3. Зависит от множества Г, доказательством тому являются 2 примера…

6, Потому что

А) Пусть верно => Любое подмножество Г непротиворечиво => Любая конъюнкция выполнима (не фи_i=false)

Б) Г – противоречиво => Существует противоречивая конъюнкция => ее отрицание - общезначимо

Задача 15. Известно, что в программе Р ответ на запрос ?P(х) не имеет успешных вычислений ( было изначально в варианте: всегда является отрицательным). Каким будет ответ на запрос ?not(P(с))?

1. Всегда положительным вне зависимости от программы Р, потому что…

2. Всегда отрицательным вне зависимости от программы Р, потому что…

3 Может быть как положительным, так и отрицательным в зависимости от вида программы Р, потому что…

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

Задача 16. Предположим, что в правило резолюции было внесено следующее изменение: резольвентой дизъюнктов D1=D1’or L1, D2=D2’ or Not(L2) объявляется всякий дизъюнкт D0=(D1’ and D2’)n, где n – унификатор (не обязательно наиболее общий) L1 и L2.

После этого изменения Теорема корректности резолютивного вывода (1) и Теорема полноты резолютивного вывода(2) будут…

1. 1,2 верно

2. 1 верно, 2 неверно

3. 1 неверно, 2 верно

4. 1,2 верно,

потому что 1. Полнота: если всякий раз в качестве этого "любого" унификатора

использовать наиболее общий, то получится обычный метод резолюций, а

он полон, так что полнота не теряется.

2. Корректность: поскольку переменные в дизъюнктах понимаются

связанными кванторами всеобщности, то добавление к системе примера

любого дизъюнкта из этой системы не изменяет ее (не-)противоречивости.

Остается заметить, что "расширенное" правило резолюции сводится к

вычислению "классической" резольвенты и взятию ее примера.

Задача 17. Предположим, что ни один основной атом не является логическим следствием хоновской логической программы P.

1 Интерпретация I=пуст мн-ву является можель P, тк

2 Программа Р не имеет ни одной модели

3 Любая эрбр интерпретация I явся моделью для Р

4 Исходное условие не осуществимо, то есть не существует ни одной такой хорновской логической программы Р, для которой выполнялось бы, что ни один основной атом не является логическим следствием хоновской логической программы P, потому что по теореме о наименьшей модели всякая хорновская логическая программа имеет наименьшую эрбрановскую модель

5 Ни одно(1-4)не верно, тк

Задача 18. Известно, что формула PLTL фи имеет длину n, а конечная модель (LTS) M имеет m состояний. Тогда система Хинтикки для фи представляет собой ориентированный граф , в котором m*2^O(n) вершин, потому что (s,B) в s – m, в В 2^O(n) множеств.

Задача 19. Формула фи логики предикатов 1го порядка выполнима тогда и только тогда, когда

1 В любом дереве табличного вывода для таблицы Т=<фи, 0> каждая ветвь завершается аксиомой

2 В любом дереве табличного вывода для таблицы Т=<фи, 0> хотя бы одна ветвь завершается аксиомой

3 Хотя бы в одном дереве табличного вывода для таблицы Т=<фи, 0> каждая ветвь завершается аксиомой

4 Хотя бы в одном дереве табличного вывода для таблицы Т=<фи, 0> хотя бы одна ветвь завершается аксиомой

5 1-4 не верно, потому что

Задача 20. Известно, что в программе Р ответ на запрос ?P(х) имеет успешное SLD-резолютивное опровержение, в результате которого в качестве ответа вычисляется подстановка {x/f(y)}. Что будет верно независимо от программы Р и атома Р(х) и модели I?

1 Р |= АхР(х)

2 Р |= ЕхР(х) x/f(y)

3 Р |= АхР(f(y)) мы вывели пустой дизъюнкт при x/f(y)

4 Р |= ЕхР(f(y))

5 все не верно

Задача 21. Известно, что эрбарановская интерпретация I является моделью хоновской логической программы P.

1 Множества I (= Succ(p)

2 I =) Succ(p) , потому что Succ(p) = минимальной эрбрановской модели по определению

3 I (= Succ(p) или I =) Succ(p), зависит от I

4 I , Succ(p) несравнимы

Задача 22. фи - формула логики предикатов в ссф. Что неверно?

1 Если фи выполнима, то фи выполнима хотя бы в одной эрб интерпретации для формулы фи(нет, так как мы можем взять формулу, которая выполнима в интерп с беск предметной областью, но не выполнима в интп с конечной – хотя бы одна конст и f)

2 Если фи выполнима хотя бы в одной эрб интерпретации для формулы фи, то фи выполнима

3 Если фи выполнима в каждой эрб интерпретации для формулы фи, то фи общезначима

4 Если фи не имеет эрб моделей, то фи не имеет никаких моделей (пример из1)

5 1-4 верно, потому что

Задача 23. Первая подстановка, которая будет вычислена программой Р в ответ на запрос G

1 зависит только от стратегии обхода SLd-вычислений программы Р для запроса G

2 зависит только от порядка расположения программных утверждений в Р

3 зависит только от порядка расположения подцелей в G

4 зависит только от порядка расположения атомов в теле процедур Р

5 зависти от 1-4

6 не зависит от 1-4

Задача 24. Изветсно, что каждое конечное подмножество D’ бесконечного семейства дизъюнктов D непротиворечиво.

1 семейство дизъюнктов D будет непротиворечивым.

2 семейство дизъюнктов D может быть как непротиворечивым, так и противоречивым

3 семейство дизъюнктов D будет противоречивым.

4 1-3 неверно.

Задача 23. G – запрос к хорновской логической программе Р

1 каждый правильный ответ является вычислимым ответом (тк прав ответ – частный случай вычислимого ответа)

2 каждый вычислимый ответ является правильным ответом (теорема о корректности sld)

3 Некоторые (не все) правильные ответы являются вычислимыми ответами

4 Некоторые (не все) вычмслимые ответы являются правильными ответами

Задача 24. Известно, что их множества дизъюнктов S можно посторить резолют вывод пустого диз.

1Существует успешный табличный вывод для Т=<0,s>

2 Существует успешный табличный вывод для Т=<s,0> в s есть d=false

3 не существует успешный табличный вывод для Т=<0,s>

4 не существует успешный табличный вывод для Т=<s,0>

5 1-4 неверно

Задача 25. Пусть Г – непустое множество логических следствий формулы φ. Г не имеет ни одной модели с конечной или счетной областью интерпретации

Что неверно?

1 φ не имеет ни одной модели с конечной или счетной областью интерпретации

2 φ не имеет вообще ни одной модели