4
$\begingroup$

There is the Quine–McCluskey algorithm for finding a minimal expression of a boolean expression in dis-junctive normal form. Would applying DeMorgan's rule to the minimal DNF result in the minimal CNF?

Is there an equivalent algorithm for con-junctive normal form? Not necessarily looking for something efficient as the results will be cached, just if such an algorithm exists.

$\endgroup$
1
  • $\begingroup$ Just from that wikipedia page: "The Quine–McCluskey algorithm is functionally identical to Karnaugh mapping". And from the page on Karnaugh mapping: "A sum-of-products expression (SOP) can always be implemented using AND gates feeding into an OR gate, and a product-of-sums expression (POS) leads to OR gates feeding an AND gate". Which from the context means it can be applied to both CNF and DNF. $\endgroup$
    – rus9384
    Commented May 25, 2022 at 22:19

1 Answer 1

2
$\begingroup$

I'm not 100% sure about this but here's what I think:

Would applying DeMorgan's rule to the minimal DNF result in the minimal CNF?

If you negate the expression and then apply De Morgan's laws you get a CNF for the negation of the original expression. I think it's also minimal though I don't have a rigorous proof.

Is there an equivalent algorithm for con-junctive normal form?

You can use Quine–McCluskey with a minor modification based on the previous idea. First negate the expression. Then apply Quine–McCluskey to get DNF for the negation. Then apply negation again and De Morgan's laws to get the original expression in CNF form.

Another way to look at this is that normal Quine–McCluskey basically combines 1s in the truth table of the expression to get minterms and a minimal DNF. With the modification I gave the algorithm essentially combines 0s to get a CNF (which I think is also minimal).

$\endgroup$

Your Answer

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

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