1、2022-4-41主要內容：主要內容： 關系的概念及表示方法關系的概念及表示方法 關系的性質關系的性質 關系的運算關系的運算: : 關系的復合，求逆關系，關系的閉包。關系的復合，求逆關系，關系的閉包。 三種關系三種關系: : 等價關系，相容關系，等價關系，相容關系， 次序關系。次序關系。 2022-4-42一、序偶與有序一、序偶與有序n n元組元組1.1.定義定義: :由兩個對象由兩個對象x x、y y組成的序列稱為有序二元組成的序列稱為有序二元組，也稱之為序偶，記作組，也稱之為序偶，記作；稱；稱x x、y y分別為分別為序偶序偶的第一，第二元素。的第一，第二元素。 注意，序偶注意，序偶與集合

2、與集合x,yx,y不同：不同：序偶序偶：元素：元素x x和和y y有次序；有次序；集合集合x,yx,y：元素：元素x x和和y y的次序無關緊要。的次序無關緊要。4-1 4-1 序偶與集合的笛卡爾積序偶與集合的笛卡爾積2022-4-432.2.定義：設定義：設，是兩個序偶，是兩個序偶， 如果如果x=ux=u和和y=vy=v則稱則稱和和相等，相等， 記作記作=。3 .定義：有序定義：有序3元組是一個序偶元組是一個序偶,其第一個元其第一個元素也是個序偶。素也是個序偶。 有序有序3元組元組, c可以簡記成可以簡記成， 但但a,不是有序不是有序3元元組。組。 2022-4-444.定義：有序定義：有序

3、n元組是一個序偶元組是一個序偶,其第一個元素其第一個元素本身是個有序本身是個有序n-1元組元組, 記作記作, xn。且可以簡。且可以簡記成記成。5. 定義定義= ( x1= y1) ( x2= y2) ( xn= yn)2022-4-45 例如例如“斗獸棋斗獸棋”的的1616顆棋子，顆棋子， 豹豹貓貓虎虎象象獅獅狗狗鼠鼠虎虎象象獅獅豹豹狼狼鼠鼠貓貓狗狗狼狼設：設：A A=紅紅, ,藍藍 B=B=象象, ,獅獅, ,虎虎, ,豹豹, ,狼狼, ,狗狗, ,貓貓, ,鼠鼠 每個棋子可以看成一個序偶，斗獸棋可記成集合每個棋子可以看成一個序偶，斗獸棋可記成集合A A B B ：, , , , , 20

4、22-4-461.1.定義定義: :設設A A、B B是集合，由是集合，由A A的元素為第一元素，的元素為第一元素，B B的元素為第二元素組成序偶的集合，稱為的元素為第二元素組成序偶的集合，稱為A A和和B B的笛卡爾積，記作的笛卡爾積，記作A AB B，即，即 A A B=|xB=|x AyAy BB 例例1 1 設設A=0,1A=0,1，B=a,bB=a,b，求，求A A B B ， B B A A， A A A A 。 解：解： A A B=,B=, B B A=,A=, A A A=,A=,可見可見 A ABBBBA A所以，集合的笛卡爾積運算不滿足交換律。所以，集合的笛卡爾積運算不滿

5、足交換律。2022-4-47v另外另外 (A(A B)B) C=,c|C=,c| A A B B c c CC A A (B(B C)=a,|aC)=a,|a A A b,c B B C,C, 因因 a,a,不是有序三元組不是有序三元組, , 所以所以(A(A B)B) C C A A (B(B C)C)。故。故 也不滿足結合律。也不滿足結合律。2.2.性質性質 1) 1) 如果如果A A、B B都是有限集，且都是有限集，且|A|=m, |B|=n|A|=m, |B|=n，則，則 |A|A B |=mnB |=mn。 證明：證明：由笛卡爾積的定義及排列組合中的乘法由笛卡爾積的定義及排列組合中的

6、乘法原理，直接推得此定理。原理，直接推得此定理。 2) A2) A = B= B= 2022-4-483) 對對和和滿足分配律。滿足分配律。 設設A,B,CA,B,C是任意集合，則是任意集合，則 A A (BC)= (A(BC)= (A B)(AB)(A C)C)； A A (BC)= (A(BC)= (A B)(AB)(A C)C)； (AB) (AB) C= (AC= (A C)(BC)(B C)C)； (AB) (AB) C= (AC= (A C)(BC)(B C)C)； 證明證明 ：任取任取 A A (BC) (BC) x x A A y y BC BC x x A A (y(y By

7、By C) C) ( ( x x A A y y B)(xB)(x A A y y C)C) A A BB A A C C (A(A B)(AB)(A C) C) 所以所以式成立。（其余可以類似證明）式成立。（其余可以類似證明）2022-4-494) 4) 若若C C, , 則則 A A B B(A(A C C B B C) C) (C(C A A C C B)B)證明：證明：充分性：充分性： 設設A A B B，求證，求證 A A C C B B C C 任取任取 A A C C x x A A y y C C x x B B y y C (C (因因A A B)B) B B C C 所以所

8、以, A, A C C B B C C。 必要性：必要性：若若C C, , 由由A A C C B B C C 求證求證 A A B B 取取C C中元素中元素y, y, 任取任取 x x A A x x A A y y C C A A C C B B C (C (由由A A C C B B C )C ) x x B B y y C C x x B B 所以所以, A, A B B。 所以所以 A A B B(A(A C C B B C)C) 類似可以證明類似可以證明 A A B B (C(C A A C C B)B)。2022-4-4105) 5) 設設A A、B B、C C、D D為非空集

9、合，則為非空集合，則 A A B B C C D DA A CBCB D D證明：首先首先, ,由由A A B B C C D D 證明證明A A CBCB D D 任取任取x x A A，任取，任取y y B B，所以，所以 x x A A y y B B A AB B C CD (D (由由A A B B C C D )D ) x x C C y y D D 所以所以, A, A CBCB D D。 其次其次, , 由由A A C C，B B D D 證明證明A A B B C C D D 任取任取 A AB B x x A A y y B B x x C C y y D (D (由由A

10、A C C，B B D)D) C CD D 所以所以, A, A B B C C D D 證畢。證畢。2022-4-411 6) 6)約定約定 (A(A1 1 A A2 2) ) A An-1n-1) ) A An n)=A)=A1 1 A A2 2 A An n 特別特別 A A A A A = AA = An n v設R是實數集合，則R2表示笛卡爾坐標平面， R3表示三維空間，Rn表示n維空間。 3. 3. 應用應用 1)令A1=x|x是學號 A2=x|x是姓名 A3=男,女 A4=x|x是出生日期 A5=x|x是班級 A6 =x|x是籍貫 則A1A2A3 A4A5 A6中一個元素： 這就

11、是學生檔案數據庫的一條信息，所以學生的檔案就是A1A2A3 A4A5 A6的一個子集。2022-4-4122) 令A=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v, w,x,y,z 是英文字母表 一個英文單詞可以看成有序n元組：如 at=, boy=, data=, computer= 于是可以說： atA2 ,boyA3,dataA4,computerA8, 所以英文詞典中的單詞集合可以看成是 AA2An 的一個子集。 作業 P105 2022-4-4134-2 關系及其表示法n 相關相關 按照某種規則，確認了二個對象或多個按照某種規則，確認了二個對

12、象或多個對象之間有關系，稱這二個對象或多個對象是相對象之間有關系，稱這二個對象或多個對象是相關的。關的。例例1 1： 大寫英文字母與五單位代碼的對應關系R1: 令=A,B,C,D,Z =30,23,16,22,21是五單位代碼集合 =11000, 10011, 01110, 10010, 10001R1=,.,2022-4-414例例2 2：令令=1,2,3,4, A=1,2,3,4, A中元素間的中元素間的關系關系R R2 2 ： R R2 2= ,= , , , , , , , A AA A 關系的定義關系的定義定義定義1 1: : 設設A A、是集合，如果、是集合，如果 A AB B，則

13、稱，則稱R R是一是一個從個從A A到到B B的二元關系。如果的二元關系。如果 R R A AA A，則稱，則稱R R是是A A上上的二元關系。二元關系簡稱為關系的二元關系。二元關系簡稱為關系。定義定義2:2: 任何序偶的集合，都稱之為一個二元關系。任何序偶的集合，都稱之為一個二元關系。如如:R=,:R=,2022-4-4158 R R xRy xRy 也稱之為也稱之為x x與與y y有關系有關系。后綴表示后綴表示中綴表示中綴表示8 R R xRy xRy 也稱之為也稱之為x x與與y y沒有關系。沒有關系。例例3.3. R R是實數集合，是實數集合，R R上的幾個熟知的關系上的幾個熟知的關系

14、x2+y2=4=xyv 從例從例3 3中可以看出關系是中可以看出關系是序偶序偶( (點點) )的集合的集合( (構成線、面構成線、面) )。2022-4-416 關系的定義域與值域關系的定義域與值域定義域定義域(domain)(domain)：設設R R A AB B，由所有，由所有 R R的的第一個元素組成的集合，稱為第一個元素組成的集合，稱為R R的定義域。的定義域。 記作記作dom Rdom R，即，即 dom R=x|dom R=x| y(y( R R) ) 值域值域(range)(range)：設設R R A AB B，由所有，由所有 R R的第二的第二個元素組成的集合，稱為個元素組

15、成的集合，稱為R R的值域。的值域。 記作記作ran Rran R，即，即 ran R=y|ran R=y| x(x( R R) ) 令：令： R1= , ,R1= , , , , , , , , , , dom R1 =1,2,3,4 dom R1 =1,2,3,4 ran R1 =1,2,3,4 ran R1 =1,2,3,42022-4-417 枚舉法：枚舉法： 即將關系中所有序偶一一列舉出，寫在大括號內。即將關系中所有序偶一一列舉出，寫在大括號內。如如R R = , , , = , , , , , , , , , , , 。 謂詞公式法謂詞公式法： 即用謂詞公式表示序偶的第一元素與第二

16、元素間即用謂詞公式表示序偶的第一元素與第二元素間的關系。例如的關系。例如 R=|xyR=|xy 有向圖法有向圖法： R R A AB,B,用兩組小圓圈用兩組小圓圈( (稱為稱為 結點結點) )分別表示分別表示A A和和B B的元素，當的元素，當 R R時，從時，從x x到到y y引一條有向弧引一條有向弧( (邊邊) )。這樣得到的圖形稱為。這樣得到的圖形稱為R R的關系圖。的關系圖。2022-4-418例例 設設A=1,2,3,4,B=a,b,c, RA=1,2,3,4,B=a,b,c, R1 1 A AB,RB,R2 2 A AA A， R R1 1 = ,= , R R2 2 = , =

17、, , ,R2 :3214ABabc1234R1 :R1 R1 、R2R2的關系圖如下：的關系圖如下：2022-4-419 矩陣表示法矩陣表示法： 設設A=aA=a1 1, a, a2 2, , , a, amm ，B=bB=b1 1, b, b2 2, , , b, bn n 是個有限是個有限集，集， R R A AB B，定義，定義R R的的mmn n階矩陣階矩陣 MMR R=(r=(rij ij) )mmn n，其中，其中1 若若R0 若若R(1im,1jn)rij=例：例：R R1 1= , = , R R2 2= ,= , , ,1 0 10 1 01 0 00 0 1431 2 3

18、 4a b c上例中上例中 MR1 =MR2=1 0 0 10 0 1 01 1 0 01 0 0 1441 2 3 41 2 3 42022-4-420 空關系空關系： 因為因為 A AB B，( (或或 A AA)A)，所以，所以也是一個從也是一個從A A到到B(B(或或A A上上) )的關系，稱之為空關系。的關系，稱之為空關系。 即無任何元素的關系，它的關系圖中只有結點即無任何元素的關系，它的關系圖中只有結點, ,無無任何邊；它的矩陣中全是任何邊；它的矩陣中全是0 0。 完全關系完全關系( (全域關系全域關系) ) ： A AB(B(或或A AA)A)本身也是一個從本身也是一個從A A到

19、到B(B(或或A A上上) ) 的關的關系，稱之為完全關系。系，稱之為完全關系。 即含有全部序偶的關系。它的矩陣中全是即含有全部序偶的關系。它的矩陣中全是1 1。2022-4-421 A A上的恒等關系上的恒等關系I IA A： I IA A A AA,A,且且I IA A =|xA =|xA為為A A上的恒等關系。上的恒等關系。A=1,2,3, A=1,2,3, 則則I IA A =, =, A A上的上的、完全關系及、完全關系及I IA A的關系圖及矩陣如下：的關系圖及矩陣如下： 1 1 11 1 11 1 133MAA=1。2。31。2。31。2。3AA IAMIA =1 0 00 1

20、00 0 1330 0 00 0 00 0 033M=2022-4-422v 由于關系就是集合，所以集合的由于關系就是集合，所以集合的、- -、 和和 運算對關系也適用。運算對關系也適用。例如例如 A A是學生集合，是學生集合，R R是是A A上的同鄉關系，上的同鄉關系，S S是是A A上上的同姓關系，則的同姓關系，則 RSRS：或同鄉或同姓關系：或同鄉或同姓關系 RSRS：既同鄉又同姓關系：既同鄉又同姓關系 R-S R-S ：同鄉而不同姓關系：同鄉而不同姓關系 R R S S：同鄉而不同姓：同鄉而不同姓, ,或同姓而不同鄉關系或同姓而不同鄉關系 RR：不是同鄉關系：不是同鄉關系, , 這里這

21、里R=(AR=(AA)-RA)-R作業作業 P109 P109 、c)d)c)d)2022-4-423v本節中所討論的關系都是集合本節中所討論的關系都是集合A A中的關系。中的關系。v關系的性質主要有：自反性、反自反性、對稱性、關系的性質主要有：自反性、反自反性、對稱性、反對稱性和傳遞性。反對稱性和傳遞性。一一. . 自反性自反性定義定義: :設設R R是集合是集合A A中的關系，如果對于任意中的關系，如果對于任意xAxA都都有有R (xRx)R (xRx)，則稱，則稱R R是是A A中自反關系。中自反關系。 即即 R R是是A A中自反的關系中自反的關系x(xx(x A AxRx)xRx)例

22、如：例如：在實數集合中在實數集合中,“,“ ”是自反關系，因是自反關系，因為，對任意實數為，對任意實數x x，有，有x x x. x. 4-3 4-3 關系的性質關系的性質2022-4-424v從關系有向圖看自反性從關系有向圖看自反性: :每個結點都有環。每個結點都有環。v從關系矩陣看自反性：主對角線都為從關系矩陣看自反性：主對角線都為1 1。 令令A=1,2,3A=1,2,3，確定以下八個關系中哪些是自反的？，確定以下八個關系中哪些是自反的？1。2。3R21 。2。3R11。2。3R31 。2。3R41。2。3R51 。2。3R61。2。3R71。2。3R82022-4-425二二. .反自

23、反性反自反性定義：定義：設設R R是集合是集合A A中的關系，如果對于任意的中的關系，如果對于任意的xAxA都有都有 R R ，則稱，則稱R R為為A A中的反自反關系。中的反自反關系。 即即 R R是是A A中反自反的中反自反的x(xx(x A A R)R)v 從關系有向圖看反自反性從關系有向圖看反自反性: :每個結點都無環。每個結點都無環。v 從關系矩陣看反自反性：主對角線都為從關系矩陣看反自反性：主對角線都為0 0。如如 實數的大于關系實數的大于關系，父子關系是反自反的。，父子關系是反自反的。注意：注意：一個不是自反的關系，不一定就是反自反一個不是自反的關系，不一定就是反自反 的，如前邊

24、的，如前邊R R6 6、R R7 7非自反非自反, ,也非反自反。也非反自反。2022-4-426R2、R5、 R8、均是反自反關系。1。2。3R21 。2。3R11。2。3R31 。2。3R41。2。3R51 。2。3R61。2。3R71。2。3R8觀察下圖：觀察下圖：2022-4-427三三. .對稱性對稱性定義定義: :R R是集合是集合A A中關系中關系, ,若對任何若對任何x, x, yA,yA,如果有如果有xRy,xRy,必有必有yRx,yRx,則稱則稱R R為為A A中的對稱關系。中的對稱關系。 R R是是A A上對稱的上對稱的 x x y(xy(x A A y y A A xR

25、y) xRy) yRx)yRx)v從關系有向圖看對稱性從關系有向圖看對稱性: :在兩個不同的結在兩個不同的結點之間，若有邊的話，則有方向相反的點之間，若有邊的話，則有方向相反的兩條邊。兩條邊。v從關系矩陣看對稱性：以主對角線為對從關系矩陣看對稱性：以主對角線為對稱的矩陣。稱的矩陣。例例 鄰居關系和朋友關系是對稱關系。鄰居關系和朋友關系是對稱關系。2022-4-4281。2。3R21 。2。3R11。2。3R31 。2。3R41。2。3R51 。2。3R61。2。3R71。2。3R8R3、R4、 R6 、 R8均是對稱關系。均是對稱關系。2022-4-429四四. .反對稱性反對稱性定義定義:

26、:設設R R為集合為集合A A中關系中關系, ,若對任何若對任何x, x, yA,yA,如果有如果有xRy,xRy,和和yRx,yRx,就有就有x=y,x=y,則稱則稱R R為為A A中反對稱關系中反對稱關系 。R R R是是A A上反對稱的上反對稱的 x x y(xy(x A A y y A A xRyxRy yRx)yRx) x=y)x=y) x x y(xy(x A A y y A A x x y y xRy)xRy)y xy x) (P112) (P112)v 由由R R的關系圖看反對稱性：兩個不同的結點之間的關系圖看反對稱性：兩個不同的結點之間最多有一條邊。最多有一條邊。v 從關系矩

27、陣看反對稱性：以主對角線為對稱的兩從關系矩陣看反對稱性：以主對角線為對稱的兩個元素中最多有一個個元素中最多有一個1 1。v另外對稱與反對稱不是完全對立的，有些關系它另外對稱與反對稱不是完全對立的，有些關系它既是對稱也是反對稱的，如空關系和恒等關系。既是對稱也是反對稱的，如空關系和恒等關系。2022-4-430上面上面R R1 1、R R2 2、R R4 4、R R5 5、R R8 8均是反對稱關系。均是反對稱關系。R R4 4、R R8 8既是對稱也是反對稱的。既是對稱也是反對稱的。1。2。3R21 。2。3R11。2。3R31 。2。3R41。2。3R51 。2。3R61。2。3R71。2。

28、3R82022-4-431五五. . 傳遞性傳遞性定義定義: :R R是是A A中關系，對任何中關系，對任何x,x,y,zA,y,zA,如果有如果有xRy,xRy,和和yRz,yRz,就有就有xRz,xRz,則稱則稱R R為為A A中傳遞關系。中傳遞關系。 即即R R在在A A上傳遞上傳遞x x y y z(xz(x A A y y A A z z A A xRyxRy yRz)yRz)xRz)xRz)例例 實數集中的實數集中的、，集合、，集合 、 是傳遞的。是傳遞的。v 從關系關系圖和關系矩陣中不易看清是否有傳從關系關系圖和關系矩陣中不易看清是否有傳遞性。必須直接根據傳遞的定義來檢查。遞性。

29、必須直接根據傳遞的定義來檢查。v 檢查時要特別注意使得傳遞定義表達式的前件檢查時要特別注意使得傳遞定義表達式的前件為為F F的時候此表達式為的時候此表達式為T T，即是傳遞的。，即是傳遞的。 即若即若RR與與RR有一個是有一個是F F時時( (即定義即定義的前件為假的前件為假) )，R R是傳遞的。是傳遞的。 2022-4-432例如例如 A=1,2,A=1,2,下面下面A A中關系中關系R R是傳遞的。是傳遞的。通過帶量詞的公式在論域展開式說明通過帶量詞的公式在論域展開式說明R R在在A A上傳遞上傳遞1 2x x y y z(xz(x A A y y A A z z A A xRyxRy

30、yRz)yRz)xRz)xRz)x x y y z(xRyz(xRy yRz)yRz)xRz) (xRz) (為了簡單做些刪改為了簡單做些刪改) ) y y z(z(1 1RyRy yRz)yRz)1 1Rz)Rz)y y z(z(2 2RyRy yRz)yRz)2 2Rz) Rz) ( ( z(z(1 1R R1 1 1 1Rz)Rz)1 1Rz)Rz) z(z(1 1R R2 2 2 2Rz)Rz)1 1Rz)Rz) ( ( z(z(2 2R R1 1 1 1Rz)Rz)2 2Rz) Rz) ( ( z(z(2 2R R2 2 2 2Rz)Rz)2 2RzRz) ) ) ( ( (1 1R

31、 R1 1 1 1R R1 1) )1 1R R1 1) ) ( (1 1R R1 1 1 1R R2 2) )1 1R R2 2) ) (1 1R R2 2 2 2R R1 1) )1 1R R1 1) ) ( (1 1R R2 2 2 2R R2 2) )1 1R R2 2) ) ) ( (2 2R R1 1 1 1R R1 1) )2 2R R1 1) ) ( (2 2R R1 1 1 1R R2 2) )2 2R R2 2) ) ( (2 2R R2 2 2 2R R1 1) )2 2R R1 1) ) ) ( (2 2R R2 2 2 2R R2 2) )2 2R R2 2) ) )

32、 ( (F(F F)F)F)F) (F(F T)T)T)T) (T(T F)F)F)F) (T(T F)F)T)T) ) (F (F F)F)F)F) (F(F T)T)F)F) (F(F F)F)F F) ) ) (F(F F)F)F F) ) )T T2022-4-433以上以上R R1 1、R R3 3、R R4 4、R R5 5、R R8 8均是傳遞的關系均是傳遞的關系。1。2。3R21 。2。3R11。2。3R31 。2。3R41。2。3R51 。2。3R61。2。3R71。2。3R82022-4-434本節要求：本節要求： 1.1.準確掌握這五個性質的定義。準確掌握這五個性質的定義

33、。 2.2.熟練掌握五個性質的判斷和證明。熟練掌握五個性質的判斷和證明。R R是是A A中自反的中自反的x(xx(x A AxRx)xRx)R R是是A A中反自反的中反自反的x(xx(x A A R)R)R R是是A A上對稱的上對稱的x x y(xy(x A A y y A A xRy) xRy) yRx)yRx)R R是是A A上反對稱的上反對稱的x x y(xy(x A A y y A A xRyxRy yRx)yRx) x=y)x=y)x x y(xy(x A A y y A A x x y y xRy)xRy)y xy x) )R R在在A A上傳遞上傳遞x x y y z(xz(

34、x A A y y A A z z A A xRyxRy yRz)yRz)xRz)xRz)v注意注意 性質性質表達式的前件為表達式的前件為F F時此表達式為時此表達式為T T，即，即R R是滿足此性質的。是滿足此性質的。 ( (自反和反自反性除外自反和反自反性除外) )2022-4-435自反性自反性反自反性反自反性對稱性對稱性傳遞性傳遞性反對稱性反對稱性每個結點都有環每個結點都有環 主對角線全是主對角線全是1 1每個結點都無環每個結點都無環 主對角線全是主對角線全是0 0不同結點間如果有不同結點間如果有邊邊, ,則有方向相反則有方向相反的兩條邊的兩條邊. .是以對角線為對是以對角線為對稱的矩

35、陣稱的矩陣不同結點間不同結點間, ,最多有最多有一條邊一條邊. .以主對角線為對稱以主對角線為對稱的位置不會同時為的位置不會同時為1 1如果有邊如果有邊, , ,則也有邊則也有邊. . 或前件為假或前件為假 如果如果a aij ij=1,=1,且且a ajk jk=1,=1,則則a aik ik=1=1性質判定性質判定 從關系的有向圖從關系的有向圖 從關系的矩陣從關系的矩陣2022-4-436下面歸納這八個關系的性質：下面歸納這八個關系的性質：Y-Y-有有 N-N-無無1 1。2 2。 。1 1。2 2。 。1 1。2 2。 。1 1。2 2。 。3 33 33 33 3R R2 2R R1

36、1R R3 3R R4 4自反性自反性 反自反性反自反性 對稱性對稱性 反對稱性反對稱性 傳遞性傳遞性 R R1 1 Y N N Y Y Y N N Y Y R R2 2 N Y N Y N N Y N Y N R R3 3 Y N Y N Y Y N Y N Y R R4 4 Y N Y Y Y Y N Y Y Y 2022-4-4371 1。2 2。1 1。2 2。1 1。2 2。1 1。2 2。3 33 33 33 3R R5 5R R6 6R R7 7R R8 8自反性自反性 反自反性反自反性 對稱性對稱性 反對稱性反對稱性 傳遞性傳遞性 R R5 5 N Y N Y YN Y N Y

37、 Y R R6 6 N N Y N NN N Y N N R R7 7 N N N N NN N N N N R R8 8 N Y Y Y YN Y Y Y Y 2022-4-438練習練習1:1:令令I I是整數集合，是整數集合，I I上關系上關系R R定義為：定義為： R=|x-yR=|x-y可被可被3 3整除整除 ， 求證求證R R是自反、對稱和傳遞的。是自反、對稱和傳遞的。證明：證明：自反性：自反性：任取任取xI, xI, 因因 x-x=0, 0 x-x=0, 0可被可被3 3整整除除, ,所以有所以有R, R, 故故R R自反。自反。對稱性：對稱性：任取任取x,yI,x,yI,設設R

38、, R, 由由R R定義得定義得 x-yx-y可被可被3 3整除整除, , 即即x-y=3n(nI)x-y=3n(nI)， y-x=-(x-y)=-3n=3(-n), -nN y-x=-(x-y)=-3n=3(-n), -nN R, R R, R是對稱的。是對稱的。傳遞性傳遞性: :任取任取x,y,zI,x,y,zI,設設xRy, yRz, xRy, yRz, 由由R R定義得定義得 x-y=3m, y-z=3n (m.nI) x-y=3m, y-z=3n (m.nI) x-z= (x-y)+(y-z)=3m+3n=3(m+n), m+nN x-z= (x-y)+(y-z)=3m+3n=3(m

39、+n), m+nN 所以所以xRz, xRz, 所以所以R R傳遞。傳遞。 證畢證畢 2022-4-439練習練習2 2：設設R R是集合是集合A A上的一個自反關系上的一個自反關系, ,求證：求證： R R是對稱和傳遞的，當且僅當是對稱和傳遞的，當且僅當和和 在在R R中中, ,則有則有也在也在R R中。中。證明：證明：必要性必要性 已知已知R R是對稱和傳遞的。是對稱和傳遞的。 設設 R R 又又 R R，( (要證出要證出 R )R ) 因因R R對稱的故對稱的故 R,R,又已知又已知 R R 由傳遞由傳遞 性得性得 R R。所以有如果。所以有如果和和在在R R 中中, ,則有則有也在也

40、在R R中。中。 充分性充分性 已知任意已知任意 a,b,ca,b,c A A，如，如和和在在 R R中中, ,則有則有也在也在R R中。中。2022-4-440先證先證R R對稱對稱 任取任取 a,ba,b A A 設設 R R，( (要證出要證出 R ) R ) 因因R R是自反的是自反的, ,所以所以 R R，由，由 R R且且 R R，根據已知條件得，根據已知條件得 R R ，所以，所以R R是對稱的。是對稱的。再證再證R R傳遞傳遞 任取任取 a,b,ca,b,c A A 設設 R R， R R。 ( (要證出要證出 R )R )由由R R是對稱的是對稱的, ,得得 R R ，由，由

41、 R R且且 R R，根據已知條件得，根據已知條件得 R R ， 所以所以R R是傳遞的。是傳遞的。作業作業 第第113113頁頁 、2022-4-4414-4 4-4 關系的復合關系的復合v下面介紹由兩個關系生成一種新的關系，下面介紹由兩個關系生成一種新的關系，即關系的復合運算。即關系的復合運算。例如例如，有，有3 3個人個人a,b,ca,b,c，A=a,b,cA=a,b,c， R R是是A A上兄妹關系，上兄妹關系， S S是是A A上母子關系，上母子關系，RSRS即即a a是是b b的哥哥的哥哥, b, b是是a a的妹妹的妹妹; ; b b是是c c的母親，的母親，c c是是b b的兒

42、子。的兒子。則則a a和和c c間就是間就是舅舅和外甥舅舅和外甥的關系的關系, ,記作記作 R R S, S, 稱它是稱它是R R和和S S的復合關系。的復合關系。 SRabcRS2022-4-4421.1.定義定義: :設設R R是從是從X X到到Y Y的關系，的關系，S S是從是從Y Y到到Z Z的關系，則的關系，則R R和和S S的復合關系記作的復合關系記作R R S S 。定義為：定義為： R R S =|xS =|x X X z z Z Z y(yy(y Y Y R R S)S) 顯然，顯然， R R S S 是從是從X X到到Z Z的關系。的關系。2.2.復合關系的計算方法復合關系

43、的計算方法(俗稱過河拆橋法俗稱過河拆橋法) A=1,2,3 B=1,2,3.4 C=1,2,3,4,5R AB S BC 枚舉法枚舉法R=, S=,則則 R S =, 2022-4-443 有向圖法有向圖法CASR12312341 12345ABRSC12345123 關系矩陣法關系矩陣法令令A=aA=a1 1, a, a2 2, a, amm B=b B=b1 1, b, b2 2, b, bn n C=c C=c1 1, c, c2 2, c, ct t R R A AB SB S B BC C2022-4-444MR .(aij)MS .(bij).M SR(cij)0 1 0 00 0

44、 1 11 0 0 034。 1 0 0 0 01 0 1 0 00 0 0 1 00 1 0 0 1=45 1 0 1 0 00 1 0 1 1 1 0 0 0 03 5c c11 11=(a=(a11 11bb11 11)(a)(a1212bb2121).(a).(a1n1nbbn1n1) ) = = (a(a1k1kbbk1k1) ) ( (其中其中是邏輯乘是邏輯乘,是邏輯加是邏輯加) )c cij ij=(a=(ai1 i1bb1j 1j)(a)(ai2i2bb2j2j).(a).(aininbbnjnj) ) = = (a(aik ikbbkj kj) (1im, 1jt) (1im

45、, 1jt)k=1nk=1n2022-4-445 謂詞公式法謂詞公式法設設I I是實數集合，是實數集合，R R和和S S都是都是I I上的關系，定義如下：上的關系，定義如下： R=| y=xR=| y=x2 2+3x+3x S=| y=2x+3 S=| y=2x+3xx2+3x2(x2+3x)+3 = 2x2+6x+3RS所以所以 R R S =| y=2xS =| y=2x2 2+6x+3+6x+3三三. .性質性質 關系復合運算不滿足交換律，但是關系復合運算不滿足交換律，但是1.1.滿足結合律滿足結合律: R: R A AB SB S B BC TC T C CD D 則則TS)(RT)S

46、(R2022-4-446b(bBb(bBRR (S (S T) T)b(bBb(bBRR c(cCc(cCSST)T)b b c(bBc(bBRR(cC(cCSST)T)c c b(cCb(cC(bB(bBRRSST)T)c (cCc (cC b(bBb(bBRRS)S)T)T)c (cCc (cC(R(R S) S)T)T)TSR )(所以TS)(RT)S(RABCDRSTR SS TR (S T)(R S) T可以用下圖形象表示:T)S(R證明：任取證明：任取2022-4-4472 2. . R R A AB SB S B BC C T T B BC C )()()()()()(TRSRT

47、SRTRSRTSR證明證明 任取任取R R (ST) (ST) b(bBb(bBRRST)ST)b(bBb(bBRR(ST)ST)b(bBb(bBRRS)S) (bB (bBRRT)T)b(bBb(bBRRS)S) b(bBb(bBRRT)T)R R SR SR T T(R (R S)(R S)(R T) T)所以所以R R (ST)=(R (ST)=(R S) S)(R(R T) T)2022-4-448證明證明 任取任取R R (S (ST)T) b(bBb(bBRRSST)T)b(bBb(bBRR(SST)T)b(bBb(bBRRS)S) (bB (bBRRT)T)b(bBb(bBRRS

48、)S) b(bBb(bBRRT)T)R R S R S R T T(R (R S)S)( (R R T) T)所以所以 R R (S (ST)T) (R(R S) S)(R(R T)T) x(A(x)x(A(x)B(x) B(x) xA(x)xA(x) xB(x)xB(x)2022-4-4493. R是從A到B的關系，則 RR II RAB驗證驗證: : 令A=1,2,3, B=a,b,c,dRIBBAB123abcdabcdAIABRA123123abcd從這兩個圖看出它們的復合都等于R。2022-4-4504. 4. 關系的乘冪關系的乘冪 令令R R是是A A上關系，由于復合運算可結合，所

49、以上關系，由于復合運算可結合，所以關系的復合可以寫成乘冪形式。即關系的復合可以寫成乘冪形式。即.R RRR R ,RR R3222例如例如R R是是A A上關系，如上圖所示上關系，如上圖所示, ,可見可見 R R2 2, ,表明在表明在R R圖上有從圖上有從a a到到c c有兩條邊的路徑有兩條邊的路徑: :abc;abc; R R3 3, ,表明在表明在R R圖上有從圖上有從a a到到d d有三條有三條邊的路徑邊的路徑:abcd:abcd。.如果如果 R Rk k, ,表明在表明在R R圖上有從圖上有從x x到到y y有有k k條邊條邊( (長為長為k)k)的路徑的路徑(x,y(x,y A)A

50、)。 R )(RR RRI RmnnmnmnmA0有有(m,n(m,n為非負整數為非負整數) )adbcR:2022-4-4514-5 4-5 逆關系逆關系一一. .定義定義 R R是從是從A A到到B B的關系，如果將的關系，如果將R R中的所有序偶的中的所有序偶的兩個元素的位置互換，得到一個從兩個元素的位置互換，得到一個從B B到到A A的關系，的關系，稱之為稱之為R R的逆關系，記作的逆關系，記作R RC C，或，或 R R-1-1。 R RC C=|=| RR R RC C R R二二. . 計算方法計算方法 1. R=,1. R=, R RC C =, =,2022-4-4522.

51、R2. RC C的有向圖：是將的有向圖：是將R R的有向圖的所有邊的方向顛的有向圖的所有邊的方向顛倒一下即可。倒一下即可。3. R3. RC C的矩陣的矩陣 M =(M M =(MR R) )T T 即為即為R R矩陣的轉置。如矩陣的轉置。如三三. .性質性質令令R R、S S都是從都是從X X到到Y Y的關系，則的關系，則 1. (R1. (RC C) )C C = R= R 2. (RS) 2. (RS)C C = R = RC CSSC C 。 3. (RS)3. (RS)C C = R = RC CSSC C 。 4. (R4. (RS) S)C C = R = RC CS SC C

52、。 1 0 1 00 0 0 11 0 1 1MR=34 0 0 0 1 0 1 0 1 1MR =c 43 1 0 12022-4-453證明證明1 1：任取：任取 (RS)(RS)C C，則，則 (RS)(RS)C C RS RS RR S S R RC C S SC C R RC CSSC C所以所以 (RS)(RS)C C = R = RC CSSC C ，其它類似可證。，其它類似可證。5. R5. R S S R RC C S SC C 。證明：充分性，已知證明：充分性，已知R RC C S SC C ，則任取，則任取RR R RC C S SC C S RS R S S 必要性，已

53、知必要性，已知R R S S，則任取，則任取RRC C R R S S S SC C R RC C S SC C 2022-4-4546.(R)6.(R)C C=R=RC C證明證明: :任取任取(R)(R)C C RR R R R RC C RRC C (R)(R)C C=R=RC C7.7.令令R R是從是從X X到到Y Y的關系，的關系，S S是是Y Y到到 Z Z的關系，則的關系，則 (R (R S) S)C C= S= SC C R RC C 。 ( (注意注意RRC C S SC C ) )證明證明：任取任取(R (R S) S)C C R R S Sy(yYy(yYRRS)S)

54、y(yYy(yYSSC CRRC C) ) S SC C R RC C 所以所以(R (R S) S)C C= S= SC C R RC C 2022-4-4558. R8. R是是A A上關系，則上關系，則 R R是對稱的，當且僅當是對稱的，當且僅當 R RC C =R =R R R是反對稱的，當且僅當是反對稱的，當且僅當 RRRRC C I IA A。 證明：證明： 充分性，充分性，已知已知 R RC C =R (=R (證出證出R R對稱對稱) ) 任取任取x,yx,y A A 設設 R,R,則則 R RC C, ,而而R RC C =R =R 所以有所以有 R R ，所以，所以R R對

55、稱。對稱。必要性，必要性，已知已知R R 對稱，對稱，( (證出證出R RC C =R)=R)先證先證R RC C R R，任取任取RRC C, ,則則 R,R,因因R R對稱對稱所以有所以有RR，所以，所以R RC C R R。再證再證R R R RC C，任取任取 R, R, 因因R R對稱，所以有對稱，所以有RR，則，則RRC C, , 所以所以R R R RC C。最后得最后得R RC C =R =R 。2022-4-456證明證明 充分性充分性，已知，已知RRRRC C I IA A，( (證出證出R R反對稱反對稱) ) 任取任取x,yx,y A A 設設 R R 且且RR， RR

56、RR RRRRC C， RRRRC C I IA A ( (因因RRRRC C I IA A ) )x=y x=y 所以所以R R反對稱。反對稱。必要性必要性，已知已知R R反對稱，反對稱，( (證出證出RRRRC C I IA A) ) 任取任取 RRRRC C RRRRC C RR R RC C RR R Rx=y (x=y (因因R R反對稱反對稱) ) I IA A 所以所以RRRRC C I IA A 。作業：第作業：第118118頁頁a)b)a)b)、2022-4-4574-6 4-6 關系的閉包運算關系的閉包運算v關系的閉包是通過關系的復合和求逆構成的一關系的閉包是通過關系的復合

57、和求逆構成的一個新的關系。個新的關系。v這里要介紹關系的自反閉包、對稱閉包和傳遞這里要介紹關系的自反閉包、對稱閉包和傳遞閉包。閉包。一一. .例子例子 給定給定 A A中關系中關系R R，如圖所示，如圖所示，求求A A上另一個關系上另一個關系RR，使，使得它是包含得它是包含R R的的“最小的最小的”( (序偶序偶盡量少盡量少) )具有自反具有自反( (對稱、傳遞對稱、傳遞) )性的關系。性的關系。這個這個R R就是就是R R的的自反自反( (對稱、傳遞對稱、傳遞) )閉包。閉包。2。31。2。32。32。32。32022-4-458這三個關系圖分別是這三個關系圖分別是R R的的自反、對稱、傳遞

58、閉包。自反、對稱、傳遞閉包。二二. .定義：定義：給定給定 A A中關系中關系R,R,若若A A上另一個關系上另一個關系R R，滿足：滿足：R R RR； R R是自反的是自反的( (對稱的、傳遞的對稱的、傳遞的) )； R R是是“最小的最小的”，即對于任何，即對于任何A A上自反上自反( (對對稱、傳遞稱、傳遞) )的關系的關系R R, ,如果如果R R R R, ,就有就有R R R R。則稱。則稱R R是是R R的自反的自反( (對稱、傳遞對稱、傳遞) )閉包。記作閉包。記作r(R)r(R)、s(R)s(R)、t(R)(t(R)(r reflexiveeflexive、s symmet

59、ricymmetric、t transitive)ransitive)1231231232022-4-459三三. .計算方法計算方法定理定理1.1.給定給定 A A中關系中關系R,R,則則 r(R)=R r(R)=RI IA A。證明證明：令令R =RR =RI IA A, ,顯然顯然RR是自反的和是自反的和R R R R ，下，下面證明面證明RR是是“最小的最小的”：如果有：如果有A A上自反關系上自反關系RR且且R R R, R,又又I IA A R, R,所以所以 RRI IA A R, R,即即R R R 。所以所以RR就是就是R R的自反閉包。即的自反閉包。即r(R)=Rr(R)=

60、RI IA A 。定理定理2.2.給定給定 A A中關系中關系R,R,則則 s(R)=RR s(R)=RRC C 。證明方法與證明方法與1. 1.類似。類似。定理定理3.3.給定給定 A中關系中關系R,則則 t(R)=RR2R3. 。證明證明：令令R = RRR = RR2 2RR3 3., ., 顯然有顯然有 R R R R ；2022-4-460證證RR是傳遞的：任取是傳遞的：任取x,y,zx,y,z A,A,設有設有 R R R, R, 由由RR定義得必存在整數定義得必存在整數i,ji,j使得使得 R Ri i , , R Rj j , ,根據關系的復合得根據關系的復合得 R Ri+ji