2009 - 2008 Экз. вопросы 2009 ((1-2-4-7-8-9-9.1) 2008 (1-2-3-4) (конкатенация) (1162062), страница 7
Текст из файла (страница 7)
Существуют арифметическая функция, вычислимая на машине Тьюринга, для вычисления которой нет логической программы даже в случае использования операторов is и not, потому что...Задача 13 (3 балла). Докажите, что существует алгоритм, проверяющий общезначимость формуллогики предикатов, предваренная нормальная форма которых имеет вид∀x1 ∀x2 .
. . ∀xn ϕ(x1 , x2 , . . . , xn ).Каков этот алгоритм?Задача 13 (3 балла). Известно, что формула PLTL ϕ имеет длину n, а конечная модель (LTS) Mимеет m состояний. Тогда система Хинтикки для формулы ϕ и LTS M представляет собой ориентированный граф, в котором содержится самое большее1.
O(nm ) вершин, потому что....2. O(mn ) вершин, потому что....3. n2O(m) вершин, потому что....4. m2O(n) вершин, потому что....5. 2O(nm) вершин, потому что....Задача 13 (3 балла). Из логической программы P (содержащей операторы отсечения и отрицания)с запросом G были удалены все операторы отсечения, в результате чего образовалась новая программаP 0 . Какие из приведенных ниже утверждений будут всегда верны и почему?1. Всякое успешное вычисление запроса G к программе P будет также являться успешным вычислением запроса G к программе P 0 , потому что...2.
Всякое успешное вычисление запроса G к программе P 0 будет также являться успешным вычислением запроса G к программе P, потому что...3. Всякий вычислимый ответ на запрос G к программе P будет также являться вычислимым ответомна запрос G к программе P , потому что...4. Всякий вычислимый ответ на запрос G к программе P 0 будет также являться вычислимым ответом на запрос G к программе P, потому что...5. Ни одно из приведенных выше утверждений в общем случае неверно..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
