Hi,

If I have boolean variable x1

And assuming multiplication means "AND" for boolean expressions;

and that addition means "OR"

Then

  x1 = x1^2 = x1^3 = ...=x1^k, k >= 1

Since "x1 and x1 and x1 ... and x1" = x1;

it is true if x1 is true and false if x1 is false.

How can a boolean expression with variables taken

to various powers be simplified?

I can't take credit for this; but Dave Rusin showed

me a command that seems to work very slick to

perform this.

Let's sayI have variables x1 : x7 and have a boolean

expression with those variables (to various powers

of those variables).

Let's say I want to simplify the expression;

call it "expr"; bringing all the powers back to one.

         simplify( expr, {seq( (x||i)^2 = x||i, i=1..7 ) } );

Example:

expr := expand(1-(1-x1*x2)*(1-x1*x3)*(1-x2*x3));

=> x2*x3+x1*x3-x1*x3^2*x2+x1*x2-x1*x2^2*x3-x1^2*x2*x3+x1^2*x2^2*x3^2

expr2 := simplify( expr, {seq( (x||i)^2 = x||i, i=1..3 ) } );

=> x2*x3+x1*x3+x1*x2-2*x1*x3*x2
 

From Dave:  (regarding a case with 7 variables)

"think in terms of the ring  Z[x]/(x^2 = x) . That is, all the
substitutions are the consequence of the single identity  x^2 = x
(e.g. x^3 = x x^2 = x x = x^2 = x ) . Maple can do this (in your case) with:

 simplify( expr, {seq( (x||i)^2 = x||i, i=1..7 ) } );

There are efficient algorithms at work here, using Groebner bases
for ideals in polynomial rings. (At least, that's how I would
program it!)"

-Jay