Задачи с ответами (2012) (1158171), страница 3
Текст из файла (страница 3)
Решение очень похоже на решение обычных систем уравнения. Вобщем делает то, что кажется правильным, 6 правил запоминать наизусть, на мой взгляд,нет смысла.___________________________________________________________Задача 8 (2 балла).Что называется деревом SLD-резолютивных вычислений запроса G, обращённогок хорновской логической программе P? Зависит ли устройство дерева SLDрезолютивных вычислений от правила выбора подцелей?Фафа ляля.Зависит. Или не зависит (аргументация ниже)Хотя...
Деревья, в которых подцели выбирались разным образом, будут равными с точностью до порядкаподветвей в каждой точке ветвления, так как всё равно будут посещены все ветви. То есть еслирасматривать деревья как графы - то они равны и ответ “Не зависит”. “Устройство дерева” - не оченьточное понятие, и непонятно по какому критерию эти “устройства деревьев” сравнивать.___________________________________________________________Задача 9 (2 балла).Как определяется отношение выполнимости I,t |=PLTL? Верно ли, что формулыформулами логики PLTL?в темпоральной логикеявляются равносильными______________________________________________________________________________Задача 10.
Известно, что некоторая модель для формулы φ не является моделью дляформулы ψ. Какие из приведенных ниже утверждений всегда верны для любых замкнутыхформул φ и ψ?1. Не существует успешного табличного вывода из таблицы T' = <{ψ}, {φ}>, потомучто…2. Не существует успешного табличного вывода из таблицы T = <{φ}, {ψ}>,потому что… (По условию существует интерпретация, в которой формулы φверны, а ψ - не верны. Следовательно, в этой интерпретации не существуетуспешного табличного вывода из таблицы T = <{φ}, {ψ}, так как она являетсявыполнимой)3. Формула φ является логическим следствием формулы ψ, потому что…4. Формула ψ является логическим следствием формулы φ, потому что…5. Все приведенных выше утверждения в общем случае неверны, потому что…Задача 11.
Пусть задано некоторое непустое множество дизъюнктов S0. Пусть S1 – этомножество всех формул, резолютивно выводимых из множества дизъюнктов S0. Какие изприведенных ниже утверждений всегда справедливы и почему?1. Если каждый дизъюнкт множества S0 выполним, то и каждый дизъюнкт множестваS1 выполним, потому что…2.
Если каждый дизъюнкт множества S1 выполним, то множество дизъюнктовS0 имеет модель, потому что… из s1 не вывели пустой диз -> s0 имеет модель3. Если множество дизъюнктов S0 имеет модель, то множество дизъюнктов S1имеет модель, потому что… так как s0->s14. Все приведенные выше утверждения всегда верны, потому что…Задача 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му.
Но вообще-то объяснений неверным пунктам можно и не давать(алгоритимческая универсальность хорновского логического программирования)Задача 13. Какие из приведенных ниже утверждений справедливы и почему?5. Любая арифметическая функция, вычислимая на машине Тьюринга, может бытьвычислена подходящей хорновской логической программой с использованиемстандартной стратегии вычисления, потому что…6.
Любая арифметическая функция, вычислимая на машине Тьюринга, может бытьвычислена подходящей логической программой, но лишь с использованиемнестандартной стратегии вычисления, потому что…7. Любая арифметическая функция, вычислимая на машине Тьюринга, может бытьвычислена подходящей логической программой с использованием стандартнойстратегии вычисления, но лишь при добавлении операторов is и not, потому что…8.
Существует арифметическая функция, вычислимая на машине Тьюринга, длявычисления которой нет логической программы даже в случае использованияоператоров is и not, потому что…1 верно, потому что хорновские программы могут моделировать машины Тьюринга(теорема Чёрча - для любой программы на машине Тьюринга существуетсоответствующаяхорновскаяпрограмма)остальныеневерны,потомучтопротиворечат 1му. Но вообще-то объяснений неверным пунктам можно и не давать(алгоритимческая универсальность хорновского логического программирования)Задача 14.
Пусть Г – некоторое множество замкнутых формул логики предикатов. Верноли, что Г является непротиворечивым множеством тогда и только тогда, когда всякаядизъюнкция вида фи1 V фи2 V... V фиN, где фиi Г не является общезначимой?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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
