離散數(shù)學(xué)：第6章 二元關(guān)系

2022/11/3第三篇二元關(guān)系第6章二元關(guān)系2022/11/36.0內(nèi)容提要關(guān)系的性質(zhì)3關(guān)系的閉包運(yùn)算4二元關(guān)系1關(guān)系的運(yùn)算22022/11/36.1本章學(xué)習(xí)要求重點(diǎn)掌握一般掌握了解11二元關(guān)系的概念和表示2關(guān)系的復(fù)合與逆運(yùn)算3關(guān)系的性質(zhì)31n重有序組2n個(gè)集合的笛卡兒積3n重有序組相等的判定21關(guān)系的閉包運(yùn)算2022/11/3第三篇二元關(guān)系

關(guān)系理論歷史悠久。它與集合論、數(shù)理邏輯、組合學(xué)、圖論和布爾代數(shù)都有密切的聯(lián)系。關(guān)系是日常生活以及數(shù)學(xué)中的一個(gè)基本概念，例如：兄弟關(guān)系，師生關(guān)系、位置關(guān)系、大小關(guān)系、等于關(guān)系、包含關(guān)系等。2022/11/3第三篇二元關(guān)系另外，關(guān)系理論還廣泛用于計(jì)算機(jī)科學(xué)技術(shù)，如計(jì)算機(jī)程序的輸入、輸出關(guān)系；數(shù)據(jù)庫(kù)的數(shù)據(jù)特性關(guān)系；數(shù)據(jù)結(jié)構(gòu)本身就是一個(gè)關(guān)系等。在某種意義下，關(guān)系是有聯(lián)系的一些對(duì)象相互之間的各種比較行為。2022/11/36.2二元關(guān)系6.2.1序偶與笛卡爾積上,下；左，右；3<4；中國(guó)地處亞洲；平面上點(diǎn)的坐標(biāo)（x,y）等。特征：成對(duì)出現(xiàn)、具有一定的順序。定義6.2.1

由兩個(gè)元素x,y按照一定的次序組成的二元組稱(chēng)為有序偶對(duì)(序偶),記作<x,y>,其中x為第一個(gè)元素，y為第二個(gè)元素。2022/11/3例6.2.1用序偶表示下列語(yǔ)句中的次序關(guān)系(1)平面上點(diǎn)A的橫坐標(biāo)是x,

縱坐標(biāo)是y,x,y∈R；(2)成都是四川的省會(huì)；(3)英語(yǔ)課本在書(shū)桌上；(4)左，右關(guān)系。解各語(yǔ)句的序偶表示如下：(1)<x,y>，x,y∈R；(2)<成都，四川>；(3)<英語(yǔ)課本，書(shū)桌>；(4)<左,右>。2022/11/3序偶相等判定定理定義6.2.2給定序偶<a,b>和<c,d>，如果a=c，b=d，則<a,b>=<c,d>。2022/11/3N重有序組定義6.2.3由n個(gè)元素a1,a2,a3,…,an按照一定次序組成的n元組稱(chēng)為n重有序組(n-Type)(Vector)，記作:<a1,…,an>例6.2.2

用n重有序組描述下列語(yǔ)句。（1）中國(guó)四川成都電子科技大學(xué)計(jì)算機(jī)學(xué)院；（2）2006年9月10日18點(diǎn)16分25秒；（3）16減5再加3除以7等于2。解：（1）<中國(guó),四川,成都,電子科技大學(xué),計(jì)算機(jī)學(xué)院>（2）<2006,9,10,18,16,25>；（3）<16,5,3,7,2>。2022/11/3N重有序組定義6.2.4給定n重有序組<a1,a2,...,an>和<b1,b2,…，bn>。如果ai＝bi(i＝1,2,…，n)，則<a1,a2,...,an>=<b1,b2,…，bn>。2022/11/3笛卡爾乘積定義6.2.5

設(shè)A，B是兩個(gè)集合，稱(chēng)集合：A×B＝{<x,y>|(x∈A)∧(y∈B)}為集合A與B的笛卡爾積(DescartesProduct)。注意：（1）集合A與B的笛卡兒積A×B仍然是集合；（2）集合A×B中的元素是序偶，序偶中的第一個(gè)元素取自A，第二個(gè)元素取自B。2022/11/3例6.2.3設(shè)A={a},B={b,c},C=Φ,D={1,2}，請(qǐng)分別寫(xiě)出下列笛卡兒積中的元素。（1）A×B,B×A；（2）A×C,C×A；（3）A×(B×D),(A×B)×D。解根據(jù)笛卡兒積的定義，有（1）A×B=

{<a,b>,<a,c>},B×A={<b,a>,<c,a>}；（2）A×C=Φ,C×A=Φ；2022/11/3例6.2.3解（續(xù)）（3）因?yàn)锽×D={<b,1>,<b,2>,<c,1>,<c,2>}，所以A×(B×D)={<a,<b,1>>,<a,<b,2>>,<a,<c,1>>,<a,<c,2>>}。同理，(A×B)×D={<<a,b>,1>,<<a,b>,2>,<<a,c>,1>,<<a,c>,2>}。2022/11/3注意由例6.2.3我們可以看出：（1）笛卡兒積不滿足交換律；（2）A×B=Φ當(dāng)且僅當(dāng)A=Φ或者B=Φ；（3）笛卡兒積不滿足結(jié)合律；（4）對(duì)有限集A,B，有

|A×B|=|B×A|=|A|×|B|2022/11/3集合相等兩個(gè)集合互相包含等式成立兩個(gè)集合相等定理6.2.1設(shè)A,B,C是任意三個(gè)集合，則（1）A×(B∪C)=(A×B)∪(A×C)；（2）(B∪C)×A=(B×A)∪(C×A)；（3）A×(B∩C)=(A×B)∩(A×C)；（4）(B∩C)×A=(B×A)∩(C×A)。分析顯然，待證等式兩端都是集合2022/11/3定理6.2.1分析對(duì)（1）A×(B∪C)=(A×B)∪(A×C)A×(B∪C)(A×B)∪(A×C),(A×B)∪(A×C)A×(B∪C)利用按定義證明方法，首先敘述包含關(guān)系的定義，即首先敘述A×(B∪C)(A×B)∪(A×C)的定義：對(duì)任意<x,y>∈A×(B∪C)，…，有<x,y>∈(A×B)∪(A×C)，則A×(B∪C)(A×B)∪(A×C)。同理可分析(A×B)∪(A×C)A×(B∪C)。2022/11/3定理6.2.1證明（1）對(duì)任意<x,y>∈A×(B∪C)，由笛卡兒積的定義知，x∈A且y∈B∪C；由并運(yùn)算定義知，y∈B或者y∈C。于是有x∈A且y∈B或者x∈A且y∈C。從而，<x,y>∈A×B或者<x,y>∈A×C。即<x,y>∈(A×B)∪(A×C)，所以，A×(B∪C)(A×B)∪(A×C)。2022/11/3定理6.2.1證明（續(xù)）另一方面，對(duì)任意<x,y>∈(A×B)∪(A×C)，由并運(yùn)算定義知,<x,y>∈A×B或者<x,y>∈A×C。由笛卡兒積的定義知,x∈A且y∈B或x∈A且y∈C。進(jìn)一步有x∈A且y∈B∪C，從而<x,y>∈A×(B∪C)。所以(A×B)∪(A×C)A×(B∪C)。于是，根據(jù)定理1.2.2，有A×(B∪C)=(A×B)∪(A×C)。(2)、(3)和(4)的證明作為練習(xí)，自證。2022/11/3定理6.2.2設(shè)A,B,C,D是任意四個(gè)集合，則(A×B)(C×D)AC，BD。證明充分性()：對(duì)任意<x,y>∈A×B，有x∈A且y∈B。又因?yàn)锳C，BD，所以有x∈C且y∈D，即<x,y>∈C×D，從而(A×B)(C×D)。2022/11/3定理6.2.2證明（續(xù)）設(shè)A,B,C,D是任意四個(gè)集合，則(A×B)(C×D)AC，BD。證明必要性()：對(duì)任意的x∈A，y∈B，有<x,y>∈A×B。又因?yàn)?A×B)(C×D)，所以<x,y>∈C×D。根據(jù)笛卡兒積的定義有x∈C且y∈D，從而AC，BD。綜上所述，定理成立。2022/11/3定義6.2.6設(shè)A1,A2,…,An是n個(gè)集合，稱(chēng)集合A1×A2×…×An

={<a1,a2,…,an>|(ai∈Ai)∧i∈{1,2,3,…,n}}為集合A1,A2,…,An的笛卡兒積(DescartesProduct)當(dāng)A1=A2=…=An=A時(shí)，有A1×A2×…×An=An。2022/11/3定理6.2.3當(dāng)集合A1,A2,…,An都是有限集時(shí)，|A1×A2×…×An|=|A1|×|A2|×…×|An|。2022/11/36.2.2關(guān)系的定義問(wèn)題：某學(xué)校組織學(xué)生看電影，電影院里共有n個(gè)座位，看電影的學(xué)生共有m個(gè)（m≤n），每個(gè)學(xué)生坐一個(gè)座位。請(qǐng)問(wèn)，怎樣表示學(xué)生和座位之間的從屬關(guān)系？a1a2a3amABbnb3b2b10圖6.2.1假設(shè)A,B分別表示某學(xué)校所有學(xué)生的集合和電影院里所有座位的集合，即A={a1,a2,…,am},B={b1,b2,…,bn}。2022/11/3定義6.2.7設(shè)A,B為兩個(gè)非空集合，稱(chēng)A×B的任何子集R為從A到B的二元關(guān)系，簡(jiǎn)稱(chēng)關(guān)系(Relation)。如A＝B，則稱(chēng)R為A上的二元關(guān)系。 二元關(guān)系設(shè)一有序?qū)?lt;x,y>：若<x,y>∈R，則記為xRy，讀作“x對(duì)y有關(guān)系R”；若<x,y>R，則記為xRy，讀作“x對(duì)y沒(méi)有關(guān)系R”。注：當(dāng)R=Φ時(shí)，稱(chēng)R為空關(guān)系(emptyrelation)；當(dāng)R=A×B時(shí)，則稱(chēng)R為全關(guān)系(TotalRelation)。2022/11/3例6.2.4假設(shè)A={a,b}，B={c,d}，寫(xiě)出從A到B的所有不同關(guān)系。解因?yàn)锳={a,b},B={c,d}，所以A×B={<a,c>,<a,d>,<b,c>,<b,d>}。于是A×B的所有不同子集為：0–元子集：Φ；1–元子集：{<a,c>},{<a,d>},{<b,c>},{<b,d>}；2–元子集：{<a,c>,<a,d>},{<a,c>,<b,c>},{<a,c>,<b,d>},{<a,d>,<b,d>},{<a,d>,<b,d>},{<b,c>,<b,d>}；2022/11/3例6.2.4解（續(xù)）3–元子集：{<a,c>,<a,d>,<b,c>},{<a,c>,<a,d>,<b,d>},{<a,c>,<b,c>,<b,d>},{<a,d>,<b,c>,<b,d>}；4–元子集：{<a,c>,<a,d>,<b,c>,<b,d>}。注意：當(dāng)集合A,B都是有限集時(shí)，A×B共有2|A|?|B|個(gè)不同的子集，即，從A到B的不同關(guān)系共有2|A|?|B|個(gè)。2022/11/3其中，A稱(chēng)為R的前域，B稱(chēng)為R的后域。DA，CB滿足：D＝{x|<x,y>R}，C＝{y|<x,y>R}，稱(chēng)D為R的定義域，記為D＝domR；稱(chēng)C為R的值域,記C＝ranR；并稱(chēng)fldR＝D∪C為R的域。2022/11/3假設(shè)A={a1,a2,a3,a4,a5,a6},B={b1,b2,b3,b4,b5},C={a3,a4,a6},D={b1,b2,b4,b5},R={<a3,b1>,<a3,b2>,<a4,b4>,<a6,b4>,<a6,b5>}。顯然，RC×DA×B。2022/11/3求定義在Z上關(guān)系的定義域、值域和域。（1）R1={<x,y>|(x,y∈Z)∧{y=x2}}；（2）R2={<x,y>|(x,y∈Z)∧{|x|=|y|=7}}。解（1）domR1=Z,ranR1=Z+∪{0},fldR1=Z；

（2）domR2={7,–7},ranR2={7,–7},fldR2={7,–7}。例6.2.52022/11/3例6.2.6設(shè)H={f,m,s,d}表示一個(gè)家庭中父母子女四個(gè)人的集合，確定H上的一個(gè)長(zhǎng)幼關(guān)系RH，指出該關(guān)系的定義域、值域和域。解RH={<f,s>,<f,d>,<m,s>,<m,d>}；domRH={f,m},ranRH={s,d}，fldRH={f,m,s,d}定義6.2.8設(shè)A1,A2,…,An為n個(gè)非空集合，稱(chēng)A1×A2×…×An的任意子集R為以A1×A2×…×An為基的n元關(guān)系(n-Relation)。2022/11/36.2.3關(guān)系的表示法1.集合表示法（枚舉法和敘述法）例6.2.7（1）設(shè)A={a},B={b,c}，用枚舉法寫(xiě)出從A到B的不同關(guān)系；（2）用敘述法寫(xiě)出定義在R上的“相等”關(guān)系。解（1）A到B的不同關(guān)系有：R1=Ф,R2={<a,b>},R3={<a,c>},R4={<a,b>,<a,c>}；（2）設(shè)R上的“相等”關(guān)系為S，則S={<x,y>|(x,y∈R)∧(x=y)}。2022/11/36.2.3關(guān)系的表示法2.關(guān)系圖法（1）A≠B設(shè)A＝{a1,a2,...,an},B＝{b1,b2,...,bn}，R是從A到B的一個(gè)二元關(guān)系，則規(guī)定R的關(guān)系圖如下：

①.設(shè)a1,a2,...,an和b1,b2,...,bn分別為圖中的結(jié)點(diǎn)，用“?！北硎荆?/p>

②.如<ai,bj>R,則從ai到bj可用有向邊ai。。bj相連。<ai,bj>為對(duì)應(yīng)圖中的有向邊。2022/11/3（2)A=B設(shè)A＝B=<a1,a2,...,an>，R是A上的關(guān)系，則R的關(guān)系圖規(guī)定如下：①.設(shè)a1,a2,...,an為圖中節(jié)點(diǎn)，用“?！北硎劲?如<ai,aj>R,則從ai到aj可用有向邊ai。。bj相連。<ai,aj>為對(duì)應(yīng)圖中的有向邊。③.如<ai,ai>R,則從ai到ai用一帶箭頭的小圓環(huán)表示，即：ai2.關(guān)系圖法（續(xù)）2022/11/32圖6.2.3244336134圖6.2.4例6.2.8試用關(guān)系圖表示下面的關(guān)系。（1）設(shè)A={2,3,4}，B={3,4,5,6}，則A到B之間的一種整除關(guān)系:

R1={<2,4>,<2,6>,<3,3>,<3,6>,<4,4>}（2）假設(shè)A={1,2,3,4}，則A上的小于等于關(guān)系:R2={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}。2022/11/3設(shè)A={a1,a2,...,an},B={b1,b2,...,bm},R是從A到B的一個(gè)二元關(guān)系，稱(chēng)矩陣MR＝（rij)n×m為關(guān)系R的關(guān)系矩陣(RelationMatrix)，其中又稱(chēng)MR為R的鄰接矩陣(AdjacencyMatrix)。3.關(guān)系矩陣注意：A中元素序號(hào)對(duì)應(yīng)矩陣元素的行下標(biāo)，B中元素序號(hào)對(duì)應(yīng)矩陣元素的列下標(biāo)；關(guān)系矩陣是0-1矩陣，稱(chēng)為布爾矩陣。2022/11/3例6.2.9

設(shè)A={1,2,3,4}，考慮A上的整除關(guān)系R和等于關(guān)系S。（1）試寫(xiě)出R和S中的所有元素；（2）試寫(xiě)出R和S的關(guān)系矩陣。2022/11/3例6.2.9

解

（1）根據(jù)整除關(guān)系和等于關(guān)系的定義，有

R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<1,3>,<1,4>,<2,4>}S={<1,1>,<2,2>,<3,3>,<4,4>}。（2）設(shè)R和S的關(guān)系矩陣分別為MR和MS，則有

2022/11/3布爾矩陣的運(yùn)算定義6.2.9

如果A=(aij)和B=(bij)是兩個(gè)m×n矩陣,則A和B的并(join)是矩陣A∨B=C=(cij),其中：。(6.2.2)定義6.2.10

如果A=(aij)和B=(bij)是兩個(gè)m×n矩陣,則A和B的交(meet)是矩陣A∧B=C=(cij),其中：。(6.2.3)2022/11/3布爾矩陣的運(yùn)算(續(xù))定義6.2.11

如果A=(aij)是m×p矩陣，B=(bij)是p×n矩陣，則A和B的布爾積(Booleanproduct)是矩陣A⊙B=C=(cij),其中：

兩個(gè)布爾矩陣可進(jìn)行并和交運(yùn)算的前提是有相同的行數(shù)和列數(shù)；兩個(gè)布爾矩陣可進(jìn)行布爾積運(yùn)算的前提是前一矩陣的列數(shù)等于后一矩陣的行數(shù)。2022/11/3例6.2.10令、和。計(jì)算（1）A∨B；（2）A∧B；（3）A⊙C。（1）（2）（3）2022/11/36.2.5關(guān)系的應(yīng)用集合A到集合B上的關(guān)系可以看成是列出了集合A中的一些元素與集合B中的相關(guān)元素的表(table)。例6.2.11

試用關(guān)系表示圖6.2.5。dbcfae圖6.2.5解圖6.2.5可以用關(guān)系表示如下：{<a,c>,<a,b>,<b,b>,<b,f>,<c,d>,<c,e>,<d,c>,<d,b>,<e,f>,<f,d>}。2022/11/3例6.2.12設(shè)集合A={張紅，李明，王強(qiáng)，程飛，趙偉}，B={離散數(shù)學(xué)，操作系統(tǒng)，計(jì)算機(jī)圖形學(xué)}，R={<張紅，離散數(shù)學(xué)>，<李明，離散數(shù)學(xué)>，<王強(qiáng)，操作系統(tǒng)>，<程飛,操作系統(tǒng)>，<趙偉，計(jì)算機(jī)科學(xué)>，<張紅,算法分析>，<李明，組合數(shù)學(xué)>，<王強(qiáng),數(shù)據(jù)結(jié)構(gòu)>，<程飛，組合數(shù)學(xué)>，<趙偉，計(jì)算機(jī)圖形學(xué)>}，試用表的形式表示關(guān)系R。解關(guān)系R的表的表示形式見(jiàn)表6.2.1。學(xué)生課程張紅離散數(shù)學(xué)李明離散數(shù)學(xué)王強(qiáng)操作系統(tǒng)程飛操作系統(tǒng)趙偉計(jì)算機(jī)科學(xué)張紅算法分析李明組合數(shù)學(xué)王強(qiáng)數(shù)據(jù)結(jié)構(gòu)程飛組合數(shù)學(xué)趙偉計(jì)算機(jī)圖形學(xué)2022/11/3例6.2.13請(qǐng)分別將下列表6.2.2和6.2.3表示的關(guān)系改寫(xiě)為關(guān)系集合表示形式。表6.2.2表6.2.38840錘子9921鉗子452油漆2207地毯a3b1b4c1解（1）設(shè)表6.2.2表示的關(guān)系為R1，則R1={<8840,錘子>,<9921,鉗子>,<452,油漆>,<2207,地毯>}；(2)設(shè)表6.2.3表示的關(guān)系為R2，則R2={<a,3>,<b,1>,<b,4>,<c,1>}2022/11/3例6.2.1請(qǐng)將下列關(guān)系改寫(xiě)為表。（1）R={<a,6>,<b,2>,<a,1>,<c,1>}；（2）在{1,2,3}上定義關(guān)系R：如果x2≥y，則<x,y>∈R。解（1）關(guān)系R的表表示形式見(jiàn)表6.2.4；（2）由題意得R={<1,1>,<2,1>,<3,1>,<2,2>,<2,3>,<3,2>,<3,3>}，其對(duì)應(yīng)的表見(jiàn)表6.2.5a6b2a1c111213122233233

表6.2.4表6.2.5

2022/11/36.3關(guān)系的運(yùn)算設(shè)R，S都是從集合A到B的兩個(gè)關(guān)系，則：R∪S＝{<x,y>|(xRy)∨(xSy)}R∩S＝{<x,y>|(xRy)∧(xSy)}注意：A×B是相對(duì)于R的全集，所以有＝A×B-R,且∪R＝A×B,∩R＝Φ。R-S＝{<x,y>|(xRy)∧(xSy)}

＝{<x,y>|(xRy)}2022/11/3例6.3.1

設(shè)A={a,b,c,d}，A上關(guān)系R和S定義如下：R={<a,b>,<b,d>,<c,c>}，S={<a,c>,<b,d>,<d,b>}。計(jì)算R∪S,R∩S,R–S,S–R,。2022/11/3例6.3.1解R∪S={<a,b>,<a,c>,<b,d>,<c,c>,<d,b>}；R∩S={<x,y>|(xRy)∧(xSy)}={<b,d>}；R–S={<x,y>|(xRy)∧(xy)}={<a,b>,<c,c>}；=A2–R={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<b,d>,<c,a>,<c,b>,<c,c>,<c,d>,<d,a>,<d,b>,<d,c>,<d,d>}–{<a,b>,<b,d>,<c,c>}={<a,a>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<c,a>,<c,b>,<c,d>,<d,a>,<d,b>,<d,c>,<d,d>}。2022/11/36.3.1關(guān)系的復(fù)合運(yùn)算定義6.3.1設(shè)A,B,C是三個(gè)集合，R是從A到B的關(guān)系(R:A→B)，S是從B到C的關(guān)系(S:B→C)，則R與S的復(fù)合關(guān)系(合成關(guān)系)(Composite)RS是從A到C的關(guān)系，并且：

RS＝{<x,z>|x∈A∧z∈C∧

(y)(y∈B∧xRy∧ySz)}運(yùn)算“”稱(chēng)為復(fù)合運(yùn)算(CompositeOperation)。2022/11/36.3.1關(guān)系的復(fù)合運(yùn)算1.R和S是可復(fù)合的R的后域和S的前域完全相同；2.RoS的前域是R的前域A，后域是S的后域C；3.RoS=Φ對(duì)任意的x∈A和z∈C，不存在y∈B，使得xRy和ySz同時(shí)成立。4.ΦoR=RoΦ=Φ2022/11/3例6.3.2試判斷下列關(guān)系是否是兩個(gè)關(guān)系的復(fù)合，如果是，請(qǐng)指出對(duì)應(yīng)的兩個(gè)關(guān)系。（1）“祖孫”關(guān)系；（2）“舅甥”關(guān)系；（3）“兄妹”關(guān)系。解（1）“祖孫”關(guān)系是“父女”關(guān)系和“母子”關(guān)系的復(fù)合；（2）“舅甥”關(guān)系是“兄妹”關(guān)系和“母子”關(guān)系的復(fù)合；（3）不是。2022/11/3例6.3.3設(shè)A={a,b,c,d},B={b,c,d},C={a,b,d},R={<a,b>,<c,d>,<b,b>}是A到B的關(guān)系，S={<d,b>,<b,d>,<c,a>}是B到C的關(guān)系。試用關(guān)系的三種表示方法求RS。解（1）RS={<a,d>,<c,b>,<b,d>}；（2）RS的關(guān)系圖如圖6.3.2所示，其中圖6.3.1是以y為“橋梁”的情形。據(jù)圖6.3.2得RS={<a,d>,<c,b>,<b,d>}；bSRoSRabcdabcddcabdabd圖6.3.1圖6.3.22022/11/3例6.3.4設(shè)A={1,2,3,4}，R={<1,2>,<2,2>,<3,4>},S={<2,4>,<3,1>,<4,2>},T={<1,4>,<2,1>,<4,2>}是A上的三個(gè)關(guān)系。計(jì)算（1）RoS和SoR；(1)RoS={<1,2>,<2,2>,<3,4>}o{<2,4>,<3,1>,<4,2>}={<1,4>,<2,4>,<3,2>}SoR={<2,4>,<3,1>,<4,2>}o{<1,2>,<2,2>,<3,4>}={<3,2>,<4,2>}2022/11/3例6.3.4設(shè)A={1,2,3,4}，R={<1,2>,<2,2>,<3,4>},S={<2,4>,<3,1>,<4,2>},T={<1,4>,<2,1>,<4,2>}是A上的三個(gè)關(guān)系。計(jì)算（2）(RoS)oT和Ro(SoT)。(2)(RoS)oT=({<1,2>,<2,2>,<3,4>}o{<2,4>,<3,1>,<4,2>})o{<1,4>,<2,1>,<4,2>}={<1,4>,<2,4>,<3,2>}o{<1,4>,<2,1>,<4,2>}={<1,2>,<2,2>,<3,1>}Ro(SoT)={<1,2>,<2,2>,<3,1>}=(RoS)oT2022/11/3定理6.3.1設(shè)A、B、C和D是任意四個(gè)集合，R、S和T分別是從A到B，B到C和C到D的二元關(guān)系，則（1）(RoS)oT=Ro(SoT)；（2）IAoR=RoIB=R，其中IA和IB分別是A和B上的恒等關(guān)系。分析：二元關(guān)系是集合，二元關(guān)系的復(fù)合是關(guān)系，從而也是集合，因此上面兩式就是證明兩個(gè)集合相等。根據(jù)集合相等的定義，有A=BAB并且BA，

ABxA，有xB。2022/11/3定理6.3.1證明（1）(RoS)oT=Ro(SoT)(1)任意<a,d>∈(RS)T，由“”知,至少存在c∈C,使得<a,c>∈RS,<c,d>∈T.對(duì)<a,c>∈RS，同樣至少存一個(gè)b∈B，使得<a,b>∈R，<b,c>∈S。于是,由<b,c>∈S,<c,d>∈T,有<b,d>∈ST，由<a,b>∈R和<b,d>∈ST，知<a,d>∈R(ST),所以(RS)TR(ST)。同理可證：R(ST)(RS)T。由集合性質(zhì)知：(RS)T＝R(ST)。構(gòu)造性證明方法2022/11/3定理6.3.1證明（2）IAoR=RoIB=R（2）任取<a,b>∈IAoR，其中a∈A，b∈B，由“o”的定義知，存在a∈A，使得<a,a>∈IA且<a,b>∈R，從而有IAo

RR。反過(guò)來(lái)，任取<a,b>∈R，由IA的定義知，<a,a>∈IA

，即<a,b>∈IAoR。從而RoIAR。于是由定理1.2.2知,IAo

R=R。同理可證RoIBR。于是IAoR=RoIB=R得證。2022/11/3設(shè)A、B、C和D是任意四個(gè)集合，R是從A到B的關(guān)系，S1，S2是從B到C的關(guān)系，T是從C到D的關(guān)系，則：

1)、R(S1∪S2)=(RS1)∪(RS2)

2)、R(S1∩S2)(RS1)∩(RS2)

3)、(S1∪S2)T=(S1T)∪(S2T)

4)、(S1∩S2)T

(S1T)∩(S2T)定理6.3.22022/11/3證明：對(duì)任意<b,d>∈(S1∩S2)T，則由復(fù)合運(yùn)算知，至少存在c∈C,使得<b,c>∈(S1∩S2)，<c,d>∈T。即：<b,c>∈S1,且<b,c>∈S2。因此，由<b,c>∈S1,且<c,d>∈T，則有：

<b,d>∈(S1T),

由<b,c>∈S2,且<c,d>∈T，則有：<b,d>∈(S2T)。所以，<b,d>∈(S1T)∩(S2T)。即，

(S1∩S2)T(S1T)∩(S2T)。■定理6.3.2

4)、(S1∩S2)T(S1T)∩(S2T)2022/11/3試說(shuō)明下面的包含關(guān)系不一定成立。（1）(RoS1)∩(RoS2)

Ro(S1∩S2)（2）(S1oT)∩(S2oT)

(S1∩S2)oT例6.3.5分析：如要說(shuō)明某一事實(shí)不一定成立，則可舉一反例加以說(shuō)明。2022/11/3設(shè)A＝{a},B＝{b1,b2},C＝{c},關(guān)系R，S1，S2定義如下：R＝{<c,b1>,<c,b2>},S1＝{<b1,a>},S2＝{<b2,a>}。則由于S1∩S2＝Φ,所以R(S1∩S2)

＝RΦ＝Φ,但(RS1)＝{<c,a>},(RS2)＝{<c,a>}，所以(RS1)∩(RS2)＝{<c,a>}，即(RoS1)∩(RoS2)

Ro(S1∩S2),這說(shuō)明(RoS1)∩(RoS2)Ro(S1∩S2)不一定成立。例6.3.5解（1）(RoS1)∩(RoS2)Ro(S1∩S2)不一定成立2022/11/3設(shè)A＝{a},B＝{b1,b2},C＝{c},關(guān)系S1，S2，T定義如下：S1＝{<a,b1>},S2＝{<a,b2>},T＝{<b1,c>,<b2,c>}。則由于S1∩S2＝Φ,所以(S1∩S2)T＝ΦT＝Φ,但(S1T)＝{<a,c>},(S2T)＝{<a,c>}，所以(S1T)∩(S2T)＝{<a,c>}，

即(S1T)∩(S2T)

(S1∩S2)T，這說(shuō)明(S1oT)∩(S2oT)(S1∩S2)oT不一定成立。例6.3.5解（2）(S1oT)∩(S2oT)(S1∩S2)oT不一定成立2022/11/3說(shuō)明如果說(shuō)明某事實(shí)一定成立，則一定加以證明。如要說(shuō)明某一事實(shí)不一定成立，則可舉一反例加以說(shuō)明。如要說(shuō)明某事實(shí)一定不成立，則也一定加以證明。2022/11/3定義6.3.2設(shè)A，B是兩個(gè)集合，R是A到B的關(guān)系，則從B到A的關(guān)系

R-1＝{<b,a>|<a,b>∈R}稱(chēng)為R的逆關(guān)系(InverseRelation),運(yùn)算“-1”稱(chēng)為逆運(yùn)算(InverseOperation)。6.3.2關(guān)系的逆運(yùn)算注意：關(guān)系是一種集合，逆關(guān)系也是一種集合，因此，如果R是一個(gè)關(guān)系，則R-1和都是關(guān)系，但R-1和是完全不同的兩種關(guān)系，千萬(wàn)不要混淆。(R-1)-1=R；Φ-1=Φ。2022/11/3例6.3.6設(shè)A={1,2,3,4},B={a,b,c,d},C={2,3,4,5},R是從A到B的一個(gè)關(guān)系且R={<1,a>,<2,c>,<3,b>,<4,b>,<4,d>},S是從B到C的一個(gè)關(guān)系且S={<a,2>,<b,4>,<c,3>,<c,5>,<d,5>}。（1）計(jì)算R-1，并畫(huà)出R和R-1的關(guān)系圖；解：(1)R-1={<1,a>,<2,c>,<3,b>,<4,b>,<4,d>}-1={<a,1>,<c,2>,<b,3>,<b,4>,<d,4>}，2022/11/3例6.3.6解(1)R-1={<1,a>,<2,c>,<3,b>,<4,b>,<4,d>}-1={<a,1>,<c,2>,<b,3>,<b,4>,<d,4>}，R和R-1的關(guān)系圖見(jiàn)圖6.3.3和圖6.3.4。R-1abcd124

圖6.3.3圖6.3.43R1234abdcABBA2022/11/3例6.3.6(1)R-1={<1,a>,<2,c>,<3,b>,<4,b>,<4,d>}-1={<a,1>,<c,2>,<b,3>,<b,4>,<d,4>}（2）寫(xiě)出R和R-1的關(guān)系矩陣；解：2022/11/3例6.3.6解(1)R-1={<1,a>,<2,c>,<3,b>,<4,b>,<4,d>}-1={<a,1>,<c,2>,<b,3>,<b,4>,<d,4>}R和R-1的關(guān)系圖見(jiàn)圖6.3.3和圖6.3.4。R-1abcd124

圖6.3.3圖6.3.43R1234abdcABBA2022/11/3例6.3.6解（續(xù)）解：(3)∵RoS={<1,2>,<2,3>,<2,5>,<3,4>,<4,4>,<4,5>}，∴(RoS)-1={<2,1>,<3,2>,<5,2>,<4,3>,<4,4>,<5,4>}?！?/p>

R-1={<a,1>,<c,2>,<b,3>,<b,4>,<d,4>}，

S-1={<2,a>,<4,b>,<3,c>,<5,c>,<5,d>}，∴S-1oR-1={<2,1>,<3,2>,<5,2>,<4,3>,<4,4>,<5,4>}。設(shè)A={1,2,3,4},B={a,b,c,d},C={2,3,4,5},R是從A到B的一個(gè)關(guān)系且R={<1,a>,<2,c>,<3,b>,<4,b>,<4,d>},S是從B到C的一個(gè)關(guān)系且S={<a,2>,<b,4>,<c,3>,<c,5>,<d,5>}。求：(3)計(jì)算(RoS)-1和S-1oR-1。2022/11/3注意（1）將R的關(guān)系圖中有向邊的方向改變成相反方向即得R-1的關(guān)系圖，反之亦然；（2）將R的關(guān)系矩陣轉(zhuǎn)置即得R-1的關(guān)系矩陣，即R和R-1的關(guān)系矩陣互為轉(zhuǎn)置矩陣。（3）R-1的前域與后域正好是R的后域和前域，即domR=ranR-1，domR-1=ranR；（4）|R|=|R-1|；（5）(RoS)-1=S-1oR-1.2022/11/3設(shè)A、B和C是任意三個(gè)集合，R,S分別是從A到B，B到C的二元關(guān)系，則(RoS)-1=S-1oR-1。定理6.3.32022/11/3任取<c,a>∈(RS)-1，則<a,c>∈RS由“”的定義知：則至少存一個(gè)b∈B,使得：<a,b>∈R，<b,c>∈S，由“R-1”的定義知，<b,a>∈R-1,<c,b>∈S-1，從而有<c,a>∈S-1R-1，即(RS)-1S-1R-1。反之，任取<c,a>∈S-1R-1，由“”的定義知：則至少存一個(gè)b∈B,使得：

<c,b>∈S-1和<b,a>∈R-1。由“R-1”的定義知，有<a,b>∈R,<b,c>∈S。從而<a,c>∈RS，即<c,a>∈(RS)-1,即S-1R-1(RS)-1。由集合的定義知：(RS)-1＝S-1R-1?！龆ɡ?.3.3的證明

(RoS)-1=S-1oR-12022/11/3設(shè)R，S是從集合A到集合B的關(guān)系，則有(R∪S)-1＝R-1∪S-1； (分配性)(R∩S)-1＝R-1∩S-1；

(R-S)-1＝R-1-S-1；(

)-1＝； (可換性)(A×B)-1＝(B×A)；

SRS-1R-1； (單調(diào)性)定理6.3.42022/11/3定義6.3.3設(shè)R是集合A上的關(guān)系，則R的n次冪，記為Rn,定義如下：(1)R0＝IA＝{<a,a>|a∈A}；(2)R1＝Ｒ；(3)Rn+1＝RnR＝RRn。6.3.3關(guān)系的冪運(yùn)算顯然，RmRn

＝

Rm+n,(Rm)n

＝

Rmn。該Rn也是A上的二元關(guān)系，2022/11/3例6.3.7設(shè)A={1,2,3,4,5,6}，定義在A上的關(guān)系R={<1,1>,<1,2>,<2,3>,<3,4>,<4,5>,<5,6>}，S={<1,2>,<2,3>,<3,4>,<4,5>,<5,6>}，計(jì)算：(1)Rn(n=1,2,3,4,…)，和(2)Sn(n=1,2,3,4,…)，和。2022/11/3例6.3.7解（1）R1＝R，R2＝RR

＝{<a,a>,<a,b>,<a,c>,<b,d>,<c,e>,<d,f>}，R3＝RRR＝R2R＝{<a,a>,<a,b>,<a,c>,<a,d>,<b,e>,<c,f>}，R4＝R3R＝{<a,a>,<a,b>,<a,c>,<a,d>,<a,e>,<b,f>}，R5＝R4R＝{<a,a>,<a,b>,<a,c>,<a,d>,<a,e>,<a,f>}，R6＝R5R={<a,a>,<a,b>,<a,c>,<a,d>,<a,e>,<a,f>}=R5，

R7＝R6R＝R5，…，Rn＝R5

(n＞5)。2022/11/3例6.3.7解（續(xù)）={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,3>,<2,4>,<2,5>,<2,6>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,6>}；2022/11/3

（2)S1＝S,例6.3.7解（續(xù)）

S2＝SS＝{<a,c>,<b,d>,<c,e>,<d,f>}，S3＝SSS＝S2S＝{<a,d>,<b,e>,<c,f>}，S4＝S3S＝{<a,e>,<b,f>}，S5＝S4S＝{<a,f>}，S6＝S5S＝Φ，S7＝Φ，

…，

Sn＝Φ

(n＞5)。2022/11/3由例6.3.7可以看出：（1）冪集Rn的基數(shù)|Rn|并非隨著n的增加而增加，而是呈遞減趨勢(shì)；（2）當(dāng)n≥|A|時(shí)，則Rn

例6.3.7解（續(xù)）={<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,3>,<2,4>,<2,5>,<2,6>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,6>}；2022/11/3證明

顯然，

。下面證：設(shè)A是有限集合，且|A|=n，R是A上的二元關(guān)系，則：

——說(shuō)明冪運(yùn)算具有周期性定理6.3.5由于，

為此，只要證明對(duì)任意的k＞n，有Rk

即可。對(duì)任意<a,b>∈Rk，則由“”的定義知，存在a1,a2,…,ak-1∈A（為了統(tǒng)一，并假設(shè)a0＝a，ak＝b)，使得：<a0,a1>∈R，<a1,a2>∈R，<a2,a3>∈R，…,<ak-1,ak>∈R。構(gòu)造性證明方法2022/11/3由于|A|＝n，所以由鴿籠原理知：a0,a1,…,ak共k+1個(gè)元素中至少有兩個(gè)以上元素相同.不妨假設(shè)ai＝aj(i＜j)，則可在<a0,a1>∈R，<a1,a2>∈R，<a2,a3>∈R，…,<ak-1,ak>∈R中刪去<ai,ai+1>∈R，<ai+1,ai+2>∈R，…,<aj-1,aj>∈R后仍有<a0,a1>∈R，<a1,a2>∈R，<a2,a3>∈R，…,<ai-1,ai>∈R，<aj,aj+1>∈R，…,<ak-1,ak>∈R定理6.3.5證明續(xù)2022/11/3即有：<a,b>，由此有：Rk

。由k的任意性知：

，

由關(guān)系的復(fù)合運(yùn)算得，<a,b>=<a0,ak>∈Rk’，其中k’＝k-(j-i)，此時(shí)：定理6.3.5證明續(xù)若k'≤n，則：<a,b>；

若k'＞n，則重復(fù)上述做法，最終總能找到k"≤n，使得：<a,b>＝<a0,ak>∈Rk"，所以，

。■2022/11/3有R8

即可。設(shè)A={a0，a1，a2，a3，a4,a5}，|A|＝6，R是A上的二元關(guān)系。例：取k＝8＞6＝n，對(duì)<a,b>∈R8，則由“”的定義知，存在a1,a2,…,a7∈A（為了統(tǒng)一，并假設(shè)a0＝a，a8＝b)，使得：<a0,a1>∈R，<a1,a2>∈R，<a2,a3>∈R，<a3,a4>∈R，<a4,a5>∈R，<a5,a6>∈R，<a6,a7>∈R，<a7,a8>∈R。2022/11/3由于|A|＝6，所以由鴿籠原理知：9個(gè)元素中至少有兩個(gè)以上元素相同，不妨假設(shè)a4＝a7(4＜7)，則可在<a0,a1>∈R，<a1,a2>∈R，<a2,a3>∈R，<a3,a4>∈R，<a4,a5>∈R，<a5,a6>∈R，<a6,a7>∈R，<a7,a8>∈R。中刪去<a4,a5>∈R，<a5,a6>∈R，<a6,a7>∈R，后有<a0,a1>∈R，<a1,a2>∈R，<a2,a3>∈R，<a3,a4>∈R，<a7,a8>∈R。例（續(xù)）：2022/11/3由關(guān)系的復(fù)合運(yùn)算得，<a,b>=<a0,a8>∈R5，其中5＝8-(7-4)，此時(shí)：顯然，5<6，則：<a,b>；例（續(xù)）：2022/11/36.3.5關(guān)系運(yùn)算的應(yīng)用例6.3.8設(shè)有關(guān)系R和S分別如表6.3.1和表6.3.2所示，現(xiàn)在在R中增加關(guān)系S中的所有元組，試求增加后的關(guān)系。ABC462213615ABC125213562表6.3.1表6.3.22022/11/3分析在關(guān)系R中增加S中的所有元組，在關(guān)系數(shù)據(jù)庫(kù)中稱(chēng)為對(duì)關(guān)系表的插入操作(InsertOperation)，該操作可以通過(guò)關(guān)系的并運(yùn)算完成，即求在R中增加關(guān)系S的所有元組等價(jià)于求R∪S。解關(guān)系R增加S的元組后所構(gòu)成的關(guān)系R∪S，見(jiàn)右表。ABC1252135624626152022/11/3例6.3.9設(shè)有關(guān)系R和S如表6.3.4和表6.3.5所示，現(xiàn)在在R中去掉關(guān)系S中所出現(xiàn)的元組，試求去掉S后的關(guān)系。解關(guān)系R中除去S中所出現(xiàn)的元組后所得的關(guān)系R-S如表6.3.6所示。ABCABCABC123123456456789789表6.3.4表6.3.5表6.3.62022/11/36.4關(guān)系的性質(zhì)

本節(jié)涉及到的關(guān)系，如無(wú)特別聲明，都是假定其前域和后域相同。即都為定義在集合A上的關(guān)系，且A是非空集合。對(duì)于前后域不相同的關(guān)系，其性質(zhì)無(wú)法加以定義。2022/11/36.4.1關(guān)系性質(zhì)的定義1、自反性和反自反性定義6.4.1

設(shè)R是集合A上的關(guān)系，（1）如果對(duì)x∈A,都有<x,x>∈R，那么稱(chēng)R在A上是自反的(Reflexive)，或稱(chēng)R具有自反性(Reflexivity)；例如：同學(xué)關(guān)系。（2）如果對(duì)任意的x∈A，都有<x,x>R，那么稱(chēng)R在A上是反自反的(Antireflexive)，或稱(chēng)R具有反自反性(Antireflexivity)。例如：父子關(guān)系。2022/11/3符號(hào)化：（1）R在A上是自反的

(x)(x∈A→<x,x>∈R)=1，（2）R在A上是反自反的

(x)(x∈A→<x,x>R)=1。根據(jù)上面兩式分別可得：（1）R在A上不是自反的

(x)(x∈A∧<x,x>R))=1，（2）R在A上不是反自反的

(x)(x∈A∧<x,x>∈R)=1。2022/11/3例6.4.1設(shè)A={1,2,3}，定義A上的關(guān)系R,S和T如下：（1）R={<1,1>,<1,2>,<2,2>,<3,3>}；（2）S={<1,2>,<2,3>,<3,1>}；（3）T={<1,1>,<1,2>,<1,3>,<3,1>,<3,3>}。判斷這三個(gè)關(guān)系是否具有自反性或者反自反性。解：R：自反

S：反自反

T：既不是自反的，也不是反自反的。R在A上是自反的(x)(x∈A→<x,x>∈R)=1R在A上是反自反的(x)(x∈A→<x,x>R)=12022/11/3例6.4.1解（1）a)因?yàn)锳中x，都有<x,x>∈R，

所以R是自反的；

b）因?yàn)锳中x，都有<x,x>S，

所以S是反自反的；

c）因?yàn)榇嬖?∈A，使<2,2>T，

所以T不是自反的；又因?yàn)榇嬖?∈A，使<1,1>∈T，

所以T不是反自反的，即T既不是自反的，也不是反自反的。2022/11/3（2）設(shè)R,S和T的關(guān)系矩陣分別為MR,MS和MT，則：（3）R,S和T的關(guān)系圖分別是下圖的(a),(b)和(c)。例6.4.1解（續(xù)）133123212(a)(b)(c)2022/11/3結(jié)論：（1）關(guān)系R是自反的R一定不是反自反的；（2）存在既不是自反的也不是反自反的關(guān)系；（3）關(guān)系R是自反的

關(guān)系圖中每個(gè)結(jié)點(diǎn)都有自環(huán)，關(guān)系R是反自反的

關(guān)系圖中每個(gè)結(jié)點(diǎn)都無(wú)自環(huán)；（4）關(guān)系R是自反的

關(guān)系矩陣的主對(duì)角線上全為1，關(guān)系R是反自反的關(guān)系矩陣的主對(duì)角線上全為0。2022/11/3例6.4.2設(shè)A={a,b}，試計(jì)算A上所有具有自反性的關(guān)系R的個(gè)數(shù)。解

A上具有自反性的關(guān)系R的個(gè)數(shù)為：C（2，0）+C（2，1）+C（2，2）=4.2022/11/32、對(duì)稱(chēng)性和反對(duì)稱(chēng)性定義6.4.2設(shè)R是集合A上的關(guān)系。（1）對(duì)任意的x,y∈A，如果<x,y>∈R，那么<y,x>∈R，則稱(chēng)關(guān)系R是對(duì)稱(chēng)的(Symmetric)，或稱(chēng)R具有對(duì)稱(chēng)性(Symmetry)；（2）對(duì)任意的x,y∈A，如果<x,y>∈R且<y,x>∈R，那么x=y，則稱(chēng)關(guān)系R是反對(duì)稱(chēng)的(Antisymmetric)，或稱(chēng)R具有反對(duì)稱(chēng)性(Antisymmetry)。2022/11/3（1）R在A上是對(duì)稱(chēng)的對(duì)x,y∈A，有：<x,y>∈R并且<y,x>∈R或<x,y>R并且<y,x>R。（2）R在A上是反對(duì)稱(chēng)的對(duì)x,y∈A，如果x≠y，則<x,y>R或<y,x>R。符號(hào)化：（1）R在A上是對(duì)稱(chēng)的(x)(y)(x∈A∧y∈A∧<x,y>∈R→<y,x>∈R)=1，（2）R在A上是反對(duì)稱(chēng)的(x)(y)(x∈A∧y∈A∧<x,y>∈R∧<y,x>∈R→x=y)=1。2022/11/3結(jié)論：（3）R在A上不是對(duì)稱(chēng)的x,y∈A，有<x,y>∈R但<y,x>R或者<x,y>R但<y,x>∈R；（4）R在A上不是反對(duì)稱(chēng)的

x,y∈A，有<x,y>∈R且<y,x>∈R。2022/11/3例6.4.2設(shè)A={1,2,3,4}，定義A上的關(guān)系R,S,T和V如下：（1）R={<1,1>,<1,3>,<3,1>,<4,4>}；（2）S={<1,1>,<1,3>,<1,4>,<2,4>}；（3）T={<1,1>,<1,2>,<1,3>,<3,1>,<1,4>}；（4）V={<1,1>,<2,2>,<3,3>,<4,4>}。試判定它們是否具有對(duì)稱(chēng)性和反對(duì)稱(chēng)性，并寫(xiě)出R,S,T和V的關(guān)系矩陣和畫(huà)出相應(yīng)的關(guān)系圖。對(duì)稱(chēng)反對(duì)稱(chēng)不是對(duì)稱(chēng)的，也不是反對(duì)稱(chēng)是對(duì)稱(chēng)的，也是反對(duì)稱(chēng)2022/11/3例6.4.2解（1）a）關(guān)系R是對(duì)稱(chēng)的；b）關(guān)系S是反對(duì)稱(chēng)的；c）在關(guān)系T中，有<1,2>，但沒(méi)有<2,1>,即S不是對(duì)稱(chēng)的；另外有<1,3>，且有<3,1>，但是1≠3，即S不是反對(duì)稱(chēng)的。

因此T既不是對(duì)稱(chēng)的，也不是反對(duì)稱(chēng)的；d）在關(guān)系V中，對(duì)x,y∈A，x≠y時(shí)都有<x,y>R，根據(jù)式(6.4.5)和(6.4.6)知V既是對(duì)稱(chēng)的，也是反對(duì)稱(chēng)的。2022/11/3例6.4.2解（2）1234(a)(b)(c)(d)123412341234設(shè)R,S,T和V的關(guān)系矩陣分別為MR,MS,MT和MV，則(3)R,S,T和Ｖ的關(guān)系圖分別是圖(a),(b),(c)和(d)。2022/11/3注意（1）存在既不是對(duì)稱(chēng)也不是反對(duì)稱(chēng)的關(guān)系，也存在既是對(duì)稱(chēng)也是反對(duì)稱(chēng)的關(guān)系；（2）關(guān)系R是對(duì)稱(chēng)的關(guān)系圖中任何一對(duì)結(jié)點(diǎn)之間，要么有方向相反的兩條邊，要么無(wú)任何邊；關(guān)系R是反對(duì)稱(chēng)的關(guān)系圖中任何一對(duì)結(jié)點(diǎn)之間，至多有一條邊；（3）關(guān)系R是對(duì)稱(chēng)的R的關(guān)系矩陣為對(duì)稱(chēng)矩陣，關(guān)系R是反對(duì)稱(chēng)的R的關(guān)系系矩陣為反對(duì)稱(chēng)矩陣。2022/11/33、傳遞性定義6.4.3設(shè)R是集合A上的關(guān)系。對(duì)任意的x,y,z∈A，如果<x,y>∈R且<y,z>∈R，那么<x,z>∈R，則稱(chēng)關(guān)系R是傳遞的(Transitive)，或稱(chēng)R具有傳遞性(Transitivity)。將定義6.4.3符號(hào)化為：R在A上是傳遞的(x)(y)(z)(x∈A∧y∈A∧z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R)=1。（6.4.7）2022/11/3結(jié)論：（1）對(duì)任意的x,y,z∈A，如果<x,y>∈R，<y,z>∈R且<x,z>∈R，則R在A上是傳遞的；（2）對(duì)任意的x,y,z∈A，如果<x,y>R或者<y,z>R，則R在A上是傳遞的（3）R在A上不是傳遞的當(dāng)且僅當(dāng)存在x,y,z∈A，有<x,y>∈R且<y,z>∈R，但<x,z>R。2022/11/3例6.4.3設(shè)A={1,2,3}，定義A上的關(guān)系R,S,T和V如下：（1）R={<1,1>,<1,2>,<2,3>,<1,3>}；（2）S={<1,2>}；（3）T={<1,1>,<1,2>,<2,3>}；（4）V={<1,2>,<2,3>,<1,3>,<2,1>}。試判定它們是否具有傳遞性，并寫(xiě)出R,S,T和V的關(guān)系矩陣和畫(huà)出相應(yīng)的關(guān)系圖。是傳遞的是傳遞的不是傳遞的不是傳遞的2022/11/3（1）a)關(guān)系R是傳遞的；

b)關(guān)系S是傳遞的；

c)在關(guān)系T中，存在x=1,y=2,z=3∈A且<1,2>,<2,3>∈T，但<1,3>T，根據(jù)式(6.4.7)知T不是傳遞的；

d)在關(guān)系V中，存在x=1,y=2和z=1∈A，使得<1,2>∈V且<2,1>∈V，但是<1,1>V，根據(jù)式(6.4.7)知關(guān)系V不是傳遞的。例6.4.3解,2022/11/3例6.4.3解（續(xù)）（2）設(shè)R,S,T和V的關(guān)系矩陣分別為MR,MS,MT和MV，則。（3）R,S,T和Ｖ的關(guān)系圖分別是圖a),(b),(c)和(d).123(a)(b)(c)(d)1231231232022/11/3例6.4.5設(shè)A={a,b},試畫(huà)出A上所有具有傳遞性的關(guān)系R的關(guān)系圖。解A上所有具有傳遞性的關(guān)系R共8種，其關(guān)系圖見(jiàn)下圖。2022/11/3自反性反自反性對(duì)稱(chēng)性反對(duì)稱(chēng)性傳遞性集合IARR∩IA=R=R1R∩R1IARRR關(guān)系矩陣主對(duì)角線元素全是1主對(duì)角線元素全是0矩陣是對(duì)稱(chēng)矩陣若rij＝1,且i≠j,則rji＝0M2中1位置,在M中相應(yīng)位置都是1關(guān)系圖每個(gè)頂點(diǎn)都有環(huán)每個(gè)頂點(diǎn)都沒(méi)有環(huán)兩點(diǎn)之間有邊,是一對(duì)方向相反的邊兩點(diǎn)之間有邊,并且是一條有向邊點(diǎn)xi到xj有邊,xj到xk有邊,則xi到xk也有邊關(guān)系性質(zhì)的三種等價(jià)條件五種性質(zhì)在關(guān)系矩陣和關(guān)系圖中的特點(diǎn)：2022/11/3總結(jié)對(duì)任意給定的A上的關(guān)系R，可以采用下面的四種方法判定它所具有的性質(zhì)：（1）定義判定法；（2）關(guān)系矩陣判定法；（3）關(guān)系圖判定法；（4）符號(hào)化語(yǔ)言判定法。2022/11/3例6.4.6判定下列關(guān)系所具有的特殊性質(zhì)。（1）集合A上的全關(guān)系；（2）集合A上的空關(guān)系；（3）集合A上的恒等關(guān)系。解(1)集合A上的全關(guān)系具有自反性，對(duì)稱(chēng)性和傳遞性；(2)集合A上的空關(guān)系具有反自反性、對(duì)稱(chēng)性、反對(duì)稱(chēng)性和傳遞性；特別地，如果A為空集，則A上的空關(guān)系具有自反性、反自反性、對(duì)稱(chēng)性、反對(duì)稱(chēng)性和傳遞性；(3)集合A上的恒等關(guān)系具有自反性、對(duì)稱(chēng)性、反對(duì)稱(chēng)性和傳遞性。2022/11/3例6.4.7判定下列關(guān)系所具有的特殊性質(zhì)。（1）在實(shí)數(shù)集R上定義的“等于”關(guān)系；（2）冪集上的“真包含”關(guān)系。解（1）R上的“等于”關(guān)系具有自反性、對(duì)稱(chēng)性、反對(duì)稱(chēng)性和傳遞性；（2）冪集上的“真包含”關(guān)系具有反自反性，反對(duì)稱(chēng)性和傳遞性。2022/11/3例6.4.8假設(shè)A={a,b,c,d}，R={<a,a>,<a,b>,<b,a>,<c,d>}是定義在A上的關(guān)系。試判定R所具有的特殊性質(zhì)。解由前面的分析可知，R既不是自反的，也不是反自反的；既不是對(duì)稱(chēng)的，也不是反對(duì)稱(chēng)的；而且也不是傳遞的。即R不具備關(guān)系的任何性質(zhì)。2022/11/3例6.4.9設(shè)R={<1,1>,<2,2>}，試分別判斷R在集合A或集合B上具備的特殊性質(zhì)，其中A={1,2},B={1,2,3}。解

當(dāng)R是定義在集合A上的關(guān)系時(shí)，R是自反、對(duì)稱(chēng)、反對(duì)稱(chēng)和傳遞的；當(dāng)R是定義在集合B上的關(guān)系時(shí)，R是對(duì)稱(chēng)、反對(duì)稱(chēng)和傳遞的。注意：絕對(duì)不能脫離基集來(lái)談?wù)撽P(guān)系的性質(zhì)。2022/11/3定理6.4.1

設(shè)R是集合A上的二元關(guān)系，則：（1）R是自反的IAR；（2）R是反自反的

R∩IA＝Φ；（3）R是對(duì)稱(chēng)的

R＝R-1；（4）R是反對(duì)稱(chēng)的

R∩R-1IA；（5）R是傳遞的

RRR。6.4.2關(guān)系性質(zhì)的判斷定理2022/11/3證明（4）R是反對(duì)稱(chēng)的

R∩R-1IA（4）

“”

設(shè)R是反對(duì)稱(chēng)的。對(duì)<a,b>∈R∩R-1,則(<a,b>∈R)∧(<a,b>∈