Justin Pombrio

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[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])