A computer from scratch - NANDing all the way

A technical side note to my first "A computer from scratch" post and In preparation for the next step, I've examined whether it's possible to build any gate from NANDs. Is it possible? YES! Let's prove it, mathematically.

Too Old For This Shit

Theorem

Any truth table can be built by combining NANDs.

Lemma 1

Any truth table can be built with OR, AND and NOT.

Proof

Any truth table is defined by N bits in input (i1, i2, …, ik, …, iN). A truth table will also have 2N outputs (out1, out2, …, outl, …, out2N).

nothing but the truth

We want to create an expression with only OR, NOT and AND that "represents" each row of inputs, in other words:

  • if outl is 1, then the expression is equal to 1 if and only if all the input match the given inputs
  • if outl is 0, then the expression is equal to 0 independently from the inputs

This allows us to combine all the expression through OR to obtain an expression for the truth table.

In case of outl = 0 the function is easy to build. It's always the function 0, which can be elided from the whole-expression OR later.
In case of outl = 1, for each input we will create a sub expression which is valued 1 if the input matches with the given value for the row, and zero otherwise. ANDing all these together will give us an expression as required (its value will be 0 if any input doesn't match, otherwise 1).

How do we create these subexpressions? If the expected input value is 0 then NOT i, if the expected input value is 1 then i.

Example

An example will make everything clear. Let's create an expression to represent the following truth table:

our truth

  1. Let's ignore all lines with value 0.

their truth

  1. Let's write in ik in place of all the 1s and NOT ik in place of all the 0s.

your truth

  1. Let's AND all columns for each row and put the output in the out cell.

my truth

  1. Finally, ORing together all the rows will give us our final expression.

(NOT i1 AND NOT i2 AND NOT i3) OR (i1 AND NOT i2 AND NOT i3) OR (i1 AND NOT i2 AND NOT i3) OR (i1 AND i2 AND i3)

Lemma 2

AND, OR and NOT can be expressed in terms of NANDs

Proof

It's easy to see that

NOT a = a NAND a

NOT from NAND

By definition:

a AND b = NOT (a NAND b)

And therefore

a AND b = (a NAND b) NAND (a NAND b)

AND from NAND

Finally it's easy to verify that

a OR b = (NOT a) NAND (NOT b)

And therefore

a OR b = (a NAND a) NAND (b NAND b)

OR from NAND

Proof (of the theorem)

Every truth table can be expressed in terms on NAND gates by construction:

  1. We can build an expression with only AND, OR, NOT using lemma 1
  2. We can substitute the three expressions for AND, OR and NOT in terms of NAND to get a ginormous, but valid, expression.

References

(discuss on HN)


Hi, I'm Marco Cecconi. I am the founder of Intelligent Hack, developer, hacker, blogger, conference lecturer. Bio: ex Stack Overflow core team, ex Toptal EM.

Read more

Newest Posts

Fan mail

Multiple people with my name use my email address and I can read their email, chaos ensues!

Read more
Intelligent Trip

After years of building, our top-notch consultancy to help start-ups and scale-ups create great, scalable products, I think it is high time I added an update to how it is going and what's next for us.

Read more
Guest blog: Building, in partnership with communities by Shog9

A lesson in building communities by Stack Overflow's most prominent community manager emeritus, Shog9

Read more
Can you migrate a company from on-premise to remote-only?

Some lessons learned over the past 8 years of remote work in some of the best remote companies on the planet

Read more
Announcing Intelligent Cache, our caching library

Our newest open source initiative, intelligent cache, is available for use

Read more

Gleanings

You Are Not Google
Ozan Onay • Jun 07, 2017

Software engineers go crazy for the most ridiculous things. We like to think that we’re hyper-rational, but when we have to choose a technology, we end up in a kind of frenzy 

Read more…