🔗 Câu 4 · 2 điểm
Quan hệ Tương đương
Lớp · Tập thương · Phân hoạch
Chìa khóa: gom nhóm các phần tử có chung "đặc điểm". Trình bày đủ 3 bước: kiểm tra tính chất → lớp tương đương → phân hoạch.
Định nghĩa & Tính chất
Quan hệ tương đương
Phải thỏa ĐỒNG THỜI cả 3 tính chất
🔁
Phản xạ
$\forall x \in X: xRx$
↔️
Đối xứng
$xRy \Rightarrow yRx$
➡️
Bắc cầu
$xRy \land yRz \Rightarrow xRz$
Phân biệt: Tương đương vs Thứ tự
| Tính chất | Tương đương | Thứ tự |
|---|---|---|
| Phản xạ | ✅ | ✅ |
| Đối xứng | ✅ | ❌ |
| Phản xứng | ❌ | ✅ |
| Bắc cầu | ✅ | ✅ |
📋 Template trình bày chuẩn — Kiểm tra quan hệ
=== Kiểm tra R là quan hệ tương đương trên X ===
[1] PHẢN XẠ:
Với mọi x ∈ X, xem xR x có đúng không?
→ [Chứng minh ngắn] ✓/✗
[2] ĐỐI XỨNG:
Giả sử xRy. Ta cần chứng minh yRx.
→ [Chứng minh] ✓/✗
[3] BẮC CẦU:
Giả sử xRy và yRz. Ta cần chứng minh xRz.
→ [Chứng minh] ✓/✗
Kết luận: Vì R thỏa cả 3 tính chất, R là quan hệ tương đương trên X. □
Lớp tương đương, Tập thương & Phân hoạch
Lớp tương đương $[x]_R$
Tập tất cả phần tử $y \in X$ sao cho $yRx$.
Ký hiệu: $[x]_R = \{y \in X \mid yRx\}$
Ký hiệu: $[x]_R = \{y \in X \mid yRx\}$
Tập thương $X/R$
Tập hợp tất cả các lớp tương đương phân biệt.
$X/R = \{[x]_R \mid x \in X\}$
$X/R = \{[x]_R \mid x \in X\}$
Phân hoạch
Bộ các tập con rời nhau, hợp lại bằng $X$. Các lớp tương đương luôn tạo thành một phân hoạch của $X$.
⚡ Trick liệt kê lớp tương đương
Bước 1: Xác định đặc điểm chung của quan hệ (cùng số dư, cùng chữ số đầu, cùng giá trị $f(x)$...).
Bước 2: Gom các phần tử có cùng đặc điểm vào một lớp.
Kiểm tra: Tổng số phần tử của tất cả lớp $= |X|$. ✓
Bước 2: Gom các phần tử có cùng đặc điểm vào một lớp.
Kiểm tra: Tổng số phần tử của tất cả lớp $= |X|$. ✓
✏️ Ví dụ mẫu: Quan hệ đồng dư
Đề bài
Cho $X = \{0,1,2,3,4,5,6,7,8\}$ và quan hệ $R$: $aRb \Leftrightarrow a \equiv b \pmod{3}$.
a) Chứng minh $R$ là quan hệ tương đương.
b) Tìm các lớp tương đương, tập thương và viết phân hoạch của $X$.
a) Chứng minh $R$ là quan hệ tương đương.
b) Tìm các lớp tương đương, tập thương và viết phân hoạch của $X$.
a) Chứng minh R là quan hệ tương đương
[1] Phản xạ: $a \equiv a \pmod 3$ vì $a - a = 0 \vdots 3$ ✓Phản xạ
[2] Đối xứng: Nếu $a \equiv b\pmod 3$, tức $3 \mid (a-b)$, thì $3 \mid (b-a)$, nên $b \equiv a \pmod 3$ ✓Đối xứng
[3] Bắc cầu: Nếu $3\mid(a-b)$ và $3\mid(b-c)$ thì $3\mid[(a-b)+(b-c)] = (a-c)$ ✓Bắc cầu
→ R là quan hệ tương đương trên X. □Kết luận
b) Lớp tương đương, tập thương, phân hoạch
Phân loại theo số dư ÷ 3:—
$[0]_R = \{0, 3, 6\}$ (số dư = 0)Lớp 0
$[1]_R = \{1, 4, 7\}$ (số dư = 1)Lớp 1
$[2]_R = \{2, 5, 8\}$ (số dư = 2)Lớp 2
Tập thương: $X/R = \bigl\{[0]_R, [1]_R, [2]_R\bigr\} = \bigl\{\{0,3,6\},\{1,4,7\},\{2,5,8\}\bigr\}$Tập thương
Phân hoạch: $X = \{0,3,6\} \cup \{1,4,7\} \cup \{2,5,8\}$Phân hoạch
Kiểm tra: $3 + 3 + 3 = 9 = |X|$ ✓Validate
✏️ Ví dụ 2: Quan hệ cho bởi bảng
Đề bài (dạng quan hệ cho bởi tập cặp)
Cho $A = \{1,2,3,4,5\}$, $R = \{(a,b) \mid a-b$ chia hết cho $2\}$.
Tìm các lớp tương đương và viết phân hoạch.
Tìm các lớp tương đương và viết phân hoạch.
Bài giải
Quan hệ: $aRb \Leftrightarrow 2 \mid (a-b)$ ⟺ $a,b$ cùng tính chẵn/lẻNhận xét
$[1]_R = \{1, 3, 5\}$ (số lẻ)Lớp chẵn/lẻ
$[2]_R = \{2, 4\}$ (số chẵn)Lớp chẵn
Phân hoạch: $A = \{1,3,5\} \cup \{2,4\}$, kiểm tra: $3+2=5=|A|$ ✓Kết luận