The question is quite straightforward: Why do Karnaugh maps work? What was the reasoning that led Maurice Karnaugh to come up with these maps? At first glance, it doesn't seem a natural approach, instead it feels somewhat arbitrary yet surprising that it works.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The key here is graycode. I think the easiest way to see why Karnaugh maps work is to go through an example: Consider the following truth table:
$\hskip2in$
We can easily find the logical formula describing this table in terms of the sum of products formula (I will use the boolean algebraic notation): $$ \begin{align*} E(A, B, C) &= \overline{A} \cdot B\cdot \overline{C} + A \cdot \overline{B}\cdot \overline{C} + A \cdot \overline{B}\cdot C+A\cdot B \cdot \overline{C} \\&= B \cdot \overline{C}\cdot (\overline{A} + A) + A\cdot \overline{B}\cdot (\overline{C} + C)\\ &= B\cdot \overline{C} + A\cdot \overline{B} .\end{align*} $$ Notice that when using the distributive law backwards, we always need two of the three variables to be constant and only one of the three to change and that it always simplifies if two stay constant and the third changes. The corresponding Karnaugh-map would look like:
$\quad\quad\quad\quad $
The alignment of the map entries exhibit a gray code alignment of the logical expressions, meaning that each entry's binary expression only differs by a single bit, e.g. first entry is $000$ and second entry is $010$ so they only differ in the second bit. This is exactly what we have found when examining the minimisation of the Sums of products representation, namely that we hold two values constant and consider the third one changing.
To read off the Sum of products representation of our logic table from the Karnaugh-map, we therefore first circle all the pairs of ones. For the light-green pair we find that $B$ and $C$ stay constant but $A$ changes making the $A$ term obsolete and, hence, obtain $B\overline{C}$. For the darker green pair we find that $A$ and $B$ stay constant but $C$ changes, leaving use with $A\overline{B}$. The last term follows analogously and you end up with the same formula found before.
I hope this makes the underlying concept clear, if you want me to further explain the generalised version of this, just tell me.
