Sets, logic and maths for computing

For the Student......Page 6
 For the Instructor......Page 8
 The Third Edition......Page 11
Contents......Page 14
Sets......Page 20
 1.1 The Intuitive Concept of a Set......Page 21
  1.2.1 Inclusion......Page 22
  1.2.2 Identity and Proper Inclusion......Page 24
  1.2.3 Diagrams......Page 27
  1.2.4 Ways of Defining a Set......Page 30
  1.3.1 Emptiness......Page 31
  1.3.2 Disjoint Sets......Page 32
  1.4.1 Meet......Page 33
  1.4.2 Union......Page 35
  1.4.3 Difference and Complement......Page 39
 1.5 Generalised Union and Meet......Page 43
 1.6 Power Sets......Page 45
 1.7 End-of-Chapter Exercises......Page 49
 1.8 Selected Reading......Page 53
 2.1 Ordered Tuples, Cartesian Products, Relations......Page 54
  2.1.1 Ordered Tuples......Page 55
  2.1.2 Cartesian Products......Page 56
  2.1.3 Relations......Page 58
  2.2.1 Tables......Page 61
  2.2.2 Digraphs......Page 62
  2.3.1 Converse......Page 63
  2.3.2 Join, Projection, Selection......Page 65
  2.3.3 Composition......Page 67
  2.3.4 Image......Page 70
  2.4.1 Reflexivity......Page 72
  2.4.2 Transitivity......Page 74
  2.5.1 Symmetry......Page 76
  2.5.2 Equivalence Relations......Page 77
  2.5.3 Partitions......Page 79
  2.5.4 The Partition/Equivalence Correspondence......Page 80
  2.6.1 Partial Order......Page 83
  2.6.2 Linear Orderings......Page 86
  2.6.3 Strict Orderings......Page 87
  2.7.1 Transitive Closure of a Relation......Page 90
  2.7.2 Closure of a Set Under a Relation......Page 92
 2.8 End-of-Chapter Exercises......Page 93
 2.9 Selected Reading......Page 98
 3.1 What is a Function?......Page 99
  3.2.2 Restriction, Image, Closure......Page 103
  3.2.3 Composition......Page 105
  3.2.4 Inverse......Page 106
  3.3.1 Injectivity......Page 107
  3.3.2 Surjectivity......Page 109
  3.3.3 Bijective Functions......Page 111
  3.4.1 Equinumerosity......Page 112
  3.4.3 The Pigeonhole Principle......Page 114
  3.5.1 Identity Functions......Page 116
  3.5.2 Constant Functions......Page 117
  3.5.4 Characteristic Functions......Page 118
  3.5.5 Choice Functions......Page 119
  3.6.1 Families of Sets......Page 121
  3.6.2 Sequences and Suchlike......Page 122
 3.7 End-of-Chapter Exercises......Page 124
 3.8 Selected Reading......Page 129
 4.1 What are Induction and Recursion?......Page 130
 4.2 Proof by Simple Induction on the Positive Integers......Page 131
  4.2.1 An Example......Page 132
  4.2.2 The Principle Behind the Example......Page 133
 4.3 Definition by Simple Recursion on the Positive Integers......Page 138
 4.4 Evaluating Functions Defined by Recursion......Page 140
  4.5.1 Cumulative Recursive Definitions......Page 142
  4.5.2 Proof by Cumulative Induction......Page 144
  4.5.3 Simultaneous Recursion and Induction......Page 146
 4.6 Structural Recursion and Induction......Page 148
  4.6.1 Defining Sets by Structural Recursion......Page 149
  4.6.2 Proof by Structural Induction......Page 153
  4.6.3 Defining Functions by Structural Recursion on Their Domains......Page 155
  4.7.1 Well-Founded Sets......Page 159
  4.7.2 Proof by Well-Founded Induction......Page 162
  4.7.3 Defining Functions by Well-Founded Recursion on their Domains......Page 164
  4.7.4 Recursive Programs......Page 166
 4.8 End-of-Chapter Exercises......Page 167
 4.9 Selected Reading......Page 171
Maths......Page 172
 5.1 Basic Principles for Addition and Multiplication......Page 173
  5.1.1 Principles Considered Separately......Page 174
  5.1.2 Using the Two Principles Together......Page 177
  5.2.1 Order and Repetition......Page 178
  5.2.2 Connections with Functions......Page 180
  5.3.1 The Formula for Permutations......Page 183
  5.3.2 Counting Combinations......Page 185
  5.4.1 Permutations with Repetition Allowed......Page 189
  5.4.2 Combinations with Repetition Allowed......Page 191
 5.5 Rearrangements......Page 193
 5.6 End-of-Chapter Exercises......Page 195
 5.7 Selected Reading......Page 197
 6.1 Finite Probability Spaces......Page 199
  6.1.1 Basic Definitions......Page 200
  6.1.2 Properties of Probability Functions......Page 202
  6.2.1 Philosophical Interpretations......Page 204
  6.2.3 Digression: A Glimpse of the Infinite Case......Page 206
 6.3 Some Simple Problems......Page 207
 6.4 Conditional Probability......Page 210
  6.4.1 The Ratio Definition......Page 211
  6.4.2 Applying Conditional Probability......Page 213
 6.5 Interlude: Simpson’s Paradox......Page 219
 6.6 Independence......Page 221
 6.7 Bayes’ Rule......Page 224
 6.8 Expectation......Page 228
 6.9 End-of-Chapter Exercises......Page 231
 6.10 Selected Reading......Page 235
 7.1 My First Tree......Page 236
  7.2.1 Explicit Definition......Page 239
  7.2.2 Recursive Definitions......Page 241
  7.3.1 Trees Grow Everywhere......Page 243
  7.3.2 Labelled and Ordered Trees......Page 244
 7.4 Interlude: Parenthesis-Free Notation......Page 247
 7.5 Binary Trees......Page 249
 7.6 Unrooted Trees......Page 252
  7.6.1 Definition......Page 253
  7.6.2 Properties......Page 254
  7.6.3 Spanning Trees......Page 257
 7.7 End-of-Chapter Exercises......Page 259
 7.8 Selected Reading......Page 261
Logic......Page 262
 8.1 What is Logic?......Page 263
 8.2 Truth-Functional Connectives......Page 264
  8.3.1 The Language of Propositional Logic......Page 269
  8.3.2 Tautological Implication......Page 270
  8.3.3 Tautological Equivalence......Page 273
  8.3.4 Tautologies, Contradictions, Satisfiability......Page 278
  8.4.1 Disjunctive Normal Form......Page 282
  8.4.2 Conjunctive Normal Form......Page 285
  8.4.3 Least Letter Set......Page 287
  8.4.4 Most Modular Version......Page 289
 8.5 Truth-Trees......Page 291
 8.6 End-of-Chapter Exercises......Page 297
 8.7 Selected Reading......Page 301
 9.1 The Language of Quantifiers......Page 302
  9.1.1 Some Examples......Page 303
  9.1.2 Systematic Presentation of the Language......Page 304
  9.1.3 Freedom and Bondage......Page 308
  9.2.1 Quantifier Interchange......Page 309
  9.2.2 Distribution......Page 311
  9.2.3 Vacuity and Re-lettering......Page 312
  9.3.1 The Shared Part of the Two Semantics......Page 315
  9.3.2 Substitutional Reading......Page 317
  9.3.3 The x-Variant Reading......Page 320
 9.4 Semantic Analysis......Page 323
  9.4.1 Logical Implication......Page 324
  9.4.2 Clean Substitutions......Page 327
  9.4.3 Fundamental Rules......Page 328
  9.4.4 Identity......Page 330
 9.5 End-of-Chapter Exercises......Page 331
 9.6 Selected Reading......Page 335
 10.1 Elementary Derivations......Page 337
  10.1.1 My First Derivation Tree......Page 338
  10.1.2 The Logic behind Chaining......Page 340
 10.2 Consequence Relations......Page 341
  10.2.1 The Tarski Conditions......Page 342
  10.2.2 Consequence and Chaining......Page 344
  10.2.3 Consequence as an Operation......Page 346
 10.3 A Higher-Level Proof Strategy: Conditional Proof......Page 348
  10.3.1 Informal Conditional Proof......Page 349
  10.3.2 Conditional Proof as a Formal Rule......Page 350
  10.3.3 Flattening Split-Level Proofs......Page 353
  10.4.1 Disjunctive Proof and Proof by Cases......Page 355
  10.4.2 Proof by Contradiction......Page 360
  10.4.3 Proof Using Arbitrary Instances......Page 364
  10.4.4 Summary Discussion of Higher-Level Proof......Page 366
 10.5 End-of-Chapter Exercises......Page 369
 10.6 Selected Reading......Page 371
 11.1 Some Curious Classical Principles......Page 373
 11.2 A Bit of History......Page 375
 11.3 Analyses of some Truth-Trees......Page 379
 11.4 Direct Acceptability......Page 383
 11.5 Acceptability......Page 389
 11.6 End-of Chapter Exercises......Page 395
 11.7 Selected Reading......Page 397
Index......Page 399