第 02 篇、關係

# 關係 relation

$A,B$ 各為一集合，$R \subseteq A \times B$ 稱 $R$ 為$A$ 至$B$ 的關係 relation

# 表示法

$X = \{1, 2, 3\},Y = \{ A, B, C, D \},R = \{ (1,D),(2,C),(3,C) \}$

# 運算

# 合成

$R_1 \subseteq A \times B, R_2 \subseteq B \times C$ 合成為$R_2 \circ R_1 \subseteq A \times C$

# 定理 1

$M_{R_2 \circ R_1} = M_{R_1}M_{R_2}$

# 定理 2

$R_1 \subseteq A \times B, R_2 \subseteq B \times C, R_3 \subseteq C \times D$
$\Rightarrow (R_3 \circ R_2) \circ R_1 = R_3 \circ (R_2 \circ R_1)$(關係有結合律)

# 反關係

$R \subseteq A \times B ,R^{-1} \subseteq B \times A$
eg.$R =\{(1,a),(2,a),(2,b),(3,b) \}$
$R^{-1} =\{(a,1),(a,2),(b,2),(b,3) \}$
$M_R = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{bmatrix}, M_{R^{-1}} = \begin{bmatrix} 1 & 1 & 0\\ 0 & 1 & 1 \end{bmatrix}$

# 補關係

$R \subseteq A \times B,\overline{R} \subseteq A \times B$，$a\overline{R}b$

eg.$R = \{ (1,a), (2,a), (2,b), (3,b) \}$
$\rightarrow \overline{R} = \{ (1,b),(3,a) \} = (A \times B) - R$

# 基本關係

# 二元關係 Binary Relation

$R \subseteq A \times A$，稱$R$ 為$A$ 的二元關係 Binary Relation

# 反身性 Reflexive / 非反身性 Irreflexive

# 反身性 <-> 不具反身性

$R$ 具有反身性$\leftrightarrow \forall a \in A, aRa$ 有 (a,a)
反之，則稱為不具反身性 (對角線不全為 1)

eg.$A = \{ 1,2,3 \},R = \{ (1,1),(1,2),(2,3),(2,2),(3,3) \}$
$\rightarrow$ 每一個都和自己有關係，$R$ 就具反身性

# 非反身性 <-> 不具非反身性

$R$ 具有非反身性$\leftrightarrow \forall a \in A, a\overline{R}a$ 無 (a,a)
反之，則稱為不具反身性 (對角線不全為 0)

eg.$A = \{ 1,2,3 \},R = \{ (1,2),(2,3),(1,3) \}$
$\rightarrow$ 每一個都和自己沒關係，$R$ 就具非反身性

# 對稱性 / 非對稱性 / 反對稱性

$R \subseteq A \times A$，並假設$A = \{ 1,2,3 \}$

1. $R$ 具有對稱性 symmetric $\leftrightarrow \forall a,b \in A, aRb \Rightarrow bRa$
   $R = \{(1,1),(1,2),(2,1),(2,3),(3,2)\}.$
2. $R$ 具有非對稱性 asymmetric $\leftrightarrow \forall a,b \in A, aRb \Rightarrow b\overline{R}a$
   $R = \{(1,2),(2,3)\}.$
3. $R$ 具有反對稱性 antisymmetric $\leftrightarrow \forall a,b \in A, aRb \Rightarrow bRa(a=b) , aRb \Rightarrow b\overline{R}a (a \neq b)$
   $R = \{(1,1),(1,2),(2,3)\}.$

# 遞移性 transitive

$R \subseteq A \times A$
$R$ 具有遞移性$\leftrightarrow \forall a,b,c \in A, aRb,bRc \rightarrow aRc$
eg.$A = \{1,2,3 \},R = \{(1,1),(1,2),(2,3),(1,3) \}$

# 定理

$R$ 具有遞移性$\leftrightarrow R^2 \subseteq R$

# 等價關係 → 分堆關係

# 等價關係 equivalence relation (ER)

$R \subseteq A \times A$，若$R$ 具有 反身性 、 對稱性 、 遞移性
稱$R$ 為$A$ 上的一等價關係
eg.$A = \{ 1,2,3,4 \},R = \{ (1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(3,4),(4,3) \}$

# 等價類 equivalence class (EC)

$R \subseteq A \times A$ 為一等價關係，$a \in A$
定義$[a] = \{ x| xRa \}$稱為$a$ 的等價類

eg.$A = \{ 1,2,3,4 \},R = \{ (1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(3,4),(4,3) \}$
$[1] = \{1,2\} = [2]$
$[3] = \{3,4\} = [4]$

# 引理

$R \subseteq A \times A$ 為一等價關係，$a,b \in A,aRb \Leftrightarrow [a] = [b]$

# 分割

令$A_1,A_2,...,A_k \in A$，滿足:

1. $A_1 \cup A_2 \cup A_3 \cup ... \cup A_k = A$
2. $A_i \cap A_j = \phi, \forall i \neq j$

# 定理

$R \subseteq A \times A$ 為一等價關係$\Rightarrow P = \{ [a]| a \in A \}$形成$A$ 的一分割

# 關係 Closure

令$R \subseteq A \times A$

1. $r(R)$ 表示包含$R$ 的最小反身關係，稱為 reflexive closure
2. $s(R)$ 表示包含$R$ 的最小對稱關係，稱為 symmetric closure
3. $t(R)$ 表示包含$R$ 的最小遞移關係，稱為 transitive closure
   ( 解題時，推薦用 畫圖 解法，快又不容易錯