Minimal contact circuits for a sequence of Boolean functions (Q2049296)

In this paper the author develops a sequence of Boolean functions \[ \begin{array}{l} p_1(\tilde x,\tilde y)-p_1(x_1,y_1)=x_1y_1 \\ p_{n}(\tilde x,\tilde y)-p_n(x_1,\ldots ,x_n,y_1\ldots ,y_n)=x_1y_1\lor (x_1\lor y_1)p_{n-1}(x_2,\ldots ,x_n,y_2,\ldots,y_n)\\ n=2,3,\ldots \end{array} \] It is easy to see that the function \(p_n(x,y)\) specifies the transfer to the highest \((n + 1)\)-digit of the sum that occurs when two \(n\)-digit binary numbers \(x\) and \(y\) are added arithmetically (it is assumed that \(x_1,y_1\) are the highest digits). The following theorem is proved: Theorem. To implement the transfer function \(p_n(x,y)\) by a contact circuit, it is necessary and sufficient to have \(4n-2\) contacts. The resulting estimate is a contribution to mathematical theory of Control Systems.