Normal Forms
123
Example 1.
(a) a A b A -c is a term.
(b) The formula
(a A b A c) V (-a A -,b A --c) V (a A -- c A q)
is in disjunctive normal form.
(c) T is a term. It is a conjunction of zero literals.
(d) a is a term. It is a conjunction of one literal.
(e) a A b A -"c and T are in disjunctive normal form. Each is a disjunction of one term.
(f) F is in disjunctive normal form. It is a disjunction of zero terms.
Theorem 1. Every formula is logically equivalent to a formula in DNE.
The proof of Theorem 1 is just a formalization of what is done in Example 2.
Example 2. Let VV be the formula
*I = (-(p - q)) - (q A -- r)
Determine a DNF for *.
Solution. A formula may have several equivalent formulas in DNF, but we want a systematic way to find one.
The first step in finding a DNF for * is to find the truth table for all the interpretations
of 4', as shown in Table 2.7.
Table 2.7 Abbreviated Truth Table for 4
Interpretation
p
q
r
(-(p -- q)) --* (q A -'r)
Io
T
T T
T
I1
T
T F
T
12
T
F
T
F
13
T
F
F
F
14
F
T T
T
15
F
T F
T
16
F
F
T
T
17
F
F
F
T
The next step is to construct, for each interpretation Ii, 0 < i < 7, a term that is T in
that interpretation and F in all other interpretations. Such terms are listed in Table 2.8.
Interpretation
Matching Term
10
pAqAr
I1
pAqA--r
Table 2.8 True Terms
12
p A -q A r
in the Interpretations
13
p A -q A -r
14
-pAqAr
15
-p A q A -r
16
-PA -q A r
17
-p A -q A -r