Список отличий (пролог)(логическое программирование)

Question

У меня проблема с решением проблемы различий с помощью бумаги-карандаша не с помощью SWI Prolog (в настоящее время я готовлю экзамен по логическому программированию).

Вот вопрос:

q(X) :- p(X - []).
p([X|Y] - Y).
p([X|Y] - Z) :- p(Y - [X|Z]).

Явно дайте набор всех основных терминов t, для которых выполняется запрос?- q(t). преуспевает. Сформулируйте формальное определение множества в закрытой форме (т. Е. Не используйте рекурсивное определение).

Ответ:

{[t1,.,,, tn−1, tn, tn−1, .,,, t1] | n > 0, ti является основным членом для всех i ∈ {1, .,,, n}}

Я использовал [1,2,3,2,1], и это дало мне верный ответ.

Я не мог понять, что шаги для того, чтобы решить эту проблему?

Answer 1

Позволять t = [t1,t2,t3, ... , tn] быть списком

q(t). удастся, если p(t - []). преуспевает.

p(t - []). успешно, если p([t2,t3,...,tn] - [t1]). успешно (третье правило).

p([t2,t3,...,tn] - [t1]). успешно, если p([t3,...,tn] - [t2,t1]) успешно и т. д.

Это на самом деле закончится успешно только в том случае, если в какой-то момент будет применено второе правило (в противном случае мы в конечном итоге вызовем p([] - _). который не соответствует ни одному из доступных правил), то есть если мы имеем p([ti,ti+1,...,tn] - [ti+1,...,tn]).,

Второй список [ti+1,...,tn] на самом деле [ti-1,ti-2,...,t2,t1] в соответствии с тем, как оно построено в третьем правиле.

Следовательно q(t). преуспевает, если ti-1 = ti+1, ti-2 = ti+2, ..., t2 = tn-1, t1 = tn, что значит t = [t1,t2,...,ti-1,ti,ti-1,...,t2,t1],