Nand-To-Tetris #1: Thoughts on NAND
Why would we define the most basic logical operator in terms of operators that we use it to construct? We've created a circular dependency at the lowest levels of logic, smh
I've decided to build a computer from scratch.
In looking at the landscape of guides on how to do something like this, I stumbled upon a book called 'The Elements of Computing Systems' (I ordered the second edition). I was attracted to the name and especially the subtitle: "Building a modern computer from first principles". I ordered it from Amazon right away.
So this book arrived and told me I would be building a computer from first principles.
Well, what is the most basic building block of a computer? Logic. And how do we codify logic in circuits? Logic Gates.
We already know that any logical statement can be found by combining the logical operators (AND, OR, NOT)... but did you know that all of THOSE logical operators can be created by composing just the logical operator NAND?
And thus, the foundations of my journey to build a computer would start with the humble NAND gate.
But you might be thinking, what the hell is a NAND?
I couldn't figure this out. I mean, sure, I know it stands for NOT AND, and I know its properties as a logic gate, but NAND gates are used to build both the NOT gate and the AND gate, so how can we define it in terms of NOT and AND?
So ignoring circuits for a moment and just thinking about the way we use logical operators in natural language, what is a natural language translation for NAND that doesn't rely on the words "not" or "and" (which, again I will remind you, can actually be COMPOSED merely of a number of NAND operators, and therefore can not be used as a prerequisite to defining the NAND operator, or you would have a circular definition).
I didn't know. NAND... NAND... NAND...
Well, let's think about some sentences with truth values. Let's take 2: statement A, and statement B.
A: I love Priya
B: I hate Priya
(Priya is my dear wife, and so, A is true and B is false.)
Okay, so what is the truth value of A AND B? (I love Priya AND I hate Priya) Clearly this is False.
That being said, what about "I love Priya OR I hate Priya"? Is that True? YES. That's true because OR is true even when only one statement is True.
Remember that truth values (since there are only two) can be represented with a simple 1 or 0. We'll take 1 to mean true, so A = 1 and B = 0...
Using this, we can construct truth tables for each logical operator:
Here are the truth tables for AND, OR, NAND, and NOR:
AND and OR are both intuitively obvious to us. Why? Because we use them in natural language all the time. We could derive these truth tables from scratch.
A AND B is true only when both A and B are true. A OR B is true when either A or B or both are true. A NOR B is true when NEITHER A nor B are true. Look, I even use the words naturally because the words literally mean their logical equivalent.
But I have no intuition for "NAND", because we never learn it in English. But is there a synonym?
Here are the logical statements that encompass NAND in plain English, so we can start chewing on them:
1) when neither A nor B are true, NAND is true
2) when either A or B is true, NAND is true
3) when both A and B is true, NAND is false
Let's focus on 3 for a second. What else is false when BOTH A and B are True?
Well, my first thought was the word "contradicts". Because if both A and B are true, then A cannot contradict B. We KNOW that A is true and B is true means [A contradicts B] is False.
So what is "contradicts"?
Well, contradicts is a form of conditional statement. It says: if A, then not B, AND if B then not A.
if A is true and B is true, that means A contradicts B is False. [1, 1 → 0]
if A is true and B is false, that means A contradicts B is True. [1, 0 → 1]
if B is true and A is false, that means A contradicts B is True. [0, 1 → 1]
if A is false and B is false, then… ?? [0, 0 → ?]
Well in conditional logic, this is complicated, because your conditional premise is false. But if we have a false premise, then we can't really say anything about whether our conclusion is true or false.
However, in cases like this, logicians tend to say that the statement is "vacuously True".
So if both A and B are false, then A contradicts B is neither True nor False, but it's definitely not False (they don't contradict!), so we say it's "vacuously True".
In other words, our truth tables match! NAND, and "contradicts" have identical truth tables.
This presents interesting ideas about logic. If all logical gates can be constructed from just NAND gates, does that mean all of computing can be considered a series of nested contradictions, or is this a bridge too far, overdrawing the analogy?
I will investigate further as I progress in the course, but the main thing I want to point out from my early thoughts on NAND is that NAND is a horrible, horrible name for the most fundamental, base unit of computing.
If the NOT operator and the AND operator are both architected by arranging NAND (NOT-AND) operations, then why the hell would we call it "NOT-AND".
Furthermore, every other basic logic gate has a correlated natural language word that is commonly used in English. That the most fundamental gate is one that doesn't have any natural language equivalent is a serious oversight. Maybe "CONTRA" isn't the best name for this gate, but I know that NAND is definitely not.
If you know anyone else who has written about this, please link me to their writing below. I'm putting together a course on the foundations of computing, and I want to introduce NAND gates through a natural language analogy -- I'd like to pick something with strong roots.
I’ve put NAND-To-Tetris posts in a separate section of my blog. Feel free to unsubscribe to that section if you wouldn’t like these updates.
If you do want updates, subscribe here: