= Solution
Write $x\uparrow y=\neg(x\land y)$ for a two-input <NAND gate>. Three elementary constructions are
$$
\neg x=x\uparrow x,\qquad
x\land y=(x\uparrow y)\uparrow(x\uparrow y),\qquad
x\lor y=(x\uparrow x)\uparrow(y\uparrow y).
$$
The last identity is <De Morgan's laws>. To see that these operations suffice from first principles, take any finite truth table. For each row whose output is $1$, form the conjunction of input literals that matches exactly that row: use $x_i$ when the row has $x_i=1$, and $\neg x_i$ when it has $x_i=0$. Disjoin all such conjunctions. On any input, precisely its matching row conjunction can be true, so this <disjunctive normal form> equals the desired <Boolean function>.
Replace each negation, conjunction and disjunction by the displayed <NAND gate> constructions, nesting two-input gates for longer conjunctions or disjunctions. Constant outputs are available too: for any input $x$, $x\uparrow(x\uparrow x)=1$, and NANDing that value with itself gives $0$. Thus
$$
\boxed{\text{NAND alone is functionally complete for Boolean functions of positive arity}.}
$$
A zero-input constant circuit additionally needs a supplied constant signal, such as a fixed logic supply. The positive-arity construction already covers constant-valued <Boolean functions> having one or more unused inputs.
For a three-input <CMOS NAND gate>, put three <PMOS transistors> in parallel from the positive supply $V_{DD}$ to the output $Y$, and three <NMOS transistors> in series from $Y$ to ground. Each input controls one device in each network:
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2005/computing-prelims-2005-cmos-nand.png]
{title=Three-input CMOS NAND: parallel PMOS pull-up paths and a series NMOS pull-down path}
A high input turns on its <NMOS transistor> and turns off its <PMOS transistor>; a low input does the opposite. If $A=B=C=1$, every series <NMOS transistor> conducts and every <PMOS transistor> is off, pulling $Y$ low. If any input is zero, its <NMOS transistor> breaks the series path and its <PMOS transistor> provides a path to $V_{DD}$, pulling $Y$ high. Consequently
$$
\boxed{Y=\overline{ABC}.}
$$
For ideal settled inputs, the complementary networks do not simultaneously connect supply to ground. The <CMOS> arrangement gives a driven high or low output in every input case, rather than leaving the output floating.
Back to article page
