Universal Logic Gates

Output

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 composeGates(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 composition."""
	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 composeGates(a1, a2, a3) not in gateSet:
								return False
	return True

def closedCounterexample(gateSet):
	for g1 in gateSet:
		for g2 in gateSet:
			for g3 in gateSet:
				if g1.compose(g2, g3) not in gateSet:
					return g1.compose(g2, g3)

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 universalCounterexample(gateSet, closedSets):
	for set in closedSets:
		if set.issuperset(gateSet):
			return set

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 "\n\nClosed:"
	for gates in allGateSets:
		if closed(gates) and len(gates) != len(allGates):
			printGates(gates, freeGates)
			closedGateSets.append(gates)
	for gates in allGateSets:
		if universal(gates, closedGateSets):
			universalGateSets.append(gates)
	print ''
	print len(closedGateSets)
	print "\nMinimal Universal:"
	for gates in universalGateSets:
		if minimal(gates, universalGateSets):
			printGates(gates, freeGates)
			minimalUniversalGateSets.append(gates)
	print ''
	print len(minimalUniversalGateSets)

print '\n\nNO GATES'
main([])
print '\n\nIDENTITY GATE'
main([g_id])
print '\n\nIDENTITY & FALSE GATES'
main([g_id, g_false])
print '\n\nIDENTITY, TRUE, & FALSE GATES'
main([g_id, g_true, g_false])