内容简介

This course is offered to undergraduates and is an elementary discrete mathematics course oriented towards applications in computer science and engineering. Topics covered include: formal logic notation, induction, sets and relations, permutations and combinations, counting principles, and discrete probability.

作品目录

I Proofs

1 Propositions 5

1.1 Compound Propositions 6

1.2 Propositional Logic in Computer Programs 10

1.3 Predicates and Quantifiers 11

1.4 Validity 19

1.5 Satisfiability 21

2 Patterns of Proof 23

2.1 The Axiomatic Method 23

2.2 Proof by Cases 26

2.3 Proving an Implication 27

2.4 Proving an “If and Only If” 30

2.5 Proof by Contradiction 32

2.6 Proofs about Sets 33

2.7 Good Proofs in Practice 40

3 Induction 43

3.1 The Well Ordering Principle 43

3.2 Ordinary Induction 46

3.3 Invariants 56

3.4 Strong Induction 64

3.5 Structural Induction 69

4 Number Theory 81

4.1 Divisibility 81

4.2 The Greatest Common Divisor 87

4.3 The Fundamental Theorem of Arithmetic 94

4.4 Alan Turing 96

4.5 Modular Arithmetic 100

4.6 Arithmetic with a Prime Modulus 103

4.7 Arithmetic with an Arbitrary Modulus 108

4.8 The RSA Algorithm 113

II Structures

5 Graph Theory 121

5.1 Definitions 121

5.2 Matching Problems 128

5.3 Coloring 143

5.4 Getting from A to B in a Graph 147

5.5 Connectivity 151

5.6 Around and Around We Go 156

5.7 Trees 162

5.8 Planar Graphs 170

6 Directed Graphs 189

6.1 Definitions 189

6.2 Tournament Graphs 192

6.3 Communication Networks 196

7 Relations and Partial Orders 213

7.1 Binary Relations 213

7.2 Relations and Cardinality 217

7.3 Relations on One Set 220

7.4 Equivalence Relations 222

7.5 Partial Orders 225

7.6 Posets and DAGs 226

7.7 Topological Sort 229

7.8 Parallel Task Scheduling 232

7.9 Dilworth’s Lemma 235

8 State Machines 237

III Counting

9 Sums and Asymptotics 243

9.1 The Value of an Annuity 244

9.2 Power Sums 250

9.3 Approximating Sums 252

9.4 Hanging Out Over the Edge 257

9.5 Double Trouble 269

9.6 Products 272

9.7 Asymptotic Notation 275

10 Recurrences 283

10.1 The Towers of Hanoi 284

10.2 Merge Sort 291

10.3 Linear Recurrences 294

10.4 Divide-and-Conquer Recurrences 302

10.5 A Feel for Recurrences 309

11 Cardinality Rules 313

11.1 Counting One Thing by Counting Another 313

11.2 Counting Sequences 314

11.3 The Generalized Product Rule 317

11.4 The Division Rule 321

11.5 Counting Subsets 324

11.6 Sequences with Repetitions 326

11.7 Counting Practice: Poker Hands 329

11.8 Inclusion-Exclusion 334

11.9 Combinatorial Proofs 339

11.10 The Pigeonhole Principle 342

11.11 A Magic Trick 346

12 Generating Functions 355

12.1 Definitions and Examples 355

12.2 Operations on Generating Functions 356

12.3 Evaluating Sums 361

12.4 Extracting Coefficients 363

12.5 Solving Linear Recurrences 370

12.6 Counting with Generating Functions 374

13 Infinite Sets 379

13.1 Injections, Surjections, and Bijections 379

13.2 Countable Sets 381

13.3 Power Sets Are Strictly Bigger 384

13.4 Infinities in Computer Science 386

IV Probability

14 Events and Probability Spaces 391

14.1 Let’s Make a Deal 391

14.2 The Four Step Method 392

14.3 Strange Dice 402

14.4 Set Theory and Probability 411

14.5 Infinite Probability Spaces 413

15 Conditional Probability 417

15.1 Definition 417

15.2 Using the Four-Step Method to Determine Conditional Probability 418

15.3 A Posteriori Probabilities 424

15.4 Conditional Identities 427

16 Independence 431

16.1 Definitions 431

16.2 Independence Is an Assumption 432

16.3 Mutual Independence 433

16.4 Pairwise Independence 435

16.5 The Birthday Paradox 438

17 Random Variables and Distributions 445

17.1 Definitions and Examples 445

17.2 Distribution Functions 450

17.3 Bernoulli Distributions 452

17.4 Uniform Distributions 453

17.5 Binomial Distributions 456

18 Expectation 467

18.1 Definitions and Examples 467

18.2 Expected Returns in Gambling Games 477

18.3 Expectations of Sums 483

18.4 Expectations of Products 490

18.5 Expectations of Quotients 492

19 Deviations 497

19.1 Variance 497

19.2 Markov’s Theorem 507

19.3 Chebyshev’s Theorem 513

19.4 Bounds for Sums of Random Variables 516

19.5 Mutually Independent Events 523

20 Random Walks 533

20.1 Unbiased Random Walks 533

20.2 Gambler’s Ruin 542

20.3 Walking in Circles 549