About a week ago I had a discussion with a fellow programmer about some boolean logic. We had three parameters, something like:

1. personHasInsurence (A)
2. personNeedsInsurence (B)
3. personIsKnownAtThisAgency (C)

We also had two particulair cases for an insurance page:

Case 1:
Person has insurence and isn’t yet known at this agency

Case 2:
Person doesn’t have insurence, needs insurence and is known at this agency

Case 3:
Person doesn’t have insurence, doesn’t need insurence and is known at this agency

So the view-logic was a bit complex:

if( (A && !C) || (!A && B && C) || (!A && !B && C ) ) {
    showPage();
}

Then I remebered something I learned at school some time ago. So called karnaugh maps. I’ve completely forgotten how to use them, but I knew it was possible to calculate the shortest form to comply to the logic rules. When looking further I found the so called “Quine McCluskey“-algorithm, and I decided to implement it (just to learn how it works).

Quine - McCluskey algorithm

First of, lets go through a couple of terms.

Minterm: A small boolean function which has all the different input variables, once. So for example, a minterm using the above variables would be: ABC (A and B and C), or A’BC (not A and B and C).

The first thing you do using this algorithm is that you find so called “prime implicants”. An implicant is a combination of one (or more) minterms, and a prime implicant is a implicant which can’t be combined with other implicants (for more details, read the wikipage with examples)!

After combining all the minterm of your case(s), you’ll end up with a “prime implicant chart”. This is a chart with all the prime implicants and the fields they cover. Sometimes its easy to spot “essential prime implicants”. That is, implicants which are unique in covering a field. You have to use these implicants in the final logic.

When you have multiple options left to combine to cover all the fields, you can use Petrick’s Method to select the best/smallest option.

Using the above example, if you minimize, you’ll come down to:

if((!A && C) || (A && !C)) {
    showPage();
}

The algorithm is pretty fun to program, and its a bit different from most algorithms I’ve seen lately!

And if you need something even faster, try out Espresso!

ps. I love browsing this page: List of algorithms
But OTOH, its kind of depressing I still have soo much to learn.