[PDF] Notes on Discrete Mathematics 08-Jun-2022 2 Mathematical

View - Download Notes on Discrete Mathematics

Previous PDF

Next PDF

Notes on Discrete Mathematics

James Aspnes

2022-06-08 10:27

iCopyrightc?2004-2022 by James Aspnes. Distributed under a Creative Com- mons Attribution-ShareAlike 4.0 International license:https://creativecommons. org/licenses/by-sa/4.0/.

Contents

Table of contents

ii

List of figures

xv ii

List of tables

xix

List of algorithms

xx

Preface

xxi

Resources

xxii

1 Introduction

1

1.1 So why do I need to learn all this nasty mathematics?

1

1.2 But isn"t math hard?

2

1.3 Thinking about math with your heart

3

1.4 What you should know about math

3

1.4.1 Foundations and logic

4

1.4.2 Basic mathematics on the real numbers

4

1.4.3 Fundamental mathematical objects

5

1.4.4 Modular arithmetic and polynomials

6

1.4.5 Linear algebra

6

1.4.6 Graphs

6

1.4.7 Counting

7

1.4.8 Probability

7

1.4.9 Tools

8

2 Mathematical logic

9

2.1 The basic picture

9

2.1.1 Axioms, models, and inference rules

9 ii

CONTENTSiii

2.1.2 Consistency

10

2.1.3 What can go wrong

10

2.1.4 The language of logic

11

2.1.5 Standard axiom systems and models

11

2.2 Propositional logic

12

2.2.1 Operations on propositions

13

2.2.1.1 Precedence

15

2.2.2 Truth tables

16

2.2.3 Tautologies and logical equivalence

17

2.2.3.1 Inverses, converses, and contrapositives

21

2.2.3.2 Equivalences involving true and false

21

Example

22

2.2.4 Normal forms

23

2.3 Predicate logic

25

2.3.1 Variables and predicates

26

2.3.2 Quantifiers

27

2.3.2.1 Universal quantifier

27

2.3.2.2 Existential quantifier

27

2.3.2.3 Negation and quantifiers

28

2.3.2.4 Restricting the scope of a quantifier

28

2.3.2.5 Nested quantifiers

29

2.3.2.6 Examples

31

2.3.3 Functions

32

2.3.4 Equality

33

2.3.4.1 Uniqueness

33

2.3.5 Models

34

2.3.5.1 Examples

34

2.4 Proofs

35

2.4.1 Inference Rules

36

2.4.2 Proofs, implication, and natural deduction

38

2.4.2.1 The Deduction Theorem

39

2.4.2.2 Natural deduction

40

2.4.3 Inference rules for equality

40

2.4.4 Inference rules for quantified statements

42

2.5 Proof techniques

43

2.6 Examples of proofs

47

2.6.1 Axioms for even numbers

47

2.6.2 A theorem and its proof

48

2.6.3 A more general theorem

50

2.6.4 Something we can"t prove

51

CONTENTSiv

3 Set theory

52

3.1 Naive set theory

52

3.2 Operations on sets

54

3.3 Proving things about sets

55

3.4 Axiomatic set theory

57

3.5 Cartesian products, relations, and functions

59

3.5.1 Examples of functions

61

3.5.2 Sequences

61

3.5.3 Functions of more (or less) than one argument

62

3.5.4 Composition of functions

62

3.5.5 Functions with special properties

62

3.5.5.1 Surjections

63

3.5.5.2 Injections

63

3.5.5.3 Bijections

63

3.5.5.4 Bijections and counting

63

3.6 Constructing the universe

64

3.7 Sizes and arithmetic

66

3.7.1 Infinite sets

66

3.7.2 Countable sets

68

3.7.3 Uncountable sets

68

3.8 Further reading

69

4 The real numbers

70

4.1 Field axioms

71

4.1.1 Axioms for addition

71

4.1.2 Axioms for multiplication

72

4.1.3 Axioms relating multiplication and addition

74

4.1.4 Other algebras satisfying the field axioms

75

4.2 Order axioms

76

4.3 Least upper bounds

77

4.4 What"s missing: algebraic closure

79

4.5 Arithmetic

79

4.6 Connection between the reals and other standard algebras

80

4.7 Extracting information from reals

82

5 Induction and recursion

83

5.1 Simple induction

83

5.2 Alternative base cases

85

5.3 Recursive definitions work

86

5.4 Other ways to think about induction

86

CONTENTSv

5.5 Strong induction

87

5.5.1 Examples

88

5.6 Recursively-defined structures

89

5.6.1 Functions on recursive structures

90

5.6.2 Recursive definitions and induction

90

5.6.3 Structural induction

91

6 Summation notation

92

6.1 Summations

92

6.1.1 Formal definition

93

6.1.2 Scope

94

6.1.3 Summation identities

95

6.1.4 Choosing and replacing index variables

96

6.1.5 Sums over given index sets

97

6.1.6 Sums without explicit bounds

98

6.1.7 Infinite sums

98

6.1.8 Double sums

99

6.2 Products

99

6.3 Other big operators

100

6.4 Closed forms

101

6.4.1 Some standard sums

101

6.4.2 Guess but verify

103

6.4.3 Ansatzes

103

7 Asymptotic notation

105

7.1 Definitions

105

7.2 Motivating the definitions

105

7.3 Proving asymptotic bounds

106

7.4 General principles for dealing with asymptotic notation

107

7.4.1Remember the difference between big-O, big-Ω, and

big-Θ. . . . . . . . . . . . . . . . . . . . . . . . . . .107

7.4.2 Simplify your asymptotic terms as much as possible

108

7.4.3 Use limits (may require calculus)

108

7.5 Asymptotic notation and summations

109

7.5.1 Pull out constant factors

109

7.5.2 Bound using a known sum

109

7.5.2.1 Geometric series

109

7.5.2.2 Constant series

110

7.5.2.3 Arithmetic series

110

7.5.2.4 Harmonic series

110

CONTENTSvi

7.5.3 Bound part of the sum

111

7.5.4 Integrate

111

7.5.5 Grouping terms

111

7.5.6 An odd sum

111

7.5.7 Final notes

112

7.6 Variations in notation

112

7.6.1 Absolute values

112

7.6.2 Abusing the equals sign

112

8 Number theory

114

8.1 Divisibility

115

8.2 The division algorithm

115

8.3 Modular arithmetic and residue classes

117

8.3.1 Arithmetic on residue classes

117

8.4 Greatest common divisors

119

8.4.1 The Euclidean algorithm for computinggcd(m,n). .120

8.4.2 The extended Euclidean algorithm

120

8.4.2.1 Example

121

8.4.2.2 Applications

121

8.5 The Fundamental Theorem of Arithmetic

123

8.5.1 Unique factorization and gcd

124

8.6 More modular arithmetic

124

8.6.1 Division inZm. . . . . . . . . . . . . . . . . . . . . .124

8.6.2 The Chinese Remainder Theorem

126

8.6.3 The size ofZ?mand Euler"s Theorem. . . . . . . . . . 129

8.7 RSA encryption

130

9 Relations

132

9.1 Representing relations

132

9.1.1 Directed graphs

132

9.1.2 Matrices

133

9.2 Operations on relations

134

9.2.1 Composition

134

9.2.2 Inverses

135

9.3 Classifying relations

135

9.4 Equivalence relations

136

9.4.1 Why we like equivalence relations

138

9.5 Partial orders

138

9.5.1 Drawing partial orders

140

9.5.2 Comparability

140

CONTENTSvii

9.5.3 Lattices

141

9.5.4 Minimal and maximal elements

142

9.5.5 Total orders

143

9.5.5.1 Topological sort

143

9.5.6 Well orders

146

9.6 Closures

148

9.6.1 Examples

150

10 Graphs

152

10.1 Types of graphs

153

10.1.1 Directed graphs

153

10.1.2 Undirected graphs

153

10.1.3 Hypergraphs

154

10.2 Examples of graphs

155

10.3 Local structure of graphs

156

10.4 Some standard graphs

156

10.5 Subgraphs and minors

161

10.6 Graph products

162

10.7 Functions between graphs

163

10.8 Paths and connectivity

164

10.9 Cycles

165

10.10Proving things about graphs

167

10.10.1Paths and simple paths

167

10.10.2The Handshaking Lemma

168

10.10.3Characterizations of trees

168

10.10.4Spanning trees

172

10.10.5Eulerian cycles

172

11 Counting

174

11.1 Basic counting techniques

175

11.1.1 Equality: reducing to a previously-solved case

175

11.1.3 Addition: the sum rule

176

11.1.3.1 For infinite sets

177

11.1.3.2 The Pigeonhole Principle

177

11.1.4 Subtraction

178

11.1.4.1 Inclusion-exclusion for infinite sets

quotesdbs_dbs42.pdfusesText_42

[PDF] 2° fois que je le poste s*v*p T-T 5ème Latin

[PDF] 3 PDF Cours,Exercices ,Examens

[PDF] 3 approches du pib PDF Cours,Exercices ,Examens

[PDF] 3 ARGUMENT pour valoriser le cinéma francais 3ème Français

[PDF] 3 arguments contre la publicité PDF Cours,Exercices ,Examens

[PDF] 3 arguments et 3 exemple sur la ville un paradis A RENDRE DEMAIN !!!!!!!!!!! 3ème Français

[PDF] 3 Arguments pour le téléchargement de la musique sur internet 4ème Allemand

[PDF] 3 arguments sur comment résister ? l'occupant nazi pendant la seconde guerre mondiale 3ème Histoire

[PDF] 3 au cube PDF Cours,Exercices ,Examens

[PDF] 3 Avantages et 3 Inconvenants du recyclage 3ème Autre

[PDF] 3 axes de polarité des vertébrés PDF Cours,Exercices ,Examens

[PDF] 3 bis boulevard de strasbourg toulouse PDF Cours,Exercices ,Examens

[PDF] 3 cercles tangents PDF Cours,Exercices ,Examens

[PDF] 3 EME 4ème Français

[PDF] 3 éme 4ème Mathématiques