DNF and CNF

DNF (disjunctive normal form) and CNF (conjunctive normal form)

are ways of writing wff's that have special roles for computer applications.

In both we have an expression rewritten so that there are no negated parentheses and no other connectives apart from our symbols for negation, disjunction, and conjunction. In DNF the main connectives are for disjunction, while in CNF they are for conjunction. When there is only one connective, for simplicity it can count for either DNF or CNF.

Let's go through a series of steps to rewrite the wff p -> ~(q & r) in DNF.

p -> ~(q v r)
~p v ~(q v r) MI
~p v (~q & ~r) DeM

If you think about it, this is the same result we would get by decomposing an expression for use in a consistency tree.

Now let's take the same expression but rewrite it in CNF.

p -> ~(q v r)
~p v ~(q v r)      MI
~p v (~q & ~r)   DeM
(~p v ~q) & (~p v ~r)    Dist

Practice Exercises

Convert each of the wff's below to DNF and to CNF, justifying each step

(p v ~q) -> (q v ~r)
(p -> ( ~q & ~(p v r)) -> ~r

Send your work on to your instructor for comment.