Lesson 7

Problem. Construct a component that outputs \(1\) if and only if all bits of the input are equal to \(0\). The inputs are \(x_{3},x_{2},x_{1},x_{0}\), where \(x_{3}\) is the most significant bit. The output is a single bit \(z\).

You may use only the following functions: \[\begin{aligned}\operatorname{NAND}(a,b) &= \neg(a \land b), & \operatorname{INV}(a) &= \neg a, \\ \operatorname{AND}(a,b) &= a \land b, & \operatorname{OR}(a,b) &= a \lor b, \\ \operatorname{XOR}(a,b) &= a \oplus b. &\end{aligned}\]

Examples: \[0000 \mapsto 1,\] \[0001 \mapsto 0,\] \[1010 \mapsto 0.\]

The authors' solution uses \(4\) gates.