Условия и некоторые решения задач (1158137), страница 2

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

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

___________________________________________________________

Задача 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)

Составляем систему уравнений:

t1 = s1

t2 =

…

tn = sn

Применяем 6 правил. Решение очень похоже на решение обычных систем уравнения. В общем делает то, что кажется правильным, 6 правил запоминать наизусть, на мой взгляд, нет смысла.

___________________________________________________________

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

Что называется деревом SLD-резолютивных вычислений запроса G, обращённого к хорновской логической программе P? Зависит ли устройство дерева SLD-резолютивных вычислений от правила выбора подцелей?

Фафа ляля.

Зависит. Или не зависит (аргументация ниже)

Хотя... Деревья, в которых подцели выбирались разным образом, будут равными с точностью до порядка подветвей в каждой точке ветвления, так как всё равно будут посещены все ветви. То есть если расматривать деревья как графы - то они равны и ответ “Не зависит”. “Устройство дерева” - не очень точное понятие, и непонятно по какому критерию эти “устройства деревьев” сравнивать.

Зависит же, выбрав одно правило можем уйти в бесконечность, сразу, а можем выбрать его позже, и потом уйти в бесконечность, и полученные деревья будут разные. хм?

//Речь не о порядке применения правил, а о порядке выбора подцелей. Есть теорема => не зависит. Хотя, как отмечено выше, деревья всё-таки одинаковы лишь с точностью до порядка расположения ветвей.

___________________________________________________________

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

Как определяется отношение выполнимости I,t |= в темпоральной логике PLTL? Верно ли, что формулы являются равносильными формулами логики PLTL?

______________________________________________________________________________

Задача 10. Известно, что некоторая модель для формулы φ не является моделью для формулы ψ. Какие из приведенных ниже утверждений всегда верны для любых замкнутых формул φ и ψ?

1. Не существует успешного табличного вывода из таблицы T' = <{ψ}, {φ}>, потому что…

2. Не существует успешного табличного вывода из таблицы T = <{φ}, {ψ}>, потому что… (По условию существует интерпретация, в которой формулы φ верны, а ψ - не верны. Следовательно, в этой интерпретации не существует успешного табличного вывода из таблицы T = <{φ}, {ψ}, так как она является выполнимой)

3. Формула φ является логическим следствием формулы ψ, потому что…

4. Формула ψ является логическим следствием формулы φ, потому что…

5. Все приведенных выше утверждения в общем случае неверны, потому что…

Задача 11. Пусть задано некоторое непустое множество дизъюнктов S0. Пусть S1 – это множество всех формул, резолютивно выводимых из множества дизъюнктов S0. Какие из приведенных ниже утверждений всегда справедливы и почему?

1. Если каждый дизъюнкт множества S0 выполним, то и каждый дизъюнкт множества S1 выполним, потому что…

2. Если каждый дизъюнкт множества S1 выполним, то множество дизъюнктов S0 имеет модель, потому что… из s1 не вывели пустой диз -> s0 имеет модель

3. Если множество дизъюнктов S0 имеет модель, то множество дизъюнктов S1 имеет модель, потому что… так как s0->s1

4. Все приведенные выше утверждения всегда верны, потому что…

Задача 12. Пусть Р – это хорновская логическая программа, а S – это множество всех дизъюнктов, соответствующих программным утверждениям программы Р. Известно, что для наименьшей эрбрановской модели МР программы Р выполняется соотношение МР = ø. Какие из приведенных ниже утверждений будут при этом всегда верны и почему?

1. Система дизъюнктов S выполняется в каждой эрбрановской интерпретации, потому что…

2. Из системы дизъюнктов S нельзя вывести ни одной резольвенты, потому что…

3. Система дизъюнктов S является противоречивой, потому что…

4. В каждом дизъюнкте из системы S есть хотя бы один атом со связкой отрицания ¬, потому что… (в этой программе нет фактов, так как если в ней есть хотя бы одитн факт, то мэм !=0 -> a0<-a1,…,an переходит в а0 или не а1 или … не аn)

5. Все приведенные выше утверждения всегда неверны, потому что…

Задача 13. Какие из приведенных ниже утверждений справедливы и почему?

1. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей хорновской логической программой с использованием стандартной стратегии вычисления, потому что…

2. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей логической программой, но лишь с использованием нестандартной стратегии вычисления, потому что…

3. Любая арифметическая функция, вычислимая на машине Тьюринга, может быть вычислена подходящей логической программой с использованием стандартной стратегии вычисления, но лишь при добавлении операторов is и not, потому что…

4. Существует арифметическая функция, вычислимая на машине Тьюринга, для вычисления которой нет логической программы даже в случае использования операторов is и not, потому что…

1 верно, потому что хорновские программы могут моделировать машины Тьюринга (теорема Чёрча - для любой программы на машине Тьюринга существует соответствующая хорновская программа) остальные неверны, потому что противоречат 1му. Но вообще-то объяснений неверным пунктам можно и не давать (алгоритимческая универсальность хорновского логического программирования)

Задача 14. Пусть Г – некоторое множество замкнутых формул логики предикатов. Верно ли, что Г является непротиворечивым множеством тогда и только тогда, когда всякая дизъюнкция вида фи1 V фи2 V... V фиN, где фиi Г не является общезначимой?

1. Верно, потому что…

2. Неверно, потому что…

3. Зависит от множества Г, доказательством тому являются 2 примера…

6, Потому что

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

Список файлов вопросов/заданий