Матлогика - задачи с примечаниями (1162128), страница 5
Текст из файла (страница 5)
Что называют SLD-резольтвентой целевого утверждения G и программного утверждения D? Возможен ли случай, когда SLD-резольвентой целевого утверждения G и программного утверждения D оказывается тот же самый запрос G?
Да, возможен
___________________________________________________________
Задача 8.
Что называется стратегией вычисления логических программ? Какая стратегия вычисления логических программ считается стандартной?
Стратегией вычисления называется порядок построения дерева резолютивных вычислений. Стандартная стратегия: обход в глубину с возвратом
___________________________________________________________
Задача 9
Как определяется отношение выполнимости I,s |= 
для формулы в состоянии s интуиционистской интерпретации I? Верно ли, что всякая формула, являющаяся общезначимой в интуиционистской логике, также является общезначимой в классической логике?
Нет, неверно (наоборот же, верно).
Задача 9
Какая формула называется слабейшим предусловием для заданной программы 
и заданного постусловия 
Каково слабейшее предусловия для программы
if x>1 then x <= x-2 else x<=x+2
Слабейшее предусловие - то, при котором любой результат программы будет удовлетворять постусловию.
wpr(...) = x > 1 & wpr(x - 2,
Задача 9.
Как определяется отношение выполнимости I, s0 I |= F
и темпоральной логики PLTL? Является ли формулы F(
) и F
& F
равносильными?
_____________________________________________________
Задача 10
Множество замкнутых формул Г не имеет модели. Какое из приведенных ниже утверждений справедливы и почему
1.Существует успешный табличный вывод для исходной таблицы T=<0, Г>, потому что...
2.Существует успешный табличный вывод для исходной таблицы T=<Г, 0>, потому что...
3. Не существует успешного табличного вывод для исходной таблицы T=<0, Г>, потому что...
4. Не существует успешного табличного вывод для исходной таблицы T=<Г, 0>, потому что...
5.Ни одно из приведенных ниже утверждений не является верным
2 - таблица невыполнима => существует успешный вывод
Задача 10
Известно, что для семантической таблицы Т=<{ϕ}, {ψ}> нельзя построить ни одного успешного табличного вывода. Какие из приведенных ниже утверждений всегда верны для любых замкнутых формул ϕ и ψ.
1.Таблица Т=<{ϕ}, {ψ}> не является выполнимой, потому что...
2.Для таблицы Т’=<{ψ}, {ϕ}> также не существует ни одного успешного вывода, потому что...
3.Формула ϕ не является логическим следствием формулы ψ, потому что
4.Формула ψ не является логическим следствием формулы ϕ, потому что...
5.Все приведенные выше утверждения в общем случае неверны, потому что...
//Ответ 4. Надо норм обосновать, тк ϕ->ψ не катит, инфа 100%.
Отсутствие вывода = таблица выполнима. => есть интерпретация, где выполнена фи и не выполнена пси. => пси не является следствием фи.
Задача 10
Известно, что выполнимые замкнутые формулы ϕ и ψ не имеют ни одной общей модели. Какие из приведенных ниже утверждений всегда верны и почему?
1.Существует формула X, логическим следствием которой являются обе формулы ϕ и ψ, потому что… false подходит
2.Существует формула X, являющаяся логическим следствием обеих формул ϕ и ψ, потому что… как ни странно, true является логическим следствием любых
3.Не существует ни одного успешного табличного вывода из семантической таблицы <{ϕ}, {ψ}>, потому что...
4.Все приведенные выше утверждения верны.
4?
____________________________________________________________________________
3.Если подстановка 
является правильным ответом на запрос G, обращенный к программе P0, но не является правильным ответом на запрос G, обращенный к программе P1, то запрос G , обращенный к программе P2, имеет успешноЗадача 11(3 балла)
Предположим, что S - некоторые противоречивое множество хорновских дизъюнктов. Какие из приведенных ниже утверждений всегда справедливы и почему?
1.В множестве S есть дизъюнкт, состоящий только из одного атома, потому что...
2.В множестве S есть дизъюнкт, состоящий только из положительных литер, потому что...
3.В множестве S есть дизъюнкт, состоящий только из отрицательных литер, потому что...
4.Противоречивых множеств хорновских дизъюнктов не существует, потому что...
5.Все приведенные выше утверждения всегда верны
По-моему верно 1,2,3 - потому что пустой дизъюнкт может получиться только как резольвента двух атомов, один из которых положительный, другой отрицательный.
Задача 11(3 балла)
Пусть А(Х) - атом, Р - хорновская логическая программа, I - эрбрановская модель для логической программы Р. Какие из приведенных ниже утверждений всегда справедливы и почему?
1.Если I |= ∃Х А(Х), то запрос ?А(Х), обращенный к программе Р, имеет хотя бы одно успешное вычисление, потому что...
2.Если все вычисления запроса ?А(Х), обращенного к программе Р, являеются успешными, то I |= ∀Х А(Х), потому что
3.Если хотя бы одно вычисление запроста ? А(Х), обращенного к программе Р, является успешным, то I |= ∃Х А(Х), потому что
4.Если I |= ∀Х А(Х), , то все вычисления запроса ?А(Х), обращенного к программе Р, являются успешными, потому что ...
Задача 11
Известно, что из множества непустых дизъюнктов S={D1, ..., Dn} можно построить резолютивный вывод пустого дизъюнкта □. Какие из приведенных ниже утверждений справедливы и почему?
1.Семантическая таблица T=<0 | {D1 & D2 & ... Dn}> имеет успешный табличный вывод, потому что...
2.Семантическая таблица T=<0 | {D1 & D2 & ... Dn}> не имеет успешного табличного вывода, потому что...
3.Семантическая таблица T=<{D1 & D2 & ... Dn} | 0> имеет успешный табличный выв
од, потому что...
4.Семантическая таблица T=<{D1 & D2 & ... Dn} | 0> не имеет успешного табличного вывода, потому что...
5.Ни одно из приведенных утверждений в общем случае неверно.
_____________________________________________________________________
Задача 12(3 балла)
Пусть G - запрос к хорновской логической программе P и 
и 
- некоторые подстановки. Какие из приведенных ниже утверждений будут при этом всегда верны и почему?
1.Если и - вычисленные ответы на запрос G к программе P, то подстановка 
является правильным ответом на запрос G к программе P, потому что...
2.Если - не является вычисленным ответом на запрос G, обращенный к программе P1, то подстановка не является правильным ответом на запрос G к программе P, потому что...
3.Если подстановка является вычисленным ответом на запрос G, а подстановка не является вычисленным ответом на запрос G к программе P, то подстановка не является правильным ответом на запрос G к программе P, потому что
4.Все приведенные выше утверждения, вообще говоря, неверны, потому что...
Задача 12
Пусть известно, что обе системы дизъюнктов S1 и S2 непротиворечивы. Какие из приведенных ниже утверждений верны и почему?
1.Обе системы дизъюнктов S1
S2 и S1 
S2 также непротиворечивы, потому что...
2.Система S1 S2 обязательно будет непротиворечивой, а система дизъюнктов S1 S2 может оказаться противоречивой, потому что (наверное, оно)
3.Система S1 S2 обязательно будет непротиворечивой, а система дизъюнктов S1 S2 может оказаться противоречивой, потому что...
4. Обе системы дизъюнктов S1 S2 и S1 S2 могут оказаться противоречивыми, потому что...
Пересечение множеств непротиворечиво, потому что подмножество непротиворечивого множества непротиворечиво. Так что скорее всего действительно 2.
Задача 12
Пусть P0, P1 и P2 - три хорновские логические программы и при этом P0 = P1 P2. Пусть - некоторый ответ на запрос G. Какие из приведенных ниже утверждений и почему?
1.Если подстановка является правильным ответом на запрос G, обращенный к программе P0, то либо является правильным ответом на запрос G, обращенный к программе P1, либо является правильным ответом на запрос G, обращенный к программе P2, потому что…
2.Если подстановка является правильным ответом на запрос G, обращенный к программе P0, то является правильным ответом на запрос G, обращенный к программе P1, так и к программе P2, потому что...
е вычисление, потому что...
4. Ни одно из приведенных выше утверждений в общем случае не является верным, потому что...
_____________________________________________________________________
Задача 13(3 балла)
К каким задачам из теории графов сводится решение задачи model checking для темпоральной логики PLTL?
1.К задаче проверки ацикличности ориентированных графов
2.К задаче проверки раскраски ориентированных графов
3.К задаче выделения компонет сильной связности в ориентированных графах
4.К задаче проверки достижимости заданного подграфа из заданной вершины в ориентированных графах
5.К задаче выделения в графе максимального полного подкрафа(клики)
6.К задаче проверки изоморфизма ориентированных графов
Кажется, так, потому что мы ищем бесконечный радужный маршрут в графе: компоненту сильной связности с вершинами всех цветов + достижимость этой компоненты из нужной вершины. //По-моему 2 ещё.
Задача 13(3 балла)
Из логической программы P(содержащей операторы отсечения и отрицания) с запросом G были удалены все операторы отсечения, в результате чего образовалась новая программа P'. Какие из приведенных ниже утверждений будут всегда верны и почему?
1. Всякое успешное вычисление запроса G к программе P будет также являться успешным вычислением запроса G к программе P', потому что...
2. Всякое успешное вычисление запроса G к программе P' будет также являться успешным вычислением запроса G к программе P, потому что...
3. Всякий вычислимый ответ на запрос G к программе P будет также являться вычислимым ответом на запрос 4к пгрограмме P', потому что...
4. Всякий вычислимый ответ на запрос G к программе P’ будет также являться вычислимым ответом на запрос G к пгрограмме P, потому что...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
