本書從算法分析和問題求解的角度，全面系統地介紹了離散數學的基礎概念及相關知識，并在其前一版的基礎上進行了修改與擴展。書中通過大量實例，深入淺出地講解了集合與邏輯，證明，函數、序列與關系，算法，數論，計數方法與鴿巢原理，遞推關系，圖論，樹，網絡模型，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
書單推薦
