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>