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

Что такое допущение замкнутости мира? Верно ли, что ϕ ∨ ψ |=CW A ¬ϕ?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 |=фКажись верны, хотя в лекция предлагается вывести формулы самим.________________________________________________________Задача 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 - дерева.Зависит - правильность ответа неизвестна.

если вам попадётся этот вопрос, вы неудачник! гы!____________________________________________________________Задача 9 (2 балла). Как определяется частичная корректность программы πотносительно предусловия ϕ и постусловия ψ в интерпретации I?Является ли программа while X > 0 do X + + od частично корректной относительнопредусловия ϕ = (X > 0) и постусловия ψ = (X < 0) в стандартной интерпретацииI |= ф{pi} psiКажись корректно.____________________________________________________________Задача 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, является успешным?Класс задач ХЛП в точности совпадает с классом задач машины тьюринга.________________________________________________________________Задача 8 (2 балла).

Какова формулировка теоремы Черча о проблемеобщезначимости в классической логике предикатов? Существует ли алгоритм,проверяющий противоречивость конечных множеств замкнутых формул логикипредикатов?См.выше.__________________________________________________________________Задача 9 (2 балла).

Как определяется отношение выполнимости I, s0 |= Fψ втемпоральной логикеPLTL? Являются ли формулы F(ψ1 &ψ2 ) и Fψ1 & Fψ2 равносильными?Существует такая K>=0, что I,sk |= ψЯвляются______________________________________________________________________Задача 5 (2 балла). Какова формулировка теоремы корректности табличноговывода для классической логики предикатов? Корректно ли правило табличноговывода?〈Γ, ∀xϕ(x) | ∆〉〈Γ | ∃x¬ϕ(x), ∆〉См выше________________________________________________________________Задача 6 (2 балла).

Как формулируется теорема компактности Мальцева? Следуетли из теоремы компактности теорема Эрбрана?См.выше______________________________________________________________Задача 7 (2 балла). Какой ответ на запрос G к хорновской логической программе Pназывается правильным? Сколько правильных ответов может иметь запрос G =?A,обращенный к хорновской логической программе P, в том случае, если A основнойатом?См.выше__________________________________________________________________Задача 8 (2 балла). Что означает алгоритмическая универсальность хорновскогологического программирования? Верно ли, что для любой логической программыс операторами отсечения и отрицания существует такая хорновская логическаяпрограмма (без отсечений и отрицаний), которая вычисляетточно такое же множество ответов?См.

выше_____________________________________________________________________Задача 9 (2 балла). Как определяется отношение выполнимости I, w |= □ϕ вмодальной логике?Верно ли, что для любой модели Крипке I и для любого состояния w если I, w |=□¬p, то I, w |= ♦p ?См.выше_________________________________________________________________________Задача 5 (2 балла).

Сформулируйте теорему компактности Мальцева. Следует ли изэтой теоремыутверждение: Если бесконечное множество предложений Γ не имеет модели, тохотя бы одно предложениемножества Γ является противоречивым ?____________________________________________________________________________Задача 6 (2 балла). Какие формулы логики предикатов называютсяравносильными? Докажите,что два предложения ϕ и ψ являются равносильными тогда и только тогда, когдамножество логическихследствий формулы ϕ совпадает с множеством логических следствий формулы ψ?_____________________________________________________________________________Задача 7 (2 балла). Какой ответ на запрос G к хорновской логической программе Pназываетсявычисленным? Существуют ли такие правильные ответы на запрос G к хорновскойлогической программеP, которые не могут быть вычислены?__________________________________________________________________________Задача 8 (2 балла).

Что такое допущение замкнутости мира? Верно ли, что ϕ ∨ ψ |=CW A ¬ϕ?___________________________________________________________________________Задача 9 (2 балла). Как определяется отношение выполнимости I, s0 |= ϕUψ втемпоральнойлогике PLTL? Являются ли формулы ϕU(ψ1 &ψ2 ) и ϕUψ1 & ϕUψ2 равносильными?____________________________________________________________________________Задача 6 (2 балла). Какая интерпретация называется эрбрановской интерпретациейдля заданнойсигнатуры σ? Сколько существует различных эрбрановских интерпретаций всигнатуре σ, состоящейтолько из одного одноместного предикатного символа P и из одной предметнойконстанты c ?_______________________________________________________________________Задача 7 (2 балла).

Сформулируйте теорему об основном правильном ответе назапрос к хорновской логической программе. Верно ли, что если запрос G(x) к хорновскойлогической программе имеетхотя бы одно успешное вычисление, то этот запрос имеет хотя бы один основнойправильный ответ?_____________________________________________________________________Задача 8 (2 балла). Что называется стратегией вычисления логических программ?Зависит лиответ на запрос G =? not(P (x)) от того, какая именно стратегия вычисленияприменяется?___________________________________________________________________________Задача 9 (2 балла).

Как определяется частичная корректность программы πотносительно предусловия ϕ и постусловия ψ в интерпретации I?Является ли программа while X > 0 do X + + od частично корректной относительнопредусловияϕ = (X > 0) и постусловия ψ = (X < 0) в стандартной интерпретации арифметикицелых чисел?___________________________________________________________________________Задача 6 (2 балла). Что называется эрбрановским универсумом заданнойсигнатуры σ? Сколько различных элементов содержит эрбрановский универсумсигнатуры σ, состоящей из одного одномест-ного предикатного символа P , одногоодноместного функционального символа f и из одной предметнойконстанты c ?_______________________________________________________________Задача 7 (2 балла). Приведите определение SLD-резольвенты запроса G ипрограммного утвер-ждения D.

Выпишите все SLD-резольвенты запроса ? P (X, c), P(c, f (X)) и программного утверждения P (X, X) ← R(X)._________________________________________________________________Задача 8 (2 балла). Что называется стратегией вычисления логических программ?Зависит ли ответ на запрос G =? not(P (x)) от того, какая именно стратегиявычисления применяется?____________________________________________________________________Задача 9 (2 балла). Как определяется интерпретация интуиционистской логикивысказываний? Является ли формула p → ¬¬p общезначимой в интуиционистскойлогике высказываний?___________________________________________________________Ответ 5 :Ответ 6:Ответ 7:Ответ 8:Ответ 9:______________________________________________________________________________мож ебанем остальную теорию?даже если каждый напишет один вопрос уже огромный профитвсем впадлу=)можно задачки ещезуб мы тут разобрались с !с чем? оператор отсечениязаходи, расскажизуб ты ботал ? какая же это хуета....надо всем рассказать будетя напишу в ответах на задачу с !чето я хуй че понял...зайди ептатам вопросы в конце в основном повторяются, лишние б поудалять лучшехер бы с ними, лучше тестов добавить...они вроде на дропбоксе же лежали? ну или что это за архив на мылеэто маткибовский - мне ден слил...там далеко не все и пояснения кое-где с говнецомесли это не всё, тогда что ж за жопа там будет...можно взять пару вариантов полностью так выложить и прорешать...кто за? только поприватнее бы, ато больно срача многохз, если будет кто-то решать, способных не так много, как кажется ._.хуйня, с лекциями и инетом любой имбицилл справитсяну чего? полетели?лучше тестов добавить...они понажористее будутДОБАВЬТЕ ВОПРОСЫ 10-13.