A Logical Approach to Discrete Math

Front cover ......Page 1
Types Used in this Text ......Page 2
Texts and Monographs in Computer Science Series ......Page 3
Books in the Series ......Page 4
Title page ......Page 5
Copyright page ......Page 6
Dedication ......Page 7
Preface ......Page 9
Contents ......Page 15
0 Using Mathematics ......Page 19
1.1 Preliminaries ......Page 25
1.2 Textual substitution ......Page 26
1.3 Textual substitution and equality ......Page 29
1.4 Leibniz\'s rule and function evaluation ......Page 31
1.5 Reasoning using Leibniz\'s rule ......Page 32
1.6 The assignment statement ......Page 34
Exercises for Chapter 1 ......Page 39
2.1 Syntax and evaluation of boolean expressions ......Page 43
2.2 Equality versus equivalence ......Page 47
2.3 Satisfiability, validity and duality ......Page 49
2.4 Modeling English propositions ......Page 50
Exercises for Chapter 2 ......Page 56
3.1 Preliminaries ......Page 59
3.2 Equivalence and true ......Page 61
3.3 Negation, inequivalence, and false ......Page 63
3.4 Disjunction ......Page 67
3.5 Conjunction ......Page 69
3.6 Implication ......Page 74
Exercises for Chapter 3 ......Page 80
4.1 An abbreviation for proving implications ......Page 87
4.2 Additional proof techniques ......Page 89
Exercises for Chapter 4 ......Page 98
5.1 Solving word problems ......Page 101
5.2 Combinational digital circuits ......Page 108
Exercises for Chapter 5 ......Page 122
6.1 Hilbert-style proofs ......Page 127
6.2 Natural deduction ......Page 131
6.3 Additional proof formats ......Page 136
6.4 Styles of reasoning ......Page 138
Exercises for Chapter 6 ......Page 140
7.1 Formal logical systems ......Page 143
7.2 Constructive logics ......Page 148
Exercises for Chapter 7 ......Page 152
8.1 On types ......Page 157
8.2 Syntax and interpretation of quantification ......Page 160
8.3 Rules about quantification ......Page 165
8.4 Manipulating ranges ......Page 170
Exercises for Chapter 8 ......Page 173
9 Predicate Calculus ......Page 175
9.1 Universal quantification ......Page 176
9.2 Existential quantification ......Page 181
9.3 English to predicate logic ......Page 186
Exercises for Chapter 9 ......Page 191
10.1 Specification of programs ......Page 197
10.2 Reasoning about the assignment statement ......Page 199
10.3 Calculating parts of assignments ......Page 204
10.4 Conditional statements and expressions ......Page 206
Exercises for Chapter 10 ......Page 209
11.1 Set comprehension and membership ......Page 213
11.2 Operations on sets ......Page 219
11.3 Theorems concerning set operations ......Page 221
11.4 Union and intersection of families of sets ......Page 226
11.5 The axiom of choice \' ......Page 227
11.6 Ill-defined sets and paradoxes ......Page 228
11.7 Bags ......Page 229
Exercises for Chapter 11 ......Page 231
12.1 Induction over the natural numbers ......Page 235
12.2 Inductive definitions ......Page 240
12.3 Peano arithmetic ......Page 245
12.4 Induction and well-founded sets ......Page 246
12.5 Induction for inductive definitions ......Page 250
12.6 The correctness of loops ......Page 254
Exercises for Chapter 12 ......Page 261
13.1 The basic theory of sequences ......Page 269
13.2 Extending the theory with new operations ......Page 272
13.3 Extending the theory to use integers ......Page 276
Exercises for Chapter 13 ......Page 280
14.1 Tuples and cross products ......Page 283
14.2 Relations ......Page 285
14.3 Functions ......Page 297
14.4 Order relations ......Page 303
14.5 Relational Databases ......Page 312
Exercises for Chapter 14 ......Page 317
15.1 Integral domains ......Page 321
15.2 Exploring minimum and maximum ......Page 329
15.3 Exploring absolutes ......Page 332
15.4 Divisibility, common divisors, and primes ......Page 333
15.5 Common representations of natural numbers ......Page 345
Exercises for Chapter 15 ......Page 349
16.1 Rules of counting ......Page 355
16.2 Properties of n choose r ......Page 361
16.3 Examples of counting ......Page 366
16.4 The pigeonhole principle ......Page 373
Exercises for Chapter 16 ......Page 375
17.1 Homogeneous difference equations ......Page 381
17.2 Nonhomogeneous difference equations ......Page 389
17.3 Generating functions ......Page 393
Exercises for Chapter 17 ......Page 401
18.1 The structure of algebras ......Page 405
18.2 Group theory ......Page 414
18.3 Boolean algebras ......Page 430
Exercises for Chapter 18 ......Page 435
19.1 Graphs and multigraphs ......Page 441
19.2 Three applications of graph theory ......Page 448
19.3 Classes of graphs ......Page 454
19.4 Subgraphs and morphisms ......Page 455
19.5 Hamilton circuits ......Page 457
19.6 Planar graphs ......Page 463
19.7 Shortest paths and spanning trees ......Page 467
Exercises for Chapter 19 ......Page 476
20.1 Finite versus infinite sets ......Page 479
20.2 The cardinality of an infinite set ......Page 480
20.3 Countable and uncountable sets ......Page 484
Exercises for Chapter 20 ......Page 488
References ......Page 491
Index ......Page 495
Books in the Series ......Page 517
Theorems of the propositional and predicate calculi ......Page 520
Back cover ......Page 530