《离散数学及其应用 英文版 第4版》

1 The Foundations : Logic,Sets,and Functions1

Index of Biographies1

Suggested Readings1

A.1 Exponential and Logarithmic Functions1

Appendixes1

LIST OF SYMBOLS1

1．1 Logic1

Index3

A.2 Pseudocode5

1．2Propositional Equivalences14

1．3 Predicates and Quantifiers21

1．4 Sets38

1．5 Set Operations46

1．6 Functions56

1．7Sequences and Summations69

1．8 The Growth of Functions80

Key Terms and Results92

Review Questions94

Supplementary Exercises95

Writing Projects97

Computer Projects97

Computations and Explorations97

2 The Fundamentals : Algorithms,the Integers,and Matrices99

2．1 Algorithms99

2．2 Complexity of Algorithms105

2．3 The Integers and Division112

2．4 Integers and Algorithms127

2．5 Applications of Number Theory137

2.6 Matrices150

Key Terms and Results161

Review Questions162

Supplementary Exercises163

Computer Projects164

Writing Projects165

Computations and Expl165orations165

3 Mathematical Reasoning167

3．1 Methods of Proof167

3．2 Mathematical Induction186

3．3 Recursive Definitions202

3．4 Recursive Algorithms214

3．5 Program Correctness219

Key Terms and Results225

Review Questions226

Supplementary Exercises227

Computer Projects229

Writing Projects230

Computations and Explorations230

4 Counting232

4．1 The Basics of Counting232

4．2 The Pigeonhole Principle244

4．3 Permutations and Combinations250

4．4 Discrete Probability260

4．5 Probability Theory267

4．6 Generalized Permutations and Combinations286

4．7 Generating Permutations and Combinations296

Key Terms and Concept301

Review Questions302

Supplementary Exercises303

Computations and Explorations306

Computer Projects306

Writing Projects307

5．1 Recurrence Relations308

5 Advanced Counting Techniques308

5．2 Solving Recurrence Relations319

5．3 Divide-and-Conquer Relations332

5．4 Generating Functions338

5．5 Inclusion-Exclusion354

5．6 Applications of Inclusion-Exclusion360

Key Terms and Results368

Review Questions369

Supplementary Exercises369

Computer Projects371

Writing Projects372

Computations and Explorations372

6．1 Relations and Their Properties374

6 Relations374

6．2 n-ary Relations and Their Applications384

6．3 Representing Relations390

6．4 Closures of Relations396

6．5 Equivalence Relations408

6．6 Partial Orderings415

Key Terms and Results430

Review Questions431

Supplementary Exercises432

Writing Projects436

Computations and Explorations436

Computer Projects436

7．1 Introduction to Graphs438

7 Graphs438

7．2 Graph Terminology445

7．3 Representing Graphs and Graph Isomorphism456

7．4 Connectivity467

7．5 Euler and Hamilton Paths475

7．6 Shortest Path Problems490

7．7 Planar Graphs501

7．8 Graph Coloring510

Key Terms and Results519

Review Questions521

Supplementary Exercises522

Computer Projects525

Computations and Explorations526

Writing Projects527

8 Trees528

8．1 Introduction to Trees528

8．2 Applications of Trees541

8．3 Tree Traversal547

8．4 Trees and Sorting562

8．5 Spanning Trees570

8．6 Minimum Spanning Trees580

Key Terms and Results587

Supplementary Exercises588

Review Questions588

Computations and Explorations591

Computer Projects591

Writing Projects592

9 Boolean Algebra593

9．1 Boolean Functions593

9．2 Representing Boolean Functions600

9．3 Logic Gates604

9．4 Minimization of Circuits611

Key Terms and Results625

Review Questions625

Supplementary Exercises626

Computer Projects627

Writing Projects628

Computations and Explorations628

10．1 Languages and Grammars629

10 Modeling Computation629

10．2 Finite-State Machines with Output640

10．3 Finite-Satae Machines with No Output647

10．4 Language Recognition656

10．5 Turing Machines666

Key Terms and Results674

Supplementary Exercises675

Review Questions675

Computer Projects677

Writing Projects678

Computations and Explorations678