Ảnh tập hợp, quan hệ tương đương và phủ định logic
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| preimage/ˌpriːˈɪmɪdʒ/ | ảnh ngược |
| equivalence relation/ɪˈkwɪvələns rɪˈleɪʃn/ | mối quan hệ tương đương |
| negation/nɪˈɡeɪʃn/ | The statement that is true exactly when the original is false. |
Two records, one label
- A hash function sends files $a$ and $b$ to the same label $L$. With $A = \{a\}$, $B = \{b\}$: $f(A \cap B) = \varnothing$, but $f(A) \cap f(B) = \{L\}$.
- GRE set and logic questions test images versus preimages 原像, equivalence relations 等价关系 and correct negation 否定.
Images
- $f(A \cup B) = f(A) \cup f(B)$ always. Only $f(A \cap B) \subseteq f(A) \cap f(B)$ is automatic; equality holds when $f$ is injective.
- Example: $f(x) = x^2$, $A = \{-1\}$, $B = \{1\}$.
For every function $f$ and sets $A, B$ in its domain, which always holds?
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Unions are preserved; the others need injectivity.
Preimages behave perfectly
- $f^{-1}(C) = \{x : f(x) \in C\}$ exists even if $f$ has no inverse function.
- Preimages preserve unions, intersections and complements: $f^{-1}(C \cap D) = f^{-1}(C) \cap f^{-1}(D)$.
$f^{-1}(C \cap D) = f^{-1}(C) \cap f^{-1}(D)$ for every function $f$.
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Preimages preserve intersections.
Equivalence relations
- Reflexive, symmetric, transitive — all three. The classes partition the set.
- "Same remainder mod 4" on $\mathbb Z$: four classes. $|x - y| \le 1$: reflexive and symmetric, but $0 \sim 1$, $1 \sim 2$, $0 \not\sim 2$ — not transitive.
- $x \sim y \iff x = \pm y$ on $\mathbb R$: classes $\{x, -x\}$, with $\{0\}$ alone.
Equivalence relation?
Check reflexive, symmetric and transitive together.
How many equivalence classes does “same remainder mod 6” have on $\mathbb Z$?
Độ khó 2/5 · 140 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Two integers are related when they leave the same remainder on division by 6. The possible remainders 0, 1, …, 5 give exactly 6 classes.
On $\mathbb Z$, the relation “$x - y$ is odd” is
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
It fails reflexivity because x − x = 0 is even. It is symmetric (x − y odd ⇒ y − x odd) but not transitive: 1 − 2 and 2 − 3 are odd, yet 1 − 3 is even.
Negation
- $P \Rightarrow Q$ is false only when $P$ is true and $Q$ false. So $\neg(P \Rightarrow (Q \wedge R)) \equiv P \wedge (\neg Q \vee \neg R)$.
- $\neg(\forall x\, \exists y\; S) \equiv \exists x\, \forall y\; \neg S$: flip each quantifier, keep the order.
"Every stored file has a hash" is false means some stored file has no hash — not that no file has one.
The negation of “for every $\varepsilon > 0$ there is $N$ with $|a_n| < \varepsilon$ for all $n > N$” is
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Flip each quantifier in order, negate the inner inequality.
$P \Rightarrow Q$ is false only when $P$ is true and $Q$ is ____.
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Truth table of implication.
Recap
- Images keep unions; intersections only as $\subseteq$ unless $f$ is injective.
- Preimages keep unions, intersections and complements.
- Equivalence needs all three properties; negate quantifiers one by one in order.
- negation: The statement that is true exactly when the original is false.