MathGroup Archive 2005

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

Search the Archive

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

  • To: mathgroup at smc.vnet.net
  • Subject: [mg62103] Re: [mg62054] Re: ((a&&b)||c)==((a||c)&&(b||c))
  • From: "Steven T. Hatton" <hattons at globalsymmetry.com>
  • Date: Fri, 11 Nov 2005 02:52:18 -0500 (EST)
  • References: <dksdln$h87$1@smc.vnet.net> <200511100750.CAA07295@smc.vnet.net> <43736392.1010702@wolfram.com>
  • Sender: owner-wri-mathgroup at wolfram.com

On Thursday 10 November 2005 10:13 am, Daniel Lichtblau wrote:
> Steven T. Hatton wrote:

> > 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. 


No. I mean that you can build two distinct parse trees which when joined with 
a biconditional connective evaluate to True.  In order to compare statements 
of symbolic logic, the program using parse trees would have to be able to 
backtrack, and try alternative trees for each side of the expression until it 
evaluated to a definite value, or had conclusively exhausted all 
laternatives.

> 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.)

I understand why equals groups as it does.  It is being used in the sense of 
programming, not in the sense of a biconditional.  I believe Richard Fateman 
explained, in part, why this is happening.

> 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.

I guess I never got around to posting my question about Karnaugh maps. But I 
will now conclude that Mathematica does not have any built-in capability for 
evaluating Karnaugh maps.  

> 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.

I found a notebook on the WRI site implementing some kind of logical 
operations using ring theory, but I can't say I've studied it.  While I was 
poking around, I did find several sources which look helpful. Thanks for 
reminding me about Quine.  It's been a very long time since I thought about 
this stuff in depth.

Steven


  • Prev by Date: Re: To be or not to be...
  • Next by Date: Tilting at Windmills?
  • Previous by thread: Re: Re: ((a&&b)||c)==((a||c)&&(b||c))
  • Next by thread: Reals and Equal