Education5 min read
Discrete Math: Study & Quiz Guide — How to Work Through Each Unit
How to use Discrete Math: Study & Quiz unit by unit: what its ten units cover, which practice mode suits which job, and when to reach for the logic tools.
Topic hub · 66 articles
Discrete Mathematics
Discrete mathematics is the mathematics of things you can count: true-or-false statements, finite sets, integers, arrangements and networks. For many students it is also where mathematics changes from calculating answers to proving statements, and that change is a large part of what makes it feel new.
The subject is held together by a small number of habits. Write the definition down before you use it. Check a claim on a tiny case before you try to prove it in general. Know which proof technique a statement is asking for. A skipped definition or an unchecked case undoes more arguments than a forgotten formula does.
These guides follow a common teaching order — logic, proof, sets and functions, number theory, induction, counting, probability, recurrences and graphs — and every worked example in them can be checked with pencil and paper.
Where to start
Start with logic and proof
Truth tables, implications and the main proof techniques come up in every later topic. Read the cornerstone guide, then the logic and proof articles, before anything else.
Then counting and probability together
Permutations, combinations, inclusion–exclusion and the pigeonhole principle are the tools; discrete probability is the same counting with a denominator.
Practise on small cases
The worked examples are small enough to check by writing every case out. If a formula disagrees with a list you wrote out by hand, trust the list and find the mistake.
Start here
Everything else in this hub
- Education4 min read
Adjacency Matrices and Lists: Representing a Graph, and Counting Walks
How to store a graph as an adjacency matrix, an adjacency list or an edge list, what each costs, and how matrix powers count walks and triangles.
- Education5 min read
Big-O Notation for Discrete Math Students: Definitions, Proofs and Common Classes
What f(n) = O(g(n)) means, how to prove it by finding constants c and k, how big-Omega and big-Theta differ, and the growth classes that algorithms fall into.
- Education4 min read
The Binomial Distribution: Counting Successes in Repeated Trials
When a fixed number of independent trials each succeed with the same chance, the count of successes is binomial. Formula, mean, variance and examples.
- Education4 min read
The Binomial Theorem and Pascal's Triangle: Where the Coefficients Come From
Why the coefficients of (x + y)ⁿ are the numbers n choose k, how Pascal's triangle builds them, a worked expansion, and identities you can prove by counting.
- Education5 min read
Bipartite Graphs: The Two-Colour Test and the Odd-Cycle Rule
A graph is bipartite when its vertices split into two sides with every edge crossing between. How to test it, why odd cycles rule it out, and matchings.
- Education4 min read
The Birthday Problem: Why 23 People Are Enough
In a group of 23, the chance that two share a birthday is just over 50%. The calculation, a probability table, why intuition misses it, and hash collisions.
- Education5 min read
Boolean Algebra and Logic Gates: From Truth Tables to Circuits
Boolean algebra writes logic with 0, 1, + and ·. The laws, the gates that implement them, building a circuit from a truth table, and a half adder.
- Education4 min read
The Cartesian Product: Ordered Pairs, Grids and Relations
A × B is the set of ordered pairs (a, b) with a in A and b in B. Worked examples, why |A × B| = |A| · |B|, why order matters, and how relations use it.
- Education4 min read
Catalan Numbers: Where They Appear and How to Compute Them
The Catalan numbers 1, 1, 2, 5, 14, 42 count balanced brackets, mountain paths, binary trees and triangulations. The formula, the recurrence and why they match.
- Education4 min read
The Chinese Remainder Theorem: Solving Simultaneous Congruences
Find a number with given remainders for several coprime moduli: the theorem, the construction step by step, a sieving shortcut, and when no solution exists.
- Education4 min read
Conditional Probability and Bayes' Theorem, with a Worked Test Example
How conditional probability works, how to reverse it with Bayes' theorem, and why a test that catches 95% of faults can still be wrong most of the time.
- Education4 min read
Converse, Inverse and Contrapositive: Which One Means the Same Thing?
The contrapositive of an if-then statement always means the same thing; the converse and inverse do not. Truth tables, examples and the mistakes to avoid.
- Education4 min read
Countable vs Uncountable Sets: Cantor's Diagonal Argument in Plain Steps
Why the integers and rationals are countable but the reals are not: listing arguments, Cantor's diagonal proof step by step, and what it means for computing.
- Education4 min read
De Morgan's Laws Explained, with Logic and Set Examples
De Morgan's laws say how to negate an and or an or: flip the connective and negate each part. Proofs by truth table and Venn diagram, plus uses in code.
- Education4 min read
Derangements: The Hat-Check Problem and Its Formula
A derangement is a permutation that leaves nothing in place. Count them with inclusion–exclusion, see why the odds approach 1/e, and use the recurrence.
- Education4 min read
Dijkstra's Algorithm Worked by Hand on a Small Graph
Dijkstra's algorithm finds shortest paths from one vertex. The table method step by step, recovering the route, and why negative weights break it.
- Education5 min read
Discrete Math Cheat Sheet: The Laws, Formulas and Definitions on One Page
The core of a first discrete math course in one reference: logic laws, proof methods, set identities, counting formulas, number theory and graph facts.
- Education4 min read
Equivalence Relations and Equivalence Classes, with Partitions You Can Draw
An equivalence relation is reflexive, symmetric and transitive, and it splits a set into equivalence classes. How to prove one, find its classes and draw them.
- Education4 min read
The Euclidean Algorithm: Finding a GCD by Hand, and Why It Works
Find the greatest common divisor of two numbers by repeated division with remainder. Worked examples, why it works, how fast it is, and the extended version.
- Education5 min read
Euler Paths vs Euler Circuits: The Degree Test and How to Find One
An Euler path uses every edge once; an Euler circuit also ends where it started. Count odd-degree vertices to decide which exists, then find one by hand.
- Education4 min read
Expected Value and Linearity of Expectation: The Shortcut That Solves Hard Counting Problems
Expected value is a probability-weighted average. How to compute it, why expectations add even for dependent events, and how indicator variables help.
- Education5 min read
Fermat's Little Theorem and How RSA Uses Modular Arithmetic
Fermat's little theorem says aᵖ⁻¹ ≡ 1 (mod p) for a prime p. How to use it, why it can mislead a primality test, and a toy RSA example worked by hand.
- Education4 min read
Finite State Machines: States, Transitions and the Strings They Accept
A finite state machine reads input one symbol at a time and changes state. How to design one, trace an input, and see what no finite machine can recognise.
- Education4 min read
Composition and Inverse Functions: When an Inverse Exists and How to Find It
How to compose functions, why order matters, when a function has an inverse, and how to find and check one, with examples on finite sets and the integers.
- Education4 min read
Primes and the Fundamental Theorem of Arithmetic: Why Factorisation Is Unique
Every integer above 1 is a product of primes in exactly one way. Why that needs proof, how existence and uniqueness are shown, and what it tells you.
- Education4 min read
Generating Functions: Turning a Sequence into an Algebra Problem
A generating function stores a sequence as the coefficients of a power series. How to build one, the core identities, and how to count and solve recurrences.
- Education5 min read
Graph Coloring and the Chromatic Number: Scheduling, Maps and Limits
A proper coloring gives adjacent vertices different colors. How to find the chromatic number, the bounds that help, the four color theorem, and scheduling uses.
- Education4 min read
Graph Isomorphism: How to Show Two Graphs Are (or Are Not) the Same
Two graphs are isomorphic when a relabelling turns one into the other. How to prove it with a bijection, disprove it with an invariant, and avoid the traps.
- Education4 min read
Graph Theory Basics: Vertices, Edges, Degrees and the Handshake Lemma
The vocabulary of graph theory explained with small examples: vertices, edges, degree, paths, cycles, connectivity and the handshake lemma, with its proof.
- Education4 min read
Hamiltonian Paths and Cycles: Why No Simple Test Exists
A Hamiltonian cycle visits every vertex exactly once. Why no simple test exists, the sufficient conditions that help, and how to rule one out.
- Education5 min read
How to Make a Truth Table, Step by Step
Build a truth table without errors: count the rows, fill the input columns in a fixed pattern, add one column per connective, and read the final column.
- Education4 min read
How to Study for a Discrete Math Exam: A Plan Built Around Definitions and Practice
A two-week plan for a discrete math exam: learn the definitions, test yourself instead of rereading, practise proofs from blank paper, and sit a timed mock.
- Education5 min read
How to Write a Direct Proof: A Template and Five Worked Examples
A direct proof assumes the hypothesis and reasons forward to the conclusion. A reusable template, five worked proofs and the mistakes that cost marks.
- Education5 min read
The Inclusion–Exclusion Principle: Counting Overlaps Without Double-Counting
Inclusion–exclusion counts a union of overlapping sets: add the sets, subtract pairwise overlaps, add back triple overlaps. Formulas and four worked problems.
- Education4 min read
Injective, Surjective and Bijective Functions: How to Tell Them Apart
One-to-one, onto, or both? Definitions, worked examples on finite and infinite sets, how to prove each property, and how to count each kind of function.
- Education4 min read
Knights and Knaves Puzzles: Solving Them with Propositional Logic
Knights always tell the truth and knaves always lie. How to turn each statement into a biconditional, solve by cases or truth table, and check the answer.
- Education4 min read
Counting Lattice Paths on a Grid
How many shortest routes cross a grid? Why the answer is a binomial coefficient, how to count paths through or around a point, and the Pascal link.
- Education5 min read
Proving Logical Equivalence: Truth Tables vs Laws of Logic
Two ways to prove statements are logically equivalent: compare truth tables, or rewrite one into the other with named laws. Worked proofs and when to use each.
- Education4 min read
Minimum Spanning Trees: Kruskal's and Prim's Algorithms by Hand
How to connect every vertex of a weighted graph at least total cost. Kruskal's and Prim's algorithms worked step by step, and the cut property behind both.
- Education4 min read
Modular Arithmetic: Clock Maths, Congruences and the Rules That Make It Work
Modular arithmetic works with remainders. What a ≡ b (mod n) means, which operations are safe, how to reduce big powers, and where it is used in computing.
- Education5 min read
Modular Inverses with the Extended Euclidean Algorithm
Find the inverse of a modulo n with the extended Euclidean algorithm, see when none exists, use the prime shortcut, and solve ax ≡ b (mod n).
- Education4 min read
The Monty Hall Problem: Why Switching Wins Two Times in Three
Three doors, one car, and a host who opens a goat door. Why switching wins with probability 2/3, shown by listing cases, by Bayes' theorem and with 100 doors.
- Education5 min read
How to Negate a Statement with Quantifiers (Without Changing the Order of the Quantifiers)
To negate a quantified statement, flip each quantifier and negate what follows. Step-by-step negations of nested statements, including limits and conditionals.
- Education4 min read
Number Bases: Converting Between Binary, Decimal and Hexadecimal
How place value works in any base, how to convert decimal to binary by repeated division, why hexadecimal groups four bits, and the mistakes to avoid.
- Education5 min read
Partial Orders and Hasse Diagrams: How to Draw One and What It Shows
A partial order is reflexive, antisymmetric and transitive. How to draw its Hasse diagram, read maximal and least elements, and find upper and lower bounds.
- Education4 min read
Permutations vs Combinations: The One Question That Decides Which to Use
Ask whether order matters. Formulas for permutations and combinations, why they differ by k!, worked examples, and the four-way table for repetition.
- Education4 min read
The Pigeonhole Principle: Simple Statement, Surprising Proofs
If more than n items go into n boxes, some box holds two. The general version, how to choose the boxes, and seven worked examples from socks to compression.
- Education5 min read
Planar Graphs and Euler's Formula V − E + F = 2
Which graphs can be drawn without crossing edges, why V − E + F = 2 for every connected planar graph, and how it proves K₅ and K₃,₃ are not planar.
- Education4 min read
Power Sets: Why a Set with n Elements Has 2ⁿ Subsets
The power set of a set is the set of all its subsets. How to list one without missing any, three proofs that it has 2ⁿ elements, and the traps with ∅ and {∅}.
- Education5 min read
Predicates and Quantifiers: Reading ∀ and ∃ Without Getting Lost
What predicates, the universal quantifier ∀ and the existential quantifier ∃ mean, how the domain changes a statement's truth, and why order matters.
- Education5 min read
Proof by Contradiction: How It Works and When to Reach for It
Proof by contradiction assumes the statement is false and derives an impossibility. Why it is valid, four worked proofs, and how to write the first line.
- Education4 min read
Proof by Contrapositive: The Indirect Proof That Is Often Easiest
To prove 'if p then q', prove 'if not q then not p' instead. Why it is valid, how to write one, five worked examples and how to tell it is the right method.
- Education4 min read
Proof by Induction, Step by Step: Base Case, Hypothesis and the Inductive Step
How to write a proof by induction: the base case, the inductive hypothesis and the step that uses it, with worked sum, divisibility and inequality proofs.
- Education4 min read
Reflexive, Symmetric, Antisymmetric, Transitive: Checking a Relation's Properties
How to test a relation for the four key properties using its list of pairs, its matrix or its directed graph, with worked examples and the antisymmetry traps.
- Education4 min read
Ramsey Numbers: Why R(3,3) = 6
In any group of six people, three are mutual friends or mutual strangers. The proof, why five is not enough, and why Ramsey numbers are so hard to compute.
- Education5 min read
Recurrence Relations: Setting Them Up and Solving the Linear Ones
How to model a problem with a recurrence relation and solve linear ones with constant coefficients, including repeated roots and a constant extra term.
- Education4 min read
Rules of Inference: Modus Ponens, Modus Tollens and the Rest, with Worked Arguments
The rules of inference used in discrete math, from modus ponens to resolution and the quantifier rules, with a numbered derivation and the fallacies to avoid.
- Education4 min read
Sigma Notation and Sums: Reading, Splitting and Proving Summation Formulas
How to read Σ notation, the rules for splitting and shifting sums, the standard closed forms, telescoping sums, and how to prove a sum formula.
- Education4 min read
Set Operations Explained: Union, Intersection, Difference and Complement
Union, intersection, difference, complement and symmetric difference, each defined with a Venn picture and a worked example, plus how to prove set identities.
- Education4 min read
Stars and Bars: Counting Combinations with Repetition
How the stars and bars method counts ways to share identical items among distinct groups, with and without minimums, and why the formula is C(k + n − 1, n − 1).
- Education5 min read
Strong Induction vs Ordinary Induction: When You Need More Than One Step Back
Strong induction assumes every earlier case, not just the last. When you need it, why it is valid, and worked proofs with stamps, primes and Fibonacci numbers.
- Education4 min read
Tautology, Contradiction or Contingency? How to Tell in One Truth Table
A tautology is always true, a contradiction always false and a contingency depends on its parts. How to classify any statement, with worked truth tables.
- Education5 min read
Trees in Graph Theory: Why a Tree with n Vertices Has n − 1 Edges
A tree is a connected graph with no cycles. Its equivalent definitions, why every tree has two leaves and n − 1 edges, and rooted and binary trees.
- Education4 min read
Valid vs Sound Arguments: Why a Valid Argument Can Still Be Wrong
A valid argument's conclusion must follow from its premises; a sound one is valid with true premises too. How to test validity, with examples of each case.
- Education4 min read
What Is Discrete Math? The Subjects, Why Computer Science Needs Them, and Where to Start
Discrete math studies separate, countable things: logic, sets, proofs, counting, number theory and graphs. What each topic is and why computing depends on it.