Essentials of discrete mathematics Third Edition = 离散数学概要 第3版PDF电子书下载

Chapter 1 Logical Thinking 1

1.1 Formal Logic 2

1.1.1 Inquiry Problems 2

1.1.2 Connectives and Propositions 3

1.1.3 Truth Tables 5

1.1.4 Logical Equivalences 7

Exercises 1.1 10

1.2 Propositional Logic 15

1.2.1 Tautologies and Contradictions 16

1.2.2 Derivation Rules 18

1.2.3 Proof Sequences 20

1.2.4 Forward-Backward 22

Exercises 1.2 23

1.3 Predicate Logic 28

1.3.1 Predicates 29

1.3.2 Quantifiers 29

1.3.3 Translation 31

1.3.4 Negation 32

1.3.5 Two Common Constructions 34

Exercises 1.3 35

1.4 Logic in Mathematics 42

1.4.1 The Role of Definitions in Mathematics 42

1.4.2 Other Types of Mathematical Statements 44

1.4.3 Counterexamples 45

1.4.4 Axiomatic Systems 46

Exercises 1.4 50

1.5 Methods of Proof 54

1.5.1 Direct Proofs 55

1.5.2 Proof by Contraposition 57

1.5.3 Proof by Contradiction 59

Exercises 1.5 61

Chapter 2 Relational Thinking 65

2.1 Graphs 66

2.1.1 Edges and Vertices 66

2.1.2 Terminology 67

2.1.3 Modeling Relationships with Graphs 69

Exercises 2.1 75

2.2 Sets 81

2.2.1 Membership and Containment 82

2.2.2 New Sets from Old 83

2.2.3 Identities 86

Exercises 2.2 88

2.3 Functions 92

2.3.1 Definition and Examples 93

2.3.2 One-to-One and Onto Functions 97

2.3.3 New Functions from Old 101

Exercises 2.3 103

2.4 Relations and Equivalences 107

2.4.1 Definition and Examples 108

2.4.2 Graphs of Relations 108

2.4.3 Relations vs.Functions 109

2.4.4 Equivalence Relations 111

2.4.5 Modular Arithmetic 114

Exercises 2.4 116

2.5 Partial Orderings 121

2.5.1 Definition and Examples 122

2.5.2 Hasse Diagrams 123

2.5.3 Topological Sorting 124

2.5.4 Isomorphisms 126

2.5.5 Boolean Algebras ？ 129

Exercises 2.5 131

2.6 Graph Theory 136

2.6.1 Graphs：Formal Definitions 136

2.6.2 Isomorphisms of Graphs 137

2.6.3 Degree Counting 139

2.6.4 Euler Paths and Circuits 140

2.6.5 Hamilton Paths and Circuits 141

2.6.6 Trees 144

Exercises 2.6 147

Chapter 3 Recursive Thinking 151

3.1 Recurrence Relations 152

3.1.1 Definition and Examples 153

3.1.2 The Fibonacci Sequence 154

3.1.3 Modeling with Recurrence Relations 155

Exercises 3.1 159

3.2 Closed-Form Solutions and Induction 163

3.2.1 Guessing a Closed-Form Solution 164

3.2.2 Polynomial Sequences：Using Differences？ 165

3.2.3 Inductively Verifying a Solution 167

Exercises 3.2 171

3.3 Recursive Definitions 175

3.3.1 Definition and Examples 176

3.3.2 Writing Recursive Definitions 180

3.3.3 Recursive Geometry 181

3.3.4 Recursive Jokes 185

Exercises 3.3 185

3.4 Proof by Induction 190

3.4.1 The Principle of Induction 191

3.4.2 Examples 192

3.4.3 Strong Induction 197

3.4.4 Structural Induction 200

Exercises 3.4 202

3.5 Recursive Data Structures 205

3.5.1 Lists 206

3.5.2 Efficiency 210

3.5.3 Binary Search Trees Revisited 212

Exercises 3.5 213

Chapter 4 Quantitative Thinking 219

4.1 Basic Counting Techniques 220

4.1.1 Addition 220

4.1.2 Multiplication 221

4.1.3 Mixing Addition and Multiplication 225

Exercises 4.1 227

4.2 Selections and Arrangements 231

4.2.1 Permutations：The Arrangement Principle 232

4.2.2 Combinations：The Selection Principle 234

4.2.3 The Binomial Theorem？ 237

Exercises 4.2 239

4.3 Counting with Functions 244

4.3.1 One-to-One Correspondences 244

4.3.2 The Pigeonhole Principle 248

4.3.3 The Generalized Pigeonhole Principle 249

4.3.4 Ramsey Theory？ 250

Exercises 4.3 251

4.4 Discrete Probability 257

4.4.1 Definitions and Examples 257

4.4.2 Applications 259

4.4.3 Expected Value 262

Exercises 4.4 264

4.5 Counting Operations in Algorithms 268

4.5.1 Algorithms 269

4.5.2 Pseudocode 269

4.5.3 Sequences of Operations 271

4.5.4 Loops 271

4.5.5 Arrays 274

4.5.6 Sorting 276

Exercises 4.5 278

4.6 Estimation 283

4.6.1 Growth of Functions 283

4.6.2 Estimation Targets 288

4.6.3 Properties of Big-？ 289

Exercises 4.6 291

Chapter 5 Analytical Thinking 295

5.1 Algorithms 296

5.1.1 More Pseudocode 296

5.1.2 Preconditions and Postconditions 298

5.1.3 Iterative Algorithms 300

5.1.4 Functions and Recursive Algorithms 301

Exercises 5.1 305

5.2 Three Common Types of Algorithms 309

5.2.1 Traversal Algorithms 310

5.2.2 Greedy Algorithms 314

5.2.3 Divide-and-Conquer Algorithms 317

Exercises 5.2 320

5.3 Algorithm Complexity 325

5.3.1 The Good，the Bad，and the Average 326

5.3.2 Approximate Complexity Calculations 330

Exercises 5.3 333

5.4 Bounds on Complexity 339

5.4.1 Algorithms as Decisions 339

5.4.2 A Lower Bound 342

5.4.3 Searching an Array 343

5.4.4 Sorting 344

5.4.5 P vs.NP 345

Exercises 5.4 346

5.5 Program Verification 350

5.5.1 Verification vs.Testing 351

5.5.2 Verifying Recursive Algorithms 351

5.5.3 Searching and Sorting 354

5.5.4 Towers of Hanoi 356

Exercises 5.5 358

5.6 Loop Invariants 362

5.6.1 Verifying Iterative Algorithms 363

5.6.2 Searching and Sorting 366

5.6.3 Using Invariants to Design Algorithms 370

Exercises 5.6 371

Chapter 6 Thinking Through Applications 377

6.1 Patterns in DNA 378

6.1.1 Mutations and Phylogenetic Distance 379

6.1.2 Phylogenetic Trees 380

6.1.3 UPGMA 382

Exercises 6.1 386

6.2 Social Networks 388

6.2.1 Definitions and Terminology 388

6.2.2 Notions of Equivalence 390

6.2.3 Hierarchical Clustering 394

6.2.4 Signed Graphs and Balance 396

Exercises 6.2 400

6.3 Structure of Languages 402

6.3.1 Terminology 403

6.3.2 Finite-State Machines 404

6.3.3 Recursion 407

6.3.4 Further Issues in Linguistics 411

Exercises 6.3 412

6.4 Discrete-Time Population Models 414

6.4.1 Recursive Models for Population Growth 415

6.4.2 Fixed Points，Equilibrium，and Chaos 417

6.4.3 Predator-Prey Systems 419

6.4.4 The SIR Model 421

Exercises 6.4 423

6.5 Twelve-Tone Music 426

6.5.1 Twelve-Tone Composition 426

6.5.2 Listing All Permutations 427

6.5.3 Transformations of Tone Rows 429

6.5.4 Equivalence Classes and Symmetry 430

Exercises 6.5 432

Hints，Answers，and Solutions to Selected Exercises 435

1.1 Formal Logic 435

1.2 Propositional Logic 437

1.3 Predicate Logic 439

1.4 Logic in Mathematics 441

1.5 Methods of Proof 442

2.1 Graphs 444

2.2 Sets 445

2.3 Functions 446

2.4 Relations and Equivalences 448

2.5 Partial Orderings 450

2.6 Graph Theory 453

3.1 Recurrence Relations 454

3.2 Closed-Form Solutions and Induction 455

3.3 Recursive Definitions 458

3.4 Proof by Induction 459

3.5 Recursive Data Structures 462

4.1 Basic Counting Techniques 463

4.2 Selections and Arrangements 464

4.3 Counting with Functions 465

4.4 Discrete Probability 466

4.5 Counting Operations in Algorithms 467

4.6 Estimation 469

5.1 Algorithms 470

5.2 Three Common Types of Algorithms 471

5.3 Algorithm Complexity 473

5.4 Bounds on Complexity 474

5.5 Program Verification 475

5.6 Loop Invariants 476

Selected References 479

Index 483

Index of Symbols 491