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