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 of the Boolean function in each gate, we will explicitly specify which function is to be used by its name, and each task statement will include the list of available functions together with their format. 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})\). 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 mimick 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 a partial credit in case 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.