<<

. 14
( 107 .)



>>

You try it
................................................................
1. Open Wittgenstein™s World. Start a new sentence ¬le and write the following
sentence.
¬¬¬¬¬Between(e, d, f)

2. Use the Verify button to check the truth value of the sentence.

3. Now play the game, choosing whichever commitment you please. What
happens to the number of negation symbols as the game proceeds? What
happens to your commitment?

4. Now play the game again with the opposite commitment. If you won the
¬rst time, you should lose this time, and vice versa. Don™t feel bad about
losing.

5. There is no need to save the sentence ¬le when you are done.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Congratulations

Remember

1. If P is a sentence of fol, then so is ¬P.

2. The sentence ¬P is true if and only if P is not true.

3. A sentence that is either atomic or the negation of an atomic sentence
is called a literal.




Section 3.1
70 / The Boolean Connectives


Exercises


3.1 If you skipped the You try it section, go back and do it now. There are no ¬les to submit,
but you wouldn™t want to miss it.

3.2 (Assessing negated sentences) Open Boole™s World and Brouwer™s Sentences. In the sentence ¬le
‚ you will ¬nd a list of sentences built up from atomic sentences using only the negation symbol.
Read each sentence and decide whether you think it is true or false. Check your assessment. If
the sentence is false, make it true by adding or deleting a negation sign. When you have made
all the sentences in the ¬le true, submit the modi¬ed ¬le as Sentences 3.2

3.3 (Building a world) Start a new sentence ¬le. Write the following sentences in your ¬le and save
‚ the ¬le as Sentences 3.3.
1. ¬Tet(f)
2. ¬SameCol(c, a)
3. ¬¬SameCol(c, b)
4. ¬Dodec(f)
5. c=b
6. ¬(d = e)
7. ¬SameShape(f, c)
8. ¬¬SameShape(d, c)
9. ¬Cube(e)
10. ¬Tet(c)

Now start a new world ¬le and build a world where all these sentences are true. As you modify
the world to make the later sentences true, make sure that you have not accidentally falsi¬ed
any of the earlier sentences. When you are done, submit both your sentences and your world.

3.4 Let P be a true sentence, and let Q be formed by putting some number of negation symbols
 in front of P. Show that if you put an even number of negation symbols, then Q is true, but
that if you put an odd number, then Q is false. [Hint: A complete proof of this simple fact
would require what is known as “mathematical induction.” If you are familiar with proof by
induction, then go ahead and give a proof. If you are not, just explain as clearly as you can
why this is true.]
Now assume that P is atomic but of unknown truth value, and that Q is formed as before.
No matter how many negation symbols Q has, it will always have the same truth value as a
literal, namely either the literal P or the literal ¬P. Describe a simple procedure for determining
which.




Chapter 3
Conjunction symbol: § / 71



Section 3.2
Conjunction symbol: §
The symbol § is used to express conjunction in our language, the notion we
normally express in English using terms like and, moreover, and but. In ¬rst-
order logic, this connective is always placed between two sentences, whereas in
English we can also conjoin other parts of speech, such as nouns. For example,
the English sentences John and Mary are home and John is home and Mary
is home have the same ¬rst-order translation:
Home(john) § Home(mary)
This sentence is read aloud as “Home John and home Mary.” It is true if and
only if John is home and Mary is home.
In English, we can also conjoin verb phrases, as in the sentence John slipped
and fell. But in fol we must translate this the same way we would translate
John slipped and John fell :
Slipped(john) § Fell(john)
This sentence is true if and only if the atomic sentences Slipped(john) and
Fell(john) are both true.
A lot of times, a sentence of fol will contain § when there is no visible
sign of conjunction in the English sentence at all. How, for example, do you
think we might express the English sentence d is a large cube in fol? If you
guessed
Large(d) § Cube(d)
you were right. This sentence is true if and only if d is large and d is a cube”
that is, if d is a large cube.
Some uses of the English and are not accurately mirrored by the fol
conjunction symbol. For example, suppose we are talking about an evening
when Max and Claire were together. If we were to say Max went home and
Claire went to sleep, our assertion would carry with it a temporal implication,
namely that Max went home before Claire went to sleep. Similarly, if we were to
reverse the order and assert Claire went to sleep and Max went home it would
suggest a very di¬erent sort of situation. By contrast, no such implication,
implicit or explicit, is intended when we use the symbol §. The sentence
WentHome(max) § FellAsleep(claire)
is true in exactly the same circumstances as
FellAsleep(claire) § WentHome(max)



Section 3.2
72 / The Boolean Connectives


Semantics and the game rule for §
Just as with negation, we can put complex sentences as well as simple ones
together with §. A sentence P § Q is true if and only if both P and Q are true.
Thus P § Q is false if either or both of P or Q is false. This can be summarized
by the following truth table.
P Q P§Q
true true true
truth table for §
true false false
false true false
false false false

The Tarski™s World game is more interesting for conjunctions than nega-
tions. The way the game proceeds depends on whether you have committed
game rule for §
to true or to false. If you commit to the truth of P § Q then you have
implicitly committed yourself to the truth of each of P and Q. Thus, Tarski™s
World gets to choose either one of these simpler sentences and hold you to the
truth of it. (Which one will Tarski™s World choose? If one or both of them are
false, it will choose a false one so that it can win the game. If both are true,
it will choose at random, hoping that you will make a mistake later on.)
If you commit to the falsity of P § Q, then you are claiming that at least
one of P or Q is false. In this case, Tarski™s World will ask you to choose one of
the two and thereby explicitly commit to its being false. The one you choose
had better be false, or you will eventually lose the game.

You try it
................................................................
1. Open Claire™s World. Start a new sentence ¬le and enter the sentence

¬Cube(a) § ¬Cube(b) § ¬Cube(c)

2. Notice that this sentence is false in this world, since c is a cube. Play
the game committed (mistakenly) to the truth of the sentence. You will
see that Tarski™s World immediately zeros in on the false conjunct. Your
commitment to the truth of the sentence guarantees that you will lose the
game, but along the way, the reason the sentence is false becomes apparent.
3. Now begin playing the game committed to the falsity of the sentence.
When Tarski™s World asks you to choose a conjunct you think is false,
pick the ¬rst sentence. This is not the false conjunct, but select it anyway
and see what happens after you choose OK.



Chapter 3
Conjunction symbol: § / 73




4. Play until Tarski™s World says that you have lost. Then click on Back a
couple of times, until you are back to where you are asked to choose a
false conjunct. This time pick the false conjunct and resume the play of
the game from that point. This time you will win.

5. Notice that you can lose the game even when your original assessment
is correct, if you make a bad choice along the way. But Tarski™s World
always allows you to back up and make di¬erent choices. If your original
assessment is correct, there will always be a way to win the game. If it
is impossible for you to win the game, then your original assessment was
wrong.

6. Save your sentence ¬le as Sentences Game 1 when you are done.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Congratulations

Remember

1. If P and Q are sentences of fol, then so is P § Q.

2. The sentence P § Q is true if and only if both P and Q are true.



Exercises


3.5 If you skipped the You try it section, go back and do it now. Make sure you follow all the
‚ instructions. Submit the ¬le Sentences Game 1.
3.6 Start a new sentence ¬le and open Wittgenstein™s World. Write the following sentences in the
‚ sentence ¬le.
1. Tet(f) § Small(f)
2. Tet(f) § Large(f)
3. Tet(f) § ¬Small(f)
4. Tet(f) § ¬Large(f)
5. ¬Tet(f) § ¬Small(f)
6. ¬Tet(f) § ¬Large(f)
7. ¬(Tet(f) § Small(f))
8. ¬(Tet(f) § Large(f))




Section 3.2
74 / The Boolean Connectives


9. ¬(¬Tet(f) § ¬Small(f))
10. ¬(¬Tet(f) § ¬Large(f))

Once you have written these sentences, decide which you think are true. Record your eval-
uations, to help you remember. Then go through and use Tarski™s World to evaluate your
assessments. Whenever you are wrong, play the game to see where you went wrong.
If you are never wrong, playing the game will not be very instructive. Play the game a
couple times anyway, just for fun. In particular, try playing the game committed to the falsity
of sentence 9. Since this sentence is true in Wittgenstein™s World, Tarski™s World should be able
to beat you. Make sure you understand everything that happens as the game proceeds.
Next, change the size or shape of block f , predict how this will a¬ect the truth values of
your ten sentences, and see if your prediction is right. What is the maximum number of these
sentences that you can get to be true in a single world? Build a world in which the maximum
number of sentences are true. Submit both your sentence ¬le and your world ¬le, naming them
as usual.

3.7 (Building a world) Open Max™s Sentences. Build a world where all these sentences are true.
‚ You should start with a world with six blocks and make changes to it, trying to make all the
sentences true. Be sure that as you make a later sentence true you do not inadvertently falsify
an earlier sentence.


Section 3.3
Disjunction symbol: ∨
The symbol ∨ is used to express disjunction in our language, the notion we
express in English using or. In ¬rst-order logic, this connective, like the con-
junction sign, is always placed between two sentences, whereas in English we
can also disjoin nouns, verbs, and other parts of speech. For example, the
English sentences John or Mary is home and John is home or Mary is home
both have the same ¬rst-order translation:

Home(john) ∨ Home(mary)

This fol sentence is read “Home John or home Mary.”
Although the English or is sometimes used in an “exclusive” sense, to say
exclusive vs. inclusive
disjunction that exactly one (i.e., one but no more than one) of the two disjoined sentences
is true, the ¬rst-order logic ∨ is always given an “inclusive” interpretation: it
means that at least one and possibly both of the two disjoined sentences is
true. Thus, our sample sentence is true if John is home but Mary is not, if
Mary is home but John is not, or if both John and Mary are home.



Chapter 3
Disjunction symbol: ∨ / 75



<<

. 14
( 107 .)



>>