Подготовка к экзамену (1158071), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

(имхо: почему нет, просто они все справа, но моё мнение не в счёт)

(невыполнимая впринципе формула только одна - тождественно ложный диъюнкт (а также все формулы, равносильные ему, пример: any x (P(x) & !P(x))). Ставим слева пустое множество, справа - тлд, всё пучком)

___________________________________________________________

Задача 6 (2 балла).

Какие формулы логики предикатов называются равносильными? Докажите, что два предложения ϕ и ψ являются равносильными тогда и только тогда, когда множество логических следствий формулы ϕ совпадает с множеством логических следствий формулы ψ?

Равносильными называются формулы фи и пси, для которых общезначима формула (фи -> пси)&(пси -> фи) - эту формулу ещё называют отношением эквиваленции.

Доказательство очевидно глядя на формулу. (“=>” очевидно, а обратно - не особо)

Думаю написать что оно следует из теоремы о логическом следствии будет достаточно.

____________________________________________________________

Задача 7 (2 балла).

Какой ответ на запрос G к хорновской логической программе P называется вычисленным? Существуют ли такие правильные ответы на запрос G к хорновской логической программе P, которые не могут быть вычислены?

Если последовательность SLD резолюции конечна и завершается квадратиком, то конкатенация Theta i ограниченная Y₁...Y_n является вычислимым ответом.

Не существуют с точностью до подстановки, по теореме полноты.

____________________________________________________________

Задача 8 (2 балла).

Что такое допущение замкнутости мира?

Верно ли, что ϕ ∨ ψ |=CWA ¬ϕ?

CWA: Это когда из того что

Г |=/= fi => Г |_cwa= -fi

Хрен знает, я бы сказал что “да”, я тоже.

Я бы сказал, что “нет”. Если взять фи и пси одинаковыми, то получим, что из ϕ ∨ ψ выводится фи.

____________________________________________________________

Задача 9 (2 балла).

Как определяется отношение выполнимости I, s₀ |= ϕUψ в темпоральной логике PLTL? Являются ли формулы ϕU(ψ₁ &ψ₂) и (ϕUψ₁ & ϕUψ₂) равносильными?

I, s₀ |= ϕUψ

значит, что cуществует K>=0 : верно I, s_k |=ψ и для любого 0<=i<k верно I, s_i |=ф

Кажись верны, хотя в лекция предлагается вывести формулы самим.

Не являются равносильными, ϕ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-дерева => не все вычисления успешны (?)

________________________________________________________________

Задача 8 (2 балла).

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

См.выше.

__________________________________________________________________

Задача 9 (2 балла).

Как определяется отношение выполнимости I, s₀ |= Fψ в темпоральной логике

PLTL? Являются ли формулы F(ψ₁ &ψ₂ ) и Fψ₁ & Fψ₂ равносильными?

Существует такая K>=0, что I,s_k |= ψ

Являются. Не являются, вспомним определение: “Future: φ должно стать истинным хотя бы в одном состоянии в будущем.” - первая формула, в отличие от второй, требует одновременности истинности ψ₁ и ψ₂.

______________________________________________________________________

Задача 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, которые не могут быть вычислены?

Определение вычисленного ответа

Пусть

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 общезначимой в интуиционистской логике высказываний?

Характеристики

Список файлов ответов (шпаргалок)