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