Discrete mathematics is the basis of much of computer science, from algorithms and automata theory to combinatorics and graph theory. This textbook covers the discrete mathematics that every computer science student needs to learn. Guiding students quickly through thirty-one short chapters that discuss one major topic each, this flexible book can be tailored to fit the syllabi for a variety of courses.
Proven in the classroom, Essential Discrete Mathematics for Computer Science aims to teach mathematical reasoning as well as concepts and skills by stressing the art of proof. It is fully illustrated in color, and each chapter includes a concise summary as well as a set of exercises. The text requires only precalculus, and where calculus is needed, a quick summary of the basic facts is provided.
Essential Discrete Mathematics for Computer Science is the ideal introductory textbook for standard undergraduate courses, and is also suitable for high school courses, distance education for adult learners, and self-study.
- The essential introduction to discrete mathematics
- Features thirty-one short chapters, each suitable for a single class lesson
- Includes more than 300 exercises
- Almost every formula and theorem proved in full
- Breadth of content makes the book adaptable to a variety of courses
- Each chapter includes a concise summary
- Solutions manual available to instructors
Harry Lewis is Gordon McKay Professor of Computer Science and former dean of Harvard College at Harvard University. His books include Blown to Bits: Your Life, Liberty, and Happiness after the Digital Explosion. Rachel Zax is a software engineer at Google.
- Preface
- 1 The Pigeonhole Principle
- 2 Basic Proof Techniques
- 3 Proof by Mathematical Induction
- 4 Strong Induction
- 5 Sets
- 6 Relations and Functions
- 7 Countable and Uncountable Sets
- 8 Structural Induction
- 9 Propositional Logic
- 10 Normal Forms
- 11 Logic and Computers
- 12 Quantificational Logic
- 13 Directed Graphs
- 14 Digraphs and Relations
- 15 States and Invariants
- 16 Undirected Graphs
- 17 Connectivity
- 18 Coloring
- 19 Finite Automata
- 20 Regular Languages
- 21 Order Notation
- 22 Counting
- 23 Counting Subsets
- 24 Series
- 25 Recurrence Relations
- 26 Probability
- 27 Conditional Probability
- 28 Bayes’ Theorem
- 29 Random Variables and Expectation
- 30 Modular Arithmetic
- 31 Public Key Cryptography
- Index
"I want to share with everybody my enjoyment of this excellent textbook."—Narciso Marti-Oliet, European Math Society
"Those teaching computer scientists who take discrete mathematics alongside other mathematics modules such as linear algebra and calculus (as is the case with the CS20 students at Harvard), and who need a book with an emphasis on proof, will likely and this book a very good choice for their students."—London Mathematical Society, Glenn Hawe
"Carefully constructed and elegantly written, this book delivers exactly what its title promises—an introductory treatment of all the essentials of discrete mathematics that a computer scientist needs to know."—David P. Williamson, Cornell University
"This excellent book is an outstanding combination of clarity, rigor, and elegance. Lewis and Zax have produced a remarkably comprehensive guide to the world of discrete mathematics—a guide that will be invaluable for any student of computer science."—John MacCormick, Dickinson College
"Lewis and Zax give us a nice introduction to the essential concepts of discrete mathematics that any computer scientist should know. Their book presents a rigorous treatment of the important results, but it also goes beyond that by discussing the big picture behind the key ideas. Their explanations are at the perfect level for anyone with little background in mathematical proofs, making it ideal as a textbook or as supplementary reading."—Saúl A. Blanco, Indiana University
"Finally, a book that covers discrete mathematics the way I like to teach it to students of computer science."—Saad Mneimneh, Hunter College, City University of New York
