INTERNATIONAL STUDENT EDITION STUDEN I ISE Scheinerman Edward Scheinerman Mathematics:A Discrete Introduction Mathematics:A Discrete Introduction Second Edition Second Edition BROOKS/COL THOMSON Not for Sale in the United States
Proof Templates 1 Direct proof of an if-then theorem.19 2 Direct proof of an if-and-only-if theorem.23 3 Refuting a false if-then statement via a counterexample. 26 4 Truth table proof of logical equivalence.30 5 Proving two sets are equal.51 6 Proving one set is a subset of another. 54 7 Proving existential statements.59 8 Proving universal statements. 60 9 Combinatorial proof.67 10 Using inclusion-exclusion. 129 11 Proof by contrapositive.136 12 Proof by contradiction.137 13 Proving that a set is empty.140 14 Proving uniqueness.140 15 Proof by smallest counterexample. 146 16 Proof by the Well-Ordering Principle. 150 17 Proof by induction.158 18 Proof by strong induction. 163 19 To show f:A→B. 196 20 Proving a function is one-to-one. 199 21 Proving a function is onto.201 22 Proving two functions are equal. 213 23 Proving (G,*is a group. 344 24 Proving a subset of a group is a subgroup.354 25 Proving theorems about trees by leaf deletion. 418
Proof Templates 1 Direct proof of an if-then theorem. 19 2 Direct proof of an if-and-only-if theorem. 23 3 Refuting a false if-then statement via a counterexample. 26 4 Truth table proof of logical equivalence. 30 5 Proving two sets are equal. 51 6 Proving one set is a subset of another. 54 7 Proving existential statements. 59 8 Proving universal statements. 60 9 Combinatorial proof. 67 10 Using inclusion-exclusion. 129 11 Proof by contrapositive. 136 12 Proof by contradiction. 137 13 Proving that a set is empty. 140 14 Proving uniqueness. 140 15 Proof by smallest counterexample. 146 16 Proof by the Well-Ordering Principle. 150 17 Proof by induction. 158 18 Proof by strong induction. 163 19 To show f : A ~ B. 196 20 Proving a function is one-to-one. 199 21 Proving a function is onto. 201 22 Proving two functions are equal. 213 23 Proving (G, *) is a group. 344 24 Proving a subset of a group is a subgroup. 354 25 Proving theorems about trees by leaf deletion. 418
Contents To the Student xv How to Read a Mathematics Book xvi Exercises xvii To the Instructor xix Audience and Prerequisites xix Topics Covered and Navigating the Sections Xix Sample Course Outlines Special Features xxi What's New in This Second Edition xxiii Acknowledgments XXV This New Edition XXV From the First Edition XXV 1 Fundamentals 1 1 Joy 1 Why?1 The Agony and the Ecstasy 2 Exercise 2 2 Definition 2 Recap 5 Exercises 5 3 Theorem 8 The Nature of Truth 8 If-Then 9 If and Only If 11 And,Or,and Not 12 What Theorems Are Called 13 Vacuous Truth 14 Recap 14 Exercises 15 4 Proof 16 A More Involved Proof 20 Proving If-and-Only-If Theorems 22
Contents To the Student xv How to Read a Mathematics Book xvi Exercises xvii To the Instructor xix Audience and Prerequisites xix Topics Covered and Navigating the Sections xix Sample Course Outlines xxi Special Features xxi What's New in This Second Edition xxiii Acknowledgments xxv This New Edition xxv From the First Edition xxv 1 Fundamentals 1 Joy 1 Why? 1 The Agony and the Ecstasy 2 Exercise 2 2 Definition 2 Recap 5 Exercises 5 3 Theorem 8 The Nature of Truth 8 If-Then 9 If and Only If 11 And, Or, and Not 12 What Theorems Are Called 13 Vacuous Truth 14 Recap 14 Exercises 15 4 Proof 16 A More Involved Proof 20 1 Proving If-and-Only-If Theorems 22 v
Contents Proving Equations and Inequalities 24 Recap 25 Exercises 25 5 Counterexample 25 Recap 27 Exercises 27 6 Boolean Algebra 27 More Operations 31 Recap 32 Exercises 32 Chapter 1 Self Test 34 1 Collections 37 7 Lists 37 Counting Two-Element Lists 37 Longer Lists 40 Recap 43 Exercises 43 8 Factorial 45 Much Ado About 0! 46 Product Notation 47 Recap 48 Exercises 48 9 Sets l:Introduction,Subsets 49 Equality of Sets 51 Subset 53 Counting Subsets 55 Power Set 57 Recap 57 Exercises 57 10 Quantifiers 58 There Is 58 For All 59 Negating Quantified Statements 60 Combining Quantifiers 61 Recap 62 Exercises 63 11 Sets ll:Operations 64 Union and Intersection 64 The Size of a Union 66 Difference and Symmetric Difference 68
vi Contents Proving Equations and Inequalities 24 Recap 25 Exercises 25 5 Counterexample 25 Recap 27 Exercises 27 6 Boolean Algebra 27 More Operations 31 Recap 32 Exercises 32 Chapter 1 Self Test 34 2 Collections 37 7 Lists 37 Counting Two-Element Lists 37 Longer Lists 40 Recap 43 Exercises 43 8 Factorial 45 Much Ado About 0! 46 Product Notation 47 Recap 48 Exercises 48 9 Sets 1: Introduction, Subsets 49 Equality of Sets 51 Subset 53 Counting Subsets 55 Power Set 57 Recap 57 Exercises 57 10 Quantifiers 58 There Is 58 For All 59 Negating Quantified Statements 60 Combining Quantifiers 61 Recap 62 Exercises 63 11 Sets II: Operations 64 Union and Intersection 64 The Size of a Union 66 Difference and Symmetric Difference 68
Contents vii Cartesian Product 73 Recap 74 Exercises 74 12 Combinatorial Proof:Two Examples 76 Recap 80 Exercises 80 Chapter 2 Self Test 80 3 Counting and Relations 83 13 Relations 83 Properties of Relations 86 Recap 87 Exercises 87 14 Equivalence Relations 89 Equivalence Classes 92 Recap 95 Exercises 96 15 Partitions 98 Counting Classes/Parts 100 Recap 102 Exercises 102 16 Binomial Coefficients 104 Calculating ( 107 Pascal's Triangle 109 A Formula for() 111 Recap 113 Exercises 113 17 Counting Multisets 117 Multisets 117 Formulas for()） 119 Recap 122 Exercises 122 18 Inclusion-Exclusion 123 How to Use Inclusion-Exclusion 126 Derangements 129 A Ghastly Formula 132 Recap 132 Exercises 132 Chapter 3 Self Test 133
Contents vii Cartesian Product 73 Recap 74 Exercises 7 4 12 Combinatorial Proof: Two Examples 76 Recap 80 Exercises 80 Chapter 2 Self Test 80 3 Counting and Relations 83 13 Relations 83 Properties of Relations 86 Recap 87 Exercises 87 14 Equivalence Relations 89 Equivalence Classes 92 Recap 95 Exercises 96 15 Partitions 98 Counting Classes/Parts 100 Recap 102 Exercises 102 16 Binomial Coefficients 104 Calculating G) 107 Pascal's Triangle 109 A Formula for G) 111 Recap 113 Exercises 113 17 Counting Multisets 117 Multisets 117 Formulas for (G)) 119 Recap 122 Exercises 122 18 Inclusion-Exclusion 123 How to Use Inclusion-Exclusion 126 Derangements 129 A Ghastly Formula 132 Recap 132 Exercises 132 Chapter 3 Self Test 133