离散数学 英文版PDF电子书下载

1 Sets and Logic 1

1.1 Sets 2

1.2 Propositions 14

1.3 Conditional Propositions and Logical Equivalence 21

1.4 Arguments and Rules of Inference 31

1.5 Quantifiers 36

1.6 Nested Quantifiers 51

Problem-Solving Corner:Quantifiers 60

Notes 62

Chapter Review 62

Chapter Self-Test 63

Computer Exercises 64

2 Proofs 66

2.1 Mathematical Systems,Direct Proofs,and Counterexamples 67

2.2 More Methods of Proof 76

Problem-Solving Corner:Proving Some Properties of Real Numbers 87

2.3 Resolution Proofs 90

2.4 Mathematical Induction 93

Problem-Solving Corner:Mathematical Induction 106

2.5 Strong Form of Induction and the Well-Ordering Property 108

Notes 115

Chapter Review 115

Chapter Self-Test 116

Computer Exercises 116

3 Functions,Sequences,and Relations 117

3.1 Functions 117

Problem-Solving Corner:Functions 135

3.2 Sequences and Strings 136

3.3 Relations 148

3.4 Equivalence Relations 159

Problem-Solving Corner:Equivalence Relations 166

3.5 Matrices of Relations 168

3.6 Relational Databases 173

Notes 178

Chapter Review 178

Chapter Self-Test 179

Computer Exercises 180

4 Algorithms 181

4.1 Introduction 181

4.2 Examples of Algorithms 186

4.3 Analysis of Algorithms 193

Problem-Solving Corner:Design and Analysis of an Algorithm 211

4.4 Recursive Algorithms 213

Notes 220

Chapter Review 221

Chapter Self-Test 221

Computer Exercises 222

5 Introduction to Number Theory 223

5.1 Divisors 223

5.2 Representations of Integers and Integer Algorithms 234

5.3 The Euclidean Algorithm 248

Problem-Solving Corner:Making Postage 259

5.4 The RSA Public-Key Cryptosystem 260

Notes 263

Chapter Review 263

Chapter Self-Test 263

Computer Exercises 264

6 Counting Methods and the Pigeonhole Principle 265

6.1 Basic Principles 265

Problem-Solving Corner:Counting 277

6.2 Permutations and Combinations 278

Problem-Solving Corner:Combinations 291

6.3 Generalized Permutations and Combinations 293

6.4 Algorithms for Generating Permutations and Combinations 299

6.5 Introduction to Discrete Probability 305

6.6 Discrete Probability Theory 309

6.7 Binomial Coefficients and Combinatorial Identities 320

6.8 The Pigeonhole Principle 325

Notes 330

Chapter Review 330

Chapter Self-Test 330

Computer Exercises 332

7 Recurrence Relations 333

7.1 Introduction 333

7.2 Solving Recurrence Relations 345

Problem-Solving Corner:Recurrence Relations 358

7.3 Applications to the Analysis of Algorithms 361

Notes 373

Chapter Review 373

Chapter Self-Test 374

Computer Exercises 374

8 Graph Theory 376

8.1 Introduction 377

8.2 Paths and Cycles 388

Problem-Solving Corner:Graphs 399

8.3 Hamiltonian Cycles and the Traveling Salesperson Problem 400

8.4 A Shortest-Path Algorithm 407

8.5 Representations of Graphs 412

8.6 Isomorphisms of Graphs 417

8.7 Planar Graphs 425

8.8 Instant Insanity 431

Notes 435

Chapter Review 436

Chapter Self-Test 437

Computer Exercises 438

9 Trees 440

9.1 Introduction 440

9.2 Terminology and Characterizations of Trees 448

Problem-Solving Corner:Trees 453

9.3 Spanning Trees 454

9.4 Minimal Spanning Trees 461

9.5 Binary Trees 467

9.6 Tree Traversals 474

9.7 Decision Trees and the Minimum Time for Sorting 480

9.8 Isomorphisms of Trees 486

9.9 Game Trees 496

Notes 505

Chapter Review 505

Chapter Self-Test 506

Computer Exercises 508

10 Network Models 510

10.1 Introduction 510

10.2 A Maximal Flow Algorithm 516

10.3 The Max Flow,Min Cut Theorem 524

10.4 Matching 528

Problem-Solving Corner:Matching 533

Notes 534

Chapter Review 535

Chapter Self-Test 536

Computer Exercises 536

11 Boolean Algebras and Combinatorial Circuits 537

11.1 Combinatorial Circuits 537

11.2 Properties of Combinatorial Circuits 544

11.3 Boolean Algebras 549

Problem-Solving Corner:Boolean Algebras 554

11.4 Boolean Functions and Synthesis of Circuits 556

11.5 Applications 561

Notes 570

Chapter Review 570

Chapter Self-Test 571

Computer Exercises 572

12 Automata,Grammars,and Languages 573

12.1 Sequential Circuits and Finite-State Machines 573

12.2 Finite-State Automata 579

12.3 Languages and Grammars 585

12.4 Nondeterministic Finite-State Automata 595

12.5 Relationships Between Languages and Automata 602

Notes 608

Chapter Review 609

Chapter Self-Test 609

Computer Exercises 611

13 Computational Geometry 612

13.1 The Closest-Pair Problem 612

13.2 An Algorithm to Compute the Convex Hull 617

Notes 625

Chapter Review 625

Chapter Self-Test 625

Computer Exercises 626

Appendix 627

A Matrices 627

B Algebra Review 631

C Pseudocode 644

References 650

Hints and Solutions to Selected Exercises 655

Index 754