2
$\begingroup$

I am fairly confident of the definition of CNF and DNF (e.g. why $ (P \land Q)$ in both CNF and DNF.

However, I'm a little shaky when it comes to converting between the two normal forms. Is it possible to just follow some mechanical steps to arrive at the answer?

Have I got the right idea below:

$(P \rightarrow Q) \land (S \rightarrow R)$

$(\neg P \lor Q) \land (\neg S \lor R)$ First, convert all connectives to $\{\neg, \land,\lor\} $. Formula is in CNF.

$((\neg P \lor Q) \land \neg S) \lor ((\neg P \lor Q)\land R)$ Use Distributive law. Not in DNF.

$((\neg P \land \neg S) \lor (Q \land \neg S)) \lor ((\neg P \land R) \lor (Q \land R))$ Distribute again. Now in DNF.

First, I got rid of all connectives not allowed in CNF/DNF. Then I Used the distributive law repeatedly until the CNF formula became DNF.

Is this a good way to go about it?

I've taken the earlier problem and changed it to the below:

$$ (P \rightarrow Q) \lor (S \rightarrow R)$$

My solution:

$$(\neg S \lor\neg P) \lor (\neg S \lor Q) \lor (\neg P \lor R) \lor (Q \lor R)$$

Simplified:

$$\neg S \lor \neg P \lor Q \lor R$$ This should be in CNF right? Since there is no disjunction>Conjunction>Disjunction in the syntax tree of this formula. Same reason $(P \lor Q)$ can be both CNF and DNF.

Meaning that a formula consisting only of Conjunction or Disjunctions is both CNF and DNF. I realise that I could just put in $(\neg P \lor Q) \lor (\neg S \lor R)$. Just wanted to see if other representations are OK.

$\endgroup$
  • 1
    $\begingroup$ You did just fine! Indeed because of associativity of $\lor$, you can write you last line as $$(\neg P \land \neg S) \lor (Q \land \neg S) \lor (\neg P \land R) \lor (Q \land R)$$ I simply deleted unnecessary parentheses. $\endgroup$ – Namaste Oct 14 '16 at 21:51
  • $\begingroup$ Awesome. I have tried this with converting a DNF version of this to CNF. I'll add it to the main question. Pls let me know what you think. $\endgroup$ – Shiny_and_Chrome Oct 14 '16 at 22:34
  • 1
    $\begingroup$ Yes, you did just fine. I just saw that you had changed starting points. But you did more work than you needed to. Note $$(P \rightarrow Q) \lor (S \rightarrow R) \equiv \lnot P \lor Q \lor \lnot S \lor R$$ directly. $\endgroup$ – Namaste Oct 14 '16 at 23:09
  • $\begingroup$ Fantastic. I think I've got it now. I did realise the simple solution, I just wanted to make sure that I can represent the same formula is different CNF forms. Thanks. $\endgroup$ – Shiny_and_Chrome Oct 15 '16 at 13:00
  • 1
    $\begingroup$ Great! nice work! and your welcome :-) $\endgroup$ – Namaste Oct 15 '16 at 13:38

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.