Page 4 - Discrete Mathematics and Its Applications

Contents

About the Author vi
Preface vii
The Companion Website xvi
To the Student xvii

1 The Foundations: Logic and Proofs .................................. 1

1.1 Propositional Logic ............................................................ 1
1.2 Applications of Propositional Logic.............................................16
1.3 Propositional Equivalences .................................................... 25
1.4 Predicates and Quantifiers ..................................................... 36
1.5 Nested Quantifiers ............................................................ 57
1.6 Rules of Inference ............................................................ 69
1.7 Introduction to Proofs ......................................................... 80
1.8 Proof Methods and Strategy....................................................92
End-of-Chapter Material ..................................................... 109

2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices .115
2.1 Sets ........................................................................ 115
2.2 Set Operations...............................................................127
2.3 Functions ................................................................... 138
2.4 Sequences and Summations...................................................156
2.5 Cardinality of Sets ........................................................... 170
2.6 Matrices .................................................................... 177
End-of-Chapter Material ..................................................... 185

3 Algorithms ........................................................ 191
3.1 Algorithms .................................................................. 191
3.2 The Growth of Functions ..................................................... 204
3.3 Complexity of Algorithms .................................................... 218
End-of-Chapter Material ..................................................... 232

4 Number Theory and Cryptography................................237

4.1 Divisibility and Modular Arithmetic ........................................... 237
4.2 Integer Representations and Algorithms ........................................ 245
4.3 Primes and Greatest Common Divisors ........................................ 257
4.4 Solving Congruences.........................................................274
4.5 Applications of Congruences..................................................287
4.6 Cryptography ............................................................... 294
End-of-Chapter Material ..................................................... 306

iii