All you need is NAND, NAND, NAND; NAND is all you need!

All animations courtesy of my Wireworld built in Svelte

If you’ve spent any time programming, you may recognize the “big three” boolean operators: AND, OR, and NOT (often written &&, ||, ! in many programming languages). Together these oper…

All animations courtesy of my Wireworld built in Svelte

If you’ve spent any time programming, you may recognize the “big three” boolean operators: AND, OR, and NOT (often written &&, ||, ! in many programming languages). Together these operators are functionally complete, meaning they can be used to build any boolean logic. Combined with some sort of memory, functionally complete operators can be used to build a turing complete system.

What if I told you we need only one operator to be functionally complete? That’s right! All you need is NAND (short for Not AND; !(x && y)). But don’t trust me, let me show you.



Proving NAND is all you need



NAND is NOT

You’ve seen the animation of a NAND in a Wireworld above (NAND-imation anyone?). What would happen if instead of two inputs, we tied them both together as one input?

Animation of NAND acting as a NOT

Notice how this new operator constantly outputs until an input is received and then it stops (aka NOT logic). In JavaScript, if we had a nand(x, y) function, we could make not() like this:

const not = (x) => nand(x, x);

Look at NAND’s truth table where both inputs are the same:

X Y = O
false false = true
true true = false

Looks a lot like NOT to me! NAND is NOT.



NAND is AND

Look at NAND’s full truth table compared to AND:

X Y = NAND AND
false false = true false
false true = true false
true false = true false
true true = false true

It’s perfectly inverse (that is the definition of Not AND after all). If only we could NOT the output of our NAND, we would have AND… if you read the last section, that’s exactly what we have! Just put the output of a NAND as both inputs to another NAND and viola! an AND appears:

Animation of two NANDs acting as an AND

Again to relate this to code it might look something like this:

const and = (x, y) => nand(nand(x, y), nand(x, y));



NAND is OR

Perhaps the trickiest one yet. AND and NOT were fairly obvious looking at their truth tables. But OR?

X Y = NAND OR
false false = true false
false true = true true
true false = true true
true true = false true

OR is tantalizingly close to NAND. They both have three outputs of true and only one case of false. But the tables are backwards! What are we supposed to do with this? What if I showed you a table with the opposite inputs:

NOT X NOT Y = OR
true true = true
true false = true
false true = true
false false = false

Does that pattern look familiar? If we NOT our inputs first (using the same NAND as NOT trick) and put those as the inputs to our NAND, we’ll get an OR!

Animation of three NANDs acting as an OR

We’ll finish out our code examples:

const or = (x, y) => nand(nand(x, x), nand(y, y));

(We just did DeMorgan’s Theorem a very cool trick for making boolean code more readable; but we’ll talk more about that later)



NAND is all you need

If you accept that AND, OR, and NOT are functionally complete, since NAND can build each of those three things, NAND, all by itself, is functionally complete!

So yes, NAND is all you need… but please don’t write all your booleans using only NANDs. This is for your edification and education.



Why should I care?



Problem Transformations Solve Problems

What is the difference between a Bubble Sort and a Quick Sort? They will both give an equally sorted output after all. The importance comes in performance. Because while they are logically equivalent they are not operationally equivalent; one of them will finish faster when a physical computer executes the sort.

Many, many things in the business of software development see drastic improvements from transforming the physical operations while keeping logical equivalence. The better we become at this skill, the better programmers we become. (One way to become better is seeing examples, like this).



NAND Runs the World

It just so happens that in real-world computer chips NAND is one of the easiest things to build. If you’ve ever heard of 3D NAND, you now know what that NAND stands for. And when your code works the first time around, thank a NAND gate.



It’s Just Cool!

Who would have thought that just one operator can run the whole world?


Print Share Comment Cite Upload Translate
APA
Nathan Kallman | Sciencx (2024-03-28T14:21:41+00:00) » All you need is NAND, NAND, NAND; NAND is all you need!. Retrieved from https://www.scien.cx/2021/04/19/all-you-need-is-nand-nand-nand-nand-is-all-you-need/.
MLA
" » All you need is NAND, NAND, NAND; NAND is all you need!." Nathan Kallman | Sciencx - Monday April 19, 2021, https://www.scien.cx/2021/04/19/all-you-need-is-nand-nand-nand-nand-is-all-you-need/
HARVARD
Nathan Kallman | Sciencx Monday April 19, 2021 » All you need is NAND, NAND, NAND; NAND is all you need!., viewed 2024-03-28T14:21:41+00:00,<https://www.scien.cx/2021/04/19/all-you-need-is-nand-nand-nand-nand-is-all-you-need/>
VANCOUVER
Nathan Kallman | Sciencx - » All you need is NAND, NAND, NAND; NAND is all you need!. [Internet]. [Accessed 2024-03-28T14:21:41+00:00]. Available from: https://www.scien.cx/2021/04/19/all-you-need-is-nand-nand-nand-nand-is-all-you-need/
CHICAGO
" » All you need is NAND, NAND, NAND; NAND is all you need!." Nathan Kallman | Sciencx - Accessed 2024-03-28T14:21:41+00:00. https://www.scien.cx/2021/04/19/all-you-need-is-nand-nand-nand-nand-is-all-you-need/
IEEE
" » All you need is NAND, NAND, NAND; NAND is all you need!." Nathan Kallman | Sciencx [Online]. Available: https://www.scien.cx/2021/04/19/all-you-need-is-nand-nand-nand-nand-is-all-you-need/. [Accessed: 2024-03-28T14:21:41+00:00]
rf:citation
» All you need is NAND, NAND, NAND; NAND is all you need! | Nathan Kallman | Sciencx | https://www.scien.cx/2021/04/19/all-you-need-is-nand-nand-nand-nand-is-all-you-need/ | 2024-03-28T14:21:41+00:00
https://github.com/addpipe/simple-recorderjs-demo