Book123

    Free register and download UseNet downloader, then you can FREE Download from UseNet.

    Download without Limit " Technical Discrete Mathematics for Computer Science (Some Notes) " from UseNet for FREE!

More

Discrete Mathematics for Computer Science (Some Notes) by Jean Gallier

These are notes on discrete mathematics for computer scientists. The presentation is somewhat unconventional. Indeed I begin with a discussion of the basic rules of mathematical reasoning and of the notion of proof formalized in a natural deduction system ``a la Prawitz''. The rest of the material is more or less traditional but I emphasize partial functions more than usual (after all, programs may not terminate for all input) and I provide a fairly complete account of the basic concepts of graph theory.

Contents

1 Mathematical Reasoning, Proof Principles and Logic 5

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Inference Rules, Deductions, The Proof Systems N)m and NG)m . . . . . . . 6

1.3 Adding ^, _, ?; The Proof Systems N),^,_,? c and NG),^,_,? c . . . . . . . . . 17

1.4 Clearing Up Differences Between Rules Involving ? . . . . . . . . . . . . . . 24

1.5 Other Rules of Classical Logic and Examples of Proofs . . . . . . . . . . . . 27

1.6 Adding Quantifiers; The Proof Systems N),^,_,8,9,? c , NG),^,_,8,9,? c . . . . . . 31

1.7 Decision Procedures, Proof Normalization, etc. . . . . . . . . . . . . . . . . . 40

1.8 Basics Concepts of Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 46



2 Relations, Functions, Partial Functions 55

2.1 What is a Function? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

2.2 Ordered Pairs, Cartesian Products, Relations, etc. . . . . . . . . . . . . . . . 58

2.3 Induction Principle on N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

2.4 Composition of Relations and Functions . . . . . . . . . . . . . . . . . . . . 64

2.5 Recursion on N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

2.6 Inverses of Functions and Relations . . . . . . . . . . . . . . . . . . . . . . . 68

2.7 Injections, Surjections, Bijections, Permutations . . . . . . . . . . . . . . . . 71

2.8 Direct Image and Inverse Image . . . . . . . . . . . . . . . . . . . . . . . . . 74

2.9 Equinumerosity; Pigeonhole Principle; Schr¨oder–Bernstein . . . . . . . . . . 76

2.10 An Amazing Surjection: Hilbert’s Space Filling Curve . . . . . . . . . . . . . 84

2.11 Strings, Multisets, Indexed Families . . . . . . . . . . . . . . . . . . . . . . . 85

3 Some Counting Problems; Binomial Coefficients 91

3.1 Counting Permutations and Functions . . . . . . . . . . . . . . . . . . . . . 91

3.2 Counting Subsets of Size k; Binomial Coefficients . . . . . . . . . . . . . . . 93

3.3 The Inclusion-Exclusion Principle . . . . . . . . . . . . . . . . . . . . . . . . 100

4 Partial Orders and Equivalence Relations 109

4.1 Partial Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

4.2 Lattices and Tarski’s Fixed Point Theorem . . . . . . . . . . . . . . . . . . . 115

4.3 Well-Founded Orderings and Complete Induction . . . . . . . . . . . . . . . 121

4.4 Unique Prime Factorization in Z and GCD’s . . . . . . . . . . . . . . . . . . 130

4.5 Equivalence Relations and Partitions . . . . . . . . . . . . . . . . . . . . . . 134

4.6 Transitive Closure, Reflexive and Transitive Closure . . . . . . . . . . . . . . 138

4.7 Distributive Lattices, Boolean Algebras, Heyting Algebras . . . . . . . . . . 139



5 Graphs, Basic Notions 149

5.1 Why Graphs? Some Motivations . . . . . . . . . . . . . . . . . . . . . . . . 149

5.2 Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

5.3 Path in Digraphs; Strongly Connected Components . . . . . . . . . . . . . . 155

5.4 Undirected Graphs, Chains, Cycles, Connectivity . . . . . . . . . . . . . . . 163

5.5 Trees and Arborescences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

5.6 Minimum (or Maximum) Weight Spanning Trees . . . . . . . . . . . . . . . . 173

5.7 -Cycles, Cocycles, Cotrees, Flows and Tensions . . . . . . . . . . . . . . . . 178

5.8 Incidence and Adjacency Matrices of a Graph . . . . . . . . . . . . . . . . . 195

5.9 Eulerian and Hamiltonian Cycles . . . . . . . . . . . . . . . . . . . . . . . . 199

5.10 Network Flow Problems; The Max-Flow Min-Cut Theorem . . . . . . . . . . 203

5.11 Matchings, Coverings, Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . 220

5.12 Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230



Buy Book at Lowest Price on Amazon





-<To fans of interesting, necessary and useful books CLICK HERE>-

Rating:
2.5 out of 5 by Book123