How to turn truth table into smallest possible if / else block

Question

How can I take a truth table and turn it into a compacted if block?

For instance, let's say I have this truth table where A and B are conditions and x, y and z are possible actions:

A B | x y z
-------------
0 0 | 0 0 1
0 1 | 0 0 1
1 0 | 0 1 0
1 1 | 1 0 0

This could transform into below if block:

if(A)
{
    if(B)
    {
        do(x)
    }
    else
    {
        do(y)
    }
}
else
{
    do(z)
}

This is an easy sample, but I frequently have several conditions that combined in different ways should produce different outputs and it gets hard to figure out the most compacted and elegant way to represent their logic in an if block.

Answer 1

If you are designing from a Karnaugh map, then the code may as well look that way too:

//                   a      b
def actionMap = [ false: [false: { z() },
                          true:  { z() }],
                  true:  [false: { x() },
                          true:  { y() }]]

actionMap[a][b]()

Answer 2

In C#.NET, you can use a Dictionary Class to get the result without any IF ELSE as follows - The nice thing about this is:

1. It is readable
2. New keys will be unique (otherwise, you get an error)
3. Sequence does not matter
4. Easy to add or remove entries

If you don't have an equivalent of Dictionary Class, you can do the same in a binary look-up/search function.

//A B | x y z
//-------------
//0 0 | 0 0 1
//0 1 | 0 0 1
//1 0 | 0 1 0
//1 1 | 1 0 0
// Create a Dictionary object and populate it
Dictionary<string, string> _decisionTable = new Dictionary<string, string>() { 
    { "0,0", "0,0,1" }, 
    { "0,1", "0,0,1" }, 
    { "1,0", "0,1,0" }, 
    { "1,1", "1,0,0"} 
};

//usage example: Find the values of X,Y,Z for A=1,B=0
Console.WriteLine(_decisionTable["1,0"]);
Console.Read();

Answer 3

What you want is a Rete algorithm. This automatically combs a set of rules and prioritizes them into a tree the way you describe.

There are a number of commercial "rules engine" systems that do this on the very large scale (millions of rules) where execution speed is essential.

Answer 4

Map the inputs into a single value and then switch on it:

#define X(a, b) (!!(a) * 2 + !!(b))
switch(X(A, B)) {
case X(0, 0):
    ...
    break;
case X(0, 1):
    ...
    break;
case X(1, 0):
    ...
    break;
case X(1, 1):
    ...
    break;
}
#undef X

Answer 5

Here is your library :) And you dont need to pass full K-table, only fields that you are interested in :) It assumes that its AND operator in truth table. If you want to use more operators, you should be able to rewrite it. You can have any number of arguments. Written in python, and tested.

def x():
    print "xxxx"

def y():
    print "yyyyy"

def z(): #this is default function
    print "zzzzz"

def A():
    return 3 == 1

def B():
    return 2 == 2


def insert(statements,function):
    rows.append({ "statements":statements, "function":function })

def execute():
    for row in rows:
        print "==============="
        flag = 1

        for index, val in enumerate(row["statements"]):
            #for first pass of lopp, index is 0, for second its 1....
            #if any function returns result different than one in our row, 
            # we wont execute funtion of that row (mark row as not executable)
            if funcs[index]() != val:
                flag = 0

        if flag == 1:
            #we execute function 
            row["function"]()
        else: z() #we call default function


funcs = [A,B]  #so we can access functions by index key
rows = []

insert( (0,0), y)
insert( (0,1), y)
insert( (1,0), x)
insert( (1,1), x)
insert( (0,1), x)

execute()

Answer 6

A lookup table containing functions pointers can work well in some situations. In C, for example, you can do something like this:

typedef void(*VoidFunc)(void);

void do(int a, int b)
{
    static VoidFunc myFunctions[4] = {z, z, y, x}; // the lookup table

    VoidFunc theFunction = myFunctions[ a * 2 + b ];
    theFunction();
}

This is a good solution when the number of inputs is relatively small, since the number of entries in the table has to be 2^^n where n is the number of inputs. 7 or 8 inputs might be manageable, 10 or 12 starts to get ugly. If you have that many inputs, try to simplify by other means (such as Karnaugh maps) first.

Answer 7

The best way to express the code depends on what a, b, and x, y, and z are. Sure, in some cases, it may be appropriate to adopt one of the lookup table approaches given in other answers however, in many cases it results in harder to read code, and you'd be best writing code like this:

def f(a, b) :
  if (not a):
    z()
    return

  if (b):
    x()
  else:
    y()

or even:

def f(a, b) :
  if (not a):
    z()
    return

  if (b):
    x()
    return
  
  y()

Frankly, thinking about this in terms of a truth table at all is often the wrong way of doing it. You want to think about the flow of code and what the different options mean and how they are logically associated with each other.

Answer 8

Look at the "Gorgeous Karnaugh" software - it can accept truth tables quite exact as your sample, accept analytic boolean formulas definition, accept Lua scripting to build truth tables. Next, "Gorgeous Karnaugh" software draws the K-Maps for taken input, which you can minimize manually or using "Espresso" logic minimizer, and produces output for C/C++ and some hardware languages. Look to the summary features page for "Gorgeous Karnaugh" - http://purefractalsolutions.com/show.php?a=xgk/gkm

Answer 9

In a language with pattern matching, you don't need to transform anything, because you can code up your table more or less directly. For example in Rust:

match (a, b) {
    (false, _) => z(),
    (true, false) => y(),
    (true, true) => x(),
}

The pros of this approach is that is very efficient, the compiler checks that all cases are covered and only one of the branches is evaluated.