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)