Midterm 1 note sheet
Logic, integers, sets and induction
This sheet comes printed with Midterm 1. 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)\) |