Матлогика - задачи с примечаниями (1162128), страница 3

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

Текст из файла (страница 3)

Составляем систему уравнений:

t1 = s1

t2 =

…

tn = sn

Применяем 6 правил. Решение очень похоже на решение обычных систем уравнения. В общем делает то, что кажется правильным, 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->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 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. Корректность: поскольку переменные в дизъюнктах понимаются

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

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

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

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

ИМХО потому что. По теореме Эрбрана система дизъюнктов противоречива ⇔ когда существует конечное противоречивое множество основных примеров. Т. е. то каким образом мы будем выбирать эти основные примеры не играет роли.

Задача 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 неверно.

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

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