As I understand it the Quine-McCluskey method allows you to start with a set of maxterms (or minterms), and combine them pairwise in a systematic way into a smaller set of clauses with a smaller set of variables in some (hopefully most) of the clauses. I understand how to apply the method, given a set of maxterms.

My question is: if I start not with a set of maxterms, but with an arbitrary set of clauses in a CNF (analogously in a DNF), can I apply the same approach to "combine" compatible terms? Or must I first expand the CNF into product of maxterms? The latter would make the algorithm exponential in worst case, and the former would seem to be quadratic in best case.

When I look at the QM method, it is not immediately obvious to me which part of the algorithm really depend on the initial set of clauses being maxterms.

  • $\begingroup$ My testing seems to indicate that QM still works. QM phase #1 reducew pairs like $(X\vee \neg Y)\wedge (X\vee Y)\to X$. QM suggests to sort the clauses by increasing number of one-bits, assuming each term is a bit-string with length=n (the number of Boolean variables). However, if we represent each term as a list of integers such as (1 3 -5) representing $x_1\vee x_3\vee\neg x_5$, then the QM method seems to still apply, we just sort by number of positives, but be carful to only compare clauses with the same length. $(1~3~-5)\wedge (1~3~5) \to (1~3)$ $\endgroup$
    – Jim Newton
    Feb 13, 2019 at 11:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.