UTT- Boolean Algebra Equivalence

[Ithryndil]

Ok, I am having a difficult time with the following problem. I am to show that the two sides are equal.

x1'x3 + x1x2x3' +x1'x2+x1x2' = x2'x3+x1x3'+x2x3'+x1'x2x3

For the LHS I can simplify it to:
x2(x1'+x1x3') + x1'x3 + x1x2'
x2x1' + x2x3' + x1'x3 + x1x2'
x1'x3 + x2x3' + x1x2'

For the RHS I can simplify to:
x2(x3' + x1'x3) + x2'x3 + x1x3'
x2x3' + x2x1' + x2'x3 + x1x3'
x1'x3 + x1'x2 + x2x3

At this point I am stuck. I know that both sides should be equal. I have to do this algebraically, so using a truth table is out of it.

 

[Elucidus]

In order to show two Boolean expressions to be equal, it suffices to show they can be transformed into equivalent forms. The most rudimentary way is to find their complete-sum-of-products form (aka disjunctive normal form DNF).

When the number of variable is small, a Karnaugh map is also useful.

Removing the distraction of subscripts by letting x = x1, y = x2, and z = x3:

You need to show that x'z + xyz' + x'y + xy' = y'z + xz' + yz' + x'yz.

When finding the "completed" version of a fundamental product recall that

ab = ab(1) = ab(c + c') = abc + abc'

and then delete extra identical summands.

Or show that both expressions have the same Karnaugh map.

\begin{array}{c|c|c|c|c}<br /> &amp; yz &amp; yz&#039; &amp; y&#039;z&#039; &amp; y&#039;z \\<br /> \hline<br /> x &amp; &amp; \checkmark &amp; \checkmark &amp; \checkmark \\<br /> x&#039; &amp; \checkmark &amp; \checkmark &amp; &amp; \checkmark \\<br /> \end{array}<br />

When the number of variables increases things get more difficult.

--Elucidus

 

[Kenneth Mann]

I hope this isn't too late.
Also, I agree with ELUCIDUS about removing subscripts and making it easier, so I'll use his.

Hint:
You don't always have to minimize first. You can start out by expanding terms, such as:

X'Z = X'YZ + X'Y'Z
Then you can re-combine terms, then minimize. Try it!~

KM