Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 9

Write $x\uparrow y=\neg (x\wedge y)$ for a two-input NAND gate. Three elementary constructions areThe 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$. ThusA 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:

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. ConsequentlyFor 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.

The printed word “even” conflicts with the displayed numbers: all ten listed prime numbers are odd, and $2$ is the only even prime number. The scan confirms that wording.^[ref] We first construct the detector for the explicitly listed numbers, then add $2$ as requested. The literal even-prime detector is also given below.

Let the five input bits be $A,B,C,D,E$ with value $16A+8B+4C+2D+E$. Every listed number has $E=1$. For that plane, the four-variable Karnaugh map is

The entire $E=0$ plane is zero. Five valid groups in the displayed Karnaugh map give the product termsIncluding $E$, their accepted numbers are respectively $\{3,11\}$, $\{5,13\}$, $\{17,19\}$, $\{29,31\}$, and $\{3,7,19,23\}$. Their union is exactly the ten listed numbers. Hence an explicit Boolean circuit is: invert $A,B,C,D$ where needed, feed the five products into five AND gates, combine those outputs with an OR gate, and AND with $E$. Its output isAny gate with more than two inputs can be replaced by a tree of two-input gates. To include the exceptional prime number $2$, detect its exact binary representation $00010$ and add one OR branch:If “even prime” is read literally instead of following the listed numbers, the complete first detector is simplyAll three formulas classify all $32$ possible inputs, including $0$ and $1$ as nonprime.