Suggesion for an undergrad final year project in Python

[phil_nospam_schmidt at yahoo.com]

How about a tool that can compute the intersection/union/disjunction of
boolean expressions, and return the result as a boolean expression?
This is something I've had on my plate for awhile, but haven't been
able to get around to doing.

As a simple example, assume we have the following expressions:

e1 = (y)
e2 = ((not x) and (not y)) or ((not x) and (y) and (z))

The union of these two would be ((not x) or (y)). The simplest
representation of the result would be best.


To make it harder consider the following additional requirements:

1) Instead of just boolean variables, allow variables with more than
two discrete values (i.e., True and False). For example, if a variable
x can represent the values 1, 2, and 3, then an expression could test
for x!=3, or x>1, or even x in [1,3].

2) Use Python's native data structures to represent expressions. Using
the example above, we might have something like this:

e1 = [{'y':True}]
e2 = [{'x':False, 'y':False}, {'x':False, 'y':True, 'z':True}]

How you might extend this to non-boolean expressions would be up to
you.

3) Make it fast, and scalable to many variables (up to at least 50). I
haven't studied this extensively, but I believe a Quine-McKlusky method
is order n^2 with n being the number of variables, so this will quickly
blow up as the number of variables increases.

4) As my example in (2) suggested, make variable names strings. This
allows arbitrary names. For non-boolean discrete variables, allow any
arbitrary list of numbers or strings as elements.

5) Since a side-effect of the program will (probably) be the ability to
reduce expressions to their simplest representation, make this
capability a part of the public API, since that's a useful function in
itself.