Truth Tables (… you can handle the truth)

About eight years ago I worked on my first major commercial software project. Before I worked as a freelancer and had mostly rather small and dull projects. This project however had a team of eight people plus management and it was surprisingly complex at times.

One day we had to implement a feature which depended on four independent conditions. Independent in this case means that there were no exclusive branches of logic. To implement it multiple branches with similar but not identical logic were necessary. I was a bit scared because I knew that this would be one big ugly hairball of a nested if / case statement which is impossible to get right on the first attempt and will probably be hard to test.

Then our head of engineering came along, an experienced old school hacker, who told me: »Lets implement it with a truth table!«

At first I didn’t know what he was talking about and then I felt like this would be some kind of arcane low level hack solution to this complex problem but it turned out to make everything clean and easy to reason about.

Since then I had maybe three or four other occasions where I used truth tables to solve similar complex problems and I was always grateful for this advice. Every time I proposed to use a truth table in these situations there were always some colleagues who either didn’t know about them, just like me seven years ago, or knew them theoretically but never used them in practice.

The last occurrence was just recently in my current project at Wooga which is why I thought it might be a good idea to share the concept with everyone who does not already know what I’m talking about.

Show Me The Tables

If you have studied computer science and/or philosophy you should have seen truth tables on paper. They are often used to describe the behavior of logic gates for example. This is how a truth table for an AND gate would look like:

 A | B | Output
---|---|-------
 0 | 0 |   0
 1 | 0 |   0
 0 | 1 |   0
 1 | 1 |   1

This table tells you that the output of an AND gate will be 1 only if input A AND B are 1.

In philosophy the same tables are used for reasoning about logic statements in arguments
(philosophers, please correct me here if thats not accurate enough, I know you care :).

Practical Application of Truth Tables

For practical applications truth tables have a slightly different form. Imagine we have a website where users generate a lot of content and they have the option to download their entire history which is so massive that we have to process and compress it. Now the app can be in a couple of different states and in only one of the states the user can actually download the archive.

Lets start simple and say we have two boolean variables which are important to determine the state of our application.

requested_archive:   true | false
processing_finished: true | false

For each of the variables we would now assign a unique binary flag:

requested_archive:   01 (decimal: 1)
processing_finished: 10 (decimal: 2)

Now the truth table would look like this:

requested | processing |
archive   | finished   | result | meaning
----------|------------|--------|----------------------------- 
    00    |    00      |   00   | not requested, not processed
    01    |    00      |   01   | requested but not processed
    00    |    10      |   10   | impossible
    01    |    10      |   11   | requested and processed

The basic idea here is to evaluate the conditions separately and use a binary OR to compute the resulting bit flag.

Like I said, it is a simple example which does not strictly require implementing a truth table but even in this situation a truth table in form of a comment above the nested conditional statement can have a benefit for the next person reading your code.

Also it provides an overview of all the possible combinations and what cases are actually relevant for you. You know what unit tests to write and you can be certain that you’ve covered everything.

Implementation

Ok now lets implement this truth table. We already know what cases we have and what they mean so the first thing is to assign them symbolic names in your code. In this example I will use ruby but it should work in a similar way in your favorite language.

For this simple example it might not seem obvious why truth tables are great but it illustrates some aspects already. The evaluation of conditions is isolated into separate functions which you can unit test very easily.

When you unit test the archive_state function and you get an unexpected state, the bit flags will tell you exactly which of the conditions was failing your expectations.

You give each state a symbolic name and you avoid a nested conditional.

I know, I know this looks crazy complex but its just an example and as soon as you add one or more conditions it will be much more clear why I prefer a truth table over nested conditions any time.

The next code example is from a real world erlang application and its again about determining the state of an application. Based on the day of the season, the state of the user data and the state of the processing we have to do different things and there is no exclusive branch for one of the conditions which means the implementation would be painful. (Note: there is a hidden fourth condition in the first one, checking that the season is really over as in all matches have been simulated on the last day of the season)

With truth tables we know we have 2^3 possible combinations, of which two are impossible, we know exactly which cases mean what and what we want to do for each of them, we also can implement each conditions in neat and tidy functions which are easily unit testable, we have symbolic names and the final case statement is actually readable.

Without the comment which shows the actual truth table and without all the other comments, this whole code snippet would be a lot less intuitive of course but with them it is self sufficient documentation.

The best part is, even if you have four or five conditions the complexity of the code does not increase, it is just more work to write down the initial truth table of 16 or 32 possibilities but the implementation would follow the same pattern and the evaluating case statement would still be easy to read.

Personally I went as far as four conditions and when I would encounter a situation where five conditions are evaluated I would first spent a few hours trying to reduce the amount of conditions maybe even refactoring code but if you really have this kind of complex system, truth tables are your best chance to implement it without losing your sanity.

Let me know in the comments if that was helpful.

15 thoughts on "Truth Tables (… you can handle the truth)"

  1. mechko says:

    Hej hukl, this is a good advice indeed. When implementing such conditions I often write down truth tables, but most of the time I just translate them to boolean expressions and if/else statements, while using constants for both conditions and results is indeed way more readable and easier to apply changes on. Thanks for sharing! Regards, mechko

  2. Peter Körner says:

    Excellent Article! Thank you for that!

    Your CSS-Declaration of pre-Tags lacks the generic Font-Name “monospace”, thus your Code-Examples look ugly on Linux.

    1. hukl says:

      is it better now?

  3. LB says:

    The sample code is missing in your RSS Feed 🙁

    1. hukl says:

      I had to embed it from github – thats why I guess

  4. Denny says:

    I heard about truth tables, but never used them so far (I did not study computer science or philosophy). But, I think I’ll consider using them in future projects as I think they are a very useful tool. Thanks for sharing your insights.

  5. Karsten says:

    Kind of looks like a half-assed deterministic finite automaton, only with non-obvious, externally handled state transitions. You may want to check out DFAs, or “Deterministische endliche Automaten” (DEA).

    1. hukl says:

      Hmm sample implementations / examples would be nice. Because from what I read on wikipedia I cannot directly map that to our use case in the example

  6. Marcus says:

    Hi hukl,

    Is it intended that you overwrite FINISHED_PROCESSING in your first example? Or am I wrong and should read it one more time? 🙂

    Greets, Marcus

    1. hukl says:

      ah good catch – fixed it! thanks!

      1. Marcus says:

        You’re welcome. 🙂

        1. Marcus says:

          Nevermind, it’s a great post. I will use it more often. Thanks!

  7. Markus says:

    Karnaugh maps have been used in games (Bards Tale, Maze) to simplify the logic of a 2D map and tiles.

    https://en.wikipedia.org/wiki/Karnaugh_map

  8. Yawar says:

    In Erlang (and of course Elixir), you can directly use pattern matching to implement the truth table, no? E.g., assuming the test functions are reimplemented to return booleans:


    case {is_current_season_over(), is_finished_processing(), is_state_reset()} of
    {false, true, false} -> noop;
    {true, false, true} -> noop;
    {true, true, false} -> start_processing();
    {true, false, false} -> resume_processing();
    {false, false, true} -> fc_league_state:reset_state();
    Unexpected -> throw({broken_state, Unexpected})
    end.

    This gets rid of most of the boilerplate and in fact looks like a literal truth table.

    1. hukl says:

      Sure that works too. I prefer the described way but this is just as valid.

Leave a Reply

Your email address will not be published. Required fields are marked *