21

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.

12
  • 12
    you mean transforming a Karnaugh map into a ifelse cascade? Aug 22, 2011 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, 2011 at 5:34
  • 1
    @jalayn most karnaugh tools are for digital circuitry; those have different heuristics than what the question is about Aug 22, 2011 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, 2011 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. Dec 17, 2014 at 13:57

9 Answers 9

15

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]()
5
  • What language is this? Javascript? Python?
    – TheLQ
    Aug 22, 2011 at 17:26
  • TheLQ, its not python, might be javascript. But it would be very similar if written in python
    – grizwako
    Aug 22, 2011 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. Aug 22, 2011 at 18:33
  • 4
    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, 2014 at 1:19
  • @kevincline please, pretty please, "Lua", not "LUA". :)
    – Machado
    Aug 18, 2017 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();
2
  • 3
    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, 2014 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, 2014 at 10:16
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.

2

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) Somewhat ironically given your username, this will yield significantly duplicated code when the handling of each individual output param should be reusable; which is pretty much what the question title is focusing on. (b) You're reinventing the flags enum. Not sure which language you were using and if it contains an existing implementation of a flags enum, but it's worth mentioning the concept here either to use it or be able to find more documentation on it.
    – Flater
    Aug 3, 2023 at 1:25
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

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.

1

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.

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

2
  • 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, 2012 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, 2012 at 11:42
0

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.

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