9.5 Universality for bit gates
Do we need all these gates? Is there some subset of the 1- and 2-bit gates that can generate all the others? Let’s begin with a nand gate and see what we can build from there.
The first new construction is that not x =
x nand x. If we feed x
to both inputs of nand, we get the same result as not!
The black dot “●” reuses the bit’s value so we can use it as two inputs.
This circuit shows that if we have nand, we don’t need not as well. Though we may use not in circuits, it is superfluous.
The original set of 1- and 2-bit gates was
not and or xor nand nor xnor .
Since x and y =
not (x nand
y), the gates we still need are
or xor nand nor xnor .
We can construct or from three nand gates.
Since x nor y =
not (x nor
y), our list of required gates...