Boolean Algebra Karnaugh Maps

Question

I'm having trouble solving this:

Simplify the expression F = W'X'Y'Z' + W'X'YZ' + WX'Y'Z' + WX'YZ' + WXYZ + W'XYZ using a Karnaugh Map.

The book I have very poorly describes how to do Karnaugh Maps. I'd appreciate any help.

Answer 1

As pointed out this is easily simplified without using Karnaugh maps, but one should note that this simplification need not leave disjunctive normal forms for more than one step, and a Karnaugh map is just another representation of just that.

What you do is first to use distributive law and then absorbtion law, that is $AB+A\overline B = A(B+\overline B) = A$, in the Karnaugh table this mean to join two adjecent congruent groupings into one.

In your example this would be:

$\overline W\overline X\overline Y\overline Z + \overline W \overline X Y\overline Z + W\overline X\overline Y\overline Z + W\overline XY\overline Z + WXYZ + \overline WXYZ$

that is only groupings of one cell. The Karnaugh map is:

$\begin{matrix} & & W & WZ & Z \\ & A & B & & \\ X & C & D & & \\ XY &&& E & F\\ Y & \\ \end{matrix}$

I've labeled the cells that contains ones (and left zeroes blank) to ease the explaination. Now one would easily see that A, B, C and D can be grouped into one group and E and F into one, but to use the above law we do the first in two steps. First we group A+B, C+D and E+F, the corresponding operation on the expression would be (lets first order the terms):

${\overline W\overline X\overline Y\overline Z}^A + {W\overline X\overline Y\overline Z}^B + {\overline W \overline X Y\overline Z}^C + {W\overline XY\overline Z}^{D} + {\overline WXYZ}^E+{WXYZ}^F$

Now combining the grops A+B, C+D and E+F:

${\overline X\overline Y\overline Z}^{A+B} + {\overline X Y\overline Z}^{C+D} + {XYZ}^{E+F}$

Now you have three congruent groupings, but only A+B and C+D are adjecent so we can group them together and have the groups A+B+C+D and E+F, in the expression this will be:

${\overline XY\overline Z}^{A+B+C+D} + {XYZ}^{E+F}$

This is just the first step of Quine-McCluskey algorithm.

Next is to identify essential implicants which in the Karnaugh table means cells that are only covered with one grouping and eliminate redundant implicants (groups in the Karnaught table or terms in the expression). In the Karnaugh table this means removing groups that are covered by two or more other groups, in the expression this means using the consensus rule.

If you consider it your way to solve this through the expression it will not use other than these two steps and therefore they (algebraic manipulation, Kernaugh table and Quine-McCluskey algorithm) are just different ways to represent the same method.

Answer 2

The Karnaugh map looks like this:

\begin{array}{|c|c|c|c|c|}\hline \large wx\backslash yz\normalsize &00 &01 &11 &10 \\\hline 00 &1 &0 &0 &1 \\ 01 &0 &0 &1 &0 \\ 11 &0 &0 &1 &0 \\ 10 &1 &0 &0 &1 \\\hline \end{array}

There are two simplifications we can make:

\begin{array}{|c|c|c|c|c|}\hline \large wx\backslash yz\normalsize &00 &01 &11 &10 \\\hline 00 &\color{red}1 &0 &0 &\color{red}1 \\ 01 &0 &0 &\color{blue}1 &0 \\ 11 &0 &0 &\color{blue}1 &0 \\ 10 &\color{red}1 &0 &0 &\color{red}1 \\\hline \end{array} In $\color{red}{\text{red}}$ we have $$\overline w\overline x\overline y \overline z + \overline w \overline x y \overline z + w \overline x \overline y \overline z + w \overline x y\overline z = \overline x \overline z. $$ In $\color{blue}{\text{blue}}$ we have $$\overline w x y z + wxyz = xyz. $$ Therefore the reduced expression is $$\overline x \overline z + xyz. $$