Discrete mathematics forms the theoretical foundation of computer science. Concepts such as proofs, logic, sets, graphs, combinatorics, probability, and recurrences are essential for analyzing algorithms, designing software, understanding networks, and reasoning about computation.
Mathematics for Computer Science addresses these core topics with a strong emphasis on rigorous reasoning. In modern computing, formal proofs are not only a mathematical exercise but also a practical tool used to verify software correctness, analyze algorithms, and reason about computational limits such as the Halting Problem and cryptographic security.
About the book
Mathematics for Computer Science is written by Eric Lehman, F. Thomson Leighton, and Albert R. Meyer. The book explains how mathematical models and methods are used to analyze problems that arise in computer science, with proofs playing a central role.
The text is structured into five major parts: Proofs, Structures, Counting, Probability, and Recurrences. It is intended for students in computer science and related disciplines, as well as self-learners who want a solid theoretical foundation. The material assumes comfort with basic algebra and logical reasoning, but it develops the necessary mathematical tools systematically.
The authors emphasize that proofs are essential for genuine understanding and for certifying that software and hardware behave correctly. The approach is rigorous but oriented toward computational applications.
What you will learn
By studying this book, readers develop the ability to construct and understand mathematical proofs, including proof by contradiction, induction, and well-ordering. They learn formal logic, propositional reasoning, and the structure of mathematical arguments used throughout computer science.
The book covers discrete structures such as sets, sequences, functions, relations, graphs, and partial orders. It introduces number theory topics relevant to cryptography, including modular arithmetic and RSA public key encryption. Graph theory is treated in depth, including directed graphs, planar graphs, matchings, coloring, connectivity, and network structures.
In addition, readers learn combinatorial counting techniques, generating functions, asymptotic notation, and recurrence relations. The probability section develops probability spaces, conditional probability, random variables, expectation, variance, and random walks, all with applications to computational settings.
These tools are directly applicable to algorithm analysis, complexity reasoning, cryptographic systems, distributed systems, and formal verification.
Table of contents
I Proofs
Introduction
1 What is a Proof?
1.1 Propositions
1.2 Predicates
1.3 The Axiomatic Method
1.4 Our Axioms
1.5 Proving an Implication
1.6 Proving an “If and Only If”
1.7 Proof by Cases
1.8 Proof by Contradiction
1.9 Good Proofs in Practice
1.10 References
2 The Well Ordering Principle
2.1 Well Ordering Proofs
2.2 Template for Well Ordering Proofs
2.3 Factoring into Primes
2.4 Well Ordered Sets
3 Logical Formulas
3.1 Propositions from Propositions
3.2 Propositional Logic in Computer Programs
3.3 Equivalence and Validity
3.4 The Algebra of Propositions
3.5 The SAT Problem
3.6 Predicate Formulas
4 Mathematical Data Types
4.1 Sets
4.2 Sequences
4.3 Functions
4.4 Binary Relations
4.5 Finite Cardinality
5 Induction
5.1 Ordinary Induction
5.2 Strong Induction
5.3 Strong Induction vs. Induction vs. Well Ordering
5.4 State Machines
6 Recursive Data Types
6.1 Recursive Definitions and Structural Induction
6.2 Strings of Matched Brackets
6.3 Recursive Functions on Nonnegative Integers
6.4 Arithmetic Expressions
6.5 Induction in Computer Science
7 Infinite Sets
7.1 Infinite Cardinality
7.2 The Halting Problem
7.3 The Logic of Sets
7.4 Does All This Really Work?
II Structures
Introduction
8 Number Theory
8.1 Divisibility
8.2 The Greatest Common Divisor
8.3 Prime Mysteries
8.4 The Fundamental Theorem of Arithmetic
8.5 Alan Turing
8.6 Modular Arithmetic
8.7 Remainder Arithmetic
8.8 Turing’s Code (Version 2.0)
8.9 Multiplicative Inverses and Cancelling
8.10 Euler’s Theorem
8.11 RSA Public Key Encryption
8.12 What has SAT got to do with it?
8.13 References
9 Directed graphs & Partial Orders
9.1 Digraphs & Vertex Degrees
9.2 Adjacency Matrices
9.3 Walk Relations
9.4 Directed Acyclic Graphs & Partial Orders
9.5 Weak Partial Orders
9.6 Representing Partial Orders by Set Containment
9.7 Path-Total Orders
9.8 Product Orders
9.9 Scheduling
9.10 Equivalence Relations
9.11 Summary of Relational Properties
10 Communication Networks
10.1 Complete Binary Tree
10.2 Routing Problems
10.3 Network Diameter
10.4 Switch Count
10.5 Network Latency
10.6 Congestion
10.7 2-D Array
10.8 Butterfly
10.9 Benes Network
11 Simple Graphs
11.1 Vertex Adjacency and Degrees
11.2 Sexual Demographics in America
11.3 Some Common Graphs
11.4 Isomorphism
11.5 Bipartite Graphs & Matchings
11.6 The Stable Marriage Problem
11.7 Coloring
11.8 Simple Walks
11.9 Connectivity
11.10 Odd Cycles and 2-Colorability
11.11 Forests & Trees
11.12 References
12 Planar Graphs
12.1 Drawing Graphs in the Plane
12.2 Definitions of Planar Graphs
12.3 Euler’s Formula
12.4 Bounding the Number of Edges in a Planar Graph
12.5 Returning to K5 and K3;3
12.6 Coloring Planar Graphs
12.7 Classifying Polyhedra
12.8 Another Characterization for Planar Graphs
III Counting
Introduction
13 Sums and Asymptotics
13.1 The Value of an Annuity
13.2 Sums of Powers
13.3 Approximating Sums
13.4 Hanging Out Over the Edge
13.5 Products
13.6 Double Trouble
13.7 Asymptotic Notation
14 Cardinality Rules
14.1 Counting One Thing by Counting Another
14.2 Counting Sequences
14.3 The Generalized Product Rule
14.4 The Division Rule
14.5 Counting Subsets
14.6 Sequences with Repetitions
14.7 Counting Practice: Poker Hands
14.8 The Pigeonhole Principle
14.9 Inclusion-Exclusion
14.10 Combinatorial Proofs
14.11 References
15 Generating Functions
15.1 Infinite Series
15.2 Counting with Generating Functions
15.3 Partial Fractions
15.4 Solving Linear Recurrences
15.5 Formal Power Series
15.6 References
IV Probability
Introduction
16 Events and Probability Spaces
16.1 Let’s Make a Deal
16.2 The Four Step Method
16.3 Strange Dice
16.4 The Birthday Principle
16.5 Set Theory and Probability
17 Conditional Probability
17.1 Monty Hall Confusion
17.2 Definition and Notation
17.3 The Four-Step Method for Conditional Probability
17.4 Why Tree Diagrams Work
17.5 The Law of Total Probability
17.6 Simpson’s Paradox
17.7 Independence
17.8 Mutual Independence
18 Random Variables
18.1 Random Variable Examples
18.2 Independence
18.3 Distribution Functions
18.4 Great Expectations
18.5 Linearity of Expectation
19 Deviation from the Mean
19.1 Why the Mean?
19.2 Markov’s Theorem
19.3 Chebyshev’s Theorem
19.4 Properties of Variance
19.5 Estimation by Random Sampling
19.6 Confidence versus Probability
19.7 Sums of Random Variables
19.8 Really Great Expectations
20 Random Walks
20.1 Gambler’s Ruin
20.2 Random Walks on Graphs
V Recurrences
Introduction
21 Recurrences
21.1 The Towers of Hanoi
21.2 Merge Sort
21.3 Linear Recurrences
21.4 Divide-and-Conquer Recurrences
21.5 A Feel for Recurrences
Bibliography
Glossary of Symbols
Index
Book details
- Title: Mathematics for Computer Science
- Author(s): Eric Lehman; F. Thomson Leighton; Albert R. Meyer
- Main category: Mathematics
- Subcategory: Discrete Mathematics
- License: Creative Commons (2011, Eric Lehman, F. Tom Leighton, Albert R. Meyer)
More books by language: Discrete Mathematics, Mathematics
Legal notice: This book is shared for educational purposes only. The content is distributed under Creative Commons licenses or with explicit permission from the author. FreeProgrammingBooks does not host copyrighted material.