<<

. 23
( 107 .)



>>


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)

<<

. 23
( 107 .)



>>