viii
Contents
1.7 Mathematical Induction 45
1.71 A First Form of Induction 45
1.72 A Template for Constructing Proofs by Induction 49
1.73 Application: Fibonacci Numbers 51
1.74 Application: Size of a Power Set 53
1.75 Application: Geometric Series 54
1.8 Program Correctness 56
1.8.1 Pseudocode Conventions 56
1.8.2 An Algorithm to Generate Perfect Squares 58
1.8.3 Two Algorithms for Computing Square Roots 58
1.9 Exercises 62
1.10 Strong Form of Mathematical Induction 66
1.10.1 Using the Strong Form of Mathematical Induction 69
1.10.2 Application: Algorithm to Compute Powers 72
1.10.3 Application: Finding Factorizations 75
1.10.4 Application: Binary Search 77
1.11 Exercises 79
1.12 Chapter Review 81
1.12.1 Summary 82
1.12.2 Starting to Review 84
1.12.3 Review Questions 85
1.12.4 Using Discrete Mathematics in Computer Science 87
CHAPTER 2
Formal Logic
89
2.1 Introduction to Propositional Logic 89
2.1.1 Formulas 92
2.1.2 Expression Trees for Formulas 94
2.1.3 Abbreviated Notation for Formulas 97
2.1.4 Using Gates to Represent Formulas 98
2.2 Exercises 99
2.3 Truth and Logical Truth 102
2.3.1 Tautologies 106