Матлогика - задачи с примечаниями (1162128), страница 4

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

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

Задача 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).

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+H

better(K,N,L) <- subset (X1, L), 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 — сравнение и равенство.

1.) Некоторые сходящиеся последовательности действ. чисел имеют хотя бы 2 различные предельные точки.

2.) Сумма любых двух расходящихся последовательностей действ. чисел является сходящейся последовательностью действ. чисел.

3.) Всякая неограниченная последовательностей действ. чисел не имеет предела.

Ответы:

1.) ∃x∃y∃p∃q [ S(x) & R(y) & M(y,x) & R (p) & R(q) & R(q) & A(p,x) & A(q,x) & (q < p) ]

2.) ∀x∀y∃z ( [S(x) & S(y) & ¬ ( ∃ p R(p) ¹& M(p,x)) & ¬ ( ∃ q R(q) & M(q,y))] →(S(z) & ∀ n (N(n) ???????→∃ x1 ∃ x2 ∃ x3 (E(x1, n, y) & E(x2, n, x) & E(x3, n, z) & (x3 = x1 + x2)))& ∃ m (R(m) & M(m, z))))

3.) ∀x ((S(x) & ¬ (∃y ∀n ( R(y) & N(n) & (∃ x1 (R(x1) & E(x1,n,x) &( -y < x1) & (x1 < y)))))) → ¬( ∃m (R(m) & M(m,x))))

Братва Civ побывала тут.

_____________________________________________________________

Задача 5.

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) & (x2, n, y2) & E(x3, n, y3) & (x3 = x1 + x2))))

- суммой числовых последовательностей (xn) и (yn) называется числовая последовательность (zn) такая, что zn = xn + yn. (википедия)

Что называется успешным табличным выводом для семантической таблицы T=<Г, >? Всякая ли невыполнимая семантическая таблица имеет успешный табличный вывод?и

Успешный вывод - дерево конечно, все листья - закрытые таблицы.

Да, по теореме о полноте табличного вывода.

Задача 5.

Сформулируйте теорему Левенгейма-Сколема. Следует ли из этой теоремы утверждение: "Если любая интерпретация предметной областью которой является множество всех рациональных чисел является моделью для предложения , то формула общезначима"

Теорема: формула выполнима тогда и только тогда, когда она имеет модель с конечной или счетно- бесконечной предметной областью. По-моему не следует, в теореме речь о выполнимости.

_____________________________________________________________

Задача 6.

Сформулируйте теорему корректности для резолютивного вывода из множества дизъюнктов. Верно ли, что если хотя бы одна эрбрановская интерпретация не является моделью для множества дизъюнктов S, то из S резолютивно выводим пустой дизъюнкт?

Если из системы дизъюнктов резолютивно выводим пустой дизъюнкт, то эта система противоречива. Неверно, эрбрановские интерпретации можно построить и совсем по левым данным.

Задача 6

Какая подстановка называется композицией подстановок ? Какая подстановка образуется в результате следующей композиции {x/y}{y/z}{z/u}{u/x}?

композиция g = - подстановка, удовлетворяющая условию Pg = (Pθ)η для любого P, результатом будет являться подстановка {y/x, z/x, u/x}

____________________________________________________________

Задача 7

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

Список файлов ответов (шпаргалок)