Section 4.5

118 / The Logic of Boolean Connectives

S(P) ” S(Q)

This is known as the principle of substitution of logical equivalents.

We won™t prove this principle at the moment, because it requires a proof

by induction, a style of proof we get to in a later chapter. But the observation

allows us to use a few simple equivalences to do some pretty amazing things.

For example, using only the two DeMorgan laws and double negation, we can

take any sentence built up with §, ∨, and ¬, and transform it into one where

¬ applies only to atomic sentences. Another way of expressing this is that any

sentence built out of atomic sentences using the three connectives §, ∨, and

¬ is logically equivalent to one built from literals using just § and ∨.

To obtain such a sentence, you simply drive the ¬ in, switching § to ∨,

∨ to §, and canceling any pair of ¬™s that are right next to each other, not

separated by any parentheses. Such a sentence is said to be in negation normal

negation normal form

(NNF) form or NNF. Here is an example of a derivation of the negation normal form

of a sentence. We use A, B, and C to stand for any atomic sentences of the

language.

¬((A ∨ B) § ¬C) ” ¬(A ∨ B) ∨ ¬¬C

” ¬(A ∨ B) ∨ C

” (¬A § ¬B) ∨ C

In reading and giving derivations of this sort, remember that the symbol

” is not itself a symbol of the ¬rst-order language, but a shorthand way of

saying that two sentences are logically equivalent. In this derivation, the ¬rst

step is an application of the ¬rst DeMorgan law to the whole sentence. The

second step applies double negation to the component ¬¬C. The ¬nal step is

an application of the second DeMorgan law to the component ¬(A ∨ B). The

sentence we end up with is in negation normal form, since the negation signs

apply only to atomic sentences.

We end this section with a list of some additional logical equivalences

that allow us to simplify sentences in useful ways. You already constructed

truth tables for most of these equivalences in Exercises 4.13-4.16 at the end

of Section 4.2.

1. (Associativity of §) An fol sentence P § (Q § R) is logically equivalent

associativity

to (P § Q) § R, which is in turn equivalent to P § Q § R. That is,

P § (Q § R) ” (P § Q) § R ” P § Q § R

2. (Associativity of ∨) An fol sentence P ∨ (Q ∨ R) is logically equivalent

to (P ∨ Q) ∨ R, which is in turn equivalent to P ∨ Q ∨ R. That is,

P ∨ (Q ∨ R) ” (P ∨ Q) ∨ R ” P ∨ Q ∨ R

Chapter 4

Pushing negation around / 119

3. (Commutativity of §) A conjunction P § Q is logically equivalent to commutativity

Q § P. That is,

P§Q ” Q§P

As a result, any rearrangement of the conjuncts of an fol sentence is

logically equivalent to the original. For example, P § Q § R is equivalent

to R § Q § P.

4. (Commutativity of ∨) A conjunction P ∨ Q is logically equivalent to

Q ∨ P. That is,

P∨Q ” Q∨P

As a result, any rearrangement of the disjuncts of an fol sentence is

logically equivalent to the original. For example, P ∨ Q ∨ R is equivalent

to R ∨ Q ∨ P.

5. (Idempotence of §) A conjunction P § P is equivalent to P. That is, idempotence

P§P ” P

More generally (given Commutativity), any conjunction with a repeated

conjunct is equivalent to the result of removing all but one occurrence

of that conjunct. For example, P § Q § P is equivalent to P § Q.

6. (Idempotence of ∨) A disjunction P ∨ P is equivalent to P. That is,

P∨P ” P

More generally (given Commutativity), any disjunction with a repeated

disjunct is equivalent to the result of removing all but one occurrence

of that disjunct. For example, P ∨ Q ∨ P is equivalent to P ∨ Q.

Here is an example where we use some of these laws to show that the ¬rst

sentence in the following list is logically equivalent to the last. Once again (as

in what follows), we use A, B, and C to stand for arbitrary atomic sentences

of fol. Thus the result is in negation normal form.

(A ∨ B) § C § (¬(¬B § ¬A) ∨ B) ” (A ∨ B) § C § ((¬¬B ∨ ¬¬A) ∨ B)

” (A ∨ B) § C § ((B ∨ A) ∨ B)

” (A ∨ B) § C § (B ∨ A ∨ B)

” (A ∨ B) § C § (B ∨ A)

” (A ∨ B) § C § (A ∨ B)

” (A ∨ B) § C

Section 4.5

120 / The Logic of Boolean Connectives

We call a demonstration of this sort a chain of equivalences. The ¬rst step

chain of equivalences

in this chain is justi¬ed by one of the DeMorgan laws. The second step involves

two applications of double negation. In the next step we use associativity to

remove the unnecessary parentheses. In the fourth step, we use idempotence

of ∨. The next to the last step uses commutativity of ∨, while the ¬nal step

uses idempotence of §.

Remember

1. Substitution of equivalents: If P and Q are logically equivalent:

P”Q

then the results of substituting one for the other in the context of a

larger sentence are also logically equivalent:

S(P) ” S(Q)

2. A sentence is in negation normal form (NNF) if all occurrences of ¬

apply directly to atomic sentences.

3. Any sentence built from atomic sentences using just §, ∨, and ¬ can

be put into negation normal form by repeated application of the De-

Morgan laws and double negation.

4. Sentences can often be further simpli¬ed using the principles of asso-

ciativity, commutativity, and idempotence.

Exercises

4.31 (Negation normal form) Use Tarski™s World to open Turing™s Sentences. You will ¬nd the fol-

‚ lowing ¬ve sentences, each followed by an empty sentence position.

1. ¬(Cube(a) § Larger(a, b))

3. ¬(Cube(a) ∨ ¬Larger(b, a))

5. ¬(¬Cube(a) ∨ ¬Larger(a, b) ∨ a = b)

7. ¬(Tet(b) ∨ (Large(c) § ¬Smaller(d, e)))

9. Dodec(f) ∨ ¬(Tet(b) ∨ ¬Tet(f) ∨ ¬Dodec(f))

In the empty positions, write the negation normal form of the sentence above it. Then build

any world where all of the names are in use. If you have gotten the negation normal forms

Chapter 4

Conjunctive and disjunctive normal forms / 121

correct, each even numbered sentence will have the same truth value in your world as the odd

numbered sentence above it. Verify that this is so in your world. Submit the modi¬ed sentence

¬le as Sentences 4.31.

4.32 (Negation normal form) Use Tarski™s World to open the ¬le Sextus™ Sentences. In the odd

‚ numbered slots, you will ¬nd the following sentences.

1. ¬(Home(carl) § ¬Home(claire))

3. ¬[Happy(max) § (¬Likes(carl, claire) ∨ ¬Likes(claire, carl))]

5. ¬¬¬[(Home(max) ∨ Home(carl)) § (Happy(max) ∨ Happy(carl))]

Use Double Negation and DeMorgan™s laws to put each sentence into negation normal form in

the slot below it. Submit the modi¬ed ¬le as Sentences 4.32.

In each of the following exercises, use associativity, commutativity, and idempotence to simplify the

sentence as much as you can using just these rules. Your answer should consist of a chain of logical

equivalences like the chain given on page 119. At each step of the chain, indicate which principle you

are using.

4.33 4.34

(A § B) § A (B § (A § B § C))

4.35 4.36

(A ∨ B) ∨ (C § D) ∨ A (¬A ∨ B) ∨ (B ∨ C)

4.37 (A § B) ∨ C ∨ (B § A) ∨ A

Section 4.6

Conjunctive and disjunctive normal forms

We have seen that with a few simple principles of Boolean logic, we can

start with a sentence and transform it into a logically equivalent sentence

in negation normal form, one where all negations occur in front of atomic

sentences. We can improve on this by introducing the so-called distributive

laws. These additional equivalences will allow us to transform sentences into

what are known as conjunctive normal form (CNF) and disjunctive normal

form (DNF). These normal forms are quite important in certain applications

of logic in computer science, as we discuss in Chapter 17. We will also use

disjunctive normal form to demonstrate an important fact about the Boolean

connectives in Chapter 7.

Recall that in algebra you learned that multiplication distributes over ad-

dition: a—(b+c) = (a—b)+(a—c). The distributive laws of logic look formally distribution

Section 4.6

122 / The Logic of Boolean Connectives

much the same. One version tells us that P § (Q ∨ R) is logically equivalent to

(P § Q) ∨ (P § R). That is, § distributes over ∨. To see that this is so, notice

that the ¬rst sentence is true if and only if P plus at least one of Q or R

is true. But a moment™s thought shows that the second sentence is true in

exactly the same circumstances. This can also be con¬rmed by constructing

a joint truth table for the two sentences, which you™ve already done if you did

Exercise 4.17.

In arithmetic, + does not distribute over —. However, ∨ does distribute

over §. That is to say, P ∨ (Q § R) is logically equivalent to (P ∨ Q) § (P ∨ R),

as you also discovered in Exercise 4.18.

Remember

(The distributive laws) For any sentences P, Q, and R:

1. Distribution of § over ∨: P § (Q ∨ R) ” (P § Q) ∨ (P § R)

2. Distribution of ∨ over §: P ∨ (Q § R) ” (P ∨ Q) § (P ∨ R)

As you may recall from algebra, the distributive law for — over + is in-

credibly useful. It allows us to transform any algebraic expression involving +

and —, no matter how complex, into one that is just a sum of products. For

example, the following transformation uses distribution three times.

(a + b)(c + d) = (a + b)c + (a + b)d

= ac + bc + (a + b)d

= ac + bc + ad + bd

In exactly the same way, the distribution of § over ∨ allows us to transform

any sentence built up from literals by means of § and ∨ into a logically

equivalent sentence that is a disjunction of (one or more) conjunctions of

(one or more) literals. That is, using this ¬rst distributive law, we can turn

any sentence in negation normal form into a sentence that is a disjunction of

conjunctions of literals. A sentence in this form is said to be in disjunctive

disjunctive normal

form (DNF) normal form.

Here is an example that parallels our algebraic example. Notice that, as

in the algebraic example, we are distributing in from the right as well as the

left, even though our statement of the rule only illustrates distribution from

the left.

(A ∨ B) § (C ∨ D) ” [(A ∨ B) § C] ∨ [(A ∨ B) § D]

” (A § C) ∨ (B § C) ∨ [(A ∨ B) § D]

” (A § C) ∨ (B § C) ∨ (A § D) ∨ (B § D)

Chapter 4

Conjunctive and disjunctive normal forms / 123

As you can see, distribution of § over ∨ lets us drive conjunction signs

deeper and deeper, just as the DeMorgan laws allow us to move negations

deeper. Thus, if we take any sentence and ¬rst use DeMorgan (and double

negation) to get a sentence in negation normal form, we can then use this

¬rst distribution law to get a sentence in disjunctive normal form, one in

which all the conjunction signs apply to literals.

Likewise, using distribution of ∨ over §, we can turn any negation normal

form sentence into one that is a conjunction of one or more sentences, each of

which is a disjunction of one or more literals. A sentence in this form is said

to be in conjunctive normal form (CNF). Here™s an example, parallel to the conjunctive normal

form (CNF)

one given above but with § and ∨ interchanged:

(A § B) ∨ (C § D) ” [(A § B) ∨ C] § [(A § B) ∨ D]

” (A ∨ C) § (B ∨ C) § [(A § B) ∨ D]

” (A ∨ C) § (B ∨ C) § (A ∨ D) § (B ∨ D)

On page 118, we showed how to transform the sentence ¬((A ∨ B) § ¬C)