离散数学及其应用 英文版 第4版PDF电子书下载

1 The Foundations : Logic,Sets,and Functions 1

Index of Biographies 1

Suggested Readings 1

A.1 Exponential and Logarithmic Functions 1

Appendixes 1

LIST OF SYMBOLS 1

1．1 Logic 1

Index 3

A.2 Pseudocode 5

1．2Propositional Equivalences 14

1．3 Predicates and Quantifiers 21

1．4 Sets 38

1．5 Set Operations 46

1．6 Functions 56

1．7Sequences and Summations 69

1．8 The Growth of Functions 80

Key Terms and Results 92

Review Questions 94

Supplementary Exercises 95

Writing Projects 97

Computer Projects 97

Computations and Explorations 97

2 The Fundamentals : Algorithms,the Integers,and Matrices 99

2．1 Algorithms 99

2．2 Complexity of Algorithms 105

2．3 The Integers and Division 112

2．4 Integers and Algorithms 127

2．5 Applications of Number Theory 137

2.6 Matrices 150

Key Terms and Results 161

Review Questions 162

Supplementary Exercises 163

Computer Projects 164

Writing Projects 165

Computations and Expl165orations 165

3 Mathematical Reasoning 167

3．1 Methods of Proof 167

3．2 Mathematical Induction 186

3．3 Recursive Definitions 202

3．4 Recursive Algorithms 214

3．5 Program Correctness 219

Key Terms and Results 225

Review Questions 226

Supplementary Exercises 227

Computer Projects 229

Writing Projects 230

Computations and Explorations 230

4 Counting 232

4．1 The Basics of Counting 232

4．2 The Pigeonhole Principle 244

4．3 Permutations and Combinations 250

4．4 Discrete Probability 260

4．5 Probability Theory 267

4．6 Generalized Permutations and Combinations 286

4．7 Generating Permutations and Combinations 296

Key Terms and Concept 301

Review Questions 302

Supplementary Exercises 303

Computations and Explorations 306

Computer Projects 306

Writing Projects 307

5．1 Recurrence Relations 308

5 Advanced Counting Techniques 308

5．2 Solving Recurrence Relations 319

5．3 Divide-and-Conquer Relations 332

5．4 Generating Functions 338

5．5 Inclusion-Exclusion 354

5．6 Applications of Inclusion-Exclusion 360

Key Terms and Results 368

Review Questions 369

Supplementary Exercises 369

Computer Projects 371

Writing Projects 372

Computations and Explorations 372

6．1 Relations and Their Properties 374

6 Relations 374

6．2 n-ary Relations and Their Applications 384

6．3 Representing Relations 390

6．4 Closures of Relations 396

6．5 Equivalence Relations 408

6．6 Partial Orderings 415

Key Terms and Results 430

Review Questions 431

Supplementary Exercises 432

Writing Projects 436

Computations and Explorations 436

Computer Projects 436

7．1 Introduction to Graphs 438

7 Graphs 438

7．2 Graph Terminology 445

7．3 Representing Graphs and Graph Isomorphism 456

7．4 Connectivity 467

7．5 Euler and Hamilton Paths 475

7．6 Shortest Path Problems 490

7．7 Planar Graphs 501

7．8 Graph Coloring 510

Key Terms and Results 519

Review Questions 521

Supplementary Exercises 522

Computer Projects 525

Computations and Explorations 526

Writing Projects 527

8 Trees 528

8．1 Introduction to Trees 528

8．2 Applications of Trees 541

8．3 Tree Traversal 547

8．4 Trees and Sorting 562

8．5 Spanning Trees 570

8．6 Minimum Spanning Trees 580

Key Terms and Results 587

Supplementary Exercises 588

Review Questions 588

Computations and Explorations 591

Computer Projects 591

Writing Projects 592

9 Boolean Algebra 593

9．1 Boolean Functions 593

9．2 Representing Boolean Functions 600

9．3 Logic Gates 604

9．4 Minimization of Circuits 611

Key Terms and Results 625

Review Questions 625

Supplementary Exercises 626

Computer Projects 627

Writing Projects 628

Computations and Explorations 628

10．1 Languages and Grammars 629

10 Modeling Computation 629

10．2 Finite-State Machines with Output 640

10．3 Finite-Satae Machines with No Output 647

10．4 Language Recognition 656

10．5 Turing Machines 666

Key Terms and Results 674

Supplementary Exercises 675

Review Questions 675

Computer Projects 677

Writing Projects 678

Computations and Explorations 678