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

Re: Re: ((a&&b)||c)==((a||c)&&(b||c))

• To: mathgroup at smc.vnet.net
• Subject: [mg62095] Re: [mg62054] Re: ((a&&b)||c)==((a||c)&&(b||c))
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Fri, 11 Nov 2005 02:51:58 -0500 (EST)
• References: <dksdln$h87$1@smc.vnet.net> <dkshui$jki$1@smc.vnet.net> <200511100750.CAA07295@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Steven T. Hatton wrote:
> Peter Pein wrote:
> 
> 
>>But Mathematica does:
>>
>>In[1]:= expr = ((a && b) || c) == ((a || c) && (b || c))
>>Out[1]= ((a && b) || c) == ((a || c) && (b || c))
>>In[2]:= LogicalExpand /@ expr
>>Out[2]= True
> 
> 
> However:
> 
> In[1]:= expr = ((a && b) || c) == (a || c) && (b || c);
> LogicalExpand /@ expr
> Out[1]:= ((a && b) || c) == (a || c) && (b || c)
> 
> I believe the reason Mathematica is having a hard time with this

I do not know what you mean by "having a hard time". If you mean it 
fails to alter the "right hand side", that may be due to operator 
precedence not being quite as (I think) you had intended.

In[5]:= FullForm[expr]
Out[5]//FullForm= And[Equal[Or[And[a, b], c], Or[a, c]], Or[b, c]]

The head is And, and the right hand side is Or[b,c]. Your Equal is 
inside the left hand side. Equal has higher precedence than the logical 
operators And and Or, but lower than the arithmetic operators Plus and 
Times. One reason may be an artifact of our own use of logical operators 
and LogicalExpand. Specifically, Equal is used in equation solving, and 
equation systems often need to be put into a convenient form for further 
processing (Or of Ands. More on this below.)

To do what I think you had in mind, make the grouping explicit.

Out[6]= ((a && b) || c) == ((a || c) && (b || c))

In[7]:= Map[LogicalExpand, expr]
Out[7]= True


> is because
> the rules of combining logical operators cannot be expressed in terms of a
> strict precedence hierarchy.  I particular the distributive laws:
> 
> (P && (Q || R)) <=> ((P && Q) || (P && R))
> (P || (Q && R)) <=> ((P || Q) && (P || R))

These dual distributive laws do not preclude the existence of canonical 
forms with a strict precedence between And and Or. Disjunctive Normal 
Form (DNF) and Conjunctive Normal Form (CNF) come close to being 
canonical. Application of the Quine-McCluskey algorithm to DNF can 
provide a canonical form. LogicalExpand does not do this, but what it 
gives is often reasonably close.

If instead you work with Not, And, and Xor, then you have an isomorphism 
to a polynomial boolean algebra (work modulo 2, with all indeterminates 
satisfying x^2==x). In this case the usual polynomial simplification 
will be canonical. One reason one might wish to avoid going in this 
direction is that logical expressions are often formed naturally from 
Not, And, and Or. Conversion to Xor has the unfortunate effect of 
blowing up the size.


Daniel Lichtblau
Wolfram Research

• References:
  • Re: ((a&&b)||c)==((a||c)&&(b||c))
    • From: "Steven T. Hatton" <hattons@globalsymmetry.com>