задачи с ответами (2012) (1162130), страница 6
Текст из файла (страница 6)
Какие из приведенных нижеутверждений справедливы и почему?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.
Ни одно из приведенных выше утверждений в общем случае не является верным,потому что..._____________________________________________________________________Задача 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 будет также являтьсявычислимым ответом на запрос G к пгрограмме P', потому что...4. Всякий вычислимый ответ на запрос G к программе P’ будет также являтьсявычислимым ответом на запрос G к пгрограмме P, потому что...5.
Ни одно из приведенных выше утверждений в общем случае неверно.1 и 2 точно не верно. 2 - понятно, из-за возможности найти ответ в той частипрограммы, где было отсечение, а 1 - из-за взаимодействия отсечения и not. Про этосам Захаров говорил на апелляции, там может в какой-то ветви not из-за отрицаниянайтись правильный ответ и все перевернется!3 и 4 надо проверить. Но мне кажется, что ответ 5.// на апелляции сказал ответ 5.Задача 13(3 балла)Существует ли такой алгоритм, который получив на входе произвольную формулулогики предикатов, предваренная нормальная форма которой имеет вид∀x1 ∀x2 ...
∀x3 Ф(x1,..xn),где Ф(x1,... xn) - бескванторная матрица,выдает на входе 0, если эта формула общезначима, и 1, если эта форма необщезначима?1.Такого алгоритма не существует, потому что...2.Такой алгоритм существует, и вот его описание...2 - Алгоритм - Табличный вывод.___________________________________________________________вопрос: если бы я сначала L(любое) применил а потом R(любое) так щас на бумажкесоображузначит: применяем L(любое) к T2=> T3= <(), P( t ) v R( y ) | Vx P(x),R(y)>к T3 применяем R(любое) =>T4= <(), P( t ) v R( y ) | P(c),R(y)>т.е у нас разные термы, а на картинке из-за другого порядка выполнения правилT4= <(), P( с1 ) v R( y ) | P(c1),R(y)>ну мля если бы все было детерминировано то на этомбы закончился курс епта.??? не понял//типа надо думать, чтоб не запороться +1ну там думать мало где надо, в основном алгоритмы в задачах, главное - внимательно делать, авот с этим у меня например вечно проблемы - к счастью, обошлось в этот раз ._.ЗаЧеМ оПеРаТоРы оТсЕчЕнИя И оТрИцАнИя В зАпРоСе К пРоГрАмМе???!?!?!так, в слайдах всё про это идеально сказано! пизже и ровнее некуда.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
