Discrete Mathematics for AI

Discrete mathematics starts with sets — well-defined, unordered collections of distinct objects — because nearly every data structure an AI system manipulates is, underneath, a set or an operation on sets. MIT's open textbook Mathematics for Computer Science, used in MIT's 6.042J course, treats sets, sequences, functions, and relations together as the field's basic 'mathematical data types,' the vocabulary every later topic in the course builds on. Concretely: suppose a machine-learning project has a labeled dataset D = {email1, email2, email3, email4, email5} and splits it into a training set A = {email1, email2, email3} and a test set B = {email3, email4, email5}. The union A ∪ B recovers the full dataset D; the intersection A ∩ B = {email3} identifies the one example that, by a labeling mistake, ended up in both splits — exactly the kind of data-leakage bug that set operations make trivial to detect by simple inspection. The set difference A − B = {email1, email2} gives the examples used only for training. None of this requires anything beyond the basic definitions of union, intersection, and difference, yet checking that a train/test split is a genuine partition — disjoint sets whose union is the whole dataset — is one of the most common and consequential sanity checks in applied machine learning.

A relation on a set formalizes 'how elements are connected,' and a function is the special case of a relation where every input is connected to exactly one output — a distinction that matters enormously once a program has to compute rather than merely represent. Levin's open textbook Discrete Mathematics: An Open Introduction develops relations and functions as core structures alongside logic, counting, and graphs, explicitly building the vocabulary needed before combinatorics or recurrences make sense. Consider a concrete relation R on the set {1, 2, 3, 4, 5, 6} defined by 'x R y if x mod 3 equals y mod 3.' Checking a few pairs by hand shows (1,4) is in R since 1 mod 3 = 4 mod 3 = 1, and (2,5) is in R for the same reason, while (1,2) is not, since 1 mod 3 = 1 and 2 mod 3 = 2. This relation is reflexive (every element relates to itself), symmetric (if x R y then y R x), and transitive (if x R y and y R z then x R z) — the three properties that together define an equivalence relation, one that partitions the set into groups of mutually related elements: {1,4}, {2,5}, {3,6}. The function f(x) = x mod 3 generates exactly this equivalence relation: f maps each of 1 through 6 to a single output in {0,1,2}, and 'maps to the same output under f' is the general recipe by which any function partitions its domain into equivalence classes.

Combinatorics answers the question 'how many' precisely enough to reason about the size of a search space before running an algorithm over it, and it is treated as a full part of the MIT 6.042 curriculum under 'Counting,' covering cardinality rules and generating functions. The two workhorse counting rules are permutations (ordered selections) and combinations (unordered selections). Suppose an AI team is choosing 3 input features to keep out of a pool of 10 candidate features, and the order in which the 3 are listed does not matter. The number of possible feature subsets is the binomial coefficient C(10,3) = 10! / (3! × 7!) = (10 × 9 × 8) / (3 × 2 × 1) = 720 / 6 = 120. If instead the team needed to assign 3 of those features to 3 distinct, ordered roles — say, first-stage filter, second-stage filter, and final tiebreaker — order would matter, and the count becomes the permutation P(10,3) = 10 × 9 × 8 = 720, six times larger, exactly the 3! = 6 orderings of each unordered subset. This single distinction, ordered versus unordered selection, is what separates a feature-selection search space of 120 candidates from one of 720, and getting it wrong silently multiplies or divides the actual cost of an exhaustive search by a fixed, computable factor.

A recurrence relation defines a sequence by expressing each term in terms of earlier terms, and it is the natural language for describing the running time of any recursive or divide-and-conquer algorithm — exactly why MIT 6.042 devotes its final unit to recurrence relations, using the Towers of Hanoi puzzle and divide-and-conquer algorithms like merge sort as its running examples. In the classic Towers of Hanoi puzzle, moving n disks requires first moving the top n−1 disks out of the way, then moving the largest disk, then moving the n−1 disks back on top, giving the recurrence T(n) = 2·T(n−1) + 1, with base case T(1) = 1. Unrolling this by hand for small n makes the pattern concrete: T(1) = 1, T(2) = 2·T(1) + 1 = 3, T(3) = 2·T(2) + 1 = 7, T(4) = 2·T(3) + 1 = 15 — each term is one less than a power of 2, so the closed form is T(n) = 2^n − 1. The identical recurrence structure — 'solve two smaller subproblems, then do a fixed amount of extra work' — appears throughout AI, such as in a recursive game-tree search that must explore both a move and its opposing reply, and being able to unroll and solve such a recurrence by hand is what lets a researcher predict whether a proposed recursive algorithm will finish in seconds or centuries before ever running it.

Boolean algebra formalizes reasoning with statements that are simply true or false, combined with the operators AND, OR, and NOT, and it underlies both classical rule-based AI systems and the propositional logic covered under 'Logical Formulas' in MIT 6.042's first unit. Consider a simple spam-filtering rule expressed as a Boolean formula: FLAG = (score > 0.8) AND (sender_unknown OR NOT previously_seen). Evaluating this by hand for a concrete email with score = 0.9, sender_unknown = TRUE, and previously_seen = FALSE proceeds mechanically: NOT previously_seen is TRUE, so (sender_unknown OR NOT previously_seen) is TRUE OR TRUE = TRUE; (score > 0.8) is TRUE; so FLAG = TRUE AND TRUE = TRUE, and the email is flagged. A full truth table for this formula would list all eight combinations of the three Boolean inputs and confirm the output for each — a small enough table to construct entirely by hand, and a useful discipline for catching a rule that unintentionally flags, or unintentionally never flags, some combination of conditions the designer had not consciously considered.