Discrete Mathematics for Computer Science

122 CHAPTER 2 Formal Logic

2.5.1 Disjunctive Normal Form

Consider the following two formulas:

=(p -- (q V r)) +* (q - p)

and

= (p A q) V (p A -q A r) V (-p A -,q)

The truth tables for t and t would show that these two formulas are logically equivalent.

By some measures, 7& is more complicated. For example, 0 has four propositional connec-

tives, whereas Vf has nine. Nevertheless, many people find * to be far easier to understand.

The formula * explicitly lists three cases in which the formula is true:

(1) p and q are both T.

(2) p and r are T and q is F.

(3) p and q are both F.

For all other interpretations of p, q, and r, the truth value of *r is F. It is not nearly so

obvious what 0 "says." Although 0 is shorter, it also seems to be more complex.

A formula like *t that is just a list of cases that make the formula have a truth value of

T is called a disjunctive normal form (DNF). Each of the three cases, (p A q), (p A -q A

r), and (--p A -'q), is called a term. One might think of each term as describing a single

case. The entire disjunctive normal form formula is just a disjunct of terms that make the

formula T. (The words term and disjunctive normal form will be defined formally below.)

The difference in comprehensibility is even more extreme if the formula 0 is negated.

The formula

-((p -- (q V r)) *-> (q -+ p))

is logically equivalent to the disjunctive normal form formula

(--p A q) V (p A --q A -r)

The disjunctive normal form is a disjunction of only two terms, which makes it particularly

easy to understand.

Definition 1. Let p be a proposition letter. Then, p is a positive literal, and -p is a

negative literal. A literal is a positive literal or a negative literal.

Definition 2. Let-, X-2 ...... km be a set of m literals with m E N. A term is a conjunc-

tion

),1Ak2 A ... A Xm

of m literals. A formula f is in DNF if it is a disjunction 01 V 02 V ... V Ok of k terms

where k e N.

The disjunction of zero formulas is F. The conjunction of zero formulas is T. This is

analogous to defining the sum of zero numbers to be zero and the product of zero numbers

to be 1. For example, F v p <* p is analogous to 0 + x = x.