Матлогика - задачи с примечаниями (1162128), страница 2

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

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

Как в интуиционистской логике определяется отношение выполнимости I,w |= для импликативной формулы? Укажите, какие из формул и являются общезначимыми формулами интуиционистской логики?

Ответ 9:

I,w |= fi -> psi <=> для любого w`, если (w,w`) принадлежит R и I,w’ |=fi, то I,w’ |= psi

p-> p - общезначимая

________________________________________________________

Задача 5 (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 уже были истинными, не обязательно одновременно.

И что? Результат станет true только после того, как они станут одновременно истинными, благодаря центральному &

________________________________________________________

Задача 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)) от того, какая именно стратегия вычисления применяется?Ïðèâåäèòå ïðèìåð çàìêíóòîé ôîðìóëû ', êîòîðàÿ íå ÿâëÿåòñÿ ëîãè÷åñêèì ñëåäñòâèåì ìíîæåcòâà

çàìêíóòûõ ôîðìóë = {9xP(x), 8x¬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)

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

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