conjunctive normal form (idea)

The conjunctive normal form is a way of expressing formulae in propositional logic that only uses the negation and disjunction operators (NOT and OR). Once the formulae have been converted to this form, they are then strung together in a series of conjunctions, (AND statements) creating one long expression.

The procedure for converting standardly expressed propositional formulae into conjunctive normal form has three steps:

1. Remove all instances of the implication operator using this truth-functional equivilent form:
   (P→Q) to (¬PvQ)

2. Reduce the scope of the negation symbols by using DeMorgan's Rules:
   ¬(P&Q) to ¬Pv¬Q
   ¬(PvQ) to ¬P&¬Q

3. Remove conjunctions from within disjunctions using distributivity:
   Pv(Q&R) becomes (PvQ) & (PvR)

Example
Convert the following set of formulae into the Conjunctive Normal Form:

a) (G&¬T)→L
b) L→(DvS)
c) ¬T→R
d) ¬R

a)
First, we'll remove the implication using Rule 1.
(G&¬T)→L becomes ¬(G&¬T)vL
Then remove the conjunction using Rule 2.
¬(G&¬T)vL becomes (¬GvT)vL

b)
Simply have to remove the implication.
L→(DvS) becomes ¬Lv(DvS)

c)
Remove the implication.
¬T→R becomes (TvR)

d)
¬R is correct the way it is.

Finally, we string together the formulae in a series of conjunctions and we have the Conjunctive Normal Form.

(¬GvT)vL & ¬Lv(DvS) & (TvR) & ¬R