задачи с ответами (2012) (1162130), страница 3
Текст из файла (страница 3)
Такая минимальная модель существует, вообще говоря,не всегда, например, Г={A V B}.CWA-логическое следствие: пусть существуется непротиворечивое множество замкнутыхформул Г и замкнутая формула ф.Тогда формула -ф является логическим следствием Гв допущении замкнутости мира Г |= cwa - ф,если неверно,что ф логически следует из Г.(CWA = close world assumption).Теперь наш второй вопрос.Чтобы эта штука была верной,по определениюнеобходимо,чтобы был неверен факт: “ф логически следует из”.На мой взгляд,этотфакт не верен.Значит,ответ “Верно”Тут, как заметили в аналогичном вопросе, для случая ф=пси получаются странныевещи. Также, может быть, стоит обратить внимание на факт “Такая минимальнаямодель существует, вообще говоря, не всегда, например, Г={A V B}.” - тут как разтакой случай, но что из этого следует?____________________________________________________________________Задача 9 (2 балла).Как определяется интерпретация интуиционистской логики высказываний?Является ли формула p → ¬¬p общезначимой в интуиционистской логикевысказываний?1) Лекция 18-19 слайд 11.2) является (это один из законов ИЛ)___________________________________________________________Задача 5 (2 балла).Сформулируйте теорему о логическом следствии для классической логикипредикатов.
Верно ли, что всякое множество замкнутых формул имеет бесконечномного различных логических следствий?___________________________________________________________Задача 6 (2 балла).Сформулируйте теорему о сколемовской стандартной форме?Выполнимость замкнутой формулы <=> Выполнимость ССФВерно ли. что если формула phi в предварённой нормальной форме являетсяобщезначимой формулой, то и соответствуюзая ей сколемовская стандартнаяформа так же будет общезначимой формулой?Нет, пример: ПНФ exists x P(x) V any x !P(x), ССФ: any X (P(c) V !P(x))Общезначимость не сохраняется, так как при замене кванторов существования нафункциональные символы и константы теряется свобода выбора этих функциональныхсиволов и констант, они уже зависят от интерпретации.___________________________________________________________Задача 7 (2 балла).Опишите алгоритм вычисления наиболее общего унификатора двух атомовP(t1,t2,...,tn) и P(s1,s2,...,sn)Составляем систему уравнений:t1 = s1t2 = s2…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->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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
