Skip to main content

Final exam note sheet

The whole course: the tables of the three midterm sheets

Published

Last modified: 2026-11-19 12:07:39 (PST)

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

Table 1: Connectives.
\(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
Table 2: Laws.
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)\)
Table 3: Quantifiers.
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

Table 4: 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

Table 5: 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

Table 6: 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

Table 7: 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

Table 8: 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

Table 9: 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

Table 10: 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

Table 11: 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

Table 12: 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

Table 13: 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

Table 14: 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

Table 15: 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
Back to top