Let S be a boolean expression in conjunctive normal form. S is expressed as the products of sums (where product is defined as AND, and sum is defined as OR).

For example: (a+b) * (-b + c) * (-a + b + c)

The satisfiability of a boolean expression in conjunctive normal form was the first problem proven to be np-complete. See Cook's Theorem.

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

Log in or register to write something here or to contact authors.