Re: Re: Boolean algebra
- To: mathgroup at smc.vnet.net
- Subject: [mg69435] Re: [mg69417] Re: Boolean algebra
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Tue, 12 Sep 2006 06:53:22 -0400 (EDT)
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
a*b+a+b
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
PolynomialReduce:
Last[PolynomialReduce[or[b1, a1]*or[b1, a2], {a1^2 - a1, a2^2 - a2,
b1^2 - b1, a1*a2, a1 + a2 - 1}, Modulus -> 2]]
b1
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]
True
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