+1(978)310-4246 credencewriters@gmail.com
Select Page

1. Translate the following into GPLI:

Everyone apart from Alice likes Sydney and at least one other city.

[Note: regard this proposition as stating nothing about what Alice does, or does not,

like.]

2. For the following proposition, describe

(i) a model on which it is true (and explain

why it is true on this model), and

(ii) a model on which it is false (and explain why it is

false on this model).

If there is no model of one of these types, explain why.

Ã¢Ë†â‚¬

x

Ã¢Ë†â‚¬

y

(

Rxy

Ã¢â€ â€™

(

x

=

y

Ã¢Ë†Â§

P x

Ã¢Ë†Â§

Qy

))

Ã¢Ë†Â§Ã‚Â¬Ã¢Ë†Æ’

x

(

P x

Ã¢Ë†Â§

Qx

)

LOGIC
The Drill
Nicholas J.J. Smith and John Cusbert
Copyright c 2012 by Nicholas Jeremy Josef Smith and John Cusbert
Cover photograph: Alser StraÃƒÅ¸e, Vienna. c Nicholas J.J. Smith
30 May 2012: first published.
29 November 2014: corrections.
16 May 2017: corrections.
Preface
The first part of this volume contains all the exercise questions that appear in Logic: The Laws of Truth by Nicholas J.J. Smith (Princeton University Press, 2012). The second part contains answers to almost all of these
exercises. Both the questions and the answers are a collaborative effort
between Nicholas J.J. Smith and John Cusbert.
One obvious use of this work is as a solutions manual for readers of Logic:
The Laws of TruthÃ¢â‚¬â€but it should also be of use to readers of other logic
books. Students of logic need a large number of worked examples and
exercise problems with solutions: the more the better. This volume should
help to meet that need.
After each question, a cross-reference of the form Ã¢â‚¬Ëœ[A p.x]Ã¢â‚¬â„¢ appears. This
indicates the page on which the answer to that question can be found. You
can click on the cross-reference to be taken directly to the answer. Each
answer then contains a cross-reference of the form Ã¢â‚¬Ëœ[Q p.x]Ã¢â‚¬â„¢ which leads
back to the corresponding question. Other blue items are also links: for
example, clicking on an entry in the Contents pages takes you directly to
the relevant section, and at the end of each exercise set and each answer
set there is a link back to the Contents.
If you find any errorsÃ¢â‚¬â€or have any other comments or suggestionsÃ¢â‚¬â€
logicthedrill@gmail.com
http://njjsmith.com/philosophy/lawsoftruth/
Any significant revisions (e.g. corrections or additions to the exercises or
iii
Contents
Preface
iii
Questions
2
1. Propositions and Arguments
2
Exercises 1.2.1
2
Exercises 1.3.1
3
Exercises 1.4.1
3
Exercises 1.5.1
4
Exercises 1.6.1.1
4
Exercises 1.6.2.1
5
Exercises 1.6.4.1
5
Exercises 1.6.6
6
2. The Language of Propositional Logic
7
Exercises 2.3.3
7
Exercises 2.3.5
8
Exercises 2.3.8
8
iv
Exercises 2.5.1
10
Exercises 2.5.3.1
11
Exercises 2.5.4.1
11
Exercises 2.5.5.1
11
3. Semantics of Propositional Logic
13
Exercises 3.2.1
13
Exercises 3.3.1
14
Exercises 3.4.1
14
Exercises 3.5.1
15
4. Uses of Truth Tables
16
Exercises 4.1.2
16
Exercises 4.2.1
17
Exercises 4.3.1
18
Exercises 4.4.1
18
5. Logical Form
20
Exercises 5.1.1
20
Exercises 5.2.1
20
Exercises 5.3.1
21
Exercises 5.4.1
22
Exercises 5.5.1
23
v
24
Exercises 6.5.1
24
Exercises 6.6.3
25
7. Trees for Propositional Logic
27
Exercises 7.2.1.1
27
Exercises 7.2.2.1
27
Exercises 7.2.3.1
28
Exercises 7.3.1.1
28
Exercises 7.3.2.1
29
Exercises 7.3.3.1
30
Exercises 7.3.4.1
30
Exercises 7.3.5.1
31
8. The Language of Monadic Predicate Logic
32
Exercises 8.2.1
32
Exercises 8.3.2
33
Exercises 8.3.5
34
Exercises 8.4.3.1
35
Exercises 8.4.5.1
36
9. Semantics of Monadic Predicate Logic
38
Exercises 9.1.1
38
Exercises 9.2.1
39
vi
Exercises 9.3.1
39
Exercises 9.4.3
40
Exercises 9.5.1
43
10. Trees for Monadic Predicate Logic
44
Exercises 10.2.2
44
Exercises 10.3.8
45
11. Models, Propositions, and Ways the World Could Be
47
12. General Predicate Logic
48
Exercises 12.1.3.1
48
Exercises 12.1.6
49
Exercises 12.1.9
50
Exercises 12.2.2
52
Exercises 12.3.1
54
Exercises 12.4.1
57
Exercises 12.5.4
57
13. Identity
58
Exercises 13.2.2
58
Exercises 13.3.1
60
Exercises 13.4.3
61
Exercises 13.5.1
63
vii
Exercises 13.6.1.1
64
Exercises 13.6.2.1
65
Exercises 13.6.3.1
66
Exercises 13.7.4
66
14. Metatheory
70
Exercises 14.1.1.1
70
Exercises 14.1.2.1
71
Exercises 14.1.3.1
71
15. Other Methods of Proof
72
Exercises 15.1.5
72
Exercises 15.2.3
74
Exercises 15.3.3
75
16. Set Theory
76
78
1. Propositions and Arguments
78
78
78
79
79
viii
80
80
80
81
2. The Language of Propositional Logic
84
84
84
85
87
89
90
90
3. Semantics of Propositional Logic
92
92
93
95
98
4. Uses of Truth Tables
99
99
102
105
ix
109
5. Logical Form
112
112
113
114
116
117
118
118
128
7. Trees for Propositional Logic
134
134
135
136
137
141
144
148
151
8. The Language of Monadic Predicate Logic
156
x
156
158
159
161
163
9. Semantics of Monadic Predicate Logic
165
165
165
166
167
171
10. Trees for Monadic Predicate Logic
172
172
180
11. Models, Propositions, and Ways the World Could Be
190
12. General Predicate Logic
191
191
192
193
196
xi
200
217
220
13. Identity
221
221
223
226
244
258
259
260
261
14. Metatheory
265
265
265
267
15. Other Methods of Proof
269
269
284
303
xii
16. Set Theory
304
xiii
Questions
1
Chapter 1
Propositions and Arguments
Exercises 1.2.1
Classify the following as propositions or nonpropositions.
1. Los Angeles is a long way from New York.
[A p.78]
2. LetÃ¢â‚¬â„¢s go to Los Angeles!
[A p.78]
3. Los Angeles, whoopee!
[A p.78]
4. Would that Los Angeles were not so far away.
[A p.78]
5. I really wish Los Angeles were nearer to New York.
[A p.78]
6. I think we should go to Los Angeles.
[A p.78]
7. I hate Los Angeles.
[A p.78]
8. Los Angeles is great!
[A p.78]
9. If only Los Angeles were closer.
[A p.78]
10. Go to Los Angeles!
[A p.78]
[Contents]
2
Exercises 1.3.1
Represent the following lines of reasoning as arguments.
1. If the stock market crashes, thousands of experienced investors will
lose a lot of money. So the stock market wonÃ¢â‚¬â„¢t crash.
[A p.78]
2. Diamond is harder than topaz, topaz is harder than quartz, quartz is
harder than calcite, and calcite is harder than talc, therefore diamond
is harder than talc.
[A p.79]
3. Any friend of yours is a friend of mine; and youÃ¢â‚¬â„¢re friends with everyone on the volleyball team. Hence, if SallyÃ¢â‚¬â„¢s on the volleyball
team, sheÃ¢â‚¬â„¢s a friend of mine.
[A p.79]
4. When a politician engages in shady business dealings, it ends up on
page one of the newspapers. No South Australian senator has ever
appeared on page one of a newspaper. Thus, no South Australian
[A p.79]
[Contents]
Exercises 1.4.1
State whether each of the following arguments is valid or invalid.
1.
All dogs are mammals.
All mammals are animals.
All dogs are animals.
2.
[A p.79]
All dogs are mammals.
All dogs are animals.
All mammals are animals.
3.
[A p.79]
All dogs are mammals.
No fish are mammals.
No fish are dogs.
[A p.79]
3
4.
All fish are mammals.
All mammals are robots.
All fish are robots.
[A p.79]
[Contents]
Exercises 1.5.1
1. Which of the arguments in Exercise 1.4.1 are sound?
[A p.79]
2. Find an argument in Exercise 1.4.1 that has all true premises and a
true conclusion but is not valid and hence not sound.
[A p.79]
3. Find an argument in Exercise 1.4.1 that has false premises and a false
conclusion but is valid.
[A p.79]
[Contents]
Exercises 1.6.1.1
1. What is the negand of:
(i) Bob is not a good student
[A p.80]
(ii) I havenÃ¢â‚¬â„¢t decided not to go to the party.
[A p.80]
(iii) Mars isnÃ¢â‚¬â„¢t the closest planet to the sun.
[A p.80]
(iv) It is not the case that Alice is late.
[A p.80]
(v) I donÃ¢â‚¬â„¢t like scrambled eggs.
[A p.80]
(vi) Scrambled eggs arenÃ¢â‚¬â„¢t good for you.
[A p.80]
2. If a proposition is true, its double negation is. . . ?
[A p.80]
3. If a propositionÃ¢â‚¬â„¢s double negation is false, the proposition is. . . ?
[A p.80]
[Contents]
4
Exercises 1.6.2.1
What are the conjuncts of the following propositions?
1. The sun is shining, and I am happy.
[A p.80]
2. Maisie and Rosie are my friends.
[A p.80]
3. Sailing is fun, and snowboarding is too.
[A p.80]
4. We watched the movie and ate popcorn.
[A p.80]
5. Sue does not want the red bicycle, and she does not like the blue one.
[A p.80]
6. The road to the campsite is long and uneven.
[A p.80]
[Contents]
Exercises 1.6.4.1
What are the (a) antecedents and (b) consequents of the following propositions?
1. If thatÃ¢â‚¬â„¢s pistachio ice cream, it doesnÃ¢â‚¬â„¢t taste the way it should.
[A p.80]
2. That tastes the way it should only if it isnÃ¢â‚¬â„¢t pistachio ice cream.
[A p.80]
3. If that is supposed to taste that way, then it isnÃ¢â‚¬â„¢t pistachio ice cream.
[A p.81]
4. If you pressed the red button, then your cup contains coffee.
[A p.81]
5. Your cup does not contain coffee if you pressed the green button.
[A p.81]
6. Your cup contains hot chocolate only if you pressed the green button.
[A p.81]
[Contents]
5
Exercises 1.6.6
State what sort of compound proposition each of the following is, and
identify its components. Do the same for the components.
1. If it is sunny and windy tomorrow, we shall go sailing or kite flying.
[A p.81]
2. If it rains or snows tomorrow, we shall not go sailing or kite flying.
[A p.81]
3. Either heÃ¢â‚¬â„¢ll stay here and weÃ¢â‚¬â„¢ll come back and collect him later, or
heÃ¢â‚¬â„¢ll come with us and weÃ¢â‚¬â„¢ll all come back together.
[A p.81]
4. Jane is a talented painter and a wonderful sculptor, and if she remains interested in art, her work will one day be of the highest quality.
[A p.81]
5. ItÃ¢â‚¬â„¢s not the case that the unemployment rate will both increase and
decrease in the next quarter.
[A p.82]
6. Your sunburn will get worse and become painful if you donÃ¢â‚¬â„¢t stop
swimming during the daytime.
[A p.82]
7. Either Steven wonÃ¢â‚¬â„¢t get the job, or IÃ¢â‚¬â„¢ll leave and all my clients will
leave.
[A p.82]
8. The Tigers will not lose if and only if both Thompson and Thomson
get injured.
[A p.82]
9. Fido will wag his tail if you give him dinner at 6 this evening, and if
you donÃ¢â‚¬â„¢t, then he will bark.
[A p.82]
10. It will rain or snow todayÃ¢â‚¬â€or else it wonÃ¢â‚¬â„¢t.
[A p.83]
[Contents]
6
Chapter 2
The Language of Propositional
Logic
Exercises 2.3.3
Using the glossary:
A: Aristotle was a philosopher
B: Paper burns
F: Fire is hot
translate the following from PL into English.
1. Ã‚Â¬ A
[A p.84]
2. ( A ^ B)
[A p.84]
3. ( A ^ Ã‚Â¬ B)
[A p.84]
4. (Ã‚Â¬ F ^ Ã‚Â¬ B)
[A p.84]
5. Ã‚Â¬( F ^ B)
[A p.84]
[Contents]
7
Exercises 2.3.5
Using the glossary of Exercise 2.3.3, translate the following from PL into
English.
1. (( A ^ B) _ F )
[A p.84]
2. (Ã‚Â¬ A _ Ã‚Â¬ B)
[A p.84]
3. (( A _ B) ^ Ã‚Â¬( A ^ B))
[A p.84]
4. Ã‚Â¬( A _ F )
[A p.84]
5. ( A ^ ( B _ F ))
[A p.85]
[Contents]
Exercises 2.3.8
1. Using the glossary:
B: The sky is blue
G: Grass is green
R: Roses are red
W: Snow is white
Y: Bananas are yellow
translate the following from PL into English.
(i) (W ! B)
[A p.85]
(ii) (W \$ (W ^ Ã‚Â¬ R))
[A p.85]
(iv) (( R _ W ) ! ( R ^ Ã‚Â¬W ))
[A p.85]
(vi) ( G _ (W ! R))
[A p.85]
(iii) Ã‚Â¬( R ! Ã‚Â¬W )
[A p.85]
(v) ((W ^ W ) _ ( R ^ Ã‚Â¬ B))
[A p.85]
(vii) ((Y \$ Y ) ^ (Ã‚Â¬Y \$ Ã‚Â¬Y ))
[A p.85]
(viii) (( B ! W ) ! (Ã‚Â¬W ! Ã‚Â¬ B))
(ix) ((( R ^ W ) ^ B) ! (Y _ G ))
8
[A p.85]
[A p.85]
(x) Ã‚Â¬(Ã‚Â¬ R ^ (Ã‚Â¬W _ G ))
[A p.85]
2. Translate the following from English into PL.
(i) Only if the sky is blue is snow white.
[A p.86]
(ii) The sky is blue if, and only if, snow is white and roses are
not red.
[A p.86]
(iii) ItÃ¢â‚¬â„¢s not true that if roses are red, then snow is not white.
[A p.86]
(iv) If snow and roses are red, then roses are red and/or snow isnÃ¢â‚¬â„¢t.
[A p.86]
(v) Jim is tall if and only if Maisy is, and Maisy is tall only if Nora
is not.
[A p.86]
(vi) Jim is tall only if Nora or Maisy is.
[A p.86]
(vii) If Jim is tall, then either Maisy is tall or Nora isnÃ¢â‚¬â„¢t.
[A p.86]
(viii) Either snow is white and Maisy is tall, or snow is white and she
isnÃ¢â‚¬â„¢t.
[A p.86]
(ix) If Jim is tall and Jim is not tall, then the sky both is and is not
blue.
[A p.86]
(x) If Maisy is tall and the sky is blue, then Jim is tall and the sky is
not blue.
[A p.86]
3. Translate the following from English into PL.
(i) If it is snowing, we are not kite flying.
[A p.87]
(ii) If it is sunny and it is windy, then we are sailing or kite flying.
[A p.87]
(iii) Only if it is windy are we kite flying, and only if it is windy are
we sailing.
[A p.87]
(iv) We are sailing or kite flyingÃ¢â‚¬â€or skiing.
[A p.87]
(v) IfÃ¢â‚¬â€and only ifÃ¢â‚¬â€it is windy, we are sailing.
[A p.87]
(vi) We are skiing only if it is windy or snowing.
[A p.87]
(vii) We are skiing only if it is both windy and snowing.
[A p.87]
(viii) If it is sunny, then if it is windy, we are kite flying.
[A p.87]
(ix) We are sailing only if it is sunny, windy, and not snowing.
[A p.87]
9
(x) If it is sunny and windy, weÃ¢â‚¬â„¢re sailing, and if it is snowing and
not windy, weÃ¢â‚¬â„¢re skiing.
[A p.87]
[Contents]
Exercises 2.5.1
1. State whether each of the following is a wff of PL.
(i) (( A ! B))
[A p.87]
(ii) ( A !! B)
[A p.87]
(iv) A ! (( A ! A))
[A p.87]
(vi) ( A _ ( A _ ( A _ ( A _ ( A _ ( A _ ( A _ A))))))
[A p.87]
(iii) ( A ! ( A ! A))
[A p.87]
(v) (( A ^ B)^) A
[A p.87]
(vii) (( AA _ ^ BC ))
[A p.87]
(viii) (( A _ A) ^ BC ))
[A p.87]
(ix) ABC
[A p.87]
(x) (( A _ A) ^ (( A _ A) ^ (( A _ A) ^ A)))
[A p.87]
2. Give recursive definitions of the following.
(i) The set of all odd numbers.
[A p.88]
(ii) The set of all numbers divisible by five.
[A p.88]
(iii) The set of all Ã¢â‚¬Å“wordsÃ¢â‚¬Â (finite strings of letters) that use only (but
not necessarily both of) the letters a and b.
[A p.88]
(iv) The set containing all of BobÃ¢â‚¬â„¢s ancestors.
[A p.88]
(v) The set of all cackles: hah hah hah, hah hah hah hah, hah hah
hah hah hah, and so on.
[A p.88]
[Contents]
10
Exercises 2.5.3.1
Write out a construction for each of the following wffs, and state the main
connective.
1. (Ã‚Â¬ P _ ( Q ^ R))
[A p.89]
2. Ã‚Â¬( P ^ ( Q _ R))
[A p.89]
3. ((Ã‚Â¬ P ^ Ã‚Â¬ Q) _ Ã‚Â¬ R)
[A p.89]
4. (( P ! Q) _ ( R ! S))
[A p.89]
5. ((( P \$ Q) \$ R) \$ S)
[A p.89]
6. ((Ã‚Â¬ P ^ Ã‚Â¬Ã‚Â¬ P) ! ( P ^ Ã‚Â¬ P))
[A p.90]
[Contents]
Exercises 2.5.4.1
1. For each of the remaining orderings (2Ã¢â‚¬â€œ6) of the connectives !, ^,
and _ given in Ã‚Â§2.5.4, state which disambiguation (1Ã¢â‚¬â€œ5) results from
restoring parentheses to our original expression in this order.
[A p.90]
[Contents]
Exercises 2.5.5.1
1. Write the following in the notation of this book:
(i) _ Ã‚Â¬ P ^ QR
[A p.90]
(iii) ^ Ã‚Â¬ _ PQR
[A p.90]
(ii) Ã‚Â¬ ^ _ PQR
[A p.90]
(iv) _ ^ Ã‚Â¬ PÃ‚Â¬ QÃ‚Â¬ R
[A p.90]
(v) \$\$\$ PQRS
[A p.90]
2. Write the following in Polish notation:
(i) Ã‚Â¬( P ^ ( Q _ R))
[A p.91]
11
(ii) ([ P ! ( Q _ R)] ! S)
[A p.91]
(iv) ( P ! [( Q _ R) ! S])
[A p.91]
(iii) [( P ! Q) _ ( R ! S)]
[A p.91]
(v) [(Ã‚Â¬ P ^ Ã‚Â¬Ã‚Â¬ P) ! ( P ^ Ã‚Â¬ P)]
12
[A p.91]
[Contents]
Chapter 3
Semantics of Propositional Logic
Exercises 3.2.1
Determine the truth values of the following wffs, given the truth values
for their basic components, which are written under those components.
1.
(Ã‚Â¬ P ^ ( Q _ R))
T
T
F
[A p.92]
2.
Ã‚Â¬ ( P _ ( Q ! R))
T
T
F
[A p.92]
3.
(Ã‚Â¬ Ã‚Â¬ P ^ ( Q ! ( R _ P)))
F
T
T
F
[A p.92]
4.
(Ã‚Â¬ Ã‚Â¬ P ^ ( Q ! ( R _ P)))
T
F
F
T
[A p.92]
5.
(( P _ Q) ! ( P _ P))
F
T
F
F
[A p.92]
6.
(( P _ Q) ! ( P _ P))
T
F
T
T
[A p.93]
7.
( P ! ( Q ! ( R ! S)))
T
T
T
F
[A p.93]
8.
( P ! ( Q ! ( R ! S)))
F
T
F
T
[A p.93]
9.
Ã‚Â¬ (((Ã‚Â¬ P \$ P) \$ Q) ! R)
F
F
F
F
[A p.93]
13
10.
Ã‚Â¬ (((Ã‚Â¬ P \$ P) \$ Q) ! R)
T
T
T
T
[A p.93]
[Contents]
Exercises 3.3.1
Draw up truth tables for the following propositions.
1. (( P ^ Q) _ P)
[A p.93]
2. ( P ^ ( P _ P))
[A p.94]
3. Ã‚Â¬(Ã‚Â¬ P ^ Ã‚Â¬ Q)
[A p.94]
4. ( Q ! ( Q ^ Ã‚Â¬ Q))
[A p.94]
5. ( P ! ( Q ! R))
[A p.94]
6. (( P _ Q) \$ ( P ^ Q))
[A p.94]
7. Ã‚Â¬(( P ^ Q) \$ Q)
[A p.94]
8. ((( P ! Ã‚Â¬ P) ! Ã‚Â¬ P) ! Ã‚Â¬ P)
[A p.94]
9. Ã‚Â¬( P ^ ( Q ^ R))
[A p.95]
10. ((Ã‚Â¬ R _ S) ^ (S _ Ã‚Â¬ T ))
[A p.95]
[Contents]
Exercises 3.4.1
Draw up a joint truth table for each of the following groups of propositions.
1. ( P ! Q) and ( Q ! P)
[A p.95]
2. Ã‚Â¬( P \$ Q) and (( P _ Q) ^ Ã‚Â¬( P ^ Q))
[A p.95]
3. Ã‚Â¬( P ^ Ã‚Â¬ Q) and Ã‚Â¬ Q
[A p.95]
4. (( P ! Q) ^ R) and ( P _ ( Q _ R))
[A p.96]
5. (( P ^ Q) ^ (Ã‚Â¬ R ^ Ã‚Â¬S)) and (( P _ ( R ! Q)) ^ S)
[A p.96]
14
6. ( P ^ Ã‚Â¬ P) and ( Q ^ Ã‚Â¬ Q)
[A p.96]
7. ( P _ ( Q \$ R)) and (( Q ! P) ^ Q)
[A p.96]
8. Ã‚Â¬(( P ^ Q) ^ R) and (( P ! Q) \$ ( P ! R))
[A p.97]
9. ( P _ Q), Ã‚Â¬ P and ( Q _ Q)
[A p.97]
10. ( P ! ( Q ! ( R ! S))) and Ã‚Â¬S
[A p.97]
[Contents]
Exercises 3.5.1
1. Can the meaning of any of our two-place connectives (^, _, !, \$)
be specified as the truth function f 22 defined in Figure 3.2? [A p.98]
2. Define truth functions f 42 and f 52 such that the meanings of ^ and !
(respectively) can be specified as these truth functions.
[A p.98]
3. Suppose we introduce a new one-place connective ? and specify its
meaning as the truth function f 11 defined in Figure 3.2. What is the
truth value of ? A when A is T?
[A p.98]
4. What truth values do you need to know to determine the truth value
of ?( A ! B)?
(i) The truth values of A and B.
(ii) The truth value of A but not of B.
(iii) The truth value of B but not of A.
(iv) None.
[A p.98]
5. Which of our connectives could have its meaning specified as the
two-place function g( x, y) defined as follows?
g( x, y) = f 32 ( f 21 ( x ), y)
[A p.98]
[Contents]
15
Chapter 4
Uses of Truth Tables
Exercises 4.1.2
Use truth tables to determine whether each of the following arguments is
valid. For any argument that is not valid, give a counterexample.
1. A _ B
A!C
) (B ! C) ! C
[A p.99]
2. Ã‚Â¬ A
) Ã‚Â¬(( A ! B) ^ ( B ! C )) _ C
3. ( A ^ Ã‚Â¬ B) ! C
Ã‚Â¬C
B
) Ã‚Â¬A
[A p.99]
[A p.100]
4. ( A ^ B) \$ C
A
) C!B
[A p.100]
5. (Ã‚Â¬ A ^ Ã‚Â¬ B) \$ Ã‚Â¬C
Ã‚Â¬( A _ B)
) C ! Ã‚Â¬C
[A p.100]
6. A _ B
Ã‚Â¬A _ C
B!C
) C
[A p.101]
16
7. Ã‚Â¬( A _ B) \$ Ã‚Â¬C
Ã‚Â¬ A ^ Ã‚Â¬B
) C ^ Ã‚Â¬C
[A p.101]
8. Ã‚Â¬( A ^ B) ! (C _ A)
Ã‚Â¬ A _ Ã‚Â¬B
A
) Ã‚Â¬(C _ Ã‚Â¬C )
[A p.101]
9. A ! ( B ^ C )
B \$ Ã‚Â¬C
) Ã‚Â¬A
[A p.102]
10. A ! B
B!C
Ã‚Â¬C
) Ã‚Â¬A
[A p.102]
[Contents]
Exercises 4.2.1
Write out truth tables for the following propositions, and state whether
each is a tautology, a contradiction, or neither.
1. (( P _ Q) ! P)
[A p.102]
2. (Ã‚Â¬ P ^ ( Q _ R))
[A p.103]
3. ((Ã‚Â¬ P _ Q) \$ ( P ^ Ã‚Â¬ Q))
[A p.103]
4. ( P ! ( Q ! ( R ! P)))
[A p.103]
5. ( P ! (( P ! Q) ! Q))
[A p.103]
6. ( P ! (( Q ! P) ! Q))
[A p.104]
7. (( P ! Q) _ Ã‚Â¬( Q ^ Ã‚Â¬ Q))
[A p.104]
8. (( P ! Q) _ Ã‚Â¬( Q ^ Ã‚Â¬ P))
[A p.104]
9. (( P ^ Q) \$ ( Q \$ P))
[A p.104]
10. Ã‚Â¬(( P ^ Q) ! ( Q \$ P))
[A p.104]
[Contents]
17
Exercises 4.3.1
Write out joint truth tables for the following pairs of propositions, and
state in each case whether the two propositions are (a) jointly satisfiable,
(b) equivalent, (c) contradictory, (d) contraries.
1. ( P ! Q) and Ã‚Â¬( P ^ Ã‚Â¬ Q)
[A p.105]
2. ( P ^ Q) and ( P ^ Ã‚Â¬ Q)
[A p.105]
3. Ã‚Â¬( P \$ Q) and Ã‚Â¬( P ! Q) _ Ã‚Â¬( P _ Ã‚Â¬ Q)
[A p.105]
4. ( P ! ( Q ! R)) and (( P ! Q) ! R)
[A p.106]
5. ( P ^ ( Q ^ Ã‚Â¬ Q)) and Ã‚Â¬( Q ! Ã‚Â¬( R ^ Ã‚Â¬ Q))
[A p.106]
6. ( P ^ Ã‚Â¬ P) and ( R _ Ã‚Â¬ R)
[A p.107]
7. ( P ^ Ã‚Â¬ P) and Ã‚Â¬( Q ! Q)
[A p.107]
8. (( P ! Q) ! R) and Ã‚Â¬( P _ Ã‚Â¬( Q ^ Ã‚Â¬ R))
[A p.108]
9. ( P \$ Q) and (( P ^ Q) _ (Ã‚Â¬ P ^ Ã‚Â¬ Q))
[A p.108]
10. ( P \$ Q) and (( P ^ Q) _ (Ã‚Â¬ P ^ Ã‚Â¬ Q))
[A p.109]
[Contents]
Exercises 4.4.1
Write out a joint truth table for the propositions in each of the following
sets, and state whether each set is satisfiable.
1. {( P _ Q), Ã‚Â¬( P ^ Q), P}
[A p.109]
2. {Ã‚Â¬( P ! Q), ( P \$ Q), (Ã‚Â¬ P _ Q)}
[A p.109]
3. {( P ! Ã‚Â¬ P), ( P _ Ã‚Â¬ P), (Ã‚Â¬ P ! P)}
[A p.109]
4. {(( P _ Q) _ R), (Ã‚Â¬ P ! Ã‚Â¬ Q), (Ã‚Â¬ Q ! Ã‚Â¬ R), Ã‚Â¬ P}
[A p.110]
5. {( P \$ Q), ( Q _ R), ( R ! P)}
[A p.110]
6. {(Ã‚Â¬ P ! Ã‚Â¬ Q), ( P \$ Q), P}
[A p.110]
7. {Ã‚Â¬ P, ( P ! ( P ! P)), (Ã‚Â¬ P \$ P)}
[A p.110]
18
8. {( P _ Ã‚Â¬ Q), ( P ! R), Ã‚Â¬ R, (Ã‚Â¬ R ! Q)}
[A p.111]
9. {Ã‚Â¬ R, Ã‚Â¬ P, (( Q ! Ã‚Â¬ Q) ! R)}
[A p.111]
10. {(Ã‚Â¬ P _ Ã‚Â¬ Q), Ã‚Â¬( P ^ Ã‚Â¬ Q), ( P _ Ã‚Â¬ Q), Ã‚Â¬(Ã‚Â¬ P ^ Ã‚Â¬ Q)}
[A p.111]
[Contents]
19
Chapter 5
Logical Form
Exercises 5.1.1
For each of the following propositions, give three correct answers to the
question Ã¢â‚¬Å“what is the form of this proposition?Ã¢â‚¬Â
1. Ã‚Â¬( R ! ( R ! Q))
[A p.112]
2. ( R _ P) ! ( R _ P)
[A p.112]
3. P ^ (Ã‚Â¬ P ! Q)
[A p.112]
4. ((Ã‚Â¬ P _ Q) ^ P) \$ R
[A p.112]
[Contents]
Exercises 5.2.1
1. The following propositions all have three logical forms in common.
State what the three forms are, and in each case, show what replacements of variables by propositions are required to obtain the three
propositions from the form.
(i) Ã‚Â¬Ã‚Â¬C
(ii) Ã‚Â¬Ã‚Â¬( A ^ B)
(iii) Ã‚Â¬Ã‚Â¬(C ^ Ã‚Â¬ D )
[A p.113]
20
2. State whether the given propositions are instances of the given form.
If so, show what replacements of variables by propositions are required to obtain the proposition from the form.
(i) Form: Ã‚Â¬(a ! b)
Propositions:
(a) Ã‚Â¬( P ! Q)
(b) Ã‚Â¬( R ! Q)
(c) Ã‚Â¬( R ! ( R ! Q))
[A p.113]
[A p.113]
[A p.113]
(a) Ã‚Â¬( P ! ( P ! Q))
(b) Ã‚Â¬( P ! ( P ! P))
(c) Ã‚Â¬( P ! ( Q ! P))
[A p.113]
[A p.113]
[A p.113]
(a) (Ã‚Â¬ P _ Q) ! (Ã‚Â¬ P ^ Q)
(b) ( P _ Ã‚Â¬ P) ! ( P ^ Ã‚Â¬ P)
(c) Ã‚Â¬( R _ S) ! Ã‚Â¬( R ^ S)
[A p.113]
[A p.113]
[A p.113]
(a) ( P _ Q) _ ( Q _ ( P _ Q))
(b) Q _ (Ã‚Â¬ Q _ ( Q ^ Q))
(c) Ã‚Â¬ P _ (Ã‚Â¬Ã‚Â¬ P _ Ã‚Â¬ P)
[A p.113]
[A p.113]
[A p.113]
(ii) Form: Ã‚Â¬(a ! (a ! b))
Propositions:
(iii) Form: (a _ b) ! (a ^ b)
Propositions:
(iv) Form: a _ (Ã‚Â¬ b _ a)
Propositions:
[Contents]
Exercises 5.3.1
For each of the following arguments, give four correct answers to the question Ã¢â‚¬Å“what is the form of this argument?Ã¢â‚¬Â For each form, show what replacements of variables by propositions are required to obtain the argument from the form.
1. Ã‚Â¬( R ! ( R ! Q))
) R _ ( R ! Q)
[A p.114]
21
2. ( P ^ Q) ! Q
Ã‚Â¬Q
) Ã‚Â¬( P ^ Q)
[A p.114]
3. Ã‚Â¬ Q ! ( R ! S)
Ã‚Â¬Q
) R!S
[A p.115]
4. ( P ! Ã‚Â¬ Q) _ (Ã‚Â¬ Q ! P)
Ã‚Â¬(Ã‚Â¬ Q ! P)
) P ! Ã‚Â¬Q
[A p.115]
[Contents]
Exercises 5.4.1
For each of the following arguments, (i) show that it is an instance of the
form:
a
a!b
) b
by stating what substitutions of propositions for variables have to be made
to otbain the argument from the form, and (ii) show by producing a truth
table for the argument that it is valid.
1. P
P!Q
) Q
[A p.116]
2. ( A ^ B)
( A ^ B) ! ( B _ C )
) (B _ C)
[A p.116]
3. ( A _ Ã‚Â¬ A)
( A _ Ã‚Â¬ A) ! ( A ^ Ã‚Â¬ A)
) ( A ^ Ã‚Â¬ A)
[A p.116]
4. ( P ! Ã‚Â¬ P)
( P ! Ã‚Â¬ P) ! ( P ! ( Q ^ Ã‚Â¬ R))
) ( P ! ( Q ^ Ã‚Â¬ R))
[A p.116]
[Contents]
22
Exercises 5.5.1
1.
(i) Show by producing a truth table for the following argument
form that it is invalid:
a
) b
[A p.117]
(ii) Give an instance of the above argument form that is valid; show
that it is valid by producing a truth table for the argument.
[A p.117]
2. While it is not true in general that every instance of an invalid argument form is an invalid argument, there are some invalid argument
forms whose instances are always invalid arguments. Give an example of such an argument form.
[A p.117]
[Contents]
23
Chapter 6
Connectives: Translation and
Exercises 6.5.1
Translate the following arguments into PL and then assess them for validity (you may use shortcuts in your truth tables).
1. Bob is happy if and only if it is raining. Either it is raining or the sun
is shining. So Bob is happy only if the sun is not shining. [A p.118]
2. If I have neither money nor a card, I shall walk. If I walk, I shall get
tired or have a rest. So if I have a rest, I have money.
[A p.119]
3. Maisy is upset only if there is thunder. If there is thunder, then there
is lightning. Therefore, either Maisy is not upset, or there is lightning.
[A p.121]
4. The car started only if you turned the key and pressed the accelerator. If you turned the key but did not press the accelerator, then the
car did not start. The car did not startÃ¢â‚¬â€so either you pressed the accelerator but did not turn the key, or you neither turned the key nor
pressed the accelerator.
[A p.122]
5. Either Maisy isnÃ¢â‚¬â„¢t barking, or there is a robber outside. If there is a
robber outside and Maisy is not barking, then she is either asleep or
depressed. Maisy is neither asleep nor depressed. Hence Maisy is
barking if and only if there is a robber outside.
[A p.123]
24
6. If it isnÃ¢â‚¬â„¢t sunny, then either it is too windy or we are sailing. We are
having fun if we are sailing. It is not sunny and it isnÃ¢â‚¬â„¢t too windy
eitherÃ¢â‚¬â€hence we are having fun.
[A p.124]
7. Either you came through Singleton and Maitland, or you came through
Newcastle. You didnÃ¢â‚¬â„¢t come through either Singleton or MaitlandÃ¢â‚¬â€
you came through Cessnock. Therefore, you came through both
Newcastle and Cessnock.
[A p.125]
8. We shall have lobster for lunch, provided that the shop is open. Either the shop will be open, or it is Sunday. If it is Sunday, we shall go
to a restaurant and have lobster for lunch. So we shall have lobster
for lunch.
[A p.126]
9. Catch Billy a fish, and you will feed him for a day. Teach him to fish,
and youÃ¢â‚¬â„¢ll feed him for life. So either you wonÃ¢â‚¬â„¢t feed Billy for life, or
you will teach him to fish.
[A p.127]
10. IÃ¢â‚¬â„¢ll be happy if the Tigers win. Moreover, they will winÃ¢â‚¬â€or else they
wonÃ¢â‚¬â„¢t. However, assuming they donÃ¢â‚¬â„¢t, it will be a draw. Therefore,
if itÃ¢â‚¬â„¢s not a draw, and they donÃ¢â‚¬â„¢t win, IÃ¢â‚¬â„¢ll be happy.
[A p.128]
[Contents]
Exercises 6.6.3
1. State whether each of the following is a functionally complete set of
(i) {!, Ã‚Â¬}
[A p.128]
(ii) {\$, Y}
[A p.129]
(iv) {!, ^}
[A p.130]
(vi) {_, Ã¢â€°Â 4 }
[A p.131]
(iii) {Ã¢â€°Â 15 } (The connective Ã¢â€°Â 15 is often symbolized by #;
another common symbol for this connective is NOR.) [A p.130]
(v) {Ã‚Â¬, Ã¢â€°Â 12 }
[A p.131]
2. Give the truth table for each of the following propositions.
(i) B Ã¢â€°Â 14 A
[A p.131]
25
(ii) ( A Ã¢â€°Â 11 B) Ã¢â€°Â 15 B
[A p.131]
(iii) Ã‚Â¬( A _ ( A Ã¢â€°Â 6 B))
[A p.131]
(iv) A \$ ( A Ã¢â€°Â 3 Ã‚Â¬ B)
[A p.131]
(v) ( A Ã¢â€°Â 12 B) Y ( B Ã¢â€°Â 12 A)
[A p.132]
(vi) ( A Ã¢â€°Â 12 B) Y ( B Ã¢â€°Â 16 A)
[A p.132]
3. Consider the three-place connectives ] and , whose truth tables are
as follows:
a b
T T
T T
T F
T F
F T
F T
F F
F F
g
T
F
T
F
T
F
T
F
](a, b, g)
T
F
T
T
T
F
T
T
(a, b, g)
F
F
T
T
T
T
F
F
(i) Define ] using only (but not necessarily all of) the connectives
_, ^, and Ã‚Â¬.
[A p.132]
(ii) Do the same for .
[A p.132]
4. State a proposition involving only the connectives Ã‚Â¬ and ^ that is
equivalent to the given proposition.
(i) Ã‚Â¬( A ! B)
[A p.132]
(ii) Ã‚Â¬( A _ B)
[A p.132]
(iv) Ã‚Â¬(Ã‚Â¬ A _ B)
[A p.132]
(vi) ( A ! B) _ ( B ! A)
[A p.132]
(iii) Ã‚Â¬ A _ Ã‚Â¬ B
5.
[A p.132]
(v) A \$ B
[A p.132]
(i) What is the dual of Ã‚Â¨1 ?
[A p.132]
(ii) What is the dual of !?
[A p.133]
(iii) Which one-place connectives are their own duals?
[A p.133]
(iv) Which two-place connectives are their own duals?
[A p.133]
[Contents]
26
Chapter 7
Trees for Propositional Logic
Exercises 7.2.1.1
Apply the appropriate tree rule to each of the following propositions.
1. (Ã‚Â¬ A _ Ã‚Â¬ B)
[A p.134]
2. (Ã‚Â¬ A ! B)
[A p.134]
3. (( A ! B) ^ B)
[A p.134]
4. (( A \$ B) \$ B)
[A p.134]
5. Ã‚Â¬( A \$ Ã‚Â¬Ã‚Â¬ A)
[A p.134]
6. Ã‚Â¬(Ã‚Â¬ A _ B)
[A p.135]
[Contents]
Exercises 7.2.2.1
Construct finished trees for each of the following propositions.
1. (( A ! B) ! B)
[A p.135]
2. (( A ! B) _ ( B ! A))
[A p.135]
3. Ã‚Â¬(Ã‚Â¬ A ! ( A _ B))
[A p.135]
4. Ã‚Â¬Ã‚Â¬(( A ^ B) _ ( A ^ Ã‚Â¬ B))
[A p.135]
[Contents]
27
Exercises 7.2.3.1
Construct finished trees for each of the following propositions; close paths
as appropriate.
1. Ã‚Â¬( A ! ( B ! A))
[A p.136]
2. (( A ! B) _ (Ã‚Â¬ A _ B))
[A p.136]
3. Ã‚Â¬(( A ! B) _ (Ã‚Â¬ A _ B))
[A p.136]
4. Ã‚Â¬Ã‚Â¬Ã‚Â¬( A _ B)
[A p.136]
5. Ã‚Â¬( A ^ Ã‚Â¬ A)
[A p.136]
6. Ã‚Â¬(Ã‚Â¬( A ^ B) \$ (Ã‚Â¬ A _ Ã‚Â¬ B))
[A p.137]
[Contents]
Exercises 7.3.1.1
Using trees, determine whether the following arguments are valid. For
any arguments that are invalid, give a counterexample.
1.
A
) ( A _ B)
2.
( A _ B)
) B
3.
( A _ B)
( A ! C)
(B ! D)
) (C _ D )
4.
5.
[A p.137]
[A p.137]
[A p.138]
(( A _ Ã‚Â¬ B) ! C )
(B ! Ã‚Â¬D)
D
) C
[A p.138]
B
( A ! B)
) A
[A p.138]
28
6.
7.
8.
9.
10.
A
( A ! B)
) B
[A p.138]
( A _ ( B ^ C ))
( A ! B)
(B \$ D)
) (B ^ D)
[A p.139]
Ã‚Â¬(Ã‚Â¬ A ! B)
Ã‚Â¬(C \$ A)
( A _ C)
Ã‚Â¬(C ! B)
) Ã‚Â¬( A ! B)
[A p.139]
( A \$ B)
(B ! C)
(Ã‚Â¬ B ! Ã‚Â¬C )
( A _ ( B ^ Ã‚Â¬ B))
) C
[A p.140]
( A ! B)
(B ! C)
(C ! D )
( D ! E)
) Ã‚Â¬( A ^ Ã‚Â¬ E)
[A p.140]
[Contents]
Exercises 7.3.2.1
1. Using trees, test whether the following propositions are contradictions. For any proposition that is satisfiable, read off from an open
path a scenario in which the proposition is true.
(i) A ^ Ã‚Â¬ A
[A p.141]
(ii) ( A _ B) ^ Ã‚Â¬( A _ B)
[A p.141]
(iv) ( A ! Ã‚Â¬( A _ B)) ^ Ã‚Â¬(Ã‚Â¬( A _ B) _ B)
[A p.141]
(vi) ( A \$ Ã‚Â¬ A) _ ( A ! Ã‚Â¬( B _ C ))
[A p.142]
(iii) ( A ! B) ^ Ã‚Â¬( A _ B)
[A p.141]
(v) Ã‚Â¬((Ã‚Â¬ B _ C ) \$ ( B ! C ))
29
[A p.142]
2. Using trees, test whether the following sets of propositions are satisfiable. For any set that is satisfiable, read off from an open path a
scenario in which all the propositions in the set are true.
(i) {( A _ B), Ã‚Â¬ B, ( A ! B)}
[A p.142]
(ii) {( A _ B), ( B _ C ), Ã‚Â¬( A _ C )}
[A p.142]
(iii) {Ã‚Â¬(Ã‚Â¬ A ! B), Ã‚Â¬(C \$ A), ( A _ C ), Ã‚Â¬(C ! B), ( A ! B)}
[A p.143]
(iv) {( A \$ B), Ã‚Â¬( A ! C ), (C ! A), ( A ^ B) _ ( A ^ C )} [A p.143]
[Contents]
Exercises 7.3.3.1
Test whether the following pairs of propositions are contraries, contradictories, or jointly satisfiable.
1. (Ã‚Â¬ A ! B) and ( B ! A)
[A p.144]
2. ( A ! B) and Ã‚Â¬( A ! ( A ! B))
[A p.144]
3. Ã‚Â¬( A \$ Ã‚Â¬ B) and Ã‚Â¬( A _ Ã‚Â¬ B)
[A p.145]
4. Ã‚Â¬( A _ Ã‚Â¬ B) and (Ã‚Â¬ A ! Ã‚Â¬ B)
[A p.146]
5. (Ã‚Â¬ A ^ ( A ! B)) and Ã‚Â¬(Ã‚Â¬ A ! ( A ! B))
[A p.147]
6. (( A ! B) \$ B) and Ã‚Â¬( A ! B)
[A p.147]
[Contents]
Exercises 7.3.4.1
Test whether the following propositions are tautologies. (Remember to
restore outermost parentheses before adding the negation symbol at the
frontÃ¢â‚¬â€recall Ã‚Â§2.5.4.) For any proposition that is not a tautology, read off
from your tree a scenario in which it is false.
1. A ! ( B ! A)
[A p.148]
2. A ! ( A ! B)
[A p.148]
30
3. (( A ^ B) _ Ã‚Â¬( A ! B)) ! (C ! A)
[A p.148]
4. ( A ^ ( B _ C )) \$ (( A ^ B) _ ( A ^ C ))
[A p.149]
5. Ã‚Â¬ A _ Ã‚Â¬( A ^ B)
[A p.149]
6. A _ (Ã‚Â¬ A ^ Ã‚Â¬ B)
[A p.149]
7. ( A ! B) _ ( A ^ Ã‚Â¬ B)
[A p.150]
8. ( B ^ Ã‚Â¬ A) \$ ( A \$ B)
[A p.150]
9. ( A _ ( B _ C )) \$ (( A _ B) _ C )
[A p.150]
10. ( A ^ ( B _ C )) \$ (( A _ B) ^ C )
[A p.151]
[Contents]
Exercises 7.3.5.1
Test whether the following are equivalent. Where the two propositions
are not equivalent, read off from your tree a scenario in which they have
different truth values.
1. P and ( P ^ P)
[A p.151]
2. ( P ! ( Q _ Ã‚Â¬ Q)) and ( R ! R)
[A p.151]
3. Ã‚Â¬( A _ B) and (Ã‚Â¬ A ^ Ã‚Â¬ B)
[A p.152]
4. Ã‚Â¬( A _ B) and (Ã‚Â¬ A _ Ã‚Â¬ B)
[A p.152]
5. Ã‚Â¬( A ^ B) and (Ã‚Â¬ A ^ Ã‚Â¬ B)
[A p.152]
6. Ã‚Â¬( A ^ B) and (Ã‚Â¬ A _ Ã‚Â¬ B)
[A p.153]
7. A and (( A ^ B) _ ( A ^ Ã‚Â¬ B))
[A p.153]
8. Ã‚Â¬( P \$ Q) and (( P ^ Ã‚Â¬ Q) _ (Ã‚Â¬ P ^ Q))
[A p.154]
9. (( P ^ Q) ! R) and ( P ! (Ã‚Â¬ Q _ R))
[A p.154]
10. Ã‚Â¬( P \$ Q) and ( Q ^ Ã‚Â¬ P)
[A p.155]
[Contents]
31
Chapter 8
Predicate Logic
Exercises 8.2.1
Translate the following propositions from English into MPL:
1. The Pacific Ocean is beautiful.
[A p.156]
2. New York is heavily populated.
[A p.156]
3. Mary is nice.
[A p.156]
4. John is grumpy.
[A p.157]
5. Seven is a prime number.
[A p.157]
6. Pluto is a planet.
[A p.157]
7. Bill and Ben are gardeners
[A p.157]
8. If Mary is sailing or Jenny is kite flying, then Bill and Ben are grumpy.
[A p.157]
9. Mary is neither sailing nor kite flying.
[A p.157]
10. Only if Mary is sailing is Jenny kite flying.
[A p.157]
11. John is sailing or kite flying but not both.
[A p.157]
12. If Mary isnÃ¢â‚¬â„¢t sailing, then unless heÃ¢â‚¬â„¢s kite flying, John is sailing.
[A p.157]
32
13. Jenny is sailing only if both Mary and John are.
[A p.157]
14. Jenny is sailing if either John or Mary is.
[A p.157]
15. IfÃ¢â‚¬â€and only ifÃ¢â‚¬â€Mary is sailing, Jenny is kite flying.
[A p.157]
16. If Steve is winning, Mary isnÃ¢â‚¬â„¢t happy.
[A p.157]
17. Two is prime, but it is also even.
[A p.157]
18. Canberra is smallÃ¢â‚¬â€but itÃ¢â‚¬â„¢s not tiny, and itÃ¢â‚¬â„¢s a capital city. [A p.157]
19. If Rover is kite flying, then two isnÃ¢â‚¬â„¢t prime.
[A p.157]
20. Mary is happy if and only if Jenny isnÃ¢â‚¬â„¢t.
[A p.157]
[Contents]
Exercises 8.3.2
Translate the following from English into MPL.
1. If Independence Hall is red, then something is red.
[A p.158]
2. If everything is red, then Independence Hall is red.
[A p.158]
3. Nothing is both green and red.
[A p.158]
4. It is not true that nothing is both green and red.
[A p.158]
5. Red things arenÃ¢â‚¬â„¢t green.
[A p.158]
6. All red things are heavy or expensive.
[A p.158]
7. All red things that are not heavy are expensive.
[A p.158]
8. All red things are heavy, but some green things arenÃ¢â‚¬â„¢t.
[A p.158]
9. All red things are heavy, but not all heavy things are red. [A p.158]
10. Some red things are heavy, and furthermore some green things are
heavy too.
[A p.158]
11. Some red things are not heavy, and some heavy things are not red.
[A p.158]
33
12. If Kermit is green and red, then it is not true that nothing is both
green and red.
[A p.159]
13. OscarÃ¢â‚¬â„¢s piano is heavy, but it is neither red nor expensive. [A p.159]
14. If Spondulix is heavy and expensive, and all expensive things are red
and all heavy things are green, then Spondulix is red and green.1
[A p.159]
15. If Kermit is heavy, then something is green and heavy.
[A p.159]
16. If everything is fun, then nothing is worthwhile.
[A p.159]
17. Some things are fun and some things are worthwhile, but nothing is
both.
[A p.159]
18. Nothing is probable unless something is certain.
[A p.159]
19. Some things are probable and some arenÃ¢â‚¬â„¢t, but nothing is certain.
[A p.159]
20. If something is certain, then itÃ¢â‚¬â„¢s probable.
[A p.159]
[Contents]
Exercises 8.3.5
Translate the following propositions from English into MPL.
1. Everyone is happy.
[A p.159]
[A p.159]
3. No one is both happy and sad.
[A p.159]
4. If someone is sad, then not everyone is happy.
[A p.159]
5. No one who isnÃ¢â‚¬â„¢t happy is laughing.
[A p.160]
6. If Gary is laughing, then someone is happy.
[A p.160]
7. Whoever is laughing is happy.
[A p.160]
1 Ã¢â‚¬Å“SpondulixÃ¢â‚¬Â
is the name of a famous gold nugget, found in 1872.
34
8. Everyone is laughing if Gary is.
[A p.160]
9. Someone is sad, but not everyone and not Gary.
[A p.160]
10. Gary isnÃ¢â‚¬â„¢t happy unless everyone is sad.
[A p.160]
11. All leaves are brown and the sky is gray.
[A p.160]
12. Some but not all leaves are brown.
[A p.160]
13. Only leaves are brown.
[A p.160]
14. Only brown leaves can stay.
[A p.160]
15. Everyone is in trouble unless Gary is happy.
[A p.160]
16. Everyone who works at this company is in trouble unless Gary is
happy.
[A p.160]
17. If Stephanie is telling the truth, then someone is lying.
[A p.160]
18. If no one is lying, then Stephanie is telling the truth.
[A p.160]
19. Either Stephanie is lying, or no-oneÃ¢â‚¬â„¢s telling the truth and everyone
is in trouble.
[A p.160]
20. If Gary is lying, then not everyone in this room is telling the truth.
[A p.160]
[Contents]
Exercises 8.4.3.1
Write out a construction for each of the following wffs, and state the main
operator.
1. 8 x ( Fx ! Gx )
[A p.161]
2. 8 x Ã‚Â¬ Gx
[A p.161]
3. Ã‚Â¬9 x ( Fx ^ Gx )
[A p.161]
4. ( Fa ^ Ã‚Â¬9 x Ã‚Â¬ Fx )
[A p.161]
5. 8 x ( Fx ^ 9y( Gx ! Gy))
[A p.162]
35
6. (8 x ( Fx ! Gx ) ^ Fa)
[A p.162]
7. ((Ã‚Â¬ Fa ^ Ã‚Â¬ Fb) ! 8 x Ã‚Â¬ Fx )
[A p.162]
8. 8 x 8y(( Fx ^ Fy) ! Gx )
[A p.163]
9. 8 x ( Fx ! 8yFy)
[A p.163]
10. (8 xFx ! 8yFy)
[A p.163]
[Contents]
Exercises 8.4.5.1
Identify any free variables in the following formulas. State whether each
formula is open or closed.
1. Tx ^ Fx
[A p.163]
2. Tx ^ Ty
[A p.163]
3. 9 xTx ^ 9 xFx
[A p.163]
4. 9 xTx ^ 8yFx
[A p.163]
5. 9 xTx ^ Fx
[A p.164]
6. 9 x ( Tx ^ Fx )
[A p.164]
7. 8y9 xTy
[A p.164]
8. 9 x (8 xTx ! 9yFx )
[A p.164]
9. 9y8 xTx ! 9yFx
[A p.164]
10. 8 x (9 xTx ^ Fx )
[A p.164]
11. 8 x 9 xTx ^ Fx
[A p.164]
12. 9 xTy
[A p.164]
13. 8 xTx ! 9 xFx
[A p.164]
14. 9 x 8y( Tx _ Fy)
[A p.164]
15. 8 xFx ^ Gx
[A p.164]
36
16. 8 x 8yFx ! Gy
[A p.164]
17. 8 x 8y( Fx ! 8 xGy)
[A p.164]
18. 9yGb ^ Gc
[A p.164]
19. 9yGy ^ 8 x ( Fx ! Gy)
[A p.164]
20. 8 x (( Fx ! 9 xGx ) ^ Gx )
[A p.164]
[Contents]
37
Chapter 9
Logic
Exercises 9.1.1
For each of the propositions:
(i) Pa
(ii) 9 xPx
(iii) 8 xPx
state whether it is true or false on each of the following models.
1. Domain: {1, 2, 3, . . . }2
Referent of a: 1
Extension of P: {1, 3, 5, . . . }3
[A p.165]
2. Domain: {1, 2, 3, . . . }
Referent of a: 1
Extension of P: {2, 4, 6, . . . }4
[A p.165]
3. Domain: {1, 2, 3, . . . }
Referent of a: 2
Extension of P: {1, 3, 5, . . . }
[A p.165]
4. Domain: {1, 2, 3, . . . }
Referent of a: 2
Extension of P: {2, 4, 6, . . . }
[A p.165]
2 That
is, the set of positive integers.
is, the set of odd numbers.
4 That is, the set of even numbers.
3 That
38
5. Domain: {1, 2, 3, . . . }
Referent of a: 1
Extension of P: {1, 2, 3, . . . }
[A p.165]
6. Domain: {1, 2, 3, . . . }
Referent of a: 2
Extension of P: Ã¢Ë†â€
[A p.165]
[Contents]
Exercises 9.2.1
State whether each of the following propositions is true or false in each of
the six models given in Exercises 9.1.1.
(i) (Ã‚Â¬ Pa ^ Ã‚Â¬ Pa)
(ii) (Ã‚Â¬ Pa ! Pa)
(iii) ( Pa \$ 9 xPx )
(iv) (9 xPx _ Ã‚Â¬ Pa)
(v) Ã‚Â¬(8 xPx ^ Ã‚Â¬9 xPx )
[Contents]
Exercises 9.3.1
1. If a( x ) is ( Fx ^ Ga), what is
(i) a( a/x )
[A p.166]
(ii) a(b/x )
[A p.166]
2. If a( x ) is 8y( Fx ! Gy), what is
(i) a( a/x )
[A p.166]
(ii) a(b/x )
[A p.166]
3. If a( x ) is 8 x ( Fx ! Gx ) ^ Fx, what is
(i) a( a/x )
[A p.166]
39
(ii) a(b/x )
[A p.166]
4. If a( x ) is 8 x ( Fx ^ Ga), what is
(i) a( a/x )
[A p.166]
(ii) a(b/x )
[A p.166]
5. If a(y) is 9 x ( Gx ! Gy), what is
(i) a( a/y)
[A p.166]
(ii) a(b/y)
[A p.166]
6. If a( x ) is 9y(8 x ( Fx ! Fy) _ Fx ), what is
(i) a( a/x )
[A p.166]
(ii) a(b/x )
[A p.166]
[Contents]
Exercises 9.4.3
1. Here is a model:
Domain: {1, 2, 3, 4}
Extensions: E: {2, 4} O: {1, 3}
State whether each of the following propositions is true or false in
this model.
(i) 8 xEx
[A p.167]
(iii) 9 xEx
[A p.167]
(ii) 8 x ( Ex _ Ox )
[A p.167]
(iv) 9 x ( Ex ^ Ox )
[A p.167]
(vi) 8 xEx _ 9 x Ã‚Â¬ Ex
[A p.167]
(v) 8 x (Ã‚Â¬ Ex ! Ox )
[A p.167]
2. State whether the given proposition is true or false in the given models.
(i) 8 x ( Px _ Rx )
(a) Domain: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Extensions: P: {1, 2, 3} R: {5, 6, 7, 8, 9, 10}
40
[A p.167]
(b) Domain: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Extensions: P: {1, 2, 3, 4} R: {4, 5, 6, 7, 8, 9, 10}
[A p.167]
(ii) 9 x (Ã‚Â¬ Px \$ ( Qx ^ Ã‚Â¬ Rx ))
(a) Domain: {1, 2, 3, . . .}
Extensions: P: {2, 4, 6, . . .}
Q: {1, 3, 5, . . .}
R: {2, 4, 6, . . .}
[A p.167]
(b) Domain: {1, 2, 3, . . .}
Extensions: P: {2, 4, 6, . . .}
Q: {2, 4, 6, . . .}
R: {1, 3, 5, . . .}
[A p.167]
(iii) 9 xPx ^ Ra
(a) Domain: {1, 2, 3, . . .}
Referent of a: 7
Extensions: P: {2, 3, 5, 7, 11, . . .}5 R: {1, 3, 5, . . .} [A p.167]
(b) Domain: {Alice, Ben, Carol, Dave}
Referent of a: Alice
Extensions: P: {Alice, Ben} R: {Carol, Dave} [A p.167]
3. Here is a model:
Domain: {Bill, Ben, Alison, Rachel}
Referents: a: Alison r: Rachel
Extensions: M: {Bill, Ben} F: {Alison, Rachel}
J: {Bill, Alison} S: {Ben, Rachel}
State whether each of the following propositions is true or false in
this model.
(i) ( Ma ^ Fr ) ! 9 x ( Mx ^ Fx )
[A p.167]
(ii) 8 x 8y( Mx ! My)
[A p.167]
(iv) 8 xMx ! 8 xJx
[A p.167]
(vi) 9 x ( Fx ^ Sx ) ! 8 x ( Fx ! Sx )
[A p.167]
(iii) (Ã‚Â¬ Ma _ Ã‚Â¬ Jr ) ! 9 x 9y( Mx ^ Fy)
(v) 9 x 9y( Mx ^ Fy ^ Sr )
5 That
[A p.167]
[A p.167]
is, the set of prime numbers.
41
4. For each of the following propositions, describe (a) a model in which
it is true, and (b) a model in which it is false. If there is no model of
one of these types, explain why.
(i) 8 x ( Fx ! Gx )
[A p.167]
(ii) 8 xFx ^ Ã‚Â¬ Fa
[A p.167]
(iv) 9 x ( Fx ^ Gx )
[A p.168]
(vi) 9 xFx ^ 9 xGx
[A p.168]
(viii) 9 x ( Fx ^ Ã‚Â¬ Fx )
[A p.168]
(x) 9 x ( Fx ! Fx )
[A p.169]
(xii) 9 xFx ! 8 xGx
[A p.169]
(xiv) 8 x ( Fx ! Fa)
[A p.169]
(xvi) 8 x ( Fx _ Gx )
[A p.170]
(xviii) 8 x ( Fx ^ Ã‚Â¬ Fx )
[A p.170]
(iii) 9 xFx ^ Ã‚Â¬ Fa
[A p.168]
(v) 8 x ( Fx ! Fx )
[A p.168]
(vii) 8 xFx ! 9 xFx
[A p.168]
(ix) 9 xFx ^ 9 x Ã‚Â¬ Fx
[A p.168]
(xi) 9 xFx ! 9 xGx
[A p.169]
(xiii) 8 xFx ! Fa
[A p.169]
(xv) Fa ! Fb
[A p.169]
(xvii) 9 x ( Fx _ Gx )
[A p.170]
(xix) 8 x 9y( Fx ! Gy)
[A p.170]
(xx) 8 x ( Fx ! 9yGy)
5.
[A p.170]
(i) Is 8 x ( Fx ! Gx ) true or false in a model in which the extension
of F is the empty set?
[A p.170]
(ii) Is 9 x ( Fx ^ Gx ) true in every model in which 8 x ( Fx ! Gx ) is
true?
[A p.170]
[Contents]
42
Exercises 9.5.1
For each of the following arguments, either produce a countermodel (thereby
showing that the argument is invalid) or explain why there cannot be a
countermodel (in which case the argument is valid).
1. 9 xFx ^ 9 xGx
) 9 x ( Fx ^ Gx )
[A p.171]
2. 9 x ( Fx ^ Gx )
) 9 xFx ^ 9 xGx
[A p.171]
3. 8 x ( Fx _ Gx )
Ã‚Â¬8 xFx
) 8 xGx
[A p.171]
4. 8 x ( Fx ! Gx )
8 x ( Gx ! Hx )
) 8 x ( Fx ! Hx )
[A p.171]
5. 8 x ( Fx ! Gx )
8 x ( Gx ! Hx )
) 8 x ( Hx ! Fx )
[A p.171]
[Contents]
43
Chapter 10
Exercises 10.2.2
1. Using trees, determine whether the following propositions are logical truths. For any proposition that is not a logical truth, read off
from your tree a model in which it is false.
(i) Fa ! 9 xFx
[A p.172]
(ii) 9 xFx ! Ã‚Â¬8 x Ã‚Â¬ Fx
[A p.172]
(iv) 8 xFx ! 9 xFx
[A p.173]
(vi) 9 xFx ^ 9 x Ã‚Â¬ Fx
[A p.174]
(iii) 8 x (( Fx ^ Ã‚Â¬ Gx ) ! 9 xGx )
[A p.173]
(v) ( Fa ^ ( Fb ^ Fc)) ! 8 xFx
[A p.173]
(vii) 9 x ( Fx ! 8yFy)
[A p.174]
(viii) 8 x ( Fx ! Gx ) ! ( Fa ! Ga)
(ix) Ã‚Â¬8 x ( Fx ^ Gx ) \$ 9 x Ã‚Â¬( Fx ^ Gx )
(x) Ã‚Â¬9 x ( Fx ^ Gx ) \$ 8 x (Ã‚Â¬ Fx ^ Ã‚Â¬ Gx )
[A p.174]
[A p.175]
[A p.175]
2. Using trees, determine whether the following arguments are valid.
For any argument that is not valid, read off from your tree a model
in which the premises are true and the conclusion false.
(i) 9 xFx ^ 9 xGx
) 9 x ( Fx ^ Gx )
[A p.176]
(ii) 9 x 8y( Fx ! Gy)
) 8y9 x ( Fx ! Gy)
[A p.176]
44
(iii) Fa ! 8 xGx
) 8 x ( Fa ! Gx )
[A p.177]
(iv) Fa ! 8 xGx
) 9 x ( Fa ! Gx )
[A p.177]
(v) 8 x ( Fx _ Gx )
Ã‚Â¬8 xFx
) 8 xGx
[A p.177]
(vi) 9 x ( Fx ^ Gx )
) 9 xFx ^ 9 xGx
[A p.178]
(vii) 8 x ( Fx ! Gx )
Fa
) Ga
[A p.178]
(viii) Ã‚Â¬8 x ( Fx _ Gx )
) 9 x (Ã‚Â¬ Fx ^ Ã‚Â¬ Gx )
[A p.178]
(ix) 8 x ( Fx ! Gx )
8 x ( Gx ! Hx )
) Ã‚Â¬9 x (Ã‚Â¬ Fx ^ Hx )
[A p.179]
(x) 8 x ( Fx _ Gx )
) Ã‚Â¬9 x ( Fx ^ Gx )
[A p.179]
[Contents]
Exercises 10.3.8
Translate the following arguments into MPL, and then test for validity using trees. For any argument that is not valid, read off from your tree a
model in which the premise(s) are true and the conclusion false.
1. All dogs are mammals. All mammals are animals. Therefore, all
dogs are animals.
[A p.180]
2. If everything is frozen, then everything is cold. So everything frozen
is cold.
[A p.181]
3. If a thing is conscious, then either there is a divine being, or that thing
has a sonic screwdriver. Nothing has a sonic screwdriver. Thus, not
everything is conscious.
[A p.182]
4. All cows are scientists, no scientist can fly, so no cow can fly.
[A p.183]
45
5. Someone here is not smoking. Therefore, not everyone here is smoking.
[A p.184]
6. If Superman rocks up, all cowards will shake. Catwoman is not a
coward. So Catwoman will not shake.
[A p.185]
7. Each car is either red or blue. All the red cars are defective, but some
of the blue cars arenÃ¢â‚¬â„¢t. Thus, there are some defective cars and some
nondefective cars.
[A p.186]
8. For each thing, it swims only if there is a fish. Therefore, some things
donÃ¢â‚¬â„¢t swim.
[A p.187]
9. All robots built before 1970 run on kerosene. Autovac 23E was built
before 1970, but it doesnÃ¢â‚¬â„¢t run on kerosene. So itÃ¢â‚¬â„¢s not a robot.
[A p.188]
10. Everyone who is tall is either an athlete or an intellectual. Some people are athletes and intellectuals, but none of them is tall. Graham is a
person. Therefore, if heÃ¢â‚¬â„¢s an athlete, then either heÃ¢â‚¬â„¢s not an intellectual, or he isnÃ¢â‚¬â„¢t tall.
[A p.189]
[Contents]
46
Chapter 11
Models, Propositions, and Ways
the World Could Be
There are no exercises for chapter 11.
47
[Contents]
Chapter 12
General Predicate Logic
Exercises 12.1.3.1
State whether each of the following is a wff of GPL.
1. 8 xF1 y
[A p.191]
2. 8 x 9yF1 y
[A p.191]
3. 8 xR2 xy
[A p.191]
4. 8 x 9 xR2 yy
[A p.191]
5. R2 x
[A p.191]
6. 8 xR2 x
[A p.191]
7. 8 x ( F1 x ! R2 x )
[A p.191]
8. 8 x 9y( F1 x ! R2 xy)
[A p.191]
9. 8 x 9y( F1 xy ! R2 y)
[A p.191]
10. 8 x 9y8 x 9yR2 xy
[A p.191]
[Contents]
48
Exercises 12.1.6
Translate the following into GPL.
1. Bill heard Alice.
[A p.192]
2. Bill did not hear Alice.
[A p.192]
3. Bill heard Alice, but Alice did not hear Bill.
[A p.192]
4. If Bill heard Alice, then Alice heard Bill.
[A p.192]
5. Bill heard Alice if and only if Alice heard Alice.
[A p.192]
6. Bill heard Alice, or Alice heard Bill.
[A p.192]
7. Clare is taller than Dave, but sheÃ¢â‚¬â„¢s not taller than Edward. [A p.192]
8. Mary prefers Alice to Clare.
[A p.192]
9. Mary doesnÃ¢â‚¬â„¢t prefer Dave to Clare; nor does she prefer Clare to Dave.
[A p.192]
10. Edward is taller than Clare, but heÃ¢â‚¬â„¢s not tall.
[A p.192]
11. The Eiffel tower is taller than both Clare and Dave.
[A p.192]
12. If Dave is taller than the Eiffel tower, then heÃ¢â‚¬â„¢s tall.
[A p.192]
13. Although the Eiffel tower is taller, Clare prefers Dave.
[A p.193]
14. If Alice is taller than Dave, then he prefers himself to her. [A p.193]
15. Dave prefers Edward to Clare only if Edward is taller than the Eiffel
tower.
[A p.193]
16. Dave prefers Edward to Clare only if sheÃ¢â‚¬â„¢s not tall.
[A p.193]
17. Mary has read Fiesta, and she likes it.
[A p.193]
18. Dave doesnÃ¢â‚¬â„¢t like Fiesta, but he hasnÃ¢â‚¬â„¢t read it.
[A p.193]
19. If Dave doesnÃ¢â‚¬â„¢t like The Bell Jar, then he hasnÃ¢â‚¬â„¢t read it.
[A p.193]
20. Dave prefers The Bell Jar to Fiesta, even though he hasnÃ¢â‚¬â„¢t read either.
[A p.193]
[Contents]
49
Exercises 12.1.9
Translate the following into GPL.
1.
(i) Something is bigger than everything.
[A p.193]
(ii) Something is such that everything is bigger than it.
[A p.193]
(iii) If Alice is bigger than Bill, then something is bigger than Bill.
[A p.193]
(iv) If everything is bigger than Bill, then Alice is bigger than Bill.
[A p.193]
(v) If something is bigger than everything, then something is bigger
than itself.
[A p.193]
(vi) If Alice is bigger than Bill and Bill is bigger than Alice, then
everything is bigger than itself.
[A p.193]
(vii) There is something that is bigger than anything that Alice is bigger than.
[A p.193]
(viii) Anything that is bigger than Alice is bigger than everything that
Alice is bigger than.
[A p.193]
(ix) Every room contains at least one chair.
[A p.193]
(x) In some rooms some of the chairs are broken; in some rooms all
of the chairs are broken; in no room is every chair unbroken.
[A p.194]
2.
(i) Every person owns a dog.
[A p.194]
(ii) For every dog, there is a person who owns that dog. [A p.194]
(iii) There is a beagle that owns a chihuahua.
[A p.194]
(iv) No beagle owns itself.
[A p.194]
(v) No chihuahua is bigger than any beagle.
[A p.194]
(vi) Some chihuahuas are bigger than some beagles.
[A p.194]
(vii) Some dogs are happier than any person.
[A p.194]
(viii) People who own dogs are happier than those who donÃ¢â‚¬â„¢t.
[A p.194]
(ix) The bigger the dog, the happier it is.
[A p.194]
(x) There is a beagle that is bigger than every chihuahua and smaller
than every person.
[A p.194]
50
3.
(i) Alice is a timid dog, and some cats are bigger than her.
[A p.195]
(ii) Every dog that is bigger than Alice is bigger than Bill. [A p.195]
(iii) Bill is a timid cat, and every dog is bigger than him.
[A p.195]
(iv) Every timid dog growls at some gray cat.
[A p.195]
(v) Every dog growls at every timid cat.
[A p.195]
(vi) Some timid dog growls at every gray cat.
[A p.195]
(vii) No timid dog growls at any gray cat.
[A p.195]
(viii) Alice wants to buy something from Woolworths, but Bill doesnÃ¢â‚¬â„¢t.
[A p.195]
(ix) Alice wants to buy something from Woolworths that Bill doesnÃ¢â‚¬â„¢t.
[A p.195]
(x) Bill growls at anything that Alice wants to buy from Woolworths.
[A p.195]
4.
[A p.196]
[A p.196]
[A p.196]
himself.6
[A p.196]
[A p.196]
(vii) Frank admires Elvis but he prefers the Rolling Stones. [A p.196]
(viii) Frank prefers any song recorded by the Rolling Stones to any
song recorded by Elvis.
[A p.196]
(ix) The Rolling Stones recorded a top-twenty song, but Elvis didnÃ¢â‚¬â„¢t.
[A p.196]
(x) Elvis prefers any top-twenty song that the Rolling Stones recorded
to any song that he himself recorded.
[A p.196]
[Contents]
Ã¢â‚¬Å“himselfÃ¢â‚¬Â here as gender-neutralÃ¢â‚¬â€that is, the claim is that no one self-admires.
Ã¢â‚¬Å“himselfÃ¢â‚¬Â here as gender-neutralÃ¢â‚¬â€that is, the claim is that Dave admires anyone who doesnÃ¢â‚¬â„¢t self-admire.
51
Exercises 12.2.2
1. Here is a model:
Domain:
Referents:
Extensions: E:
P:
L:
{1, 2, 3, . . .}
a: 1 b: 2 c: 3
{2, 4, 6, . . .}
{2, 3, 5, 7, 11, . . .}8
{h1, 2i, h1, 3i, h1, 4i, . . . , h2, 3i, h2, 4i, . . . , h3, 4i, . . .} 9
State whether each of the following propositions is true or false in
this model.
(i) Lba
[A p.196]
(ii) Lab _ Lba
[A p.196]
(iii) Laa
[A p.196]
(iv) 9 xLxb
[A p.196]
(vi) 9 xLxx
[A p.197]
(viii) 8 x 9yLyx
[A p.197]
(v) 9 xLxa
[A p.196]
(vii) 8 x 9yLxy
[A p.197]
(ix) 9 x ( Px ^ Lxb)
[A p.197]
(xi) 8 x 9y( Ey ^ Lxy)
[A p.197]
(x) 9 x ( Px ^ Lcx )
[A p.197]
(xii) 8 x 9y( Py ^ Lxy)
[A p.197]
(xiv) 8 x (( Lax ^ Lxc) ! Ex )
[A p.197]
(xvi) 9 x 9y9z( Ex ^ Py ^ Ez ^ Pz ^ Lxy ^ Lyz)
[A p.197]
(xiii) 8 x ( Lcx ! Ex )
[A p.197]
(xv) 8 x 8y( Lxy _ Lyx )
[A p.197]
(xvii) 9 x 9y9z( Lxy ^ Lyz ^ Lzx )
(xviii) 8 x 8y8z(( Lxy ^ Lyz) ! Lxz)
8 That
[A p.197]
[A p.197]
is, the set of prime numbers.
is, the set of all pairs h x, yi such that x is less than y. A more compact way of