I Heart Karnaugh Maps

Have you ever found yourself writing a long Boolean condition in your code like the line below?


if ((policy.Type == PolicyType.AutoInsurance && policy.PolicyHolder.PriorAccidents == 0) || (policyPaidInFull && policy.Type == PolicyType.AutoInsurance || policy.IsPremium) || (policy.Type == PolicyType.AutoInsurance && policy.PolicyHolder.PriorAccidents == 0 && policy.IsPremium))

 

I Heart Karnaugh MapsPerhaps that line of code above is the first and easiest way you thought about all the conditions that have to occur in your application’s business logic. You write that line of code, test it in many different scenarios and it works so you think you have done a good job. Well, there are ways to improve upon that line of code by removing logically equivalent Boolean expressions, not to mention some style improvements that might make it more understandable.

We owe gratitude to our dear friends the Electrical Engineers for developing a clever tool, named Karnaugh Maps, to help with this dilemma, usually for cases of no more than 6 variable conditions. Karnaugh Maps (pronounced “car-no” and often simply called “K-Maps”) are a system for reducing Boolean expressions into a more simplistic form. They originated from the need to reduce electrical wiring gates, or circuit minimization, but they are still useful for the high-level software developer.

 

Benefits of reduced Boolean expressions

  1. Increased program performance
  2. Increased readability of code
  3. Less code results in easier to change code

Reducing our example expression

The 1st step is to let letters represent each of the conditions in our expression. In our case:

  • a :     policy.Type == PolicyType.AutoInsurance
  • b :     policyPaidInFull
  • c :     policy.PolicyHolder.PriorAccidents == 0
  • d :     policy.IsPremium

Then, draw a graphical square like the one pictured below. This represents each possible combination of our Boolean conditions. The boxes are blank because we have not yet entered what Boolean results we want in our resultant expression.

Blank Karnaugh Map

Let’s take the first, simplified condition in parentheses, if (a && c), and put it into the map. The result would look like the below image, because we only need to fill in the boxes where a and c are both 1.

Sample Karnaugh Map

Following this example, we can use the entire Boolean expression to fill out the whole map. The completed Karnaugh Map is pictured below.

Completed Karnaugh Map

Now circle any square or straight line of boxes since they correspond to an expression that differs by only two bits.

Circled Karnaugh Map

Because of the way we have arranged our variables around the outside of the map, we can eliminate variables based on boxes filled with 1s being adjacent to each other. In our example, the vertical “circle” exhibits a scenario where the expression should always be true as long as both the a bit and the b bit are 1, hence the condition ( a && b ). Likewise, the square “circle” exhibits true cases whenever the c bit is 1 and the a bit is 1. Because the b bit and d bit are true no matter if their values are 0 or 1, they can be deleted from the resulting simplified expression, which would be || ( a && c ). We use a similar rule to find the final d condition.

In one sentence, this rule can be summarized as “the circled boxes can be grouped together and the two variables that differ can be discarded.”

The resulting Boolean expression is:

if ( ( a && b ) || ( d ) || ( a && c ) )

which, using Boolean algebra, can be further reduced to:

if ( ( a && ( b || c ) ) || ( d ) )

We were not able to completely remove any variables, but we did simplify the expression quite a bit. The original Boolean conditions can be substituted for our letter variables, and we can rewrite the original expression as below:


bool policyIsAuto = ( PolicyType.AutoInsurance == policy.Type );
bool zeroPriorAccidents = ( 0 == policy.PolicyHolder.PriorAccidents );
if ( policyIsAuto && ( policyPaidInFull || zeroPriorAccidents ) || policy.IsPremium )

Seems easy, right? It is. And I am sorry if my steps went too fast for you. My intention is not to teach how to use Karnaugh Maps for all circumstances but instead to show you how easy and useful it is to simplify your Boolean logic.

For help with different scenarios, find the book Bebop to the Boolean Boogie – an Unconventional Guide to Electronics at your local library, check out this Wikipedia link, or you can even download software to perform the rules for you.

Happy Karnaugh Mapping!

In the mean time, I hope I was able to show you how fun and easy using a system like this can be. Feel free to post questions in the comments.

 

– Karnaugh Map Images taken from Bebop to the Boolean Boogie – an Unconventional Guide to Electronics

– Digital Logic image created by Garrett Crawford

Advertisements

About Stu
I am a software developer living in Cincinnati, OH. I primarily focus on .NET and Microsoft technologies and have bounced around quite a bit in my short career between multiple cities in the Midwest (including Cleveland, Columbus, Cincinnati, and St. Louis). I would like to learn more about programming, technology, marketing, and how to run a business. -Nathan Stuller

4 Responses to I Heart Karnaugh Maps

  1. Sam Schutte says:

    That’s really cool Nate!

    I’m confused though – how did you go from the last graph of circles and boxes to the boolean expression? What do you mean “the two variables that differ can be discarded”?

    I’ve reduced complex boolean expressions in a similar manner before, but never had the benefit of a graph. Of course, I guess it gets more complicated if you have more variables…

    s.

  2. Stu says:

    Thanks for calling that out. I was admittedly lazy at that part and could have been more clear. I have updated the paragraph immediately following that graph and I hope it makes more sense. Also, this is a pretty narrow example, so it isn’t meant to cover every rule, but I hope it helps people to follow the process and to gain an initial understanding of how it works.

  3. Sam Schutte says:

    Ok – that makes more sense. Thanks!

  4. Pingback: Blank Karnaugh Map – How One Search Keyword Changed my Way of Thinking | Midwest Developer Insights

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s