Boolean algebra - is it possible to simplify this expression to 0

Tags:
1. Sep 27, 2016

Rectifier

The problem
I have been trying to solve a long problem but my answer differs from my books answer with just a few peculiar terms.

$x_1' \vee x_0'x_1x_2 \vee x_0x_1'x_2' \vee x_2$

Book:
$x_1' \vee x_2$

My question is:
Is it possible to simplify $x_0'x_1x_2 \vee x_0x_1'x_2'$ to 0?

The attempt at a solution
I tried rewriting $x_1x_2$ on both side using deMorgan's laws but that didn't lead anywhere. I have also tried writing different combinations of terms as product using the consensus law but that extra element which is created always becomes 0 so there is no point in doing that either.

2. Sep 27, 2016

Staff: Mentor

Can you show the original problem and the work you did to get your answer?

There may be an error in your derivation.

One thing you can try is compare the book answer truth table to the original one that you started with.

3. Sep 27, 2016

Rectifier

Should I create a new thread?

4. Sep 27, 2016

Staff: Mentor

No, its part of this problem, right? and so it should go in this thread, right?

5. Sep 27, 2016

Rectifier

This is not a complete solution since it would take too long time to write it down here.

I will edit this post tomorrow since I am of to bed.

I am trying to simplify ("minimize") this:
$x_0'x_1'x_2' \vee x_0'x_1'x_2 \vee x_0'x_1x_2 \vee x_0x_1'x_2' \vee x_0x_1'x_2 \vee x_0x_1x_2$

This part below may be wrong------

Distribution for two first and last terms.

$x_0'x_1' \vee x_0'x_1x_2 \vee x_0x_1'x_2' \vee x_0x_2$

Producing consensus term from two of the terms $x_0x_1'x_2' \vee x_0x_2 = x_0x_1'x_2' \vee x_0x_2 \vee x_0x_1'$

Moving terms around and producing a consensus term from the combination of $x_0x_1'x_2' \vee x_0x_2 = x_0x_1'x_2' \vee x_0x_2 \vee x_0x_0x_2'$

$x_0'x_1' \vee x_1'x_2 \vee x_0x_1' \vee x_0x_2 \vee x_0'x_1x_2 \vee x_0x_1'x_2'$

Last edited: Sep 27, 2016
6. Sep 27, 2016

Staff: Mentor

One way to answer this is to draw a Truth Table.

7. Sep 28, 2016

Staff: Mentor

I converted your expression to x, y, z and using + and * for OR and AND operations.

Starting with the expression:

$x'y'z' + x'y'z + x'yz + xy'z' + xy'z + xyz$

I noticed a pattern that 3 terms have x and three have x' allowing this simplification

$x' * ( y'z' + y'z + yz ) + x * ( y'z' + y'z + yz )$

an then to:

$( x' + x ) * ( y'z' + y'z + yz )$

Since $(x' + x)$ always evaluates to 1, the expression reduces to:

$( y'z' + y'z + yz )$

From here we can rearrange it again to: $( y' * (z' + z) + yz )$

and from there a truth table or the identity $( p + qr ) = ( p + q ) * ( p + r )$ known as the absorbtion law may help.

Last edited: Sep 28, 2016
8. Sep 28, 2016

jbriggs444

Back in the 70's we were taught a graphical technique for simplifying using Truth Tables. https://en.wikipedia.org/wiki/Karnaugh_map

Another way to attack the problem at hand is to look at your answer:

$x_1' \vee x_0'x_1x_2 \vee x_0x_1'x_2' \vee x_2$

If $x_2$ holds then the expression as a whole will be true and the rest of the expression does not matter. Putting that another way, it is only if $x_2$ fails to hold that one need consider any of the other terms. But if $x_2$ fails to hold then $x_0'x_1x_2$ cannot hold. So one can simply discard that term.

That's rather informal and may be unconvincing. But you can formalize it: Rewrite the expression as $x_1' \vee x_0x_1'x_2' \vee ( x_0'x_1x_2 \vee x_2 )$

Then look at that last term and use the distributive law to rewrite it as $(x_0'x_1 \vee 1)x_2$ The next steps are obvious.

See if you can apply this same set of manipulations to $x_1'$.

9. Sep 28, 2016

Rectifier

Thank you for your replies! Couldn't solve this problem for several hours at home but somehow managed to solve it on the bus. Yey brain!

If somene else has the same problem as me use the distribution rule on the last step and you will be able to get the final answer.