# Simplification of a Boolean function

Let

$$f(x_1, x_2, x_3) := \sum m(2, 3, 4, 5, 6, 7)$$

With the normal SOP expression for this function, it must be, with the use of minterm:

$$f = m_2 + m_3 + m_4 + m _6 + m_7 = x_1'x_2x_3'+x_1'x_2x_3+x_1x_2'x_3'+x_1x_2x_3'+x_1x_2x_3$$

How can this function be simplified?

(I copied this exercise from a book. I think there should be a mistake because something is missing. Specifically, i looked author's solution for his exercise and i see that he added a term that you cannnot understand where it comes from. So, probably it's a mistake.)

This is the author's solution:

$$f = x_1'x_2(x_3'+x_3)+x_1'(x_2'+x_2)x_3'+x_1x_2(x_3'+x_3)\\ \qquad \quad = x_1'x_2+x_1x_3'+x_1x_2=(x_1'+x_1)x_2+x_1x_3'=x_2+x_1x_3'$$

So, is his solution correct or did he make a mistake?

• Shouldn't the expression contain also $m_5 = x_1x_2'x_3$...? – CiaPan Mar 29 '18 at 14:41
• You can use Karnaugh table to help you maybe – MysteryGuy Mar 29 '18 at 14:41

First, you're missing $m_5=x_1x_2'x_3$

To simplify, either use a Karnaugh Map, or us some handy-dandy equivalences principles like:

$PQ + PQ' = P$

For example, $x_1'x_2x_3'+x_1'x_2x_3=x_1'x_2$, $x_1x_2'x_31+x_1x_21x_3=x_1x_2$, and $x_1x_2x_3'+x_1x_2x_3=x_1x_2$

Applying those, we thus get: $x_1'x_2+x_1x_2'+x_1x_2$

And, combining $x_1x_21$ and $x_1x_2$ to just $x_1$ we thus get: $x_1'x_2+x_1$

Another very useful one is:

Reduction

$P+P'Q=P+Q$

So, once you have $x_2$ you can reduce $x_1'x_2+x_1$ to $x_1+x_2$

In sum:

$$x_1'x_2x_3'+x_1'x_2x_3+x_1x_2'x_3'+x_1x_2'x_3+x_1x_2x_3'+x_1x_2x_3\overset{Adjacency }=$$

$$x_1'x_2+x_1x_2'+x_1x_2\overset{Adjacency}=$$

$$x_1'x_2+x_1\overset{Reduction}=$$

$$x_2+x_1$$

If $m_5$ is not included, then we get:

$$x_1'x_2x_3'+x_1'x_2x_3+x_1x_2'x_3'+x_1x_2x_3'+x_1x_2x_3\overset{Adjacency }=$$

$$x_1'x_2+x_1x_2'x_3'+x_1x_2\overset{Adjacency}=$$

$$x_2+x_1x_2'x_3'\overset{Reduction}=$$

$$x_2+x_1x_3'$$

• I edited my post, can you give it a look? Thanks! – Κωνσταντίνος Κορναράκης Mar 29 '18 at 14:58
• @ΚωνσταντίνοςΚορναράκης The book's answer does not include $m_5$. If $m_5$ is included, the answer is $x_1+x_2$. If $m_5$ is not included, the answer is $x_2+x_1x_3'$ – Bram28 Mar 29 '18 at 15:04

Using SymPy:

>>> from sympy import *
>>> x1, x2, x3 = symbols('x1 x2 x3')
>>> f = (Not(x1) & x2 & Not(x3)) | (Not(x1) & x2 & x3) | (x1 & Not(x2) & Not(x3)) | (x1 & x2 & Not(x3)) | (x1 & x2 & x3)
>>> simplify(f)
Or(And(Not(x3), x1), x2)


which does match the author's solution. Adding the possibly missing term:

>>> f = (Not(x1) & x2 & Not(x3)) | (Not(x1) & x2 & x3) | (x1 & Not(x2) & Not(x3)) | (x1 & x2 & Not(x3)) | (x1 & Not(x2) & x3) | (x1 & x2 & x3)
>>> simplify(f)
Or(x1, x2)


which does match Bram's solution.