MathGroup Archive 2006

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

Search the Archive

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


  • Prev by Date: Re: parenthesis in reactions...
  • Next by Date: extract homogenous solution from DSolve?
  • Previous by thread: Re: Boolean algebra
  • Next by thread: Re: Re: Boolean algebra