A Mathematical Foundation for Computer Science, Preliminary Edition

Description

Undergraduate computer science students need to learn and use the mathematical method of abstraction, definition, and proof, perhaps even earlier than do mathematics students. They deal constantly with formally defined systems beyond those studied in mathematics courses, and must be able reason about them formally in order to write and understand programs. A Mathematical Foundation for Computer Science introduces the mathematical method using examples from computer science, often illustrated by Java-like code. It begins with propositional and predicate logic, introduces number theory, and deals thoroughly with mathematical induction as it relates to recursive definition and recursive algorithms. Later chapters cover combinatorics, probability, graphs and searching, finite-state machines, and a brief introduction to formal language theory. Each chapter is divided into narrative sections, each with Exercises and Problems, and Excursion sections suitable for active learning exercises. This preliminary edition includes the first four chapters, used as the textbook for the first half of a UMass course, COMPSCI 250. Cover Preliminary Edition Contents Full Version Contents Author's Note 1 Sets, Propositions, and Predicates 1.1 Sets #11,0,-1 1.2 Strings and String Operations #20,0,-1 1.3 Excursion: What is a Proof? #29,0,-1 1.4 Propositions and Boolean Operations #33,0,-1 1.5 Set Operations and Propositions About Sets #43,0,-1 1.6 Truth-Table Proofs #54,0,-1 1.7 Rules for Propositional Proofs #61,0,-1 1.8 Propositional Proof Strategies #68,0,-1 1.9 Excursion: A Murder Mystery #74,0,-1 1.10 Predicates #77,0,-1 1.11 Excursion: Translating Predicates #84,0,-1 Glossary for Chapter 1 #87,78,-12 Quantifiers and Predicate Calculus #90,0,-1 2.1 Relations #91,0,-1 2.2 Excursion: Relational Databases #97,0,-1 2.3 Quantifiers #99,0,-1 2.4 Excursion: Translating Quantifiers #106,0,-1 2.5 Operations on Languages #108,0,-1 2.6 Proofs With Quantifiers #114,0,-1 2.7 Excursion: Practicing Proofs #121,29,-1 2.8 Properties of Binary Relations #123,0,-1 2.9 Functions #130,0,-1 2.10 Partial Orders #137,0,-1 2.11 Equivalence Relations #144,0,-1 Glossary for Chapter 2 #151,0,-13 Number Theory 3.1 Divisibility and Primes #155,0,-248 3.2 Excursion: Playing With Numbers #164,0,-248 3.3 Modular Arithmetic #167,0,-248 3.4 There are Infinitely Many Primes #176,0,-248 3.5 The Chinese Remainder Theorem #181,0,-248 3.6 The Fundamental Theorem of Arithmetic #188,0,-248 3.7 Excursion: Expressing Predicates in Number Theory #196,44,-248 3.8 The Ring of Congruence Classes #199,0,-248 3.9 Finite Fields and Modular Exponentiation #205,0,-248 3.10 Excursion: Certificates of Primality #211,0,-248 3.11 The RSA Cryptosystem