第七章關係-大葉大學.ppt

* Discrete Mathematics Chapter 7 Relations (關係) 大葉大學 資訊工程系 黃鈴玲 Ch8-* 7.1 Relations and their properties. ※表示兩集合間元素的關係，最直覺的方式就是使用序對(ordered pair) (有順序的配對)。 由序對構成的集合稱為二元關係(binary relation)。 Example 1. A : the set of students in your school. B : the set of courses. R = { (a, b) : a?A, b?B, 學生a 選修了課程 b } 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 }. Ch8-* 0 1 2 a b A B R R ? A?B = { (0,a) , (0,b) , (1,a) (1,b) , (2,a) , (2,b)} ?R ?R 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. 用圖形來表示關係： Ch8-* 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). Ch8-* 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) } Ch8-* Example 5. 考慮下列定義在Z上的關係. 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 2. 列出在集合{1, 2, 3, 4, 5, 6}上 關係 R={(a,b) | a整除b} 中所有的有序數對。 Ch8-* 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 Ch8-* 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),