# Building arbitrary Boolean functions with NAND gates

March 15, 2017Digital circuits are the fundamental building block of computer architecture. They allow us to move onto a higher level of abstraction where we do not have to deal with the physics of hardware anymore. Computations on this level are described by Boolean functions which simply define an input-output relationship of bits. A boolean function \( f \) can be described like this:

$$ f: \{0,1\}^k \rightarrow \{0,1\}, \text{ for some } k > 0 $$

From a mathematical perspective, this is nothing fancy: Map a bunch of zeros and ones onto a zero or a one. But from a hardware perspective, this contains a lot of abstraction already. After all, a function and even the numbers zero and one are completely abstract concepts. How can they possibly be represented in hardware? Of course, I do not have a final answer, but I understand the following:

- Zero and one can be represented by low and high voltage.
- A function can be represented by input wires conducting electricity leading into a single output wire.
- Function composition can be modeled by simply connecting output of one function an input of another.

Connecting and manipulating the physics of wires and electricity results in so called logical gates. These blocks are physical entities with input and output wires that behave according to some Boolean function. There could for example be a \( NOT \) or an \( AND \) gate, behaving the way their truth tables specify. These building blocks can then be connected to build more complex Boolean functions. And this is where theory comes in handy: It would make sense to build a few small functions in actual hardware (with logical gates) and combine them to build more complex abstract functions without the need for new hardware. Therefore the question becomes: What functions do we need to build arbitrary complex Boolean functions?

There are many answers to this, but one of the smallest so called **functionally complete** sets is \( \{ NAND \} \). The set \( \{ NOT, AND, OR \} \) is functionally complete. Given an arbitrary Boolean function (that is, its truth table), one can build a corresponding logical formula using just these three functions. This fact requires a proof of its own, but there are multiple intuitive methods to achieve this. For now, it just means that it is enough to show how this set of three functions can be constructed from just \( NAND \). But this is not complicated either and can be achieved by playing around with the function just a bit:

$$ NOT(x) = NAND(x,x) $$

$$ AND(x,y) = NAND( NAND(x,y), NAND(x,y) ) $$

$$ OR(x,y) = NAND( NAND(x,x), NAND(y,y) ) $$

What does this show? It means nothing less than building a physical gate that behaves like a \( NAND \) is all you need to do. If you can make the physics happen for \( NAND \) , you can make the physics happen for any Boolean function essentially. Every single one. I find it fascinating that one binary Boolean function contains the power of arbitrary complex functions with an arbitrary amount of arguments. And the “proof” is nothing but a few elementary computations. I am always impressed with such simple yet powerful theoretical results. Well, theoretical result is probably an overstatement here since it is really just a construction, but a nice example still.