Saturday, July 11, 2009

Boolean expression simplification question

Would anybody be so kind to provide a direct proof of the following identity?

x · y + x · z + ~y · z = x · y + ~y · z

Thanks in advance.

PS: finally, I think I found a derivation using "integration factors" so to speak... but I am still interested in alternatives!

6 comments:

Stefan Schmiedl said...

It's been quite a while since I've done something like and might totally be wrong. Also I don't know what "integration factors" are, but kneading the expressions seems to work, too.

Claim:

x·y + x·z + ~y·z = x·y + ~y·z

Practically speaking: Can x·z influence the result of x·y + ~y·z?
The only way it could would be for the latter to be false and the former to be true, i.e.

~( x·y + ~y·z ) · (x·z) = 1

Let's rewrite the first expression:

~( x·y + ~y·z )
  = ~(x·y) · ~(~y·z)
  = ( ~x + ~y ) · ( ~~y + ~z )
  = ( ~x + ~y ) · ( y + ~z )
  = ~x·( y + ~z ) + ~y·( y + ~z )
  = ~x·y + ~x·~z + ~y·y + ~y·~z
  = ~x·y + ~x·~z + ~y·~z

Now our expression from above becomes

~( x·y + ~y·z ) · (x·z)
  = ( ~x·y + ~x·~z + ~y·~z ) · (x·z)
  = (~x·y)·(x·z) + (~x·~z)·(x·z) + (~y·~z)·(x·z)
  = ~x·x·y·z + ~x·x·~z·z + x·~y·~z·z
  = 0

i.e. it is always false, no matter the values of x,y,z. So your claim is true.

Andres said...

Ahhh, wonderful! Thank you! What I did was to compare

(x·y + x·z + ~y·z)(x·z)
(x·y + x·z + ~y·z)(~(x·z))

with

(x·y + ~y·z)(x·z)
(x·y + ~y·z)(~(x·z))

The resulting expressions are identical, and hence, the expressions on the left (should, I think) have the same behavior too. I tried finding a direct derivation and failed miserably... so I ended up using (x·z) as some sort of "integration factor". I almost used the term "summation factor" as it is used in Concrete Mathematics... sometimes, sum(f(x)) is impossible to find, but sum(kf(x)) is very easy and so k becomes a "summation factor".

By the way, a truth table analysis shows the claim is true... although I was looking for more than just a truth table "cheat" :).

Andres said...

Actually, more than "summation factor", it's more along the lines of verifying that the expressions on the left do not depend on (x·z) by "taking derivatives"...

Stefan Schmiedl said...

heh ... I did give the truth table proof a shot before I dove into symbol juggling :-)

And I seriously have to go dig out my copy of Concrete Mathematics ... it's been too long a time, since I worked on it.

Andres said...

Concrete Mathematics kicks ass.

Markus Gälli said...

or ask :
Wolfram Alpha

Concrete Mathematics is available online here.

Cheers

Markus