(Python) Quine-McCluskey Algorithm

What is it?

The Quine-McCluskey 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 to p ^ (q v ~r)
• a or (a and b) simplifies to a

Requirements

• Basic Knowledge of Python
• Power Sets
• Recursion

Quine-McCluskey Algorithm

Now first, in order to best explain the Quine-McCluskey 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:

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:

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 1-bit 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 1-bit difference between them at the b variable. To put this into logical expression terms, this is really what we're doing:

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 1-bit 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:

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)

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 self-explanatory.

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)

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)

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)

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.

Quine-McCluskey 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 built-in 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 self-explanatory 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) = 0-00, and another minterm, say m(8, 12) = 1-00, 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 human-readable 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 Quine-McCluskey 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 Quine-McCluskey Algorithm
        """

        # Keep track of groups by 2-dimensional 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 Quine-McCluskey 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:

1. Get a list of prime implicants

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

2. 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.

3. 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 Quine-McCluskey 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/Quine-McCluskey-Python. 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 Quine-McCluskey 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