第6章二元關(guān)系

1、第三篇第三篇 二元關(guān)系二元關(guān)系 關(guān)系理論歷史悠久。它關(guān)系理論歷史悠久。它與集合論、數(shù)理邏輯、與集合論、數(shù)理邏輯、組合學(xué)、圖論和布爾代數(shù)組合學(xué)、圖論和布爾代數(shù)都有密切的聯(lián)系。都有密切的聯(lián)系。 關(guān)系是關(guān)系是日常生活以及數(shù)學(xué)日常生活以及數(shù)學(xué)中的一個(gè)基本概念，中的一個(gè)基本概念，例如：兄弟關(guān)系，師生關(guān)系、位置關(guān)系、大小關(guān)系、例如：兄弟關(guān)系，師生關(guān)系、位置關(guān)系、大小關(guān)系、等于關(guān)系、包含關(guān)系等。等于關(guān)系、包含關(guān)系等。l計(jì)算機(jī)程序的輸入、輸出關(guān)系；計(jì)算機(jī)程序的輸入、輸出關(guān)系；l數(shù)據(jù)庫的數(shù)據(jù)特性關(guān)系；數(shù)據(jù)庫的數(shù)據(jù)特性關(guān)系；l計(jì)算機(jī)語言的字符關(guān)系；計(jì)算機(jī)語言的字符關(guān)系；l數(shù)據(jù)結(jié)構(gòu)、情報(bào)檢索、數(shù)據(jù)庫、算法分析、計(jì)算

2、機(jī)數(shù)據(jù)結(jié)構(gòu)、情報(bào)檢索、數(shù)據(jù)庫、算法分析、計(jì)算機(jī)理論等計(jì)算機(jī)學(xué)科很好的數(shù)學(xué)工具。理論等計(jì)算機(jī)學(xué)科很好的數(shù)學(xué)工具。 第第6 6章章 二元關(guān)系二元關(guān)系關(guān)系的性質(zhì)關(guān)系的性質(zhì)3關(guān)系的閉包運(yùn)算關(guān)系的閉包運(yùn)算4二元關(guān)系二元關(guān)系1關(guān)系的運(yùn)算關(guān)系的運(yùn)算2內(nèi)內(nèi)容容提提要要6.26.2 二元關(guān)系二元關(guān)系6.2.1 6.2.1 序偶與笛卡爾積序偶與笛卡爾積 上上, ,下下；左，右左，右；3434；中國地處亞洲中國地處亞洲；平面上點(diǎn)平面上點(diǎn)的坐標(biāo)（的坐標(biāo)（x,yx,y）等。等。 特征：特征：成對出現(xiàn)、具有一定的順序。成對出現(xiàn)、具有一定的順序。由兩個(gè)元素由兩個(gè)元素x,yx,y按照按照一定的次序一定的次序組成組成的的二元組

3、二元組稱為稱為有有序偶序偶對對( (序偶序偶) )，記作記作 ，其，其中稱中稱x x為為 的第一元素，的第一元素，y y為為 的第二元素。的第二元素。例例6.2.16.2.1用序偶表示下列語句中的次序關(guān)系用序偶表示下列語句中的次序關(guān)系(1)(1)平面上點(diǎn)平面上點(diǎn)A A的橫坐標(biāo)是的橫坐標(biāo)是x x，縱坐標(biāo)是，縱坐標(biāo)是y y，x,yRx,yR；(2)(2)成都是四川的省會(huì)；成都是四川的省會(huì)；(3)(3)英語課本在書桌上；英語課本在書桌上；(4)(4)左，右關(guān)系。左，右關(guān)系。 ，x,yRx,yR； 序偶與集合的關(guān)系序偶與集合的關(guān)系定義定義6.2.26.2.2 給定序偶給定序偶 和和 ， = a=ca=

4、c且且b=db=d。1.1. 序偶可以看作是具有兩個(gè)元素的集合；序偶可以看作是具有兩個(gè)元素的集合；2.2. 但是序偶中的兩個(gè)元素具有但是序偶中的兩個(gè)元素具有確定的次序確定的次序。 即即 ，但是但是a,b=a,b=b,ab,a 。N N重有序組重有序組定義定義6.2.3 6.2.3 由由n n個(gè)元素個(gè)元素a a1 1,a,a2 2,a,a3 3, ,a,an n按照一定次序按照一定次序組成的組成的n n元組稱為元組稱為n n重有序組重有序組( (n-Type)(Vectorn-Type)(Vector) )，記記作：作：a 例例6.2.26.2.2 用用n n重有序組描述下列語句。重有序組描述下

5、列語句。（1 1）中國四川成都電子科技大學(xué)計(jì)算機(jī)學(xué)院；）中國四川成都電子科技大學(xué)計(jì)算機(jī)學(xué)院；（2 2）20062006年年9 9月月1010日日1818點(diǎn)點(diǎn)1616分分2525秒；秒；（3 3）1616減減5 5再加再加3 3除以除以7 7等于等于2 2。定義定義6.2.4 6.2.4 給定給定n n重有序組重有序組a 和和b 。a= a ai i= =b bi i(i(i=1,2,=1,2,n),n) 笛卡爾乘積笛卡爾乘積定義定義6.2.56.2.5 設(shè)設(shè)A A，B B是兩個(gè)集合，稱集合：是兩個(gè)集合，稱集合：A AB B|(x|(xA)(yA)(yB)B)為為集合集合A A與與B B的的笛卡

6、爾積笛卡爾積(DescartesProduct)(DescartesProduct)。注意注意： 集合集合A A與與B B的笛卡兒積的笛卡兒積A AB B仍然是集合；仍然是集合； 集合集合A AB B中的元素是序偶，序偶中的第一元素取中的元素是序偶，序偶中的第一元素取自自A A，第二元素取自，第二元素取自B B。例例6.2.36.2.3設(shè)設(shè)A=aA=a，B=B=b,cb,c ，C=C=，D=1,2D=1,2，請分別寫出，請分別寫出下列笛卡兒積中的元素。下列笛卡兒積中的元素。（1 1）A AB B，B BA A；（；（2 2）A AC C，C CA A；（3 3）A A(B(BD)D)，(A(A

7、B)B)D D。解解 根據(jù)根據(jù)笛卡兒積的定義笛卡兒積的定義，有，有（1 1）A AB=B=,，B BA=A=,；（2 2）A AC=C=，C CA=A=；例例6.2.36.2.3解解( (續(xù)續(xù)) )（3 3）因?yàn)椋┮驗(yàn)锽 BD=,D=,，所以所以A A(B(BD)D)=a,a,a,a,=a,a,a,a,。同理同理，(A(AB)B)D D=,1,2,1,2=,1,2,1,2。注意注意由例由例6.2.3我們可以看出：我們可以看出：（1）笛卡兒積不滿足交換律；）笛卡兒積不滿足交換律；（2）AB=當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A=或者或者B=；（3）笛卡兒積不滿足結(jié)合律；）笛卡兒積不滿足結(jié)合律；（4）對有限集）對有

8、限集A,B，有，有|AB|=|BA|=|A|B|。集合相等集合相等兩個(gè)集合互相包含兩個(gè)集合互相包含等式成立等式成立兩個(gè)集合相等兩個(gè)集合相等定理定理6.2.1設(shè)設(shè)A,B,C是任意三個(gè)集合，則是任意三個(gè)集合，則（1）A(BC)=(AB)(AC)；（2）(BC)A=(BA)(CA)；（3）A(BC)=(AB)(AC)；（4）(BC)A=(BA)(CA)。分析分析 待證等式兩端都是集合待證等式兩端都是集合定理定理6.2.16.2.1證明證明（1 1）對任意）對任意 AA(BC)(BC)，由由笛卡兒積笛卡兒積的定義知，的定義知，xAxA且且yBCyBC；由由并運(yùn)算并運(yùn)算定義知，定義知，yByB或者或者y

9、CyC。于是有于是有xAxA且且yByB或者或者xAxA且且yCyC。從而，從而， AAB B或者或者 AAC C。即即 (A(AB)(AB)(AC)C)，所以，所以，A A(BC)(BC) (A(AB)(AB)(AC)C)。定理定理6.2.16.2.1證明證明( (續(xù)續(xù)) )另一方面，對任意另一方面，對任意 (A(AB)(AB)(AC)C)，由由并運(yùn)算定義并運(yùn)算定義知，知， AAB B或者或者 AAC C。由由笛卡兒積的定義笛卡兒積的定義知，知，xAxA且且yByB或或xAxA且且yCyC。進(jìn)一步有進(jìn)一步有xAxA且且yBCyBC，從而從而 AA(BC)(BC)。所以所以(A(AB)(AB)

10、(AC)C) A A(BC)(BC)。于是，根據(jù)定理于是，根據(jù)定理1.2.21.2.2，有有A A(BC)=(A(BC)=(AB)(AB)(AC)C)。(2)(2)、(3)(3)和和(4)(4)的證明作為練習(xí)，自證。的證明作為練習(xí)，自證。定理定理6.2.26.2.2設(shè)設(shè)A,B,C,DA,B,C,D是任意四個(gè)集合，則是任意四個(gè)集合，則(A(AB)B) (C(CD) D) A A C C，B B D D。證明證明 充分性充分性( () )：對任意對任意 AAB B，有，有xAxA且且yByB。又因?yàn)橛忠驗(yàn)锳 A C C，B B D D，所以有，所以有xCxC且且yDyD，即，即 CCD D，從而，

11、從而(A(AB)B) (C(CD)D)。定理定理6.2.26.2.2證明證明( (續(xù)續(xù)) )必要性必要性( () )：對任意對任意xAxA，yByB，有，有 AAB B。又因?yàn)橛忠驗(yàn)?A(AB)B) (C(CD)D)，所以，所以 CCD D。根據(jù)笛卡兒積的定義有根據(jù)笛卡兒積的定義有xCxC且且yDyD，從而，從而A A C C，B B D D。綜上所述，定理成立。綜上所述，定理成立。推廣推廣定義定義6.2.6 6.2.6 設(shè)設(shè)A A1 1,A,A2 2, ,A,An n是是n n個(gè)集合，稱集合個(gè)集合，稱集合A A1 1A A2 2A An n =a=|(a|(ai iAAi i)i1,2,3,

12、)i1,2,3,n,n為集合為集合A A1 1,A,A2 2, ,A,An n的的笛卡兒積笛卡兒積( (DescartesProductDescartesProduct) )當(dāng)當(dāng)A A1 1=A=A2 2= =A=An n=A=A時(shí)，有時(shí)，有A A1 1A A2 2A An n=A=An n。定理定理6.2.3 6.2.3 當(dāng)集合當(dāng)集合A A1 1,A,A2 2, ,A,An n都是都是有限集有限集時(shí)，時(shí)，|A|A1 1A A2 2A An n|=|A|=|A1 1| |A|A2 2| |A|An n| |。6.2.26.2.2關(guān)系的定義關(guān)系的定義問題：問題：某學(xué)校組織學(xué)生看電影，電影院里共有

13、某學(xué)校組織學(xué)生看電影，電影院里共有n n個(gè)個(gè)座位，看電影的學(xué)生共有座位，看電影的學(xué)生共有m m個(gè)（個(gè)（mnmn），每個(gè)學(xué)生），每個(gè)學(xué)生坐一個(gè)座位。請問，坐一個(gè)座位。請問，怎樣表示學(xué)生和座位之間的從怎樣表示學(xué)生和座位之間的從屬關(guān)系？屬關(guān)系？a1a2a3amABbnb3b2b10假設(shè)假設(shè)A,BA,B分別表示某學(xué)校分別表示某學(xué)校所有所有學(xué)生的集合學(xué)生的集合和電影院和電影院里所有里所有座位的集合座位的集合，即，即A=aA=a1 1,a,a2 2, ,a,am m B=bB=b1 1,b,b2 2, , ,b bn n 定義定義6.2.7 6.2.7 設(shè)設(shè)A,BA,B為兩個(gè)非空集合，稱為兩個(gè)非空集合，稱

14、A AB B的任何的任何子集子集R R為為從從A A到到B B的二元關(guān)系的二元關(guān)系，簡稱關(guān)系，簡稱關(guān)系(Relation)(Relation)。如如A AB B，則稱則稱R R為為A A上的二元關(guān)系上的二元關(guān)系。這里這里，A A稱為稱為R R的的前域前域，B B稱為稱為R R的的后后域。域。令令C Cx|x| RR A A，D Dy|y| RR B B，稱稱C C為為R R的的定義域定義域，記為記為C CdomRdomR；稱稱D D為為R R的的值域值域，記記D DranRranR；并并稱稱fldRfldRDCDC為為R R的的域域。二元關(guān)系二元關(guān)系當(dāng)當(dāng)R=R=時(shí)，稱時(shí)，稱R R為為空關(guān)系空關(guān)

15、系( (emptyrelationemptyrelation) )；當(dāng)當(dāng)R=AR=AB B時(shí)，則稱時(shí)，則稱R R為為全關(guān)系全關(guān)系( (TotalRelationTotalRelation) )。設(shè)一有序?qū)υO(shè)一有序?qū)?：若若 R R，則則記為記為xRyxRy，讀作讀作“x x對對y y有關(guān)系有關(guān)系R”R”；若若 x,y R R，則記為則記為xRyxRy，讀作讀作“x x對對y y沒有關(guān)系沒有關(guān)系R”R”。當(dāng)當(dāng)A=BA=B時(shí)時(shí)，稱稱I IA A=|a aA A 是是A A上的上的恒等關(guān)系恒等關(guān)系。特別特別例例6.2.46.2.4假設(shè)假設(shè)A=A=a,ba,b ，B=B=c,dc,d ，試寫出從，試寫

16、出從A A到到B B的所有不同的所有不同關(guān)系。關(guān)系。解解 因?yàn)橐驗(yàn)锳=A=a,ba,b ，B=B=c,dc,d ，所以，所以A AB=B=,。于是于是A AB B的所有不同子集為：的所有不同子集為：00元子集：元子集：；11元子集：元子集： ,；22元子集：元子集：,，,， , ,，,， , ,，,； 例例6.2.46.2.4解解( (續(xù)續(xù)) )33元子集：元子集： ,，,；44元子集：元子集：,。注意注意當(dāng)集合當(dāng)集合A,BA,B都是有限集時(shí)，都是有限集時(shí)，A AB B共有共有2 2|A|A|B|B|個(gè)不同個(gè)不同的子集，即的子集，即從從A A到到B B的不同關(guān)系共有的不同關(guān)系共有2 2|A|A

17、|B|B|個(gè)。個(gè)。用圖表示關(guān)系用圖表示關(guān)系假設(shè)假設(shè)A=aA=a1 1,a,a2 2,a,a3 3,a,a4 4,a,a5 5,a,a6 6 ，B=bB=b1 1,b,b2 2,b,b3 3,b,b4 4,b,b5 5 ， C=a C=a3 3,a,a4 4,a,a6 6 ，D=bD=b1 1,b,b2 2,b,b4 4,b,b5 5 ， R=a R=,。顯然，顯然，R R C CD D A AB B。a a1 1a a2 2a a5 5a a3 3a a4 4a a6 6b b3 3b b2 2b b4 4b b5 5b b1 1D DC CA AB BR R求定義在求定義在Z Z上關(guān)系的定義

18、域、值域和域。上關(guān)系的定義域、值域和域。 （1 1）R R1 1=|(|(x,yZ)(yx,yZ)(y=x=x2 2)；（2 2）R R2 2=|(|(x,yZ)(|xx,yZ)(|x|=|y|=7)|=|y|=7)。解解（1 1）domRdomR1 1=Z=Z，ranRranR1 1=x=x2 2|xZ|xZ，fldRfldR1 1=Z=Z； （2 2）domRdomR2 2=7,-7=7,-7，ranRranR2 2=7,-7=7,-7，fldRfldR2 2=7,7=7,7。例例6.2.56.2.5推廣推廣定 義定 義 6 . 2 . 86 . 2 . 8 設(shè)設(shè) A A1 1, A, A

19、2 2, , , A, An n為為 n n 個(gè) 非 空 集 合 ， 稱個(gè) 非 空 集 合 ， 稱A A1 1A A2 2A An n的任意子集的任意子集R R為以為以A A1 1A A2 2A An n為基的為基的n n元元關(guān)系關(guān)系(n-Relation)(n-Relation)。6.2.36.2.3關(guān)系的表示法關(guān)系的表示法1. 1. 集合表示法集合表示法（枚舉法和敘述法枚舉法和敘述法）例例6.2.76.2.7（1 1）設(shè)）設(shè)A=aA=a，B=B=b,cb,c ，用枚舉法寫出從，用枚舉法寫出從A A到到B B的不同關(guān)系；的不同關(guān)系；（2 2）用敘述法寫出定義在）用敘述法寫出定義在R R上的上

20、的“相等相等”關(guān)系。關(guān)系。解解（1 1）A A到到B B的不同關(guān)系有：的不同關(guān)系有：R R1 1= =，R R2 2=，R R3 3=，R R4 4=,=,；（2 2）設(shè)）設(shè)R R上的上的“相等相等”關(guān)系為關(guān)系為S S，則，則S=|(x,yR)(x=y)S=|(x,yR)(x=y)。2.2.關(guān)系圖法關(guān)系圖法（1 1）A AB B設(shè)設(shè)A A a a1 1,a,a2 2, ,a,an n ，B Bbb1 1,b,b2 2, , ,b bm m ，R R是是從從A A到到B B的一個(gè)二元關(guān)系，則規(guī)定的一個(gè)二元關(guān)系，則規(guī)定R R的關(guān)系圖如下：的關(guān)系圖如下：. .設(shè)設(shè)a a1 1,a,a2 2, ,a,

21、an n和和b b1 1,b,b2 2, , ,b bm m分別為圖中的結(jié)點(diǎn)，分別為圖中的結(jié)點(diǎn)，用用“”表示表示； . .如如 R R，則從則從a ai i到到b bj j可用有向邊可用有向邊a ai i。b bj j相連。相連。 為對應(yīng)圖中的有向邊。為對應(yīng)圖中的有向邊。 （2)A=B2)A=B設(shè)設(shè)A AB=aB= ，R R是是A A上的關(guān)系，則上的關(guān)系，則R R的關(guān)的關(guān)系圖規(guī)定如下：系圖規(guī)定如下：. .設(shè)設(shè)a a1 1,a,a2 2, ,a,an n為圖中結(jié)點(diǎn)，用為圖中結(jié)點(diǎn)，用“”表表示示. .如如 R R，則從則從a ai i到到a aj j可用有向邊可用有向邊a ai i。b bj j相

22、連。相連。 為對應(yīng)圖中的有向邊為對應(yīng)圖中的有向邊。. .如如 R,R,則從則從a ai i到到a ai i用一帶箭頭的小圓環(huán)用一帶箭頭的小圓環(huán)表示，即：表示，即：a ai i關(guān)系圖法關(guān)系圖法( (續(xù)續(xù)) )例例6.2.86.2.8試用關(guān)系圖表示下面的關(guān)系。試用關(guān)系圖表示下面的關(guān)系。 （1 1）設(shè)）設(shè)A=2,3,4A=2,3,4，B=3,4,5,6B=3,4,5,6，則，則A A到到B B之間的一之間的一種種整除關(guān)系整除關(guān)系R R1 1=,=,2 24 44 43 33 36 65 5A AB BR R1 1關(guān)系圖中的關(guān)系圖中的有向邊與關(guān)有向邊與關(guān)系集合中的系集合中的序偶一樣多序偶一樣多例例6.

23、2.8(6.2.8(續(xù)續(xù)) )（2 2）假設(shè)）假設(shè)A=1,2,3,4A=1,2,3,4，則，則A A上的上的小于等于關(guān)系小于等于關(guān)系R R2 2=,=,。2 23 34 41 1設(shè)設(shè)A Aaa1 1,a,a2 2, ,a,an n ，B Bbb1 1,b,b2 2, , ,b bm m ，R R是從是從A A到到B B的一個(gè)二元關(guān)系，稱矩陣的一個(gè)二元關(guān)系，稱矩陣M MR R（r rijij) )n nm m為關(guān)系為關(guān)系R R的的關(guān)系矩陣關(guān)系矩陣(Relation Matrix)(Relation Matrix)，其中，其中又稱又稱M MR R為為R R的的鄰接矩陣鄰接矩陣(Adjacency

24、Matrix)(Adjacency Matrix)。i ij ji ij ji ij j1 1 R Rr r = =( (i i= =1 1, , 2 2, , . . . ., , n n, , j j= =1 1, , 2 2, , . . . ., ,m m) )0 0 R R3.3.關(guān)系矩陣關(guān)系矩陣1.1. 必須先對集合必須先對集合A,BA,B中的元素排序中的元素排序2.2. A A中元素序號中元素序號對應(yīng)矩陣元素的對應(yīng)矩陣元素的行下標(biāo)行下標(biāo)，3.3. B B中元素序號中元素序號對應(yīng)矩陣元素的對應(yīng)矩陣元素的列下標(biāo)列下標(biāo)；4.4. 關(guān)系矩陣是關(guān)系矩陣是0-10-1矩陣，稱為矩陣，稱為布爾

25、矩陣布爾矩陣。 注注意意例例6.2.96.2.9設(shè)設(shè)A = 1, 2, 3, 4A = 1, 2, 3, 4，考慮，考慮A A上的上的整除關(guān)系整除關(guān)系R R和和等于等于關(guān)系關(guān)系S S。（1 1）試寫出）試寫出R R和和S S中的所有元素；中的所有元素；（2 2）試寫出）試寫出R R和和S S的關(guān)系矩陣。的關(guān)系矩陣。例例6.2.96.2.9解解 （1 1）根據(jù)整除關(guān)系和等于關(guān)系的定義，有）根據(jù)整除關(guān)系和等于關(guān)系的定義，有R=,R=,S=,S=,。（2 2）設(shè)）設(shè)R R和和S S的關(guān)系矩陣分別為的關(guān)系矩陣分別為M MR R和和M MS S，則有，則有 R R1 1 1 11 1 1 10 1 0

26、10 1 0 1M =M =0 0 1 00 0 1 00 0 0 10 0 0 1 S S1 0 0 01 0 0 00 1 0 00 1 0 0M =M =0 0 1 00 0 1 00 0 0 10 0 0 112 3 412 3 41 12 23 34 412 3 412 3 41 12 23 34 4布爾矩陣的運(yùn)算布爾矩陣的運(yùn)算定義定義6.2.96.2.9 如果如果A=(A=(a aijij) )m mn n和和B=(B=(b bijij) )m mn n是布爾矩陣，是布爾矩陣，則則A A和和B B的并的并(join)(join)是矩陣是矩陣AB=C=(AB=C=(c cijij)

27、)m mn n，其中：，其中：定義定義6.2.106.2.10 如果如果A=(A=(a aijij) )和和B=(B=(b bijij) )是兩個(gè)是兩個(gè)m mn n矩陣，矩陣，則則A A和和B B的交的交(meet)(meet)是矩陣是矩陣AB=C=(AB=C=(c cijij) )，其中：，其中：(6.2.3)(6.2.3) ijijijijijijijijijij1,如1,如果果a= 1且a= 1且b= 1b= 1(1im,(1im,c=c=0,如0,如果果a= 0或a= 0或b= 01jn)b= 01jn)1,1,( (6.2.2)(6.2.2)0,0, ijijijijijijijij

28、ijij如如果果a= 1或a= 1或b= 1b= 11im,1im,c c如如果果a= 0且a= 0且b= 01jn)b= 01jn)即即c cijij = = a aijijb bijij 即即c cijij = = a aijijb bijij 布爾矩陣的運(yùn)算布爾矩陣的運(yùn)算( (續(xù)續(xù)) )定義定義6.2.116.2.11 如果矩陣如果矩陣A=(A=(a aijij) )m mp p，B=(B=(b bijij) )p pn n，則，則A A和和B B的布爾積的布爾積(Boolean product)(Boolean product)是矩陣是矩陣A AB=C=(B=C=(c cijij) )

29、m mn n，其中：，其中： 1, 存1, 存在在k使k使得得a=1且a=1且b=1b=1ikkjikkjc=1kp, 1 im, 1jnc=1kp, 1 im, 1jnijij0, 其0, 其他他兩個(gè)布爾矩陣可進(jìn)行并和交運(yùn)算的前提兩個(gè)布爾矩陣可進(jìn)行并和交運(yùn)算的前提是是有相同的行數(shù)和列數(shù)有相同的行數(shù)和列數(shù)；兩個(gè)布爾矩陣可進(jìn)行布爾積運(yùn)算的前提是兩個(gè)布爾矩陣可進(jìn)行布爾積運(yùn)算的前提是前一矩陣的列數(shù)等于后一矩陣的行數(shù)。前一矩陣的列數(shù)等于后一矩陣的行數(shù)。即即 p pijikkjijikkjk=1k=1c=(ab )c=(ab )例例6.2.106.2.10令令 、 和和 。計(jì)算計(jì)算（1 1）ABAB；

30、（2 2）ABAB； （3 3）ACAC。1 1 0 0 1 11 1 1 1 1 1A A = =1 1 0 0 0 00 0 0 0 1 10 0 00 0 01 0 11 0 1B =B =1 1 01 1 00 1 10 1 10 0 0 0 0 0 1 1C C = = 1 1 0 0 1 1 1 11 1 1 1 0 0 0 01 0 10 0 01 0 11 0 10 0 01 0 11 1 11 0 11 1 11 1 11 0 11 1 1AB =AB =1 0 01 1 01 1 01 0 01 1 01 1 00 0 10 1 10 1 10 0 10 1 10 1 1（

31、1 1）1 0 10 0 00 0 01 0 10 0 00 0 01 1 11 0 11 0 11 1 11 0 11 0 1AB =AB =1 0 01 1 01 0 01 0 01 1 01 0 00 0 10 1 10 0 10 0 10 1 10 0 1（2 2）1 0 11 1 0 11 0 11 1 0 10 0 0 10 0 0 11 1 11 1 1 11 1 11 1 1 1AAC =C = 1 0 1 11 0 1 11 0 00 0 0 11 0 00 0 0 11 1 0 01 1 0 00 0 11 1 0 00 0 11 1 0 0（3 3）解解6.2.4 6.2

32、.4 二元關(guān)系的難點(diǎn)二元關(guān)系的難點(diǎn) 1.1. 序偶有兩層含義：一是序偶有兩層含義：一是“順序順序”，二是，二是“偶對偶對”，即由兩，即由兩個(gè)元素形成的有順序的一個(gè)偶對。當(dāng)個(gè)元素形成的有順序的一個(gè)偶對。當(dāng)xyxy時(shí)，一定有時(shí)，一定有x, y 。注意與由兩個(gè)元素構(gòu)成的集合的區(qū)別；。注意與由兩個(gè)元素構(gòu)成的集合的區(qū)別；2.2. 關(guān)系是一種特殊的集合關(guān)系是一種特殊的集合，牢記其元素是以序偶的形式出現(xiàn)，牢記其元素是以序偶的形式出現(xiàn)的，注意與一般集合的區(qū)別。在一個(gè)普通集合的，注意與一般集合的區(qū)別。在一個(gè)普通集合A A中任取一個(gè)中任取一個(gè)元素表示為元素表示為“x xA A”，在一個(gè)關(guān)系，在一個(gè)關(guān)系R R中任取

33、一個(gè)元素表示中任取一個(gè)元素表示為為“ R R”；3.3. 在在關(guān)系圖表示法關(guān)系圖表示法中，注意中，注意A A到到B B的關(guān)系與的關(guān)系與A A上的關(guān)系相應(yīng)關(guān)系上的關(guān)系相應(yīng)關(guān)系圖的區(qū)別；圖的區(qū)別；4.4. 在關(guān)系矩陣表示法中，對集合在關(guān)系矩陣表示法中，對集合A A到到B B的關(guān)系的關(guān)系R R，對應(yīng)對應(yīng)A A和和B B中不中不同的元素順序，可以得到不同的關(guān)系矩陣同的元素順序，可以得到不同的關(guān)系矩陣，但是，經(jīng)過一，但是，經(jīng)過一些初等變換后，這些不同的關(guān)系矩陣可以變?yōu)橥痪仃嚒Ｐ┏醯茸儞Q后，這些不同的關(guān)系矩陣可以變?yōu)橥痪仃?。因此，在通常情況下，如果集合以枚舉法表示時(shí)，則因此，在通常情況下，如果集合以枚

34、舉法表示時(shí)，則默認(rèn)默認(rèn)枚舉的次序?yàn)樵氐捻樞蛎杜e的次序?yàn)樵氐捻樞颉?6.3 6.3 關(guān)系的運(yùn)算關(guān)系的運(yùn)算設(shè)設(shè)R R，S S都是從集合都是從集合A A到到B B的兩個(gè)關(guān)系，則：的兩個(gè)關(guān)系，則： R RS S|(|(xRy)xRy)(xSy(xSy) R RS S|(|(xRy)xRy)(xSy(xSy) R-S R-S|(|(xRy)(xSxRy)(xSy)y) R R|(x|(xR Ry)y)注意注意：A AB B是相對于是相對于R R的全集的全集，所以，所以有有R RA AB-RB-R，且且R RR RA AB B，R RRR。 R R = = R R, , S SR RR RS S例例6

35、.3.16.3.1設(shè)設(shè)A=a,b,c,dA=a,b,c,d，A A上關(guān)系上關(guān)系R R和和S S定義如下：定義如下： R = , , R = , , ， S = , , S = , , 。計(jì)算計(jì)算 RSRS，RSRS，RSRS，SRSR，R R。解解RS=,RS=,；RS=|(xRy)(xSy)=RS=|(xRy)(xSy)=；RS=|(xRy)(xy)=RS=|(xRy)(xy)=,；R=AR=A2 2R=,R=,=,=,。6.3.1 6.3.1 關(guān)系的關(guān)系的復(fù)合運(yùn)算復(fù)合運(yùn)算定義定義6.3.1 6.3.1 設(shè)設(shè)A,B,CA,B,C是三個(gè)集合，是三個(gè)集合，R R是從是從A A到到B B的關(guān)系的關(guān)

36、系(R(R：AB)AB)，S S是從是從B B到到C C的關(guān)系的關(guān)系(S(S：BC)BC)，則，則R R與與S S的的復(fù)合關(guān)系復(fù)合關(guān)系( (合成關(guān)系合成關(guān)系)()(Composite)RComposite)R S S是從是從A A到到C C的的關(guān)系，并且：關(guān)系，并且： R R S S|xAzC|xAzC( ( y)y)(yBxRyySz)(yBxRyySz)運(yùn)算運(yùn)算“ ”稱為稱為復(fù)合運(yùn)算復(fù)合運(yùn)算( (CompositeOperationCompositeOperation) )。1.1. R R和和S S是可復(fù)合的是可復(fù)合的R R的后域和的后域和S S的的前域完全相同；前域完全相同；2.2.

37、RoSRoS的的前域是前域是R R的前域的前域A A，后域是后域是S S的后域的后域C C；3.3. RoSRoS對任意對任意xAxA和和zCzC，不存在不存在yByB，使得使得xRyxRy和和ySzySz同時(shí)成立同時(shí)成立；4.4. oRoRRoRo 。例例6.3.26.3.2試判斷下列關(guān)系是否是兩個(gè)關(guān)系的復(fù)合，如果是，試判斷下列關(guān)系是否是兩個(gè)關(guān)系的復(fù)合，如果是，請指出對應(yīng)的兩個(gè)關(guān)系。請指出對應(yīng)的兩個(gè)關(guān)系。（1 1）“祖孫祖孫”關(guān)系；關(guān)系； （2 2）“舅甥舅甥”關(guān)系；關(guān)系；（3 3）“兄妹兄妹”關(guān)系。關(guān)系。解解（1 1）“祖孫祖孫”關(guān)系關(guān)系是是“父女父女”關(guān)系關(guān)系和和“母子母子”關(guān)關(guān)系系的復(fù)

38、合或的復(fù)合或“父子父子”關(guān)系關(guān)系與與“父子父子”關(guān)系關(guān)系的復(fù)合；的復(fù)合；（2 2）“舅甥舅甥”關(guān)系關(guān)系是是“兄妹兄妹”關(guān)系關(guān)系和和“母子母子”關(guān)關(guān)系系的復(fù)合；的復(fù)合；（3 3）不是。）不是。例例6.3.36.3.3設(shè)設(shè)A=A=a,b,c,da,b,c,d ，B=B=b,c,db,c,d ，C=C=a,b,da,b,d ，R=R=,是是A A到到B B的關(guān)系，的關(guān)系，S=S=,是是B B到到C C的關(guān)系。的關(guān)系。試用關(guān)系的試用關(guān)系的三種表示方法三種表示方法求求R R S S。解解（1 1）R R S=S=,； 根據(jù)關(guān)系復(fù)合的定義，根據(jù)關(guān)系復(fù)合的定義， RR S S當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)存在存在b bk

39、 kBB使得使得 RR且且 SS，用關(guān)系矩，用關(guān)系矩陣描述即為陣描述即為pk 1ijikkjijikkjr(ab )r(ab )RRSRSSRS1 0 00 0 11 0 00 0 10 0 10 0 11 0 00 0 11 0 00 0 1M= MM =0 0 0 =M= MM =0 0 0 =0 0 11 1 00 0 11 1 01 1 01 1 00 1 00 0 00 1 00 0 0（2 2）R SRSR SRS故故 MMM MMM例例6.3.3(6.3.3(續(xù)續(xù)) )（3 3）R R S S的關(guān)系圖如圖的關(guān)系圖如圖6.3.26.3.2所示，其中圖所示，其中圖6.3.16.3.1

40、是 以是 以 y y 為為 “ 橋 梁橋 梁 ” 的 情 形 。 根 據(jù) 圖的 情 形 。 根 據(jù) 圖 6 . 3 . 26 . 3 . 2 得得R R S=S=, 。c cd db bS SR Ra ab bc cd da ab bd d圖圖6.3.16.3.1A AB BC CRoSRoSa ab bc cd da ab bd d圖圖6.3.26.3.2A AC C例例6.3.46.3.4設(shè)設(shè)A=1,2,3,4A=1,2,3,4，R=,R=,，S=,S=,，T=,T=,是是A A上的三個(gè)關(guān)系。上的三個(gè)關(guān)系。計(jì)算計(jì)算（1 1）RoSRoS和和SoRSoR；（2 2）( (RoS)oTRoS)

41、oT和和Ro(SoTRo(SoT) )。解解(1)RoS=,o, (1)RoS=,o, =, =, SoRSoR=,o,=,o, =, =,(2)(RoS)oT=(,o(2)(RoS)oT=(,o ,)o, ,)o,=,o,=,o,=,=, Ro(SoTRo(SoT)=,)=,=(=(RoS)oTRoS)oT定理定理6.3.16.3.1設(shè)設(shè)A A、B B、C C和和D D是任意四個(gè)集合，是任意四個(gè)集合，R R、S S和和T T分別是從分別是從A A到到B B，B B到到C C和和C C到到D D的二元關(guān)系，則的二元關(guān)系，則（1 1）( (RoS)oTRoS)oT= =Ro(SoTRo(SoT)

42、 )；（2 2）I IA AoRoR= =RoIRoIB B=R=R，其中，其中I IA A和和I IB B分別是分別是A A和和B B上的恒上的恒等關(guān)系。等關(guān)系。分析：分析：二元關(guān)系是集合，二元關(guān)系的復(fù)合是關(guān)系，從二元關(guān)系是集合，二元關(guān)系的復(fù)合是關(guān)系，從 而也是集合，因此上面兩式就是證明兩個(gè)集合相等。而也是集合，因此上面兩式就是證明兩個(gè)集合相等。根據(jù)集合相等的定義，有根據(jù)集合相等的定義，有A=BA=BA A B B并且并且B B A A， A A B B x x A A，有，有x x B B。證明證明(1)(1)任意任意 (R(R S)S) T T，由由“ ”知，知，至少存在至少存在cC，使

43、得，使得R S，T。對對R R S S，同樣同樣至少存一個(gè)至少存一個(gè)bBbB，使得使得R R，S S。于是，由于是，由S S，T T，有，有S S T T，由由R R和和S S T T，知，知R R (S(S T)T)，所以所以(R(R S)S) T T R R (S(S T)T)。同理可證：同理可證：R R (S(S T)T) (R(R S)S) T T。由集合性質(zhì)知：由集合性質(zhì)知：(R(R S)S) T TR R (S(S T)T)。證明證明( (續(xù)續(xù)) )（2 2）任取任取 I IA AoRoR，其中，其中aAaA，bBbB，由，由“o”o”的定義知，存在的定義知，存在aAaA，使得，使

44、得 IIA A且且 RR，從而有從而有I IA A o o R R R R。反 過 來 ， 任 取反 過 來 ， 任 取 R R ， 由， 由 I IA A的 定 義 知 ，的 定 義 知 ， IIA A ，即，即 I IA AoRoR。從而從而RoIRoIA A R R。于是由定理于是由定理1.2.21.2.2知，知，I IA Ao o R R= =R R 。同理可證同理可證RoIRoIB B=R=R。于是于是I IA AoRoR= =RoIRoIB B=R=R得證。得證。 設(shè)設(shè)A A、B B、C C和和D D是任意四個(gè)集合，是任意四個(gè)集合，R R是從是從A A到到B B的關(guān)系，的關(guān)系，S

45、S1 1，S S2 2是從是從B B到到C C的關(guān)系，的關(guān)系，T T是從是從C C到到D D的關(guān)系，則：的關(guān)系，則：1) R1) R (S(S1 1SS2 2) )(R(R S S1 1)(R)(R S S2 2) )2)2) R R (S(S1 1SS2 2) ) (R(R S S1 1)(R)(R S S2 2) )3)3) (S(S1 1SS2 2) ) T T(S(S1 1 T)(ST)(S2 2 T)T)4)4) (S(S1 1SS2 2) ) T T (S(S1 1 T)(ST)(S2 2 T)T)定理定理6.3.26.3.2對任意對任意 (S(S1 1SS2 2) ) T T，則

46、由復(fù)合運(yùn)算知，則由復(fù)合運(yùn)算知，至少存在至少存在ccC C，使得使得 (S(S1 1SS2 2) )， T T。即：即： S S1 1，且，且 S S2 2。因此，由因此，由 S S1 1，且，且 T T，則有：，則有： (S(S1 1 T)T)，由由 S S2 2，且，且 T T，則有：，則有： (S S2 2 T)T)。所以，所以， (S(S1 1 T)(ST)(S2 2 T)T)。即，即，( (S S1 1SS2 2) ) T T (S(S1 1 T)(ST)(S2 2 T)T)。證明：證明：4)4)試說明下面的包含關(guān)系不一定成立。試說明下面的包含關(guān)系不一定成立。（1 1）(RoS(RoS

47、1 1)(RoS)(RoS2 2) ) Ro(SRo(S1 1SS2 2) )（2 2）(S(S1 1oT)(SoT)(S2 2oToT) (S S1 1SS2 2)oT)oT例例6.3.56.3.5分析：分析：如要說明某一事實(shí)如要說明某一事實(shí)不一定不一定成立，則可舉一成立，則可舉一反例加以說明。反例加以說明。設(shè)設(shè)A Aaa，B Bbb1 1,b,b2 2 ，C Ccc，關(guān)系關(guān)系R,SR,S1 1,S,S2 2定義如下：定義如下：R Ra, b, , ，S S1 1b,c，S S2 2b,c則由于則由于S S1 1SS2 2，所以，所以R R (S(S1 1SS2 2) ) R R ，但但(

48、(R R S S1 1) ),(,(R R S S2 2) )，所以所以 ( (R R S S1 1) () (R R S S2 2) ) ，即即 (RoS(RoS1 1)(RoS)(RoS2 2) ) Ro(SRo(S1 1SS2 2) )，這這說明說明(RoS(RoS1 1)(RoS)(RoS2 2) ) Ro(SRo(S1 1SS2 2) )不一定成立。不一定成立。解解(1)(1) 設(shè)設(shè)A Aaa，B Bbb1 1,b,b2 2 ，C Ccc，關(guān)系關(guān)系S S1 1，S S2 2，T T定義如下：定義如下：S S1 1a,b，S S2 2a,b，T Tb,c。則由于則由于S S1 1SS2

49、 2，所以，所以(S(S1 1SS2 2) ) T T T T，但但( (S S1 1 T)T)，(S(S2 2 T)T)，所以所以( (S S1 1 T)(ST)(S2 2 T)T)， 即即(S(S1 1 T)(ST)(S2 2 T)T) (S(S1 1SS2 2) ) T T，這這說明說明(S(S1 1oT)(SoT)(S2 2oToT) (S S1 1SS2 2)oT)oT不一定成立。不一定成立。解解(2)(2) 說明說明如果說明某事實(shí)一定成立，則一定加以證明。如果說明某事實(shí)一定成立，則一定加以證明。如要說明某一事實(shí)如要說明某一事實(shí)不一定不一定成立，則可舉一反成立，則可舉一反例加以說明。

50、例加以說明。如要說明某事實(shí)一定不成立，則也一定加以如要說明某事實(shí)一定不成立，則也一定加以證明。證明。定義定義6.3.2 6.3.2 設(shè)設(shè)A A，B B是兩個(gè)集合，是兩個(gè)集合，R R是是A A到到B B的關(guān)系，則的關(guān)系，則從從B B到到A A的關(guān)系的關(guān)系 R R-1-1|RR稱為稱為R R的的逆關(guān)系逆關(guān)系( (InverseRelationInverseRelation) )，運(yùn)算運(yùn)算“-1”“-1”稱為稱為逆運(yùn)算逆運(yùn)算( (InverseOperationInverseOperation) )。6.3.2 6.3.2 關(guān)系的關(guān)系的逆逆運(yùn)算運(yùn)算注意：注意：關(guān)系是一種集合，逆關(guān)系也是一種集合，關(guān)系

51、是一種集合，逆關(guān)系也是一種集合，因因此，如果此，如果R R是一個(gè)關(guān)系，則是一個(gè)關(guān)系，則R R-1-1和都是關(guān)系，但和都是關(guān)系，但R R-1-1和和是完全不同的兩種關(guān)系，千萬不要混淆。是完全不同的兩種關(guān)系，千萬不要混淆。若若R R A AB B，則，則 A AB BR R A AB B，R R-1-1 B BA A。RRR由定義：由定義： (R (R-1-1) )-1-1=R=R； -1-1=。例例6.3.66.3.6設(shè)設(shè)A=1,2,3,4A=1,2,3,4，B=B=a,b,c,da,b,c,d ，C=2,3,4,5C=2,3,4,5，R R是從是從A A到到B B的一個(gè)關(guān)系且的一個(gè)關(guān)系且R=,

52、 R=, ,，S S是從是從B B到到C C的一個(gè)關(guān)系且的一個(gè)關(guān)系且S=, S=, , , ,。（1 1）計(jì)算）計(jì)算R R-1-1，并畫出，并畫出R R和和R R-1-1的關(guān)系圖；的關(guān)系圖；（2 2）寫出）寫出R R和和R R-1-1的關(guān)系矩陣；的關(guān)系矩陣；（3 3）計(jì)算）計(jì)算(RoS)(RoS)-1-1和和S S-1o-1oR R-1-1。例例6.3.66.3.6解解(1)R(1)R-1-1=,=,-1-1 =, =,，R R和和R R-1-1的關(guān)系圖見圖的關(guān)系圖見圖6.3.36.3.3和圖和圖6.3.46.3.4。圖圖6.3.36.3.3R R1 12 23 34 4a ab bd dc

53、cB BA AR R-1-1a ab bc cd d1 12 24 43 3A AB B圖圖6.3.46.3.4例例6.3.66.3.6解解( (續(xù)續(xù)) )-1-1R RR R1 0 0 01 0 0 01 0 0 01 0 0 00 0 1 00 0 1 10 0 1 00 0 1 1M =,M=M =,M=0 1 0 00 1 0 00 1 0 00 1 0 00 1 0 10 0 0 10 1 0 10 0 0 1(3) (3) RoSRoS=,=,，(RoS)(RoS)-1-1=,=,。 R R-1-1=,=,， S S-1-1=,=,， S S-1-1oRoR-1-1=,=,。(2)

54、 R(2) R和和R R-1-1的關(guān)系矩陣為：的關(guān)系矩陣為：定理定理6.3.36.3.3設(shè)設(shè)A A、B B和和C C是任意三個(gè)集合，是任意三個(gè)集合，R,SR,S分別是從分別是從A A到到B B，B B到到C C的二元關(guān)系，則的二元關(guān)系，則(RoS)(RoS)-1-1=S=S-1-1oRoR-1-1。任取任取(R(R S)S)-1-1，則，則R R S S由由“ ”的定義知：則的定義知：則存在存在b bBB，使得：，使得：R R，S S，由由“R R-1-1”的定義知，的定義知，R R-1-1，S S-1-1，從而有從而有S S-1-1 R R-1-1，即，即(R(R S)S)-1-1 S S-

55、1-1 R R-1-1。反之，任取反之，任取S S-1-1 R R-1-1，由由“ ”的定義知：則至少存一個(gè)的定義知：則至少存一個(gè)bBbB，使得：，使得： S S-1-1和和R R-1-1。由由“R R-1-1”的定義知，有的定義知，有R R，S S。從而從而R R S S，即，即(R(R S)S)-1-1，即，即S S-1-1 R R-1-1 (R(R S)S)-1-1。由集合的定義知：由集合的定義知：(R(R S)S)-1-1S S-1-1 R R-1-1。證明證明 設(shè)設(shè)R R，S S是從集合是從集合A A到集合到集合B B的關(guān)系，則有的關(guān)系，則有 (RS)(RS)-1-1R R-1-1S

56、S-1-1；( (分配性分配性) ) (RS)(RS)-1-1R R-1-1SS-1-1； (R-S)(R-S)-1-1R R-1-1-S-S-1-1； ( () )-1-1 ；( (可換性可換性) ) (A(AB)B)-1-1(B(BA)A)； S S R R S S-1-1 R R-1-1；( (單調(diào)性單調(diào)性) )定理定理6.3.46.3.4RR1 定義定義6.3.36.3.3設(shè)設(shè)R R是集合是集合A A上的關(guān)系，則上的關(guān)系，則R R的的n n次冪次冪，記，記為為R Rn n，定義如下：，定義如下：1.1. R R0 0I IA A|a|aAA；2.2. R R1 1R R；3.3. R

57、Rn+1n+1R Rn n R RR R R Rn n。6.3.3 6.3.3 關(guān)系的關(guān)系的冪冪運(yùn)算運(yùn)算 由于關(guān)系的復(fù)合運(yùn)算滿足結(jié)合律，由于關(guān)系的復(fù)合運(yùn)算滿足結(jié)合律，R Rn n即為即為n n個(gè)個(gè)R R的復(fù)合，也是的復(fù)合，也是A A上的二元關(guān)系。上的二元關(guān)系。 顯然顯然，R Rm m R Rn nR Rm+nm+n，(R(Rm m) )n nR Rmnmn。例例6.3.76.3.7設(shè)設(shè)A=1,2,3,4,5,6A=1,2,3,4,5,6，定義在，定義在A A上的關(guān)系上的關(guān)系R=,R=,，S=,S=,，計(jì)算：計(jì)算：(1)R(1)Rn n(n=1,2,3,4,(n=1,2,3,4,) )， 和和

58、(2(2) )S Sn n(n=1,2,3,4,(n=1,2,3,4,) )， 和和 。 i ii=1i=1S S6 6i ii=1i=1R Ri ii=1i=1R R 6 6i ii=1i=1S S解解（1 1）R R1 1R R，R R2 2R R R R,，R R3 3R R R R R RR R2 2 R R,，R R4 4R R3 3 R R,，R R5 5R R4 4 R R,，R R6 6R R5 5 R R= =,= =R R5 5，R R7 7R R6 6 R RR R5 5， ， R Rn nR R5 5(n(n5)5)。解解( (續(xù)續(xù)1)1) =, =,；6 6i126i

59、126i=1i=1R = R R = R R R R Ri1267i1267i=1i=1R = RR = R R R R R R R 12551255= R= R R R R R R R 6 6i ii=1i=1=R=R（2) S2) S1 1S S，S S2 2S S S S,，S S3 3S S S S S SS S2 2 S S,，S S4 4S S3 3 S S,，S S5 5S S4 4 S S，S S6 6S S5 5 S S，S S7 7，S Sn n(n(n5)5)。解解( (續(xù)續(xù)2)2)由例由例6.3.76.3.7可以看出：可以看出：（1 1）冪集）冪集R Rn n的基數(shù)的基

60、數(shù)| |R Rn n| |并非隨著并非隨著n n的增加而增加，的增加而增加，而是呈遞減趨勢；而是呈遞減趨勢；（2 2）當(dāng)）當(dāng)n|An|A| |時(shí)，則時(shí)，則R Rn n 解解( (續(xù)續(xù)3)3) =, =, , , , ,；6 6i126i126i=1i=1S = S S = S S S S S6 6i126ii126ii=1i=1i=1i=1S = S S = S S S S S =S=S6 6i ii=1i=1R R設(shè)設(shè)A A是有限集合，且是有限集合，且| |A|A|n n，R R是是A A上的二元關(guān)系，則：上的二元關(guān)系，則：11niiiiRR 證明證明顯然，顯然， 。下面證：下面證： 。11