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.