MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: Boolean algebra

On 11 Sep 2006, at 18:39, Menace wrote:

> Thanks for your reactions. Unfortunately, in my actual application the
> preliminaries will be much longer. Both in number and in length (e.g.
> (b1&&b2&&b3&&b4&&b5)=False).
> Do you have any suggestions as to which addOn I could use to solve
> these kinds of problems?
> Dennis Nieuwenhuisen

I have got a message from Daniel Lichtblau suggesting that this could  
be approached vie the well known (but forgotten by me) equivalence  
between Boolean Algebras and Boolean rings. Let me quickly describe  
what this means. A Boolean ring is a commutative ring with 1 with the  
the property that for any element a we have 2a==0, a^2==a. There is a  
well known equivalence between the categories of Boolean rings and  
Boolean algebras, in which the And operation corresponds to  
multiplication and the Xor operation to addition. In particular, the  
Or operation can be written as

So by means of this identification we can "solve" such problems by  
using ordinary polynomial algebra modulo 2. Let me illustrate this on  
the two examples from the original message:

Let's first define an operation or in our ring, which will correspond  
to the usual Or:

or[a_, b_] := a*b + a + b;
or[a_, x__] := Expand[or[a, or[x]]] /; Length[{x}] > 1;

Now we have:

or[a, b, c]

b*a + b*c*a + c*a + a + b + b*c + c

We can deal with the first example immediately by using  

Last[PolynomialReduce[or[b1, a1]*or[b1, a2], {a1^2 - a1, a2^2 - a2,  
b1^2 - b1, a1*a2, a1 + a2 - 1}, Modulus -> 2]]

The second example is of course more problematic:

x = Last[PolynomialReduce[or[b1, a1, c1]*or[b2, a2, a1], {a1^2 - a1,  
a2^2 - a2, b1^2 - b1, b2^2 - b2, c1^2 - c1, a1*a2, a1 + a2 - 1}, {a2,  
a1}, Modulus -> 2]]

b1*a1 + b1*c1*a1 + c1*a1 + a1 + b1 + b1*c1 + c1

The answer is given in terms of (+), which corresponds to Xor so it  
is not immediately obvious that this is what we want but we can  
verify this easily;

x == or[b1, a1, c1]

So it would seem that this almost solves the problem except that we  
would like to be able to convert automatically the above expressions  
into Or form. As I have no time to think about this right now I think  
I will leave this to the readers ;-)

Andrzej Kozlowski

  • Prev by Date: General--Different Results
  • Next by Date: Re: Re: Color names and the 10 elementary colors?
  • Previous by thread: Re: Re: Boolean algebra
  • Next by thread: General--Series Command uses 100% of CPU