<<

. 24
( 107 .)



>>

into one in negation normal form. The result was (¬A § ¬B) ∨ C. This sen-
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.

<<

. 24
( 107 .)



>>