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 `NOT`

ing 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 `NOT`

s, 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 `NAND`

s 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!

## Top comments (0)