Any free software to compute boolean expression?

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!

-
evaluate or simplify? evaluation is a relatively easy problem, whereas simplification is, I believe, rather more difficult. –  JustJeff Aug 28 '11 at 10:04
Yeah just evaluation. Thanks anyway, Jeff :3 –  CppLearner Aug 28 '11 at 22:32
@JustJeff minimization is difficult, but Espresso is quite good at it :o) –  vicatcu Aug 31 '11 at 3:18
(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) –  Kevin Vermeer Aug 31 '11 at 10:20
@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. –  JustJeff Aug 31 '11 at 10:31

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


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" )

-
+1, awesome job –  NickHalden Aug 28 '11 at 18:41
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! –  CppLearner Aug 28 '11 at 22:31
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" )))) –  CppLearner Aug 28 '11 at 22:33
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. –  Wouter van Ooijen Aug 29 '11 at 6:11

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

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"

-