Karnaugh-Veitch Map.

Question

Reduce $F(X,Y,Z,W) = \sum (0,1,4,5,6,7,8,9,11,15)$ using Karnaugh-Veitch map.

$$\begin{array}{|c|c|c|c|c|}\hline_{xy}\backslash^{wz} & \overline Z \overline W \quad\scriptsize{00}& \overline Z W \quad\scriptsize{01}& ZW \quad\scriptsize{11}& Z\overline W \quad\scriptsize{10}\\ \hline \overline X \overline Y\quad\scriptsize{00}& 1 \qquad\scriptsize0& 1\qquad\scriptsize1 & 0\qquad\scriptsize3 &0 \qquad\scriptsize2 \\ \hline \overline X Y\quad\scriptsize{01}&1 \qquad\scriptsize4&1 \qquad\scriptsize5&1 \qquad\scriptsize7&1\qquad\scriptsize6\\ \hline X Y\quad\scriptsize{11}&0 \qquad\scriptsize12&0 \qquad\scriptsize13&1 \qquad\scriptsize15&0\qquad\scriptsize14\\ \hline X \overline Y\quad\scriptsize{10}&1\qquad\scriptsize8&1\qquad\scriptsize9&1\qquad\scriptsize11&0\qquad\scriptsize10\\ \hline \end{array}$$

• quad$[0,1,4,5] = \overline X\overline Z$

• quad$[4,5,7,6] = \overline XY$

• pair$[8,9] = X\overline Y\overline Z$

• pair$[15,11] = XZW$.

So $F = \overline X\overline Z + \overline XY + X\overline Y\overline Z + XZW$

---

Solution given in the book :-

• quad$[8,9,1,0] = \overline Y\overline Z$

• quad$[4,5,7,6] = \overline XY$

• pair$[15,11] = XZW$.

Hence $F = \overline Y\overline Z + XZW + \overline XY$.

Why did I get a different solution than given in the book ?

Answer 1

You have some redundancy in there. Your terms, visually, correspond to these blocks:

Note that 4 and 5 are covered with two blocks. Therefore, you had to cover 8 and 9 with an additional block.

The solution from the book uses these blocks:

(Remember that the blocks can "wrap around" the border). This solution is really minimal and has no redundancies, as it covers the $1$s with the smallest number of blocks.

_{Extended in response to the comments:}

The rules that must be followed when creating the groups are summarized at the (German version of) the Wikipedia site about Karnaugh-Veitch-Diagrams. I'll add the translations here, split into two parts: The "basic" rules are these:

• Neighboring/adjacent fields that contain a $1$ are summarized into groups
• A group may not contain a field that does not contain a $1$
• All $1$s must be contained in groups
• The groups may only have sizes that are powers of two (1, 2, 4, 8, 16, 32, 64...)
• The groups must be rectangular blocks
• The groups may wrap around the borders

The rules that are important in order to really find the minimal solution are:

• The groups must be as large as possible
• There must be as few groups as possible
• The groups may overlap
• Two groups may not contain the exact same set of $1$s
• No group may be fully contained in another group