Project: Quine McCluskey Applet
Enter a boolean expression, list of minterms, or list of maxterms,
any don't care term min-values, and press "Run QM".
During Fall of my junior year (Fall 2010), I learned about the Quine McCluskey algorithm to simplify boolean expressions into their minimum SOP (sum of product) terms. As one of the only non-trivial algorithmic things which we discussed in that digital circuit design course, I was naturally interested in writing a QM program for myself. For those of you who are unfamiliar with the QM algorithm, I've tried to describe it with an example below.
So what does QM do? The algorithm takes a boolean expression and converts it into the simplified version of the canonical form known as the sum-of-products representation. For example, if A, B, C are boolean variables, then the expression AB+B'C'+AC is a sum-of-products expression which reads "(A and B) or (not B and not C) or (A and C)." As an aside, the (non-simplified) canonical sum of product representation refers to the SOP representation where each term contains each of the variables. So the canonical SOP for the SOP expression AB+B'C'+AC is ABC' + ABC + A'B'C'+ AB'C' + AB'C (each of the terms there represents a '1' in the truth table shown below). Note that the boolean operator "and" is treated as a product, and "or" is treated as a sum. The above boolean expression can be represented as the truth table:
| Term # | A | B | C | AB+B'C'+AC |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 2 | 0 | 1 | 0 | 0 |
| 3 | 0 | 1 | 1 | 0 |
| 4 | 1 | 0 | 0 | 1 |
| 5 | 1 | 0 | 1 | 1 |
| 6 | 1 | 1 | 0 | 1 |
| 7 | 1 | 1 | 1 | 1 |
Another way to represent a boolean expression without letters is by writing out the minterms or maxterms of the expression. The minterms are the term indices of all of the '1's of the function, and the maxterms are the zeroes. So, the above expression can be represented by the minterms \{0, 4, 5, 6, 7\} or by the maxterms \{1, 2, 3\}. If you enter in the minterm equivalent into the QM applet above, you'll see that Quine McCluskey actually simplifies the expression to an even simpler SOP form: A + B'C' (when we started with AB+B'C'+AC). However, if you enter the above maxterms (just \{1, 2, 3\}), you'll get the simplified SOP of A'B'. This seems wrong. Didn't we just say that the above representations all represent the same boolean expression? Then why is the maxterm equivalent showing a different output when run with QM? Because the QM applet assumes that there are the least number of variables for the input indices to make sense. So, for the input \{1, 2, 3\}, it's possible that there are only TWO input variables, just 'A' and 'B'. Consider the following truth table:
| Term # | A | B | A'B' |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 2 | 1 | 0 | 0 |
| 3 | 1 | 1 | 0 |
Because the above expression has the same maxterm representation and fewer variables, QM assumes that this is the expression you are talking about. For information how QM works, what "don't care" terms are, or how I implemented it, fill out the form at the bottom of the page.
