Log in

Discrete mathematics glossary

Short definitions of the terms you will meet most often. Each entry links to the topic page with a calculator and a worked study guide. Looking for an order to study in? See the learning path.

A

Adjacency matrix
A square matrix whose (i, j) entry records whether, or how many edges, join vertex i to vertex j. Its k-th power counts walks of length k. See Matrices.
Antisymmetric relation
A relation in which (a, b) and (b, a) can both be present only when a = b. See Relations.
Associativity
A property of an operation ∘ where (a ∘ b) ∘ c = a ∘ (b ∘ c) for all elements. See Algebraic Structures.

B

Bayes' theorem
A rule that reverses conditional probabilities: P(A | B) = P(B | A)·P(A) / P(B). See Probability.
Big-O notation
An upper bound on how fast a function grows, used to describe the running time or memory use of an algorithm for large inputs. See Algorithms & Complexity.
Bijection
A function that is both injective and surjective, so every codomain element has exactly one preimage. See Functions.
A search that repeatedly halves a sorted list by comparing the target with the middle element; it takes O(log n) steps. See Algorithms & Complexity.
Bipartite graph
A graph whose vertices can be split into two groups so that every edge joins different groups; equivalently, a graph with no odd cycle. See Graph Theory.
Boolean function
A function from n binary inputs to a binary output. There are 2^(2ⁿ) of them for n variables. See Boolean Algebra.

C

Cartesian product
For sets A and B, the set A × B of all ordered pairs (a, b) with a in A and b in B. See Set Theory.
Cayley table
A table listing the result of a ∘ b for every pair of elements of a finite structure. See Algebraic Structures.
Characteristic equation
For aₙ = c₁aₙ₋₁ + c₂aₙ₋₂, the equation x² − c₁x − c₂ = 0 whose roots determine the closed form. See Recurrence Relations.
Closure (of a relation)
The smallest relation containing a given relation that also has a stated property such as reflexivity, symmetry or transitivity. See Relations.
Combination
An unordered selection of r items from n, counted by C(n, r) = n! / (r!(n − r)!). See Counting.
Complement
For a set A inside a universal set U, the set of elements of U that are not in A. See Set Theory.
Composition (of functions)
The function g ∘ f defined by (g ∘ f)(x) = g(f(x)); f is applied first. See Functions.
Conditional probability
The probability of A given that B has occurred: P(A | B) = P(A ∩ B) / P(B). See Probability.
Congruence
a ≡ b (mod m) means m divides a − b; a and b leave the same remainder on division by m. See Number Theory.
Contrapositive
For P → Q, the statement ¬Q → ¬P, which is logically equivalent to the original. See Propositional Logic.
Cycle
A path in a graph that starts and ends at the same vertex without repeating other vertices. See Graph Theory.

D

De Morgan's laws
¬(P ∧ Q) ≡ ¬P ∨ ¬Q and ¬(P ∨ Q) ≡ ¬P ∧ ¬Q; the same holds for sets and Boolean algebra. See Propositional Logic.
Degree (of a vertex)
The number of edges incident to a vertex. The degrees of a graph sum to twice its number of edges. See Graph Theory.
Deterministic finite automaton (DFA)
A machine with finitely many states and exactly one transition for each state and input symbol; it accepts a string if it ends in an accepting state. See Automata.
Dijkstra's algorithm
A greedy shortest-path algorithm for graphs with non-negative edge weights. See Graph Algorithms.

E

Equivalence relation
A relation that is reflexive, symmetric and transitive; it partitions a set into equivalence classes. See Relations.
Euclidean algorithm
A method for computing gcd(a, b) by repeatedly replacing (a, b) with (b, a mod b) until the remainder is 0. See Number Theory.
Euler circuit
A closed walk that uses every edge of a graph exactly once; it exists in a connected graph when every vertex has even degree. See Graph Theory.
Euler's totient φ(n)
The number of integers from 1 to n that are coprime to n. See Number Theory.
Expected value
The probability-weighted average of the values of a random variable: E[X] = Σ x·P(x). See Probability.

F

Fibonacci sequence
The sequence defined by F₀ = 0, F₁ = 1 and Fₙ = Fₙ₋₁ + Fₙ₋₂. See Recurrence Relations.
Full adder
A circuit that adds two bits and a carry-in, producing a sum bit and a carry-out. See Logic Circuits.

G

Greatest common divisor (GCD)
The largest positive integer that divides each of two given integers. See Number Theory.
Group
A set with an associative operation, an identity element, and an inverse for every element. See Algebraic Structures.

H

Hamming code
An error-correcting code that adds parity bits at power-of-two positions so any single-bit error can be located and fixed. See Coding Theory.
Hamming distance
The number of positions at which two equal-length strings differ. See Coding Theory.
Handshaking lemma
The sum of all vertex degrees in a graph equals twice the number of edges. See Graph Theory.

I

Induction
A proof technique: prove a base case and show that truth for k implies truth for k + 1. See Proofs.
Injection
A function in which different inputs always give different outputs (one-to-one). See Functions.
Inverse (modular)
For a modulo m, a number b with ab ≡ 1 (mod m); it exists exactly when gcd(a, m) = 1. See Number Theory.

M

Minterm
A product term that contains every variable, complemented or not, and equals 1 for exactly one input combination. See Boolean Algebra.
Monoid
A set with an associative operation and an identity element. See Algebraic Structures.

N

Nondeterministic finite automaton (NFA)
A finite automaton that may have several transitions, or ε-transitions, from a state; it accepts if some path accepts. See Automata.

P

Partial order
A relation that is reflexive, antisymmetric and transitive. See Relations.
Permutation
An ordered arrangement of items; P(n, r) = n! / (n − r)! counts arrangements of r items from n. See Counting.
Pigeonhole principle
If more than k items are placed into k boxes, at least one box contains at least two items. See Counting.
Power set
The set of all subsets of a set A; it has 2^|A| elements. See Set Theory.
Predicate
A statement with variables, such as P(x): “x is even”, that becomes true or false once the variables are given values. See Predicate Logic.
Prime number
An integer greater than 1 whose only positive divisors are 1 and itself. See Number Theory.

Q

Quantifier
A symbol, ∀ (for all) or ∃ (there exists), that states how many members of a domain satisfy a predicate. See Predicate Logic.

R

Recurrence relation
An equation that defines each term of a sequence using earlier terms. See Recurrence Relations.
Reflexive relation
A relation containing (a, a) for every element a. See Relations.

S

Spanning tree
A subgraph of a connected graph that includes every vertex and is a tree. See Trees.
Surjection
A function whose range equals its codomain: every element of the codomain is an output. See Functions.

T

Tautology
A formula that is true under every assignment of truth values. See Propositional Logic.
Topological sort
A linear ordering of the vertices of a directed acyclic graph in which every edge points forward. See Graph Algorithms.
Transitive relation
A relation in which (a, b) and (b, c) together imply (a, c). See Relations.
Tree
A connected graph with no cycles; a graph on n vertices is a tree when it is connected with n − 1 edges. See Trees.
Truth table
A table listing the value of a formula for every combination of truth values of its variables. See Propositional Logic.

U

Universal set
The set of all elements under consideration, against which complements are taken. See Set Theory.

V

Venn diagram
A diagram that uses overlapping regions to show the relationships between sets. See Set Theory.