4
\$\begingroup\$

I found a few but they cannot evaluate long expressions. For long expressions they give me boolean values for each individual sub expressions (which is usually grouped by parentheses).

((A v B) + (~A v ~B)) v ((C v D) + (~C v ~D)) v ((E v F) + (~E v ~F)) v ((G v H) + (~G v ~H)) v ((I v J) + (~I v ~J)) v ((K v L) + (~K v ~L)) v ((M v N) + (~M v ~N)) v ((P v Q) + (~P v ~Q))

This is the kind of expression I need to evaluate. It will give me 2^16 ~ 65k rows.

I used this website, but doesn't seem giving me the final column.

Oh. I don't want to compile the program myself... Thank you very much!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ evaluate or simplify? evaluation is a relatively easy problem, whereas simplification is, I believe, rather more difficult. \$\endgroup\$
    – JustJeff
    Aug 28, 2011 at 10:04
  • \$\begingroup\$ Yeah just evaluation. Thanks anyway, Jeff :3 \$\endgroup\$
    – CppLearner
    Aug 28, 2011 at 22:32
  • \$\begingroup\$ @JustJeff minimization is difficult, but Espresso is quite good at it :o) \$\endgroup\$
    – vicatcu
    Aug 31, 2011 at 3:18
  • \$\begingroup\$ (Takes mod hat off) I think it's hilarious that both answers here get around the "I don't want to compile the program myself" restriction by using Python. (Puts mod hat back on) \$\endgroup\$ Aug 31, 2011 at 10:20
  • \$\begingroup\$ @vicatu - to clarify, I meant minimization is difficult in the computer-science sense of the word, not that it can't be done, of course. \$\endgroup\$
    – JustJeff
    Aug 31, 2011 at 10:31

2 Answers 2

11
\$\begingroup\$

This Python procedure will evaluate a formula in your format (first argument) against a list of single-letter variables (second argument):

def table( x, v , w = "" ):
   if( v == "" ):
      print( "%s : %d " % ( w, eval( x.replace( "v", " or " ).replace( "~", " ! " ).replace( "+", " and " ))))
   else:
      table( x.replace( v[ 0 ], "0" ), v[ 1 : ], w + "0" )
      table( x.replace( v[ 0 ], "1" ), v[ 1 : ], w + "1" )

for example

table( "(A v B ) + ~ C", "ABC" )

produces

000 : 0 
001 : 0 
010 : 1 
011 : 0 
100 : 1 
101 : 0 
110 : 1 
111 : 0 

To get your answer, evaluate

X = "((A v B) + (~A v ~B)) v ((C v D) + (~C v ~D)) v ((E v F) + (~E v ~F)) v ((G v H) + (~G v ~H)) v ((I v J) + (~I v ~J)) v ((K v L) + (~K v ~L)) v ((M v N) + (~M v ~N)) v ((P v Q) + (~P v ~Q))"
table( X, "ABCDEFGHIJKLMNPQ" )
\$\endgroup\$
3
  • \$\begingroup\$ Hi Wouter. Your script is brilliant. Thanks. I want to mention that the "not" operator, "!" is sensitive to space. It requires a space between the "!" and the letter that follows it. >>> for demo purpose # table( "( ( ~ A + ~ B ) v ( A + B ) ) +( ( ~ C + ~ D ) v ( C + D ) )", "ABCD" ) Thanks! \$\endgroup\$
    – CppLearner
    Aug 28, 2011 at 22:31
  • 1
    \$\begingroup\$ so always add spaces :], and to help reading better, add a pair of single quoting marks to %d. ==> print( "%s : '%d'" % ( w, eval( x.replace( "v", "or" ).replace( "~", "not" ).replace( "+", "and" )))) \$\endgroup\$
    – CppLearner
    Aug 28, 2011 at 22:33
  • \$\begingroup\$ Funny, those spaces where there in the code that I cut-n-pasted in my answer. Maybe lost in the first posting, because I then did not format it as code. \$\endgroup\$ Aug 29, 2011 at 6:11
0
\$\begingroup\$

Here's a Python module that uses a different notation for boolean expressions. It is the notation used in http://en.wikipedia.org/wiki/Canonical_form_%28Boolean_algebra%29 where there is an implicit AND between adjacent variables, + means OR, and a trailing single quote ' inverts whatever it comes after. So, (A v B ) + ~ C in Wouter's example would be written as (a + b)c'

To print the truth table of the expression, call the module as:

>>> printtruth("(a+b)c'")
a b c F
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 0

The module itself:

def parsebool(s):
    tokens = list()
    allvars = set()
    paridx = list()
    lastpar = None
    for i, char in enumerate(s):
        if char == "'":
            if len(tokens) == 0:
                raise ValueError("cannot negate empty expression")
            elif tokens[-1] == ")":
                tokens.insert(lastpar, "not")
            else:
                tokens.insert(-1, "not")
        elif char == "(":
            if tokens and not (tokens[-1] in ("or", "and", "(")):
                # implicit and
                tokens.append("and")
            paridx.append(len(tokens))
            tokens.append("(")
        elif char == ")":
            tokens.append(")")
            lastpar = paridx.pop()
        elif char.islower() or char == '0' or char == '1':
            if tokens and not (tokens[-1] in ("or", "and", "(")):
                # implicit and
                tokens.append("and")
            if char.islower():
                allvars.add(char)
            tokens.append(char)
        elif char == "+":
            tokens.append("or")
        elif char == "*":
            tokens.append("and")
        elif char in " \t\n":
            pass
        else:
            raise ValueError("invalid character in input: \"%s\"", char)
    return tokens, allvars

def boolfunc(s, name="F"):
    tokens, allvars = parsebool(s)
    allvars = list(sorted(allvars))
    lambdastr = "lambda %s: %s" % (','.join(allvars), ' '.join(tokens))
    F = eval(lambdastr, {'__builtins__':None}, {})
    F.func_doc = 'Boolean function %s(%s) = %s' % (name, ', '.join(allvars), s)
    F.func_name = name
    return F

def printtruth(F):
    if not callable(F):
        F = boolfunc(F)

    varnames = F.func_code.co_varnames
    Fname = F.func_name
    allnames = varnames + (Fname,)
    rowfmt = " ".join("%% %ds" % len(v) for v in allnames)
    print " ".join(allnames)
    for args in itertools.product((0,1), repeat=len(varnames)):
        try:
            result = str(int(F(*args)))
        except Exception:
            result = "E"
        print rowfmt % (args + (result,))

def printcompare(F, G):
    if not callable(F):
        F = boolfunc(F)
    if not callable(G):
        G = boolfunc(G)

    Fvarnames = F.func_code.co_varnames
    Fname = F.func_name
    Gvarnames = G.func_code.co_varnames
    Gname = G.func_name

    varnames = tuple(sorted(frozenset(Fvarnames).union(Gvarnames)))
    allnames = varnames + (Fname, Gname, "=")
    rowfmt = " ".join("%% %ds" % len(v) for v in allnames)
    print " ".join(allnames)

    allequals = True
    for args in itertools.product((0,1), repeat=len(varnames)):
        argdict = dict(zip(varnames, args))
        Fargs = [argdict[n] for n in Fvarnames]
        Gargs = [argdict[n] for n in Gvarnames]
        try:
            Fresult = str(int(F(*Fargs)))
        except Exception:
            Fresult = "E"
        try:
            Gresult = str(int(G(*Gargs)))
        except Exception:
            Gresult = "E"
        equals = Fresult == Gresult
        allequals = allequals and equals
        print rowfmt % (args + (Fresult,Gresult,equals))

    if allequals:
        print "functions are equivalent"
    else:
        print "functions are NOT EQUIVALENT"
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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