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))

 

Perhaps 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 1^st 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.

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.

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

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

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