Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm writing some code for implementing the Quine McCluskey algorithm and I simply need to clear out if my logic for implementation is ok.

I get some number of minterms and combine each of them so they produce an implicant, later I combine these implicants and consider them as prime implicants. So for the new prime implicants plus the unchecked implicants, I treat them as candidates for essential implicants.

So I'm talking about two loops here, for the total minterms right later for total implicants obtained before.

I've tested my code for a few examples and got good results so far but I need to know this works for n minterms.

share|cite|improve this question
up vote 2 down vote accepted

For an optimal solution you need more than "two loops". The selection of a minimum number of implicants is a set cover problem and was shown to be NP-complete. Selecting a cover with a greedy algorithm just grabs the most promising implicants and is not guaranteed to arrive at an optimal solution.

A good overview on two-level logic minimization was published by Olivier Coudert. Chapter 3 describes the Quine-McCluskey algorithm. This algorithm is of interest for historical reasons but hardly used in practice any more.

For practical experiments, you could try tools like Logic Friday 1. It uses the two-level minimizer Espresso. Logic Friday features an exact/fast switch. It allows you to play with the trade-off between solution speed and optimality.

Another tool for experiments is Karma 3.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.