Relation

---

請先讀: 表達人事物之間的關係 (為什麼要學 Binary Relation 與 Graph)

範例/定義/表示法

其實 binary relation 比 graph 涵蓋的範圍更廣一點 -- a 與 b 可以來自不同的集合, 例如:

1. 「就教」: a 同學是否修到 b 老師的課?
2. 「著作」: a 作者是否參與 b 書籍的撰寫?
3. 「上架」: a CD 是否在 b 唱片行的架上可以看到?
4. 「食草」: a 這種動物是否吃 b 這種植物?

一個 binary relation 將兩個集合綁在一起, 左邊集合的稱為 domain 定義域, 右邊的集合稱為 range 值域。 「就教」 例中, domain 可能是 "朝陽科技大學所有同學", range 可能是 "朝陽科技大學所有老師"; 「食草」 例中, domain 可能是 「臺灣的草食動物」, range 可能是 「臺灣的植物」。

之前談過 binary relation 的表示法。 如果用 W 表示 「著作」 關係, 用 ia 表示科幻作家 Issac Asimov, 用 fe 表示他的作品 "Foundation and Empire", 則 "Issac Asimov 參與 Foundation and Empire 的撰寫" 這句話, 有幾個表示法:

1. 簡寫成 "ia W fe"
2. 把 W 寫成一個集合, 把 (ia,fe) 列舉在其中: W = { ... (ia,fe), ... }
3. 把 W 寫成一個矩陣, 左邊列出所有作者 (domain), 上面列出所有作品 (range), 在 ia 那一列, fe 那一行的交叉點填 1
4. 把 W 畫成一個 bipartite directed graph: 所有代表作者的 vertices 列在一側, 所有代表作品的 vertices 列在另一側, 並從 ia 這個 vertex 畫一條 edge 指向 fe。

「Domain 等於 Range」 的一些特殊 Binary Relations

有許多 binary relation 的 domain 與 range 是同一個集合, 像上一篇的那些例子都是。 這種情況下, 最後一個表示法裡面, 每個 vertex 在兩側各畫一次, 有點重複。 可以改成每個 vertex 只畫一遍, 也就變成上一篇的一般 graph (而不再是 bipartite graph)。 這節所談的 R 就是這樣一個從 D 到 D 的 binary relation。

如果 binary relation 具有以下特性: "D 裡面的每個元素 a 都符合 aRa", 則稱 R 是一個 reflexive relation。 以 graph 來說, 就是圖裡面每一個 vertex 都指向自己。 例如 「整除」 與 「溝通」 都是。 (除非...?)

如果 binary relation 具有以下特性: "沒有任何一個元素符合 aRa", 則稱 R 是一個 irreflexive relation。 以 graph 來說, 就是圖裡面沒有任何 vertex 都指向自己 (沒有 loop)。 例如 「先修」 與 「愛戀」 都是。 (除非...?)

如果 binary relation 具有以下特性: "若 aRb 且 bRc 則 aRc", 則稱 R 是一個 transitive relation 遞移關係。 以 graph 來說, 就是: "若 a 指向 b 且 b 指向 c, 則 a 指向 c"。 例如 「尊親」 與 「整除」 都是。

Transitive Closure

看看這個關係: 「祖孫」: "a 是 b 的內/外 祖 父/母嗎?" 這與 「生下」 關係是否看來有一些相關? 沒錯, 將 「生下」 關係計算兩次, 就得到 「祖孫」 關係。 如果用 P 表示 「生下」, 那麼可以用 P² 表示 「祖孫」。 Q: 請用中文描述 P³。 Q: 若用 L 表示 「愛戀」, 請用中文描述 L²。 (嫉妒不是辦法; 把他當做激勵自己上進/練修養的對象吧。) 關係也可以計算乘方, 用數學符號表達, 果然比文字簡潔吧?

明確地說, R² = { (a,c) | 存在 b 使得 aRb 且 bRc } ; 用 graph 來說, 在原圖 R 當中, 如果有一條 edge 從 a 指向 b, 又有一條 edge 從 b 指向 c, 則在新圖當中, 就畫一條 edge 從 a 指向 c, 這個新圖就是 R²。

從一個關係 R 出發, 可以計算 R, R², R³, R⁴, ... 求上述所有關係的聯集, 所得到的新關係叫做 R 的 transitive closure。 用 graph 來說, 凡是從 a 出發可以到達的任何 vertex b, 在新的圖當中都畫一條 edge 從 a 指向 b。 「尊親」 關係就是 「生下」 關係的 transitive closure。 Q: 請用中文描述 「溝通」 關係的 transitive closure。 Q: 請用中文描述 「通訊錄」 關係的 transitive closure。 Q: 請在 N (自然數的集合) 上面定義一個簡單的關係 S, 它的 transitive closure 必須是 「小於」, 而它的 graph 裡面, edges 越少越好。

顯然, 一個 transitive relation 的 transitive closure 就是它自己。 還有, transtive closure 一定是一個 transitive relation。 (所以才取名為 transitive closure 啊!) 請看上面的例子。

---

以下暫不整理。 (不知道何時才會再教到離散數學...)

---

Binary Relations 基本概念

1. 例: 定義一個從 Z 到 Z 的 binary relation | 如下: a | b 表示 "a 這個整數整除 b 這個整數".
2. 例: 定義一個從 M 到 H 的 binary relation F 如下: a F b 表示 "a 這個男子為 b 這個人的父親".
3. 例: 定義一個從 AP 到 OS 的 binary relation R 如下: a R b 表示 "a 這個應用程式可以在 b 這個作業系統上執行".
4. 例: 定義一個從 S 到 S 的 binary relation RA 如下: a RA b 表示 "a 這顆星球繞著 b 這顆星球轉".
5. 例: 定義一個從 A 到 P 的 binary relation E 如下: a E b 表示 "a 這種動物喜歡吃 b 這種植物".
6. 其他例子: <, <=, ..., "a 認識 b", "副程式 a 呼叫副程式 b", "a 是 b 的父親或母親", ...
7. 幾個常見名詞/符號: 以下假設 R 為一個從 A 到 B binary relation, 並以 A = {1,3,5}, B = {0,2,4,6}, "<" = { (1,2), (1,4), (1,6), (3,4), (3,6), (5,6) } 為例.
   

   名詞/符號	set	digraph	範例
   R(x), R-relative set of x	{ y in B | (x,y) in R }	所有「被 x 指到」的 y.	"<"(3) = {4,6}
   R(A1), R-relative set of A1	{ y in B | (x,y) in R for some x in A1 }	所有「被 A1 內任何一個元素指到」的 y.	"<"({1,3}) = {2,4,6}
   restriction of R to A1	R intersect (A1 x A1)	把 A1 以外的 vertices 及其上 edges 都拿掉.	(通常只用於 A = B 的場合)

8. 作業: 將上表加上一行 matrix 表示法的解釋.
9. Q: 令 A = B = { 1, 2, 3, 4, 5, 6 }, R 為 A 上的 "<" 這個 binary relation, x = 3, z = 4, A1 = {2,5}, 試以 set, matrix, digraph, 等三種表示法將上述各名詞表示出來.
10. Q: 從 Z 到 Z 的 binary relation "<", 它的 complement 是? 它的 inverse 是?
11. Q: 若 R 為一個從 A 到 B 的 binary relation, 且 x in A, 試問 R(x) 與 out-degree(x) 有何關係?
12. 提醒: 當書本或考題說 "令 A x B 的一個子集合 R 表示 ... 這樣的一個 relation" 時, 請以集合表示法理解.
13. Q: 若 |A| = m, |B| = n, 則從 A 到 B 可以定義出多少個不同的 binary relations?
14. 我們對什麼樣的 relations 有興趣? 若一個 binary relation R on A 內的所有元素都滿足 ... 特性, 則稱 R 為一個 ... relation.
    
15. Q: 令 A 表 Gimp (一套類似 PhotoShop 的軟體, 喜歡畫圖的讀者一定要試試看!) 程式原始碼當中, 所有副程式所成的集合. 定義 C 為一個從 A 到 A 的 binary relation 如下: x C y 表示 x 的程式碼當中呼叫到 y. 試描述 A 的一個子集合 A1, 可以讓 restriction of C to A 為 reflexive.
16. partial order: reflexive, transitive, antisymmetric 的 binary relation. 例: a 整除 b; A 這個集合包含於 B 這個集合; ...
17. equivalence relation: reflexive, transitive, symmetric 的 binary relation. 例: a is congruent to b mod 7; a 與 b 這兩顆星球繞著同一顆星球轉; ...
18. equivalence relation (「同一國的關係」) 與 partition (「把所有元素分成那幾國」) 其實是同一觀念的不同表示法, 從一個可以產生出另外一個.
19. equivalence class of x 記為 [x], 其實就是先前定義的 R(x), 也就是「和 x 同一國的所有元素所成集合」.
20. Q: 以下各集合各滿足上述那些特性? R1 = {(a,a) | a is in A}, R2 = {(a,b) | a != b}, R3 = {(a,b) | a, b are in A}, R4 = {}

衍生出來的 relations

1. complement of R: (A x A) \ R
2. inverse of R: R^-1 = { (b,a) | (a,b) is in R }
3. reflexisive closure of R: R union { (a,a) | a in A }
4. symmetric closure of R: R union R^-1
5. transitive closure of R: ...
6. 所謂 "R 的 ... closure" 就是在 R 當中加入最少的元素對, 讓新的 relation 滿足 ... 特性.
7. Q: 若一個集合原本就已經是 reflexive, 則它的 reflexive closure 為? 若原本就已經是 symmetric, 則它的 symmetric closure 為?
8. Q: 「a 是 b 的手足」 的 reflexive closure 是? 「a 是 b 的丈夫」 的 symmetric closure 是? (答案在原始檔中)
9. composition of R and S: 若 R 為從 A 到 B 的 relation, S 為從 B 到 C 的 relation, 則定義 R 與 S 的 composition 為 { (a,c) | 存在 b 使得 (a,b) in R 且 (b,c) in S } 並記為 S o R
10. 例:
    1. 「a 這學期修 b 這門課」與「b 這門課在星期 c 這天有課」的 composition 為「a 這學期在星期 c 這天有課」.
    2. 「a 這個出版社曾經出版過 b 這本書」與「b 這本書可以算是 c 這類的書」的 composition 為「a 這個出版社曾經出版過 c 這類的書」.
    3. 「a 是 b 的兒子或女兒」與「b 是 c 的父親或母親」的 composition 為「a 是 c 的兄弟姊妹」
    4. 「a 是 b 的父親或母親」與「b 是 c 的兒子或女兒」的 composition 為「a 是 c 的夫妻或自己」
11. 從最後兩個例子可以看出: S o R 與 R o S 不一定相等. 事實上即使 S o R 存在, R o S 甚至未必存在.
12. 符號: (S o R)(x) = S(R(a)) 與 a 有關係的所有 c 所成集合.
13. 若 binary relation R 以矩陣方式表示為 M_R, S 以矩陣方式表示為 M_S, 則 S o R 如何以矩陣表示? 把一般矩陣乘法的定義當中的數字乘法改成 and, 把數字加法改成 or, 所得結果記為 M_R Q M_S 稱為 M_R 與 M_S 的 boolean product, 這個結果正好就是 S o R 的矩陣表示法. 想法: 只要存在有任何一個 b (多了也沒關係) 使得 a R b 且 b R c, 則稱 a (S o R) c.
14. Q: 給你兩個 relations R 與 S 用 digraphs 表示, 如何求出 S o R 的 digraph 表示法? 提示在本頁 source 某處.
15. transitive closure of R: 若 R 以矩陣表示為 M_R, 則 R 的 transitive closure 以矩陣表示為 M_R Q M_R² Q M_R³ ... (事實上若 A 內的元素個數為 n, 則上面的無窮 boolean product 只要算前面 n 項就夠了.)
16. Warshall's algorithm for computing Transitive Closure:
    

            for k=1,2,3...n
                列出可以到達 k 的 i 有那些 (第 k 列所有 1 出現的地方)
                列出從 k 可以到達的 i 有那些 (第 k 行所有 1 出現的地方)
                將所有的 (i,j) 填 1.
            end
        
    

    到第 k 步為止, 所求得的結果並不是 M^k 也不是 M union M^2 union ... M^k 而是「若只准以 1,2,...k 為中繼站, 有那些地方可以相通?」

函數

1. 何謂函數? 凡是滿足以下特性的 relation 都叫做函數: f 是一個從 A 到 B 的 binary relation, 且 A 的每個元素 a 都滿足 f(a) 恰有一個元素. (注意: 這裡的 f(a) 是 relation 的符號, 也就是 f-relative set of a). 亦即: 若一個 relation 的 domain 當中的每個元素的 out degree 都恰為 1, 則這個 relation 即是一個函數.
2. 約定俗成的偷懶表示法: 若 f 為一個函數, 我們可以將 f(a) = {b} 簡單地寫成 f(a) = b 就好.
3. 函數亦稱為 mapping (映射) 或 transformation (轉換). f(a)=b 當中的 a 稱為 argument (引數), b 稱為 image of a under f (a 在 f 作用下所得到的映象).
4. 從 A 到 B 的 binary relation f, 若它恰好是一個 function, 我們經常用這樣的寫法來表示: f : A --> B
5. one-to-one function: 「不同的 a 必然映射到不同的 b」 這類函數. 又叫做 injective function 或 injection (嵌射, 一山不容二虎). 亦即, 每個 b 的 in-degree 至多是 1.
6. onto function: 「每個 b 都是某個 a 的映象」 這類函數. 又叫做 surjective function 或 surjection (蓋射, 每座山上都有老虎). 亦即, 每個 b 的 in-degree 至少是 1.
7. one-to-one correspondence between A and B: 既是 injective 又是 surjective 的函數. 又叫做 bijective function 或 bijection. 亦即, 每個 b 的 in-degree 恰為 1.
8. 一般的函數 f, 它的 inverse relation f^-1 不一定滿足函數的定義; 但若 f 為 bijective, 則 f^-1 (它的 inverse relation) 不僅是一個 relation, 還會是一個 bijective function. f^-1 稱為 f 的 inverse fucntion (反函數); 我們說 f 是一個 invertible function (因為可以對它求反函數).
9. 因為每個函數也都是一個 relation, 所以像 inverse 與 composition 這樣的觀念都被 "繼承" 下來了. 但要注意 f 的 inverse relation 一定存在; 但 f 的 inverse function 不一定存在.

Order Relations

1. 一個從 A 到 A 的 binary relation R, 若滿足 reflexivity, transitivity, antisymmetry, 則稱為一個 partial order. (A, R) 稱為一個 partially ordered set, 或簡稱為 poset.
2. 若 R 為一個 partial order, 則 R^-1 也是一個 partial order, 稱為 R 的 dual. 例如 "小於等於" 的 dual 是 "大於等於"; "包含於" 的 dual 是 "包含", "a 是 b 的因數" 的 dual 是 "a 是 b 的倍數",...
3. 一個 poset (A, R) 當中的兩個元素 a 與 b, 如果 aRb 或 bRa 成立, 則稱 a 與 b 為 comparable. 若 (A, R) 當中的每一對元素都是 comparable, 則稱 R 為一個 linear order, 稱 A 為一個 linearly ordered set, 又稱為 chain.
4. Q: 請對上述每一名詞舉例.
5. 定理: poset 的 digraph 表示法中, 只會有 loop, 不會有更長的 cycle 出現.
6. Hasse diagram: 簡化的 poset 表示法.
   1. 把所有的 loop 省略不畫 (反正我們知道 poset 一定是 reflexive)
   2. 把所有 "由 transitivity 可以推導出來的關係" 省略不畫. (反正我們知道 poset 一定是 transitive)
   3. 將 diagram 擺設成所有的箭頭都往上指, (由上述定理知道這一定可以辦得到) 並把所有的箭頭省略不畫,
7. 請練習把 poset 的 digraph 表示法與 Hasse diagram 互換.
8. 假設 (A,R) 與 (B,S) 為兩個 posets. 一個從 A 到 B 的函數 f, 如果它是 one-to-one correspondence (bijection) 而且又滿足: a R b <==> f(a) S f(b), 則稱 f 為一個從 (A,R) 到 (B,S) 的 isomorphism (同構).
9. 兩個 posets 之間, 如果可以找到 isomorphism, 則稱這它們為 isomomorphic posets.
10. 例: 令 A = 2^{a,b,c}, R 為 A 上面的 "包含於" 關係; B = {1,2,3,5,6,10,15,30}, S 為 B 上面的 "整除" 關係. 則 (A,R) 與 (B,S) 同構. (事實上它們之間有好幾個 isomorphisms.)
11. isomorphism 的直覺解釋: 換湯不換葯; 換零件的標籤不換相對關係, 換零件的廠牌不換整體結構 (所以叫做同構).
12. 自己與自己之間的 isomorphism 叫做 automorphism.
13. 為何研究 isomorphism? 希望只要研究少數的 posets, 就可以把所有的定理搬到其他同構的 posets 上直接使用, 不必再證明一次.

---

• 本頁最新版網址: https://frdm.cyut.edu.tw/~ckhung/b/dm/relation.php; 您所看到的版本: February 14 2012 02:32:25.
• 作者: 朝陽科技大學 資訊管理系 洪朝貴
• 寶貝你我的地球, 請 減少列印, 多用背面, 丟棄時做垃圾分類。
• 本文件以 Creative Commons Attribution-ShareAlike License 或以 Free Document License 方式公開授權大眾自由複製/修改/散佈。