Circuits of Functional Elements

Prove that the perfect, reduced, and minimal DNF for the function $\operatorname {odd}\left(x_{1}, x_{2}, \ldots , x_{n}\right)$ coincide and have $2^{n-1}$ elementary conjunctions of length $n$. $\square$

Prove that the minimal circuit for addition modulo two has complexity $L(\oplus )=4$ in the basis $\mathcal{B}_{0}$. Hint. Prove this statement for the functions $x_{1} \oplus x_{2}$ and $x_{1} \leftrightarrow x_{2}$ simultaneously.

Prove Proposition 85 on p. 260.

Proposition 85: Let $\Pi$ be a linear program with input variables $x_{1}, \ldots , x_{n}$, computing the function $f$ in the variable $y$, such that no non-input variable is used before it is assigned a value. Then there exists a formula $\Phi_{\Pi }$ with variables $x_{1}, \ldots , x_{n}$ realizing this same function.

Prove that in the basis $\mathcal{B}_{0}$ every Boolean function $f$ can be computed by a linear program in which assignment is performed to no more than three variables. Can this number be reduced to two?

Prove item 2) of Theorem 86 on p. 260.

Theorem 86, item 2): Let $\mathcal{B}$ be a basis that allows obtaining the constant 0, and let a program $\Pi$ in the basis $\mathcal{B}$, besides the input variables $x_{1}, \ldots , x_{n}$, contain $z_{1}, \ldots , z_{m}$, each of which computes the function $f_{1}, \ldots , f_{m}$ respectively. Then one can effectively construct a circuit $\mathfrak {S}_{\Pi }$ in the basis $\mathcal{B}$, containing in particular vertices $v_{1}, \ldots , v_{m}$ such that $f_{v_{i}}=f_{i}$ for $i=1, \ldots , m$.

Using the circuit $\mathrm{SUM}_{n}$, construct a circuit realizing the operation of subtracting two $n$-bit binary numbers: $d=a-b$ (assuming that $a \geqslant b$). Estimate the complexity of the resulting circuit.

Determine the depth of the circuits $\mathfrak {S}_{\oplus }, \mathfrak {S}_{\text{odd }}, \mathrm{SUM}_{1}$ and $\mathrm{SUM}_{n}$.

Two players independently choose one of the four numbers from 0 to 3. The first player wins if their sum is a power of two. Construct a circuit that determines whether the first player wins. Its inputs $u_{1}, u_{0}$ represent, in binary, the number $2 u_{1}+u_{0}$ chosen by the first player, and $v_{1}, v_{0}$ the number $2 v_{1}+v_{0}$ chosen by the second player.

Construct a circuit $\mathfrak {C}_{n}$ for comparing two $n$-digit numbers represented in binary. The circuit should have inputs $u_{n-1}, \ldots , u_{0}$ and $v_{n-1}, \ldots , v_{0}$ for the original numbers and three outputs for the result: greater, less, or equal.

Construct a circuit for multiplying two two-digit binary numbers. The circuit should have inputs $a_{1}, a_{0}$ and $b_{1}, b_{0}$ for the original numbers and four outputs for the digits of the result.

Construct a circuit that determines the result of a vote in a committee consisting of three members and a chairman. In case of a tie, the chairman's vote is decisive.

Let the argument tuples of a Boolean function of three arguments be ordered lexicographically, and let its values be given by a sequence of eight zeros and ones. Construct circuits realizing the following functions: