What to do with a hanging $1$ in a Karnaugh map?

Question

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?

Answer 1

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'.

Answer 2

As pointed out you need to order the rows and columns properly so that adjacent cells differ only in one variable. If your labeling is correct you need to swap the rightmost two columns for this (then of course it's customary to order the columns 00, 01, 11 and 10, but that's not necessary for the working of the diagram).

If it's just a typo in the labeling and the table is indeed correct you will have fx:

$\begin{matrix} & BC & C && B \\ A & 0 & 1 & 1 & 0\\ & 1 & 1 & 0 & 1\\ \end{matrix}$

Now you can find four groupings of two cells (which are prime implicants), the the terms are $A\overline B+C\overline B+C\overline A+B\overline A$. Next step is to identify the essential implicants which is $A\overline B$ (because it's the only one covering $A\overline B\overline C$) and $B\overline A$ (because it's the only one covering $\overline AB\overline C$. The other two terms/groups are not essential, but one of them has to be choosen - there's no reason to choose one over the other so you can just pick one of:

$A\overline B+C\overline A+B\overline A$

$C\overline B+C\overline A+B\overline A$

The way you went wrong is first when you went for the red group second. Normally you go for essential prime implicants first (which will mean that they don't have a matching neighbor outside the group). The second error is that you should always aim for the largest possible groups (that is prime implicants) - even if you allowed the first error to slip you will anyway have to use a group of two for the hanging 1.

You will have a hanging one anyway if you do it correctly:

$\begin{matrix} & BC & C && B \\ A & 0 & \color{red}1 & \color{red}1 & 0\\ & \color{green}1 & 1 & 0 & \color{green}1\\ \end{matrix}$

now the black one could be combined with either its red or green neighbor and since it can it should to be combined.