Boolean simplification gives two different results

Here is the question I'm trying to solve:

Use algebraic manipulation to find the minimum sum-of-products expression for the function $$f=x_1x_3+x_1\overline{x}_2+\overline{x}_1x_2x_3+\overline{x}_1\overline{x}_2\overline{x}_3$$

The way I attempted it was as follows:

f = ac + ab' + a'bc + a'b'c'
= ac + b'(a + a'c') + a'bc   [distributive]
= c(a + a'b) + b'(a + a'c')  [distributive]
= c(a + b) + b'(a + c')      [using x + x'y = x + y]
= ac + bc + ab' + b'c'

where a = x1, b = x2, c = x3

The correct answer, however is:

$$f=x_1x_3+x_2x_3+\overline{x}_2\overline{x}_3$$

Can anyone tell me where I went wrong?

• Next time, put the question and answer here directly, or at least a summary, rather than using links to external images – HackerBoss Oct 10 '18 at 23:49
• You did't quite go wrong. You just missed one simplification. The $x_1\bar{x}_2$ term is redundant. – Fabio Somenzi Oct 10 '18 at 23:57
• You're right, but how is x1x2' redundant? I don't quite see it... – StaticCrazee Oct 11 '18 at 0:07
• One way to see it is in user10354138's answer. Another way is to note that it is the consensus term of the first and third terms. Consensus terms are redundant. – Fabio Somenzi Oct 11 '18 at 5:16
• @FabioSomenzi Yes, I've clearly missed that! A little reordering and consensus was the key. Thanks! – StaticCrazee Oct 11 '18 at 16:23

\begin{align} &ac + bc + ab' + b'c'\\=~&bc +~ ac + ab' + b'c'\\ =~& bc+~(abc+ab'c)+(ab'c+ab'c')+(ab'c'+a'b'c')\\\vdots~~& \\ =~& bc+~ac+b'c'\\=~& ac+bc+b'c' \end{align}

Complete the missing steps, and you are done.

• Thanks for answering. The missing steps is where I'm stuck. For instance, where'd the ab' disappear to? – StaticCrazee Oct 11 '18 at 2:46
• Look carefully at the three statements in brackets. Do you notice any thing? [Hint: idempotence] @StaticCrazee – Graham Kemp Oct 11 '18 at 3:50

You haven't simplified it completely: $$x_1\bar{x_2}=x_1\bar{x_2}(x_3+\bar{x_3})=x_1\bar{x_2}x_3+x_1\bar{x_2}\bar{x_3}.$$ The first term contains $$x_1x_3$$ and the second term contains $$\bar{x_2}\bar{x_3}$$. So $$x_1\bar{x_2}$$ is redundant in your $$f$$.

• Not the most complete answer – HackerBoss Oct 11 '18 at 0:02

Karnough maps are more standard and consistent than algebra, but algebra works too. You are almost there. Observe that bc + b'c' is true iff b$$\equiv$$c. If this is the case, then ac + ab'$$\iff$$a(c+b')$$\iff$$a. On the other hand, if bc + b'c' is false, then b$$\equiv$$c' and ac + ab'$$\iff$$a(c+b')$$\iff$$ac. So either the bc + b'c' term makes the expression true, or ac + ab' is equivalent to just ac.

• Thanks for answering. But that doesn't match the answer? – StaticCrazee Oct 11 '18 at 0:06