(Python) QuineMcCluskey Algorithm
(Python) QuineMcCluskey Algorithm
What is it?
The QuineMcCluskey Algorithm is an algorithm developed by Willard Quine in the late 1950s which was then improved upon by Edward McCluskey. The purpose of this algorithm is to take the results of a logical expression or a boolean algebraic expression and simplify it to it's simplest form.
Examples
(p ^ q ^ r) v (p ^ q ^ ~r) v (p ^ ~q ^ ~r)
simplifies top ^ (q v ~r)
a or (a and b)
simplifies toa
Requirements
 Basic Knowledge of Python
 Power Sets
 Recursion
QuineMcCluskey Algorithm
Now first, in order to best explain the QuineMcCluskey Algorithm, we are going to set up an example of a modified truth table that will show you the values that will be used for this example.
Grouping
Let's say we have a logical expression that evaluates per the function f(a, b, c, d) = Σ m(0, 4, 5, 7, 8, 11, 12, 15)
Now what this means is that whenever the binary equivalents of the variables make the decimal value equal to any of these values, the expression is evaluating to true:
a  b  c  d  bits  decimal 

0  0  0  0  0000  0 
0  1  0  0  0100  4 
0  1  0  1  0101  5 
0  1  1  1  0111  7 
1  0  0  0  1000  8 
1  0  1  1  1011  11 
1  1  0  0  1100  12 
1  1  1  1  1111  15 
Now we group the bits by however many 1's there are in the binary value. Don't worry about the used
column just yet. I will explain that a few steps down:
# of 1's  decimal  a  b  c  d  used 

0  0  0  0  0  0  yes 
1  4  0  1  0  0  yes 
8  1  0  0  0  yes  
2  5  0  1  0  1  yes 
12  1  1  0  0  yes  
3  7  0  1  1  1  yes 
11  1  0  1  1  yes  
4  15  1  1  1  1  yes 
Now, each of these values becomes a minterm. What a minterm is is just something that holds information about where a decimal value, or values, evaluates to true and what binary value it holds. When we combine them, we only want to look for where there is a 1bit difference in 2 minterms. The reason we do that is because we want to remove the bits that don't matter. For example, let's say we compare minterms 0 and 4. We see that there is only a 1bit difference between them at the b
variable. To put this into logical expression terms, this is really what we're doing:
Expression  Action 

(~a ^ ~b ^ ~c ^ ~d) v (~a ^ b ^ ~c ^ ~d)  Given 
(~a ^ ~c ^ ~d) ^ (~b v b)  Distributive Law 
(~a ^ ~c ^ ~d) ^ t  Identity Law 
(~a ^ ~c ^ ~d)  Tautology 
Now, as you can see above, we were able to take out a common factor of (~a ^ ~c ^ ~d)
and leave behind (~b v b)
. In logic, (~b v b)
will always be true no matter the value of b
. This is the reason we want to compare minterms that have only a 1bit difference.
Comparing
After we compare each term in adjacent groups with one another, we get another table that looks like the following table. There is an extra column to keep track of whether or not we used the minterm specified when we try combining the minterms. Since we used all of the minterms in the earlier table, we know that we don't have to remember to use any of them. If we don't use a minterm, then that minterm must be one of the prime implicants, which is what is used to generate the simplified logical expression:
groups  minterm  a  b  c  d  used 

01  m(0, 4)  0    0  0  yes 
m(0, 8)    0  0  0  yes  
12  m(4, 5)  0  1  0    no 
m(4, 12)    1  0  0  yes  
m(8, 12)  1    0  0  yes  
23  m(5, 7)  0  1    1  no 
34  m(7, 15)    1  1  1  no 
m(11, 15)  1    1  1  no 
Now that we've compared every term in adjacent groups with one another, we can move onto doing the same step again which will get us with 2 values.
Comparing (continued)
groups  minterm  a  b  c  d  used 

0112  m(0, 4, 8, 12)      0  0  no 
m(0, 8, 4, 12)      0  0  no 
Now as you can see, these 2 minterms are actually the same exact minterm. Just because the order of the numbers is different doesn't make them any different in reality. Therefore, the order of the values in the minterms doesn't actually matter when combining them. However, we must make sure that minterms m(0, 4)
, m(0, 8)
, m(4, 12)
, and m(8, 12)
are used which helps us simplify the expression.
Prime Implicant Table
From the minterms that aren't used, we create a table with the variables on the left and the values from the function at the beginning on the right. When we go through the unused minterms, we put X
's in the columns that the minterm holds values for. For example m(0, 4, 8, 12)
should have X
's in columns 0, 4, 8, and 12. That part is pretty selfexplanatory.
a  b  c  d  0  4  5  7  8  11  12  15 

~c  ~d  X  X  X  X  
~a  b  ~c  X  X  
~a  b  d  X  X  
b  c  d  X  X  
a  c  d  X  X 
Once we have this table setup, we want to look for what is known as the essential prime implicants which are prime implicants that need to exist in order for the expression to evaluate to true at the values specified earlier. To find these essential prime implicants, we look for the numbers who have only 1 X
in the entire column. In our case, those columns are 0, 8, 11, and 12. Once we find those essential prime implicants, we go to the row that contains that X
and add it to our final expression. When we cover an expression from a row, we then ignore all the X
's that exist in the rest of the column.
For example, since we see that 0, 8, and 12 are essential values, we add (~c ^ ~d)
to the final expression and cross out all the columns that minterm covers. The reason we have (~c ^ ~d)
as the expression for this minterm is because the binary equivalent is 00
. Wherever there is a hyphen (
), we do not put the variable that corresponds to it. Whenever there is a 0
, we put a NOT (~
) operator in front of the variable that corresponds to it. Whenever there is a 1
, we just put the variable itself.
Expression: (~c ^ ~d)
a  b  c  d  0  4  5  7  8  11  12  15 

~c  ~d  
~a  b  ~c  X  
~a  b  d  X  X  
b  c  d  X  X  
a  c  d  X  X 
Now we have another essential value at column 11 so we need to add (a ^ c ^ d)
to the final expression.
Expression: (~c ^ ~d) v (a ^ c ^ d)
a  b  c  d  0  4  5  7  8  11  12  15 

~~~c~~  ~~~d~~  
~a  b  ~c  X  
~a  b  d  X  X  
b  c  d  X  
Since we do not have any more essential prime implicants, we want to find which implicant(s) will create the simplest expression and covers the most values. In this case, we can see that m(5, 7)
will cover the other 2 remaining columns:
Expression: (~c ^ ~d) v (a ^ c ^ d) v (~a ^ b ^ d)
a  b  c  d  0  4  5  7  8  11  12  15 

~~~c~~  ~~~d~~  
~a  b  ~c  
~~~a~~  
b  c  d  
Final Expression
Now, since we have covered every value in the prime implicant chart, the final expression is (~c ^ ~d) v (a ^ c ^ d) v (~a ^ b ^ d)
. To put that into perspective, the original expression was (~a ^ ~b ^ ~c ^ ~d) v (~a ^ b ^ ~c ^ ~d) v (~a ^ b ^ ~c ^ d) v (~a ^ b ^ c ^ d) v (a ^ ~b ^ ~c ^ ~d) v (a ^ ~b ^ c ^ d) v (a ^ b ^ ~c ^ ~d) v (a ^ b ^ c ^ d)
.
Now let's move onto the code that actually does all of this.
QuineMcCluskey Algorithm in Code
For this algorithm, I've created only 2 classes that do all of the hard work:
 The
Minterm
class, which holds the values and the binary value of the minterm  The
QuineMcCluskey
class which actually solves for the simplified form of an expression
Minterm
class
The Minterm
class is actually quite simple and doesn't hold much at all.
First we have the basic builtin methods:
class Minterm: def __init__(self, values, value): self._values = values self._value = value self._used = False self._values.sort() def __str__(self): values = ", ".join([str(value) for value in self._values]) return f"m({values}) = {self._value}" def __eq__(self, minterm): if type(minterm) != Minterm: return False return ( self._value == minterm._value and self._values == minterm._values )
The __str__
method is there to print out a specific minterm nicely in the form of m(0, 4, 8, 12) = 00
Next, we have some basic getters and setters that are used in the QuineMcCluskey
portion of the code:
def get_values(self): """Returns all the implicants that this minterm covers. """ return self._values def get_value(self): """Returns the bit values ('010', '1010', etc.) for this minterm. """ return self._value def use(self): """Keeps track of when this minterm is "used" in a comparison. """ self._used = True def used(self): """Returns whether or not this minterm was used. """ return self._used
These are all both documented and pretty selfexplanatory so I don't think I need to really go over them much.
This next (and last) portion of code for the Minterm
class is used when we combine minterms in the algorithm:
def combine(self, minterm): """Combines this minterm with the specified minterm if possible. """ # Check if this minterm is the same as the one trying to be combined with if self._value == minterm._value or self._values == minterm._values: return None # Keep track of the amount of difference between the value of the minterm # and also keep track of the resulting string diff = 0 result = "" # Iterate through all the bit values for char in range(len(self._value)): # Check if this minterm and the combined minterm have a bit difference if self._value[char] != minterm._value[char]: diff += 1 result += "" # There is no difference else: result += self._value[char] # The difference is greater than 1, these minterms cannot be combined if diff > 1: return None return Minterm(self._values + minterm._values, result)
Now as you can see, this code will return a new Minterm
object if 2 minterms can be combined with one another. For example, what this does is take a minterm, say m(0, 4) = 000
, and another minterm, say m(8, 12) = 100
, and it will combine them together which then becomes m(0, 4, 8, 12) = 00
.
That is really all that needs to be done for the Minterm
class. Now let's move on to the QuineMcCluskey
class which has all the meat of the code.
QuineMcCluskey
class
The QuineMcCluskey
class has the majority of the functions that create an initial group, combine minterms from adjacent groups, solves the function, and then generates the function into a humanreadable format.
First, we need the basic constructor and a function that gets the binary equivalent of a decimal value:
class QM: """A class to handle processing the QuineMcCluskey Algorithm. """ def __init__(self, variables, values): self._variables = variables self._values = values def __get_bits(self, value): """Returns the binary digit for the specified value. """ # Pad the result with extra 0's at the beginning to match how many variables # there are being used return bin(value)[2:].rjust(len(self._variables), "0")
The reason we need the __get_bits
function is to be able to get the binary equivalent of the values where the function evaluates to true. For example, 4 is 0100
, 5 is 0101
, and 7 is 0111
in our example. It's important to pad extra 0's to the beginning of the value to match that of the number of variables in the expression.
The Initial Group
Before beginning the process of getting a list of unused prime implicants, we need to create an initial group where each binary value is matched up with how many 1's the binary value has.
def __initial_group(self): """Creates the initial grouping for the bits from the values given to the QuineMcCluskey Algorithm """ # Keep track of groups by 2dimensional list groups = [] for count in range(len(self._variables) + 1): groups.append([]) # Iterate through values for value in self._values: # Count number of 1's in value's bit equivalent count = self.__get_bits(value).count("1") # Add count to proper group groups[count].append(Minterm([value], self.__get_bits(value))) return groups
In essence, what this function does is create the groups of minterms based off of how many 1's there are in the binary values for the decimal values. In the case of our function from earlier, the list would look something like this:
groups = [ ['m(0) = 0000'], # 0 1's ['m(4) = 0100', 'm(8) = 1000'], # 1 1's ['m(5) = 0101', 'm(12) = 1100'], # 2 1's ['m(7) = 0111', 'm(11) = 1011'], # 3 1's ['m(15) = 1111'] # 4 1's ]
Prime Implicants
The next step is to get all the prime implicants that could possibly cover the expression. Like mentioned earlier in the explanation of the QuineMcCluskey Algorithm, to get the prime implicants, we must compare every term in one group with every term in an adjacent group. That is what the following code does:
def __get_prime_implicants(self, groups = None): """Recursively gets the prime implicants for the expression. """ # Get initial group if group is None if groups == None: groups = self.__initial_group() # If there is only 1 group, return all the minterms in it if len(groups) == 1: return groups[0] # Try comparing the rest else: unused = [] comparisons = range(len(groups)  1) new_groups = [[] for c in comparisons] for compare in comparisons: group1 = groups[compare] group2 = groups[compare + 1] # Compare every term in group1 with every term in group2 for term1 in group1: for term2 in group2: # Try combining it term3 = term1.combine(term2) # Only add it to the new group if term3 is not None # term3 will only be None if term1 and term2 could not # be combined if term3 != None: term1.use() term2.use() if term3 not in new_groups[compare]: new_groups[compare].append(term3) # Get list of all unused minterms for group in groups: for term in group: if not term.used() and term not in unused: unused.append(term) # Add recursive call for term in self.__get_prime_implicants(new_groups): if not term.used() and term not in unused: unused.append(term) return unused
The first if
statement is pretty simple to comprehend. All it's checking for is whether or not a parameter is given, which is used in the recursive call, and setting it to be the initial group if it is not given.
The next if
statement is the base case of this recursive function. If there is only one group left, then only the prime implicants in that function will cover the expression given.
The else
statement handles everything else about getting prime implicants. First, we set up which minterms are unused in the comparisons. Then we want to only compare groups that are adjacent to one another. So if there are 5 groups, we only want to compare group 0 and 1, 1 and 2, 2 and 3, and 3 and 4. That's only 4 comparisons. Finally, we want to keep track of these new groups once we compare minterms.
When we loop through the comparisons, we only go from the first group to the second to last group or else we would have an IndexError
when the group2 = groups[compare + 1]
line of code came up. Once we loop through each minterm in each group, we try to combine the 2 minterms. If the 2 minterms cannot be combined, nothing will happen. However, if the 2 minterms can be combined, we want to keep track of using the minterm. Then, we make sure that the resulting minterm does not already exist in the new group that it belongs to.
Once we finish with comparing minterms, we want to keep track of which minterms were not used, if there were any. Then we make the recursive call which uses the new list of groups to compare every minterm again. Each time the __get_prime_implicants
function is run, it returns a list of unused minterms. At the end of the recursive call, we get a total list of all the minterms which become the prime implicants.
Power Set
A power set, for those who don't understand what it is, is just a set of combinations of an existing set. For example, let's take a set to be {1, 2, 3}
. The power set would be, {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
.
The reason we need to understand what a power set is is because after the essential prime implicants are found (which will be explained right after this section), the power set function will determine which remaining implicants cover the remainder of the expression and which set has the fewest implicants.
def __power_set(self, values, prime_implicants): """Creates a power set of all valid prime implicants that covers the rest of an expression. This is used after the essential prime implicants have been found. """ # Get the power set of all the prime_implicants prime_implicants = list(prime_implicants) power_set = [] # Iterate through decimal values from 1 to 2 ** size  1 for i in range(1, 2 ** len(prime_implicants)): current_set = [] # Get the binary value of the decimal value bin_value = bin(i)[2:].rjust(len(prime_implicants), "0") # Find which indexes have 1 in the bin_value string for index in range(len(bin_value)): if bin_value[index] == "1": current_set.append(prime_implicants[index]) power_set.append(current_set) # Remove all subsets that do not cover the rest of the implicants new_power_set = [] for subset in power_set: # Get all the values the set covers temp_values = [] for implicant in subset: for value in implicant.get_values(): if value not in temp_values and value in values: temp_values.append(value) temp_values.sort() # Check if this subset covers the rest of the values if temp_values == values: if len(subset) < len(minSet): minSet = subset return minSet
There are a few things that go on in this function. First, the initial power set is created from the prime implicants given through the parameter. After that is done, we then iterate over each set to determine if the set contains minterms that cover the rest of the expression. When the smallest subset is found, a variable, minSet
, is updated to keep track of the smallest set so that at the end, the smallest set is returned which includes the final prime implicant, or implicants, that cover the rest of the expression.
Solving
Now let's get on to actually solving the expression.
def __solve(self): """Solves for the expression returning the minimal amount of prime implicants needed to cover the expression. """ # Get the prime implicants prime_implicants = self.__get_prime_implicants(self.__initial_group()) # Keep track of values with only 1 implicant # These are the essential prime implicants essential_prime_implicants = [] values_used = [False] * len(self._values) for i in range(len(self._values)): value = self._values[i] uses = 0 last = None for minterm in prime_implicants: if value in minterm.get_values(): uses += 1 last = minterm if uses == 1 and last not in essential_prime_implicants: for v in last.get_values(): values_used[self._values.index(v)] = True essential_prime_implicants.append(last) # Check if all values were used if values_used.count(False) == 0: return essential_prime_implicants # Keep track of prime implicants that cover as many values as possible # with as few variables as possible prime_implicants = [prime_implicant for prime_implicant in prime_implicants if prime_implicant not in essential_prime_implicants] # Check if there is only one implicant left (very rare but just in case) if len(prime_implicants) == 1: return essential_prime_implicants + prime_implicants # Create a power set from the remaining prime implicants and check which # combination of prime implicants gets the simplest form return essential_prime_implicants + self.__power_set([ self._values[index] for index in range(len(self._values)) if not values_used[index] ], prime_implicants)
The basic function of the solve
function is to:

Get a list of prime implicants
# Get the prime implicants prime_implicants = self.__get_prime_implicants(self.__initial_group())

Find the essential prime implicants
# Keep track of values with only 1 implicant # These are the essential prime implicants essential_prime_implicants = [] values_used = [False] * len(self._values) for i in range(len(self._values)): value = self._values[i] uses = 0 last = None for minterm in prime_implicants: if value in minterm.get_values(): uses += 1 last = minterm if uses == 1 and last not in essential_prime_implicants: for v in last.get_values(): values_used[self._values.index(v)] = True essential_prime_implicants.append(last) # Check if all values were used if values_used.count(False) == 0: return essential_prime_implicants
The final
if
statement in this block of code will determine if all the essential prime implicants are the only prime implicants needed to cover the expression. 
Use the
__power_set
function to find the final prime implicant(s) that cover the expression and return it along with the essential prime implicants# Keep track of prime implicants that cover as many values as possible prime_implicants = [prime_implicant for prime_implicant in prime_implicants if prime_implicant not in essential_prime_implicants] # Check if there is only one implicant left (very rare, if not impossible, but just in case) if len(prime_implicants) == 1: return essential_prime_implicants + prime_implicants # Create a power set from the remaining prime implicants and check which # combination of prime implicants gets the simplest form return essential_prime_implicants + self.__power_set([ self._values[index] for index in range(len(self._values)) if not values_used[index] ], prime_implicants)
The purpose of reassigning the
prime_implicants
list is to remove all the prime implicants that are in that list that are also an essential prime implicant.
Getting the Expression
The final part of this algorithm is to actually return an expression that is readable to the human eye.
# Get the prime implicants and variables prime_implicants = self.__solve() # Check if there are no prime_implicants; Always False if len(prime_implicants) == 0: return "0" if len(prime_implicants) == 1: if prime_implicants[0].get_value().count("") == len(self._variables): return "1" result = "" # Iterate through prime implicants for j in range(len(prime_implicants)): implicant = prime_implicants[j] # Iterate through all bits in the implicants value for i in range(len(implicant.get_value())): if implicant.get_value()[i] == "0": result += "NOT " if implicant.get_value()[i] != "": result += self._variables[i] if implicant.get_value().count("", i + 1) < len(implicant.get_value())  i  1 and implicant.get_value()[i] != "": result += " AND " if j < len(prime_implicants)  1: result += " OR " return result
The basis of the get_function
function is to find the prime implicants from the __solve
function, iterate through the prime implicants and their binary values, and then create proper variables (with/without a NOT operator).
If there are no prime implicants received after the __solve
function is called, then the expression is always false. Therefore, a 0
is returned. If there is only 1 prime implicant that has a binary value of all hyphens (
), then the expression will always be true no matter what.
Conclusion
To conclude this tutorial, I went over the basics of the QuineMcCluskey Algorithm, how to do it by hand, and how to adapt it to code. If you want to see the simplifier in action, you can go to https://repl.it/@FellowHashbrown/QuineMcCluskeyPython. I also wrote it in Java and Node.js
If you have any suggestions or see any issues, please let me know that way I can fix it!
If you find any bugs in adaptation of the QuineMcCluskey Algorithm, definitely let me know either by leaving a comment, pinging me in Repl.it's Discord Server, or pinging me in my own Discord Server
Very cool! Time to bookmark this for later reading lol (it's way long)
@a5rocks yeah sorry it's so long. but i had to explain the algorithm and then the code for it. can't do one without the other