0
$\begingroup$

Is there a way i can go from dnf to cnf quickly? Can I simply negate dnf to get cnf? and get negate cnf to get dnf?

e.g.

$P \to (Q\wedge \neg (P \to R))$

= $\neg P \vee (Q \wedge \neg ( \neg P \vee R))$

= $\neg P \vee (Q \wedge (P \wedge \neg R))$

= $\neg P \vee (Q \wedge P \wedge \neg R)$ --- is this correctly in DNF?

How could I go from CNF from here? I'm slightly stuck.

$\endgroup$
  • $\begingroup$ Negating (and then using de Morgan) will get you a CNF from a DNF and vice versa, but they will not be equivalent. I doubt that this is what you want. $\endgroup$ – Klaus Draeger Oct 2 '15 at 16:25
  • $\begingroup$ Yup, you're right, I need them to be equivalent. Would I use distrubtivity laws? $\endgroup$ – ak1652 Oct 2 '15 at 16:26
1
$\begingroup$

Yes. You've got it in DNF. To convert to CNF use the distributive law: $A \vee (B \wedge C) = (A \vee B) \wedge (A \vee C)$

$$\neg P \vee (Q \wedge P \wedge \neg R) \leftrightarrow (\neg P \vee Q) \wedge (\neg P \vee (P \wedge \neg R)) \leftrightarrow (\neg P \vee Q) \wedge (\neg P \vee P) \wedge (\neg P \wedge \neg R) $$

(of course the $\neg P \vee P$ can be canceled).

For more information...

https://en.wikipedia.org/wiki/Conjunctive_normal_form

$\endgroup$
  • $\begingroup$ Much appreciated, thanks everybody. So the trick is to use distrubtivity laws to switch between the two and then apply cancellations. Many thanks. $\endgroup$ – ak1652 Oct 2 '15 at 16:28
  • $\begingroup$ Yep! It will cause it to grow in length, but there's nothing inherently tricky about it. :) $\endgroup$ – Bill Cook Oct 2 '15 at 16:29
  • $\begingroup$ Many thanks, had me very confused at first $\endgroup$ – ak1652 Oct 2 '15 at 16:29
  • 1
    $\begingroup$ Note if mere equisatisfiability (rather than equivalence) is all you need, you can save yourself an exponential blow-up for DNF->CNF by using the Tseitin transform (en.wikipedia.org/wiki/Tseitin_transformation). $\endgroup$ – Klaus Draeger Oct 2 '15 at 16:30

Your Answer

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

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