Final exam note sheet
The whole course: the tables of the three midterm sheets
This sheet comes printed with the final exam. You may not bring your own notes, so study with this sheet. It leaves out some results; the full definitions are in the notes. Download the PDF to print it.
Logic
| \(P\) | \(Q\) | \(\neg P\) | \(P \land Q\) | \(P \lor Q\) | \(P \Rightarrow Q\) | \(P \Leftrightarrow Q\) |
|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |
| Logically equivalent | \(A \equiv B\): \(A\) and \(B\) have the same truth value in every row |
| Double negation | \((\neg \neg P) \equiv P\) |
| De Morgan | \((\neg (P \land Q)) \equiv ((\neg P) \lor (\neg Q))\) |
| \((\neg (P \lor Q)) \equiv ((\neg P) \land (\neg Q))\) | |
| Conditional | \((P \Rightarrow Q) \equiv ((\neg P) \lor Q)\) |
| Biconditional | \((P \Leftrightarrow Q) \equiv ((P \Rightarrow Q) \land (Q \Rightarrow P))\) |
| Distributive | \((P \land (Q \lor R)) \equiv ((P \land Q) \lor (P \land R))\) |
| \((P \lor (Q \land R)) \equiv ((P \lor Q) \land (P \lor R))\) | |
| Converse of \(P \Rightarrow Q\) | \(Q \Rightarrow P\) |
| Contrapositive of \(P \Rightarrow Q\) | \((\neg Q) \Rightarrow (\neg P)\) |
| \(((\neg Q) \Rightarrow (\neg P)) \equiv (P \Rightarrow Q)\) |
| For all | \(\forall x \in D, P(x)\) |
| There exists | \(\exists x \in D, P(x)\) |
| Negating a quantifier | \((\neg (\forall x \in D, P(x))) \equiv (\exists x \in D, (\neg P(x)))\) |
| \((\neg (\exists x \in D, P(x))) \equiv (\forall x \in D, (\neg P(x)))\) | |
| Counterexample to \(\forall x \in D, P(x)\) | an \(x \in D\) with \(\neg P(x)\) |
Integers
| Integers, rationals, reals | \(\mathbb{Z}\), \(\mathbb{Q}\), \(\mathbb{R}\) |
| Even | \((n \text{ even}) \Leftrightarrow (\exists k \in \mathbb{Z}, n = 2 k)\) |
| Odd | \((n \text{ odd}) \Leftrightarrow (\exists k \in \mathbb{Z}, n = 2 k + 1)\) |
| Parity | \(\forall n \in \mathbb{Z}, (((n \text{ even}) \lor (n \text{ odd})) \land (\neg ((n \text{ even}) \land (n \text{ odd}))))\) |
| Closure | \((a, b \in \mathbb{Z}) \Rightarrow ((a + b \in \mathbb{Z}) \land (a - b \in \mathbb{Z}) \land (a b \in \mathbb{Z}))\) |
| Divides (\(a, b \in \mathbb{Z}\)) | \((a \mid b) \Leftrightarrow (\exists k \in \mathbb{Z}, b = a k)\) |
| Congruence (\(a, b, n \in \mathbb{Z}\), \(n > 0\)) | \((a \equiv b \pmod{n}) \Leftrightarrow (n \mid (a - b))\) |
| Remainder \(r\) of \(a\) by \(n\) (\(a, n \in \mathbb{Z}\), \(n > 0\)) | the unique \(r\) with \(\exists q \in \mathbb{Z}, ((a = q n + r) \land (0 \le r < n))\) |
| Rational | \((x \in \mathbb{Q}) \Leftrightarrow (\exists a, b \in \mathbb{Z}, ((b \ne 0) \land (x = a / b)))\) |
Sets
| Element | \(x \in A\) |
| Empty set, cardinality | \(\emptyset\), \({\mathopen{}\left|A\right|\mathclose{}}\) |
| Subset | \((A \subseteq B) \Leftrightarrow (\forall x, ((x \in A) \Rightarrow (x \in B)))\) |
| Set equality | \((A = B) \Leftrightarrow ((A \subseteq B) \land (B \subseteq A))\) |
| Union | \(A \cup B = {\mathopen{}\left\{x : (x \in A) \lor (x \in B)\right\}\mathclose{}}\) |
| Intersection | \(A \cap B = {\mathopen{}\left\{x : (x \in A) \land (x \in B)\right\}\mathclose{}}\) |
| Difference | \(A - B = {\mathopen{}\left\{x : (x \in A) \land (x \notin B)\right\}\mathclose{}}\) |
| Power set | \({\mathcal{P}\mathopen{}\left(A\right)\mathclose{}} = {\mathopen{}\left\{S : S \subseteq A\right\}\mathclose{}}\) |
| Cartesian product | \(A \times B = {\mathopen{}\left\{(a, b) : (a \in A) \land (b \in B)\right\}\mathclose{}}\) |
Induction
| Sum | \(\sum_{i=1}^{n} a_i = a_1 + a_2 + \cdots + a_n\) |
| Induction (\(b, k, n \in \mathbb{Z}\)) | \((P(b) \land (\forall k \ge b, (P(k) \Rightarrow P(k + 1)))) \Rightarrow (\forall n \ge b, P(n))\) |
| Base case | \(P(b)\) |
| Inductive step | assume \(P(k)\) (the induction hypothesis), show \(P(k + 1)\) |
Strong induction
| Strong induction (\(b, c, k, n \in \mathbb{Z}\)) | \((P(b) \land \cdots \land P(c) \land (\forall k \ge c, ((P(b) \land \cdots \land P(k)) \Rightarrow P(k + 1)))) \Rightarrow (\forall n \ge b, P(n))\) |
Loop invariants
| Loop invariant \(I\), guard \(G\) | \(I\) is true each time \(G\) is tested |
| Initialization | \(I\) holds when \(G\) is first tested |
| Maintenance | \((I \land G)\) before a pass through the body \(\Rightarrow\) \(I\) after it |
| Termination | the loop stops, and \((I \land (\neg G)) \Rightarrow\) the result |
Racket
| Define a function | (define (f x y) body) |
| Conditionals | (if test then-expr else-expr) |
(cond [test1 expr1] [test2 expr2] [else expr3]) |
|
| Lists | '() empty, (list 1 2 3) gives '(1 2 3) |
(cons x lst) puts x in front, (empty? lst) is #t if lst is '() |
|
(first lst), (second lst), (third lst), (rest lst) all but the first |
|
| Arithmetic | (+ a b) (- a b) (* a b) (quotient n d) (remainder n d) |
| Comparison | (= a b) (< a b) (<= a b) (> a b) (>= a b) |
(equal? a b) is #t if a and b are the same value, lists included |
|
| Logic | (and a b) (or a b) (not a) |
Recurrences
| Recurrence relation | each term from earlier terms, starting from initial terms |
| Iteration | substitute repeatedly, write the result after \(j\) steps, choose \(j\) to reach an initial term |
| Geometric sum (\(r \ne 1\)) | \(1 + r + \cdots + r^k = \dfrac{r^{k + 1} - 1}{r - 1}\) |
| Arithmetic sum | \(1 + 2 + \cdots + n = \dfrac{n (n + 1)}{2}\) |
| Logarithms | \(2^{\log_2 n} = n\) |
| \(\log_2 (x y) = \log_2 x + \log_2 y\) | |
| \(\log_2 (x^k) = k \log_2 x\) |
Growth of functions
| Big-O (\(c \in \mathbb{R}\); \(N, n \in \mathbb{Z}\)) | \((f(n) = O(g(n))) \Leftrightarrow (\exists c > 0, \exists N, \forall n \ge N, \mathopen{}\left|f(n)\right|\mathclose{} \le c \mathopen{}\left|g(n)\right|\mathclose{})\) |
| Big-Omega | \((f(n) = \Omega(g(n))) \Leftrightarrow (\exists c > 0, \exists N, \forall n \ge N, \mathopen{}\left|f(n)\right|\mathclose{} \ge c \mathopen{}\left|g(n)\right|\mathclose{})\) |
| Big-Theta | \((f(n) = \Theta(g(n))) \Leftrightarrow ((f(n) = O(g(n))) \land (f(n) = \Omega(g(n))))\) |
| Witnesses | the numbers \(c\) and \(N\) |
Relations and functions
| Relation on \(A\) | \(R \subseteq A \times A\), and \((a \mathrel{R} b) \Leftrightarrow ((a, b) \in R)\) |
| Reflexive | \(\forall a \in A, a \mathrel{R} a\) |
| Symmetric | \(\forall a, b \in A, ((a \mathrel{R} b) \Rightarrow (b \mathrel{R} a))\) |
| Transitive | \(\forall a, b, c \in A, (((a \mathrel{R} b) \land (b \mathrel{R} c)) \Rightarrow (a \mathrel{R} c))\) |
| Antisymmetric | \(\forall a, b \in A, (((a \mathrel{R} b) \land (b \mathrel{R} a)) \Rightarrow (a = b))\) |
| Equivalence relation | reflexive, symmetric and transitive |
| Equivalence class | \([a] = {\mathopen{}\left\{b \in A : b \mathrel{R} a\right\}\mathclose{}}\) |
| Injective \(f : A \to B\) | \(\forall a_1, a_2 \in A, ((f(a_1) = f(a_2)) \Rightarrow (a_1 = a_2))\) |
| Surjective | \(\forall b \in B, \exists a \in A, f(a) = b\) |
| Bijective | injective and surjective |
| Inverse of a bijection | \(f^{-1} : B \to A\) with \((f^{-1}(b) = a) \Leftrightarrow (f(a) = b)\) |
| Floor | \(\mathopen{}\left\lfloor x\right\rfloor\mathclose{} = \max {\mathopen{}\left\{n \in \mathbb{Z}: n \le x\right\}\mathclose{}}\) |
Graphs
| Degree | \(\deg(v)\): edges with endpoint \(v\), a loop counting twice |
| Walk from \(u\) to \(v\) | \(v_0, e_1, v_1, \ldots, e_n, v_n\), \(v_0 = u\), \(v_n = v\), \(e_i\) joins \(v_{i - 1}\) and \(v_i\); length \(n\) |
| Trail, path | a walk with no repeated edge; with no repeated vertex |
| Circuit | a trail of length \(\ge 1\) from a vertex to itself |
| Connected | a walk between every two vertices |
| Euler circuit | a circuit that contains every edge |
| Euler trail | a trail from \(u\) to \(v \ne u\) that contains every edge |
| Hamiltonian cycle | a circuit that visits every vertex once, then returns to its start |
| Bipartite | \(V = V_1 \cup V_2\) with \(V_1 \cap V_2 = \emptyset\), and every edge has one endpoint in \(V_1\) and one in \(V_2\) |
procedure bfs(G, s) procedure dfs(G, v) // start: dfs(G, s)
mark s, and set dist[s] := 0 mark v
Q := a queue containing only s for each vertex u in the list of v, in order
while Q is not empty if u is not marked
v := remove the front of Q dfs(G, u)
for each vertex u in the list of v, in order
if u is not marked
mark u, and set dist[u] := dist[v] + 1
add u to the back of Q
Finite automata
| DFA | \(M = (S, \Sigma, \delta, s_0, F)\): states, alphabet, \(\delta : S \times \Sigma \to S\), initial state, accepting states |
| Transition table | \(\to\) marks the initial state, \(*\) each accepting state |
| Empty string | \(\lambda\) |
| Run on \(w = x_1 \cdots x_n\) | \(r_0, \ldots, r_n\) with \(r_0 = s_0\) and \(r_i = \delta(r_{i - 1}, x_i)\) |
| Accepts \(w\) | \(r_n \in F\) |
| Language | \(L(M) = {\mathopen{}\left\{w : M \text{ accepts } w\right\}\mathclose{}}\) |
Trees
| Tree | a connected graph with no cycles |
| Edges of a tree | a tree with \(n\) vertices has \(n - 1\) edges |
| Binary tree | \(\mathtt{nil}\), or \(\operatorname{node}(x, L, R)\): root label \(x\), subtrees \(L\) and \(R\) |
| In Racket | \(\mathtt{nil}\) is '(), \(\operatorname{node}(x, L, R)\) is (list x L R) |
| Preorder | root, preorder of \(L\), preorder of \(R\) |
| Inorder | inorder of \(L\), root, inorder of \(R\) |
| Postorder | postorder of \(L\), postorder of \(R\), root |
| Level, height | the root is at level 0, a child one below its parent; height is the largest level |
| Leaf | a vertex with no children |
| Leaf of a tree with no root | a vertex of degree 1 |