Задачи с ответами (2012), страница 4
Описание файла
PDF-файл из архива "Задачи с ответами (2012)", который расположен в категории "". Всё это находится в предмете "математическая логика и логическое программирование" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 4 страницы из PDF
Известно, что эрбарановская интерпретация 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(хз какой вариант). Слово это непустой список букв фиксированного конечногоалфавита. Текст это конечный непустой список слов.
Слово W называется циклическимсдвигом U, если W = V1V2 и U = V2V1 для некоторых слов V1 и V2. Например, слово “банка”является циклическим сдвигом слова “кабан”. Построить логическую программу, котораядля заданных текстов L1 и L2 вычисляет бесповторный список X всех тех слов текста L1,никакие циклические сдвиги которых не являются словами текста L2. Запрос к программедолжен иметь вид ?G(L1,L2,X).G(L1,L2,X) <- subset (X,L1), elem(M,X), savig(M,N), not(elem(N,L2)), length(X,K),not(better(K,L1)).subset([X],L).subset([H|T1], [H|T2]) <- subset (T1,T2)subset([H1|T1],[H2|T2]) <- subset ([H1,T1], T2).savig(M,N) <- subset1(V1,M), subset2(V2,M), subset1(V2,N),subset(V1,N).subset1([],L).subset1([H|T1],[H|T2]) <- subset1(T1,T2).subset2([],[])subset2([H1|T1],[H2|T2]) <- subset ([H1,T1],T2)subset2([H|T1],[H|T2]).done//Посаны, попробуйте ваш subset запусть на сви прологе, он оч интересныерезультаты выведет, типа?- subset([1],X).true ;X = [_G385, 1|_G395] ;X = [_G385, 1, _G397, []|_G407] ;X = [_G385, 1, _G397, [], _G409, []|_G419] ;X = [_G385, 1, _G397, [], _G409, [], _G421, []|_G431] ;X = [_G385, 1, _G397, [], _G409, [], _G421, [], _G433|...] ;Непонятное решение(и вообще в хлам неправильное):?Concat(L1,L2,Lres) - Lres = L1 .
L2;1. Функция Cycle(l1,l2) - вычисляет является ли одно слово циклическим относительнодругого.1.1 equal(L1,L2) - проверяет равны ли списки.equal(nil,nil)<-;equal(X.L1,Y.L2)<- X = Y,!, equal(L1,L2);1.2 ?shift(L1,L2) - L2 - сдвиг на один списка L1shift(nil,nil)<-;shift(X.L1,L4)<- Concat(L1,X.nil,L4);1.2 ?cycle(L1,L2)CycleHelp(L1,L2,L3) <- equal(L1,L2);CycleHelp(L1,L2,L3) <- shift(L2,L4), not equal(L3,L4),!, CycleHelp(L1, L4, L3);Cycle(L1,L2) <- CycleHelp(L1,L2,L2)2. ?CycleList(X,L2) - тру если Х не является никаким циклическим сдвигом слов из L2.CycleList(X,nil) <-;CycleList(X,Y.L2) <- not Cycle(X,Y),!,CycleList(X,L2);3. ?G(L1,L2,Lres)G(nil,L2, nil)<-;G(X.L1,L2, X.Lres)<- CycleList(X,L2), not elem(X,Lres), !,G(L1,L2,Lres);G(X.L1,L2,Lres)<-G(L1,L2,Lres);Задача 0 (вариант 55).
Слово это непустой список букв фиксированного конечногоалфавита. Словарь - это конечный непустой список попарно различных слов. Построитьлогическую программу, которая для заданного словаря L разбивает множество слов Lна два таких непересекающихся словаря X и Y = L \ X, что никакие два словаине имеют ни одной общей буквы. Запрос к программе должен иметь вид ?G(L,X,Y).G(L,X,Y) <- subset(X,L), minus(Y,L,X), elem(W1,X), elem(W2,Y), not(commonletter(W1,W2))minus([],[],[]).minus([H|T1],[H|T2],X) <- minus(T1,T2,X)minus(Y,[H|T1], [H|T2]) <- minus(Y,T1,T2)commonletter(W1,W2) <- elem(X,W1), elem(X,W2)Непонятное решение:Задача 0 (вариант 53). Построить логическую программу, которая для заданногоконечного множества целых чисел, представленного бесповторным списком L, изаданного целого числа N вычисляет максимальное по числу элементов подмножество X,сумма чисел которого превосходит N.
Запрос к программе должен иметь вид ?G(L,N,X).G(L,N,X) <- subset(X,L), summ(X,M), M>N, length(X,K), not(better(K,N,L))summ([], 0)summ([H|T],M) <- summ(T,M1), M is M1+Hbetter(K,M,L) <- subset (X1, L1), summ(X,M1), M1 >N, length(X1,K1), K1 > KНепонятное решение:Задача 1 (3 штуки из разных вариантов):Доступные предикаты●●●●●●●R(x) — вещественное число;N(x) — натуральное число;S(y) — y — последовательность действительных чисел;E(x, n, y) — x — элемент y с номером n;A(p, y) — p — предельная точка последовательности y;M(x, y) — x — предел последовательности y;x < y, x = y — сравнение и равенство.“некоторые сходящиеся последовательности действ.