離散數(shù)學：第6章 二元關系

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

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

由兩個元素x,y按照一定的次序組成的二元組稱為有序偶對(序偶),記作<x,y>,其中x為第一個元素，y為第二個元素。2022/11/3例6.2.1用序偶表示下列語句中的次序關系(1)平面上點A的橫坐標是x,

縱坐標是y,x,y∈R；(2)成都是四川的省會；(3)英語課本在書桌上；(4)左，右關系。解各語句的序偶表示如下：(1)<x,y>，x,y∈R；(2)<成都，四川>；(3)<英語課本，書桌>；(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個元素a1,a2,a3,…,an按照一定次序組成的n元組稱為n重有序組(n-Type)(Vector)，記作:<a1,…,an>例6.2.2

用n重有序組描述下列語句。（1）中國四川成都電子科技大學計算機學院；（2）2006年9月10日18點16分25秒；（3）16減5再加3除以7等于2。解：（1）<中國,四川,成都,電子科技大學,計算機學院>（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

設A，B是兩個集合，稱集合：A×B＝{<x,y>|(x∈A)∧(y∈B)}為集合A與B的笛卡爾積(DescartesProduct)。注意：（1）集合A與B的笛卡兒積A×B仍然是集合；（2）集合A×B中的元素是序偶，序偶中的第一個元素取自A，第二個元素取自B。2022/11/3例6.2.3設A={a},B={b,c},C=Φ,D={1,2}，請分別寫出下列笛卡兒積中的元素。（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）因為B×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=Φ當且僅當A=Φ或者B=Φ；（3）笛卡兒積不滿足結(jié)合律；（4）對有限集A,B，有

|A×B|=|B×A|=|A|×|B|2022/11/3集合相等兩個集合互相包含等式成立兩個集合相等定理6.2.1設A,B,C是任意三個集合，則（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分析對（1）A×(B∪C)=(A×B)∪(A×C)A×(B∪C)(A×B)∪(A×C),(A×B)∪(A×C)A×(B∪C)利用按定義證明方法，首先敘述包含關系的定義，即首先敘述A×(B∪C)(A×B)∪(A×C)的定義：對任意<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）對任意<x,y>∈A×(B∪C)，由笛卡兒積的定義知，x∈A且y∈B∪C；由并運算定義知，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ù)）另一方面，對任意<x,y>∈(A×B)∪(A×C)，由并運算定義知,<x,y>∈A×B或者<x,y>∈A×C。由笛卡兒積的定義知,x∈A且y∈B或x∈A且y∈C。進一步有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)的證明作為練習，自證。2022/11/3定理6.2.2設A,B,C,D是任意四個集合，則(A×B)(C×D)AC，BD。證明充分性()：對任意<x,y>∈A×B，有x∈A且y∈B。又因為AC，BD，所以有x∈C且y∈D，即<x,y>∈C×D，從而(A×B)(C×D)。2022/11/3定理6.2.2證明（續(xù)）設A,B,C,D是任意四個集合，則(A×B)(C×D)AC，BD。證明必要性()：對任意的x∈A，y∈B，有<x,y>∈A×B。又因為(A×B)(C×D)，所以<x,y>∈C×D。根據(jù)笛卡兒積的定義有x∈C且y∈D，從而AC，BD。綜上所述，定理成立。2022/11/3定義6.2.6設A1,A2,…,An是n個集合，稱集合A1×A2×…×An

={<a1,a2,…,an>|(ai∈Ai)∧i∈{1,2,3,…,n}}為集合A1,A2,…,An的笛卡兒積(DescartesProduct)當A1=A2=…=An=A時，有A1×A2×…×An=An。2022/11/3定理6.2.3當集合A1,A2,…,An都是有限集時，|A1×A2×…×An|=|A1|×|A2|×…×|An|。2022/11/36.2.2關系的定義問題：某學校組織學生看電影，電影院里共有n個座位，看電影的學生共有m個（m≤n），每個學生坐一個座位。請問，怎樣表示學生和座位之間的從屬關系？a1a2a3amABbnb3b2b10圖6.2.1假設A,B分別表示某學校所有學生的集合和電影院里所有座位的集合，即A={a1,a2,…,am},B={b1,b2,…,bn}。2022/11/3定義6.2.7設A,B為兩個非空集合，稱A×B的任何子集R為從A到B的二元關系，簡稱關系(Relation)。如A＝B，則稱R為A上的二元關系。 二元關系設一有序?qū)?lt;x,y>：若<x,y>∈R，則記為xRy，讀作“x對y有關系R”；若<x,y>R，則記為xRy，讀作“x對y沒有關系R”。注：當R=Φ時，稱R為空關系(emptyrelation)；當R=A×B時，則稱R為全關系(TotalRelation)。2022/11/3例6.2.4假設A={a,b}，B={c,d}，寫出從A到B的所有不同關系。解因為A={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>}。注意：當集合A,B都是有限集時，A×B共有2|A|?|B|個不同的子集，即，從A到B的不同關系共有2|A|?|B|個。2022/11/3其中，A稱為R的前域，B稱為R的后域。DA，CB滿足：D＝{x|<x,y>R}，C＝{y|<x,y>R}，稱D為R的定義域，記為D＝domR；稱C為R的值域,記C＝ranR；并稱fldR＝D∪C為R的域。2022/11/3假設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上關系的定義域、值域和域。（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設H={f,m,s,d}表示一個家庭中父母子女四個人的集合，確定H上的一個長幼關系RH，指出該關系的定義域、值域和域。解RH={<f,s>,<f,d>,<m,s>,<m,d>}；domRH={f,m},ranRH={s,d}，fldRH={f,m,s,d}定義6.2.8設A1,A2,…,An為n個非空集合，稱A1×A2×…×An的任意子集R為以A1×A2×…×An為基的n元關系(n-Relation)。2022/11/36.2.3關系的表示法1.集合表示法（枚舉法和敘述法）例6.2.7（1）設A={a},B={b,c}，用枚舉法寫出從A到B的不同關系；（2）用敘述法寫出定義在R上的“相等”關系。解（1）A到B的不同關系有：R1=Ф,R2={<a,b>},R3={<a,c>},R4={<a,b>,<a,c>}；（2）設R上的“相等”關系為S，則S={<x,y>|(x,y∈R)∧(x=y)}。2022/11/36.2.3關系的表示法2.關系圖法（1）A≠B設A＝{a1,a2,...,an},B＝{b1,b2,...,bn}，R是從A到B的一個二元關系，則規(guī)定R的關系圖如下：

①.設a1,a2,...,an和b1,b2,...,bn分別為圖中的結(jié)點，用“。”表示；

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

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

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

解

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

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）設R和S的關系矩陣分別為MR和MS，則有

2022/11/3布爾矩陣的運算定義6.2.9

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

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

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

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

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

表6.2.4表6.2.5

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

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

設A={a,b,c,d}，A上關系R和S定義如下：R={<a,b>,<b,d>,<c,c>}，S={<a,c>,<b,d>,<d,b>}。計算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關系的復合運算定義6.3.1設A,B,C是三個集合，R是從A到B的關系(R:A→B)，S是從B到C的關系(S:B→C)，則R與S的復合關系(合成關系)(Composite)RS是從A到C的關系，并且：

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

(y)(y∈B∧xRy∧ySz)}運算“”稱為復合運算(CompositeOperation)。2022/11/36.3.1關系的復合運算1.R和S是可復合的R的后域和S的前域完全相同；2.RoS的前域是R的前域A，后域是S的后域C；3.RoS=Φ對任意的x∈A和z∈C，不存在y∈B，使得xRy和ySz同時成立。4.ΦoR=RoΦ=Φ2022/11/3例6.3.2試判斷下列關系是否是兩個關系的復合，如果是，請指出對應的兩個關系。（1）“祖孫”關系；（2）“舅甥”關系；（3）“兄妹”關系。解（1）“祖孫”關系是“父女”關系和“母子”關系的復合；（2）“舅甥”關系是“兄妹”關系和“母子”關系的復合；（3）不是。2022/11/3例6.3.3設A={a,b,c,d},B={b,c,d},C={a,b,d},R={<a,b>,<c,d>,<b,b>}是A到B的關系，S={<d,b>,<b,d>,<c,a>}是B到C的關系。試用關系的三種表示方法求RS。解（1）RS={<a,d>,<c,b>,<b,d>}；（2）RS的關系圖如圖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設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上的三個關系。計算（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設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上的三個關系。計算（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設A、B、C和D是任意四個集合，R、S和T分別是從A到B，B到C和C到D的二元關系，則（1）(RoS)oT=Ro(SoT)；（2）IAoR=RoIB=R，其中IA和IB分別是A和B上的恒等關系。分析：二元關系是集合，二元關系的復合是關系，從而也是集合，因此上面兩式就是證明兩個集合相等。根據(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.對<a,c>∈RS，同樣至少存一個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)。構造性證明方法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。反過來，任取<a,b>∈R，由IA的定義知，<a,a>∈IA

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

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

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證明：對任意<b,d>∈(S1∩S2)T，則由復合運算知，至少存在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)?！龆ɡ?.3.2

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

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

(S1∩S2)oT例6.3.5分析：如要說明某一事實不一定成立，則可舉一反例加以說明。2022/11/3設A＝{a},B＝{b1,b2},C＝{c},關系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),這說明(RoS1)∩(RoS2)Ro(S1∩S2)不一定成立。例6.3.5解（1）(RoS1)∩(RoS2)Ro(S1∩S2)不一定成立2022/11/3設A＝{a},B＝{b1,b2},C＝{c},關系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，這說明(S1oT)∩(S2oT)(S1∩S2)oT不一定成立。例6.3.5解（2）(S1oT)∩(S2oT)(S1∩S2)oT不一定成立2022/11/3說明如果說明某事實一定成立，則一定加以證明。如要說明某一事實不一定成立，則可舉一反例加以說明。如要說明某事實一定不成立，則也一定加以證明。2022/11/3定義6.3.2設A，B是兩個集合，R是A到B的關系，則從B到A的關系

R-1＝{<b,a>|<a,b>∈R}稱為R的逆關系(InverseRelation),運算“-1”稱為逆運算(InverseOperation)。6.3.2關系的逆運算注意：關系是一種集合，逆關系也是一種集合，因此，如果R是一個關系，則R-1和都是關系，但R-1和是完全不同的兩種關系，千萬不要混淆。(R-1)-1=R；Φ-1=Φ。2022/11/3例6.3.6設A={1,2,3,4},B={a,b,c,d},C={2,3,4,5},R是從A到B的一個關系且R={<1,a>,<2,c>,<3,b>,<4,b>,<4,d>},S是從B到C的一個關系且S={<a,2>,<b,4>,<c,3>,<c,5>,<d,5>}。（1）計算R-1，并畫出R和R-1的關系圖；解：(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的關系圖見圖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）寫出R和R-1的關系矩陣；解：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的關系圖見圖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>}。∵

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>}。設A={1,2,3,4},B={a,b,c,d},C={2,3,4,5},R是從A到B的一個關系且R={<1,a>,<2,c>,<3,b>,<4,b>,<4,d>},S是從B到C的一個關系且S={<a,2>,<b,4>,<c,3>,<c,5>,<d,5>}。求：(3)計算(RoS)-1和S-1oR-1。2022/11/3注意（1）將R的關系圖中有向邊的方向改變成相反方向即得R-1的關系圖，反之亦然；（2）將R的關系矩陣轉(zhuǎn)置即得R-1的關系矩陣，即R和R-1的關系矩陣互為轉(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設A、B和C是任意三個集合，R,S分別是從A到B，B到C的二元關系，則(RoS)-1=S-1oR-1。定理6.3.32022/11/3任取<c,a>∈(RS)-1，則<a,c>∈RS由“”的定義知：則至少存一個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，由“”的定義知：則至少存一個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設R，S是從集合A到集合B的關系，則有(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設R是集合A上的關系，則R的n次冪，記為Rn,定義如下：(1)R0＝IA＝{<a,a>|a∈A}；(2)R1＝Ｒ；(3)Rn+1＝RnR＝RRn。6.3.3關系的冪運算顯然，RmRn

＝

Rm+n,(Rm)n

＝

Rmn。該Rn也是A上的二元關系，2022/11/3例6.3.7設A={1,2,3,4,5,6}，定義在A上的關系R={<1,1>,<1,2>,<2,3>,<3,4>,<4,5>,<5,6>}，S={<1,2>,<2,3>,<3,4>,<4,5>,<5,6>}，計算：(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的增加而增加，而是呈遞減趨勢；（2）當n≥|A|時，則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證明

顯然，

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

——說明冪運算具有周期性定理6.3.5由于，

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

即可。對任意<a,b>∈Rk，則由“”的定義知，存在a1,a2,…,ak-1∈A（為了統(tǒng)一，并假設a0＝a，ak＝b)，使得：<a0,a1>∈R，<a1,a2>∈R，<a2,a3>∈R，…,<ak-1,ak>∈R。構造性證明方法2022/11/3由于|A|＝n，所以由鴿籠原理知：a0,a1,…,ak共k+1個元素中至少有兩個以上元素相同.不妨假設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的任意性知：

，

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

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

。■2022/11/3有R8

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

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

設R是集合A上的關系，（1）如果對x∈A,都有<x,x>∈R，那么稱R在A上是自反的(Reflexive)，或稱R具有自反性(Reflexivity)；例如：同學關系。（2）如果對任意的x∈A，都有<x,x>R，那么稱R在A上是反自反的(Antireflexive)，或稱R具有反自反性(Antireflexivity)。例如：父子關系。2022/11/3符號化：（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設A={1,2,3}，定義A上的關系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>}。判斷這三個關系是否具有自反性或者反自反性。解：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)因為A中x，都有<x,x>∈R，

所以R是自反的；

b）因為A中x，都有<x,x>S，

所以S是反自反的；

c）因為存在2∈A，使<2,2>T，

所以T不是自反的；又因為存在1∈A，使<1,1>∈T，

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

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

關系圖中每個結(jié)點都無自環(huán)；（4）關系R是自反的

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

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

x,y∈A，有<x,y>∈R且<y,x>∈R。2022/11/3例6.4.2設A={1,2,3,4}，定義A上的關系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>}。試判定它們是否具有對稱性和反對稱性，并寫出R,S,T和V的關系矩陣和畫出相應的關系圖。對稱反對稱不是對稱的，也不是反對稱是對稱的，也是反對稱2022/11/3例6.4.2解（1）a）關系R是對稱的；b）關系S是反對稱的；c）在關系T中，有<1,2>，但沒有<2,1>,即S不是對稱的；另外有<1,3>，且有<3,1>，但是1≠3，即S不是反對稱的。

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

b)關系S是傳遞的；

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

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

當R是定義在集合A上的關系時，R是自反、對稱、反對稱和傳遞的；當R是定義在集合B上的關系時，R是對稱、反對稱和傳遞的。注意：絕對不能脫離基集來談論關系的性質(zhì)。2022/11/3定理6.4.1

設R是集合A上的二元關系，則：（1）R是自反的IAR；（2）R是反自反的

R∩IA＝Φ；（3）R是對稱的

R＝R-1；（4）R是反對稱的

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

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

R∩R-1IA（4）

“”

設R是反對稱的。對<a,b>∈R∩R-1,則(<a,b>∈R)∧(<a,b>∈