Logic for Programmers - Part 3.

Karnaugh Maps.

July, 2006

Copyright © 2006 Leaf Mindcraft

A Brief Guide to Logic for Programmers.

In this, the last three articles, I intend to discuss the concept of the Karnaugh Map, which is a special type of Venn Diagram used in determining the particular logic expression needed in a programming situation.

The Karnaugh map is laid out as below, and is a special type of Universal Set, as described in the last article.

Remember that a '1' represents a TRUE value and a '0' a FALSE value, as in Boolean Algebra, which was discussed in the first of this series of articles. This map is universal in the sense that it covers all possible combinations of TRUE and FALSE for the logical variables A and B in the cells of the diagram as below:-

We now lay out the cells that are TRUE when A is TRUE by marking them with a 1 in the cell concerned:-

We may gather together such 1's either horizontally or vertically using the fact, derived in the first article that:-
                                    _
                        AB + AB = A
Thus the set that represents the logical expression A is:-

                                                                    _
Similarly the group for the logical expression A is:-

This is so because this set is only TRUE when A is FALSE.
And to continue, the set for B is:-

This is so because these cells are only TRUE when B is true.
                                  _
And finally, the set for B is as below:-

                                                                       _
This is the set of cells in the Karnaugh Map for B, because they are only TRUE when B is FALSE.

Having defined the sets A and B, it follows that the 'intersection' of A and B corresponds to the Boolean expression A 'and' B, or AB in Boolean Algebra and is given by the Karnaugh Map below:-

We see that this Karnaugh Map of the intersection between the sets A and B must represent AB, as it is only TRUE when both A and B are true.

Similarly the 'union' of A and B corresponds to the Boolean expression A 'or' B or A+B in Boolean Algebra and is given by the Karnaugh Map below:-

Now consider the Karnaugh Map below:-

If we ring adjacent cells either horizontally or vertically (but not diagonally), we obtain:-

                                                                             _
This diagram can be seen to represent the union of A and B, so it represents the Boolean
                  _
expression A + B. Similarly it is possible to work out what logic any 2 x 2 map represents.

Suppose one has three fields on a computer screen I, J, K, that a user is asked to fill in.

The spec. you are given says:-
1. K must be present if either I or J is present.
2. If both I and J are absent, then K must be absent.

If these conditions are not obeyed then output an error message.

You are required to work out the logical expression for the error message to be generated.

Let A be the statement 'K is present'
      B be the statement 'I is present'
and C be the statement 'J is present',
then the Karnaugh Map for three logical variables is as below:-

Note the order that all the possible combinations of B and C have been laid out. It is not in a binary counting order. Within such a diagram one can now ring together cells in groups of four as well as two (not diagonally). Going back to the problem set, we lay out 1's in the Karnaugh Map when the error message is required and 0's otherwise, as below:-

We then ring adjacent cells as follows:-

                                                                                         __
Looking at this, we can see that the single ring represents ABC and the two double rings,
_           _                                                                                               __      _       _
AB and AC, so the total is the union of all this, or, in Boolean Algebra, ABC + AB + AC,
                                               __     _
or this can be factorized as:- ABC + A (B+C).

So, finally, if A%, B% and C% were flags for the presence of something in the fields K, I and J respectively, and the error procedure was 'error_message', we would probably program this in BBC Basic as:-

Or if the flags were 'k_present', 'i_present' and 'j_present', we would program this in C as:-

Lastly, the Karnaugh Map needed if we were dealing with four logical variables is as below:-

Note that with this diagram, one can now ring together cells in blocks of eight horizontally or vertically, but not diagonally, as well as in groups of two or four.

This concludes the series of articles on logic for programmers. I hope, in particular, that Karnaugh Maps may help clarify just the right logic that might be needed in tricky programming situations.

Return to Part 1...

Return to Part 2...

Return to Home Page...