2

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?

Saturn
  • 7,191
  • 1
    You can group a 1, any number of times - that is in this the black "1" and the red "1" can be grouped together. Including a "1" multiple times is basically like ORing the corresponding term multiple times, which changes nothing. – tpb261 Jun 12 '14 at 08:32
  • @tpb261: Would it still be correct if I didn't group it with another $1$? – Saturn Jun 12 '14 at 09:10
  • It wouldn't be wrong, as in the truth table functionality would still be met, but the expression would not be optimal. In this case, for eg, if you leave the black 1 alone, it'll require four input AND gate, but if you combine it with Red 1, then you reduce the AND gates (of course OR gates increase) – tpb261 Jun 12 '14 at 09:37
  • 1
    Wait either your labeling or your ordering of the columns is not really amenable to KMaps. The usual order is like this: $b'c'$, $b'c$, $bc$, $bc'$ - only one of the symbols is changed, not both. In you case $b'c$ is becoming $bc'$ - a two symbol change. Try with the order I mentioned. – tpb261 Jun 12 '14 at 09:39

2 Answers2

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

thewillix
  • 11
  • 1
0

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.

skyking
  • 16,654