Lesson 1

We already know that every Boolean function can be expressed as some combination of NAND gates (recall that a NAND gate takes two Boolean variables and returns \(1\) if and only if at least one of the variables is \(0\)). So, in the next several steps, we will construct a collection of useful functions using only NAND gates.

We also slightly modify the format of the representation of circuits. Instead of writing a truth table in each gate, we identify the gate function by a case-sensitive name. If a function \(F\) has \(t\) outputs and arity \(k\), then a gate line has the form \[\texttt{y\_{1}}\ \dotsc\ \texttt{y\_{t} x\_{1}}\ \dotsc\ \texttt{x\_{k} F}\] This means that \((y_{1},\dotsc,y_{t})=F(x_{1},\dotsc,x_{k})\).

In each task you are given some function \[F(x_{1},\dotsc,x_{k})=(y_{1},\dotsc,y_{t}).\] A submission consists only of gate lines, and the circuit size is the number of submitted lines.

The numeral in a gate name identifies over what bit-sizes it works. For example, \(\operatorname{XOR}_{16}\) takes two 16-bit values and computes their component-wise exclusive or. In a submission, append numeric subscripts directly to the base name: for example, \(x_{1}\), and \(\operatorname{XOR}_{16}\) are written as \(\texttt{x1}\), and \(\texttt{XOR16}\).

Whenever we list the bits of a variable, we list them in descending order: from the most significant bit to the least significant bit.

Below, a representation of the circuit above is shown.

a x1 x2 NAND2
b x2 x3 NAND2
c a b NAND2
y1 a x3 NAND2
y2 c y1 NAND2

This section is inspired by the NANDgame that is, in turn, inspired by the book The Elements of Computing Systems: Building a Modern Computer from First Principles by Noam Nisan and Shimon Schocken. We mimic some of the first problems from the book and gradually build more and more advanced computer components from scratch. For each problem, we have a reference solution, and you receive partial score if you come up with a design that implements the required function correctly, but with a larger number of gates. More precisely, if the reference circuit has size \(x\) whereas your circuit has size \(y\), you get a fraction \((x / y)^{1.5}\) of the score.