tence just happens to be in disjunctive normal form. Let us repeat our earlier

transformation, but continue until we get a sentence in conjunctive normal

form.

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

” ¬(A ∨ B) ∨ C

” (¬A § ¬B) ∨ C

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

It is important to remember that a sentence can count as being in both

conjunctive and disjunctive normal forms at the same time. For example, the

sentence

Home(claire) § ¬Home(max)

is in both DNF and CNF. On the one hand, it is in disjunctive normal form

since it is a disjunction of one sentence (itself) which is a conjunction of two

literals. On the other hand, it is in conjunctive normal form since it is a

conjunction of two sentences, each of which is a disjunction of one literal.

In case you ¬nd this last remark confusing, here are simple tests for

whether sentences are in disjunctive normal form and conjunctive normal

form. The tests assume that the sentence has no unnecessary parentheses and

contains only the connectives §, ∨, and ¬.

To check whether a sentence is in DNF, ask yourself whether all the test for DNF

Section 4.6

124 / The Logic of Boolean Connectives

negation signs apply directly to atomic sentences and whether all

the conjunction signs apply directly to literals. If both answers are

yes, then the sentence is in disjunctive normal form.

To check whether a sentence is in CNF, ask yourself whether all

test for CNF

the negation signs apply directly to atomic sentences and all the

disjunction signs apply directly to literals. If both answers are yes,

then the sentence is in conjunctive normal form.

Now look at the above sentence again and notice that it passes both of

these tests (in the CNF case because it has no disjunction signs).

Remember

1. A sentence is in disjunctive normal form (DNF) if it is a disjunction

of one or more conjunctions of one or more literals.

2. A sentence is in conjunctive normal form (CNF) if it is a conjunction

of one or more disjunctions of one or more literals.

3. Distribution of § over ∨ allows you to transform any sentence in nega-

tion normal form into disjunctive normal form.

4. Distribution of ∨ over § allows you to transform any sentence in nega-

tion normal form into conjunctive normal form.

5. Some sentences are in both CNF and DNF.

You try it

................................................................

1. Use Tarski™s World to open the ¬le DNF Example. In this ¬le you will ¬nd

two sentences. The second sentence is the result of putting the ¬rst into

disjunctive normal form, so the two sentences are logically equivalent.

2. Build a world in which the sentences are true. Since they are equivalent,

you could try to make either one true, but you will ¬nd the second one

easier to work on.

3. Play the game for each sentence, committed correctly to the truth of the

sentence. You should be able to win both times. Count the number of steps

it takes you to win.

Chapter 4

Conjunctive and disjunctive normal forms / 125

4. In general it is easier to evaluate the truth value of a sentence in disjunctive

normal form. This comes out in the game, which takes at most three steps

for a sentence in DNF, one each for ∨, §, and ¬, in that order. There is

no limit to the number of steps a sentence in other forms may take.

5. Save the world you have created as World DNF 1.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Congratulations

Exercises

4.38 If you skipped the You try it section, go back and do it now. Submit the ¬le World DNF 1.

‚

4.39 Open CNF Sentences. In this ¬le you will ¬nd the following conjunctive normal form sentences

‚ in the odd numbered positions, but you will see that the even numbered positions are blank.

1. (LeftOf(a, b) ∨ BackOf(a, b)) § Cube(a)

3. Larger(a, b) § (Cube(a) ∨ Tet(a) ∨ a = b)

5. (Between(a, b, c) ∨ Tet(a) ∨ ¬Tet(b)) § Dodec(c)

7. Cube(a) § Cube(b) § (¬Small(a) ∨ ¬Small(b))

9. (Small(a) ∨ Medium(a)) § (Cube(a) ∨ ¬Dodec(a))

In the even numbered positions you should ¬ll in a DNF sentence logically equivalent to the

sentence above it. Check your work by opening several worlds and checking to see that each

of your sentences has the same truth value as the one above it. Submit the modi¬ed ¬le as

Sentences 4.39.

4.40 Open More CNF Sentences. In this ¬le you will ¬nd the following sentences in every third

‚ position.

1. ¬[(Cube(a) § ¬Small(a)) ∨ (¬Cube(a) § Small(a))]

4. ¬[(Cube(a) ∨ ¬Small(a)) § (¬Cube(a) ∨ Small(a))]

7. ¬(Cube(a) § Larger(a, b)) § Dodec(b)

10. ¬(¬Cube(a) § Tet(b))

13. ¬¬Cube(a) ∨ Tet(b)

The two blanks that follow each sentence are for you to ¬rst transform the sentence into negation

normal form, and then put that sentence into CNF. Again, check your work by opening several

worlds to see that each of your sentences has the same truth value as the original. When you

are ¬nished, submit the modi¬ed ¬le as Sentences 4.40.

Section 4.6

126 / The Logic of Boolean Connectives

In Exercises 4.41-4.43, use a chain of equivalences to convert each sentence into an equivalent sentence

in disjunctive normal form. Simplify your answer as much as possible using the laws of associativity,

commutativity, and idempotence. At each step in your chain, indicate which principle you are applying.

Assume that A, B, C, and D are literals.

4.41 4.42

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

4.43 A § (A § (B ∨ (A § C)))

Chapter 4

Chapter 5

Methods of Proof for Boolean

Logic

Truth tables give us powerful techniques for investigating the logic of the

Boolean operators. But they are by no means the end of the story. Truth

tables are ¬ne for showing the validity of simple arguments that depend only

on truth-functional connectives, but the method has two very signi¬cant lim-

itations.

First, truth tables get extremely large as the number of atomic sentences limitations of truth

table methods

goes up. An argument involving seven atomic sentences is hardly unusual, but

testing it for validity would call for a truth table with 27 = 128 rows. Testing

an argument with 14 atomic sentences, just twice as many, would take a table

containing over 16 thousand rows. You could probably get a Ph.D. in logic for

building a truth table that size. This exponential growth severely limits the

practical value of the truth table method.

The second limitation is, surprisingly enough, even more signi¬cant. Truth

table methods can™t be easily extended to reasoning whose validity depends

on more than just truth-functional connectives. As you might guess from the

arti¬ciality of the arguments looked at in the previous chapter, this rules out

most kinds of reasoning you™ll encounter in everyday life. Ordinary reasoning

relies heavily on the logic of the Boolean connectives, make no mistake about

that. But it also relies on the logic of other kinds of expressions. Since the

truth table method detects only tautological consequence, we need a method

of applying Boolean logic that can work along with other valid principles of

reasoning.

Methods of proof, both formal and informal, give us the required exten-

sibility. In this chapter we will discuss legitimate patterns of inference that

arise when we introduce the Boolean connectives into a language, and show

how to apply the patterns in informal proofs. In Chapter 6, we™ll extend our

formal system with corresponding rules. The key advantage of proof methods

over truth tables is that we™ll be able to use them even when the validity of

our proof depends on more than just the Boolean operators.

The Boolean connectives give rise to many valid patterns of inference.

Some of these are extremely simple, like the entailment from the sentence

P § Q to P. These we will refer to as valid inference steps, and will discuss

127

128 / Methods of Proof for Boolean Logic

them brie¬‚y in the ¬rst section. Much more interesting are two new methods

of proof that are allowed by the new expressions: proof by cases and proof by

contradiction. We will discuss these later, one at a time.

Section 5.1

Valid inference steps

Here™s an important rule of thumb: In an informal proof, it is always legiti-

mate to move from a sentence P to another sentence Q if both you and your

“audience” (the person or people you™re trying to convince) already know

important rule of thumb

that Q is a logical consequence of P. The main exception to this rule is when

you give informal proofs to your logic instructor: presumably, your instructor

knows the assigned argument is valid, so in these circumstances, you have to

pretend you™re addressing the proof to someone who doesn™t already know

that. What you™re really doing is convincing your instructor that you see that

the argument is valid and that you could prove it to someone who did not.

The reason we start with this rule of thumb is that you™ve already learned

several well-known logical equivalences that you should feel free to use when

giving informal proofs. For example, you can freely use double negation or

idempotence if the need arises in a proof. Thus a chain of equivalences of the

sort we gave on page 119 is a legitimate component of an informal proof. Of

course, if you are asked to prove one of the named equivalences, say one of

the distribution or DeMorgan laws, then you shouldn™t presuppose it in your

proof. You™ll have to ¬gure out a way to prove it to someone who doesn™t

already know that it is valid.

A special case of this rule of thumb is the following: If you already know

that a sentence Q is a logical truth, then you may assert Q at any point in

your proof. We already saw this principle at work in Chapter 2, when we

discussed the re¬‚exivity of identity, the principle that allowed us to assert a

sentence of the form a = a at any point in a proof. It also allows us to assert

other simple logical truths, like excluded middle (P ∨ ¬P), at any point in a

proof. Of course, the logical truths have to be simple enough that you can be

sure your audience will recognize them.

There are three simple inference steps that we will mention here that don™t

involve logical equivalences or logical truths, but that are clearly supported

by the meanings of § and ∨. First, suppose we have managed to prove a

conjunction, say P § Q, in the course of our proof. The individual conjuncts

P and Q are clearly consequences of this conjunction, because there is no way

for the conjunction to be true without each conjunct being true. Thus, we

Chapter 5

Valid inference steps / 129

are justi¬ed in asserting either. More generally, we are justi¬ed in inferring,

from a conjunction of any number of sentences, any one of its conjuncts. This conjunction

elimination

inference pattern is sometimes called conjunction elimination or simpli¬cation,

(simpli¬cation)

when it is presented in the context of a formal system of deduction. When it

is used in informal proofs, however, it usually goes by without comment, since

it is so obvious.

Only slightly more interesting is the converse. Given the meaning of §, it

is clear that P § Q is a logical consequence of the pair of sentences P and Q:

there is no way the latter could be true without former also being true. Thus

if we have managed to prove P and to prove Q from the same premises, then

we are entitled to infer the conjunction P § Q. More generally, if we want to conjunction

introduction

prove a conjunction of a bunch of sentences, we may do so by proving each

conjunct separately. In a formal system of deduction, steps of this sort are

sometimes called conjunction introduction or just conjunction. Once again,

in real life reasoning, these steps are too simple to warrant mention. In our

informal proofs, we will seldom point them out explicitly.

Finally, let us look at one valid inference pattern involving ∨. It is a simple

step, but one that strikes students as peculiar. Suppose that you have proven

Cube(b). Then you can conclude Cube(a) ∨ Cube(b) ∨ Cube(c), if you should disjunction

introduction

want to for some reason, since the latter is a consequence of the former.