Reinterpretation of Boolean sets as subsets of the vector space  $ \mathbb{Z}_2^n$

Let S be a Boolean set. For example:
In [1]:S=BooleSet([x(0),x(1)*x(2)])

In [2]:S
Out[2]:{{x(1),x(2)}, {x(0)}}

S is a set of sets of variables. Our usual interpretation is to identify it with a polynomial with corresponding terms:

In [3]:Polynomial(S)
Out[3]:x(1)*x(2) + x(0)
Another interpretation is to map a set of variables $ m$ to a vector $ v$ in $ \mathbb{Z}_2^n$ . The $ i$ -th entry of $ v$ is set to 1, if and only if the $ i$ -th variable occurs in $ m$ . So we can identify $ \{x_0\}$ with $ (1,0,0)$ and $ \{x_1,x_2\}$ with $ (0,1,1)$ in  $ \mathbb{Z}_2^3$ . Extending this identification from sets of variables to sets of set of variables we can identify $ S$ with  $ \{(1,0,0), (0,1,1)\}$ . Note, that the choice of $ n$ as $ 3$ was not determined by S. In fact every bigger $ n$ would have also been a candidate. For this reason, some procedures interpreting Boolean sets as subsets of  $ \mathbb{Z}_2^n$ taking the monomial ambient space as an additional parameter. The full vector space can be constructed by multiplying all needed variables and the set of divisors of the product.

In [4]:(x(1)*x(2)*x(3)).divisors()
Out[4]:{{x(1),x(2),x(3)}, {x(1),x(2)}, {x(1),x(3)}, {x(1)}, {x(2),x(3)}, {x(2)}, {x(3)}, {}}

We distingish between procedures, which use subsets of the ambient space (like finding zeros of a polynomial), and such procedures, where only the dimension/involved unit vectors/variables matter. The first kind of procedures usually gets the ambient space itself, the second kind gets the monomial consisting of all involved variables.



Subsections
2011-02-10