math - Prolog 给定 x 的所有可能表达式

Question

我有一个具有给定语法的序言程序:

sum --> [+], mult, sum | mult | num.
mult --> [*], num, xer.
xer --> [x] | [^], [x], num.
num --> [2] | [3] ... etc

我有我的表达的抽象树表示。例如: mul(num(2),var(x))等于 [*,2,x]已验证。
我希望能够创建满足给定 x 和解决方案的所有表达式。使用

allExpressions(Tree, X, Solution).

例如:

?- allExpressions(Tree, 2, 6)
Tree = mul(num(3),x)
Tree = sum(num(2),mul(num(2),var(x))
etc.

由于我的语法，它显然不是一个无限的方程组。
我已经编程了一个 evaluation(Tree, X, Solution)它计算给定 X 变量的答案。所以我需要帮助的是为给定的 x 变量和解生成可能的方程组。

关于我如何处理这个的任何想法？谢谢

Answer 1

这很简单:由于您的所有算术运算只能增加表达式的值，因此在搜索解决方案时限制深度很简单。简单地归纳描述一个解决方案的样子。例如，您可以使用 SWI-Prolog 的有限域约束来进行加法和乘法，如下所示:

:- use_module(library(clpfd)).

expression(var(x), X, X).
expression(num(N), _, N) :- phrase(num, [N]).
expression(mul(A,B), X, N) :-
        N1 * N2 #= N,
        N1 #> 1,
        N2 #> 1,
        expression(A, X, N1),
        expression(B, X, N2).
expression(sum(A,B), X, N) :-
        N1 + N2 #= N,
        N1 #> 1,
        N2 #> 1,
        expression(A, X, N1),
        expression(B, X, N2).

我将其他操作留作练习。

示例查询和一些结果:

?- expression(Tree, 2, 6).
Tree = mul(var(x), num(3)) ;
Tree = mul(num(2), num(3)) ;
    [...solutions omitted...]
Tree = sum(num(2), mul(num(2), var(x))) ;
Tree = sum(num(2), mul(num(2), num(2))) ;
    [...solutions omitted...]
Tree = sum(sum(num(2), num(2)), num(2)) ;
false.

+1 用于对表达式树( var(x) 、 num(N) 等)使用干净的、非默认的表示，这使您可以在推理时使用模式匹配。