fa.bianp.net

Boolean algebra, first steps

Category: sympy, Tecnologí­a

The first task for my Summer of Code project is to write a nice boolean algebra module. I wanted a clean module that follows SymPy's object model and that plays well with other objects. In practice this means that it should inherit from Basic and that it should behave well with python's boolean values (True, False) as well as with unknown values (SymPy's Symbol). To implement boolean expressions, my first thought was to implement And, Or, Not as subclass of AssocOp, just as Add and Mul. At the beginning I had some problems with commutativity, since my expressions are commutative but AssocOp does not have this feature. No problem, I thought, I'll just override .flatten(). That seemed to work until I wanted to implement double-negation rule for Not (Not(Not(x)) --> x). Maybe I could have used .flatten() also for that, but that was ugly. Overriding __new__ was even uglier, so I began to think for an alternative approach. On the other hand And and Or are functions: B^2 --> B, and Not: B --> B, where B is the boolean space, so it seems natural to implement them as subclasses of Function. It turned out that Function is very inheritance-friendly and all you have to do is override the .eval() method. This is a minimalistic And function:

class And(Function):
    @classmethod
    def eval(cls, *args):
        if all(map(lambda x: isinstance(x, bool), args)):
            return all(args)
        sargs = sorted(flatten(args, cls=cls))
        return Basic.__new__(cls, *sargs)

You can see full source code here Lot's of features are missing, of course, but it is capable of doing some simplifications and it plays nicely with Symbol and boolean types.