### 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:

It's been

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

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

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

heh ... I

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

Concrete Mathematics kicks ass.

or ask :

Wolfram Alpha

Concrete Mathematics is available online here.

Cheers

Markus

Post a Comment