Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Can't Simplify logical expression

• To: mathgroup at smc.vnet.net
• Subject: [mg90836] Re: [mg90790] Can't Simplify logical expression
• From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
• Date: Fri, 25 Jul 2008 06:19:16 -0400 (EDT)
• References: <200807240853.EAA18974@smc.vnet.net>

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

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