I am learning about Karnaugh maps to simplify boolean algebra expressions. I have this:
$$\begin{bmatrix}
& bc & b'c & bc' & b'c' \\
a & 0 & 1 & 1 & 0\\
a' & 1 & 1 & 0 & 1
\end{bmatrix}$$
There are no groups of four, so I am now looking for groups of two. I have highlighted the groups of two that I chose:
$$\begin{bmatrix}
& bc & b'c & bc' & b'c' \\
a & 0 & \color{red}1 & 1 & 0\\
a' & \color{blue}1 & \color{red}1 & 0 & \color{blue}1
\end{bmatrix}$$
One red, and another blue.
Now, there is one $1$ hanging over there. Normally, I would say that it will belong to a third group (of size one) and be done with it.
However, I remember the professor doing an example in which he was in a similar situation, but he actually joined the $1$ with another $1$ that was already grouped. I cannot recall his reasoning though.
What should I do?
Best Answer
Karnaugh maps require a particular ordering of the variables different from a normal truth table. Your K-map is ordered like a truth table: bc b'c bc' b'c' (or 11 01 10 00) whereas it has to be ordered such that only one variable changes going from one column (or row) to the next, and it is usually written with 00 on the left, namely 00 01 11 10 (or b'c' b'c bc bc'). When the K-map is arranged like this, any adjacent pair (or 4 or 8) allows the elimination of one (or 2 or 3) variables. Take as an example the two adjacent red "ones" in your table above (we can use the vertical axis of your table since the "a" variable is ordered correctly. The red "ones" mean (ab'c + a'b'c) which reduces to b'c(a+a'). a+a' is always true, ie equals 1, thus the expression reduces to b'c. So putting a ring around two adjacent "ones" eliminates the variable which has both its true and complement present. To proceed, we have to rewrite your table:
\begin{array}{ccccc} & 00 & 01 & 11 & 10\\ \hline 0 & 1 & 1 & 1 & 0\\ 1 & 0 & 1 & 0 & 1\\ \end{array} We see here three adjacent ones on the a' (a=$0$) line and two adjacent ones in the b'c column ($01$). We can make two pairs horizontally and one pair vertically. The centre "one" is shared by all three pairs. These three pairs represent a'b' + b'c + a'c. The remaining, single "one" (bottom right) represents abc'. Thus the minimised function is a'b' + b'c + a'c + abc'.