第6節(jié)關系概念、性質(zhì)及運算

1、集合與圖論1第第6節(jié)節(jié) 關系的概念、性質(zhì)及合成關系的概念、性質(zhì)及合成主要內(nèi)容：主要內(nèi)容： 關系的概念關系的概念 關系的性質(zhì)關系的性質(zhì) 關系的合成關系的合成集合與圖論2 定義定義1 設設A,B是兩個集合。是兩個集合。A B的任一子集的任一子集R稱為從稱為從A到到B的一個的一個二元關系二元關系。如果如果A=B，則稱，則稱R為為A上的一個二元關系。上的一個二元關系。1 關系的概念關系的概念 如果如果(a, b) R，則稱，則稱a與與b符合關系符合關系R，并記為，并記為aRb; 如果如果(a, b) R，則稱，則稱a與與b不符合關系不符合關系R，并記為，并記為aRb。集合與圖論3 定義定義2 設設R

2、A B，集合，集合 x x A且且 y B使得使得(x, y) R稱為稱為R的的定義域定義域，并記為，并記為dom(R)。例如：例如：設設A=1,2,3,4，B=a,b,c,d,e，(1,a),(2,b),(2,c),(3,c)是一個二元關系。是一個二元關系。1,2,3是定義域，是定義域，a,b,c是值域是值域一般情況下：一般情況下：A dom(R); B ran(R)。 集合集合 y y B且且 x A使得使得(x, y) R稱為稱為R的的值域值域，并記為，并記為ran(R)。dom(R) A; ran(R) B。定義域與值域定義域與值域集合與圖論4例如例如: A=1,2，B=a,b,c。映

3、射是特殊的二元關系。映射是特殊的二元關系。令令f:AB，f(1)=a，f(2)=b，則則映射映射f就對應著就對應著A B的子集的子集(1,a)，(2,b)關系與映射關系與映射問題問題1：映射與二元關系有什么聯(lián)系？映射與二元關系有什么聯(lián)系？ （前提：映射和二元關系都是從前提：映射和二元關系都是從A到到B的的）集合與圖論5 定義定義1 設設A,B是兩個集合，一個從是兩個集合，一個從A B到到是是,否否的映射的映射R，稱為從，稱為從A到到B的一個的一個二元關系二元關系，或，或A與與B間間的一個二元關系。的一個二元關系。 (a, b) A B，如果，如果(a, b)在在R下的象為下的象為“是是”，則則

4、a與與b符合關系符合關系R，記為，記為aRb；若若A=B，則稱，則稱R為為A上的二元關系。上的二元關系。 如果如果(a, b)在在R下的象為下的象為“否否”，則說，則說a與與b沒有或沒有或不符合關系不符合關系R，并記為，并記為aRb。關系與映射關系與映射集合與圖論6 定義定義1 一個從一個從A到到B的多值部分映射的多值部分映射R稱為從稱為從A到到B的一個的一個二元關系二元關系。關系與映射關系與映射 設設A,B是兩個集合，一個從是兩個集合，一個從A到到2B 的映射的映射R稱為稱為從從A到到B的一個的一個多值部分映射多值部分映射。 如果如果a A，R(a)= ，則稱，則稱R在在a無定義；無定義；

5、而如果而如果R(a) ，則，則 b R(a)，b稱稱 a在在R下的一下的一個象或值個象或值 。集合與圖論7例如：例如：設設A=1,2，B=a,b,c，A B=(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)。A B有有6個元素，個元素，從而有從而有26個子集，個子集，因此從因此從A到到B就有就有26個關系。個關系。答案：答案：2mn問題問題2：A到到B的關系的個數(shù)的關系的個數(shù)設設|A|=m，|B|=n，則，則A到到B上有多少個二元關系？上有多少個二元關系？關系的個數(shù)關系的個數(shù)集合與圖論8 集合集合(a, a) a A稱為稱為A上的上的恒等關系恒等關系或相等關或相等關系，并

6、記為系，并記為IA。 空集空集也是也是A B的一個子集。的一個子集。 空集空集叫做叫做A到到B的的空關系空關系。 A B是是A B的一個子集，按定義的一個子集，按定義A B也是從也是從A到到B的一個二元關系。的一個二元關系。 A B叫做叫做A到到B的的全關系全關系。四個特殊二元關系四個特殊二元關系 設設R是是A到到B的二元關系，集合的二元關系，集合 (y, x) (x, y) R稱為稱為R的的逆關系，簡稱逆關系，簡稱R的的逆，逆，記為記為R-1。 顯然：顯然：R-1是是B到到A的二元關系。的二元關系。集合與圖論9例例1：整除關系整除關系例例2：整數(shù)集整數(shù)集Z上的模上的模n同余關系同余關系 設設

7、Z為整數(shù)集，為整數(shù)集，Z上的整除關系記為上的整除關系記為 。 m, n Z, mn 當且僅當當且僅當 m能除盡能除盡n。 設設n為任一給定的自然數(shù)。對任意兩個整數(shù)為任一給定的自然數(shù)。對任意兩個整數(shù)m, k，如果如果m和和k被被n除，所得余數(shù)相等，則稱除，所得余數(shù)相等，則稱m與與k為為模模n同同余余，并記為：，并記為：m k (mod n)當當n=3時，時，2 5(mod 3)，5 7(mod 3)。關系實例關系實例例例3：設設X是一個集合，集合的包含于是一個集合，集合的包含于“ ”是是2X上的上的二元關系。二元關系。集合與圖論10 定義定義3 設設A1,A2,.,An是是n個集合，一個個集合，

8、一個A1 A2 . An的子集的子集R稱為稱為A1,A2,.,An間的間的n元關系元關系。 每個每個Ai稱為稱為R的一個的一個域域。例例4： 設設 1、A為某單位職工為某單位職工“姓名姓名”的集合；的集合； 2、B為為“性別性別”之集合，之集合，B=男，女男，女； 3、C為職工年齡集合為職工年齡集合 C=1,2,.,100; 4、D表示表示“文化程度文化程度”； D=小學小學,初中初中,高中高中,大學大學,碩士碩士,博士博士； 5、E是是“婚否婚否”集合，集合，E=是，否是，否； 6、F表示月工資，表示月工資，F(xiàn)=0,20000。二元關系到二元關系到n元關系的推廣元關系的推廣集合與圖論11姓名

9、姓名A性別性別B年齡年齡C文化程度文化程度D婚否婚否E工資工資F張三張三男男28大學大學是是400李四李四男男50碩士碩士是是1400李曉芬李曉芬女女18高中高中否否300 這其實就是關系型數(shù)據(jù)庫的一個數(shù)據(jù)表。這其實就是關系型數(shù)據(jù)庫的一個數(shù)據(jù)表。 n元關系是關系數(shù)據(jù)模型的核心，而關系數(shù)據(jù)模型元關系是關系數(shù)據(jù)模型的核心，而關系數(shù)據(jù)模型是關系型數(shù)據(jù)庫的基礎。是關系型數(shù)據(jù)庫的基礎。二元關系到二元關系到n元關系的推廣元關系的推廣集合與圖論122 關系的性質(zhì)關系的性質(zhì) 定義定義1 X上的二元關系上的二元關系R稱為稱為自反的自反的，如果，如果 x X, xRx。 在這個定義中，要求在這個定義中，要求X的每

10、個元素的每個元素x，都有，都有xRx，即即(x, x) R。設設IX是是X上的恒等關系，即：上的恒等關系，即：IX=(x, x) x X。顯然：顯然：R是自反的，當且僅當是自反的，當且僅當IX R。集合與圖論13 例例1：IX是是X上的自反關系，但上的自反關系，但IX的任一真子集的任一真子集R IX不是不是X上的自反關系。上的自反關系。 例例2：實數(shù)集上的實數(shù)集上的“小于或等于小于或等于”關系關系“”是不是不是自反的？小于關系是自反的？小于關系“是反自反的。是反自反的。注意：注意： 反自反的二元關系必不是自反的；反自反的二元關系必不是自反的； 但不是自反的二元關系，卻不一定是反自反。但不是自反

11、的二元關系，卻不一定是反自反。例例5：令令X=a,b,c，R=(a,b),(a,a),(b,c),(c,c)。 關系的性質(zhì)：反自反關系的性質(zhì)：反自反R不是自反的，但它也不是反自反的。不是自反的，但它也不是反自反的。顯然：顯然：R是反自反的，當且僅當是反自反的，當且僅當RIX= 。集合與圖論15 定義定義3 設設R為為X上的二元關系。如果上的二元關系。如果 x, y X, 只要只要xRy就有就有yRx，則稱，則稱R是是對稱的對稱的。例例6： 定義在人的集合定義在人的集合X上的上的“同學同學”、“戰(zhàn)友戰(zhàn)友”、“兄弟兄弟”關系是對稱關系。關系是對稱關系。例例7：令令f: AB, Ker(f)=(x,

12、y)x,y A且且f(x)=f(y), Ker(f)稱為稱為f的的核核。自反自反對稱對稱關系的性質(zhì)：對稱關系的性質(zhì)：對稱顯然：顯然：R是對稱的，當且僅當是對稱的，當且僅當R= R-1。集合與圖論16 定義定義4 設設R為為X上的二元關系。對上的二元關系。對X的任意元素的任意元素x,y,如果如果xRy且且yRx，則，則x=y，那么就稱，那么就稱R為為反對稱的反對稱的。例例8：集合間的包含關系集合間的包含關系 是不是反對稱關系？是不是反對稱關系？ 例例9：實數(shù)集上的實數(shù)集上的“小于或等于小于或等于”關系關系是不是反對是不是反對稱的？稱的？例例10：恒等關系恒等關系Ix。關系的性質(zhì)：反對稱關系的性質(zhì)

13、：反對稱顯然：顯然：R是反對稱的，當且僅當是反對稱的，當且僅當RR-1 IX。集合與圖論17 定義定義8：設設R為為X上的二元關系。如果對上的二元關系。如果對X上的任意上的任意x,y,z，只要，只要xRy且且yRz，就有，就有xRz，則稱，則稱R為為傳遞關系傳遞關系。例例11： Z上的模上的模n同余關系是不是傳遞關系？同余關系是不是傳遞關系？例例12： R上的上的“小于或等于小于或等于”關系關系？ Z上的整除關系是不是傳遞關系？上的整除關系是不是傳遞關系？關系的性質(zhì)：傳遞關系的性質(zhì)：傳遞顯然：顯然：R是傳遞的，當且僅當是傳遞的，當且僅當 ？。集合與圖論18例例13：設設R為為X上的二元關系。上

14、的二元關系。如果如果R且且R是反自是反自反和對稱的，則反和對稱的，則R不是傳遞的。不是傳遞的。例例14：設設R為為X上的二元關系。上的二元關系。R是對稱的且反對稱是對稱的且反對稱的當且僅當?shù)漠斍覂H當R IX。關系的性質(zhì)關系的性質(zhì)例例15：設設R,S是集合是集合X上的兩個傳遞關系，問上的兩個傳遞關系，問RS是否是傳遞關系呢？是否是傳遞關系呢？集合與圖論19運算與性質(zhì)的關系運算與性質(zhì)的關系集合與圖論20 定義定義1 設設R是是A到到B的二元關系的二元關系，S是是B到到C的二元的二元關系。關系。R與與S的的合成合成是是A到到C的一個二元關系，記成的一個二元關系，記成R S，并且，并且 R S=(x,

15、z)(x,z) A C且且 y B使得使得xRy且且ySz例例1：設設X=a,b,c,d，R=(a,b),(c,d)，S=(b,c),(d,a)。R S =(a,c), (c,a)S R =(b,d), (d,b)3 關系的合成關系的合成集合與圖論21 定理定理1 設設R1,R2,R3分別是從分別是從A到到B，B到到C，C到到D的的二元關系，則二元關系，則(R1 R2) R3=R1 (R2 R3)。2、合成運算滿足結(jié)合律、合成運算滿足結(jié)合律1、一般來說，合成運算不滿足交換律，即、一般來說，合成運算不滿足交換律，即R S S R。關系合成的性質(zhì)關系合成的性質(zhì) 定理定理2 設設R1是是A到到B的二

16、元關系，的二元關系，R2,R3是從是從B到到C的二元關系，的二元關系，R4是從是從C到到D的二元關系，則的二元關系，則 (1)R1 (R2R3)=(R1 R2)(R1 R3) (2)R1 (R2R3) (R1 R2)(R1 R3) (3)(R2R3) R4=(R2 R4)(R3 R4) (4)(R2R3) R4 (R2 R4)(R3 R4)3、合成運算對并、交運算的分配關系、合成運算對并、交運算的分配關系集合與圖論22 4、一般說來，合成運算對差運算不滿足分配律：、一般說來，合成運算對差運算不滿足分配律：R1 (R2R3) (R1 R2)(R1 R3)(R2R3) R4 (R2 R4)(R3

17、R4)例例2： 設設X=a,b,c，R1=(a,a),(a,b), R2=(a,a),(b,c)，R3=(a,c),(b,b)。R2R3=(a,a),(b,c)(R1 R2)=(a,a),(a,c)R1 (R2R3)=(a,a),(a,c)(R1 R3)=(a,c),(a,b)(R1 R2)(R1 R3)=(a,a) 關系合成的性質(zhì)關系合成的性質(zhì)集合與圖論23 定理定理3 設設R,S是集合是集合X上的兩個二元關系，則上的兩個二元關系，則 (1)(R S)-1=S-1 R-1； (2)R R-1是對稱的。是對稱的。 5、關系的逆的合成、關系的逆的合成關系合成的性質(zhì)關系合成的性質(zhì) 定理定理4 設設

18、R是是X上的二元關系，則上的二元關系，則R是傳遞的當是傳遞的當且僅當：且僅當：R R R。 6、關系、關系R是傳遞關系的充要條件是傳遞關系的充要條件例例3：集合集合X上的上的二元關系二元關系R是對稱且傳遞的，當且是對稱且傳遞的，當且僅當僅當R=R R-1。集合與圖論24關系冪運算的定義及性質(zhì)關系冪運算的定義及性質(zhì) 定義定義2 設設R是是X上的一個二元關系，上的一個二元關系，R的的n次冪次冪記作記作Rn，n為非負整數(shù)。為非負整數(shù)。(1)R0=IX，R1=R，R2=R R;(2)Rn+1=Rn R。 定理定理5 設設R是是X上的一個二元關系，則對任意的非上的一個二元關系，則對任意的非負整數(shù)負整數(shù)m,n有有 (1)Rm Rn=Rm+n, (2)(Rm)n=Rmn。集合與圖論25 定理定理7 設設R是是X