LogicTest2.py

ZERO = 0
ONE = 1
EITHER = 2

nvars = 4
varnames = ['a', 'b', 'c', 'd']

func = lambda a,b,c,d: (a and b) or (c and d)

implicant_set = set()

class Implicant:
	def __init__(self, n):
		self.Group = [n] # all of the numbers sharing this implicant
		self.Values = []
		self.OneCount = 0   # 1's
		self.MaybeCount = 0 # don'tcare's
		self.AllBuckets = []
		##
		for i in range(nvars):
			self.Values.append(ONE if (n&1) else ZERO)
			if n&1:
				self.OneCount += 1
			n >>= 1
		self.Values = self.Values[::-1]


	def __str__(self):
		s = ''
		for i in range(nvars):
			# if self.Values[i] == ONE:
			# 	s += varnames[i]
			# elif self.Values[i] == ZERO:
			# 	s += varnames[i]
			# 	s += "'"
			if self.Values[i] == ONE:
				s += '1'
			elif self.Values[i] == ZERO:
				s += '0'
			else:
				s += '-'
		return s


# gather the initial data
for i in range(2**nvars):
	implicant = Implicant(i)
	fargs = []
	for i in range(nvars):
		fargs.append(implicant.Values[i] == ONE)
	if func(*fargs):
		implicant_set.add(implicant)


# sort the implicants into buckets based on the onecount
buckets = [[] for i in range(nvars)]
for imp in implicant_set:
	buckets[imp.OneCount-1].append(imp)
	imp.AllBuckets.append(buckets[imp.OneCount-1])

print(' + '.join([str(x) for x in implicant_set]))


# join implicants differing by one term. We only need to do this
# between adjacent buckets, only they can differ by one term.
while True:
	print("Loop")
	madech = False
	for bucketn in range(nvars):
		for offs in [-1,1]:
			if 0 <= (bucketn+offs) < nvars:
				# now do the join on the buckets
				bucketa = buckets[bucketn]
				bucketb = buckets[bucketn+offs]

				for impa in bucketa:
					for impb in bucketb:
						# try doing a cancel for things with equal maybes
						if impa.MaybeCount == impb.MaybeCount:
							diff = 0
							for i in range(nvars):
								if impa.Values[i] != impb.Values[i]:
									diff += 1
							if diff == 1:
								madech = True
								# we can join this pair
								for i in range(nvars):
									if impa.Values[i] != impb.Values[i]:
										# set both values to either
										impa.Values[i] = EITHER
										break
								# delete impb, replacing it with impa
								impa.Group += impb.Group
								implicant_set.remove(impb)
								impa.OneCount -= 1
								impa.MaybeCount += 1
								for bucket in impb.AllBuckets:
									bucket.remove(impb)
									bucket.append(impa)
									impa.AllBuckets.append(bucket)
						else:
							# otherwise, for unequal maybe counts try do an expand
							# first make sure that the one with less maybes is A
							if impa.MaybeCount > impb.MaybeCount:
								impb, impa = impa, impb

							# now, check that all of the parts are less or equal
							allLE = True
							isless = False
							for i in range(nvars):
								a = impa.Values[i]
								b = impb.Values[i]
								if a == b:
									isless = True
								elif a > b:
									allLE = False
									break

							# if all less, expand A
							if allLE and isless:
								madech = True
								print("(%s | %s)" % (impa, impb))
								#find the differences and expand
								for i in range(nvars):
									a = impa.Values[i]
									b = impb.Values[i]
									if a < b:
										# two cases:
										# a = 0, b = 1 => a = -
										# a = 1, b = - => a = -
										# => in both cases, a = -
										#do the increase
										if a == ONE:
											impa.OneCount -= 1
										impa.MaybeCount += 1
										impa.Values[i] = EITHER
								print("(%s)" % impa)
	if madech:
		continue
	break




# now that we have the prime implicants left in the 


print(' + '.join(["%s:%s" % (str(x), x.Group) for x in implicant_set]))

"""


cd + abcd' + abc'

-  -  1  1  >
1  1  1  0  >  1  1  1  -
1  1  0  -


  1 1 1 0 > 1 1 1 -
  - - 1 1

  1 1 0 - > 1 1 - -
  - - 1 -


ab\cd| 00 01 11 10
-----------------
 00|   0  0  0  0
 01|   0  0  1  0
 11|   0  1  1  0
 10|   0  0  0  0

1101 | -111
-> 11-1



"""