The Examination Formula Page

definitions
discrete-math
exam
reference

The MATH1061/MATH7861 Examination Formula Page is provided in both exams, which are otherwise closed book with no written materials permitted (see math1061). Knowing what is on it — and what is not — is what decides whether a fact needs memorising.

It has seven blocks.

1. Logical equivalences

Eleven named laws, given any statement variables \(p, q, r\), a tautology \(\mathbf{t}\) and a contradiction \(\mathbf{c}\). Reproduced in full in logical-equivalence-laws.

Commutative · Associative · Distributive · Identity · Negation · Double negative · Idempotent · Universal bound · De Morgan’s · Absorption · Negations of \(\mathbf{t}\) and \(\mathbf{c}\).

2. Valid argument forms

Nine forms. Reproduced in full in valid-argument-forms.

Modus Ponens · Modus Tollens · Generalization (a)(b) · Specialization (a)(b) · Conjunction · Elimination (a)(b) · Transitivity · Proof by division into cases · Contradiction Rule.

3. Set identities

Twelve numbered laws, for all sets \(A, B, C\) that are subsets of a universal set \(U\):

Law
1 Commutative \(A \cup B = B \cup A\) · \(A \cap B = B \cap A\)
2 Associative \((A \cup B) \cup C = A \cup (B \cup C)\) · \((A \cap B) \cap C = A \cap (B \cap C)\)
3 Distributive \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\) · \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)
4 Identity \(A \cup \emptyset = A\) · \(A \cap U = A\)
5 Complement \(A \cup A^c = U\) · \(A \cap A^c = \emptyset\)
6 Double complement \((A^c)^c = A\)
7 Idempotent \(A \cup A = A\) · \(A \cap A = A\)
8 Universal bound \(A \cup U = U\) · \(A \cap \emptyset = \emptyset\)
9 De Morgan’s \((A \cup B)^c = A^c \cap B^c\) · \((A \cap B)^c = A^c \cup B^c\)
10 Absorption \(A \cup (A \cap B) = A\) · \(A \cap (A \cup B) = A\)
11 Complement of \(U\) and \(\emptyset\) \(U^c = \emptyset\) · \(\emptyset^c = U\)
12 Set difference \(A - B = A \cap B^c\)

Reproduced with worked proofs in proving-set-properties.

Note the one-to-one correspondence with the logical equivalences in block 1 — laws 1–11 are those same eleven laws in the same order, plus set difference at 12. The names are not quite identical: negation becomes complement (5), double negative becomes double complement (6), and negations of \(\mathbf{t}\) and \(\mathbf{c}\) becomes complement of \(U\) and \(\emptyset\) (11). That correspondence is not a coincidence: \(\cup\) behaves as \(\lor\), \(\cap\) as \(\land\), and complement as \(\sim\). Law 12 is the one with no counterpart in block 1.

The numbering is not decoration — it is how the course expects you to cite. The worked identity proof in Lecture 18 justifies its lines by the number on this page: by set diff law (12), by de Morgan (9b), dist. law (3b), complement law (5b), identity law (4a) — only the double complement step goes uncited there, by name alone. Naming and numbering the law is where the marks are, and this page is in front of you while you do it.

4. The Quotient-Remainder Theorem

Given any integer \(n\) and any positive integer \(d\), there exist unique integers \(q\) and \(r\) such that \(n = dq + r\) and \(0 \leq r < d\).

See modular-arithmetic. The uniqueness clause and the range \(0 \leq r < d\) are what let you read a remainder off a rearranged expression.

5. Unique Factorisation Theorem

Given any integer \(n > 1\), there exists a positive integer \(k\), distinct prime numbers \(p_1, p_2, \dots, p_k\), and positive integers \(e_1, e_2, \dots, e_k\) such that \[n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}\] and any other expression for \(n\) as a product of prime numbers is identical to this except perhaps for the order in which the factors are written.

See divisibility-and-factorisation. The second half is the “unique” part, and it is the half students leave out when asked to state the theorem.

6. Schröder-Bernstein Theorem

For all sets \(A\) and \(B\), if \(|A| \leq |B|\) and \(|A| \geq |B|\) then \(|A| = |B|\).

See cardinality. In use it means two injections, one each way, in place of one bijection, and the two must point in opposite directions between the same two sets.

7. Binomial Theorem

Given any real numbers \(a\) and \(b\), and any nonnegative integer \(n\), \[(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k\]

Belongs to the counting material (L30–L31). The coefficient \(\binom{n}{k}\) is “\(n\) choose \(k\)”, the number of \(k\)-element subsets of an \(n\)-element set (counting-selections). The theorem, with its proof by counting \(a,b\)-sequences and the method for picking one coefficient out of an expansion, is in binomial-coefficients.

What this means for revision

Blocks 1 and 2 are the bulk of the page and are reproduced in the vault, so for the logic material the assessed skill is recognising and naming which law or form applies — not recalling the list.

Block 3 works the same way: the set identities are given, so the assessed skill is choosing and citing by number, not reciting the twelve laws — see proving-set-properties for both worked methods that use them.

Blocks 4 and 5 are covered by modular-arithmetic and divisibility-and-factorisation. Block 6 is covered by cardinality. Block 7 is covered by binomial-coefficients, and its \(\binom{n}{k}\) by counting-selections.

Nothing else is provided. In particular the whole of set theory apart from block 3 — the definitions of \(\subseteq\), \(\subset\), \(\mathcal{P}(A)\), \(A \times B\), partition, function, image and preimage — is not on the page, and neither is any proof technique, nor anything about sequences, induction and recursion. Nor is anything about relations, groups or fields: the definitions of reflexive, symmetric, transitive and antisymmetric, of an equivalence relation (equivalence-relations) and a partial order (partial-order-relations), the four group properties (groups), the subgroup checks (subgroups-and-cyclic-groups) and the conditions for a field (fields). Nor are the counting rules and selection formulas of counting-principles and counting-selections, Pascal’s formula, inclusion/exclusion (inclusion-exclusion), the pigeonhole principle (pigeonhole-principle) or the Handshake Theorem (graphs). Nor is any of the rest of the graph theory: the definitions of walk, trail, circuit and connected (walks-trails-and-circuits), the Euler circuit and trail theorem (euler-circuits-and-trails), adjacency and incidence matrices (adjacency-matrices, incidence-matrices), or the theorem that a tree with \(n\) vertices has \(n - 1\) edges (trees). All of that has to come from memory.