## 2 Methods
### Transformation to a System of Linear Inequalities  
Let us take the Boolean function \(f\): \(\mathbb{B}^{n}{\rightarrow}\{0,1\}\) of \(n\) binary variables \(\vec{x}=(x_{1},x_{2},\ldots,x_{n})\). Here \(\mathbb{B}^{n}{\rightarrow}\{\vec{x}:x_{i}\in\{0,1\}\}\), \(\mathbb{B}^{n}{\subset}\mathbb{R}^{n}\) is a set of all \(2^{n}\) vertices of an \(n\)-dimensional unit cube \(U^{n}\doteq\{\vec{x}:0\leqslant x_{i}\leqslant 1\}\), i.e., the set of all \(0{-}1\) arguments of \(n\)-variant Boolean function. For a given Boolean function \(f\), we consider (as in the previous section) the set \(F\) of \(2^{n}\) vectors in \(\mathbb{R}^{n+1}\) (a kind of graph of function \(f\)) and their convex hull:  
\[ \begin{array}{rcl}F&\doteq&\{(\vec{x},f(\vec{x})){:}\vec{x}{\in}\mathbb{B}^{ n}\},\\ \mathsf{U}[F]&\doteq&\mathsf{conv}(F).\end{array}  \tag{13}\]  
From the definitions, we have \(F{\subset}\mathbb{B}^{n+1}\) and \(\mathsf{U}[F]{\subset}U^{n+1}\). Let us establish important properties of vectors from \(F\) and polyhedron \(\mathsf{U}[F]\). **Theorem 1**: _Let \(F\) and \(\mathsf{U}[F]\) be defined by (13). Then, we have the following:_  
\((a)\) _Every vector \((\vec{x},f(\vec{x})){\in}F\) is an extreme point of convex hull \(\mathsf{U}[F]\) (i.e., \((\vec{x},f(\vec{x}))\) is a vertex of polyhedron \(\mathsf{U}[F]\));_  
\((b)\) _If \((\vec{x},y){\in}\mathsf{U}[F]\) and \(\vec{x}{\in}\mathbb{B}^{n}\) then \(y=f(\vec{x})\)._  
Let us take any \((\vec{x}_{k},f(\vec{x}_{k})){\in}F\). If it is not an extreme point of \(\mathsf{U}[F]\), then there exists a nontrivial convex combination (hereinafter \(\vec{x}_{q}{\in}B^{n}(q=1{:}2^{n})\))  
\[(\vec{x}_{k},f(\vec{x}_{k}))=\sum_{q=1:2^{n}}\lambda_{q}(\vec{x}_{q},f(\vec{x} _{q})),\ \lambda_{q}\geqslant 0,\lambda_{k}=0,\ \sum_{q=1:2^{n}}\lambda_{q}=1. \tag{14}\]  
However, (14) implies impossible equation  
\[\vec{x}_{k}=\sum_{q=1:2^{n}}\lambda_{q}\vec{x}_{q},\ \lambda_{q}\geqslant 0, \lambda_{k}=0,\ \sum_{q=1:2^{n}}\lambda_{q}=1,\]  
because \(\vec{x}_{k}{\in}B^{n}\) is a vertex of unit cube \(U^{n}\) and cannot be represented as a convex combination of other vertices of \(\mathsf{U}[F]\). So, item \((a)\) is proved. The proof of item \((b)\) is quite similar. Let \(\vec{x}_{k}{\in}\mathbb{B}^{n}\). If \((\vec{x}_{k},y){\in}\mathsf{U}[F]\), then  
\[(\vec{x}_{k},y))=\sum_{q=1:2^{n}}\lambda_{q}(\vec{x}_{q},f(\vec{x}_{q})),\ \lambda_{q} \geqslant 0,\ \sum_{q=1:2^{n}}\lambda_{i}=1. \tag{15}\]  
So, we have  
\[\vec{x}_{k}=\sum_{q=1:2^{n}}\lambda_{q}\vec{x}_{q},\ \lambda_{q}\geqslant 0, \ \sum_{q=1:2^{n}}\lambda_{q}=1,\]  
which implies \(\lambda_{k}=1\) and \(y=f(\vec{x}_{k})\) (see (15)). Theorem 1 is proved. Thus, the function \(f\) may be uniquely defined by corresponding convex polyhedron \(\mathsf{U}[F]\). For example, see in Figure 1 examples of polyhedrons of Boolean functions on two variables. As it is well known in the convex analysis (e.g., see the classical book [8], Section 19) any polyhedron may be uniquely represented either by the set of its vertices, the so-called V-representation, or by the system of linear inequalities, the so-called H-representation. The sought system of the linear inequalities is the H-representation of the polyhedron \(\mathsf{U}[F]\). Therefore, there exists a system of linear inequalities of \(n+1\) variables \((\vec{x},x_{n+1})\):  
\[\mathsf{S}(\vec{x},x_{n+1})=\{a_{i}+l_{i}(\vec{x})+b_{i}x_{n+1}\geqslant 0:i=1, \ldots,m\} \tag{16}\]  
(where \(a_{i},b_{i},b_{i}\
eq 0\) are scalars, and \(l_{i}(\vec{x})\) are linear functions of \(n\) variables) such that  
\[\mathsf{U}[F]=\{(\vec{x},x_{n+1}):a_{i}+l_{i}(\vec{x})+b_{i}x_{n+1}\geqslant 0 :i=1,\ldots,m\}.\]  
Finally, from Theorem 1 we have\[\forall\vec{x}\in\mathbb{B}^{n}:\left\{f(\vec{x})=x_{n+1}\right\}\Leftrightarrow\left\{ a_{i}+l_{i}(\vec{x})+b_{i}x_{n+1}\geqslant 0:i=1,\ldots,m\right\}, \tag{17}\]  
i.e., for any \(\vec{x}\in\mathbb{B}^{n}\), \(f(\vec{x})\ =\ x_{n+1}\) if and only if \(\mathbb{S}(\vec{x},x_{n+1})\) holds.