Topics Selected......Page 6
Intended Audiences......Page 7
Goals and Approach......Page 8
Prerequisites and Course Emphases......Page 10
For Students: Reading a Mathematics Text......Page 11
Acknowledgements......Page 13
Logical Acronyms......Page 14
Contents......Page 18
1 Propositional Logic......Page 20
1.1 A Gentle Introduction to Logic and Proof......Page 21
1.2 Conjunction, Disjunction, and Negation......Page 33
1.3 Argument Semantics for Propositional Logic......Page 41
1.4 Conditional and Biconditional Sentences......Page 49
1.5 Introduction to Deduction; Rules for AND......Page 61
1.6 Elimination Rules for CONDITIONALS......Page 70
1.7 Introduction Rules for CONDITIONALS......Page 81
1.8 Proof by Contradiction: Rules for NOT......Page 94
1.9 Inference Rules for OR......Page 107
2.1 Symbolizing Sentences......Page 119
2.2 First-Order Logic: Syntax and Semantics......Page 130
2.3 Rules for Identity and Universal Quantifiers......Page 141
2.4 Rules for Existential Quantifiers......Page 152
3.1 Mathematical Induction and Recursion......Page 166
3.2 Variations on Mathematical Induction and Recursion......Page 176
3.3 Recurrence Relations; Structural Induction......Page 186
3.4 Peano Arithmetic......Page 200
3.5 Divisibility......Page 212
4.1 Relations and Operations on Sets......Page 222
4.2 Collections of Sets and the Power Set......Page 232
4.3 Multiplicative Counting Principles......Page 241
4.4 Combinations......Page 250
4.5 Additive Counting Principles......Page 263
5.1 Countably Infinite Sets......Page 271
5.2 Uncountably Infinite Sets......Page 286
5.3 Formal Set Theory and the Halting Problem......Page 297
6.1 Functions and Their Properties......Page 313
6.2 Composite Functions and Inverse Functions......Page 326
6.3 Equivalence Relations and Partitions......Page 338
6.4 The Integers and Modular Arithmetic......Page 349
7.1 Partially Ordered Sets......Page 359
7.2 Lattices......Page 371
7.3 From Boolean Lattices to Boolean Algebra......Page 382
7.4 Boolean Functions and Logic Circuits......Page 394
7.5 Representing Boolean Functions......Page 407
7.6 Simplifying Boolean Functions......Page 420
8.1 Eulerian Trails......Page 434
8.2 Hamiltonian Paths......Page 445
8.3 Planar Graphs......Page 457
8.4 Coloring Graphs......Page 470
*-21ptImage Credits......Page 482
A Inference Rules for PL and FOL......Page 484
Index......Page 487