MATH1081 - Final Review Notes (Local)MATH1081 Final 复习笔记（本地版）

Notation: $x\in A$ (belongs to), $A\subseteq B$ (subset), $A\cup B$ (union), $A\cap B$ (intersection), $\varnothing$ (empty set), $|A|$ (cardinality).

Cardinality of consecutive integers: $|\{a,a+1,\dots,b\}| = (b-a)+1$.

Let domain $A$, $|A|=m$; codomain $B$, $|B|=n$.

• All functions $f: A \to B$: $n^m$.
• Injective (one-to-one): Condition m <= n, count $P(n,m)=\dfrac{n!}{(n-m)!}$.
• Surjective (onto): Condition m >= n. If not satisfied, count is 0. If satisfied, use inclusion-exclusion to count.
• Bijective: Condition m = n, count m!.

Core equivalence: $A\to B \equiv \neg A\lor B$. This is the cornerstone of all logical translations.

Negation: $\neg(A\to B) \equiv A \land \neg B$ (arrow becomes AND, negate the consequent).

Definitions: $X = A \cap B$, $Y = A \cup C$, $Z = A \oplus B = (A\cup B)\setminus(A\cap B)$.

Two Core Strategies:

• Verification by Example:
  • When to use: Quickly eliminate wrong options, build intuition.
  • Method: Pick the smallest, simplest sets, e.g. $A=\{1\}, B=\{2\}, C=\{3\}$.
  • Caution: A successful example does not prove it is always true; it may just be a special case.
• Formal Proof / Counterexample Method:
  • When to use: When you need 100% certainty that a proposition is always true or always false.
  • Method: Derive using set definitions and operation rules, or construct a counterexample that disproves it.
  • Tip: If a formal proof gets stuck, the proposition is likely false — immediately switch to constructing a counterexample.

Definition: $\lfloor x \rfloor$ is the greatest integer less than or equal to $x$.

Key Properties:

• $\lfloor x \rfloor \le x < \lfloor x \rfloor + 1$
• $\lfloor x + n \rfloor = \lfloor x \rfloor + n$, where $n \in \mathbb{Z}$
• $\lfloor x \rfloor + \lfloor y \rfloor \le \lfloor x + y \rfloor \le \lfloor x \rfloor + \lfloor y \rfloor + 1$
• $\lfloor x \rfloor \cdot \lfloor y \rfloor \le \lfloor xy \rfloor$ (but not always equal)

Standard Form: $ax \equiv b \pmod{m}$, find integer solutions for $x$.

Existence of Solutions: Let $d = \gcd(a, m)$.

• If $d \mid b$, the equation has $d$ incongruent solutions modulo $m$.
• If $d \nmid b$, the equation has no solution.

Solving Steps:

1. Compute $d = \gcd(a, m)$, check if $d \mid b$.
2. Use Extended Euclidean Algorithm to find $(x', y')$ such that $a'x' + m'y' = d$.
3. Particular solution: $x_0 = x' \cdot \frac{b}{d}$.
4. General solution: $x \equiv x_0 + k \cdot \frac{m}{d} \pmod{m}$, $k = 0, 1, \dots, d-1$.

Definition: A poset $(P, \preceq)$ is a set $P$ equipped with a binary relation satisfying:

• Reflexive: $a \preceq a$
• Antisymmetric: If $a \preceq b$ and $b \preceq a$, then $a = b$
• Transitive: If $a \preceq b$ and $b \preceq c$, then $a \preceq c$

Key Concepts:

• Maximal Element: No $b$ exists such that $a \prec b$
• Minimal Element: No $b$ exists such that $b \prec a$
• Chain: A subset where any two elements are comparable
• Antichain: A subset where no two elements are comparable

Simplified Wordle Rules:

• 5-letter word, 6 guesses allowed
• Green = correct letter in correct position
• Yellow = letter exists but wrong position
• Gray = letter not in word

Permutation & Combination Formulas:

• Permutation with repetition: $n^r$ ($r$ positions, $n$ choices each)
• Permutation without repetition: $P(n,r) = \frac{n!}{(n-r)!}$
• Permutation with identical items: $\frac{n!}{n_1! n_2! \cdots n_k!}$

Bridge Definition: In a connected graph $G$, an edge $e$ is a bridge iff removing $e$ disconnects the graph.

Equivalent Conditions: The following are equivalent:

• $e$ is a bridge
• $e$ is not in any simple cycle
• $e$ is not in any cycle
• Removing $e$ increases the number of connected components

Detection Algorithm (DFS):

• For each edge $(u, v)$, check if there exists a path from $u$ to $v$ not using $(u, v)$
• Use DFS or BFS to verify if endpoints remain connected after removing the edge