задачи с ответами (2012) (1162130), страница 4
Текст из файла (страница 4)
Всегда отрицательным вне зависимости от программы Р, потому что…3 Может быть как положительным, так и отрицательным в зависимости от видапрограммы Р, потому что…4 На запрос ?not(P(с))может быть вообще не получено никакого ответа, потому чтоможет пойти перебор по бесконечной ветви, которая расположена раньше ветви сзапросом P(x).Задача 16. Предположим, что в правило резолюции было внесено следующееизменение: резольвентой дизъюнктов D1=D1’or L1, D2=D2’ or Not(L2) объявляется всякийдизъюнкт D0=(D1’ and D2’)n, где n – унификатор (не обязательно наиболее общий) L1 иL2.После этого изменения Теорема корректности резолютивного вывода (1) и Теоремаполноты резолютивного вывода(2) будут…1. 1,2 верно2.
1 верно, 2 неверно3. 1 неверно, 2 верно4. 1,2 верно,потому что 1. Полнота: если всякий раз в качестве этого "любого" унификатораиспользовать наиболее общий, то получится обычный метод резолюций, аон полон, так что полнота не теряется.2. Корректность: поскольку переменные в дизъюнктах понимаютсясвязанными кванторами всеобщности, то добавление к системе примералюбого дизъюнкта из этой системы не изменяет ее (не-)противоречивости.Остается заметить, что "расширенное" правило резолюции сводится квычислению "классической" резольвенты и взятию ее примера.Задача 17.
Предположим, что ни один основной атом не является логическимследствием хоновской логической программы P.1 Интерпретация I=пуст мн-ву является можель P, тк2 Программа Р не имеет ни одной модели3 Любая эрбр интерпретация I явся моделью для Р4 Исходное условие не осуществимо, то есть не существует ни одной такойхорновской логической программы Р, для которой выполнялось бы, что ниодин основной атом не является логическим следствием хоновской логическойпрограммы P, потому что по теореме о наименьшей модели всякая хорновскаялогическая программа имеет наименьшую эрбрановскую модель5 Ни одно(1-4)не верно, ткЗадача 18.
Известно, что формула PLTL фи имеет длину n, а конечная модель(LTS) M имеет m состояний. Тогда система Хинтикки для фи представляет собойориентированный граф , в котором m*2^O(n) вершин, потому что (s,B) в s – m, в В2^O(n) множеств.Задача 19. Формула фи логики предикатов 1го порядка выполнима тогда и толькотогда, когда1 В любом дереве табличного вывода для таблицы Т=<фи, 0> каждая ветвьзавершается аксиомой2 В любом дереве табличного вывода для таблицы Т=<фи, 0> хотя бы одна ветвьзавершается аксиомой3 Хотя бы в одном дереве табличного вывода для таблицы Т=<фи, 0> каждаяветвь завершается аксиомой4 Хотя бы в одном дереве табличного вывода для таблицы Т=<фи, 0> хотя быодна ветвь завершается аксиомой5 1-4 не верно, потому чтоЗадача 20.
Известно, что в программе Р ответ на запрос ?P(х) имеет успешноеSLD-резолютивное опровержение, в результате которого в качестве ответавычисляется подстановка {x/f(y)}. Что будет верно независимо от программы Р иатома Р(х) и модели I?1 Р |= АхР(х)2 Р |= ЕхР(х) x/f(y)3 Р |= АхР(f(y)) мы вывели пустой дизъюнкт при x/f(y)4 Р |= ЕхР(f(y))5 все не верноЗадача 21. Известно, что эрбарановская интерпретация I является модельюхоновской логической программы P.1 Множества I (= Succ(p)2 I =) Succ(p) , потому что Succ(p) = минимальной эрбрановской модели поопределению3 I (= Succ(p) или I =) Succ(p), зависит от I4 I , Succ(p) несравнимыЗадача 22. фи - формула логики предикатов в ссф. Что неверно?1 Если фи выполнима, то фи выполнима хотя бы в одной эрб интерпретации дляформулы фи(нет, так как мы можем взять формулу, которая выполнима в интерпс беск предметной областью, но не выполнима в интп с конечной – хотя бы однаконст и f)2 Если фи выполнима хотя бы в одной эрб интерпретации для формулы фи, то фивыполнима3 Если фи выполнима в каждой эрб интерпретации для формулы фи, то фиобщезначима4 Если фи не имеет эрб моделей, то фи не имеет никаких моделей (пример из1)5 1-4 верно, потому чтоЗадача 23.
Первая подстановка, которая будет вычислена программой Р в ответна запрос G1 зависит только от стратегии обхода SLd-вычислений программы Р для запросаG2 зависит только от порядка расположения программных утверждений в Р3 зависит только от порядка расположения подцелей в G4 зависит только от порядка расположения атомов в теле процедур Р5 зависти от 1-46 не зависит от 1-4Задача 24. Известно, что каждое конечное подмножество D’ бесконечногосемейства дизъюнктов D непротиворечиво.1 семейство дизъюнктов D будет непротиворечивым.2 семейство дизъюнктов D может быть как непротиворечивым, так ипротиворечивым3 семейство дизъюнктов D будет противоречивым.4 1-3 неверно.Задача 23.
G – запрос к хорновской логической программе Р1 каждый правильный ответ является вычислимым ответом (тк прав ответ –частный случай вычислимого ответа)2 каждый вычислимый ответ является правильным ответом (теорема окорректности sld)3 Некоторые (не все) правильные ответы являются вычислимыми ответами4 Некоторые (не все) вычмслимые ответы являются правильными ответамиЗадача 24.
Известно, что их множества дизъюнктов S можно посторить резолютвывод пустого диз.1Существует успешный табличный вывод для Т=<0,s>2 Существует успешный табличный вывод для Т=<s,0> в s есть d=false3 не существует успешный табличный вывод для Т=<0,s>4 не существует успешный табличный вывод для Т=<s,0>5 1-4 неверноЗадача 25. Пусть Г – непустое множество логических следствий формулы φ. Г неимеет ни одной модели с конечной или счетной областью интерпретацииЧто неверно?1 φ не имеет ни одной модели с конечной или счетной областью интерпретации2 φ не имеет вообще ни одной модели3 любая пси является логическим следствием φ4 любая замкнутая формула пси равносильна φ (одна из скобок фи->пси илипси->фи false)Задача 25. Пусть h, g э subst, h=gp (p э subst) (g – almost noy)1 Ah=Bh -> Ag=Bg2 Ag=Bg -> Ah=Bh3 h-noy -> g- not noy4 g-noy -> h- not noy1.2.3.4.Задача 26.
Пусть Р – это хорновская логическая программа, а S – это множествовсех дизъюнктов, соответствующих программным утверждениям программыР. Известно, что для наименьшей эрбрановской модели МР программы Рвыполняется соотношение МР = ø. Какие из приведенных ниже утверждений будутпри этом всегда НЕверны и почему?В Р нет фактов (верно)Для Р вообще не существует моделей (для любой лог проги есть эрб модель!)Любой запрос к проге выполняется неуспешноТакой проги нет (пример: P(x)<-P(x); P(x)<-;)Задача 27. ψ – пнф, φ – ссф для ψ1.2.3.4.5.1.2.3.4.5.φ - невыполнима, то ψ - невыполнимаφ - выполнима, то ψ - выполнимаφ - общезначима, то ψ - общезначима3 в другую сторонуВсе не верноЗадача 28. Пусть Р – это хорновская логическая программа, а S – это множествовсех дизъюнктов, соответствующих программным утверждениям программыР.
Известно, что для наименьшей эрбрановской модели МР программы Рвыполняется соотношение МР = ø. Какие из приведенных ниже утверждений будутпри этом всегда верны и почему?В 1-2 были утверждения по смыслу схожие с тем, что любой запрос к этойпрограмме выполняется неуспешно (или что-то в этом роде, если мне не изменяетпамять)В 1-2 были утверждения по смыслу схожие с тем, что некоторый запрос к этойпрограмме выполняется неуспешно (или что-то в этом роде, если мне не изменяетпамять)Система дизъюнктов S является противоречивой, потому что…Такой проги нет (контрпример: P(x)<-P(x); P(x)<-;)Все приведенные выше утверждения всегда неверны, потому что… (4объяснили, а вообще эта программа, в которой нет фактов, так как если бы онибыли, то было бы не верно, что МР = ø. Следовательно, 1-2-3 неверны.)ДОБАВЬТЕ ВОПРОСЫ 10-13ЗАПИЛИТЕ ВАРИАНТЫ 2011 ГОДА!!!Построить логическую программу, которая для заданного конечного множестванатуральных чисел , представленных списком L, вычисляет максимальное почислу элементов подмножество чисел X, кратных одному и тому же числу из этогоже подмножества X.
Запрос к программе должен иметь вид ?G(L,X).Только не стирайте это решениеG(L,X) :- krat(X,A), not( have_more(L,X) ), subseq(X,L), elem(A,X);krat([ ], A) :-;krat([B|X], A) :- B mod A = 0, krat(X,A);subseq([ ],[ ]) :-;subseq([A|X], [A|L]) :- subseq(X, L);subseq(X, [A|L]) :- subseq(X,L);have_more(L,X) :- krat(Y, A), subseq(Y,L), elem(A,Y), length(X,N), length(Y,M), M>N;length([ ], 0) :-;length([A|X], N) :- length(X, M), N is M+1;Ваше мнение, господа и дамы?1.похоже на правду, скомпильте, что ли \\ сви-прологу че-то не нравится, falseвыдаёт2. не знаю,по какой причине,но предикат krat работает неправильно3.
Очень сомнительна запись B mod A = 0, скорее нужно что-то вродеkrat([B|X], A) :- С is B mod A, C = 0, krat(X,A);вот мой вариант проги, проверенный на прологе (рабочий):G(L,X) <- M(L,L,nil,X)M(L,nil,X,X) <M(L,Y.L1,U,X) <- dividers(L,Z,Y), len(Z,Zlen), len(U,Ulen), Zlen > Ulen,!, M(L,L1,Z,X)M(L,Y.L1,U,X) <- M(L,L1,U,X)dividers(nil,nil,z) <dividers(x.L,x.T,z) <- x mod z = 0, dividers(L,T,z), !dividers(X.L,T,z) <- dividers(L,T,z)================ВАРИАНТ_2011===============Задача 0(хз какой вариант). Слово это непустой список букв фиксированного конечногоалфавита.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
