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:


Can anyone tell me where I went wrong?

  • $\begingroup$ Next time, put the question and answer here directly, or at least a summary, rather than using links to external images $\endgroup$ – HackerBoss Oct 10 '18 at 23:49
  • $\begingroup$ You did't quite go wrong. You just missed one simplification. The $x_1\bar{x}_2$ term is redundant. $\endgroup$ – Fabio Somenzi Oct 10 '18 at 23:57
  • $\begingroup$ You're right, but how is x1x2' redundant? I don't quite see it... $\endgroup$ – StaticCrazee Oct 11 '18 at 0:07
  • $\begingroup$ 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. $\endgroup$ – Fabio Somenzi Oct 11 '18 at 5:16
  • $\begingroup$ @FabioSomenzi Yes, I've clearly missed that! A little reordering and consensus was the key. Thanks! $\endgroup$ – 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.

  • $\begingroup$ Thanks for answering. The missing steps is where I'm stuck. For instance, where'd the ab' disappear to? $\endgroup$ – StaticCrazee Oct 11 '18 at 2:46
  • $\begingroup$ Look carefully at the three statements in brackets. Do you notice any thing? [Hint: idempotence] @StaticCrazee $\endgroup$ – 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$.

  • $\begingroup$ Not the most complete answer $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.