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

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

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

А) Пусть верно => Любое подмножество Г непротиворечиво => Любая конъюнкция выполнима (не фи_i=false)

Б) Г – противоречиво => Существует противоречивая конъюнкция => ее отрицание - общезначимо

Задача 15. Известно, что в программе Р ответ на запрос ?P(х) не имеет успешных вычислений ( было изначально в варианте: всегда является отрицательным). Каким будет ответ на запрос ?not(P(с))?

1 Всегда положительным вне зависимости от программы Р, потому что…

2 Всегда отрицательным вне зависимости от программы Р, потому что…

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. Корректность: поскольку переменные в дизъюнктах понимаются

связанными кванторами всеобщности, то добавление к системе примера

любого дизъюнкта из этой системы не изменяет ее (не-)противоречивости.

Остается заметить, что "расширенное" правило резолюции сводится к

вычислению "классической" резольвенты и взятию ее примера. WHAT?!

ИМХО потому что. По теореме Эрбрана система дизъюнктов противоречива ⇔ когда существует конечное противоречивое множество основных примеров. Т. е. то каким образом мы будем выбирать эти основные примеры не играет роли.

Задача 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), зависит от I

4 I , Succ(p) несравнимы

Задача 22. фи - формула логики предикатов в ссф. Что неверно?

1 Если фи выполнима, то фи выполнима хотя бы в одной эрб интерпретации для формулы фи(нет, так как мы можем взять формулу, которая выполнима в интерп с беск предметной областью, но не выполнима в интп с конечной – хотя бы одна конст и f) (вариант)

2 Если фи выполнима хотя бы в одной эрб интерпретации для формулы фи, то фи выполнима

3 Если фи выполнима в каждой эрб интерпретации для формулы фи, то фи общезначима (вариант)

4 Если фи не имеет эрб моделей, то фи не имеет никаких моделей (неверно, пример из1) (вариант)

5 1-4 верно, потому что

Задача 23. Первая подстановка, которая будет вычислена программой Р в ответ на запрос G

1 зависит только от стратегии обхода SLd-вычислений программы Р для запроса G

2 зависит только от порядка расположения программных утверждений в Р

3 зависит только от порядка расположения подцелей в G

4 зависит только от порядка расположения атомов в теле процедур Р

5 зависти от 1-4 (верно)

6 не зависит от 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=false

3 не существует успешный табличный вывод для Т=<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=Bg

2 Ag=Bg -> Ah=Bh (вариант)

3 h-noy -> g- not noy

4 g-noy -> h- not noy

Задача 26. Пусть Р – это хорновская логическая программа, а S – это множество всех дизъюнктов, соответствующих программным утверждениям программы Р. Известно, что для наименьшей эрбрановской модели МР программы Р выполняется соотношение МР = ø. Какие из приведенных ниже утверждений будут при этом всегда НЕверны и почему?

1. В Р нет фактов (верно)

2. Для Р вообще не существует моделей (для любой лог проги есть эрб модель!) (вариант)

3. Любой запрос к проге выполняется неуспешно

4. Такой проги нет (пример: P(x)<-P(x); P(x)<-;) (вариант)

Задача 27. ψ – пнф, φ – ссф для ψ

1. φ - невыполнима, то ψ - невыполнима (вариант)

2. φ - выполнима, то ψ - выполнима (вариант)

3. φ - общезначима, то ψ - общезначима (вариант)

4. 3 в другую сторону

5. Все не верно

Задача 28. Пусть Р – это хорновская логическая программа, а S – это множество всех дизъюнктов, соответствующих программным утверждениям программы Р. Известно, что для наименьшей эрбрановской модели МР программы Р выполняется соотношение МР = ø. Какие из приведенных ниже утверждений будут при этом всегда верны и почему?

1. В 1-2 были утверждения по смыслу схожие с тем, что любой запрос к этой программе выполняется неуспешно (или что-то в этом роде, если мне не изменяет память)

2. В 1-2 были утверждения по смыслу схожие с тем, что некоторый запрос к этой программе выполняется неуспешно (или что-то в этом роде, если мне не изменяет память)

3. Система дизъюнктов S является противоречивой, потому что…

4. Такой проги нет (контрпример: P(x)<-P(x); P(x)<-;)

5. Все приведенные выше утверждения всегда неверны, потому что… (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 - сдвиг на один списка L1

shift(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).

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

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