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

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

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

Пусть известно, что обе системы дизъюнктов 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, потому что...

5. Ни одно из приведенных выше утверждений в общем случае неверно.

1 и 2 точно не верно. 2 - понятно, из-за возможности найти ответ в той части программы, где было отсечение, а 1 - из-за взаимодействия отсечения и not. Про это сам Захаров говорил на апелляции, там может в какой-то ветви not из-за отрицания найтись правильный ответ и все перевернется!

3 и 4 надо проверить. Но мне кажется, что ответ 5.

// на апелляции сказал ответ 5.

мне кажется, ответ 1 и 2, т.к. оператор отсечения действует лишь при откате. Декларативная семантика не должна страдать

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

ну мля если бы все было детерминировано то на этом бы закончился курс епта.

??? не понялb

//типа надо думать, чтоб не запороться +1

ну там думать мало где надо, в основном алгоритмы в задачах, главное - внимательно делать, а вот с этим у меня например вечно проблемы - к счастью, обошлось в этот раз ._.

ЗаЧеМ оПеРаТоРы оТсЕчЕнИя И оТрИцАнИя В зАпРоСе К пРоГрАмМе???!?!?!

ётак, в слайдах всё про это идеально сказано! пизже и ровнее некуда

1

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

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