Allocation dynamic truthtable values to a dictionary

Question

NOTE: This post is heavy edited. I found a solution.

My question was, how I can apply all possible combinations of a truth table for an arbitary number of variables to a dictionary. E.g. for 3 vars I have a dictionary like 'lib = {"x":0, "y":0, "z":0}' I wanted to generate all 8 possible combinations. I need the n-tuples in this format to evaluate a given expression.

Because some wanted to know why I needed it. I was working on an exercise where I created a class with subclasses to handle boolean expressions. While brooding over the problem I looked over the previous chapters in the exercise book and realized, that I might solve it with recursion.

For those interested here is my implementation and with my solution:

# classes to handle boolean expressions

class ExprBoolean:
    def __str__(self):              # necessary for considering precedence: not > and > or > equal
        return self.str_aux(0)
    
    def init_Lib_Keys(self):        # if not existent, generate class var: lib - dictionary with all
        try:                        # vars, keys - list with all vars, tt - empty list for truth table
            self.lib
        except:
            self.lib = self.getVar({})
            self.keys = list(self.lib.keys())
            self.tt = []

# ---- Solution I was looking for --------------------------------
    def TruthTable(self,keys):      # generates truth table considering all vars and entered expression
        if keys == []:                  # condition to insert n-tupel as row in lib-string
            dummy = []
            for key in self.lib:
                dummy += [self.lib[key]] + ["\t| "]
            dummy += [self.eval(self.lib)] + ["\n"]
            self.tt += [dummy]
            return
        for keyN in range(len(keys)):
            for i in [True,False]:
                self.lib[keys[keyN]] = i
                self.TruthTable(keys[1:])
            break
# ----------------------------------------------------------------
      
    def make_tt(self):              # prints a truth table
        self.init_Lib_Keys() 
        for key in self.keys:
            print("{}\t\t| ".format(key),end="")    # header of table with
        print(self)                                 # expression in last column
        if not self.tt:
            self.TruthTable(self.keys)              # generates truth table
        for row in self.tt:                         # prints row after row
            for col in row:
                print(col,end="")
        
    def isTauto(self):                              # checks if expression is tautology (always True)        
        self.init_Lib_Keys()
        if not self.tt:
            self.TruthTable(self.keys)
        for row in self.tt:
            if not row[-2]:                         # in row[-2] is evaluated expression
                print(row[-2])
                return
        print(True)
            
    
class Not(ExprBoolean):
    prec = 3                        # precedence rank for brackets
    
    def __init__(self,arg):
        self.arg = arg
        
    def str_aux(self,prec):
        return "!" + self.arg.str_aux(self.prec)
    
    def getVar(self,env):
        return self.arg.getVar(env)
    
    def eval(self,env):
        return not self.arg.eval(env)

class BooOp(ExprBoolean):
    def __init__(self,x,y):
        self.x = x
        self.y = y
        
    def str_aux(self,prec):
        s = self.x.str_aux(self.prec) + self.op + self.y.str_aux(self.prec)
        if self.prec < prec:
            return "(" + s + ")"
        else:
            return s    
        
    def getVar(self,env):
        new_env = self.x.getVar(env)
        new_env = self.y.getVar(new_env)
        return new_env
    
    def eval(self,env):
        return self.fun(self.x.eval(env),self.y.eval(env))

class And(BooOp):
    prec = 2
    op = "&"
    
    def fun(self,x,y):
        return x & y

class Or(BooOp):
    prec = 1
    op = "|"
    
    def fun(self,x,y):
        return x | y

class Eq(BooOp):
    prec = 0
    op = "=="
    
    def fun(self,x,y):
        return x == y

class Var(ExprBoolean):
    def __init__(self,name):
        self.name = name
        
    def str_aux(self,prec):
        return self.name
    
    def getVar(self,env):
        env[self.name] = 0
        return env
    
    def eval(self,env):
        return env[self.name]

# examples to test class

lib = {"x":True, "y":False, "z":True}

e1 = Or(Var("x"),Not(Var("x")))
e2 = Eq(Var("x"),Not(Not(Var("x"))))
e3 = Eq(Not(And(Var("x"),Var("y"))),Or(Not(Var("x")),Not(Var("y"))))
e4 = Eq(Not(And(Var("x"),Var("y"))),And(Not(Var("x")),Not(Var("y"))))
e5 = Eq(Eq(Eq(Var("p"),Var("q")),Var("r")),Eq(Var("p"),Eq(Var("q"),Var("r"))))
e6 = And(Or(Var("x"),Var("y")),Eq(Var("x"),Var("y")))

e4.make_tt()
e4.isTauto()

Answer 1

If I understand the problem, this is one way to help solve it without using eval() or having to parse the expression yourself. (You will have to implement the other Boolean functions yourself.)

def AND(a, b):
    return a and b

def OR(a, b):
    return a or b

def NOT(a):
    return not a

x = True
y = False
z = True
print(AND(x, y))
# False
print(NOT(AND(x, y)))
# True
print(OR(x, y))
# True
print(AND(AND(x, z), NOT(y)))
# True

Answer 2

Even though python has classes, that doesn't mean you should treat every problem as an invitation to write a class hierarchy. Evaluating expression is a verb, not a noun.

First off, you don't always have to write an expression evaluator. Python has eval and exec, and boolean and arithmetic expressions in Python are pretty much standard:

>>> eval("3+5")
8
>>> eval("x=3+5")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 1
    x=3+5
     ^
SyntaxError: invalid syntax
>>> exec("x=3+5")
>>> x
8

If that is enough, look at the ast module in the standard library.

Even if you want to write it yourself, programming is often more about creating smart data that writing lots of code. Below is a small implementation of a postfix expression parser (from one of my github repos).

import operator
import math

# Global constants {{{1
_add, _sub, _mul = operator.add, operator.sub, operator.mul
_truediv, _pow, _sqrt = operator.truediv, operator.pow, math.sqrt
_sin, _cos, _tan, _radians = math.sin, math.cos, math.tan, math.radians
_asin, _acos, _atan = math.asin, math.acos, math.atan
_degrees, _log, _log10 = math.degrees, math.log, math.log10
_e, _pi = math.e, math.pi
_ops = {
    "+": (2, _add),
    "-": (2, _sub),
    "*": (2, _mul),
    "/": (2, _truediv),
    "**": (2, _pow),
    "sin": (1, _sin),
    "cos": (1, _cos),
    "tan": (1, _tan),
    "asin": (1, _asin),
    "acos": (1, _acos),
    "atan": (1, _atan),
    "sqrt": (1, _sqrt),
    "rad": (1, _radians),
    "deg": (1, _degrees),
    "ln": (1, _log),
    "log": (1, _log10),
}
_okeys = tuple(_ops.keys())
_consts = {"e": _e, "pi": _pi}
_ckeys = tuple(_consts.keys())


def postfix(expression):  # {{{1
    """
    Evaluate a postfix expression.
    Arguments:
        expression: The expression to evaluate. Should be a string or a
                    sequence of strings. In a string numbers and operators
                    should be separated by whitespace
    Returns:
        The result of the expression.
    """
    if isinstance(expression, str):
        expression = expression.split()
    stack = []
    for val in expression:
        if val in _okeys:
            n, op = _ops[val]
            if n > len(stack):
                raise ValueError("not enough data on the stack")
            args = stack[-n:]
            stack[-n:] = [op(*args)]
        elif val in _ckeys:
            stack.append(_consts[val])
        else:
            stack.append(float(val))
    return stack[-1]

The "intelligence" of this is in the _ops dictionary, which links an operator to a two-tuple of a number of arguments and an operator function.

Because of that, the evaluator itself is only 14 lines of code.