Задачи с ответами (2012)

Задача 5.Какая формула ϕ называется логическим следствием множества предложений Γ?Существует ли хотя бы однаdедложений Γ? Приведите пример замкнутой формулыϕ, которая не является логическим следствием множествазамкнутых формул Γ = {∃xP(x), ∀x¬P(x)}?Ответ: логическое следствие <=> каждая модель Г является моделью для phi(в определении сказано, что речь идёт о замкнутых формулах), очевидно чтообщезначимая формула будет лог.

следствием любого Г.Пример замкнутой формулы ф: множество противоречиво => любая замкнутаяформула является логическим следствием => нельзя привести примера______________________________________________________________________________Задача 6.Какова формулировка теоремы об эрбрановских интерпретациях? Верно ли, чтокаждая непротиворечивая система дизъюнктов имеет хотя бы одну эрбрановскуюмодель?Теорема: Система дизъюнктов S выполнима тогда и только тогда, когда S имеетэрбрановскую модель, т.е. выполнима хотя бы в одной H-интерпретации.“И, как будет показано, для проверки противоречивости систем дизъюнктов достаточноограничиться рассмотрением H-интерпретаций” - соответственно, да______________________________________________________________________________Задача 7.Какова формулировка теоремы корректности операционной семантикиотносительно декларативной семантики? Верно ли, что из этой теоремы следует,что для любого атома из наименьшей эрбрановской модели MP программы Pзапрос? A, обращенный к программе P имеет успешное вычисление?Любой вычисленный ответ является правильным.

(2го вопроса не будет, т.к. он сказал чтовыкинул модели программ из курса)______________________________________________________________________________Задача 8.Какова формулировка теоремы Черча о проблеме общезначимости в классическойлогике предикатов? Следует ли из этой теоремы, что не существует алгоритма,проверяющего выполнимость формул логики предикатов?Теорема: Следствие 2 (Теорема Черча).Не существует алгоритма, способного определить по заданной замкнутой формулелогики предикатов ϕ, является ли эта формула общезначимой, т.

е. проблемаобщезначимости "|= ϕ ?" алгоритмически неразрешима.Да, следует,т.к. проблема выполнимости phi <=> проблема общезначимости !phi.______________________________________________________________________________Задача 9. Как формулируется задача верификации моделей программ (modelchecking)? К каким задачам теории графов сводится задача model-checking длятемпоральной логики PLTL?Для любой PLTL fi и CLS M проверить M |= fi (для любой трассы tr,tr принадлежитTr0(M),имеет место I(tr),0 |= fi).Поиск компонент связанности.______________________________________________________________________________Задача 5.Какая семантическая таблица 〈Γ, ∆〉 называется выполнимой ? Является ливыполнимой семантическая таблица 〈{P (x)}, {P (y)}〉?Семантическая таблица 〈Γ, ∆〉 называется выполнимой, если существует такая I и d1...dnпринадлежащие DI ,что для любой фи из Г выполняется, что I |= фи(x1,...,xn)[d1...dn] и длялюбой пси из ∆ выполняется что I |=/=пси(x1,..,xn)[d1..dn].Таблица 〈{P (x)}, {P (y)}〉 выполнима т.к.

она атомарна и не закрыта.для тех, кто не верит:пример: d1, d2, P(d1)=true, P(d2) = false, x=d1, y=d2... вот интерпретацияи набор значений свободных переменных, для которых все формулы из Гистинны, а из Д - ложны, значит выполнима.______________________________________________________________________________Задача 6.Что такое эрбрановский универсум? Каким условиям должна удовлетворятьсигнатура σ для того, чтобы эрбрановский универсум сигнатуры σ был конечныммножеством?H - эрбраноj,вский универсум сигнатуры <Const,Func,Pred> - это множество H=Uoo0 Hi,гдеH0=либо Const, если Const непустое, либо {c} (эрбрановская константа), если Constпустое; Hi=Hi-1 U {f(n)(t1...tn), где f принадлежит Func, t1...tn - принадлежат Hi-1}.Чтоб универсум был конечен Func должно быть пустым, и Const - конечным.______________________________________________________________________________Задача 7.Какая интерпретация называется эрбрановской моделью для хорновскойлогической программы P? Верно ли то, что всякая хорновская логическаяпрограмма имеет непустую эрбрановскую модель?Эрбрановская интерпретация I для логической программы P называется её моделью,если она является моделью для любого хорновского дизъюнкта, входящего в неё.Да, верно.

(Этого не будет на экзамене)______________________________________________________________________________Задача 8.Сформулируйте правило SLDNF-резолюции. Какой ответ будет получен на запрос ?not(P (x)) к программе P = {P (c) ← R(c)}?Пусть имеется G:?not(C1),C2...Cn к программе P.Для вычисления SLDNF-резольвенты G1:1. формируется запрос G`:?C1 к программе P2.

проводится построение дерева вычислений T для запроса G`3. возможен 1 из 3х исходов:-Успех, если все ветви дерева завершились failure-Failure, если хотя бы одна ветвь дерева завершилась Успехом-Бесконечность, если дерево бесконечно и не было обнаружено успешных вычислений.В реальности, это не совсем так, результат зависит от порядка выборапрограммных правил.Построится дерево для запроса ?P(X), которое завершится failure. Тогда для исходногозапроса будет вычислен ответ, являющийся пустой подстановкой.Никакого, т.к. программа зациклица (неверно, ответа не будет т.к.

нет правила для R(c)).______________________________________________________________________________Задача 9.Как определяется интерпретация темпоральной логики линейного времени PLTL ?Являются ли равносильными PLTL формулы Fp и (p ∨ ¬p)Up?I=<N,<=,кси>N - {0,1,2...}-моменты времени<= - отношение нестрогого линейного порядка на Nкси : N x AP -> {true,false} - оценка атомарных высказываний на времениДа, являются равносильными, обе утверждают “В какой-то момент времени в будущембудет верно p”______________________________________________________________________________Задача 5 (2 балла).Какова формулировка теоремы корректности табличного вывода для классическойлогики предикатов? Корректно ли правило табличного вывода?〈Γ, ∀xϕ(x) | ∆〉/ 〈Γ | ∃x¬ϕ(x), ∆〉Теорема корректности: если семантическая таблица имеет успешный табличныйвывод, то она невыполнима.Корректно.d∀x φ (x) ≡ ~(∃x ~φ(x)) => можно перекинуть.Задача 6 (2 балла).Т.

Мальцева. Произвольное множество формул обладает моделью тогда и толькотогда, когда каждое конечное подмножество обладает моделью.ИлиЕсли Г|=φ, то существует конечное подмножество Г, называемое Г’, такое что Г’|=φ.Теорема Эрбрана. Система дизъюнктов S = {D1;...;Dт} противоречива тогда и толькотогда, когда существует конечное противоречивое множество G0 основных примеровдизъюнктов S.Да, следует.Задача 7 (2 балла).Какой ответ на запрос G к хорновской логической программе P называетсяправильным? Сколько правильных ответов может иметь запрос G =?A,обращенный к хорновской логической программе P, в том случае, если A основнойатом?Если P - программа, а G - запрос, и Theta (некая подстановка) - ответ, то Theta правильный ответ, еслиP |= \/Z1 … \/Zn GTheta, где Z1,...Zn - переменные Thetaправильный ответ = ответ, логически следующий из программыосновной атом - не содержит переменных => запрос не содержит целевых переменных =>1. либо единственный ответ на него есть пустая подстановка (если атом являетсялогическим следствием программы)2.

либо нет правильных ответов (в противном случае)=> правильных ответов может быть 0 либо 1.Задача 8 (2 балла).Что означает алгоритмическая универсальность хорновского логическогопрограммирования? Верно ли, что для любой логической программы соператорами отсечения и отрицания существует такая хорновская логическаяпрограмма (без отсечений и отрицаний), которая вычисляетточно такое же множество ответов?Значит, что класс функций, вычислимых с помощью программ ХЛП, в точности совпадаетс классом фуОчевидный ответ - нет, то что выдает программа с отсечениями - подмножествопрограммы без отсечений.

Тут не очевидно, ведь спрашивается не про ту же самуюпрограмму, но с убранными отсечениями, а про некую другую программу. Но мнекажется, что всё-таки ответ “нет”, ибо иначе не пришлось бы выдумывать операторыотсечения и not.нкций, вычислимых на машине тьюринга.Задача 9 (2 балла).Как определяется отношение выполнимости I, w |= □ϕ в модальной логике?Верно ли, что для любой модели Крипке I и для любого состояния w если I,w |= □¬p, то I, w |= ♦p ?I,w |= фи <=> для любого w’ : если (w,w’) принадлежит R , то I,w’ |= фиВерно потому что:I,w |=/= -p <=> I,w |= - -p <=> I,w |= ромбик p______________________________________________________________________________Задача 5(2 балла)Какова формулировка теоремы полноты табличного вывода для классическойлогики предикатов? Что можно сказать о выполнимости формулы , еслиизвестно, что обе семантические таблицы <{ }| 0}> и <0 | { }> не имеют успешноготабличного вывода?Ответ 5:Для любой невыполнимой семантической таблицы существует успешный табличныйвывод.Она не общезначима и ее отрицание так же не общезначимо (<fi,> == <,~fi>) => онавыполнима.Задача 6(2 балла)Сформулируйте определение эрбрановской интерпретации заданной сигнатуры .Сколько имеется различных интерпретаций сигнатуры , в которой Const = {c1, c2},Func = 0, Pred = {P^(2)}Ответ 6:Для сигнатуры c=<Const,Func,Pred> эрбановской интерпретацией называется I=(Hi,Const,Func, Pred)где Hi - эрбрановский универсумConst (c) = cFunc (f(n))=f: f(t1,...tn) = f(n)(t1..tn)Pred - задаются произвольноОтвет в 6й - 16 (2^4) потому что двухместный предикат P можно записать как P(c1,c1)P(c2,c2)P(c2,c1),P(c1,c2) и перебрать все возможные значения: каждый вариант можетбыть 0 и 1 - соотв 16 наборов из 0и1 длины 4.

Надеюсь так всем понятно??)))Задача 7.(2 балла)Сформулируйте определение SLD-резолютивного вычисления заданного запросаG, обращенного к хорновской логического программе Р. Существуют ли такиехорновские логические программы, которые не имеют ни одного успешного SLDрезолютивного вычисления ни для каких запросов?Ответ 7:SLD-резолютивным вычислением называется последовательность троек<Dj1,Theta1,G1>...<Djn,Thetan,Gn>...где1. Theta i принадлежит Subst, Dji принадлежит P, Gi - целевое утверждение2. Gi - SLD резольвента утв Dji и Gi-1 c унификатором Theta iЗадача 8.(2 балла)Сформулируйте теорему сильной полноты для хорновских логических программ?Сохраняет ли эта теорема справедливость для логических программ, содержащихоператор not?Ответ 8:Для любой функции выбора подцели вычислимый ответ совпадает с правильным сточностью до подстановки. Любой правильный ответ является частным случаем какого-тоиз вычисленных.R(X)<-R(X) - бесконечнаяЗадача 9.(2 балла)Как в интуиционистской логике определяется отношение выполнимости I,w |=для импликативной формулы? Укажите, какие из формулиявляются общезначимыми формулами интуиционистской логики?Ответ 9:I,w |= fi -> psi <=> для любого w`, если (w,w`) принадлежит R и I,w’ |=/=fi, то I,w’ |= psip-> p - общезначимая________________________________________________________Задача 5 (2 балла).Сформулируйте теорему компактности Мальцева.