# Conversion between Logic and Algebraic Expressions of Boolean Control Networks
## 2 Preliminaries  
This section reviews some basic concepts from Boolean functions and Boolean control networks (see, e.g., [6, 7]). A Boolean function is a function of the form  
\[f:\Delta^{n}\rightarrow\Delta, \tag{1}\]  
where \(\Delta=\{\text{True},\text{False}\}\) is the logical domain and \(n\) is the arity of the function. Any logical function with \(n\) variables can be expressed as a propositional formula in variables \(x_{1},x_{2},\ldots,x_{n}\). For simplicity, the logical disjunction \(x\lor y\), conjunction \(x\wedge y\) and negation \(\
eg x\) are denoted by \(x+y\), \(xy\) and \(\bar{x}\), respec- tively. A truth table specifies the values of a Boolean function for every possible combination of values of the variables in the function. Label the rows of the truth table of Boolean function (1) by \(0,1,\ldots,2^{n}-1\), respectively, and denote by \(s_{i}\) the function value in the row \(i\) of the truth table, where \(i\in\{0,1,\ldots,2^{n}-1\}\). A minterm of \(n\) variables is a product of \(n\) literals in which each variable appears exactly once in either true or complemented form, but not both. The minterm which corresponds to the row \(i\) of truth table is designated as \(m_{i}\). Boolean function (1) can uniquely be written as a sum of minterms, i.e.,  
\[f(x_{1},x_{2},\ldots,x_{n})=m_{i_{1}}+m_{i_{2}}+\cdots+m_{i_{k}}:=\sum m(i_{1},i_{2},\ldots,i_{k}), \tag{2}\]  
which is called the minterm canonical form of \(f\). **Definition 1** ([11]). : _For \(A\in\mathbb{R}^{m\times n}\) and \(B\in\mathbb{R}^{p\times q}\), the semi-tensor product (STP) of \(A\) and \(B\) is defined as_  
\[A\ltimes B=(A\otimes I_{\alpha/n})\times(B\otimes I_{\alpha/p}),\]  
_where \(\alpha\) is the least common multiple of \(n\) and \(p\), \(I\) is the identity matrix, \(\otimes\) and \(\times\) are the Kronecker product and conventional product of matrices, respectively._The STP has left-right dual forms. The STP mentioned in this paper is the left one. Using STP, a Boolean function can be converted into an algebraic form. Denote by \(\delta_{n}^{j}\) the \(j\)-th column of identity matrix \(l_{n}\), where \(j\in\{1,2,\ldots,n\}\). Represent the logical values \"True\" and \"False\" by  
\[\delta_{2}^{1}= \begin{pmatrix}1\\ 0\end{pmatrix} \text{ and }\delta_{2}^{2}= \begin{pmatrix}0\\ 1\end{pmatrix} ,\]  
respectively. Then, Boolean function (1) can be equivalently represented as  
\[f:\{\delta_{2}^{1},\delta_{2}^{2}\}^{n}\rightarrow\{\delta_{2}^{1},\delta_{2 }^{2}\}.\]  
For the sake of brevity, a matrix of the form \(\{\delta_{n}^{j_{1}}\;\delta_{n}^{j_{2}}\;\ldots\;\delta_{n}^{j_{k}}\}\) is briefly denoted by \(\delta_{n}[j_{1},j_{2},\ldots,j_{k}]\). **Lemma 1** ([11]). : _For Boolean function (1), there exists a unique binary matrix \(M_{f}\in\{0,1\}^{2\times 2^{n}}\) such that_  
\[f(x_{1},x_{2},\ldots,x_{n})=M_{f}\ltimes x_{1}\ltimes x_{2}\ltimes\cdots\ltimes x _{n}, \tag{3}\]  
_in which \(M_{f}\) is called the structure matrix of \(f\)._  
A Boolean network (BN) with \(n\) variables is described as  
\[\left\{ \begin{array}{rcl}x_{1}(t+1)&=&f_{1}(x_{1}(t),\,x_{2}(t),\,\ldots,\, x_{n}(t)),\\ x_{2}(t+1)&=&f_{2}(x_{1}(t),\,x_{2}(t),\,\ldots,\,x_{n}(t)),\\ \vdots\\ x_{n}(t+1)&=&f_{n}(x_{1}(t),\,x_{2}(t),\,\ldots,\,x_{n}(t)),\end{array} \right. \tag{4}\]  
where \(f_{j}\) (\(j\in\{1,2,\ldots,n\}\)) are Boolean functions, and \(x_{j}(\cdot)\in\{0,1\}\) (\(j\in\{1,2,\ldots,n\}\)) are states. **Lemma 2** ([11]). : _Let \(x(t)=\ltimes_{j=1}^{n}x_{j}(t)\in\{0,1\}^{2^{n}}\). Then, there exists a unique matrix \(L\in\{0,1\}^{2^{n}\times 2^{n}}\) such that BN (4) can be converted into a standard discrete-time dynamic system_  
\[x(t+1)=L\ltimes x(t),\;t=0,1,\cdots, \tag{5}\]  
_where \(L\) is called the state transition matrix of BN (4)._  
A Boolean control network (BCN) with \(m\) inputs and \(p\) outputs is described as  
\[\left\{