CODEWITHSUNDEEP
prolog
Shyamal Vaderia
Shyamal Vaderia

Reputation: 11

How can I simplfy algebraic expressions involving algebraic identities in prolog?

I have given expressions and I need to simplify them to their normal form i.e. there should not be any algebraic identities.

Algebraic identities for reference as follows.

X+0 = X
X+0 = X
X*1 = X
X*0 = 0
X/1 = X
0/X = 0
X-X = 0
X+X = 2X
X\X = 1

Sample expression and it's expected output are as follows,

Example 1:
Given expression: (X*(Y/Y)-X)*X
Simplified expression: 0

Example 2:
Given expression: ((X+X)/X)*(Y+Y-Y)
Simplified expression: 2*Y

Example 3:
Given expression: (AB/1)(C+1-C)
Simplified expression: A*B

My doubt is how can I represent any variable such as X or Y and perform this identities in prolog for this simplification.

There is no restriction on Input form or output form.

Upvotes: 1

Views: 256

Answers (1)

mat
mat

Reputation: 40768

This is an interesting question, because the algebraic identities you show are insufficient to derive the examples you show.

For example, let us consider the subterm Y/Y, which occurs in your first example.

Can you use any of the algebraic identities you show to simplify this term?

Answer: No. Exercise: Why not?

You may be tempted to add the "identity" X/X = 1 to your identities, but that would render the identities incorrect. This means that you would be able to derive identities that obviously do not hold.

To see this, consider the term 0/0, which you could reduce:

  • via 0/X → 0
  • and via X/X → 1

thus incorrectly obtaining 0 = 1 from these identities.

For more information about this interesting topic, read about term rewriting systems (TRS).

Upvotes: 1

Related Questions