Partial Boolean functions

A partial Boolean function $ f$ is given by two disjoint set of points $ O$ , $ Z$ . $ f$ is defined to have value $ 1$ on $ O$ , 0 on $ Z$ and is undefined elsewhere. For encoding sets of Boolean vectors we use the encoding defined in [*].

If we identify $ 1$ with the Boolean value True and 0 with False, operations from propositional logic get a meaning for Boolean functions.

We can apply operations like xor, and, or to partial Boolean functions, defined everywhere where the result is uniquely determined on extensions of these functions.

In [1]: from polybori.partial import PartialFunction

In [2]: O=BooleSet([Monomial(),x(0)*x(1)])

In [3]: Z=BooleSet([x(2),x(0)*x(2)])

In [4]: f=PartialFunction(zeros=Z,ones=O)

In [5]: f
Out[5]: PartialFunction(zeros={{x(0),x(2)}, {x(2)}}, ones={{x(0),x(1)}, {}})

In [6]: O2=BooleSet([x(1),x(2)])

In [7]: Z2=Bool
BooleConstant          BoolePolynomialVector  BooleRing              BooleSet

In [7]: Z2=BooleSet([x(0)*x(1),x(1)*x(2),x(0)*x(2)])

In [8]: g=PartialFunction(zeros=Z2,ones=O2)

In [9]: f & g
Out[9]: PartialFunction(zeros={{x(0),x(1)}, {x(0),x(2)}, {x(1),x(2)}, {x(2)}}, ones={})

In [10]: f|g
Out[10]: PartialFunction(zeros={{x(0),x(2)}}, ones={{x(0),x(1)}, {x(1)}, {x(2)}, {}})

In [11]: f^g
Out[11]: PartialFunction(zeros={{x(0),x(2)}}, ones={{x(0),x(1)}, {x(2)}})

Since addition of in $ \mathbb{Z}_2$ is equivalent to xor (using this identification with Boolean logic), the operators & and + coincide.

In [12]: f+g
Out[12]: PartialFunction(zeros={{x(0),x(2)}}, ones={{x(0),x(1)}, {x(2)}})

We have also build our interpolation functions as method for our PartialFunction class, which is a more convenient way to use it.

In [13]: f.interpolateSmallestLex()
Out[13]: x(2) + 1

In [14]: g.interpolateSmallestLex()
Out[14]: x(0) + x(1) + x(2)


2009-12-23