Re: Re: Boolean algebra

*To*: mathgroup at smc.vnet.net*Subject*: [mg69407] Re: [mg69385] Re: [mg69373] Boolean algebra*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Mon, 11 Sep 2006 05:38:58 -0400 (EDT)

On 10 Sep 2006, at 20:19, Andrzej Kozlowski wrote: > > On 10 Sep 2006, at 14:14, Andrzej Kozlowski wrote: > > >> >> On 9 Sep 2006, at 16:26, Menace wrote: >> >> >>> I'd like to solve the following problem in Mathematica, >>> >>> Given are the following preliminaries: >>> (a1 || a2)=True >>> (a1 && a2) = False >>> >>> Then, given the following conjunctive normal form: >>> >>> (b1 || a1) && (b1 || a2) >>> >>> This can be simpliefied to: b1 || (a1 && a2) >>> >>> Given the prelininaries I'd like Mathematica to simplify this to: >>> b1. >>> However, I cant figure out how to do this. I tried the following: >>> >>> prelims := {(a1 && a2) -> False, (a1 || a2) -> True}; >>> f1 := (b1 || a2) && (b1 || a1); >>> Simplify[f1] /. prelims >>> >>> and this seems to work. However >>> >>> f2 := (b1 || a1 || c1) && (b2 || a2 || a1); >>> Simplify[f2] /. prelims >>> >>> evaluates to: (b1 || a1 || c1) && (b2 || a2 || a1) instead of b1 >>> || a1 >>> || c1. >>> The reason of this seems to be the order in which a2 and a1 occur in >>> f2. How can I make sure it works regardless of the order of a1 and >>> a2? >>> >>> >> >> >> I seems to me that in general it will be pretty hard to use >> Mathematica for this sort of Boolean algebra without some AddOn >> package. However, your particular cases are very easy. Note that >> your assumptions amount simply to one assumption: >> >> In[1]:= >> a2 = Not[a1]; >> >> Now we have: >> >> In[2]:= >> Simplify[ (b1 || a2) && (b1 || a1)] >> >> Out[2]= >> b1 >> >> >> In[3]:= >> Simplify[(b1||a1||c1)&&(b2||a2||a1)] >> >> Out[3]= >> a1||b1||c1 >> >> >> >> Andrzej Kozlowski >> Tokyo, Japan >> > > > If you do not wish to use a global identity, you can use instead > Simplify with assumptions: > > Simplify[(b1 || a2) && (b1 || a1), a2 = !a1 ] > b1 > Simplify[(b1 || a1 || c1) && (b2 || a2 || a1), a2 = !a1] > a1 || b1 || c1 > > Andrzej Kozlowski > Tokyo, Japan > > This is obviously no improvement on my first answer: I mistakenly used = in the assumption to Simplify while I meant to use ==. But using == of course does not work; if one wanted to use Simplify with assumptions the right thing to do would be to use something like: Simplify[ (b1 || a2) && (b1 || a1),Implies[a2,Not[a1]]&&Implies[Not [a1],a2]] b1 Unfortunately: Simplify[(b1 || a1 || c1) && (b2 || a2 || a1), {Implies[a2, !a1], Implies[ !a1, a2]}] = (b1 || a1 || c1) && (b2 || a2 || a1) It is not surprising that Simplify can't deal with this sort of problem; since some sort of general elimination algorithm would be required and I am not even sure if anything like it exists for general Boolean algebras (does anyone know?). In any case, reducing the number of variables manually seems to be the best procedure I can suggest. If one does not wish to use a global identity one can do this with Block: Block[{a2 = !a1}, Simplify[(b1 || a2) && (b1 || a1)]] b1 Block[{a2 = !a1}, Simplify[(b1 || a1 || c1) && (b2 || a2 || a1)]] a1 || b1 || c1 Andrzej Kozlowski