20

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.

  • 10
    you mean transforming a Karnaugh map into a ifelse cascade? – ratchet freak Aug 22 '11 at 5:30
  • @ratchet: Seems like I do doesn't it? I didn't know about them before. Will have to do some reading but still and app that would do it for me would be nice, if nothing else, to verify my hand made results. – Juan Aug 22 '11 at 5:34
  • 1
    @jalayn most karnaugh tools are for digital circuitry; those have different heuristics than what the question is about – ratchet freak Aug 22 '11 at 11:20
  • 1
    @jsoldi: The answers you receive will be dependent on which site you ask. If you are seeking comments on a particular code fragment containing some if-then-else blocks, it certainly belongs to Code review (beta). Stackoverflow will teach you the tools and techniques. On programmers.SE, people will tell you whether you should/should not be concerned about rewriting logic statements for human understanding, or for faster execution. – rwong Aug 22 '11 at 15:15
  • 2
    Tool recommendations are off-topic, but if you change the question into "How can I do this?" it will be on-topic. If you do want a software recommendation, you should go to softwarerecs.stackexchange.com. – Kilian Foth Dec 17 '14 at 13:57
14

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]()
  • What language is this? Javascript? Python? – TheLQ Aug 22 '11 at 17:26
  • TheLQ, its not python, might be javascript. But it would be very similar if written in python – grizwako Aug 22 '11 at 18:14
  • @TheLQ: it's Groovy, because that's what I'm doing these days, and probably Ruby too. The code for Javascript or Python or LUA or Perl would be very similar. – kevin cline Aug 22 '11 at 18:33
  • 2
    This, of course, has the effect of evaluating b even when the evaluation is not needed. Maybe that's a problem, maybe it's not. – Pseudonym Dec 18 '14 at 1:19
  • @kevincline please, pretty please, "Lua", not "LUA". :) – Machado Aug 18 '17 at 20:35
4

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();
  • 1
    I like this solution, the only change I would make would be to use a Dictionary<Tuple<bool, bool>, Tuple<bool, bool, bool> instead of a Dictionary<string, string>. Then you don't need to build a string for looking up and deconstruct the result afterwards as Tuples will do this for you. – Lyise Dec 18 '14 at 10:09
  • @Lyise, Thank you for your remark. You are absolutely correct. I should incorporate your good point when I get a chance. – NoChance Dec 18 '14 at 10:16
2

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.

2

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()
1

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
1

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.

0

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

  • This look a lot like what I need, but couldn't get the C/C++ code to show anything other than empty ifs after entering a truth table. – Juan Jan 2 '12 at 6:27
  • Yes, that tool designed for logic function minimizations - after entering truth table you need to minimize logic function (PoS/SoP - by 0/by 1). The C++ code can be found in the "Minimization results" window after minimization. – Petruchio Jan 4 '12 at 11:42

protected by gnat Aug 18 '17 at 19:53

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.