A mathematical foundation for computer science

✍ Scribed by Barrington D.M

• Publisher: Kendall Hunt
• Year: 2019
• Tongue: English
• Leaves: 364
• Edition: preliminary edition
• Category: Library

✦ Table of Contents

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