Blank Karnaugh Map – How One Search Keyword Changed my Way of Thinking

3 Years ago, I wrote a blog post titled “I Heart Karnaugh Maps.” In it, I described a technique that can be used to reduce the complexity of Boolean expressions. I provided sample diagrams as I worked through the technique step by step. In one of them, I added an alt tag of “Blank Karnaugh Map” to describe the starting point of the whole process. Little did I know that defining such a targeted search keyword would alter my perspective about Internet search traffic.

Blank Karnaugh Maps

That blog post has always ranked in the top 20% of all my posts in terms of page views, largely due to the one keyword.

Among my blog’s highest ranking keywords are:

4th “Blank Karnaugh Map”

9th “Karnaugh Map”

12th “Blank Karnaugh Maps”

I first learned about Karnaugh Maps as a programming tool in my undergraduate studies at The Ohio State University. In Math 366: “Discrete Mathematics with Applications” I learned:

  • Mathematical formalization and reasoning, logic, and Boolean algebra
  • Sets, functions, relations, recursive definitions, and mathematical induction
  • Elementary counting principles

In order to refresh my knowledge before my blog post, I read an Electronics book. In neither the book nor the course do I remember a specific need for blank karnaugh maps or images of blank karnaugh maps. Therefore, as time passed, I was lead to wonder, why do so many people need blank karnaugh maps?

Has an Opportunity Presented Itself?

I had a few conversations with fellow software developers who were intrigued by my Karnaugh Map post. Apparently, Karnaugh Maps were drawing more interest than I expected and my site was getting found by people looking to know more about them. I decided to brainstorm ways I could leverage this interest into a software product I could sell. I figured people were already coming to my blog to find information about Karnaugh Maps and software development tips. Wouldn’t a product that uses this technology to improve code be useful to my readers? I decided to call it Logic Reducer.

The Market

By no means am I a good Internet marketer. However, I had recently signed up for the Micropreneur Academy and was learning the value of performing market research before beginning product development. I wanted to make sure that I could plausibly make a profit based on the number of potential users and competition. I used three high-level approaches in my research.

Quantity of Internet Searches

There are various methods to research how many people are looking for a particular topic online. I used Micro Niche Finder to determine that “Karnaugh Maps” was being searched about 1,600 times per month. While this is not a lot, I was encouraged by the quantity of searches of some of the longer-tail keywords and the relative ease with which my website could potentially rank for them.

Occupational Statistics

In order to gauge the number of potential users for my product, I researched U.S. employment data. I estimated there were about 800,000 computer engineers and 200,000 hardware engineers in the United States. These numbers were very encouraging.

Competition

Using Google, I found several applications on the Web that had the features I wanted to build. Many of them were free. However, in reading related forums, it seemed like they often failed because they froze up or had a very limited feature set. Additionally, I did not find any on the Internet that were newer than 2006. Most of the applications were downloadable, thick clients. They were lacking the advantages of being Web products.

Karnaugh Map Minimizer on SourceForce gets .5K hits/day

Logic Minimizer 1.2.1

Karnaugh Map – minimalization software

In 2010, smart phone app stores appeared to still be growing rapidly. I was leaning toward making an iPhone app that could be used as a companion to someone writing software on a personal computer. I found a few apps that already existed:

KarnCalc $.99

Karnaugh Map Optimizer $.99

Logic Shrinker –Free-

While a few cheap apps already existed, I liked that there were not yet any iPad apps. Also, one review of an app stated that if Boolean Simplification (a feature I planned to develop) were included, he would pay 7 or 8 dollars for the app. My findings did not deter me from moving forward to the next step.

How far Did I Go?

I liked that there were potentially many users of my idea. However, there were already very affordable ways to accomplish what I was considering my main value proposal. Therefore, I moved forward cautiously. I was optimistic, so I secured the domain name LogicReducer.com. However, I was concerned that there wasn’t enough market interest so I looked for validation of my idea.

I wanted to have a designer mockup my ideas so I could more clearly describe them. I got a quote from an offshore design agency for 4 screen mockups and 1 logo. It was going to cost $500.

I asked more people about what they thought regarding my idea. The general response was that people were intrigued by the product being a Boolean logic reducer. However, I also posted to the forums in the Micropreneur Academy and multiple people voiced some warnings. They felt it catered to too small of a niche, that I would not be able to gain enough revenue to make the project worthwhile.

I decided to stop working toward building Logic Reducer at that point. I was scared by the surprisingly high $500 investment for mockups and the concerns about the niche.

What Will I Do Next Time?

All in all, I did not spend very much time or money determining if Logic Reducer would be a good product to build, especially when compared to the time it would have taken to complete it and watch it fail. My blog content had exposed a tiny sliver of opportunity on the Internet. I researched that sliver and determined that I couldn’t make enough money from it for it to be worth my time.

However, I still think this is a good strategy for finding business ideas. Bloggers and content producers who have the ability to use analytics to see what topics are of interest to readers can use that knowledge to find problems in the world. Were I to find another surprisingly popular search keyword, I would research related business opportunities similar to how I did it before.

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