Задачи с ответами (2012) (1158171), страница 2
Текст из файла (страница 2)
Следует ли из этой теоремыутверждение: Если бесконечное множество предложений Γ не имеет модели, тохотя бы одно предложение множества Γ является противоречивым ?Два варианта (хз, эквивалентны они, или это две разные теоремы):● Г |= fi <=> exsist конечное подмножество Г’ in Г: Г’ |= fi.● Если Г - противоречиво, то существует конечное под-во котороепротиворечиво.Да нифига... Не следует. То что существует конечная система, не значит что эта системаразмерности 1.___________________________________________________________Задача 5 (2 балла).Какая семантическая таблица T = 〈Γ, ∆〉 называется выполнимой? Может ливыполнимая таблица содержать только невыполнимые формулы?Ответ: семантическая таблица T = 〈Γ, ∆〉 называется выполнимой,если существует такая интерпретация I и такой наборзначенийЕсли Γ=ϕ => то может.Может ли выполнимая таблица содержать только невыполнимые формулы? <<<=Пример : <0|false>(имхо: почему нет, просто они все справа, но моё мнение не в счёт)(невыполнимая впринципе формула только одна - тождественно ложный диъюнкт (а также все формулы, равносильныеему, пример: any x (P(x) & !P(x))).
Ставим слева пустое множество, справа - тлд, всё пучком)___________________________________________________________Задача 6 (2 балла).Какие формулы логики предикатов называются равносильными? Докажите, чтодва предложения ϕ и ψ являются равносильными тогда и только тогда, когдамножество логических следствий формулы ϕ совпадает с множеством логическихследствий формулы ψ?Равносильными называются формулы фи и пси, для которых общезначима формула(фи -> пси)&(пси -> фи) - эту формулу ещё называют отношением эквиваленции.Доказательство очевидно глядя на формулу.
(“=>” очевидно, а обратно - не особо)Думаю написать что оно следует из теоремы о логическом следствии будетдостаточно.____________________________________________________________Задача 7 (2 балла).Какой ответ на запрос G к хорновской логической программе P называетсявычисленным? Существуют ли такие правильные ответы на запрос G к хорновскойлогической программе P, которые не могут быть вычислены?Если последовательность SLD резолюции конечна и завершается квадратиком, токонкатенация Theta i ограниченная Y1...Yn является вычислимым ответом.Не существуют с точностью до подстановки, по теореме полноты.____________________________________________________________Задача 8 (2 балла).Что такое допущение замкнутости мира?Верно ли, что ϕ ∨ ψ |=CWA ¬ϕ?CWA: Это когда из того чтоГ |=/= fi => Г |cwa= -fiХрен знает, я бы сказал что “да”, я тоже.Я бы сказал, что “нет”.
Если взять фи и пси одинаковыми, то получим, что из ϕ ∨ ψвыводится фи.____________________________________________________________Задача 9 (2 балла).Как определяется отношение выполнимости I, s0 |= ϕUψ в темпоральной логикеPLTL? Являются ли формулы ϕU(ψ1 &ψ2) и (ϕUψ1 & ϕUψ2) равносильными?I, s0 |= ϕUψзначит, что cуществует K>=0 : верно I, sk |=ψ и для любого 0<=i<k верно I, si |=фКажись верны, хотя в лекция предлагается вывести формулы самим.Не являются равносильными, ϕU(ψ1 &ψ2 ) говорит, что фи будет истинно до тех пор,пока не станут истинными пси1 и пси2 одновременно.
Вторая формула говорит, чтофи истинно, до тех пор, пока не окажется что и пси1 и пси2 уже были истинными, необязательно одновременно.________________________________________________________Задача 6 (2 балла).Какая интерпретация называется эрбрановской интерпретацией для заданнойсигнатуры σ? Сколько существует различных эрбрановских интерпретаций всигнатуре σ, состоящейтолько из одного одноместного предикатного символа P и из одной предметнойконстанты c ?Смотри выше.2 интерпретации._________________________________________________________Задача 7 (2 балла).Приведите определение SLD-резолютивного вычисления запроса G, обращенногок хорновской логической программе P. Верно ли, что если P |= ∀xR(x), то запрос G=? R(c), R(f (y)), обращенный к хорновской логической программе P имеет хотя быодно успешное SLD-резолютивное вычисление?Пусть программа P(c)←; и запрос ?G: P(X)<P(c)←,{X/c},square>Верно.___________________________________________________________Задача 8 (2 балла).Что называется стратегией вычисления логических программ? Зависит ли ответ назапрос G =? not(P (x)) от того, какая именно стратегия вычисления применяется?Спосом построения (обхода) SLD - дерева.Зависит - правильность ответа неизвестна.Может оказаться так, что в одной ветви находится решение для P(x), а другая ветвьбесконечна - тогда получается что при одной стратегии обхода получим зависание, придругой - квадратик.(мне всё-таки кажется, что нет, но посмотрим <= из того, что надо обойти всё и всякиетеоремы об остановах, etc)____________________________________________________________Задача 9 (2 балла).Как определяется частичная корректность программы π относительнопредусловия ϕ и постусловия ψ в интерпретации I?Является ли программа while X > 0 do X + + od частично корректной относительнопредусловия ϕ = (X > 0) и постусловия ψ = (X < 0) в стандартной интерпретацииI |= ф{pi} psiКажись корректно.Да, хотя она никогда не завершится.
Если там имелось в виду X--, то тогданекорректно, ибо по завершении будет X=0, а не X<0.____________________________________________________________Задача 6 (2 балла).Какова формулировка теоремы об эрбрановских интерпретациях? Сколькоэрбрановских моделей в сигнатуре σ = 〈Const = {c}, F unc = ∅, P red = {P }〉 имеетформула ϕ = ∃xP (x)&¬P (c)?Система дизъюнктов невыполнима тогда и только тогда, когда она невыполнима нина одной эрбрановской интерпретации.От формулы количество эрбрановских моделей вообще не зависит.
ЗАВИСИТ!!!Эрбрановские модели интерпретации отличаются только толкованием предикатныхсимволов.В данном случае моделей интерпретаций 2 штуки, P(с) принимает значение либоtrue либо false.Существует 2 эрбрановских интерпретации для заданной сигнатуры, но ни одна неявляется моделью данной формулы.Ответ: 0_____________________________________________________________Задача 7 (2 балла).Какова формулировка теоремы полноты операционной семантики хорновскихлогических программ относительно декларативной семантики? Верно ли, что изэтой теоремы полноты следует, что для любого основного атома A, являющегосялогическим следствием программы P, любоевычисление запроса ?A, обращенного к программе P, является успешным?Класс задач ХЛП в точности совпадает с классом задач машины тьюринга.Любой правильный ответ является частным случаем какого-то из вычисленных.Верно, так как есть правильный ответ {} (пустая подстановка), он должен быть частнымслучаем одного из вычисленных => существует вычисленный ответ.
Не уверен, ответможет быть, но не по всем ветвям SLD-дерева => не все вычисления успешны (?)________________________________________________________________Задача 9 (2 балла).Как определяется отношение выполнимости I, s0 |= Fψ в темпоральной логикеPLTL? Являются ли формулы F(ψ1 &ψ2 ) и Fψ1 & Fψ2 равносильными?Существует такая K>=0, что I,sk |= ψЯвляются. Не являются, вспомним определение: “Future: φ должно стать истиннымхотя бы в одном состоянии в будущем.” - первая формула, в отличие от второй,требует одновременности истинности ψ1 и ψ2.__________________________________________________________________Задача 7 (2 балла).Какой ответ на запрос G к хорновской логической программе P называетсявычисленным? Существуют ли такие правильные ответы на запрос G к хорновскойлогической программе P, которые не могут быть вычислены?Определение вычисленного ответаПустьG0 = ? C1, C2, .
. . , Cm - целевое утверждение с целевыми переменными Y1, Y2, . . . , Yk,P = {D1, D2, . . . , DN } — хорновская логическая программа,comp = (Dj1, θ1, G1), (Dj2, θ2, G2), . . . , (Djn , θn, ...) - успешное SLD-резолютивноевычисление, порожденное запросом G к программе P.Тогда подстановка θ = (θ1θ2 .
. . θn)|Y1,Y2,...,Yk,представляющая собой композициювсех вычисленных унификаторов θ1, θ2, . . . , θn, ограниченную целевымипеременными Y1, Y2, . . . , Yk , называется вычисленным ответом на запрос G0 кпрограмме P.Теорема полноты гласит, что каждый правильный ответ — это пример (частный случай)некоторого вычисленного ответа .__________________________________________________________________________Задача 8 (2 балла).Что такое допущение замкнутости мира? Верно ли, что ϕ ∨ ψ |=CWA ¬ϕ?Суть Допущения Замкнутость Мира (CWA) состоит в том,что при извлечении CWAлогических следствий из базы знаний Г (|=cwa) нужно рассматривать не все моделидля Г,а только такую минимальную модель,в которой истинными являются одни лишьклассические следствия (|=) из Г.
Такая минимальная модель существует, вообще говоря,не всегда, например, Г={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 правил.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
