This book teaches two different sorts of things, woven together. It teaches you how to read and write mathematical proofs. It provides a survey of basic mathematical objects, notation, and techniques which will be useful in later computer science courses. These include propositional and predicate logic, sets, functions, relations, modular arithmetic, counting, graphs, and trees. And, finally, it gives a brief introduction to some key topics in theoretical computer science: algorithm analysis and complexity, automata theory, and computability.

This book is designed for students who have taken an introductory programming class of the sort intended for scientists or engineers. Algorithms will be presented in “pseudo-code,” so it does not matter which programming language you have used. But you should have written programs that manipulate the contents of arrays e.g. sort an array of numbers. You should also have written programs that are recursive, i.e. in which a function (aka procedure aka method) calls itself.

We’ll also assume that you have taken one semester of calculus. We will make very little direct reference to calculus: only a brief and relatively informal use of limits in Chapter 14. However, we will assume a level of fluency with precalculus (algebra, geometry, logarithms, etc) that is typically developed during while taking calculus. If you already have significant experience writing proofs, including inductive proofs, this book may be too easy for you.