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:
class Gate:
def __init__(self, name, arrays):
self.name = name
self.array = arrays[0]
self.arrays = arrays
def __str__(self):
return self.name
def __repr__(self):
return self.name
def __getitem__(self, index):
return self.array[index]
def apply(self, x, y):
return applyGate(self.array, x, y)
def applyGate(array, x, y):
return array[2 * x + y]
def combine(gate1, gate2, gate3):
array = (applyGate(gate1, gate2[0], gate3[0]),
applyGate(gate1, gate2[1], gate3[1]),
applyGate(gate1, gate2[2], gate3[2]),
applyGate(gate1, gate2[3], gate3[3]))
return gateTable[array]
g_id = Gate("id", [(0, 0, 1, 1), (0, 1, 0, 1)])
g_false = Gate("false", [(0, 0, 0, 0)])
g_true = Gate("true", [(1, 1, 1, 1)])
g_not = Gate("not", [(1, 1, 0, 0), (1, 0, 1, 0)])
g_imp = Gate("imp", [(1, 1, 0, 1), (1, 0, 1, 1)])
g_nimp = Gate("nimp", [(0, 0, 1, 0), (0, 1, 0, 0)])
g_and = Gate("and", [(0, 0, 0, 1)])
g_or = Gate("or", [(0, 1, 1, 1)])
g_xor = Gate("xor", [(0, 1, 1, 0)])
g_eq = Gate("eq", [(1, 0, 0, 1)])
g_nand = Gate("nand", [(1, 0, 0, 0)])
g_nor = Gate("nor", [(1, 1, 1, 0)])
allGates = [g_id, g_false, g_true, g_and, g_or, g_xor, g_eq,
g_not, g_imp, g_nimp, g_nand, g_nor]
gateTable = dict()
for gate in allGates:
for array in gate.arrays:
gateTable[array] = gate
def printGates(gates, freeGates):
for gate in allGates:
if gate in gates and gate not in freeGates:
print gate,
print ''
def closed(gateSet):
"""A set of gates is closed if no other gates can be formed from
it by combination."""
for g1 in gateSet:
for g2 in gateSet:
for g3 in gateSet:
for a1 in g1.arrays:
for a2 in g2.arrays:
for a3 in g3.arrays:
if combine(a1, a2, a3) not in gateSet:
return False
return True
def universal(gateSet, closedSets):
"""A set of gates is universal if all other gates can be formed
from it by composition. This is true iff its smallest closed
superset is the complete set."""
for set in closedSets:
if set.issuperset(gateSet):
return False
return True
def minimal(S, universe):
for set in universe:
if set < S:
return False
return True
def powerset(S):
subsets = []
for n in range(2 ** len(S)):
subset = set()
for i in range(len(S)):
if n / (2 ** i) % 2 != 0:
subset.add(S[i])
subsets.append(subset)
return subsets
def findAllGateSets(freeGates):
gateSets = []
for gates in powerset(list(set(allGates) - set(freeGates))):
gates.update(freeGates)
gateSets.append(gates)
return gateSets
def main(freeGates):
allGateSets = []
closedGateSets = []
universalGateSets = []
minimalUniversalGateSets = []
allGateSets = findAllGateSets(freeGates)
print "\nClosed Sets:"
for gates in allGateSets:
if (closed(gates) and len(gates) != len(allGates)
and len(gates) > len(freeGates)):
printGates(gates, freeGates)
closedGateSets.append(gates)
for gates in allGateSets:
if universal(gates, closedGateSets):
universalGateSets.append(gates)
print "\nMinimal Universal Sets:"
for gates in universalGateSets:
if minimal(gates, universalGateSets):
printGates(gates, freeGates)
minimalUniversalGateSets.append(gates)
print '*** NO GATES ***'
main([g_id])
print '\n\n*** FALSE GATE ***'
main([g_id, g_false])
print '\n\n*** TRUE and FALSE GATES ***'
main([g_id, g_true, g_false])