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.