4
$\begingroup$

Convert the following expression into SOP (sum of products) and POS (product of sums) canonical forms using boolean algebra method:

$(ac + b)(a + b'c) + ac$

Attempt at solution:

$(ac + b)(a + b'c) + ac$

  1. $(a + b)(c + b)(a + b')(a + c) + ac$

  2. $...$

  3. $...$

I'm stuck at this point. Any help would be greatly appreciated. Thanks.

$\endgroup$
8
$\begingroup$

One way to get the SoP form starts by multiplying everything out, using the distributive law:

$$\begin{align*} (ac+b)(a+b'c)+ac&=ac(a+b'c)+b(a+b'c)+ac\\ &=aca+acb'c+ba+bb'c+ac\\ &=ac+ab'c+ab+ac\\ &=ac+ab'c+ab\;. \end{align*}$$

Then make sure that every term contains each of $a,b$, and $c$ by using the fact that $x+x'=1$:

$$\begin{align*} ac+ab'c+ab&=ac(b+b')+ab'c+ab(c+c')\\ &=abc+ab'c+ab'c+abc+abc'\\ &=abc+ab'c+abc'\;. \end{align*}$$

Alternatively, you can make what amounts to a truth table for the expression:

$$\begin{array}{cc} a&b&c&ac+b&b'c&a+b'c&ac&(ac+b)(a+b'c)+ac\\ \hline 0&0&0&0&0&0&0&0\\ 0&0&1&0&1&1&0&0\\ 0&1&0&1&0&0&0&0\\ 0&1&1&1&0&0&0&0\\ 1&0&0&0&0&1&0&0\\ 1&0&1&1&0&1&1&1\\ 1&1&0&1&1&1&0&1\\ 1&1&1&1&0&1&1&1 \end{array}$$

Now find the rows in which the expression evaluates to $1$; here it’s the last three rows. For a product for each of those rows; if $x$ is one of the variables, use $x$ if it appears with a $1$ in that row, and use $x'$ if it appears with a $0$. Thus, the last three rows yield (in order from top to bottom) the terms $ab'c$, $abc'$ and $abc$.

You can use the truth table to get the PoS as well. This time you’ll use the rows in which the expression evaluates to $0$ — in this case the first five rows. Each row will give you a factor $x+y+z$, where $x$ is either $a$ or $a'$, $y$ is either $b$ or $b'$, and $z$ is either $c$ or $c'$. This time we use the variable if it appears in that row with a $0$, and we use its negation if it appears with a $1$. Thus, the first row produces the sum $a+b+c$, the second produces the sum $a+b+c'$, and altogether we get

$$(a+b+c)(a+b+c')(a+b'+c)(a+b'+c')(a'+b+c)\;.\tag{1}$$

An equivalent procedure that does not use the truth table is to begin by using De Morgan’s laws to negate (invert) the original expression:

$$\begin{align*} \Big((ac+b)(a+b'c)+ac\Big)'&=\Big((ac+b)(a+b'c)\Big)'(ac)'\\ &=\Big((ac+b)'+(a+b'c)'\Big)(a'+c')\\ &=\Big((ac)'b'+a'(b'c)'\Big)(a'+c')\\ &=\Big((a'+c')b'+a'(b+c')\Big)(a'+c')\\ &=(a'b'+b'c'+a'b+a'c')(a'+c')\\ &=a'b'(a'+c')+b'c'(a'+c')+a'b(a'+c')+a'c'(a'+c')\\ &=a'b'+a'b'c'+a'b'c'+b'c'+a'b+a'bc'+a'c'+a'c'\\ &=a'b'+a'b'c'+b'c'+a'b+a'bc'+a'c+a'c'\\ &=a'b'+b'c'+a'b+a'(c+c')\\ &=a'b+b'c'+a'b+a'\\ &=b'c'+a'\;, \end{align*}$$

where in the last few steps I used the absorption law $x+xy=x$ a few times. Now find the SoP form of this:

$$\begin{align*} b'c'+a'&=b'c'(a+a')+a'(b+b')(c+c')\\ &=ab'c'+a'b'c'+a'b(c+c')+a'b'(c+c')\\ &=ab'c'+a'b'c'+a'bc+a'bc'+a'b'c+a'b'c'\\ &=ab'c'+a'b'c'+a'bc+a'bc'+a'b'c\;. \end{align*}$$

Now negate (invert) this last expression, and you’ll have the PoS form of the original expression:

$$\begin{align*} (ab'c'&+a'b'c'+a'bc+a'bc'+a'b'c)'\\ &=(ab'c')'(a'b'c')'(a'bc)'(a'bc')'(a'b'c)'\\ &=(a'+b+c)(a+b+c)(a+b'+c')(a+b'+c)(a+b+c')\;, \end{align*}$$

which is of course the same as $(1)$, though the factors appear in a different order.

$\endgroup$
  • $\begingroup$ Are you aware of an automated tool that does this job (efficiently)? $\endgroup$ – pushpen.paul Dec 24 '18 at 1:18

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.