задачи с ответами (2012) (1162130), страница 5
Текст из файла (страница 5)
Текст это конечный непустой список слов. Слово 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 — сравнение и равенство.“некоторые сходящиеся последовательности действ.
чисел имеют хотя бы 2 различныепредельные точки”.“сумма любых двух расходящихся последовательностей действ. чисел являетсясходящейся последовательностью действ. чисел ”.“Всякая неограниченная последовательностей действ. чисел не имеет предела”.S(y) & ∃ m (R(m) & M(m, y)) - существует предел последовательности.∃ M (R(M) & ∀ n (N(n) & ∃ x (R(x) & E(x, n, y) & (|x| < M)))) - последовательность ограниченавещественным числом(S(y3) & ∀ n (N(n) ∃ x1 ∃ x2 ∃ x3 (E(x1, n, y1) & E(x2, n, y2) & E(x3, n, y3) & (x3 = x1 + x2))))- суммой числовых последовательностей (xn) и (yn) называется числоваяпоследовательность (zn) такая, что zn = xn + yn. (википедия)вот и всё что нужно._____________________________________________________________Задача 5.Что называется успешным табличным выводом для семантической таблицы T=<Г,>? Всякая ли невыполнимая семантическая таблица имеет успешный табличныйвывод?Успешный вывод - дерево конечно, все листья - закрытые таблицы.Да, по теореме о полноте табличного вывода.Задача 5.Сформулируйте теорему Левенгейма-Сколема.
Следует ли из этой теоремыутверждение: "Если любая интерпретация предметной областью которой являетсямножество всех рациональных чисел является моделью для предложения , тоформула общезначима"Теорема: формула выполнима тогда и только тогда, когда она имеет модель с конечнойили счетно- бесконечной предметной областью._____________________________________________________________Задача 6.Сформулируйте теорему корректности для резолютивного вывода из множествадизъюнктов.
Верно ли, что если хотя бы одна эрбрановская интерпретация неявляется моделью для множества дизъюнктов S, то из S резолютивно выводимпустой дизъюнкт?Если из системы дизъюнктов резолютивно выводим пустой дизъюнкт, то эта системапротиворечива.Задача 6Какая подстановка называется композицией подстановок? Какаяподстановка образуется в результате слудующей композиции {x/y}{y/z}{z/u}{u/x}?____________________________________________________________Задача 7Что называют SLD-результвентой целевого утверждения G и программногоутверждения D? Возможен ли случай, когда SLD-резольвентой целевогоутверждения G и программного утверждения D оказывается тот же самый запросG?Да, возможен___________________________________________________________Задача 8.Что называется стратегией вычисления логических программ? Какая стратегиявычисления логических программ считается стандартной?Стратегией вычисления называется порядок построения дерева резолютивныхвычислений.
Стандартная стратегия: обход в глубину с возвратом___________________________________________________________Задача 9Как определяется отношение выполнимости I,s |=для формулыв состоянии s интуиционистской интерпретации I? Верно ли,что всякая формула, являющаяся общезначимой в интуиционистской логике, такжеявляется общезначимой в классической логике?Нет, неверноЗадача 9Какая формула называется слабейшим предусловием для заданной программызаданного постусловия Каково слабейшее предусловия для программыif x>1 then x <= x-2 else x<=x+2иЗадача 9.Как определяется отношение выполнимости I, s0 I |= FPLTL? Является ли формулы F()иF&Fи темпоральной логикиравносильными?_____________________________________________________Задача 10Множество замкнутых формул Г не имеет модели.
Какое из приведенных нижеутверждений справедливы и почему1.Существует успешный табличный вывод для исходной таблицы T=<0, Г>, потому что...2.Существует успешный табличный вывод для исходной таблицы T=<Г, 0>, потомучто...3. Не существует успешного табличного вывод для исходной таблицы T=<0, Г>, потомучто...4. Не существует успешного табличного вывод для исходной таблицы T=<Г, 0>, потомучто...5.Ни одно из приведенных ниже утверждений не является верным2 - таблица невыполнима => существует успешный выводЗадача 10Известно, что для семантической таблицы Т=<{ϕ}, {ψ}> нельзя построить ни одногоуспешного табличного вывода. Какие из приведенных ниже утверждений всегдаверны для любых замкнутых формул ϕ и ψ.1.Таблица Т=<{ϕ}, {ψ}> не является выполнимой, потому что...2.Для таблица Т’=<{ψ}, {ϕ}> также не существует ни одного успешного вывода, потомучто...3.Формула ϕ не является логическим следствием формулы ψ, потому что4.Формула ψ не является логическим следствием формулы ϕ, потому что...5.Все приведенные выше утверждения в общем случае неверны, потому что...//Ответ 4.
Надо норм обосновать, тк ϕ->ψ не катит, инфа 100%.Отсутствие вывода = таблица выполнима. => есть интерпретация, гдевыполнена фи и не выполнена пси. => пси не является следствием фи.Задача 10Известно, что выполнимые замкнутые формулы ϕ и ψ не имеют ни одной общеймодели. Какие из приведенных ниже утверждений всегда верны и почему?1.Существует формула X, логическим следствием которой являются обе формулыϕ и ψ, потому что...2.Существует формула X, являющаяся логическим следствием обеих формул ϕ и ψ,потому что...3.Не существует ни одного успешного табличного вывода из семантическойтаблицы <{ϕ}, {ψ}>, потому что...4.Все приведенные выше утверждения верны.4____________________________________________________________________________Задача 11(3 балла)Предположим, что S - некоторые противоречивое множество хорновских дизъюнктов.Какие из приведенных ниже утверждений всегда справедливы и почему?1.В множестве S есть дизъюнкт, состоящий только из одного атома, потому что...2.В множестве S есть дизъюнкт, состоящий только из положительных литер,потому что...3.В множестве S есть дизъюнкт, состоящий только из отрицательных литер, потомучто...4.Противоречивых множеств хорновских дизъюнктов не существует, потому что...5.Все приведенные выше утверждения всегда верныПо-моему верно 1,2,3 - потому что пустой дизъюнкт может получитьсятолько как резольвента двух атомов, один из которых положительный, другойотрицательный.Задача 11(3 балла)Пусть А(Х) - атом, Р - хорновская логическая программа, I - эрбрановская модельдля логической программы Р.
Какие из приведенных ниже утверждений всегдасправедливы и почему?1.Если I |= ∃Х А(Х), то запрос ?А(Х), обращенный к программе Р, имеет хотя бы одноуспешное вычисление, потому что...2.Если все вычисления запроса ?А(Х), обращенного к программе Р, являеютсяуспешными, то I |= ∀Х А(Х), потому что3.Если хотя бы одно вычисление запроста ? А(Х), обращенного к программе Р, являетсяуспешным, то I |= ∃Х А(Х), потому что4.Если I |= ∀Х А(Х), , то все вычисления запроса ?А(Х), обращенного к программе Р,являются успешными, потому что ...Задача 11Известно, что из множества непустых дизъюнктов S={D1, ..., Dn} можно построитьрезолютивный вывод пустого дизъюнкта □.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
