July 26, 2015 by Marco Cecconi

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.

Any truth table can be built by combining NANDs.

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

Any truth table is defined by N bits in input (*i _{1}*,

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

- if
*out*is_{l}`1`

, then the expression is equal to`1`

if and only if all the input match the given inputs - if
*out*is_{l}`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 *out _{l}* =

`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

`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`

.

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

- Let's ignore all lines with value
`0`

.

- Let's write in
*i*in place of all the_{k}`1`

s and*NOT i*in place of all the_{k}`0`

s.

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

- 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)`

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

It's easy to see that

`NOT a = a NAND a`

By definition:

`a AND b = NOT (a NAND b)`

And therefore

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

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)`

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

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

- NAND logic, Wikipedia
- NAND & NOR Gate as Universal Gate, electrical4u.com

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 moreFebruary 03, 2021 by Marco Cecconi

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

Read moreDecember 02, 2020 by Marco Cecconi

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

Read moreNovember 25, 2020 by Marco Cecconi

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

Read moreNovember 19, 2020 by Marco Cecconi

In this post, Salvatore Sanfilippo puts together a list of qualities that I believe make the most difference in programmers’ productivity.

Read moreChris Dixon • Mar 20, 2017

What began, in Boole’s words, with an investigation “concerning the nature and constitution of the human mind,” could result in the creation of new minds—artificial minds—that might someday match or even exceed our own.

Read more…