NAND2Tetris: The Magic of NAND

So, I've embarked on the journey of nand2tetris.

What is nand2tetris? It's basically a vertically-integrated course on computer science. Starting from 0s and 1s, we build up a whole simulated computer, build an operating system on top of it, build a compiler on top of that OS, and finally build a game on that whole tower.

It's quite a daunting task. How do we get started?

The Magic of NAND

In computers (or, at least in the computer that we're implementing), there is a single circuit that we basically use for everything. It's called NAND. If you're familiar with boolean logic, it's defined something like this: NOT(A AND B)).

The truth table for NAND looks like this:

 A B | OUTPUT
==============
 0 0 |   1
 0 1 |   1
 1 0 |   1
 1 1 |   0

While this may seem unimpressive, our NAND gate includes behaviors in it such that we can create literally any other logic gate from some combination of just NAND gates. We won't be getting into formal proofs, but we'll demonstrate how to build NOT, AND, and OR from just NAND. (taking NAND as a given)

NOT

We'll start with NOT, since it's the simplest operation. The secret to NOT has to do with a property of AND. Anything AND itself simply outputs itself. Have a look: 0 AND 0 is 0, and 1 AND 1 is 1.

If we consider NAND to be a combination of NOT and AND, a value NAND itself will cancel out the AND, leaving the NOT operation. If we refer back to our truth table, 0 NAND 0 is 1 and 1 NAND 1 is 0. So, NOT A is A NAND A

Here's roughly what the logic gates look like. I'll represent NAND as a box with N written on it. If we've only got one input, we'll assume that it's hooked up to both inputs.

AND

Now that we've got a NOT, it's pretty easy to get to AND, for fairly self-evident reasons. A NOT inverts a value, so NOTing a NOT will cancel out the NOT, leaving the original value. ~~0 outputs 0, and ~~1 outputs 1.

NAND is NOT applied to the result of an AND, so if we cancel out the NOT, we're left with the AND operation. We've already built a NOT, and can simply add it to the output of our NAND

The operation looks like this: (A NAND B) NAND (A NAND B), but it's easier to draw a diagram.

If we have AND and NOT, it won't be too hard to derive OR.

OR

OR can be built through DeMorgan's law, which I've been lucky enough to derive myself a few months ago. Basically, we can represent A OR B as NOT ( NOT(A) AND NOT(B)).

if our NOT is A NAND A and our AND is made up of (A NAND B) NAND (A NAND B), we actually have enough to build an OR by substituting them in for their relevant terms.

This will be a mess to start, but we'll simplify it.

First, let's replace our NOTs, since they're simplest to do. NOT(A) is A NAND A and NOT(B) is B NAND B.

NOT( (A NAND A) AND (B NAND B) )

The overall NOT will take its term (A NAND A) AND (B NAND B) and NAND it with itself as both inputs. It'll come out like this:

((A NAND A) AND (B NAND B)) NAND ((A NAND A) AND (B NAND B))

Now, AND translates as follows: A AND B = (A NAND B) NAND (A NAND B). If we make our substitution where A = (A NAND B) and B = (B NAND B), this happens:

(((A NAND A) NAND (B NAND B)) NAND ((A NAND A) NAND (B NAND B))) NAND (((A NAND A) NAND (B NAND B)) NAND ((A NAND A) NAND (B NAND B)))

Which is, of course, completely unreadable. Let's represent it visually instead.

This is difficult to see in the written version of this logic gate implementation, but our last two NANDs are simply acting as NOT operators, flipping our output value, then flipping it back. We can simplify our logic gate by removing them, since ~~A is just A, no matter the value.

Now, if we walk backwards from our diagram, we can translate it back into a statement.

(A NAND A) NAND (B NAND B)

Not so bad.

We'll be building more complex systems in the future, but this is certainly a start!