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