Lesson 3

Below, we define a decomposition of a function \(f(x_{1},\dotsc,x_{n}) \in B_{n}\). Let \(f_{0},f_{1} \in B_{n-1}\) be the subfunctions of \(f\), obtained by substituting \(x_{1} \gets 0\) and \(x_{1} \gets 1\), respectively: \[\begin{align*}f_{0}(x_{2}, \dotsc, x_{n})&=f(0, x_{2}, \dotsc, x_{n})\ ,\\ f_{1}(x_{2}, \dotsc, x_{n})&=f(1, x_{2}, \dotsc, x_{n})\ .\end{align*}\] It is easy to see that \[f(x_{1}, \dotsc, x_{n})= (\overline{x_1}\land f_{0}(x_{2}, \dotsc, x_{n})) \lor (x_{1} \land f_{1}(x_{2}, \dotsc, x_{n})) \ .\] Thus, we have decomposed the function \(f\) by the variable \(x_{1}\). In fact, it is also possible to decompose by several variables: \[f(x_{1}, \dotsc, x_{n})=\bigvee_{a \in \{0,1\}^m}[x_{1}=a_{1}, \dotsc, x_{m}=a_{m}] \land f_{a}(x_{m+1}, \dotsc, x_{n}) \ .\] Here \([x_{1}=a_{1}, \dotsc, x_{m}=a_{m}]\) is a function of \(x_{1}, \dotsc, x_{m}\) that equals one at exactly one point \((a_{1}, \dotsc, a_{m})\), while \(f_{a}(x_{m+1}, \dotsc, x_{n})\) is the subfunction of \(f\), obtained by substituting constants \(a_{1}, \dotsc, a_{m}\) instead of variables \(x_{1}, \dotsc, x_{m}\).