Skip to content

Glossary

The number in brackets after each definition is the chapter where the term is introduced.

A

Adjacency matrix
For a graph with vertices \(v_1, \dots, v_n\), the \(n \times n\) matrix whose \((i, j)\) entry is the number of edges joining \(v_i\) and \(v_j\). (11)
Antisymmetric relation
A relation in which \(a \mathrel{R} b\) and \(b \mathrel{R} a\) together imply \(a = b\). (5)
Argument
A list of premises followed by a conclusion; it is valid if the conclusion must be true whenever all the premises are. (1)

B

Basis step
The part of a proof by induction that proves the statement for the first value. (6)
Bayes' theorem
The formula \(p(F \mid E) = p(E \mid F)p(F) / \bigl(p(E \mid F)p(F) + p(E \mid \overline{F})p(\overline{F})\bigr)\), which reverses a conditional probability. (8)
Bijection
A function that is both one-to-one and onto; exactly the functions that have inverses. (4)
Binomial coefficient
\(\binom{n}{r} = \dfrac{n!}{r!(n-r)!}\), the number of \(r\)-element subsets of an \(n\)-element set. (7)
Bipartite graph
A graph whose vertices split into two sets with every edge joining the two sets; equivalently, a graph with no cycle of odd length. (11)
Boolean algebra
A set with two operations, a complement and elements 0 and 1 satisfying the identity, complement, associative, commutative and distributive laws; \(\{0, 1\}\) with OR, AND and NOT is the main example. (13)

C

Cardinality
The number of elements of a finite set; for infinite sets, two sets have the same cardinality when there is a bijection between them. (4)
Cartesian product
\(A \times B\), the set of ordered pairs \((a, b)\) with \(a \in A\) and \(b \in B\). (4)
Characteristic equation
For the recurrence \(a_n = c_1a_{n-1} + \dots + c_ka_{n-k}\), the equation \(r^k - c_1r^{k-1} - \dots - c_k = 0\), whose roots give the solutions \(r^n\). (9)
Chromatic number
The least number of colours needed to colour the vertices of a graph so that adjacent vertices get different colours. (11)
Combination
An unordered selection of objects; an \(r\)-combination of a set is a subset with \(r\) elements. (7)
Conditional probability
\(p(E \mid F) = p(E \cap F)/p(F)\), the probability of \(E\) given that \(F\) has happened. (8)
Congruence
\(a \equiv b \pmod{m}\) means that \(m\) divides \(a - b\). (5, 10)
Connected graph
A graph with a path between every pair of vertices. (11)
Contrapositive
Of \(p \to q\), the conditional \(\neg q \to \neg p\), which is logically equivalent to it. (1)
Countable set
A set that is finite or can be listed as a sequence \(a_1, a_2, \dots\); \(\mathbb{Z}\) and \(\mathbb{Q}\) are countable and \(\mathbb{R}\) is not. (4)
Counterexample
An element for which a universal statement fails; one counterexample disproves the statement. (2, 3)

D

De Morgan's laws
\(\neg(p \wedge q) \equiv \neg p \vee \neg q\) and \(\neg(p \vee q) \equiv \neg p \wedge \neg q\), with versions for sets, quantifiers and Boolean algebra. (1)
Derangement
A permutation that leaves no element in its original position. (7)
Deterministic finite automaton (DFA)
A machine \((Q, \Sigma, \delta, q_0, F)\) that reads a string one symbol at a time, moving between finitely many states, and accepts if it ends in a state of \(F\). (14)
Divides
For integers \(a \ne 0\) and \(b\), \(a \mid b\) when \(b = ak\) for some integer \(k\). (3, 10)

E

Equivalence class
The set of all elements equivalent to a given element under an equivalence relation. (5)
Equivalence relation
A relation that is reflexive, symmetric and transitive. (5)
Euler circuit
A circuit that uses every edge of a graph exactly once; it exists in a connected multigraph exactly when every degree is even. (11)
Euler's formula
\(v - e + f = 2\) for a connected planar graph drawn in the plane with \(v\) vertices, \(e\) edges and \(f\) faces. (11)
Expected value
\(E(X) = \sum_r r\,p(X = r)\), the long-run average of a random variable. (8)

F

Function
A rule \(f : A \to B\) that assigns to each element of \(A\) exactly one element of \(B\). (4)
Functionally complete
A set of connectives or operations from which every truth table or Boolean function can be built; NAND alone is an example. (1, 13)

G

Generating function
The power series \(\sum_{n \ge 0} a_nx^n\) whose coefficients are the terms of a sequence. (9)
Greatest common divisor
The largest integer that divides both of two integers, not both zero; computed by Euclid's algorithm. (10)

H

Hamilton circuit
A cycle that visits every vertex of a graph exactly once. (11)
Handshaking theorem
In every graph the sum of the degrees is twice the number of edges. (11)
Hasse diagram
A drawing of a partial order that shows only the covering pairs, with larger elements higher. (5)

I

Inclusion-exclusion
The principle that the size of a union equals the sum of the sizes of the sets, minus the sizes of the pairwise intersections, plus the triple intersections, and so on. (7)
Independent events
Events \(E\) and \(F\) with \(p(E \cap F) = p(E)\,p(F)\). (8)
Inductive hypothesis
In a proof by induction, the assumption that the statement holds for \(k\) (or for all values up to \(k\)), used to prove it for \(k + 1\). (6)
Isomorphism
A bijection between the vertex sets of two graphs that preserves adjacency. (11)

K

Karnaugh map
A grid of the minterms of a Boolean function arranged so that adjacent cells differ in one variable, used to simplify the function. (13)
Kleene star
For a language \(A\), the set \(A^{*}\) of all concatenations of zero or more strings from \(A\). (14)

L

Language
A set of strings over an alphabet. (14)
Logically equivalent
Two compound propositions with the same truth value in every row of their truth table. (1)
Loop invariant
A statement about a program's variables that holds before a loop and after every pass, used to prove the loop correct. (6)

M

Mathematical induction
The proof method that proves \(P(b)\) and that \(P(k)\) implies \(P(k+1)\) for all \(k \ge b\), and concludes \(P(n)\) for all \(n \ge b\). (6)
Minimum spanning tree
A spanning tree of a weighted graph with the least possible total weight; found by Kruskal's or Prim's algorithm. (12)
Minterm
A product of literals, one for each variable, which equals 1 for exactly one combination of values. (13)
Modular inverse
An integer \(\bar{a}\) with \(a\bar{a} \equiv 1 \pmod m\); it exists exactly when \(\gcd(a, m) = 1\). (10)

N

Nondeterministic finite automaton (NFA)
A finite automaton that may have several possible moves, or none, from a state on a symbol; it accepts if some run ends in an accepting state. (14)

O

One-to-one (injective)
A function in which different elements have different images. (4)
Onto (surjective)
A function whose range is the whole codomain. (4)

P

Partial order
A relation that is reflexive, antisymmetric and transitive. (5)
Partition
A collection of non-empty, pairwise disjoint subsets of a set whose union is the whole set. (5)
Permutation
An ordered arrangement of objects; there are \(P(n, r) = n!/(n-r)!\) ordered arrangements of \(r\) of \(n\) objects. (7)
Pigeonhole principle
If \(N\) objects are placed in \(k\) boxes, some box contains at least \(\lceil N/k \rceil\) objects. (7)
Planar graph
A graph that can be drawn in the plane without edges crossing. (11)
Power set
The set \(\mathcal{P}(A)\) of all subsets of \(A\); it has \(2^{\lvert A \rvert}\) elements. (4)
Predicate
A statement containing variables that becomes a proposition when the variables are given values. (2)
Prefix code
A code in which no codeword is the beginning of another, so that messages can be decoded without separators. (12)
Prime
An integer greater than 1 whose only positive divisors are 1 and itself. (3, 10)
Proposition
A declarative sentence that is either true or false, but not both. (1)

Q

Quantifier
The universal quantifier \(\forall\) ("for all") or the existential quantifier \(\exists\) ("there exists"). (2)

R

Random variable
A function from the sample space of an experiment to the real numbers. (8)
Recurrence relation
An equation that expresses each term of a sequence in terms of earlier terms. (9)
Reflexive relation
A relation on \(A\) with \(a \mathrel{R} a\) for every \(a \in A\). (5)
Regular expression
An expression built from symbols, \(\lambda\) and \(\varnothing\) with union, concatenation and Kleene star, denoting a regular language. (14)
Relation
A subset of a Cartesian product \(A \times B\); a relation on \(A\) is a subset of \(A \times A\). (5)
RSA
A public-key cryptosystem with public key \((n, e)\), \(n = pq\), and private key \(d = e^{-1} \bmod (p-1)(q-1)\); it encrypts by \(C = M^e \bmod n\). (10)
Rule of inference
A basic valid argument form, such as modus ponens, used as one step of a proof. (1)

S

Sample space
The set of all possible outcomes of an experiment. (8)
Spanning tree
A subgraph of a connected graph that is a tree and contains every vertex. (12)
Strong induction
Induction in which the inductive step assumes the statement for all values from the basis up to \(k\). (6)
Symmetric relation
A relation in which \(a \mathrel{R} b\) implies \(b \mathrel{R} a\). (5)

T

Tautology
A compound proposition that is true in every row of its truth table. (1)
Topological sort
A listing of the elements of a finite partial order in which every element comes after all the elements below it. (5)
Transitive closure
The smallest transitive relation containing a given relation; it relates \(a\) to \(b\) when there is a path from \(a\) to \(b\). (5)
Transitive relation
A relation in which \(a \mathrel{R} b\) and \(b \mathrel{R} c\) imply \(a \mathrel{R} c\). (5)
Tree
A connected graph with no cycles; a tree with \(n\) vertices has \(n - 1\) edges. (12)
Truth table
A table that gives the truth value of a compound proposition for every combination of truth values of its variables. (1)

V

Valid argument
An argument whose conclusion is true whenever all its premises are true. (1)
Venn diagram
A picture of sets as regions inside a rectangle representing the universal set. (4)

W

Well-ordering principle
Every non-empty set of natural numbers has a least element. (6)