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
vili Contents 4 More Proof 135 19 Contradiction 135 Proof by Contrapositive 135 Reductio ad Absurdum 137 A Matter of Style 141 Recap 141 Exercises 141 20 Smallest Counterexample 142 Well-Ordering 148 Recap 153 Exercises 153 And Finally 154 21 Induction 155 The Induction Machine 155 Theoretical Underpinnings 157 Proof by Induction 157 Proving Equations and Inequalities 160 Other Examples 162 Strong Induction 163 A More Complicated Example 165 A Matter of Style 168 Recap 168 Exercises 168 22 Recurrence Relations 171 First-Order Recurrence Relations 172 Second-Order Recurrence Relations 175 The Case of the Repeated Root 178 Sequences Generated by Polynomials 180 Recap 187 Exercises 188 Chapter 4 Self Test 190 5 Functions 193 23 Functions 193 Domain and Image 195 Pictures of Functions 196 Counting Functions 197 Inverse Functions 198 Counting Functions,Again 202 Recap 203 Exercises 203
viii Contents 4 More Proof 135 f 19 Contradiction 135 Proof by Contrapositive 135 Reductio ad Absurdum 137 A Matter of Style 141 Recap 141 Exercises 141 20 Smallest Counterexample 142 Well-Ordering 148 Recap 153 Exercises 153 And Finally 154 21 Induction 155 The Induction Machine 155 Theoretical Underpinnings 157 Proof by Induction 157 Proving Equations and Inequalities 160 Other Examples 162 Strong Induction 163 A More Complicated Example 165 A Matter of Style 168 Recap 168 Exercises 168 22 Recurrence Relations 171 First-Order Recurrence Relations 172 Second-Order Recurrence Relations 175 The Case of the Repeated Root 178 Sequences Generated by Polynomials 180 Recap 187 Exercises 188 Chapter 4 Self Test 190 5 Functions 193 23 Functions 193 Domain and Image 195 Pictures of Functions 196 Counting Functions 197 Inverse Functions 198 Counting Functions, Again 202 Recap 203 Exercises 203
Contents iX 24 The Pigeonhole Principle 205 Cantor's Theorem 208 Recap 210 Exercises 210 25 Composition 211 Identity Function 214 Recap 215 Exercises 215 26 Permutations 216 Cycle Notation 217 Calculations with Permutations 220 Transpositions 221 A Graphical Approach 226 Recap 228 Exercises 228 27 Symmetry 231 Symmetries of a Square 231 Symmetries as Permutations 232 Combining Symmetries 233 Formal Definition of Symmetry 235 Recap 236 Exercises 236 28 Assorted Notation 236 Big oh 236 2 and 239 Little oh 240 Floor and Ceiling 241 Recap 242 Exercises 242 Chapter 5 Self Test 242 6 Probability 245 29 Sample Space 245 Recap 248 Exercises 248 30 Events 249 Combining Events 252 The Birthday Problem 253 Recap 254 Exercises 255
6 24 The Pigeonhole Principle Cantor's Theorem 208 Recap 210 Exercises 210 25 Composition 211 Identity Function 214 Recap 215 Exercises 215 26 Permutations 216 Cycle Notation 217 Calculations with Permutations Transpositions 221 A Graphical Apptoach 226 Recap 228 Exercises 228 27 Symmetry 231 Symmetries of a Square Symmetries as Permutations 231 Combining Symmetries 233 Formal Definition of Symmetry Recap 236 Exercises 236 28 Assorted Notation 236 Big oh 236 Q and e 239 Little oh 240 Floor and Ceiling 241 Recap 242 Exercises 242 Chapter 5 Self Test 242 Probability 245 29 Sample Space 245 Recap 248 Exercises 248 30 Events 249 Combining Events The Birthday Problem Recap 254 Exercises 255 252 253 Contents ix 205 220 232 235
X Contents 31 Conditional Probability and Independence 257 Independence 259 Independent Repeated Trials 261 The Monty Hall Problem 262 Recap 263 Exercises 263 32 Random Variables 266 Random Variables as Events 267 Independent Random Variables 269 Recap 270 Exercises 270 33 Expectation 271 Linearity of Expectation 276 Product of Random Variables 279 Expected Value as a Measure of Centrality 282 Variance 283 Recap 287 Exercises 287 Chapter 6 Self Test 289 7 Number Theory 293 34 Dividing 293 Div and Mod 296 Recap 297 Exercises 297 35 Greatest Common Divisor 298 Calculating the ged 299 Correctness 301 How Fast? 302 An Important Theorem 304 Recap 307 Exercises 307 36 Modular Arithmetic 309 A New Context for Basic Operations 309 Modular Addition and Multiplication 310 Modular Subtraction 311 Modular Division 313 A Note on Notation 318 Recap 318 Exercises 318
x Contents 7 31 Conditional Probability and Independence Independence 259 Independent Repeated Trials The Monty Hall Problem Recap 263 Exercises 263 261 262 32 Random Variables 266 Random Variables as Events Independent Random Variables Recap 270 Exercises 270 33 Expectation 271 Linearity of Expectation 276 267 269 Product of Random Variables 279 Expected Value as a Measure of Centrality 282 Variance 283 Recap 287 Exercises 287 Chapter 6 Self Test 289 Number Theory 293 34 Dividing 293 Div and Mod 296 Recap 297 Exercises 297 35 Greatest Common Divisor 298 Calculating the gcd 299 Correctness 301 How Fast? 302 An Important Theorem 304 Recap 307 Exercises 307 36 Modular Arithmetic 309 A New Context for Basic Operations 309 Modular Addition and Multiplication 310 Modular Subtraction 311 Modular Division 313 A Note on Notation 318 Recap 318 Exercises 318 257 fo
Contents xi 37 The Chinese Remainder Theorem 320 Solving One Equation 320 Solving Two Equations 322 Recap 324 Exercises 324 38 Factoring 325 Infinitely Many Primes 327 A Formula for Greatest Common Divisor 328 Irrationality of√2 329 Recap 331 Exercises 331 Chapter 7 Self Test 335 8 Algebra 337 39 Groups 337 Operations 337 Properties of Operations 338 Groups 340 Examples 342 Recap 345 Exercises 345 40 Group Isomorphism 347 The Same? 347 Cyclic Groups 349 Recap 352 Exercises 352 41 Subgroups 353 Lagrange's Theorem 356 Recap 359 Exercises 359 42 Fermat's Little Theorem 362 First Proof 362 Second Proof 363 Third Proof 366 Euler's Theorem 367 Primality Testing 368 Recap 369 Exercises 369 43 Public Key Cryptography l:Introduction 370 The Problem:Private Communication in Public 370 Factoring 370
Contents xi 37 The Chinese Remainder Theorem 320 Solving One Equation 320 Solving Two Equations 322 Recap 324 Exercises 324 38 Factoring 325 \ Infinitely Many Primes 327 A Formula for Greatest Common Divisor 328 Irrationality of v'2 329 Recap 331 Exercises 3 31 Chapter 7 Self Test 335 8 Algebra 337 39 Groups 337 Operations 337 Properties of Operations 338 Groups 340 Examples 342 Recap 345 Exercises 345 40 Group Isomorphism 347 The Same? 347 Cyclic Groups 349 Recap 352 Exercises 352 41 Subgroups 353 - Lagrange's Theorem 356 Recap 359 \, Exercises 359 42 Fermat's Little Theorem 362 First Proof 362 Second Proof 363 Third Proof 366 Euler's Theorem 367 Primality Testing 368 Recap 369 Exercises 369 43 Public Key Cryptography 1: Introduction 370 The Problem: Private Communication in Public 370 Factoring 370
xii Contents Words to Numbers 371 Cryptography and the Law 373 Recap 373 Exercises 373 44 Public Key Cryptography ll:Rabin's Method 373 Square Roots Modulo n 374 The Encryption and Decryption Procedures 378 Recap 379 Exercises 379 45 Public Key Cryptography Ill:RSA 380 The RSA Encryption and Decryption Functions 381 Security 383 Recap 384 Exercises 384 Chapter 8 Self Test 385 9 Graphs 389 46 Fundamentals of Graph Theory 389 Map Coloring 389 Three Utilities 391 Seven Bridges 391 What Is a Graph? 392 Adjacency 393 A Matter of Degree 394 Further Notation and Vocabulary 396 Recap 397 Exercises 397 47 Subgraphs 399 Induced and Spanning Subgraphs 400 Cliques and Independent Sets 402 Complements 403 Recap 404 Exercises 404 48 Connection 406 Walks 406 Paths 407 Disconnection 410 Recap 411 Exercises 411 49 Trees 413 Cycles 413 Forests and Trees 413
xii Contents Words to Numbers 371 Cryptography and the Law 373 Recap 373 Exercises 373 44 Public Key Cryptography II: Rabin's Method 373 Square Roots Modulo n 374 The Encryption and Decryption Procedures 378 Recap 379 Exercises 379 45 Public Key Cryptography Ill: RSA 380 The RSA Encryption and Decryption Functions 381 Security 383 Recap 384 Exercises 384 Chapter 8 Self Test 385 9 Graphs 389 46 Fundamentals of Graph Theory 389 Map Coloring 389 Three Utilities 391 Seven Bridges 391 What Is a Graph? 392 Adjacency 393 A Matter of Degree 394 Further Notation and Vocabulary 396 Recap 397 Exercises 397 47 Subgraphs 399 Induced and Spanning Subgraphs 400 Cliques and Independent Sets 402 Complements 403 Recap 404 Exercises 404 48 Connection 406 Walks 406 Paths 407 Disconnection 410 Recap 411 Exercises 411 49 Trees 413 Cycles 413 Forests and Trees 413