       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:= expr = ((a && b) || c) == ((a || c) && (b || c))
>>Out= ((a && b) || c) == ((a || c) && (b || c))
>>In:= LogicalExpand /@ expr
>>Out= True
>
>
> However:
>
> In:= expr = ((a && b) || c) == (a || c) && (b || c);
> LogicalExpand /@ expr
> Out:= ((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:= FullForm[expr]
Out//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= ((a && b) || c) == ((a || c) && (b || c))

In:= Map[LogicalExpand, expr]
Out= 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

```

• Prev by Date: Re: Re: Re: Mathematica 1
• Next by Date: Re: Re: Timing runs for the last part of my previous post
• Previous by thread: Re: ((a&&b)||c)==((a||c)&&(b||c))
• Next by thread: Re: Re: ((a&&b)||c)==((a||c)&&(b||c))