Skip to main content

Midterm 1 note sheet

Logic, integers, sets and induction

Published

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

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

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)\)
Back to top