离散数学（第八版）（英文版）

图书标准信息

• 作者 [美]Richard Johnsonbaugh（理查德 · 约翰逊鲍夫）
• 出版社 电子工业出版社
• 出版时间 2018-07
• 版次 8
• ISBN 9787121344671
• 定价 128.00元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸
• 页数 768页
• 字数 1398千字

【内容简介】

本书从算法分析和问题求解的角度，全面系统地介绍了离散数学的基础概念及相关知识，并在其前一版的基础上进行了修改与扩展。书中通过大量实例，深入浅出地讲解了集合与逻辑，证明，函数、序列与关系，算法，数论，计数方法与鸽巢原理，递推关系，图论，树，网络模型，Boole代数与组合电路，自动机、文法和语言等与计算机科学密切相关的前沿课题，既着重于各部分内容之间的紧密联系，又深入探讨了相关的概念、理论、算法和实际应用。本书内容叙述严谨、推演详尽，各章配有相当数量的习题与书后的提示和答案，为读者迅速掌握相关知识提供了有效的帮助。

【作者简介】

Richard Johnsonbaugh是美国芝加哥DePaul大学的计算机科学、通信与信息系统的Emeritus教授，并在DePaul大学的从事了20年教学工作，之前曾任莫尔豪斯学院和芝加哥州立大学的数学系教师和系主任一职。Johnsonbaugh教授在耶鲁大学获得数学学士学位、硕士学位，并获得俄勒冈大学的数学博士学位以及伊利诺伊大学的计算机硕士学位。Johnsonbaugh教授近期的研究领域包括模式识别、程序设计语言、算法和离散数学，他也是这些领域众多书籍和文章的作者或合著者。Johnsonbaugh教授的几本专著已被译成各种语言出版，他也是美国数学协会的成员。

Richard Johnsonbaugh是美国芝加哥DePaul大学的计算机科学、通信与信息系统的Emeritus教授，并在DePaul大学的从事了20年教学工作，之前曾任莫尔豪斯学院和芝加哥州立大学的数学系教师和系主任一职。Johnsonbaugh教授在耶鲁大学获得数学学士学位、硕士学位，并获得俄勒冈大学的数学博士学位以及伊利诺伊大学的计算机硕士学位。Johnsonbaugh教授近期的研究领域包括模式识别、程序设计语言、算法和离散数学，他也是这些领域众多书籍和文章的作者或合著者。Johnsonbaugh教授的几本专著已被译成各种语言出版，他也是美国数学协会的成员。

【目录】

Contents

1 Sets and Logic 1

1.1 Sets 2

1.2 Propositions 14

1.3 Conditional Propositions and Logical Equivalence 20

1.4 Arguments and Rules of Inference 31

1.5 Quantifiers 36

1.6 Nested Quantifiers 49

Problem-Solving Corner: Quantifiers 57

Chapter 1 Notes 58

Chapter 1 Review 58

Chapter 1 Self-Test 60

Chapter 1 Computer Exercises 60

2 Proofs 62

2.1 Mathematical Systems, Direct Proofs,

and Counterexamples 63

2.2 More Methods of Proof 72

Problem-Solving Corner: Proving Some Properties

of Real Numbers 83

2.3 Resolution Proofs? 85

2.4 Mathematical Induction 88

Problem-Solving Corner: Mathematical Induction 100

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

Chapter 2 Notes 109

Chapter 2 Review 109

Chapter 2 Self-Test 109

Chapter 2 Computer Exercises 110

3 Functions, Sequences, and Relations 111

3.1 Functions 111

Problem-Solving Corner: Functions 128

3.2 Sequences and Strings 129

3.3 Relations 141

3.4 Equivalence Relations 151

Problem-Solving Corner: Equivalence Relations 158

3.5 Matrices of Relations 160

3.6 Relational Databases? 165

Chapter 3 Notes 170

Chapter 3 Review 170

Chapter 3 Self-Test 171

Chapter 3 Computer Exercises 172

4 Algorithms 173

4.1 Introduction 173

4.2 Examples of Algorithms 177

4.3 Analysis of Algorithms 184

Problem-Solving Corner: Design and Analysis

of an Algorithm 202

4.4 Recursive Algorithms 204

Chapter 4 Notes 211

Chapter 4 Review 211

Chapter 4 Self-Test 212

Chapter 4 Computer Exercises 212

5 Introduction to Number Theory 214

5.1 Divisors 214

5.2 Representations of Integers and Integer Algorithms 224

5.3 The Euclidean Algorithm 238

Problem-Solving Corner: Making Postage 249

5.4 The RSA Public-Key Cryptosystem 250

Chapter 5 Notes 252

Chapter 5 Review 253

Chapter 5 Self-Test 253

Chapter 5 Computer Exercises 254

6 Counting Methods and the Pigeonhole

Principle 255

6.1 Basic Principles 255

Problem-Solving Corner: Counting 267

6.2 Permutations and Combinations 269

Problem-Solving Corner: Combinations 281

6.3 Generalized Permutations and Combinations 283

6.4 Algorithms for Generating Permutations and

Combinations 289

6.5 Introduction to Discrete Probability? 297

6.6 Discrete Probability Theory? 301

6.7 Binomial Coefficients and Combinatorial Identities 313

6.8 The Pigeonhole Principle 319

Chapter 6 Notes 324

Chapter 6 Review 324

Chapter 6 Self-Test 325

Chapter 6 Computer Exercises 326

7 Recurrence Relations 327

7.1 Introduction 327

7.2 Solving Recurrence Relations 338

Problem-Solving Corner: Recurrence Relations 350

7.3 Applications to the Analysis of Algorithms 353

7.4 The Closest-Pair Problem? 365

Chapter 7 Notes 370

Chapter 7 Review 371

Chapter 7 Self-Test 371

Chapter 7 Computer Exercises 372

8 Graph Theory 373

8.1 Introduction 373

8.2 Paths and Cycles 384

Problem-Solving Corner: Graphs 395

8.3 Hamiltonian Cycles and the Traveling Salesperson

Problem 396

8.4 A Shortest-Path Algorithm 405

8.5 Representations of Graphs 410

8.6 Isomorphisms of Graphs 415

8.7 Planar Graphs 422

8.8 Instant Insanity? 429

Chapter 8 Notes 433

Chapter 8 Review 434

Chapter 8 Self-Test 435

Chapter 8 Computer Exercises 436

9 Trees 438

9.1 Introduction 438

9.2 Terminology and Characterizations of Trees 445

Problem-Solving Corner: Trees 450

9.3 Spanning Trees 452

9.4 Minimal Spanning Trees 459

9.5 Binary Trees 465

9.6 Tree Traversals 471

9.7 Decision Trees and the Minimum Time for Sorting 477

9.8 Isomorphisms of Trees 483

9.9 Game Trees? 493

Chapter 9 Notes 502

Chapter 9 Review 502

Chapter 9 Self-Test 503

Chapter 9 Computer Exercises 505

10 Network Models 506

10.1 Introduction 506

10.2 A Maximal Flow Algorithm 511

10.3 The Max Flow, Min Cut Theorem 519

10.4 Matching 523

Problem-Solving Corner: Matching 528

Chapter 10 Notes 529

Chapter 10 Review 530

Chapter 10 Self-Test 530

Chapter 10 Computer Exercises 531

11 Boolean Algebras and Combinatorial

Circuits 532

11.1 Combinatorial Circuits 532

11.2 Properties of Combinatorial Circuits 539

11.3 Boolean Algebras 544

Problem-Solving Corner: Boolean Algebras 549

11.4 Boolean Functions and Synthesis of Circuits 551

11.5 Applications 556

Chapter 11 Notes 564

Chapter 11 Review 565

Chapter 11 Self-Test 565

Chapter 11 Computer Exercises 567

12 Automata, Grammars, and Languages 568

12.1 Sequential Circuits and Finite-State Machines 568

12.2 Finite-State Automata 574

12.3 Languages and Grammars 579

12.4 Nondeterministic Finite-State Automata 589

12.5 Relationships Between Languages and Automata 595

Chapter 12 Notes 601

Chapter 12 Review 602

Chapter 12 Self-Test 602

Chapter 12 Computer Exercises 603

Appendix 605

A Matrices 605

B Algebra Review 609

C Pseudocode 620

References 627

Hints and Solutions to Selected Exercises 633

Index 735