Задачи с ответами (2012), страница 5

чисел имеют хотя бы 2 различныепредельные точки”.“сумма любых двух расходящихся последовательностей действ. чисел являетсясходящейся последовательностью действ. чисел ”.“Всякая неограниченная последовательностей действ. чисел не имеет предела”.S(y) & ∃ m (R(m) & M(m, y)) - существует предел последовательности.∃ M (R(M) & ∀ n (N(n) & ∃ x (R(x) & E(x, n, y) & (|x| < M)))) - последовательность ограниченавещественным числом(S(y3) & ∀ n (N(n) ∃ x1 ∃ x2 ∃ x3 (E(x1, n, y1) & E(x2, n, y2) & E(x3, n, y3) & (x3 = x1 + x2))))- суммой числовых последовательностей (xn) и (yn) называется числоваяпоследовательность (zn) такая, что zn = xn + yn. (википедия)вот и всё что нужно._____________________________________________________________Задача 5.Что называется успешным табличным выводом для семантической таблицы T=<Г,>? Всякая ли невыполнимая семантическая таблица имеет успешный табличныйвывод?Успешный вывод - дерево конечно, все листья - закрытые таблицы.Да, по теореме о полноте табличного вывода.Задача 5.Сформулируйте теорему Левенгейма-Сколема.

Следует ли из этой теоремыутверждение: "Если любая интерпретация предметной областью которой являетсямножество всех рациональных чисел является моделью для предложения , тоформула общезначима"Теорема: формула выполнима тогда и только тогда, когда она имеет модель с конечнойили счетно- бесконечной предметной областью._____________________________________________________________Задача 6.Сформулируйте теорему корректности для резолютивного вывода из множествадизъюнктов. Верно ли, что если хотя бы одна эрбрановская интерпретация неявляется моделью для множества дизъюнктов S, то из S резолютивно выводимпустой дизъюнкт?Если из системы дизъюнктов резолютивно выводим пустой дизъюнкт, то эта системапротиворечива.Задача 6Какая подстановка называется композицией подстановок? Какаяподстановка образуется в результате слудующей композиции {x/y}{y/z}{z/u}{u/x}?____________________________________________________________Задача 7Что называют 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иЗадача 9.Как определяется отношение выполнимости I, s0 I |= FPLTL? Является ли формулы 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, логическим следствием которой являются обе формулыϕ и ψ, потому что...2.Существует формула X, являющаяся логическим следствием обеих формул ϕ и ψ,потому что...3.Не существует ни одного успешного табличного вывода из семантическойтаблицы <{ϕ}, {ψ}>, потому что...4.Все приведенные выше утверждения верны.4____________________________________________________________________________Задача 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, то подстановка2.Еслиявляется правильным ответом на запрос G к программе P, потому что...- не является вычисленным ответом на запрос G, обращенный к программе P1,то подстановкапотому что...3.Если подстановкане является правильным ответом на запрос G к программе P,является вычисленным ответом на запрос 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, потому что...3.Если подстановка является правильным ответом на запрос G, обращенный кпрограмме P0, но не является правильным ответом на запрос G, обращенный кпрограмме P1, то запрос G , обращенный к программе P2, имеет успешное вычисление,потому что...4.