Essentials of discrete mathematics Third Edition = 离散数学概要 第3版PDF|Epub|txt|kindle电子书版本网盘下载

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

Chapter 1 Logical Thinking1

1.1 Formal Logic2

1.1.1 Inquiry Problems2

1.1.2 Connectives and Propositions3

1.1.3 Truth Tables5

1.1.4 Logical Equivalences7

Exercises 1.110

1.2 Propositional Logic15

1.2.1 Tautologies and Contradictions16

1.2.2 Derivation Rules18

1.2.3 Proof Sequences20

1.2.4 Forward-Backward22

Exercises 1.223

1.3 Predicate Logic28

1.3.1 Predicates29

1.3.2 Quantifiers29

1.3.3 Translation31

1.3.4 Negation32

1.3.5 Two Common Constructions34

Exercises 1.335

1.4 Logic in Mathematics42

1.4.1 The Role of Definitions in Mathematics42

1.4.2 Other Types of Mathematical Statements44

1.4.3 Counterexamples45

1.4.4 Axiomatic Systems46

Exercises 1.450

1.5 Methods of Proof54

1.5.1 Direct Proofs55

1.5.2 Proof by Contraposition57

1.5.3 Proof by Contradiction59

Exercises 1.561

Chapter 2 Relational Thinking65

2.1 Graphs66

2.1.1 Edges and Vertices66

2.1.2 Terminology67

2.1.3 Modeling Relationships with Graphs69

Exercises 2.175

2.2 Sets81

2.2.1 Membership and Containment82

2.2.2 New Sets from Old83

2.2.3 Identities86

Exercises 2.288

2.3 Functions92

2.3.1 Definition and Examples93

2.3.2 One-to-One and Onto Functions97

2.3.3 New Functions from Old101

Exercises 2.3103

2.4 Relations and Equivalences107

2.4.1 Definition and Examples108

2.4.2 Graphs of Relations108

2.4.3 Relations vs.Functions109

2.4.4 Equivalence Relations111

2.4.5 Modular Arithmetic114

Exercises 2.4116

2.5 Partial Orderings121

2.5.1 Definition and Examples122

2.5.2 Hasse Diagrams123

2.5.3 Topological Sorting124

2.5.4 Isomorphisms126

2.5.5 Boolean Algebras ？129

Exercises 2.5131

2.6 Graph Theory136

2.6.1 Graphs：Formal Definitions136

2.6.2 Isomorphisms of Graphs137

2.6.3 Degree Counting139

2.6.4 Euler Paths and Circuits140

2.6.5 Hamilton Paths and Circuits141

2.6.6 Trees144

Exercises 2.6147

Chapter 3 Recursive Thinking151

3.1 Recurrence Relations152

3.1.1 Definition and Examples153

3.1.2 The Fibonacci Sequence154

3.1.3 Modeling with Recurrence Relations155

Exercises 3.1159

3.2 Closed-Form Solutions and Induction163

3.2.1 Guessing a Closed-Form Solution164

3.2.2 Polynomial Sequences：Using Differences？165

3.2.3 Inductively Verifying a Solution167

Exercises 3.2171

3.3 Recursive Definitions175

3.3.1 Definition and Examples176

3.3.2 Writing Recursive Definitions180

3.3.3 Recursive Geometry181

3.3.4 Recursive Jokes185

Exercises 3.3185

3.4 Proof by Induction190

3.4.1 The Principle of Induction191

3.4.2 Examples192

3.4.3 Strong Induction197

3.4.4 Structural Induction200

Exercises 3.4202

3.5 Recursive Data Structures205

3.5.1 Lists206

3.5.2 Efficiency210

3.5.3 Binary Search Trees Revisited212

Exercises 3.5213

Chapter 4 Quantitative Thinking219

4.1 Basic Counting Techniques220

4.1.1 Addition220

4.1.2 Multiplication221

4.1.3 Mixing Addition and Multiplication225

Exercises 4.1227

4.2 Selections and Arrangements231

4.2.1 Permutations：The Arrangement Principle232

4.2.2 Combinations：The Selection Principle234

4.2.3 The Binomial Theorem？237

Exercises 4.2239

4.3 Counting with Functions244

4.3.1 One-to-One Correspondences244

4.3.2 The Pigeonhole Principle248

4.3.3 The Generalized Pigeonhole Principle249

4.3.4 Ramsey Theory？250

Exercises 4.3251

4.4 Discrete Probability257

4.4.1 Definitions and Examples257

4.4.2 Applications259

4.4.3 Expected Value262

Exercises 4.4264

4.5 Counting Operations in Algorithms268

4.5.1 Algorithms269

4.5.2 Pseudocode269

4.5.3 Sequences of Operations271

4.5.4 Loops271

4.5.5 Arrays274

4.5.6 Sorting276

Exercises 4.5278

4.6 Estimation283

4.6.1 Growth of Functions283

4.6.2 Estimation Targets288

4.6.3 Properties of Big-？289

Exercises 4.6291

Chapter 5 Analytical Thinking295

5.1 Algorithms296

5.1.1 More Pseudocode296

5.1.2 Preconditions and Postconditions298

5.1.3 Iterative Algorithms300

5.1.4 Functions and Recursive Algorithms301

Exercises 5.1305

5.2 Three Common Types of Algorithms309

5.2.1 Traversal Algorithms310

5.2.2 Greedy Algorithms314

5.2.3 Divide-and-Conquer Algorithms317

Exercises 5.2320

5.3 Algorithm Complexity325

5.3.1 The Good，the Bad，and the Average326

5.3.2 Approximate Complexity Calculations330

Exercises 5.3333

5.4 Bounds on Complexity339

5.4.1 Algorithms as Decisions339

5.4.2 A Lower Bound342

5.4.3 Searching an Array343

5.4.4 Sorting344

5.4.5 P vs.NP345

Exercises 5.4346

5.5 Program Verification350

5.5.1 Verification vs.Testing351

5.5.2 Verifying Recursive Algorithms351

5.5.3 Searching and Sorting354

5.5.4 Towers of Hanoi356

Exercises 5.5358

5.6 Loop Invariants362

5.6.1 Verifying Iterative Algorithms363

5.6.2 Searching and Sorting366

5.6.3 Using Invariants to Design Algorithms370

Exercises 5.6371

Chapter 6 Thinking Through Applications377

6.1 Patterns in DNA378

6.1.1 Mutations and Phylogenetic Distance379

6.1.2 Phylogenetic Trees380

6.1.3 UPGMA382

Exercises 6.1386

6.2 Social Networks388

6.2.1 Definitions and Terminology388

6.2.2 Notions of Equivalence390

6.2.3 Hierarchical Clustering394

6.2.4 Signed Graphs and Balance396

Exercises 6.2400

6.3 Structure of Languages402

6.3.1 Terminology403

6.3.2 Finite-State Machines404

6.3.3 Recursion407

6.3.4 Further Issues in Linguistics411

Exercises 6.3412

6.4 Discrete-Time Population Models414

6.4.1 Recursive Models for Population Growth415

6.4.2 Fixed Points，Equilibrium，and Chaos417

6.4.3 Predator-Prey Systems419

6.4.4 The SIR Model421

Exercises 6.4423

6.5 Twelve-Tone Music426

6.5.1 Twelve-Tone Composition426

6.5.2 Listing All Permutations427

6.5.3 Transformations of Tone Rows429

6.5.4 Equivalence Classes and Symmetry430

Exercises 6.5432

Hints，Answers，and Solutions to Selected Exercises435

1.1 Formal Logic435

1.2 Propositional Logic437

1.3 Predicate Logic439

1.4 Logic in Mathematics441

1.5 Methods of Proof442

2.1 Graphs444

2.2 Sets445

2.3 Functions446

2.4 Relations and Equivalences448

2.5 Partial Orderings450

2.6 Graph Theory453

3.1 Recurrence Relations454

3.2 Closed-Form Solutions and Induction455

3.3 Recursive Definitions458

3.4 Proof by Induction459

3.5 Recursive Data Structures462

4.1 Basic Counting Techniques463

4.2 Selections and Arrangements464

4.3 Counting with Functions465

4.4 Discrete Probability466

4.5 Counting Operations in Algorithms467

4.6 Estimation469

5.1 Algorithms470

5.2 Three Common Types of Algorithms471

5.3 Algorithm Complexity473

5.4 Bounds on Complexity474

5.5 Program Verification475

5.6 Loop Invariants476

Selected References479

Index483

Index of Symbols491