[Math] Convert boolean expression into SOP and POS

boolean-algebra

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.

Best Answer

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.