Homework Help: Boolean Algebra Equivalencies

1. Nov 4, 2012

twoski

1. The problem statement, all variables and given/known data

Prove the following through boolean algebra

x’y’z’ + xy’z + x’yz’ + xyz + xyz’ = x’z’ + yz’ + xz

x’y’w + x’yw + x’yzw’ = x’w + x’yz

xy’z + x’y’z + xyz

3. The attempt at a solution

Well i start by using the commutative law on the first one.

x’y’z’ + xyz + xy’z + x’yz' + xyz’ = x’z’ + yz’ + xz

At first i thought x’y’z’ + xyz might be something i can simplify, however it doesn't look like there are any boolean identities i can use on that.

With the second and third equivalency, i don't even know where to start. :/

Last edited: Nov 5, 2012
2. Nov 4, 2012

LCKurtz

For the second start by factoring x'w out of the first two terms.

3. Nov 4, 2012

twoski

Okay, so if i shuffle things around i get

y'x'w + yx'w

Could i use the idempotent law to get rid of x'w + x'w? I guess part of my confusion comes from not knowing how to use these laws when there are more variables involved.

4. Nov 4, 2012

LCKurtz

Apparently "shuffle things around" means use the commutative law for AND. It looks to me like you just copied the first two terms down. You haven't done what I suggested yet.

5. Nov 4, 2012

twoski

So i assume the distributive law allows us to do something like (y' + y)x'w

And of course it follows that y' + y = 1 by the inverse law, and (1)x'w can be simplified to x'w.

So now we have... x'w + x’yzw’ = x’w + x’yz

All i see is x' that can be factored....

x'( w + yzw' )

And i'm not sure if this is right, but we can simplify to:

x'( (1)yz ) = x'( yz ) = x'yz

Which means we'd also have to do the same to the RHS...

x'( w + yz )

But you can't do anything with that... So i get stuck there. Attempt 2:

x'w + x’yzw’ = x’w + x’yz

So obviously the only thing on the LHS that differs from the RHS is the w' so i want to try and get rid of it.

I'm going to guess x'w + x'w'yz can be simplified to x' + x'yz which is just x'yz... The same result.

The RHS has me confused with that w.

Last edited: Nov 4, 2012
6. Nov 4, 2012

LCKurtz

Good to there. Write that quantity in parentheses as (w + w'(yz)) and think about what a form (a + a'b) simplifies to.

7. Nov 4, 2012

twoski

The only law i can see that applies to (w + w'(yz)) is the inverse law, which just leaves me with x'yz again... Is that the goal?

If the LHS is x'yz then the RHS needs to be similar to that...

x'w + x'yz can simplify to x'(w + yz) but there's no way for me to get rid of w.

8. Nov 4, 2012

LCKurtz

How does that last expression compare to the RHS of the given problem?

9. Nov 4, 2012

twoski

If both sides have x'yz then i can just cancel them out and i'm left with x'w... Is that my simplified expression?

I've also made progress with the first question.

x’y’z’ + xy’z + x’yz’ + xyz + xyz’ = x’z’ + yz’ + xz

We factor:

x’y’z’ + xy’z + x’yz’ + xy(z + z') = x’z’ + yz’ + xz

By the inverse law:

x’y’z’ + xy’z + x’yz’ + xy = x’z’ + yz’ + xz

We factor again (after applying the commutative law):

x'z'(y + y') + xy'z + xy = x’z’ + yz’ + xz

By the inverse law:

x'z' + xy'z + xy = x’z’ + yz’ + xz

We factor again:

x'z' + x(y'z + y) = x’z’ + yz’ + xz

By the inverse law:

x'z' + xz = x’z’ + xz + yz’

So the first question leaves me with yz' if i cancel the similar expressions out...

Also, what can i do if i have the following (from a related question):

z(xy' + x'y' + xy)

I can't factor any further... Could i just totally remove x'y' + xy since they are canceled by the inverse law?

Last edited: Nov 4, 2012
10. Nov 4, 2012

LCKurtz

You are trying to show the left side of that top equation equals the right side. We have been working on the left side. Didn't we end up with the right side? Do you understand that it is done?

I'm going to leave the others to you.

11. Nov 4, 2012

twoski

But.. we didn't end up with the right side since the right side has 2 more variables than the left. I'm just confused as to what the next step is, i can cancel out the LHS and part of the RHS but then i'm left with x'w. I assumed proving this equivalency meant i would end up with something like x’yz = x’yz as a final result.

12. Nov 5, 2012

Staff: Mentor

To get a feel for what's inside the parentheses, you could draw up a truth table.

Otherwise, using algebra:

xy' + x'y' + xy

=(x + x')y' + xy

= y' + xy

= (x + 1)y' + xy

= xy' + y' + xy

= x(y' + y) + y'

= x + y'

13. Nov 5, 2012

twoski

Ah thanks, i managed to come to the same answer using a slightly different approach..

We factor:

y'(xz + x'z) + xyz

And we factor again:

y'( z(x + x') ) + xyz

Which simplifies to:

y'z + xyz

Factoring again:
z(y' + xy)

Distributive:

z( (y + y')(y' + x) )

Simplified:

z(y' + x)

Our result is:

zx + zy'

Now i'm just confused about the answers to the first 2 questions.

x'z' + xz = x’z’ + xz + yz’

x'yz = x'w + x'yz

I'm at the final step with them, i just can't for the life of me figure out how i am to show they are equivalent if the LHS clearly isn't equal to the RHS.

14. Nov 5, 2012

LCKurtz

Perhaps I have misunderstood what you have been thinking. We are working only on the left side. In post #5 about 5 lines down you had the LHS = x'(w+yzw'). In post #6 I said it was good to there and asked you to rewrite the quantity in parentheses like (w+w'(yz)). This would give LHS = x'(w+w'(yz)). Then I noted the quantity in parentheses has the form (a + a'b) and asked you to think about how that simplifies. This has nothing to do with the right hand side of the equation. I apparently misunderstood whether you have understood that. So what does the form a+a'b simplify to? Just answer that for me now.

15. Nov 5, 2012

twoski

a+a'b simplifies to a + b, which would leave us with LHS = x'w + x'yz. d'oh.

that law is sneaky, it seems pretty much the same as the inverse law.

16. Nov 6, 2012

Staff: Mentor

This is all solved now, is it?