Условия и некоторые решения задач (1158137), страница 4
Текст из файла (страница 4)
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) 1& 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
Что называют 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
Слабейшее предусловие - то, при котором любой результат программы будет удовлетворять постусловию.
wpr(...) = x > 1 & wpr(x - 2,
Задача 9.
Как определяется отношение выполнимости I, s0 I |= F
и темпоральной логики PLTL? Является ли формулы 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, логическим следствием которой являются обе формулы ϕ и ψ, потому что… false подходит
2.Существует формула X, являющаяся логическим следствием обеих формул ϕ и ψ, потому что… как ни странно, true является логическим следствием любых
3.Не существует ни одного успешного табличного вывода из семантической таблицы <{ϕ}, {ψ}>, потому что...
4.Все приведенные выше утверждения верны.
4?
____________________________________________________________________________
3.Если подстановка 
является правильным ответом на запрос G, обращенный к программе P0, но не является правильным ответом на запрос G, обращенный к программе P1, то запрос G , обращенный к программе P2, имеет успешноЗадача 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} можно построить резолютивный вывод пустого дизъюнкта □. Какие из приведенных ниже утверждений справедливы и почему?
1.Семантическая таблица T=<0 | {D1 & D2 & ... Dn}> имеет успешный табличный вывод, потому что...
2.Семантическая таблица T=<0 | {D1 & D2 & ... Dn}> не имеет успешного табличного вывода, потому что...
3.Семантическая таблица T=<{D1 & D2 & ... Dn} | 0> имеет успешный табличный выв
од, потому что...
4.Семантическая таблица T=<{D1 & D2 & ... Dn} | 0> не имеет успешного табличного вывода, потому что...
5.Ни одно из приведенных утверждений в общем случае неверно.
_____________________________________________________________________
Задача 12(3 балла)
Пусть G - запрос к хорновской логической программе P и 
и 
- некоторые подстановки. Какие из приведенных ниже утверждений будут при этом всегда верны и почему?
1.Если и - вычисленные ответы на запрос G к программе P, то подстановка 
является правильным ответом на запрос G к программе P, потому что...
2.Если - не является вычисленным ответом на запрос G, обращенный к программе P1, то подстановка не является правильным ответом на запрос G к программе P, потому что...
3.Если подстановка является вычисленным ответом на запрос G, а подстановка не является вычисленным ответом на запрос G к программе P, то подстановка не является правильным ответом на запрос G к программе P, потому что
4.Все приведенные выше утверждения, вообще говоря, неверны, потому что...
Задача 12
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
