NAND2Tetris: The Magic of NAND
Tags: nand2tetris, booleanalgebra, logic
Published: 2019-05-22 06:31:41

---
title: NAND2Tetris: The Magic of NAND
series: nand2tetris
published: true
description: 
tags: nand2tetris, boolean algebra, logic
---

So, I've embarked on the journey of [nand2tetris](https://www.nand2tetris.org/).

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.

![](https://thepracticaldev.s3.amazonaws.com/i/adl8mn3i7ec25c0ae4pa.png)

## 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.

![](https://thepracticaldev.s3.amazonaws.com/i/vznifwgz881bjzfym4p0.png)

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](https://dev.to/tttaaannnggg/a-couple-of-beautiful-things-i-learned-today-3864) 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.

![](https://thepracticaldev.s3.amazonaws.com/i/1epcqm2ixb58s9htmzn3.png)

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.

![](https://thepracticaldev.s3.amazonaws.com/i/sqzpe9gwsvd30zqcnwn5.png)

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!