I'm curious if Logic Programs can do algebra

Question

I read a brief article about Prolog and Logic Programming. I'm curious if Logic Programs can do algebra. Like would you be able to ask what the Variable of X is in the equation 5+X = 7 and get an answer of -2?

Sumikosumma

Answer 1

All serious Prolog systems provide constraint logic programming over finite domains, called CLP(FD) for short, with which you can solve many such equations easily. For example, with SICStus Prolog, SWI and Yap:

?- use_module(library(clpfd)).
true.

?- 5+X #= 7.
X = 2.

Apparently, the answer is 2 instead of -2. Also check out constraint logic programming over other domains, like the rationals with library(clpq).

Seymour

Please see optimization for an approach that also works with nonlinear equations (sometimes). – Seymour

There is an implementation of an equation simplifier in Prolog that was written in 1987. I also found a more recent implementation of the Knuth-Bendix completion algorithm in Prolog. – Zion

Answer 2

Yes, Prolog can do algebra.

If you Google for Prolog and CAS (Computer algebra system) you will get lots of results.

e.g. Using Prolog as a CAS

If you understand that Prolog = Syntactic unification + backward-chaining + REPL,

then realize that it is the unification that is the heart of solving the problems/equations, you may run into equational reasoning which is used for solving problems that contain equals (=). This same logic is also used with automated theorem provers and proof assistants.

If you look here you will find prolog.ml which implements the unification and backward-chaining in this automated theorem prover.

You should also check out term rewriting and search Google for term rewriting to learn more about the science of solving equations using terms.

Enow

Very nice pointers! Would make your answer even more useful if you can also briefly summarize those concepts before giving pointers for more. – Atrophied

Answer 3

There are a few implementations of computer algebra systems in Prolog, including an equation simplifier and the PRESS equation solver. There are also several constraint solvers for linear and nonlinear equations, including CLP(R,Q) and CLP (BNR), and several other solvers that have been implemented using constraint handling rules.

Instead of implementing a computer algebra system in Prolog, it is also possible to implement a Prolog interpreter in a computer algebra system. For example, there is an article that describes an implementation of a rule-based programming system in Mathematica. There is also an implementation of logic programming system in Mathematica from the Wolfram Library Archive.

It is also apparently possible to implement logic programs in Sympy using its unification algorithm.

Zion

Answer 4

How about this? Note that this will only work for X+Y=Z.

equation(X,Y,Z):- var(X),X is Z-Y.
equation(X,Y,Z):- var(Y),Y is Z-X.
equation(X,Y,Z):- var(Z),Z is X+Y.

You can ask:

equation(5,X,7).
X = 2 .
?- equation(2,5,X).
X = 7.
?- equation(X,5,7).
X = 2

Sosthina

equation(1, 1, 2) fails, yet equation(1,1,Z), Z = 2 succeeds. – Oleviaolfaction

To solve more complicated linear equations, you can use CLP(R). – Zion