Tool that turns truth table into smallest possible if / else block

Question

Is there any application or tool that will take a truth table and turn it into a compacted if block?

For instance, lets 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 application could produce this 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

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 2

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 3

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 4

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 5

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