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
    Commented Feb 13, 2019 at 11:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.