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 token. If a function \(F\) has \(t\) outputs and arity \(k\), then a gate line has the form \[\texttt{y\_{1}}\ \dotsc\ \texttt{y\_{t} a\_{1}}\ \dotsc\ \texttt{a\_{k} F}.\] This means that \((y_{1},\dotsc,y_{t})=F(a_{1},\dotsc,a_{k})\).

A submission starts with a header line \(\texttt{n m t}\), giving the numbers of explicit inputs, gate lines, and outputs. If \(n>0\), the next line lists the \(n\) input labels; omit this line when \(n=0\). Then come exactly \(m\) gate lines and one line listing the \(t\) output labels in the required order. Mathematical subscripts are omitted from gate tokens: for example, write \(\texttt{ADD16}\) for \(\operatorname{ADD}_{16}\). 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.

3 5 2
x1 x2 x3
a x1 x2 NAND
b x2 x3 NAND
c a b NAND
w0 a x3 NAND
w1 c w0 NAND
w0 w1 NAND

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. When a new block is built, it can be used in the following problems as a basic building block. For each such synthesis problem, we have a reference solution, and you receive partial credit if you come up with a design that implements the required block correctly, but with a larger number of basic building blocks. More precisely, if the reference design has size \(x\) whereas your solution has size \(y\), you get a fraction \((x / y)^{1.5}\) of the score.