1基本定義 Basic Definitions
關係
Relation
從集合 A 到集合 B 的關係 R 是 A×B (笛卡爾積) 的子集合。
記作：R ⊆ A × B
記作：R ⊆ A × B
範例：
A = {1, 2}, B = {a, b}R = {(1,a), (2,b)} 是一個從 A 到 B 的關係
序對
Ordered Pair
(a, b) 表示有順序的兩個元素配對，(a,b) ≠ (b,a) 除非 a = b
笛卡爾積
Cartesian Product
A × B = {(a,b) | a ∈ A 且 b ∈ B}
若 |A| = m, |B| = n，則 |A × B| = m × n
2關係的性質 Properties of Relations
自反性 Reflexive
∀a ∈ A, (a,a) ∈ R
範例：≤ 是自反的
因為 a ≤ a 恆成立
因為 a ≤ a 恆成立
對稱性 Symmetric
若 (a,b) ∈ R 則 (b,a) ∈ R
範例：= 是對稱的
若 a = b 則 b = a
若 a = b 則 b = a
反對稱性 Antisymmetric
若 (a,b) ∈ R 且 (b,a) ∈ R
則 a = b
則 a = b
範例：≤ 是反對稱的
若 a ≤ b 且 b ≤ a 則 a = b
若 a ≤ b 且 b ≤ a 則 a = b
遞移性 Transitive
若 (a,b) ∈ R 且 (b,c) ∈ R
則 (a,c) ∈ R
則 (a,c) ∈ R
範例：< 是遞移的
若 a < b 且 b < c 則 a < c
若 a < b 且 b < c 則 a < c
非自反性
Irreflexive
∀a ∈ A, (a,a) ∉ R（沒有任何元素與自己有關係）
範例：
< 是非自反的，因為 a < a 永遠不成立
非對稱性
Asymmetric
若 (a,b) ∈ R 則 (b,a) ∉ R
3特殊關係類型 Special Types of Relations
等價關係
Equivalence Relation
同時滿足：自反、對稱、遞移
記憶口訣：RST (Reflexive, Symmetric, Transitive)
常見例子：
• 模 n 同餘關係 (congruence modulo n)• 相等關係 =
• 同班同學關係
偏序關係
Partial Order (Poset)
同時滿足：自反、反對稱、遞移
記憶口訣：RAT (Reflexive, Antisymmetric, Transitive)
常見例子：
• ≤ (小於等於)• ⊆ (子集合關係)
• | (整除關係)
4關係的表示方法 Representations
關係矩陣
Relation Matrix
MR[i,j] = 1 若 (i,j) ∈ R，否則為 0
範例：R = {(1,2), (2,1), (2,2)}
[0 1 0]
[1 1 0]
[0 0 0]
有向圖
Directed Graph (Digraph)
表示：R = {(1,2), (2,1), (2,2)}
5關係的運算 Operations on Relations
逆關係
Inverse Relation
R-1 = {(b,a) | (a,b) ∈ R}
矩陣表示：MR-1 = MRT (轉置)
關係的複合
Composition of Relations
S ∘ R = {(a,c) | ∃b: (a,b) ∈ R 且 (b,c) ∈ S}
矩陣表示：MS∘R = MR ⊙ MS (布林矩陣乘法)
注意：複合的順序很重要！S ∘ R ≠ R ∘ S
關係的冪
Powers of Relations
Rn = R ∘ R ∘ ... ∘ R (n 次)
意義：
R2 表示經過 2 步可達的關係R3 表示經過 3 步可達的關係
6閉包 Closures
自反閉包
Reflexive Closure
r(R) = R ∪ {(a,a) | a ∈ A}
加入所有對角線元素
對稱閉包
Symmetric Closure
s(R) = R ∪ R-1
對每個 (a,b) 加入 (b,a)
傳遞閉包
Transitive Closure
R* = R ∪ R2 ∪ R3 ∪ ...
Warshall 算法：O(n³) 時間複雜度
7等價類與分割 Equivalence Classes & Partitions
等價類
Equivalence Class
[a]R = {b | (a,b) ∈ R}
模 5 同餘類：
[2]5 = {..., -8, -3, 2, 7, 12, ...}
分割
Partition
集合 A 的分割是 A 的子集合的集合，滿足：
1. 所有子集非空
2. 兩兩不相交
3. 聯集為 A
1. 所有子集非空
2. 兩兩不相交
3. 聯集為 A
等價關係 ↔ 分割（一一對應）
8偏序集的特殊元素 Special Elements in Posets
| 名詞 | 英文 | 定義 | 範例 ({2,3,6,12,18}, |) |
|---|---|---|---|
| 極大元素 | Maximal Element | 沒有比它大的元素 | 12, 18 |
| 極小元素 | Minimal Element | 沒有比它小的元素 | 2, 3 |
| 最大元素 | Greatest Element | 比所有元素都大 | 無 |
| 最小元素 | Least Element | 比所有元素都小 | 無 |
| 上界 | Upper Bound | 大於等於集合中所有元素 | {2,3} 的上界：6,12,18 |
| 下界 | Lower Bound | 小於等於集合中所有元素 | {6,12} 的下界：2,3,6 |
| 最小上界 | Least Upper Bound (lub) | 所有上界中最小的 | lub({2,3}) = 6 |
| 最大下界 | Greatest Lower Bound (glb) | 所有下界中最大的 | glb({6,12}) = 6 |
格
Lattice
偏序集中任意兩個元素都有唯一的 lub 和 glb
Hasse 圖
Hasse Diagram
偏序的簡化圖示，省略可推導的邊和自環
整除關係的 Hasse 圖
9重要公式總結 Important Formulas
| 公式 | 說明 |
|---|---|
| 從 A 到 B 的關係總數 | 2|A|×|B| |
| n 元素集合上的關係總數 | 2n² |
| 對稱關係數 | 2n(n+1)/2 |
| 反對稱關係數 | 2n × 3n(n-1)/2 |
| 自反關係數 | 2n²-n |
💡考試解題技巧 Exam Tips
檢查關係性質的順序：
1. 自反：檢查所有 (a,a)
2. 對稱：檢查每個 (a,b) 是否有對應的 (b,a)
3. 反對稱：檢查是否存在 a≠b 使得 (a,b) 和 (b,a) 都在
4. 遞移：檢查所有 (a,b) 和 (b,c) 的組合
1. 自反：檢查所有 (a,a)
2. 對稱：檢查每個 (a,b) 是否有對應的 (b,a)
3. 反對稱：檢查是否存在 a≠b 使得 (a,b) 和 (b,a) 都在
4. 遞移：檢查所有 (a,b) 和 (b,c) 的組合
常見陷阱：
• 對稱 ≠ 反對稱（可以同時成立）
• 空關係是對稱、反對稱、遞移的，但不是自反的
• 恆等關係是等價關係也是偏序關係
• 複合運算不滿足交換律
• 對稱 ≠ 反對稱（可以同時成立）
• 空關係是對稱、反對稱、遞移的，但不是自反的
• 恆等關係是等價關係也是偏序關係
• 複合運算不滿足交換律
快速判斷等價關係：
看是否把集合分成不相交的"群組"
看是否把集合分成不相交的"群組"
快速判斷偏序關係：
看是否有"大小"或"包含"的概念
看是否有"大小"或"包含"的概念