# Universal Logic Gates

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
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, gate3),
applyGate(gate1, gate2, gate3),
applyGate(gate1, gate2, gate3),
applyGate(gate1, gate2, gate3))
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:
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])
``````