Cover......Page 1 Preliminary Edition Contents......Page 4 Full Version Contents......Page 6 Author's Note......Page 8 1 Sets, Propositions, and Predicates......Page 10 1.1 Sets......Page 11 1.2 Strings and String Operations......Page 20 1.3 Excursion: What is a Proof?......Page 29 1.4 Propositions and Boolean Operations......Page 33 1.5 Set Operations and Propositions About Sets......Page 43 1.6 Truth-Table Proofs......Page 54 1.7 Rules for Propositional Proofs......Page 61 1.8 Propositional Proof Strategies......Page 68 1.9 Excursion: A Murder Mystery......Page 74 1.10 Predicates......Page 77 1.11 Excursion: Translating Predicates......Page 84 Glossary for Chapter 1......Page 87 2 Quantifiers and Predicate Calculus......Page 90 2.1 Relations......Page 91 2.2 Excursion: Relational Databases......Page 97 2.3 Quantifiers......Page 99 2.4 Excursion: Translating Quantifiers......Page 106 2.5 Operations on Languages......Page 108 2.6 Proofs With Quantifiers......Page 114 2.7 Excursion: Practicing Proofs......Page 121 2.8 Properties of Binary Relations......Page 123 2.9 Functions......Page 130 2.10 Partial Orders......Page 137 2.11 Equivalence Relations......Page 144 Glossary for Chapter 2......Page 151 3 Number Theory......Page 154 3.1 Divisibility and Primes......Page 155 3.2 Excursion: Playing With Numbers......Page 164 3.3 Modular Arithmetic......Page 167 3.4 There are Infinitely Many Primes......Page 176 3.5 The Chinese Remainder Theorem......Page 181 3.6 The Fundamental Theorem of Arithmetic......Page 188 3.7 Excursion: Expressing Predicates in Number Theory......Page 196 3.8 The Ring of Congruence Classes......Page 199 3.9 Finite Fields and Modular Exponentiation......Page 205 3.10 Excursion: Certificates of Primality......Page 211 3.11 The RSA Cryptosystem......Page 214 Glossary for Chapter 3......Page 224 4 Recursion and Proof by Induction......Page 226 4.1 Recursive Definition......Page 227 4.2 Excursion: Recursive Algorithms......Page 235 4.3 Proof By Induction for Naturals......Page 238 4.4 Variations on Induction for Naturals......Page 245 4.5 Excursion: Fibonacci Numbers......Page 252 4.6 Proving the Basic Facts of Arithmetic......Page 255 4.7 Recursive Definition for Strings......Page 262 4.8 Excursion: Naturals and Strings......Page 270 4.9 Graphs and Paths......Page 272 4.10 Trees and Lisp Lists......Page 281 4.11 Induction For Problem Solving......Page 291 Glossary for Chapter 4......Page 300 S.1: Solutions to Exercises From Chapter 1......Page 302 S.2: Solutions to Exercises From Chapter 2......Page 317 S.3: Solutions to Exercises From Chapter 3......Page 333 S.4: Solutions to Exercises From Chapter 4......Page 349
