I trust that you have heard that nand gates are universal, meaning loosely that with enough nand gates you can construct any other binary gate. But can we define this more precisely? And other other gates universal?
A binary gate takes two inputs, each of which is either 0 or 1, and produces an output of 0 or 1. There are 4 possible input combinations, so there are 2^4 = 16 possible gates. You can combine three gates x, y, and z by applying z to the outputs of x and y.
A set of gates is closed if no combination of those gates can produce a gate not in the set. Clearly the empty set of gates is closed, because you can’t form any combinations at all. And the complete set of 16 gates is closed because any gate you form from them is clearly in the set. So is the set containing just the ‘true’ gate that always returns 1 regardless of its inputs. In general, it’s easy to check whether a set of gates is closed: just consider every combination of three of them and check that it’s still in the set.
Now we are ready to talk about universal sets. As we said before, a set of gates is universal if every other gate can be built from some combination of its elements. But how can we compute this? One possibility would be to consider every combination of three gates in the set in turn, check if that adds a new gate and if so add it to the set and start again, and stop once we’ve made a complete pass without discovering any new gate. This is called a fixpoint algorithm. But in this case it would be very slow. How can we make it faster?
There’s a neat insight here, which is that
A set of gates is universal if and only if its smallest closed superset is the complete set.
Convince yourself of this fun fact :-). We can use it to greatly speed
up testing if a set of gates S
is universal by precomputing all
closed sets of gates (of which there are only a couple dozen), and
then simply checking which closed sets S
is a subset of.
Finally, here is a listing of all of the closed and universal sets of gates (using the above trick) given a set of “assumed” starting gates. If you assume no starting gates (other than the “identity” gates representing the two inputs), there are only two singleton universal sets: nand and nor. But there are more if you allow a “false” gate which always outputs 0, or a “true” gate which always outputs 1!
*** NO GATES *** Closed Sets: false true false true not false true not and false and true and false true and false and nimp true eq or false or true or false true or true or imp and or false and or true and or false true and or true and or eq imp false xor false true xor eq not false and or xor nimp Minimal Universal Sets: nand false imp not imp nor true nimp not nimp imp nimp and not eq nimp false and eq or not false or eq xor imp true and xor and xor eq true or xor or xor eq *** FALSE GATE *** Closed Sets: true true not and true and and nimp or true or and or true and or xor true xor eq not and or xor nimp Minimal Universal Sets: nand imp nor true nimp not nimp and not eq nimp and eq or not or eq true and xor true or xor *** TRUE and FALSE GATES *** Closed Sets: not and or and or xor eq not Minimal Universal Sets: nand imp nor nimp and eq and not or eq or not and xor or xor
And here is the python script which generates it: