We can't use AND to build OR or vice-versa. However, we can use NAND to build any logic gate: AND, OR, NOT, etc. This is surprising at first, but there's no esoteric reason underneath; it falls out of the truth tables.

NAND is "NOT-AND", so it's true unless x and y are both true. In programming terms, x NAND y, means !(x AND y). Here's a truth table for both AND and NAND.

And, for completeness, the corresponding Python function:

>>> def NAND(x, y):
...     if x == 0 and y == 0: return 1
...     if x == 0 and y == 1: return 1
...     if x == 1 and y == 0: return 1
...     if x == 1 and y == 1: return 0

This function will serve as the basis for everything in this article; we'll eventually build up our four-bit adder using this primitive gate and no others.

First we build NOT, which can be defined as NAND(x, x). The truth table above shows that NAND(1, 1) == 0 and NAND(0, 0) == 1, which is exactly the behavior of NOT! Here it is in Python:

>>> def NOT(x):
...     return NAND(x, x)
>>> NOT(1)
0
>>> NOT(0)
1

NAND and AND are opposites, so we can NOT either one to get the other, allowing us to build AND using our two existing gates:

>>> def AND(x, y):
...     return NOT(NAND(x, y))

# Check
>>> [AND(0, 0), AND(0, 1), AND(1, 0), AND(1, 1)]
[0, 0, 0, 1]

With NOT and AND, we can use De Morgan's laws to build OR. To implement x OR y, we can do !(!x AND !y), which is equivalent by De Morgan. (This was row one in our table in the previous section.)

>>> def OR(x, y):
...     return NOT(AND(NOT(x),
...                    NOT(y)))

# Check
>>> [OR(0, 0), OR(0, 1), OR(1, 0), OR(1, 1)]
[0, 1, 1, 1]

Note that only NAND and NOR are universal in this way, allowing us to build all other gates from them. To make this concrete, try to define NOT using only AND. It won't work!