2

我在用纸笔解决差异列表问题时遇到了问题，而不是在 SWI Prolog 的帮助下（这些天我正在准备我的逻辑编程考试）。

这是问题：

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

明确给出查询 ?- q(t) 的所有基本项 t 的集合。成功。以封闭形式陈述集合的正式定义（即，不要使用递归定义）。

答案是：

{[t1, . . . , tn-1, tn, tn-1, . . . , t1] | n > 0, ti 是所有 i ∈ {1, . . . , n}}

我使用了 [1,2,3,2,1]，它给了我真正的预期答案。

我不明白解决这个问题的步骤是什么？

4

1 回答 1

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).成功 iff ti-1 = ti+1, ti-2 = ti+2, ..., t2 = tn-1, t1 = tn，即t = [t1,t2,...,ti-1,ti,ti-1,...,t2,t1].

于 2015-07-30T09:43:32.790 回答