Free interactive textbook

Discrete Mathematics

with applications in Computer Science

Nikolai Chukhin · Alexander S. Kulikov

A year-long course in mathematical thinking, logic and set theory, combinatorics, probability theory, and graph theory, with explanations, examples, exercises, and interactive problems.

Read online

Book contents

Introduction

About This Interactive Book

Before getting started, learn how this interactive book is organized, how to use its theory, automatically checked problems, Python code, and puzzles.

Mathematical Thinking

Proofs of Existence and Optimality

How can we prove that an object with given properties exists, or show that it cannot exist? We explore constructive and nonconstructive arguments, prove impossibility and optimality, and see how the same ideas build error-correcting codes.

Proofs of Universal Statements: Mathematical Induction

How can we prove that a statement holds for every positive integer? How can we be sure a program works correctly on all possible inputs? We explore one of the most powerful tools in discrete mathematics - the method of mathematical induction.

Proofs of Algorithm Correctness and Runtime Estimates

How can we justify an algorithm? We must show that it gives the right answer and that its running time is acceptable. We discuss mathematical methods for proving correctness and estimating runtime.

Proofs in Computer Science (Optional)

What exactly do we call a proof? Can a proof reveal nothing except that it is valid? We introduce computability and complexity, followed by interactive, zero-knowledge, and probabilistically checkable proofs.

Project: 15 Puzzle, A*, and Coordinated Motion Planning

Why are half of all 15-puzzle positions impossible to solve? We uncover the invariant hidden in the tiles, turn it into a solvability test, use the A* algorithm to find shortest solutions, and apply the same idea to coordinate several moving robots.

Logic and Set Theory

Propositional Logic

What do ordinary reasoning, mathematics, programming, and Boolean circuits have in common? Propositional logic gives them a shared language. We study its main laws and show how statements and connectives work across these settings.

Satisfiability Problem

How can we determine whether a set of logical constraints can all be satisfied at once? This is the satisfiability problem. We study tractable special cases and algorithms, then examine its applications in formal verification and complexity theory.

Boolean Circuits

How do Boolean circuits model computation and underlie microchips? We use this simple but powerful model to synthesize efficient circuits and prove that overly efficient circuits do not exist.

Set Theory

How does set theory give mathematics a common language and compare different infinities? We study countable and uncountable sets and Cantor’s diagonal argument, then connect these ideas to axioms, the halting problem, and Gödel’s incompleteness theorem.

Partially Ordered Sets

How do partial orders describe collections whose objects are not always comparable? We read Hasse diagrams and combine partial orders, extend induction to ordered sets, and use chains, antichains, and Dilworth’s theorem in scheduling and optimization.

Project: Optimal Circuit Synthesis with SAT

How can we turn the search for the smallest Boolean circuit into a SAT problem? A SAT solver constructs circuits of a given size, proves when no circuit of that size exists, and helps design a shared circuit for a seven-segment display.

Combinatorics

Arrangements and Combinations

How many possibilities hide inside a seemingly simple choice? We count arrangements, combinations, and repetitions; derive binomial identities and estimates; and meet Catalan numbers in trees, paths, and balanced parentheses.

Generation of Combinatorial Objects

How can we list each combinatorial object exactly once, rather than merely count them? We build generators for subsets, permutations, and parenthesis sequences, then prune huge search spaces with branch and bound and dynamic programming.

Recurrence Relations

How do recurrence relations describe quantities in terms of smaller instances? They arise in counting and recursive algorithms. We study recursive definitions, financial models, divide-and-conquer algorithms, and ways to solve linear recurrences.

Generating Functions

How can generating functions solve counting problems and linear recurrences? They are among the most powerful and beautiful tools of discrete mathematics, and we use them to derive the Catalan numbers in another way.

Project: Portfolio Selection

How can we track a stock market index using whole shares? We use a simplified stock market model, generating functions, dynamic programming, integer linear programming, and branch and bound.

Probability Theory

Events and Probability Spaces

How can we model random events and estimate their probabilities? We begin with probability spaces, events, and process trees, then combine events and use recursive computation and Monte Carlo simulation to estimate the odds.

Conditional Probability

How does available information change the probability of an event? We study conditional probability, dependence between events, and Bayes’ formula to untangle deceptive games and understand the logic behind diagnoses and inferences.

Random Variables

How do random outcomes become quantities we can analyze and fit to data? We study distributions, expectation, likelihood, and conditional dependence, from waiting times and rare events to empirical parameter estimation.

Deviation from the Mean

How can we estimate the probability that a random variable deviates significantly from its mean? Such estimates help evaluate unusually large measurement errors, unexpected fluctuations in demand, and rare but impactful events in complex systems.

Probability in Computer Science

How can randomness simplify or speed up an algorithm, or prove that a discrete object exists? We study randomized algorithms and hashing, then apply the probabilistic method to tournaments, Ramsey numbers, sum-free sets, and codes.

Graph Theory

What is a Graph?

What do cellphone networks, GPS navigation, and internet search have in common? Graphs model them all. We study what graphs are, when and how to use them, and how to work with them in Python.

Trees

How can you connect an entire network as cheaply as possible? We study trees, minimum spanning trees, dynamic programming, and formulas that count spanning trees, with applications to network design and efficient graph algorithms.

Cycles

What links delivery routes, genome assembly, and deadlocks? Cycles do. We study acyclic and strongly connected graphs, Eulerian and Hamiltonian cycles, the traveling salesman problem, and de Bruijn graphs for reconstructing DNA.

Flows and Connectivity

How much can pass through a network whose edges have limited capacity? A flow models this quantity. We develop max-flow/min-cut algorithms, then reduce bipartite matching, project selection, and image segmentation to flow problems.

Matchings

How can people, jobs, or resources be paired fairly and efficiently? Matchings model compatible pairs. We relate them to independent sets and vertex covers, study bipartite and stable matching, and finish with perfect matchings in general graphs.

Colorings

How can resources be distributed without creating conflicts? Graph coloring models this. We relate the chromatic number to degrees and cliques, count colorings with chromatic polynomials, and study exact and approximate coloring algorithms.

Planar Graphs

Which graphs can be drawn on the plane without edge crossings? Many graphs that arise in practice are planar. We use Euler’s formula to study nonplanarity, crossings, and colorings, then consider geometric layouts and planar separators.

Project: PageRank Algorithm

How does PageRank decide which web pages matter? We use a random walk on graphs and Markov chains, find stationary distributions, and turn the web’s link structure into a ranking.