Discrete mathematics for computer science (International version)

List of Theorems, Lemmas, and Corollaries xix
Preface xxi
CHAPTER 1 Counting 1
1.1 Basic Counting 1
The Sum Principle 1
Abstraction 3
Summing Consecutive Integers 3
The Product Principle 4
Two-Element Subsets 6
Important Concepts, Formulas, and Theorems 7
Problems 8
1.2 Counting Lists, Permutations, and Subsets 10
Using the Sum and Product Principles 10
Lists and Functions 12
The Bijection Principle 14
k-Element Permutations of a Set 15
Counting Subsets of a Set 16
Important Concepts, Formulas, and Theorems 18
Problems 20
1.3 Binomial Coefficients 22
Pascal's Triangle 22
A Proof Using the Sum Principle 24
The Binomial Theorem 26
Labeling and Trinomial Coefficients 28
Important Concepts, Formulas, and Theorems 29
Problems 30
1.4 Relations 32
What Is a Relation? 32
Functions as Relations 33
Properties of Relations 33
Equivalence Relations 36
Partial and Total Orders 39
Important Concepts, Formulas, and Theorems 41
Problems 42
1.5 Using Equivalence Relations in Counting 43
The Symmetry Principle 43
Equivalence Relations 45
The Quotient Principle 46
Equivalence Class Counting 46
Multisets 48
The Bookcase Arrangement Problem 50
The Number of k-Element Multisets
of an n-Element Set 51
Using the Quotient Principle to Explain a Quotient 52
Important Concepts, Formulas, and Theorems 53
Problems 54

CHAPTER 2 Cryptography and Number Theory 59
2.1 Cryptography and Modular Arithmetic 59
Introduction to Cryptography 59
Private-Key Cryptography 60
Public-Key Cryptosystems 63
Arithmetic Modulo n 65
Cryptography Using Addition mod n 68
Cryptography Using Multiplication mod n 69
Important Concepts, Formulas, and Theorems 71
Problems 72
2.2 Inverses and Greatest Common Divisors 75
Solutions to Equations and Inverses mod n 75
Inverses mod n 76
Converting Modular Equations to Normal Equations 79
Greatest Common Divisors 80
Euclid's Division Theorem 81
Euclid's GCD Algorithm 84
Extended GCD Algorithm 85
Computing Inverses 88
Important Concepts, Formulas, and Theorems 89
Problems 90
2.3 The RSA Cryptosystem 93
Exponentiation mod n 93
The Rules of Exponents 93
Fermat's Little Theorem 96
The RSA Cryptosystem 97
The Chinese Remainder Theorem 101
Important Concepts, Formulas, and Theorems 102
Problems 104
2.4 Details of the RSA Cryptosystem 106
Practical Aspects of Exponentiation mod n 106
How Long Does It Take to Use the RSA Algorithm? 109
How Hard Is Factoring? 110
Finding Large Primes 110
Important Concepts, Formulas, and Theorems 113
Problems 114

CHAPTER 3 Reflections on Logic and Proof 117
3.1 Equivalence and Implication 117
Equivalence of Statements 117
Truth Tables 120
DeMorgan's Laws 123
Implication 125
If and Only If 126
Important Concepts, Formulas, and Theorems 129
Problems 131
3.2 Variables and Quantifiers 133
Variables and Universes 133
Quantifiers 134
Standard Notation for Quantification 136
Statements about Variables 138
Rewriting Statements to Encompass Larger Universes 138
Proving Quantified Statements True or False 139
Negation of Quantified Statements 140
Implicit Quantification 143
Proof of Quantified Statements 144
Important Concepts, Formulas, and Theorems 145
Problems 147
3.3 Inference 149
Direct Inference (Modus Ponens) and Proofs 149
Rules of Inference for Direct Proofs 151
Contrapositive Rule of Inference 153
Proof by Contradiction 155