1 (Старые варианты экзамена)

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

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

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

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

Что такое эрбрановский универсум? Каким условиям должнаудовлетворять сигнатура σ длятого, чтобы эрбрановский универсум сигнатуры σ был конечным множеством?H - эрбрановский универсум сигнатуры <Const,Func,Pred> - Это множество H=Uoo1 HiH0=либо 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, если дерево завершилось Успехом-Бесконечность, если дерево бесконечно и не было обнаружено успешных вычислений.Никакого, т.к. программа зациклица (неверно, ответа не будет т.к. нет правила для R(c)).______________________________________________________________________________Задача 9. Как определяется интерпретация темпоральной логики линейноговремени PLTL ? Являются ли равносильными PLTL формулы Fp и (p ∨ ¬p)Up?I=<N,<=,кси>N - {0,1,2...}-моменты времени<= - отношение нестрогого линейного порядка на Nкси : N x AP -> {true,false} - оценка атомарных высказываний на времени______________________________________________________________________________Теорема корректности: если семантическая таблица имеет успешный табличныйвывод, то она невыполнима.Нет, некорректно.

Правила с кванторами вообще не допускают перекидыванияформул с одной стороны на другую.Т. Мальцева. Произвольное множество формул обладает моделью тогда и толькотогда когда каждое конечное подмножество обладает моделью.ИлиЕсли Г|=фи, то существует конечное подмножество Г, называемое Г’, такое что Г’|=фи.Да, следует.Если P - программа, а G - запрос, и Theta - ответ, то Theta - правильный ответ, еслиP |= \/Z1 … \/Zn GTheta, где Z1,...Zn - переменные Thetaправильный ответ = ответ, логически следующий из программы.Значит, что класс функций, вычислимых с помощью программ ХЛП, в точности совпадаетс классом функций, вычислимых на машине тьюринга.Очевидный ответ - нет, то что выдает программа с отсечениями - подмножествопрограммы без отсечений, но возможно както можно и написать, такую которая выдаеттоже...

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

Сформулируйте теорему компактности Мальцева. Следует ли изэтой теоремы утверждение: Если бесконечное множество предложений Γ не имеетмодели, то хотя бы одно предложение множества Γ является противоречивым ?Ответ:Теорема. Г |= fi <=> exsist подмножество Г’ in Г: Г’ |= fi.По альтернативной версии теоремы, существует конечная противоречиваясистема.А че за альтернативная версия?Если не ошибаюсь, то если Г - противоречиво, то существует конечное под-вокоторое противоречиво. На консультации сегодня вроде говорили. Так что, по идееследует.Да нифига... То что существует конечная система, не значит что эта система размерности1.___________________________________________________________Задача 5 (2 балла). Какая семантическая таблица T = 〈Γ, ∆〉 называетсявыполнимой? Может ли выполнимая таблица содержать только невыполнимыеформулы?Ответ: семантическая таблица T = 〈Γ, ∆〉 называется выполнимой,если существует такая интерпретация I и такой наборзначенийМожет ли выполнимая таблица содержать только невыполнимые формулы? <<<=Пример : <0|false>(имхо: почему нет, просто они все справа, но моё мнение не в счёт)(невополнимая впринципе формула только одна - тождественно ложный диъюнкт.

Ставим слева пустое множество,справа - тлд, всё пучком)___________________________________________________________Задача 6 (2 балла). Какие формулы логики предикатов называютсяравносильными? Докажите,что два предложения ϕ и ψ являются равносильными тогда и только тогда, когдамножествологических следствий формулы ϕ совпадает с множеством логических следствийформулы ψ?Равносильными называются формулы фи и пси, для которых общезначима формула(фи -> пси)&(пси -> фи).Доказательство очевидно глядя на формулу.

(не особо)Думаю написать что оно следует из теоремы о логическом следствии будетлостаточно.____________________________________________________________Задача 7 (2 балла). Какой ответ на запрос G к хорновской логической программе Pназывается вычисленным? Существуют ли такие правильные ответы на запрос G кхорновской логической программе P, которые не могут быть вычислены?Если последовательность SLD резолюции конечна и завершается квадратиком, токонкатенация Theta i ограниченная Y1...Yn является вычислимым ответом.Не существуют с точностью до подстановки, по теореме полноты.____________________________________________________________Задача 8 (2 балла).