Chapter 7 Relations (關係) Discrete Mathematics Chapter 7 Relations (關係) 大葉大學 資訊工程系 黃鈴玲

7.1 Relations and their properties. ※表示兩集合間元素的關係，最直覺的方式就是使用 序對(ordered pair) (有順序的配對)。 由序對構成的集合稱為二元關係(binary relation)。 Def 1 Let A and B be sets. A binary relation from A to B is a subset R of AB = { (a, b) : aA, bB }. Example 1. A : the set of students in your school. B : the set of courses. R = { (a, b) : aA, bB, 學生a 選修了課程 b }

Example 3. Let A={0, 1, 2} and B={a, b}, then R = {(0,a),(0,b),(1,a),(2,b)} is a relation from A to B. 用圖形來表示關係： 1 2 a b A B R R  AB = { (0,a) , (0,b) , (1,a) (1,b) , (2,a) , (2,b)} R

Example: A : 男生, B : 女生, R : 夫妻關系 A : 城市, B : 州或省 R : 屬於 (Example 2) Note. Relations vs. Functions A relation can be used to express a 1-to-many relationship between the elements of the sets A and B. (Function 不可一對多，只可多對一) Def 2. A relation on the set A is a subset of A  A (i.e., a relation from A to A).

Example 4. Let A be the set {1, 2, 3, 4} Example 4. Let A be the set {1, 2, 3, 4}. 則 R = { (a, b)| a divides b }裡面包含哪些序對? Sol : 1 2 3 4 1 2 3 4 R = { (1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4) }

Example 5. 考慮下列定義在Z上的關係. 哪些關係包含了序對 (1,1), (1,2), (2,1), (1,-1), R1 = { (a, b) | a  b } R2 = { (a, b) | a > b } R3 = { (a, b) | a = b or a = -b } R4 = { (a, b) | a = b } R5 = { (a, b) | a = b+1 } R6 = { (a, b) | a + b  3 } 哪些關係包含了序對 (1,1), (1,2), (2,1), (1,-1), 及 (2,2)? Sol :  (1,1) (1,2) (2,1) (1,-1) (2,2) R1 R2 R3 R4 R5 R6 ● ● ● ● ● ●

Exercise 7.1 1. 列出由A={0,1, 2, 3, 4}到 B={0, 1, 2, 3}關係中所有 的有序數對，其中關係 R 定義如下： (a) a = b (b) a + b = 4 (e) gcd(a, b)=1 2. 列出在集合{1, 2, 3, 4, 5, 6}上 關係 R={(a,b) | a整除b} 中所有的有序數對。

※ 關係的性質： Def 3. A relation R on a set A is called reflexive (反身性) if (a,a)R for every aA. Example 7. 考慮下列定義在 {1, 2, 3, 4} 上的關係: R2 = { (1,1), (1,2), (2,1) } R3 = { (1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4) } R4 = { (2,1), (3,1), (3,2), (4,1), (4,2), (4,3) } 哪些關係具備反身性(reflexive)？ Sol : (1, 1), (2, 2), (3, 3), (4, 4)都必須屬於R  R3

Example 8. 下列定義在Z上的關係，哪些具備反身性(reflexive)？ R1 = { (a, b) | a  b } R2 = { (a, b) | a > b } R3 = { (a, b) | a = b or a = -b } R4 = { (a, b) | a = b } R5 = { (a, b) | a = b+1 } R6 = { (a, b) | a + b  3 } Sol : 所有Z中的元素a，(a,a)都要屬於R，R才有反身性 (0,0)R2,  R1, R3 and R4 (0,0)R5, (2,2)R6

Def 4. (1) A relation R on a set A is called symmetric (對稱) if for a, bA, (a, b)R  (b, a)R. (2) A relation R on a set A is called antisymmetric (反對稱) if for a, bA, (a, b)R and (b, a)R  a = b. 即若 a≠b且(a,b)R  (b, a)R

Example 10. 下列關係，哪些有對稱性(symmetric)或反對稱性(antisymmetric)? Sol : 對稱：若有序對(a,b)，就要有序對(b,a) 反對稱：若有序對(a,b)且ab，就不能有(b,a) R2, R3 are symmetric R4 are antisymmetric.

Def 5. A relation R on a set A is called transitive(遞移) if for a, b, c A, (a, b)R and (b, c)R  (a, c)R.

Example 13. 下列關係有哪些具備遞移性(transitive)? Sol : 檢查：若(a, b)R 且(b, c)R ，則 (a, c)也必須R R2 沒有遞移性，因 (2,1)  R2 and (1,2)  R2 but (2,2)  R2. R3 沒有遞移性，因 (2,1)  R3 and (1,4)  R3 but (2,4)  R3. R4 is transitive.

Exercise 7.1 4.對下列定義於所有人形成集合上的關係，判斷 是否具有反身性、對稱性、反對稱性和遞移性。 當 (a,b)R 若且唯若 (a) a 比 b 高 (b) a 與 b 生於同一天 (c) a 與 b 的名字相同 (d) a 與 b 有相同的祖父母

Exercise 7.1 7. 對下列定義於所有整數集合上的關係，判斷是否 具有反身性、對稱性、反對稱性和遞移性。 (a) R={(x, y) | x  y, where x, yZ } (b) R={(x, y) | xy  1, where x, yZ } (c) R={(x, y) | x = y + 1 or x = y - 1, where x, yZ } (d) R={(x, y) | x  y (mod 7) , where x, yZ }

Example 17. Let A = {1, 2, 3} and B = {1, 2, 3, 4}. The relation R1 = {(1,1), (2,2), (3,3)} and R2 = {(1,1), (1,2), (1,3), (1,4)} can be combined to obtain R1 ∪ R2 R1 ∩ R2 = {(1,1)} R1 － R2 = {(2,2), (3,3)} R2 － R1 = {(1,2), (1,3), (1,4)} R1 R2 = {(2,2), (3,3), (1,2), (1,3), (1,4)} 對稱差(symmetric difference), 即 (A  B) – (A  B)

antisymmetric 跟 symmetric可並存 補充 : antisymmetric 跟 symmetric可並存 只要R中沒有(a, b)且a≠b即可 例：令A = {1,2,3}, 給出一個定義在A上的關係R， R需同時具備對稱性、反對稱性，但不具備反身性。 Sol : R = {(1,1), (2,2)}