This is bonus material for Philosophy 9.


23.  DISJUNCTIVE AND CONJUNCTIVE NORMAL FORMS

One thing you saw early as we began working with our equivalence rules was that we could do withour a separate symbol for implication (the arrow).  As you learned to work with consistency trees you saw how, in effect, we could break down (decompose) any expression into one in which only the sign for disjunction (the wedge) would be the main connective between any groupings.
P -> ~(Q & R)
/            \
~P       ~Q
           ~R
If we write our results on a single line, we would have ~P v (~Q & ~R).  This is an example if what we mean by a disjunctive normal form (DNF), a way of representing relationships that is important for work in computer science.

If we choose to work with what is called a conjunctive normal form (CNF), also important for some work in computer science, we make the sign for conjunction (the ampersand) our main connective between parentheses.  Conversions here are somewhat less easy in that we cannot just read the results from a consistency tree.  Instead, let us work step by step with our equivalence rules.
P -> ~(Q & R)
~P v ~(Q & R)       Impl
(~P v ~Q) & (~P v ~R)      DM

Special instances of CNFs important in computer science are Horn formulas in which, inside a grouping, all the letters except for one are negated.  An example would be
(~P v ~Q v R) & (~P v ~Q v S).

With shorter expressions, such as P, ~Q, P v Q, P & Q, no conversions occur and all if these, if we so choose, may count as either DNFs or CNFs.  The key is that when there is a more complicated expression, for a DNF the wedge is the main connective between groupings and for a CNF it is the ampersand, and also the parenthesis itself cannot be negated.  Note too that we may have more than just two letters inside the parenthesis as long as the connectives between them are the same.