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 (i1, i2, …, ik, …, iN). A truth table will also have 2N outputs (out1, out2, …, outl, …, out2N).
We want to create an expression with only OR, NOT and AND that "represents" each row of inputs, in other words:
1, then the expression is equal to
1if and only if all the input match the given inputs
0, then the expression is equal to
0independently 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
How do we create these subexpressions? If the expected input value is
NOT i, if the expected input value is
An example will make everything clear. Let's create an expression to represent the following truth table:
1s and NOT ik in place of all the
(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
a AND b = NOT (a NAND b)
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)
a OR b = (a NAND a) NAND (b NAND b)
Every truth table can be expressed in terms on NAND gates by construction:
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
December 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 planetRead more
November 25, 2020 by Marco Cecconi
Our newest open source initiative, intelligent cache, is available for useRead more
November 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 more
October 27, 2020 by Marco Cecconi
Today I want to introduce our second engineering team: Team EMEARead more
October 23, 2020 by Marco Cecconi
LEGO star-ships aren't made to collect dust on a shelf, but to explore strange new worldsRead more
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 frenzyRead more…