[Solved]: Brackets in distributive law?

Problem Detail: 

The (second) distributive law in boolean algebra is defined as

$A + (B C) = (A + B) (A + C)$

But wouldn't it be correct to define it that way:

$(A + (B C)\, ) = (A + B) (A + C)$

Because if you transform

$(\sim D + \sim C) (\sim D + B + A) (C + \sim B + \sim A)$

to

$\sim D + (\sim C (B + A) \, ) (C + \sim B + \sim A)$

it would be incorrect since * has higher precedence than +, so

$(\sim D + (\sim C (B + A)\, )\, ) (C + \sim B + \sim A)$

would be correct, or am I totally mistaken?

Asked By : Benjoyo

Answered By : Luke Mathieson

The real problem is you're making a mistake with the precedence rules being used. The sentence: $$ (\lnot D + \lnot C)(\lnot D + B + A)(C + \lnot B + \lnot A) $$ is ambiguous until we add rules of precedence, or explicitly parenthesise it. Because logical $\mathsf{AND}$ is associative (and commutative), we normally ignore the fact that we have to decide, one way or the other, which of the two $\mathsf{AND}$s applies first.

The normal rules we use (when nothing else gets in the way, go left to right) implicitly parenthesises the sentence as: $$ [(\lnot D + \lnot C)(\lnot D + B + A)](C + \lnot B + \lnot A) $$

If we parenthesise in this explicit way, and apply the distributive law, then you get what you expect: $$ [\lnot D + \lnot C(B + A)](C + \lnot B + \lnot A) $$

If we changed our rules of precedence to right-to-left and thought about it as $$ (\lnot D + \lnot C)[(\lnot D + B + A)(C + \lnot B + \lnot A)] $$ then we can't apply the distributive law at all, we have to apply the associative property first, then we again get what you expect.

In general you have to remember that we often simplify mathematical notation to ease reading, so when you are manipulation expressions, you have to remember that we're leaving things out, or put them back in for clarity.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/39507

3.2K people like this

 Download Related Notes/Documents