1 (1158076)
Текст из файла
Задача 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 балла).
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
