Boolean functions. A function \( {f:\{0,1\}^n\rightarrow\{0,1\}} \) defined on the discrete cube \( {\{0,1\}^n} \) and taking its values in \( {\{0,1\}} \) is called a Boolean function. Such a function encodes typically the status of a complex system with \( {n} \) components. Here are two basic examples:
- \( {f(x)=\mathbf{1}_{\det(x)\neq0}} \) for every \( {x\in\mathcal{M}_m(\{0,1\})\equiv\{0,1\}^{m^2}} \). Here \( {n=m^2} \).
- same set and \( {f(x)=1} \) iff the graph with adjacency matrix \( {x} \) is connected.
More generally, any property of a graph can be seen as a Boolean function by encoding the graph with its adjacency matrix, which is a Boolean object. Boolean = binary = logical = \( {\{0,1\}} \). Let us recall some basic facts about Boolean calculus. For every \( {b,b’\in\{0,1\}} \),
- negation operator: \( {\mathbf{not}\ b = 1-b} \)
- and operator: \( {b\ \mathbf{and}\ b’ = bb’} \)
- or operator: \( {b\ \mathbf{or}\ b’ = b+b’-bb’=1-(1-b)(1-b’)} \)
- equality operator: \( {\mathbf{1}_{b=b’} = 1-b-b’+2bb’} \)
Note: \( {\mathbf{and}_{i\in I}b_i=\prod_{i\in I}b_i} \) and \( {\mathbf{or}_{i\in I}b_i=1-\prod_{i\in I}(1-b_i)} \) for every \( {b\in\{0,1\}^I} \).
Naive representation of Boolean functions. For every Boolean function \( {f} \), if we define \( {Z=\{x\in\{0,1\}^n:f(x)=0\}} \) then we have for all \( {x\in\{0,1\}^n} \),
\[ f(x)={\mathbf{or}}_{s\not\in Z}{\mathbf{and}}_{1\leq i\leq n}(x_i=s_i) =1-\prod_{s\not\in Z}\left(1-\prod_{1\leq i\leq n}(1-s_i-x_i+2s_ix_i)\right) \]
and
\[ f(x)={\mathbf{and}}_{s\in Z}{\mathbf{or}}_{1\leq i\leq n}(x_i\neq s_i) =\prod_{s\in Z}\left(1-\prod_{1\leq i\leq n}(1-s_i-x_i+2s_ix_i)\right). \]
The left hand side formulas mean that \( {f} \) can be expressed as a finite combination of the logical variables \( {x_1,\ldots,x_n} \) and logical operators. In binary terms, the right hand side formulas mean that \( {f} \) is a polynomial in \( {x_1,\ldots,x_n} \). This is a remarkable polynomial fact! We will see that the notion of minimal cuts allows to reduce the representation complexity. On the other hand, we may observe that since \( {b^2=b} \) for all \( {b\in\{0,1\}} \), any polynomial in Boolean variables is identical to a polynomial of degree at most \( {2} \) in each variable.
Cuts. A cut of a Boolean function \( {f} \) is a couple \( {(I,s)} \) where \( {\varnothing\neq I\subset\{1,\ldots,n\}} \) and \( {s\in\{0,1\}^I} \) such that for all \( {x\in\{0,1\}^n} \) we have \( {f(x)=0} \) if \( {x_i=s_i} \) for all \( {i\in I} \). The Boolean function identically equal to \( {1} \) does not have cuts. For a Boolean function \( {f} \), if \( {f(x)=1} \) for some \( {x\in\{0,1\}^n} \), then for any cut \( {(I,s)} \) of \( {f} \) we have \( {x_i\neq s_i} \) for some \( {i\in I} \). Conversely, if \( {f(x)=0} \) for some \( {x\in\{0,1\}^n} \) then there exists a cut \( {(I,s)} \) of \( {f} \) such that \( {x_i=s_i} \) for all \( {i\in I} \) (take for instance the cut \( {(I,s)=(\{1,\ldots,n\},x))} \).
Representation of Boolean functions with their minimal cuts. For a Boolean function \( {f} \), let us consider the partial order on its cuts defined by \( {(I,s)\leq (I’,s’)} \) iff \( {I\subset I’} \) and \( {s_i=s’_i} \) for all \( {i\in I} \). The minimal elements are called minimal cuts.
For every \( {x\in\{0,1\}^n} \), we see that \( {f(x)=1} \) iff for any minimal cut \( {(I,s)} \) we have \( {x_i\neq s_i} \) for some \( {i\in I} \). Also, if \( {\mathcal{S}} \) stands for the set of minimal cuts, then for all \( {x\in\{0,1\}^n} \),
\[ f(x) =\mathbf{and}_{(I,s)\in\mathcal{S}}\mathbf{or}_{i\in I}(x_i\neq s_i) =\prod_{(I,s)\in\mathcal{S}}\left(1-\prod_{i\in I}(1-s_i-x_i+2s_ix_i)\right). \]
We have taken the convention \( {\prod_\varnothing=1} \). The Boolean function \( {f} \) is polynomial in the Boolean variables \( {x_1,\ldots,x_n} \). We already know that it can be simplified into a polynomial of degree at most two in each variable. The total degree is at most \( {n} \), and this is achieved by the Boolean function \( {x_1\cdots x_n} \), for which the minimal cuts are \( {(\{1\},0),\ldots,(\{n\},0)} \). Note that the Boolean function \( {\mathbf{1}_{x_1+\cdots+x_n\neq0}} \) has a unique minimal cut \( {(\{1,\ldots,n\},(0,\ldots,0))} \), and
\[ \mathbf{1}_{x_1+\cdots+x_n\neq0}=1-\prod_{i=1}^n(1-x_i). \]
Percolation. Let us consider the square graph obtained by taking the edges of \( {\mathbb{Z}^2} \) with vertices in \( {\{0,\ldots,L\}^2} \) for some fixed \( {L\in\{1,2,\ldots\}} \). On each edge we put a Boolean variable and we consider the Boolean function \( {f} \) equal to \( {1} \) iff there exists a path with edges marked \( {1} \) connecting \( {(0,0)} \) with \( {(L,L)} \). Could you list the minimal cuts? They give a polynomial representation of \( {f} \). The number of cuts is huge, as for most complex systems.
Related. Boolean functions are called structure functions in systems reliability and engineering. Two other famous problems on Boolean functions:
Goodies: recent lecture notes by G. Kalai and E. Mossel.
Recent Comments