Conjunctive Normal Form

 

In a manner entirely analogous to the above discussion we can define a fundamental disjunction to be either a literal or the disjunction of two or more literals. A conjunctive normal form (CNF) is either a fundamental disjunction or a conjunction of two or more fundamental disjunctions. For example, the following wffs are CNFs:

, , .

Let's look at some trivial examples. Notice that the following four wffs are CNFs: Ð, Ø P,  PÙ Ø P, and Ø P Ú Q.

As in the case for DNFs, some CNFs are equivalent to simpler CNFs. For example, the CNF  is equivalent to the simpler CNF P by (5.2).

Suppose some wff W has n distinct propositional letters. A CNF for W is called a full conjunctive normal form if each fundamental disjunction has exactly n literals, one for each of the n letters that appear in W. For example, the following wff is a full CNF:

.

On the other hand, the wff is a CNF but not a full CNF.

It's possible to write any truth function f  that is not a tautology as a full CNF. In this case we associate a fundamental disjunction with each line of the truth table in which f  has a false value, with the property that the fundamental disjunction is false on only that line. Let's return to our original example, in which f(P, Q) is true exactly when P and Q have opposite truth values. In the table for the function f (Table 5.3) we have created the fundamental disjunctions on the right of the lines with false values.

Table 5.3

 

P

Q

f(P, Q)

 

      Create

 

 

      Create

0

0

1

1

0

1

0

1

0

1

1

0

 

In this case, Ø P is added to the disjunction if P = true, and P is added to the disjunction if P = false. Then we take the conjunction of these disjunctions

to obtain the following conjunctive normal form of f:

.

 Of course, any tautology is equivalent to the single term CNF . Now we can state the following results for CNFs, which correspond to statements (5.2) and (5.3) for DNFs:

Every wff is equivalent to a CNF.                                                                             

     Every wff that is not a tautology is equivalent to a full CNF.                                   

We should note that some authors use the terms "disjunctive normal form" and "conjunctive normal form" to describe the expressions that we have called "full disjunctive normal forms" and "full conjunctive normal forms." For example, they do not consider  to be a DNF. We use the more general definitions of DNF and CNF because they are useful in describing methods for automatic reasoning and they are useful in describing methods for simplifying digital logic circuits.