[Math] Logic: Converting to CNF and DNF

logic

So I'm given the starting case of;
$$
(p \wedge \neg (q \vee \neg r)) \vee s)
$$
and after applying De Morgan's Law, Compliment Law and Distributive law I think I can achieve CNF by;
$$
(p \wedge (\neg q \wedge \neg \neg r)) \vee s \\
(p \wedge (\neg q \wedge r)) \vee s \\
(p \wedge \neg q \wedge r) \vee s \\
(s \vee p) \wedge (s \vee \neg q) \wedge (s \vee r)
$$
So assuming that's correct, I do not know how to get the starting case in DNF. Or convert CNF to DNF. My notes from the lecturer give the exact same steps to get CNF and DNF from the starting case, so I am confused.

Any help would be great!

Best Answer

The formula which you have already found in the second to last step $$(p\wedge \neg q \wedge r)\vee s$$ is in DNF. Especially note that you do not have to have two elements in each parentheses for it to be DNF/CNF, you just have to have the form:

  1. All negations exactly next to a propositional variable.
  2. (for CNF) all disjunctions connecting other disjunctions or a litteral (a possibly negated propositional variable).

And then the conjunctions connect the rest.

Related Question