Today I started on the first project in the NAND2Tetris course on computer science from first principles! But I didn’t get very far because I got sidetracked by some interesting mathematical questions that very quickly took me beyond the limits of my understanding! I had so much fun being curious about that stuff, I didn’t even care about finishing the project yet! So here’s what happened:
The challenge: implement these 15 chips using nothing but NAND gates and the chips you’ve already constructed from those NAND gates. Then complete the HDL files so that the supplied test scripts produce outputs that match the supplied compare files.
Philosophical note: I love the simple, dualistic universe of binary! Its black-and-white logic is a welcome break from the murky gray areas I find myself swimming through in everyday life. There are no truth tables to guide my decisions in the analog world. Or maybe there are, but they’re just too big for me to comprehend! Maybe we do live in a fundamentally digital universe and “grey area” is just an illusion created by complexity. On a practical level, I definitely find that reducing the complexity of any real-world scenario makes decisions much easier to make. Like Yoda says, “Do or do not. There is no try.”
Logistical note: I’ll try my best to respect the wishes of the course designers and not just give away the solutions, while still documenting what I’ve learned by finding them.
Fun with a single NAND gate
First I wondered: what can you can do with a single NAND gate? I think I have six options: use two inputs (like A and B), use two copies of one input (like A and A), use one input and the constant 1, use one input and the constant 0, use the constant 1 for both inputs, or use the constant 0 for both inputs.
But I don’t know why you’d ever use one of those last two options, because two constant inputs will give you one constant output, which means the logic gate wouldn’t actually be changing anything so it would be pretty useless! So let’s just say I have four options.
(This is easier to demonstrate with a drawing, but it would take a little while for me to actually add images to this blog post so I’ll skip that for now. After all, these notes are really just for me! Maybe I’ll make a video about this later and worry about the visualization then.)
Anyway, I noticed in the truth table for the NAND function that the output for A=0, B=0 and for A=1, B=1 is the negation of the input values! So NAND has a NOT function built right into it – yay, a twofer! Actually, it looks like there are two ways to implement the NOT function using a single NAND gate, unless I missed something. (I wouldn’t be surprised if I did, because I have no clue what I’m doing!)
Fun with two NAND gates
I was going to spend some time playing around with the different ways I could combine two NAND gates, but then I realized there’s only one way to do it: connect the output of one into an input of the other!
Then there are five things you can do with the other input of the second gate: pipe in the input A or B, the constants 1 or 0, or – and this took me a little while to think of – you can also pipe in a second copy of the output from the first gate!
The very name of a NAND gate – which stands for “NOT AND” – points to a solution for turning a NAND gate into an AND gate. (Yay double negatives!) Because there seem to be two ways to build a NOT gate, there are at least two ways to build an AND gate. I did stumble across a third way to make an AND gate, but it’s definitely less efficient.
That made me wonder: if I can implement the same function with two gates and with three gates, then does that mean it must also be possible to make it with four, six, eight, twelve, or any multiple of the original sets of gates? Does that mean there are an infinite number of ways to implement a given Boolean function? My gut says yes, but I’m not sure I’d know how to prove that. It seems like it would be easy, but I’ll leave that for later.
It seems like there would only be two outcomes when stringing together multiple copies of the same logic gate: either the output stays the same, or the output is inverted. I wonder if that’s true! Something to play with later. It seems intuitively true, because if you pipe the outputs from two copies of the same gate into the inputs for the next gate, then the next gate’s inputs would always be either A=0, B=0 or A=1, B=1, and if you have only two possible inputs then you’d have only two possible outputs! I think? My brain gets foggy between 2pm and 5pm so let’s leave that for later.
Turning NAND into OR is like turning lead into gold!
Implementing AND and NOT was pretty easy, but I cannot for the life of me figure out how to implement the OR function! If I look at the truth tables, it’s easy to see how negation fits into the mix, but to get from NAND to OR I need to flip the whole thing upside-down! I stared at this on paper for a while, until the other patrons at this coffee shop started giving me weird looks. But staring didn’t reveal any answers.
Then I tried some random combinations of the gates I’ve already built, but no luck. I can change the bits several different ways, but I always end up back at square one with an inefficient equivalent of a NAND or AND gate. What am I missing?
After a walk and some more coffee, I remembered about De Morgan’s laws, which were mentioned in the video lectures in the first week of the Coursera NAND2Tetris course. But I found them utterly mystifying:
“The negation of a conjunction is the disjunction of the negations. The negation of a disjunction is the conjunction of the negations.”
This sounds like a Danny Kaye skit!
In other words: NOT(x AND y) is the same as (NOT x) OR (NOT y) and conversely, NOT (x OR y) is the same as (NOT x) AND (NOT Y).
I know this is the missing ingredient for my implementation of an OR gate, but why?! Right now, these laws looks like a magic spell that turns AND into OR the same way an alchemist would turn lead into gold! (Wikipedia describes the proof of De Morgan’s laws as “trivial”, but to me this formal proof looks anything but trivial!)
This is where I take a break to watch Danny Kaye in “The Court Jester”:
After a long walk, I wrote out De Morgan’s laws, drew them as circuit diagrams, wrote out the truth tables for each step, and that’s when I finally had my “aha!” moment:
I forgot that I can invert the inputs!
How could I forget something so simple? I giggled out loud and my coffee shop neighbors all looked up from their laptops for a brief moment. In all the implementations I tried for combining AND gates and NOT gates, I never tried piping both of the original inputs through NOT gates! It’s as if my brain invented a new (and incorrect) rule out of thin air.
Here’s what I missed: I had incorrectly assumed that negating both inputs would have no effect, as if the negations would cancel each other out. (Negations only cancel each other out if you’re double-negating the same term.) If you write out every combination of two inputs and then write every combination of their negations, you end up with the same combinations, just in a different order: 00, 01, 10, 11 and 11, 10, 01, 00. Either way, you’re still counting in binary; you’re just counting forward or backward.
Well, it turns out that counting backward is exactly what I needed! Just a few paragraphs ago, I had written that “I need to flip the whole thing upside-down!” What I meant was that I saw my NAND gate’s output was 1,1,1,0 and my desired output (for an OR gate) was the same set of numbers, but with its order reversed: 0,1,1,1.
It’s easy to see what happens when you invert the output of a function (to turn 1,1,1,0 into 0,0,0,1), but it wasn’t obvious to me how to invert the order of the ouput.
It seems so obvious in hindsight: to reverse the order of the ouput, just reverse the order of the input! And to reverse the order of the input, you can just invert both inputs!
Actually, that last part isn’t so obvious. I just stumbled across an interesting property of the binary number system that I had never noticed before: counting backward is the same as counting forward and inverting each digit!
And now I’m back at my usual question: but why?! I bet this has something to do with the idea of complements in positional number systems, because when I tried counting forward and backward in the decimal system, I noticed that you could get from one set of numbers to the other by subtracting each number from 9. And that seems utterly magical! Why in the world does that work?
I bet the people in this coffee shop are wondering why I have three sheets of paper in front of me covered in colummns of numbers. Looking at them right now, I think I’ve completely lost my mind. This is how I’m spending my Sunday afternoon?
Yes, yes it is.
Learning summary (#TIL)
Time to go do other stuff for a while. So what did I accomplish today?
- I implemented AND, OR, and NOT using NAND gates.
- I realized just how much I like the primitive duality embodied in binary and Boolean algebra.
- I identified every possible thing you can do with one NAND gate and with two connected NAND gates.
- I thought of a couple interesting conjectures about logic gates and Boolean algebra.
- I reviewed De Morgan’s laws and finally learned what they are, and I think I’ll remember them from now on!
- I discoverd that binary has a special property: counting backward is the same as counting forward and inverting each digit!
- I went spelunking into the tunnel of confusion and reached the light at the end: the glorious “aha!” moment, the holy grail of any learning expedition!
Questions
- Are there an infinite number of ways to implement a given Boolean function?
- If you string together multiple copies of the same logic gate, is it true that the output can only be either the same as the base gate’s output or the negation of the base gate’s output? Or can you create entirely different logic gates by just stringing together copies of the same type of gate?
- Once again: why are De Morgan’s laws true?
- Why is it that counting backward in binary is the same as counting forward and inverting each digit?
- Why does the method of complements work and what does that reveal about the nature of positional number systems?
- What does it mean to say the NOT operator is an “isomorphism between positive logic and negative logic”?
- What is duality in the context of mathematics?
Next steps
- Implement the other 12 chips required for the first NAND2Tetris project.
- Write up my implementations in HDL and test them with the hardware simulator.
Time breakdown
- Exploring computer science and math: 5 hours 35 min
- NAND2Tetris project 1 implementations: 1 hour 40 min
- Playing with binary: 26 min
- Researching, thinking, writing: 3 hours 29 min
- Learn to Code LA emails and followup: 34 min