Free interactive textbook
Discrete Mathematics
with applications in Computer Science
A year-long course in mathematical thinking, logic and set theory, combinatorics, probability theory, and graph theory, with explanations, examples, exercises, and interactive problems.
Browse the courseCourse contents
Introduction
About this Interactive Book
Prerequisites
Notation and Basic Facts
Mathematical Thinking
Proofs of Existence and Optimality
Proofs of Universal Statements: Mathematical Induction
Proofs of Algorithm Correctness and Runtime Estimates
Proofs in Computer Science (Optional)
Project 15 Puzzle
Logic and Set Theory
Propositional Logic
Satisfiability Problem
Boolean Circuits
Set Theory
Partially Ordered Sets
Project: Optimal Circuit Synthesis with SAT
Combinatorics
Arrangements and Combinations
- Arrangements and Combinations
- Basic Rules
- Arrangements
- Combinations
- Combinations with Repetitions
- Identities
- Estimates of Binomial Coefficients
- Arrangements with Repetitions
- Catalan Numbers: Introduction
- Catalan Numbers: Proof of the Formula
- Catalan Numbers: Various Manifestations
- Lucas Theorem and the Sierpiński Triangle (Optional)
- Theory Problems