86 / The Boolean Connectives

is happy is unambiguous, whereas it would be ambiguous without the either.

What it means is that

[Home(max) § Home(claire)] ∨ Happy(carl)

In other words, either and both can sometimes act as left parentheses act in

fol. The same list of sentences demonstrates many other uses of either and

both.

Remember

1. The English expression and sometimes suggests a temporal ordering;

the fol expression § never does.

2. The English expressions but, however, yet, nonetheless, and moreover

are all stylistic variants of and.

3. The English expressions either and both are often used like parentheses

to clarify an otherwise ambiguous sentence.

Exercises

3.20 (Describing a simple world) Open Boole™s World. Start a new sentence ¬le, named Sen-

‚ tences 3.20, where you will describe some features of this world. Check each of your sentences

to see that it is indeed a sentence and that it is true in this world.

1. Notice that f (the large dodecahedron in the back) is not in front of a. Use your ¬rst

sentence to say this.

2. Notice that f is to the right of a and to the left of b. Use your second sentence to say

this.

3. Use your third sentence to say that f is either in back of or smaller than a.

4. Express the fact that both e and d are between c and a.

5. Note that neither e nor d is larger than c. Use your ¬fth sentence to say this.

6. Notice that e is neither larger than nor smaller than d. Use your sixth sentence to say

this.

7. Notice that c is smaller than a but larger than e. State this fact.

8. Note that c is in front of f; moreover, it is smaller than f . Use your eighth sentence

to state these things.

Chapter 3

Translation / 87

9. Notice that b is in the same row as a but is not in the same column as f. Use your

ninth sentence to express this fact.

10. Notice that e is not in the same column as either c or d. Use your tenth sentence to

state this.

Now let™s change the world so that none of the above mentioned facts hold. We can do this as

follows. First move f to the front right corner of the grid. (Be careful not to drop it o¬ the

edge. You might ¬nd it easier to make the move from the 2-D view. If you accidentally drop

it, just open Boole™s World again.) Then move e to the back left corner of the grid and make

it large. Now none of the facts hold; if your answers to 1“10 are correct, all of the sentences

should now be false. Verify that they are. If any are still true, can you ¬gure out where you went

wrong? Submit your sentences when you think they are correct. There is no need to submit

the modi¬ed world ¬le.

3.21 (Some translations) Tarski™s World provides you with a very useful way to check whether your

‚ translation of a given English sentence is correct. If it is correct, then it will always have the

same truth value as the English sentence, no matter what world the two are evaluated in. So

when you are in doubt about one of your translations, simply build some worlds where the

English sentence is true, others where it is false, and check to see that your translation has

the right truth values in these worlds. You should use this technique frequently in all of the

translation exercises.

Start a new sentence ¬le, and use it to enter translations of the following English sentences

into ¬rst-order logic. You will only need to use the connectives §, ∨, and ¬.

1. Either a is small or both c and d are large.

2. d and e are both in back of b.

3. d and e are both in back of b and larger than it.

4. Both d and c are cubes, however neither of them is small.

5. Neither e nor a is to the right of c and to the left of b.

6. Either e is not large or it is in back of a.

7. c is neither between a and b, nor in front of either of them.

8. Either both a and e are tetrahedra or both a and f are.

9. Neither d nor c is in front of either c or b.

10. c is either between d and f or smaller than both of them.

11. It is not the case that b is in the same row as c.

12. b is in the same column as e, which is in the same row as d, which in turn is in the

same column as a.

Before you submit your sentence ¬le, do the next exercise.

Section 3.7

88 / The Boolean Connectives

3.22 (Checking your translations) Open Wittgenstein™s World. Notice that all of the English sentences

‚ from Exercise 3.21 are true in this world. Thus, if your translations are accurate, they will also

be true in this world. Check to see that they are. If you made any mistakes, go back and ¬x

them. But as we have stressed, even if one of your sentences comes out true in Wittgenstein™s

World, it does not mean that it is a proper translation of the corresponding English sentence.

All you know for sure is that your translation and the original sentence have the same truth

value in this particular world. If the translation is correct, it will have the same truth value as

the English sentence in every world. Thus, to have a better test of your translations, we will

examine them in a number of worlds, to see if they have the same truth values as their English

counterparts in all of these worlds.

Let™s start by making modi¬cations to Wittgenstein™s World. Make all the large or medium

objects small, and the small objects large. With these changes in the world, the English sen-

tences 1, 3, 4, and 10 become false, while the rest remain true. Verify that the same holds for

your translations. If not, correct your translations. Next, rotate your modi¬ed Wittgenstein™s

World 90—¦ clockwise. Now sentences 5, 6, 8, 9, and 11 should be the only true ones that remain.

Let™s check your translations in another world. Open Boole™s World. The only English sen-

tences that are true in this world are sentences 6 and 11. Verify that all of your translations

except 6 and 11 are false. If not, correct your translations.

Now modify Boole™s World by exchanging the positions of b and c. With this change, the

English sentences 2, 5, 6, 7, and 11 come out true, while the rest are false. Check that the same

is true of your translations.

There is nothing to submit except Sentences 3.21.

3.23 Start a new sentence ¬le and translate the following into fol. Use the names and predicates

‚ presented in Table 1.2 on page 30.

1. Max is a student, not a pet.

2. Claire fed Folly at 2 pm and then ten minutes later gave her to Max.

3. Folly belonged to either Max or Claire at 2:05 pm.

4. Neither Max nor Claire fed Folly at 2 pm or at 2:05 pm.

5. 2:00 pm is between 1:55 pm and 2:05 pm.

6. When Max gave Folly to Claire at 2 pm, Folly wasn™t hungry, but she was an hour

later.

3.24 Referring again to Table 1.2, page 30, translate the following into natural, colloquial English.

Turn in your translations to your instructor.

1. Student(claire) § ¬Student(max)

2. Pet(pris) § ¬Owned(max, pris, 2:00)

3. Owned(claire, pris, 2:00) ∨ Owned(claire, folly, 2:00)

4. ¬(Fed(max, pris, 2:00) § Fed(max, folly, 2:00))

Chapter 3

Alternative notation / 89

5. ((Gave(max, pris, claire, 2:00) § Hungry(pris, 2:00)) ∨

(Gave(max, folly, claire, 2:00) § Hungry(folly, 2:00))) §

Angry(claire, 2:05)

3.25 Translate the following into fol, introducing names, predicates, and function symbols as

needed. Explain the meaning of each predicate and function symbol, unless it is completely

obvious.

1. AIDS is less contagious than in¬‚uenza, but more deadly.

2. Abe fooled Stephen on Sunday, but not on Monday.

3. Sean or Brad admires Meryl and Harrison.

4. Daisy is a jolly miller, and lives on the River Dee.

5. Polonius™s eldest child was neither a borrower nor a lender.

Section 3.8

Alternative notation

As we mentioned in Chapter 2, there are various dialect di¬erences among

users of fol. It is important to be aware of these so that you will not be

stymied by super¬cial di¬erences. In fact, you will run into alternate symbols

being used for each of the three connectives studied in this chapter.

The most common variant of the negation sign, ¬, is the symbol known

as the tilde, ∼. Thus you will frequently encounter ∼ P where we would write

¬P. A more old-fashioned alternative is to draw a bar completely across the

negated sentence, as in P. This has one advantage over ¬, in that it allows

you to avoid certain uses of parentheses, since the bar indicates its own scope

by what lies under it. For example, where we have to write ¬(P § Q), the

bar equivalent would simply be P § Q. None of these symbols are available

on all keyboards, a serious problem in some contexts, such as programming

languages. Because of this, many programming languages use an exclamation

point to indicate negation. In the Java programming language, for example,

¬P would be written !P.

There are only two common variants of §. By far the most common is

&, or sometimes (as in Java), &&. An older notation uses a centered dot, as

in multiplication. To make things more confusing still, the dot is sometimes

omitted, again as in multiplication. Thus, for P § Q you might see any of the

following: P&Q, P&&Q, P · Q, or just PQ.

Happily, the symbol ∨ is pretty standard. The only exception you may

encounter is a single or double vertical line, used in programming languages.

So if you see P | Q or P Q, what is meant is probably P ∨ Q. Unfortunately,

Section 3.8

90 / The Boolean Connectives

though, some old textbooks use P | Q to express not both P and Q.

Alternatives to parentheses

There are ways to get around the use of parentheses in fol. At one time, a

common alternative to parentheses was a system known as dot notation. This

dot notation

system involved placing little dots next to connectives indicating their relative

“power” or scope. In this system, the two sentences we write as P ∨ (Q § R)

and (P ∨ Q) § R would have been written P ∨. Q § R and P ∨ Q .§ R, respec-

tively. With more complex sentences, multiple dots were used. Fortunately,

this notation has just about died out, and the present authors never speak to

anyone who uses it.

Another approach to parentheses is known as Polish notation. In Polish

Polish notation

notation, the usual in¬x notation is replaced by pre¬x notation, and this

makes parentheses unnecessary. Thus the distinction between our ¬(P ∨ Q)

and (¬P ∨ Q) would, in pre¬x form, come out as ¬ ∨ PQ and ∨¬PQ, the

order of the connectives indicating which includes the other in its scope.

Besides pre¬x notation, Polish notation uses certain capital letters for

connectives (N for ¬, K for §, and A for ∨), and lower case letters for its atomic

sentences (to distinguish them from connectives). So an actual sentence of the

Polish dialect would look like this:

ApKNqr

Since this expression starts with A, we know right away that it is a disjunction.

What follows must be its two disjuncts, in sequence. So the ¬rst disjunct is p

and the second is KNqr, that is, the conjunction of the negation of q and of r.

So this is the Polish version of

P ∨ (¬Q § R)

Though Polish notation may look hard to read, many of you have already

mastered a version of it. Calculators use two styles for entering formulas. One

is known as algebraic style, the other as RPN style. The RPN stands for

reverse Polish notation

“reverse Polish notation.” If you have a calculator that uses RPN, then to

calculate the value of, say, (7 — 8) + 3 you enter things in this order: 7, 8, —,

3, +. This is just the reverse of the Polish, or pre¬x, ordering.

In order for Polish notation to work without parentheses, the connectives

must all have a ¬xed arity. If we allowed conjunction to take an arbitrary num-

ber of sentences as arguments, rather than requiring exactly two, a sentence

like KpNKqrs would be ambiguous. It could either mean P § ¬(Q § R) § S or

P § ¬(Q § R § S), and these aren™t equivalent.

Chapter 3

Alternative notation / 91

Remember

The following table summarizes the alternative notations discussed so far.

Our notation Common equivalents

¬P ∼ P, P, !P, Np

P§Q P&Q, P&&Q, P · Q, PQ, Kpq

P∨Q P | Q, P Q, Apq

Exercises

3.26 3.27

(Overcoming dialect di¬erences) The (Translating from Polish) Try your hand

‚ ‚

following are all sentences of fol. But at translating the following sentences

they™re in di¬erent dialects. Submit a from Polish notation into our dialect.

sentence ¬le in which you™ve translated Submit the resulting sentence ¬le.

them into our dialect. 1. NKpq

2. KNpq

1. P&Q

3. NAKpqArs

2. !(P (Q&&P))

4. NAKpAqrs

3. (∼ P ∨ Q) · P