Ответы к задачам

Задача 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) ← 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 не верно, потому что пример : ForAll(x) P(x)

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

1 Р |= АхР(х)

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

3 Р |= АхР(f(y)), т.к. P(f(y)) и любой частный случай являются логическими следствиями программы P (из условия)

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 Если фи выполнима, то фи выполнима хотя бы в одной эрб интерпретации для формулы фи

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

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

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

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

1. была такая теорема (теорема об эрбрановских моделях)

2. по определению выполнимости

3. если она необщезначима, есть интерпретация и набор, на которых она ложна, и можно по ним построить эрбрановскую, где она ложна.

4. Неверно, по теореме об эрбрановских моделях

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

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

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

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

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

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

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

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

1 семейство дизъюнктов D будет непротиворечивым. (теорема: если D противоречиво, то есть конечное подмножество формул из D, которое противоречиво

очевидный факт: если D непротиворечиво, то любое конечное подмножество непротиворечиво).

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

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

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

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

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

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

3 Некоторые (не все) правильные ответы являются вычислимыми ответами ? Если имеется в виду, что есть правильный, который не вычислимый, то это фигня. Если могут как все, так и не все, то верно.

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

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

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

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