Re: Can't Simplify logical expression

*To*: mathgroup at smc.vnet.net*Subject*: [mg90815] Re: [mg90790] Can't Simplify logical expression*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Fri, 25 Jul 2008 06:14:32 -0400 (EDT)*References*: <200807240853.EAA18974@smc.vnet.net> <F47D80C9-52F3-40F8-875C-C95E1E0E9743@mimuw.edu.pl>

On 24 Jul 2008, at 13:12, Andrzej Kozlowski wrote: > > On 24 Jul 2008, at 10:53, realyigo at gmail.com wrote: > >> Simplify[(a && (! b)) || (b && (! a))] >> >> I get this: >> a && ! b || b && ! a >> >> But I want this: >> Xor[a,b] >> >> >> Any suggestions? >> > > > What you are asking for is "the inverse" of: > > LogicalExpand[Xor[a, b]] > (a && ! b) || (b && ! a) > > but Mathematica has no built in functions for doing this. It is > possible to implement a function that would do this by using the > equivalence between Boolean algebras and Boolean rings and the > Groebner Basis algorithm modulo 2, as I described a 2006 post on > this forum: > > http://forums.wolfram.com/mathgroup/archive/2006/Sep/msg00266.html > > The idea is to work in a ring (with 1) with two generators a and b, > and relations 2a = 0, 2 b = 0, a^2=a,b^2=b. The element a of the > ring corresponds to the logical statment a, the element b to the > logical statement b, the element 1-a to !a, 1-b to !b. The product * > corresponds to And and the sum + to Xor. Logical Or[a,b] > corresponds to a*b+a+b hence your statement (a && ! b) || (b && ! > a) corresponds to: > > a*(1 - b) + (1 - a)*a*b*(1 - b) + (1 - a)*b > > Now we can use GroebnerBasis and PolynomialReduce to simplify this, > using the relations ^2=a,b^2=b: > > Last[PolynomialReduce[p, {a^2 - a, b^2 - b}, {a, b}, Modulus -> 2]] > a + b where, of course, p = a*(1 - b) + (1 - a)*a*b*(1 - b) + (1 - a)*b Andrzej Kozlowski > > > This corresponds to Xor[a,b], so we got what we wanted. > > It should not be too not too hard to write a package to do all this > automatically. > > Andrzej Kozlowski > >

**References**:**Can't Simplify logical expression***From:*realyigo@gmail.com