An effective way to find missing minterms

Question

I've been messing with logic formulas lately and there was one thing that was often causing me headache. I'll describe it briefly.

When using Quine-McClausky's algorithm for finding MDNF and MCNF, I often have to find both for one formula. Consider this:

ABC or ~AB~C or ~ABC or AB~C

Before I say anything else, let me clarify: ABC = A and B and C; ~C = not C.

Obviously, for such a short formula with only 3 variables, it easy to find the remaining minterms. But, what when you have 5 or 6 variables? I am quite bad at visualizing things, thus I often have to draw a truth table to deduct what minters are missing.

Does anyone have any suggestions on how this can be done?

Thanks!

Answer 1

I am using Logic Friday for such tasks. It includes Espresso, a tool to minimize two-level Boolean functions.

The Quine-McCluskey algorithm does not guarantee optimal solutions. It is merging adjacent minterms in a greedy fashion, whereas Espresso has an exact mode option which will end with the minimum number of terms. In general, there is no polynomial method known to compute a minimal minterm cover for arbitrary Boolean functions. The NP-complete complexity of the Min-DNF problem is discussed here.

For small expressions, you could also ask WolframAlpha.