## 2 Methods
### The Case of Boolean Functions with Many Binary Arguments  
Both methods of representation of the Boolean function, either as one linear equation with original variables and binary ancillaries, or as a system of linear inequalities without binary ancillaries, may require a long computing time. If so, the following workaround may be used, based on the representation of Boolean function as a composition of Boolean functions with fewer arguments.  
Take the Boolean function \(f(\vec{x}):B^{n}{\rightarrow}\{0,1\}\), which may be represented as composition of \(K\) Boolean functions with fewer arguments:  
\[\begin{array}{l}f(\vec{x})=f(x_{1},x_{2},\ldots,x_{n})=\Phi(\vec{Y}(\vec{x}) )=\Phi\Big{(}Y_{1}(\vec{\xi}_{1}(\vec{x})),Y_{2}(\vec{\xi}_{2}(\vec{x})), \ldots,Y_{K}(\vec{\xi}_{K}(\vec{x}))\Big{)},\text{ where}\\ \forall k{\in}\{1\ldots K\}:\Big{(}Y_{k}(\vec{\xi}_{k}):B^{n_{k}}{\rightarrow} \{0,1\},\vec{\xi}_{k}(\vec{x})=\Big{\{}x_{v(k,j)}{:}j\in\{1\ldots n_{k}\} \Big{\}},n_{k}{\ll}n\Big{)}.\end{array} \tag{26}\]  
Linear Equations with Binary Ancillaries for Composition of Boolean Functions  
Let the function \(\Phi(\vec{Y})\) have the following representation as a linear equation with binary ancillaries:  
\[\Big{(}\vec{Y}{\in}B^{K},\Phi(\vec{Y})=z\Big{)}\Leftrightarrow\Big{(}\exists \vec{a}{\in}B^{M}:E(\vec{Y},\vec{a},z)=0\Big{)}, \tag{27}\]  
where \(E(\vec{Y},\vec{a},z)\) is an affine function (there may be some nonzero constant) on original binary variables \(\vec{Y}\); a set of \(M\) binary ancillaries \(\vec{a}\); and binary scalar \(z\) is a value of \(\Phi(\vec{Y})\).  
Then, let us assume that we know the similar representation for all \"sub-functions\" \(Y_{k}\) (\(k=1\):\(K\)):  
\[\Big{(}\vec{\xi}_{k}{\in}B^{n_{k}},Y_{k}(\vec{\xi}_{k})=y_{k}\Big{)} \Leftrightarrow\Big{(}\exists\vec{a}_{k}{\in}B^{m_{k}}:e_{k}(\vec{\xi}_{k}, \vec{a}_{k},y_{k})=0\Big{)}, \tag{28}\]  
where \(e_{k}(\vec{\xi}_{k},\vec{a}_{k},y_{k})\) is an affine function on a subset of original binary variables \(\vec{\xi}_{k}(\vec{x})\); a set of \(m_{k}\) binary ancillaries \(\vec{a}_{k}\); and binary scalar \(y_{k}\) is a value of \(Y_{k}(\vec{\xi}_{k})\).  
Now we can represent original function \(f(\cdot)\) (26) as a system of \(K{+}1\) linear equations and \(K{+}M{+}\sum\limits_{k=1}^{K}m_{k}\) binary ancillaries (components of vectors \(\vec{Y}{\in}B^{K}\), \(\vec{a}{\in}B^{M}\) and \(\vec{a}_{k}{\in}B^{m_{k}}\), \(k=1\) :\(K\)):  
\[\Big{(}\vec{x}{\in}B^{n},f(\vec{x}){=}\Phi(\vec{Y}(\vec{x})){=}z\Big{)} \Leftrightarrow\left\{\begin{array}{l}\exists\vec{a}{\in}B^{M}:E((y_{1},y_{2 },\ldots,y_{K}),\vec{a},z)=0;\\ \exists\vec{a}_{1}{\in}B^{m_{1}}:e_{1}(\vec{\xi}_{1}(\vec{x}),\vec{a}_{1},y_{ 1})=0;\\ \exists\vec{a}_{2}{\in}B^{m_{2}}:e_{2}(\vec{\xi}_{2}(\vec{x}),\vec{a}_{2},y_{ 2})=0;\\ \ldots\\ \exists\vec{a}_{K}{\in}B^{m_{K}}:e_{k}(\vec{\xi}_{K}(\vec{x}),\vec{a}_{K},y_{ K})=0.\end{array}\right. \tag{29}\]  
\begin{table}
\begin{tabular}{c c c} \hline  & **Boolean Formula** & **Linear Equation** \\ \hline \(\mathrm{F}(\mathrm{B},\mathrm{C},\mathrm{D})\) & \((B\wedge\mathrm{C})\vee(\
eg B\wedge D)\) & \(B+3\mathrm{C}+2D-6F+2a_{0}-3a_{1}+2a_{2}=0\) \\ \(\mathrm{G}(\mathrm{B},\mathrm{C},\mathrm{D})\) & \((B\wedge\mathrm{D})\vee(\mathrm{C}\wedge\
eg D)\) & \(3B+2\mathrm{C}+D-6G-3a_{0}+2a_{1}+2a_{2}=0\) \\