<<

. 17
( 107 .)



>>

Section 3.7
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

<<

. 17
( 107 .)



>>