There was a Fields Medallist named Dan Quillen, after whom are named several things in topics I’ve never head of. Other than Quillen, so far as I can tell, the only mathematical eponyms beginning with Q relate to Willard Van Ormine Quine. I know him from Godel, Escher, Bach, where his paradox was explored, but I’m going to take on something a bit less headachey for me: the Quine-McCluskey Algorithm.

What is the Quine-McCluskey algorithm?

The algorithm is a method for taking a Boolean function, taking a vector of true/false inputs and returning either true or false, and reducing it to its simplest possible form.

In this article, I’m going to follow the convention that “true” corresponds to 1 and “false” to 0 - and that adding is equivalent to “or” (so $1+0 = 0+1 = 1+1 = 1$).

Suppose we have a function with three Boolean inputs, which returns:

  • 0 if the inputs are $001$, $010$, $110$ or $111$
  • 1 if the inputs are $011$, $100$ or $101$ - these inputs are called “minterms”.
  • unknown if the inputs are $000$.

One way to write the function - calling its inputs ABC - is $A’BC + AB’C’ + AB’C$. It returns 1 if either (not A, and B and C) or (A and not B, and not C) or (A and not B and C). Is this the most succinct way we can write it? Let’s ask Quine and McCluskey.

The first step of the algorithm is list all of the minterms (and the unknown value) in a table, sorted by the number of 1s:

  • Zero 1s: $000$
  • One 1: $100$
  • Two 1s: $101$ and $110$

Now we look for pairs of minterms that differ by only one digit and write down those possibilities, replacing their differing digit with a dash:

  • $000$ and $100$ could become $-00$
  • $101$ and $100$ could become $10-$
  • $100$ and $110$ could become $1-0$

This is as far as we can go - all of these possibilities differ in two places. If they didn’t, we could carry on combining.

Now we make a table with the minterms along the top and the patterns down the side; in the middle, we note whether the minterm in question matches the pattern:

 

100

101

110

-00

Y

N

N

10-

Y

Y

N

1-0

Y

N

Y

I’ve bolded two entries: they’re the ones that have only one Y in the column: these patterns are essential.

The first column is matched by both of these patterns, so the remaining row is unnecessary. (In more complicated functions, there may be more work to do to make sure all of the columns are matched - but we’re practically done!)

If our Boolean function matches AB’ or AC’ (or both), and no other possibilities, it matches our specification - so our function is $AB’ + AC’$.

Just to check: this will return true in cases $100$ and $101$ (from the first term) and $110$ and $100$ (from the second), otherwise false. The three cases we wanted to be true are true, the four false ones are false, and (it turns out) the unknown one is false.

Why is it important?

Minimising Boolean functions was a sticky problem in the 1950s, when computing power was (at its very best) scarce. Boolean functions were the domain of electronic circuits more than computer programs - if you wanted a circuit to respond in a particular way to particular inputs, using a suboptimal approach was going to cost you in space, components and maintenance.

Quine (and McCluskey, who refined the algorithm) came up with a foolproof method for minimising a function. It’s not necessarily a quick method - in general, the problem is NP-hard, and the amount of work you have to do rises rapidly with the number of inputs - in the worst case, your table may have something like $3^n \ln(n)$ rows.

Who was Willard Van Orman Quine?

Quine (1908-2000) was born and brought up in Akron, Ohio. He went to Harvard in 1930 to study Philosophy and basically stayed there until he died, 70 years later.

He’s frequently listed as one of the 20th century’s most important philosophers, making significant contributions in the fields of logic and epistemology; as a mathematician, he did important work in set theory.

He died in Boston in 2000 after a battle with Alzheimer’s disease.