The mathematics of things you can count.

Orientation

Two mathematics, one border

Where discrete ends, continuous begins — and why the border is the most interesting place to stand.

Pick up any mathematical object and ask one question: between any two of its points, is there always another point? If yes, you are in continuous territory. Between 0.1 and 0.2 sits 0.15; between 0.15 and 0.2 sits 0.175, forever. If no — if there is a next thing, and nothing in between — you are in discrete territory. Between the integers 3 and 4 there is no integer. Between two adjacent vertices of a graph there is no half-vertex. Between bit patterns 1011 and 1100 there is nothing at all.

That single distinction reorganises the whole subject. Continuous mathematics is built on limits — the machinery for talking about what happens as gaps shrink to nothing. Discrete mathematics has no gaps to shrink, so it is built on counting, structure and case analysis instead. Different questions, different tools, different proofs.

So where does calculus fit?

Calculus is the flagship of the continuous side, and it is not the enemy — it is the other half of your toolkit. Three honest relationships:

• Calculus approximates discrete things. You cannot easily compute 100! but Stirling's formula — pure calculus — tells you it is about √(2πn)·(n/e)ⁿ. Half of algorithm analysis is replacing an ugly sum with a smooth integral you can actually evaluate.
• Discrete things approximate calculus. Every derivative your computer has ever taken was a subtraction of two nearby values. Every integral was a sum. Numerical methods are the act of pushing continuous mathematics back across the border so a finite machine can hold it.
• They answer different questions. "How fast is this changing?" is a calculus question. "How many ways can this be arranged, and is any of them optimal?" is a discrete question. Machine learning needs both in the same breath: gradients are continuous, the graph they flow through is discrete.

How the branches actually connect

Discrete mathematics is not a list of ten unrelated topics, even though every syllabus presents it that way. It is a small number of ideas wearing different costumes. Drag the nodes around; click one to see what it depends on and what it feeds.

Read the map in one sentence: logic gives you the right to make claims; set theory gives you the objects to make claims about; relations put structure on those objects; graphs are the most useful structure; counting tells you how big everything is; probability is counting with weights; number theory is what happens when the objects are integers; algebra is what happens when you notice the same structure in all of the above.

What people mean by "pure math"

The pure/applied split is not about usefulness, and anyone who tells you otherwise is selling something. It is about what counts as a finished piece of work.

• Pure mathematics is finished when the theorem is proved. The object of study is the structure itself. A pure mathematician asks "what is true about all groups?" — and the answer must hold for every group that could ever exist, established by proof, not by testing a thousand of them.
• Applied mathematics is finished when the real question is answered. The structure is a means. An applied mathematician asks "which group models this crystal / this cipher / this error-correcting code, and what does that let me compute?"

The joke that writes itself: number theory was the proudest example of useless pure mathematics for two thousand years — G.H. Hardy boasted in 1940 that nothing he had done was of the slightest practical use. Roughly thirty-five years later it became RSA, and now it protects every payment you have ever made. Graph theory started as a puzzle about bridges in a Prussian town. Boolean algebra was one man's attempt to formalise the laws of thought, decades before there was anything electrical to switch.

Discrete mathematics is the subject where "pure" turned out to mean "applied, but you have to wait a century."

Studying pure mathematics trains a specific reflex: never accept a claim without a reason that covers every case. That reflex is the actual transferable skill. It is why the subject appears in interviews and why it makes people better engineers even when they never write down a proof again.

01 · Motivation

Why learn discrete mathematics

Not "because it is on the syllabus" — because it is the substrate.

Every claim below is load-bearing. Hover a card to see the concrete thing it buys you.

The honest summary: continuous mathematics describes the world; discrete mathematics describes the machine that models the world. If you write software, design systems, reason about data, or build anything with AI in it, you are doing applied discrete mathematics whether or not you use the vocabulary. Learning the vocabulary turns intuition into something you can prove, communicate and optimise.

02 · Logic and proof

Logic and proof techniques

The rules that decide which sentences you are allowed to write down next.

Logic is the operating system of mathematics. A proposition is a sentence that is definitely true or definitely false — "7 is prime" qualifies, "x > 3" does not until you say what x is, and "this sentence is false" is not a proposition at all. From atoms like p, q you build compounds with five connectives:

The one that trips everyone is implication. p → q is false in exactly one situation: p true and q false. "If it rains, I take an umbrella" is not broken on a sunny day, whatever I carry. A promise about a case that never arose was never broken. That is why vacuous truth — "every unicorn in this room is green" — is true.

Build a truth table

Type any formula in p q r s using ~ & | -> <-> (or the symbols ¬ ∧ ∨ → ↔). The table is computed by an actual parser, so try to break it.

The verdicts

A formula true in every row is a tautology (a law of logic). False in every row: a contradiction. Mixed: contingent. Two formulas are logically equivalent — written ≡ — exactly when P ↔ Q is a tautology, i.e. their columns match everywhere. Load the presets above to meet the equivalences you will use constantly:

• De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q — the rule you use every time you invert an if condition.
• Implication as disjunction: p → q ≡ ¬p ∨ q. This is why implication has no dedicated hardware gate: it is already NOT-OR.
• Contrapositive: p → q ≡ ¬q → ¬p. Always valid. Its evil twins, the converse q → p and inverse ¬p → ¬q, are not.
• Distribution, absorption, double negation — the same laws you will meet again as Boolean algebra in section 11 and as set identities in section 03. That repetition is not coincidence; see the closing section.

Normal forms

Every formula can be rewritten in a canonical shape. CNF (conjunctive normal form) is an AND of ORs; DNF (disjunctive normal form) is an OR of ANDs. The principal or canonical forms use every variable in every term: read the true rows of the truth table off as minterms and you have principal DNF for free; read the false rows as maxterms and you have principal CNF. This is not decoration — SAT solvers, the engines behind program verification and modern scheduling, take CNF as input, and section 11's Karnaugh maps are DNF minimisation drawn as a picture.

Predicates and quantifiers

Propositional logic cannot say "every". For that you need predicates — propositions with holes, like P(x) = "x is prime" — plus two quantifiers: ∀ (for all) and ∃ (there exists). Negation flips them and pushes inwards: ¬∀x P(x) ≡ ∃x ¬P(x). "Not everyone came" means "someone didn't."

Order matters, and this is the single most common mistake in the subject. Toggle the quantifiers below and watch the meaning move.

Rules of inference

A rule of inference is a licence: given these premises, you may write that conclusion. Each one is a tautology in disguise. Click to see it fire.

Proof techniques

Four techniques cover almost everything you will meet:

• Direct. Assume p, argue to q. Works when the hypothesis gives you something to hold.
• Contraposition. Prove ¬q → ¬p instead. Try this the moment the hypothesis is useless but the negated conclusion is concrete — "if n² is even then n is even" is painful directly and trivial contrapositively.
• Contradiction. Assume p ∧ ¬q and derive an absurdity. The proof that √2 is irrational, and Euclid's proof that primes never run out.
• Induction. Prove the first case; prove that each case forces the next. Then all of them fall. This is the discrete technique, because it needs a "next" — which is exactly what continuous mathematics doesn't have. Section 07 has a live one.

Two others worth naming: proof by cases (exhaust the possibilities) and proof by construction (to show something exists, build it — often the most useful kind for an engineer, since the proof is an algorithm).

03 · Sets, relations, functions

Sets, relations and functions

The nouns, the verbs and the machines.

A set is an unordered collection of distinct things. That is the entire definition, and it is enough to build all of mathematics on. {3,1,3} is the same set as {1,3} — no order, no duplicates, which is exactly the contract of a hash set in any language you use.

Key vocabulary: |A| is cardinality; ∅ is the empty set; A ⊆ B means every element of A is in B; the power set P(A) is the set of all subsets and has 2^|A| members — the first real theorem of the course, and the reason an n-bit register has 2ⁿ states.

Relations

A relation on a set A is any subset of A × A — any collection of ordered pairs. That's it. "Is a friend of", "divides", "≤", "has an edge to", "is in the same equivalence class as" are all relations, and once you see that, a relation is just a boolean matrix, a graph, or a set of tuples in a database table, depending on which room you're standing in.

Four properties do most of the work. Click cells to toggle pairs and watch the verdicts change live:

• Reflexive: every element relates to itself — the whole diagonal is filled.
• Symmetric: the matrix equals its own transpose. Antisymmetric: never both (a,b) and (b,a) off the diagonal.
• Transitive: shortcuts always exist — if a→b and b→c then a→c.

A closure is the smallest superset with a wanted property: add the diagonal for reflexive closure, add all mirrored pairs for symmetric closure, run Warshall for transitive closure. Reachability in a network is literally the transitive closure of "has a direct link".

The two great specialisations

Take reflexive + transitive, then add one of two things and you get the two most important relation families in the subject:

• + symmetric → equivalence relation. It carves the set into disjoint equivalence classes, a partition. "Same remainder mod 5" splits the integers into 5 classes; that partition is modular arithmetic (section 10). Every equivalence relation is secretly the sentence "these things are the same for my purposes."
• + antisymmetric → partial order. That's section 04.

Functions

A function is a relation where every input has exactly one output. Three properties matter, and they are the same three properties that decide whether your data pipeline loses information:

• Injective (one-to-one): different inputs give different outputs — nothing collides. A hash function that is injective on your keys has no collisions.
• Surjective (onto): every possible output is actually hit — no wasted codomain.
• Bijective: both. Only bijections have inverses, which is why encryption must be bijective and lossy compression must not be.

The pigeonhole principle (section 07) is one sentence about injections: if the domain is bigger than the codomain, no function between them can be injective. That is the whole reason hash collisions are unavoidable.

04 · Order

Partial orders and lattices

What to do when "bigger" is only sometimes defined.

A partial order is a relation that is reflexive, antisymmetric and transitive. The word partial is the whole point: some pairs are simply incomparable. On the numbers, ≤ compares everything — that's a total order. But "divides" doesn't: 2 and 3 are incomparable, neither divides the other. Neither does "is a subset of", or "must finish before", or "is a stricter type than". A set with a partial order is a poset.

This describes reality more often than total order does. Task dependencies, class inheritance, permission levels, git commits, package versions: all posets. Every build system you have used is computing a topological sort — flattening a partial order into some total order consistent with it.

Hasse diagrams

Drawing every arrow of a partial order is unreadable, because reflexive and transitive edges are implied. A Hasse diagram strips them: draw only the covering relations (a < b with nothing strictly between), put bigger elements higher, drop the arrowheads. What remains is the skeleton.

Elements of a poset

• Maximal / minimal: nothing above / below it. There can be many.
• Greatest / least: above / below everything. There can be at most one, and often there is none.
• Upper bound of a subset: an element above all of them. The least upper bound (join, ∨) is the tightest such. Dually, greatest lower bound (meet, ∧).

A lattice is a poset where every pair has both a meet and a join. Load the butterfly example above and hunt for the pair that fails — that is what non-lattice looks like.

Why care? Because lattices are where order becomes algebra. In the divisor lattice, meet is gcd and join is lcm (section 10). In the subset lattice, meet is ∩ and join is ∪ (section 03). In the truth lattice, meet is AND and join is OR (sections 02 and 11). Three subjects, one structure. Compiler optimisation, static type systems and program analysis all run on lattices for exactly this reason: they need a principled way to merge two branches of information.

05 · Algebraic structures

Monoids and groups

Stripping an operation down to the properties that actually matter.

Here is the move that makes someone a mathematician. You notice that adding integers, multiplying matrices, composing functions, concatenating strings and rotating a square are all "the same shape of thing". So you throw away what they're made of and keep only the rules. What is left is an algebraic structure: a set S with a binary operation ∗, plus a shopping list of axioms.

Each rung buys you something concrete:

• Closure means the operation never escapes the set. int8 + int8 is closed only because it wraps — that wrap-around is arithmetic mod 256.
• Associativity means you may re-bracket freely. This is why reduce can be parallelised: (a∗b)∗(c∗d) equals a∗(b∗(c∗d)), so split the work across cores. MapReduce is a theorem about monoids.
• Identity gives you a safe starting value for an empty fold — 0 for sum, 1 for product, "" for concat, ∅ for union.
• Inverses give you undo. Groups are the mathematics of reversibility, which is why they run cryptography, error correction and every symmetry in physics.

Cayley tables

A finite group is completely described by its multiplication table. Look for the tell-tale pattern: every row and every column is a permutation of the elements — each appears exactly once. That is a theorem (the Latin square property), and it follows directly from inverses existing.

Subgroups, orders, cosets

A subgroup is a subset that is itself a group under the same operation. The order of a group is how many elements it has; the order of an element is how many times you apply it before returning to the identity. If a single element generates everything, the group is cyclic — click 1 in ℤ₆, or 3 in U(7).

Pick a subgroup H and it tiles the group into equal-sized cosets gH. Equal-sized, disjoint, covering everything — so:

Lagrange's theorem: the order of a subgroup always divides the order of the group.

That one line has enormous consequences. A group of order 7 has no proper subgroups at all, so it must be cyclic. And a corollary — a^|G| = e for every element — is exactly Fermat's little theorem when the group is the units mod p. The theorem that makes RSA work is a fact about cosets. That is the payoff of abstraction: prove it once, harvest it everywhere.

Homomorphism, isomorphism, automorphism

These are the structure-respecting maps — the functions of section 03 applied to groups:

• Homomorphism: f(a∗b) = f(a)·f(b). Operate then map = map then operate. log is the famous one: it turns multiplication into addition, which is why slide rules worked.
• Isomorphism: a bijective homomorphism. The two groups are the same group in different clothes. ℤ₄ and U(5) are isomorphic — different elements, identical table once relabelled.
• Automorphism: an isomorphism from a group to itself — a symmetry of the structure. The set of them forms a group in its own right, which is where the subject starts eating its own tail in the best way.

06 · Graphs

Graph theory

Dots and lines — and somehow half of computer science.

A graph is a set of vertices plus a set of edges between them. That is an absurdly thin definition for something this powerful. The reason it works: an enormous number of real problems are secretly "things and connections between things", and once you translate into graph language you inherit seventy years of algorithms for free.

The subject was born in 1736 when Euler asked whether you could walk all seven bridges of Königsberg exactly once. His answer invented the field: it doesn't matter where the bridges are, only how many meet at each landmass. Throw away the geography, keep the connections. That is the founding act of discrete mathematics.

The vocabulary

• Degree — edges touching a vertex. Handshake lemma: the degrees sum to twice the edge count, so the number of odd-degree vertices is always even. Your first graph proof, and it is one line.
• Walk — any sequence of adjacent vertices. Trail — no repeated edge. Path — no repeated vertex. Circuit — closed trail. Cycle — closed path. The distinctions look pedantic until you meet Euler and Hamilton, whose entire difference is edges-vs-vertices.
• Connected — a path exists between every pair. Components are the maximal connected chunks.

Where a graph is fragile

A bridge is an edge whose removal disconnects the graph; a cut vertex (articulation point) is a vertex whose removal does. Load "Bridged pair" and run the analysis. This is not academic: in a network topology, bridges and cut vertices are your single points of failure, and Tarjan's algorithm finds all of them in one depth-first pass.

Independence, covering, matching

Three intertwined notions. An independent set is vertices with no edge between any two — think mutually non-conflicting tasks. A vertex cover is a set of vertices touching every edge — think guards on corridors. They are exact complements: S is independent ⟺ its complement is a cover, so maximising one minimises the other. A matching is a set of edges with no shared endpoint — pairing people to tasks, students to projects, kidneys to patients.

Bipartite graphs

A graph is bipartite if you can 2-colour it: two teams, edges only between teams. The clean theorem: bipartite ⟺ no odd cycle. Bipartite graphs are where matching becomes tractable — König's theorem says maximum matching = minimum vertex cover there, and Hall's theorem tells you exactly when everyone can be matched. Every assignment problem you meet at work is this.

Planarity and colouring

A graph is planar if it can be drawn with no edges crossing — the question a PCB designer asks about a single-layer board. Euler's formula for connected planar graphs: V − E + F = 2. From it falls E ≤ 3V − 6, which instantly proves K₅ is not planar. Kuratowski's theorem completes the story: a graph is planar exactly when it contains no K₅ or K₃,₃ hiding inside it. Both are loaded as presets above — the two smallest obstructions in all of graph theory.

Graph colouring asks for the fewest colours such that adjacent vertices differ. It is register allocation in a compiler, exam timetabling, and frequency assignment for cell towers, all the same problem. Every planar graph needs at most four colours — proved in 1976, the first major theorem to require a computer, which caused a philosophical argument that hasn't fully ended.

07 · Counting

Combinatorics

"How many?" — the question underneath complexity analysis, probability and optimisation.

Counting sounds like the easiest thing in mathematics and is reliably the hardest to get right. Everything rests on two rules. Product rule: independent choices multiply — m shirts and n trousers give mn outfits. Sum rule: disjoint alternatives add. Almost every counting error in existence is either multiplying when you should add, or forgetting that your cases overlap.

Mathematical induction

Before counting, the tool for proving counting claims. Induction has exactly two obligations: the base case (the first domino falls) and the inductive step (each domino knocks the next). Both, or nothing.

Permutations and combinations

Two questions, one distinction: does order matter?

• P(n,r) = n!/(n−r)! — ordered selections. Podium finishes, passwords, rankings.
• C(n,r) = n!/(r!(n−r)!) — unordered selections. Committees, hands of cards, subsets. Written ⁿCᵣ or (n choose r).

The relationship is worth internalising: C(n,r) = P(n,r)/r! — count the ordered ways, then divide out the r! orderings you didn't care about. That "overcount then divide by the symmetry" move is the single most reusable trick in combinatorics.

The pigeonhole principle

If n items go into k boxes and n > k, some box holds at least two. It is so obvious it feels like cheating, and it proves startling things: any 13 people share a birth month; in London at least two people have exactly the same number of hairs; any 5 points in a unit square include a pair within √2/2. Generalised form: some box holds at least ⌈n/k⌉.

Inclusion–exclusion

The fix for double-counting. For two sets |A ∪ B| = |A| + |B| − |A ∩ B|; for three, add the singles, subtract the pairs, add the triple back. In general alternate signs across all intersections. Drag the sizes and watch the arithmetic:

08 · Sequences

Recurrence relations and generating functions

Two ways to turn "it depends on the previous one" into a formula.

A recurrence relation defines each term from earlier terms plus a base case. F(n) = F(n−1) + F(n−2), F(0)=0, F(1)=1 is Fibonacci. Recurrences are how recursive algorithms describe their own cost: merge sort satisfies T(n) = 2T(n/2) + n, and solving that recurrence is proving it runs in n log n.

To solve a linear homogeneous recurrence, guess aⁿ, substitute, and you get the characteristic equation. Its roots give the closed form. Distinct roots r₁, r₂ give A r₁ⁿ + B r₂ⁿ; a repeated root r gives (A + Bn) rⁿ. The constants come from the base cases.

Notice what happens with Fibonacci: the roots are (1±√5)/2 — the golden ratio walks out of a purely discrete question. And notice the growth rate is governed entirely by the largest root. That is the general lesson: the characteristic root is the growth rate, which is exactly what you want to know about an algorithm.

Generating functions

The slickest idea in elementary combinatorics. Take a sequence a₀, a₁, a₂, … and hang it on the coefficients of a formal power series:

G(x) = a₀ + a₁x + a₂x² + a₃x³ + ⋯

You never evaluate x. It is a clothes hanger — a way to carry an infinite sequence as a single algebraic object, so that operations on sequences become operations on functions. Shifting a sequence becomes multiplying by x. Convolving two sequences (the sum-over-all-splits that appears everywhere in counting) becomes plain multiplication. Suddenly a recurrence becomes an equation you can solve with school algebra.

09 · Uncertainty

Discrete probability

Counting, but the outcomes have weights.

Probability begins as combinatorics with a denominator. A sample space S is the set of possible outcomes; an event is a subset of it — so events are sets and all of section 03 applies unchanged. When outcomes are equally likely, P(E) = |E|/|S|, and you are back to counting.

Kolmogorov's three axioms are all you need to assume: probabilities are non-negative; P(S) = 1; and disjoint events add. Everything else is a theorem, including P(Aᶜ) = 1 − P(A) and the inclusion–exclusion rule P(A ∪ B) = P(A) + P(B) − P(A ∩ B) — the very same principle from section 07, now with weights.

Conditional probability and Bayes

P(A|B) = P(A ∩ B)/P(B) — restrict the universe to B and re-normalise. Independence means P(A|B) = P(A): learning B told you nothing. Rearranging the definition twice gives Bayes' theorem, which reverses the direction of a conditional:

P(H|E) = P(E|H) · P(H) / P(E)

This is the mathematics of updating a belief when evidence arrives — the engine under spam filters, medical screening, A/B tests and every Bayesian model in your stack. Its most famous lesson is that a very accurate test for a very rare condition still produces mostly false positives, and no amount of intuition prepares people for it. Move the sliders:

Random variables and distributions

A random variable assigns a number to each outcome, so you can average it. Expectation E[X] = Σ x·P(x) is the long-run mean; variance measures spread. Expectation is linear even when variables are dependent — E[X+Y] = E[X] + E[Y] always — which is the workhorse behind average-case algorithm analysis.

Four distributions cover most of what you will meet. The first three are discrete; the last is the continuous one that keeps showing up as a limit of the others — the border from section 00, crossed in plain sight.

• Uniform: every outcome equally likely. Fair dice, random array index.
• Binomial: number of successes in n independent trials, P(k) = C(n,k)p^k(1−p)^n−k — note the combination from section 07 sitting inside it. Conversions, retries, coin flips.
• Poisson: count of rare events in a fixed window. It is the binomial as n→∞, p→0 with np = λ fixed. Requests per second, defects per batch, arrivals per minute.
• Exponential: the waiting time between Poisson events — continuous, memoryless, and the standard model for time-to-failure and inter-arrival gaps.
• Normal: the limit of sums. The central limit theorem says almost anything built by adding many independent contributions ends up here, which is why the bell curve appears in places that have nothing to do with each other.

Set the binomial to n = 50 and watch it grow a bell shape; set Poisson's λ high and watch the same thing. That convergence is the clearest single picture of discrete becoming continuous.

10 · Integers

Number theory and modular arithmetic

The oldest pure mathematics, now guarding your bank account.

Number theory studies the integers, and its central fact is the fundamental theorem of arithmetic: every integer above 1 factors into primes in exactly one way. Primes are the atoms; there are infinitely many (Euclid, by contradiction, in four lines); and finding them inside a large number is so hard that we have built the entire internet's security on that difficulty.

Division, gcd, and Euclid's algorithm

The division algorithm says any a, b give unique q, r with a = bq + r and 0 ≤ r < b. From it comes the observation that powers the oldest non-trivial algorithm still in daily use: gcd(a,b) = gcd(b, a mod b). Any common divisor of a and b divides the remainder too, so replace the pair with a smaller pair and repeat. It terminates in O(log) steps — a fact first proved via Fibonacci numbers, connecting straight back to section 08.

Modular arithmetic

Work with remainders and the integers collapse into a finite wheel. a ≡ b (mod n) means n divides a − b. This is an equivalence relation (section 03) whose classes are the n possible remainders — and those classes form a group under addition (section 05). Clocks, hashing, checksums, cyclic buffers, ISBN and NRIC check digits are all arithmetic mod something.

Fermat's little theorem

If p is prime and p ∤ a, then a^p−1 ≡ 1 (mod p). Section 05 already explained why: the non-zero residues mod p form a group of order p−1, and Lagrange's theorem forces every element to the identity when raised to the group's order. Two consequences you will actually use:

• Modular inverses: a^p−2 is the inverse of a mod p. Every competitive programmer's "divide under a prime modulus" trick.
• Primality testing: if aⁿ⁻¹ ≢ 1 (mod n) then n is definitely composite — no factoring required. Miller–Rabin refines this into the test that generates the primes in your TLS certificates.

11 · Two values

Boolean algebra

Where logic becomes hardware.

Boolean algebra is section 02's propositional logic, rewritten as arithmetic on {0,1} and equipped with a purpose: describing circuits. Shannon's 1937 master's thesis — the most consequential ever written — noticed that a relay network obeys exactly the laws Boole had written for the "laws of thought" a century earlier. AND is a series pair of switches; OR is parallel; NOT is an inverter. All of digital computing follows.

The laws should look familiar by now, because they are the set identities and the logical equivalences again: commutative, associative, distributive (both ways, unlike ordinary arithmetic), identity, complement, idempotence A + A = A, absorption A + AB = A, and De Morgan (AB)' = A' + B'.

Two structural facts. Every Boolean expression has a dual, obtained by swapping AND↔OR and 0↔1; if a theorem is true, so is its dual — you get half your results free. And every Boolean function of n variables is one of 2^(2ⁿ) possibilities: 2ⁿ input rows, each independently mapped to 0 or 1. For n = 2 that's 16 functions; for n = 4, 65,536; for n = 6, more than the atoms in a small mountain.

Minimisation with a Karnaugh map

A Boolean function has infinitely many equivalent expressions and you want a small one, because small means fewer gates, less power, less delay. A K-map rearranges the truth table so that adjacent cells differ in exactly one variable (Gray code order) — then any rectangular block of 2ᵏ ones is a term with k variables eliminated. Bigger blocks, simpler expression.

12 · Strategy

Game theory

Discrete mathematics when the other side is also thinking.

You asked where game theory fits, and the answer is: it is what happens when you point combinatorics and probability at a situation containing other decision-makers. Every other section assumes the world is indifferent to your choices. Game theory drops that assumption, and everything gets harder and more interesting.

A game is players, strategies, and a payoff function — a function (section 03) from strategy profiles to outcomes. A Nash equilibrium is a profile where no single player can improve by changing alone. Its existence is guaranteed (allowing randomised strategies) by a fixed-point theorem, which is continuous mathematics quietly paying a debt to the discrete side.

Three connections worth holding onto:

• To graphs: combinatorial games (Nim, chess, Go) are directed graphs of positions, and solving them is a labelling problem on that graph. Sprague–Grundy theory says every impartial game is equivalent to a single pile of Nim — an isomorphism, in the exact sense of section 05.
• To probability: mixed strategies are probability distributions over moves, and equilibrium is found by making your opponent indifferent — an expectation calculation from section 09.
• To your work: auction design, incentive schemes, adversarial machine learning, and multi-agent AI systems are all applied game theory. So is every "if we nudge this way, how do people respond" question in product design.

13 · Synthesis

How it all comes together

The same handful of ideas, met in different rooms.

Here is the honest structure of the subject, once the syllabus stops pretending these are ten separate topics.

Logic is the floor. It licenses every step of every argument in every other section. Set theory is the ground. Every object — a graph, a group, a sample space, a Boolean function — is defined as a set with structure imposed on it. Relations are the first structure, and everything after that is a relation with adjectives: make it symmetric and you get an equivalence (modular arithmetic); make it antisymmetric and you get an order (lattices, dependencies); draw it and you get a graph.

Counting is the measuring tape. It sizes everything else — how many subsets, how many colourings, how many keys an attacker must try. Add weights and it becomes probability. Algebra is the compression. Once you have met union, gcd, AND and join in four separate sections and noticed they obey identical laws, you name the pattern (lattice, monoid, group), prove things once, and inherit them everywhere.

A single worked chain

To see all of it at once, follow RSA end to end. Number theory supplies primes and the difficulty of factoring. Euclid's algorithm computes the private key from the public one. Group theory — Lagrange's theorem — proves that decryption actually undoes encryption. Combinatorics tells you the key space is too large to search. Probability bounds the error of the primality test that generated the keys. Logic holds the security proof together. Graph theory and Boolean algebra describe the circuit that executes it. Six branches, one padlock, and until 1977 not one of them was considered useful.

14 · Practice

How to actually learn this

An order that works, and the honest reason for it.

Three habits that separate people who get it from people who don't

• Compute small cases obsessively. Before proving anything about n, do n = 1, 2, 3 by hand. Almost every theorem in this subject was noticed as a pattern in small cases first. If you cannot count the subsets of {a,b,c} on paper, the formula will never be more than a formula.
• Write the proof out, badly, then fix it. Reading a proof teaches you nothing you can reuse; the understanding lives in the failure to write it. Aim for "would a sceptical reader have to agree?" rather than elegance.
• Translate everything into code once. Implement Warshall, greedy colouring, extended Euclid, a K-map minimiser. The implementation forces the edge cases into the open, and it is the fastest route from "I've seen this" to "I own this."

For exams like GATE or UGC NET, the weighting is predictable: logic, sets and relations, counting, graph theory and modular arithmetic carry the most marks and are the most mechanical. For interviews and competitive programming, the return concentrates in counting, recurrences, graphs and number theory. For actual engineering work, the highest-leverage sections are graphs, probability and Boolean algebra — but the ones that quietly change how you think are logic and algebra.

Discrete mathematics rewards a specific kind of stubbornness: refusing to accept a claim until you can see why it could not be otherwise. Everything else in the subject is vocabulary.