离散数学及其应用 第3版PDF电子书下载

Chapter 1 The Logic of Compound Statements 1

1.1 Logical Form and Logical Equivalence 1

1.2 Conditional Statements 17

1.3 Valid and Invalid Arguments 29

1.4 Application:Digital Logic Circuits 43

1.5 Application:Number Systems and Circuits for Addition 57

Chapter 2 The Logic of Quantified Statements 75

2.1 Introduction to Predicates and Quantified Statements Ⅰ 75

2.2 Introduction to Predicates and Quantified Statements Ⅱ 88

2.3 Statements Containing Multiple Quantifiers 97

2.4 Arguments with Quantified Statements 111

Chapter 3 Elementary Number Theory and Methods of Proof 125

3.1 Direct Proof and Counterexample Ⅰ:Introduction 126

3.2 Direct Proof and Counterexample Ⅱ:Rational Numbers 141

3.3 Direct Proof and Counterexample Ⅲ:Divisibility 148

3.4 Direct Proof and Counterexample Ⅳ:Division into Cases and the Quotient-Remainder Theorem 156

3.5 Direct Proof and Counterexample Ⅴ:Floor and Ceiling 164

3.6 Indirect Argument:Contradiction and Contraposition 171

3.7 Two Classical Theorems 179

3.8 Application:Algorithms 186

Chapter 4 Sequences and Mathematical Induction 199

4.1 Sequences 199

4.2 Mathematical Induction Ⅰ 215

4.3 Mathematical Induction Ⅱ 227

4.4 Strong Mathematical Induction and the Well-Ordering Principle 235

4.5 Application:Correctness of Algorithms 244

Chapter 5 Set Theory 255

5.1 Basic Definitions of Set Theory 255

5.2 Properties of Sets 269

5.3 Disproofs,Algebraic Proofs,and Boolean Algebras 282

5.4 Russell's Paradox and the Halting Problem 293

Chapter 6 Counting and Probability 297

6.1 Introduction 298

6.2 Possibility Trees and the Multiplication Rule 306

6.3 Counting Elements of Disjoint Sets:The Addition Rule 321

6.4 Counting Subsets of a Set:Combinations 334

6.5 r-Combinations with Repetition Allowed 349

6.6 The Algebra of Combinations 356

6.7 The Binomial Theorem 362

6.8 Probability Axioms and Expected Value 370

6.9 Conditional Probability,Bayes'Formula,and Independent Events 375

Chapter 7 F unctions 389

7.1 Functions Defined on General Sets 389

7.2 One-to-One and Onto,Inverse Functions 402

7.3 Application:The Pigeonhole Principle 420

7.4 Composition of Functions 431

7.5 Cardinality with Applications to Computability 443

Chapter 8 Recursion 457

8.1 Recursively Defined Sequences 457

8.2 Solving Recurrence Relations by lteration 475

8.3 Second-Order Linear Homogenous Recurrence Relations with Constant Coefficients 487

8.4 General Recursive Definitions 499

Chapter 9 The Efficiency of Algorithms 510

9.1 Real-Valued Functions of a Real Variable and Their Graphs 510

9.2 O,Ω，and？Notations 518

9.3 Application:Efficiency of Algorithms Ⅰ 531

9.4 Exponential and Logarithmic Functions:Graphs and Orders 543

9.5 Application:Efficiency of Algorithms Ⅱ 557

Chapter 10 Relations 571

10.1 Relations on Sets 571

10.2 Reflexivity,Symmetry,and Transitivity 584

10.3 Equivalence Relations 594

10.4 Modular Arithmetic with Applications to Cryptography 611

10.5 Partial Order Relations 632

Chapter 11 Graphs and Trees 649

11.1 Graphs:An Introduction 649

11.2 Paths and Circuits 665

11.3 Matrix Representations of Graphs 683

11.4 Isomorphisms of Graphs 697

11.5 Trees 705

11.6 Spanning Trees 723

Chapter 12 Regular Expressions and Finite-State Automata 734

12.1 Formal Languages and Regular Expressions 735

12.2 Finite-State Automata 745

12.3 Simplifying Finite-State Automata 763