《離散數(shù)學(xué)》第四章二元關(guān)系歷史人物本章導(dǎo)讀及學(xué)習(xí)要求二元關(guān)系及其表示關(guān)系的運(yùn)算1內(nèi)容導(dǎo)航CONTENTS關(guān)系的性質(zhì)關(guān)系的閉包

4.14.2

4.3

4.4關(guān)系的應(yīng)用

4.5作業(yè)

4.6本章導(dǎo)讀關(guān)系理論歷史悠久，與集合論、數(shù)理邏輯、組合學(xué)、圖論和布爾代數(shù)都有

密切聯(lián)系。關(guān)系是日常生活以及數(shù)學(xué)中的一個(gè)基本概念。例如：父子關(guān)系、兄妹關(guān)系、師生關(guān)系、商品與用戶的關(guān)系等相等關(guān)系、圖形的相似全等關(guān)系、集合的包含關(guān)系等

本章導(dǎo)讀關(guān)系理論被廣泛地應(yīng)用于計(jì)算機(jī)科學(xué)與技術(shù)計(jì)算機(jī)程序的輸入、輸出關(guān)系

以關(guān)系為核心的關(guān)系數(shù)據(jù)庫用于分析編程語言的句法表示信息之間的聯(lián)系以實(shí)現(xiàn)信息檢索關(guān)系理念也是數(shù)據(jù)結(jié)構(gòu)、情報(bào)檢索、數(shù)據(jù)庫、算法分析、計(jì)算機(jī)理論等計(jì)算機(jī)學(xué)科的數(shù)學(xué)工具在某種意義下，關(guān)系可以理解為有聯(lián)系的一些對象相互之間的比較行為。而根據(jù)比較結(jié)果來執(zhí)行不同任務(wù)的能力是計(jì)算機(jī)最重要的屬性之一。重點(diǎn)1二元關(guān)系的概念和表示2關(guān)系的復(fù)合與逆運(yùn)算3關(guān)系性質(zhì)的判定與證明難點(diǎn)1笛卡爾積和二元關(guān)系都是特殊的集合2復(fù)合運(yùn)算的理解與計(jì)算3關(guān)系性質(zhì)的判定與證明

學(xué)習(xí)要求歷史人物本章導(dǎo)讀及學(xué)習(xí)要求二元關(guān)系及其表示關(guān)系的運(yùn)算1內(nèi)容導(dǎo)航CONTENTS關(guān)系的性質(zhì)關(guān)系的閉包

4.14.2

4.3

4.4關(guān)系的應(yīng)用

4.5作業(yè)

4.6德國數(shù)學(xué)家一般拓?fù)涞牡旎?891年，在萊比錫大學(xué)學(xué)習(xí)獲得數(shù)學(xué)博士學(xué)位1895年，在萊比錫大學(xué)擔(dān)任數(shù)學(xué)和天文學(xué)的助理教授1900年，在波恩大學(xué)擔(dān)任副教授1913年，在格賴夫斯瓦爾德大學(xué)擔(dān)任教授1921年，再回波恩大學(xué)擔(dān)任數(shù)學(xué)研究所的所長，并一直在波恩大學(xué)工作。

歷史人物-豪斯多夫豪斯多夫?qū)ΜF(xiàn)代數(shù)學(xué)的形成和發(fā)展起著重要作用：豪斯多夫公理豪斯多夫空間豪斯多夫距離主要著作《集合論基礎(chǔ)》

歷史人物-豪斯多夫英國計(jì)算機(jī)科學(xué)家關(guān)系數(shù)據(jù)庫之父圖靈獎(jiǎng)獲得者1942年-1945年，以空軍機(jī)長身份參加第二次世界大戰(zhàn)1948年，在牛津大學(xué)獲得數(shù)學(xué)學(xué)士和碩士學(xué)位后，成為IBM的一名數(shù)學(xué)程序員1957年，在IBM阿爾馬登研究中心參加了IBM第一臺(tái)科學(xué)計(jì)算機(jī)701及第一臺(tái)大型晶體管計(jì)算機(jī)STRETCH的邏輯設(shè)計(jì)

歷史人物-科德1963年獲得計(jì)算機(jī)與通信專業(yè)碩土學(xué)位1965年獲得計(jì)算機(jī)與通信專業(yè)博土學(xué)位1970年，科德首次提出了數(shù)據(jù)庫的關(guān)系模型

歷史人物-科德主要貢獻(xiàn)1、科德十二定律2、科德cellular機(jī)器人3、數(shù)據(jù)庫正規(guī)化法國哲學(xué)家數(shù)學(xué)家物理學(xué)家1613年，在普依托大學(xué)學(xué)習(xí)法律與醫(yī)學(xué)1618年，在荷蘭入伍，隨軍遠(yuǎn)游1622年開始，用4年時(shí)間游歷歐洲1628年移居荷蘭，開始專心致力于哲學(xué)研究

歷史人物-笛卡爾解析幾何之父幾何圖形是直觀的，而代數(shù)方程是抽象的，能不能把幾何圖形與代數(shù)方程結(jié)合起來？？學(xué)習(xí)要求歷史人物二元關(guān)系及其表示關(guān)系的運(yùn)算1內(nèi)容導(dǎo)航CONTENTS關(guān)系的性質(zhì)關(guān)系的閉包

4.14.2

4.3

4.4關(guān)系的應(yīng)用

4.5作業(yè)

4.6問題引入上，下左，右3<4中國的首都是北京平面上一個(gè)點(diǎn)的橫、縱坐標(biāo)等特征：成對出現(xiàn)且具有一定的順序序偶序偶的定義定義4.1

由兩個(gè)元素x，y按照一定的次序組成的二元組被稱為有序偶對，簡稱序偶(OrderedCouple)，記作<x,y>，其中，稱x為<x,y>的第一元素，y為<x,y>的第二元素。例如：中國的首都是北京

的序偶表示為：李玲是李華的女兒的序偶表示為：<李玲，李華><中國，北京>注意：（1）序偶可以看作是具有兩個(gè)元素的集合。（2）序偶中的兩個(gè)元素具有確定的次序即<a,b>≠<b,a>，但{a,b}={b,a}。序偶相等定義4.2給定序偶<a,b>和<c,d>，<a,b>=<c,d>?

a=c且b=d。例4.1x，y取何值時(shí)，序偶<x+y,4>與<5,2x-y>相等？解根據(jù)定義4.2，有x+y＝52x-y＝4解此二元一次方程組得x=3，y=2。即當(dāng)x=3，y=2時(shí)，序偶<x+y，4>與<5，2x-y>相等。<中國,北京，天安門廣場>給定n重有序組<a1,a2,…,an>和<b1,b2,…,bn>。<a1,a2,…,an>=<b1,b2,…,bn>?ai=bi(i=1,2,…,n)序偶思想的推廣由n個(gè)元素a1,a2,a3,…,an按照一定次序組成的n元組稱為n重有序組(n-TypeVector)，記作：<a1,…,an>例如

中國北京天安門廣場的3重有序組表示為：n重有序組笛卡爾乘積定義4.3設(shè)A，B是兩個(gè)集合，稱集合：A×B＝{<x,y>|x∈A∧y∈B}（4-1）為集合A與B的笛卡爾積(CartesianProduct)。

實(shí)例例4.2設(shè)A＝{a}，B＝P(A)，C=Φ，D={0,1,4}，請分別寫出下列笛卡兒積中的元素。（1）A×B，B×A。（2）A×C，C×A。（3）A×(B×D)，(A×B)×D。解

B=P(A)={Φ，{a}}，根據(jù)式（4-1），有（1）A×B＝{<a，Φ>，<a，{a}>}B×A＝{<Φ，a>，<{a}，a>}（2）A×C=Φ，C×A=Φ交換律不成立實(shí)例（續(xù)）（3）因?yàn)锽×D＝{<Φ，0>，<Φ，1>，<Φ，4>，<{a}，0>，<{a}，1>，<{a}，4>}所以A×(B×D)＝{<a，<Φ，0>>，<a，<Φ，1>>，<a，<Φ，4>>，

<a，<{a}，0>>，<a，<{a}，1>>，<a，<{a}，4>>}同理(A×B)×D＝{<<a，Φ>，0>，<<a，Φ>，1>，<<a，Φ>，4>，

<<a，{a}>，0>，<<a，{a}>，1>，<<a，{a}>，4>}結(jié)合律不成立集合相等

兩個(gè)集合互相包含等式成立

兩個(gè)集合相等定理4.1定理4.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)分析待證等式兩端都是集合于是利用集合與集合關(guān)系的判定與證明方法，直接證明即可。

定理4.1證明

笛卡兒積的定義并運(yùn)算定義分配律并運(yùn)算定義笛卡兒積的定義（2）、（3）和（4）的證明略。定理4.2定理4.2設(shè)A,B,C,D是任意四個(gè)非空集合，則A×B

C×D

A

C，B

D。證明充分性(

)：<x,y><x,y>∈A×B

x∈A∧y∈Bx∈C∧y∈D

A×B

C×DA

C，B

D

<x,y>∈C×D

<x,y>∈A×B<x,y>∈C×D

x∈C∧y∈D

A

C，B

D綜上所述，定理成立。A×B

C×D

笛卡爾積的推廣定義4.4設(shè)A1,A2,…,An是n個(gè)集合，稱A1×A2×…×An={<a1,a2,…,an>|(ai∈Ai)∧i∈{1,2,3,…,n}}（4-2）為集合A1,A2,…,An的笛卡兒積(DescartesProduct)當(dāng)A1=A2=…=An=A時(shí)，有A1×A2×…×An=An。注意：當(dāng)集合A1,A2,…,An都是有限集時(shí)，|A1×A2×…×An|=|A1|×|A2|×…×|An|。問題引入問題：設(shè)A＝{1，4}，B＝{a，b}，R＝{<1，a>，<1，b>，<4，b>}，則R與A×B具有怎樣的關(guān)系呢？因?yàn)锳×B={<1，a>，<4，a>，<1，b>，<4，b>}所以R

A×BR是A×B的子集新名稱：R是A到B的一個(gè)二元關(guān)系定義4.5設(shè)A,B為兩個(gè)非空集合，稱A×B的任何子集R為從A到B的二元關(guān)系，簡稱

關(guān)系(Relation)，記作R：A→B；如A＝B，則稱R為A上的二元關(guān)系，記作R：A→A。二元關(guān)系的定義解題小貼士—給定集合是否為從A到B的一個(gè)關(guān)系的判斷方法（1）計(jì)算A×B；（2）判斷給定集合是否為A×B的子集。若<x,y>∈R，則記為xRy，讀作“x對y有關(guān)系R”；若<x,y>

R，則記為xRy，讀作“x對y沒有關(guān)系R”。例4.3例4.3假設(shè)A＝{1，4}，B＝{a，b}，試判斷下列集合是否為A到B的一個(gè)關(guān)系。（1）S1＝{<3，b>}。（2）S2＝{<1，a>，<4，a>，<1，b>，<4，b>}。解

因?yàn)?/p>

A×B＝{<1，a>，<4，a>，<1，b>，<4，b>}。所以

（1）S1不是A×B的子集，從而S1不是A到B的一個(gè)關(guān)系。

（2）S2是A×B的子集，從而S2是A到B的一個(gè)二元關(guān)系。例4.4例4.4設(shè)A={1,2}，試判斷下列集合是否為A上的關(guān)系。（1）T1＝Φ。（2）T2＝A×A。（3）T3＝{<1，1>，<2，2>}。（4）T4＝{<1，1>，<1，2>}。（5）T5＝{<1，1>，<2，2>，<2，1>，<<1，1>，1>}。解

因?yàn)锳×A={<1，1>，<2，2>，<2，1>，<1，2>}。是，空關(guān)系是，全關(guān)系是，恒等關(guān)系IA＝{<x，x>|x∈A}是不是例4.5設(shè)A＝，B＝{c，d}，試寫出從A到B的所有關(guān)系。解因?yàn)锳×B＝{<b,c>，<b,d>}，所以從A到B的所有關(guān)系為Φ，{<b，c>}，{<b，d>}，{<b，c>，<b，d>}共4個(gè)。例4.5注意當(dāng)集合A,B都是有限集時(shí)，A×B共有2|A|?|B|個(gè)不同的子集，

即從A到B的不同關(guān)系共有2|A|?|B|個(gè)。二元關(guān)系的推廣定義4.6設(shè)A1，A2，…，An為n個(gè)非空集合，則稱A1×A2×…×An的子集R為以A1×A2×…×An為基的n元關(guān)系(n-aryRelation)。姓名性別學(xué)號(hào)專業(yè)張揚(yáng)男4019091601數(shù)字媒體劉麗女4019091604計(jì)算機(jī)科學(xué)李強(qiáng)男4019091603計(jì)算機(jī)科學(xué)王琳女4019091604軟件工程問題引入例4.4設(shè)A={1,2}，試判斷下列集合是否為A上的關(guān)系。（1）T1＝Φ。（2）T2＝A×A。（3）T3＝{<1，1>，<2，2>}。（4）T4＝{<1，1>，<1，2>}。IA＝{<x，x>|x∈A}集合表示法：描述法集合表示法：列舉法關(guān)系圖表示法（1）A≠B設(shè)A＝{a1,a2,…,an}，B＝{b1,b2,…,bm}，R是從A到B的一個(gè)二元關(guān)系，則規(guī)定R的關(guān)系圖如下：

①

設(shè)a1,a2,…,an和b1,b2,…,bm分別為圖中的頂點(diǎn)，用“?！北硎荆?/p>

②如<ai,bj>

R，則ai和bj可用一條ai。。bj的有向邊相連。從A到B的關(guān)系R的關(guān)系圖(RelationGraph)是GR=<V,E>，其中V是頂點(diǎn)集，E是邊集。任意ai∈A，bj∈B，如果<ai，bj>∈R，則在R的關(guān)系圖中就有一條從ai到bj的有向邊。（2）A=B設(shè)A＝B=<a1,a2,…,an>，R是A上的一個(gè)關(guān)系，則R的關(guān)系圖畫法規(guī)定如下：①

設(shè)a1,a2,…,an為圖中頂點(diǎn)，用“?！北硎尽＂谌绻?lt;ai,aj>

R，則從ai到aj可用一條ai。。aj的有向邊相連。③

如果<ai,ai>

R，則ai到ai用一個(gè)帶箭頭的小圓圈表示，即：ai關(guān)系圖表示法（續(xù)）解關(guān)系R和S的關(guān)系圖如右圖所示。李華王珊李想王良王云陳慶李美例4.6試用關(guān)系圖表示下列關(guān)系。例4.6（1）設(shè)A＝{李華,王云,陳慶}，B＝{李美,李想,王良,王珊}，其中李華的兩個(gè)兒子是李美、李想，王云的兩個(gè)兒子是王良、王珊，即父子關(guān)系R={<李華，李美>，<李華，李想>，<王云，王良>，<王云，王珊>}。（2）設(shè)A＝{1，2，3，4}，A上的大于等于關(guān)系S＝{<1，1>,<2，2>,<3，3>,<4，4>,<2，1>,<3，1>,<4，1>,<3，2>,<4，2>,<4，3>}。2341注意（1）對于無邊相連的節(jié)點(diǎn)，不能從關(guān)系圖中刪掉。（2）給定關(guān)系的集合表示法中的序偶與關(guān)系圖表示中的有向邊是一一對應(yīng)的。例4.7試用集合表示法表示右圖中用關(guān)系圖表示的關(guān)系R，并指出R的基。例4.7a1a2a5a3a4a6b3b2b4b5b1DCABR解根據(jù)右圖，R＝{<a3，b1>，<a3，b2>，<a4，b4>，<a6，b4>，<a6，b5>}，A＝{a1，a2，a3，a4，a5，a6}，B＝{b1，b2，b3，b4，b5}，C＝{a3，a4，a6}，D＝{b1，b2，b4，b5}。顯然有R

C×D

A×B，因此，R是以C×D為基的二元關(guān)系，也是以A×B為基的二元關(guān)系。顯然，C＝{x|<x，y>∈R}

A，D＝{y|<x，y>∈R}

B，此時(shí)，A稱為關(guān)系R的前域，B稱為關(guān)系R的后域，C稱為R的定義域(Domain)，記作C＝domR，D稱為R的值域(Range)，記作D＝ranR，fldR＝domR∪ranR稱為R的域(Field)例4.8設(shè)A={1，2，4，8}，R是A上的小于關(guān)系。試寫出R的元素，畫出R的關(guān)系圖，并求出R的定義域、值域和域。例4.8解由題意可得，R={<1,2>,<1,4>,<1,8>,<2,4>,<2,8>,<4,8>}，關(guān)系圖如右圖所示。domR＝{x|<x，y>∈R}={1，2，4}，ranR＝{y|<x，y>∈R}＝{2，4，8}，fldR＝domR∪ranR＝{1，2，4，8}。1428例4.9例4.9設(shè)H={f,m,s,d}表示一個(gè)家庭中父、母、子和女四個(gè)人的集合，確定H上的一個(gè)長幼關(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}設(shè)A＝{a1,a2,…,an}，B＝{b1,b2,…,bm}，R是從A到B的一個(gè)二元關(guān)系，稱矩陣MR＝（mij)n×m為關(guān)系R的關(guān)系矩陣(RelationMatrix)，其中MR又被稱為R的鄰接矩陣(AdjacencyMatrix)。關(guān)系矩陣必須先對集合A,B中的元素排序。A中元素序號(hào)對應(yīng)矩陣元素的行下標(biāo)。B中元素序號(hào)對應(yīng)矩陣元素的列下標(biāo)。關(guān)系矩陣是0-1矩陣，稱為布爾矩陣。

注意布爾矩陣?yán)?.10試用關(guān)系矩陣表示例4.6的關(guān)系。例4.10解設(shè)R，S的關(guān)系矩陣分別為MR，Ms，則有注意

關(guān)系矩陣中1的數(shù)量與對應(yīng)關(guān)系中的序偶數(shù)量是相等的。父子關(guān)系R={<李華，李美>，<李華，李想>，<王云，王良>，<王云，王珊>}。A上的大于等于關(guān)系S＝{<1，1>,<2，2>,<3，3>,<4，4>,<2，1>,<3，1>,<4，1>,<3，2>,<4，2>,<4，3>}。例4.11

例4.11設(shè)A＝{1，2}，考慮P(A)上的包含關(guān)系R和真包含關(guān)系S。（1）試寫出R和S中的所有元素。

（2）試寫出R和S的關(guān)系矩陣。解（1）因?yàn)镻(A)＝{Φ，{1}，{2}，{1，2}}，所以R＝{<Φ，Φ>，<Φ

，{1}>，<Φ

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

例4.11（續(xù)）布爾矩陣的運(yùn)算定義4.7（1）如果A=(aij)和B=(bij)是兩個(gè)m×n階布爾矩陣，則A和B的布爾并(BooleanJoin)也是m×n階矩陣，記作A∨B。若A∨B=C=(cij)，則：（2）如果A=(aij)和B=(bij)是兩個(gè)m×n階矩陣，則A和B的布爾交(BooleanMeet)也是m×n階矩陣，記作A∧B。如果A∧B=D=(dij)，其中：即cij=aij∨bij

即dij=aij∧bij

布爾矩陣的運(yùn)算(續(xù))（3）如果矩陣A=(aij)是m×p階布爾矩陣，B=(bij)是p×n階布爾矩陣，則A和B的布爾積(BooleanProduct)是m×n階布爾矩陣，記作A⊙B，若A⊙B=E=(eij)，則：注意：（1）兩個(gè)布爾矩陣的行數(shù)和列數(shù)分別相同時(shí)才能進(jìn)行布爾并和布爾交。（2）當(dāng)?shù)谝粋€(gè)布爾矩陣的列數(shù)等于第二個(gè)布爾矩陣的行數(shù)時(shí)，它們才能進(jìn)行布爾積。（3）式(4-6)中的“∧”,“∨”分別對應(yīng)“×”,“+”時(shí)，即得普通矩陣乘法計(jì)算公式。例4.12例4.12令、和。計(jì)算（1）A∨B；（2）A∧B；（3）A⊙C。例4.12（續(xù)）解（1）根據(jù)式(4-4)，有（2）根據(jù)式(4-5)，有（3）根據(jù)式(4-6)，有。定理4.3定理4.3假設(shè)A、B和C是n×n階布爾矩陣，則（1）A∨B＝B∨A

(交換律)

A∧B＝B∧A（2）(A∨B)∨C＝A∨(B∨C)

(結(jié)合律)(A∧B)∧C＝A∧(B∧C)(A⊙B)⊙C＝A⊙(B⊙C)（3）A∧(B∨C)＝(A∧B)∨(A∧C)

(分配律)A∨(B∧C)＝(A∨B)∧(A∨C)學(xué)習(xí)要求歷史人物二元關(guān)系及其表示關(guān)系的運(yùn)算1內(nèi)容導(dǎo)航CONTENTS關(guān)系的性質(zhì)關(guān)系的閉包

4.14.2

4.3

4.4關(guān)系的應(yīng)用

4.5作業(yè)

4.6問題引入關(guān)系是一種特殊的集合，（1）關(guān)系可以進(jìn)行集合交、并、差和補(bǔ)等基本運(yùn)算嗎？（2）關(guān)系有自己特有的運(yùn)算嗎？關(guān)系是以序偶為元素的特殊集合，因此所有集合的基本運(yùn)算均適用于關(guān)系。注意：因?yàn)锳×B是相對于R的全集，所以Rc＝A×B-RR∪Rc＝A×BR∩Rc＝Φ

4.2關(guān)系的運(yùn)算

例4.13

例4.13設(shè)A={a,b}，B={1,2}，R={<a,1>,<a,2>}，S={<a,1>,<b,1>,<b,2>}都是A到B上的關(guān)系。試計(jì)算R∪S，R∩S，R-S，S-R，Rc，Sc。

問題引入設(shè)關(guān)系R表示城市之間的直達(dá)航線關(guān)系，S表示城市之間的直達(dá)公路路線關(guān)系。如果<a，b>∈R，<b，c>∈S，那么a和c之間存在怎樣的關(guān)系？又如何表示這樣的關(guān)系？復(fù)合運(yùn)算的定義定義4.8設(shè)A,B,C是三個(gè)集合，R：A→B，S：B→C，則R與S的復(fù)合關(guān)系(合成關(guān)系)(CompositeRalation)是從A到C的關(guān)系，記為R

S，其中

R

S＝{<x,z>|x∈A∧z∈C∧y(y∈B∧<x,y>∈R∧<y,z>∈S)}運(yùn)算“

”稱為復(fù)合運(yùn)算(CompositeOperation)。例4.14設(shè)關(guān)系R表示城市之間的直達(dá)航線關(guān)系，S表示城市之間的直達(dá)公路路線關(guān)系。試描述RoS的意義。解

RoS表示航空路線關(guān)系與公路路線關(guān)系的復(fù)合運(yùn)算。

如果<a，c>∈RoS，那么a與c之間存在一條先從乘飛機(jī)，再乘汽車的可達(dá)路線。解題小貼士—RoS的計(jì)算方法對任意<x,y>∈R，在S中查找所有以y為第一元素的序偶<y,z>，然后將x和z形成新的序偶<x,z>，<x,z>即為RoS的元素。注意

ΦoR＝RoΦ＝Φ。例4.15例4.15設(shè)A＝{1,2,3,4}，R＝{<1,2>,<3,4>}，S＝{<2,4>,<3,4>,<4,2>}，T＝{<1,4>,<2,1>,<4,2>}是A上的三個(gè)關(guān)系。計(jì)算（1）RoS和SoR；（2）(RoS)oT和Ro(SoT)。解（1）RoS＝{<1,2>,<3,4>}{<2,4>,<3,4>,<4,2>}＝{<1,4>,<3,2>}SoR＝{<2,4>,<3,4>,<4,2>}o{<1,2>,<3,4>}=

Φ

復(fù)合運(yùn)算不滿足交換律例4.15（續(xù)）例4.15設(shè)A＝{1,2,3,4}，R＝{<1,2>,<3,4>}，S＝{<2,4>,<3,4>,<4,2>}，T＝{<1,4>,<2,1>,<4,2>}是A上的三個(gè)關(guān)系。計(jì)算（1）RoS和SoR；（2）(RoS)oT和Ro(SoT)。解（2）(RoS)oT＝({<1,2>,<3,4>}o{<2,4>,<3,4>,<4,2>})o{<1,4>,<2,1>,<4,2>}＝{<1,4>,<3,2>}o{<1,4>,<2,1>,<4,2>}＝{<1,2>,<3,1>}Ro(SoT)＝{<1,2>,<3,4>}o({<2,4>,<3,4>,<4,2>}o{<1,4>,<2,1>,<4,2>})＝{<1,2>,<3,4>}o{<2,2>,<3,2>,<4,1>}＝{<1,2>,<3,1>}復(fù)合運(yùn)算滿足結(jié)合律定理4.4定理4.4

設(shè)A、B、C和D是任意四個(gè)集合，R:A→B，S:B→C，T:C→D，則（1）(RoS)oT=Ro(SoT)；（2）IAoR=RoIB=R，其中IA和IB分別稱為A和B上的恒等關(guān)系。集合相等

兩個(gè)集合互相包含等式成立

兩個(gè)集合相等分析待證等式兩端都是集合于是利用集合與集合關(guān)系的判定與證明方法，直接證明即可。

證明?<a,d><a,d>∈(R

S)

T

a∈A∧d∈D∧

c(c∈C∧<a,c>∈R

S∧<c,d>∈T)(“o”的定義)

a∈A∧d∈D∧

c(c∈C∧

b(b∈B∧<a,b>∈R∧<b,c>∈S∧<c,d>∈T)

(“o”的定義)

a∈A∧d∈D∧

c

b(c∈C∧b∈B∧<a,b>∈R∧<b,c>∈S∧<c,d>∈T)

a∈A∧d∈D∧

b(b∈B∧<a,b>∈R∧<b,d>∈SoT)

a∈A∧d∈D∧<a,d>∈Ro(SoT)

<a,d>∈Ro(SoT)即(RoS)oT=Ro(SoT)。證明證明（2）?<a,b>

<a,b>∈IAoR

a∈A∧<a,a>∈IA∧<a,b>∈R

<a,b>∈R即IAoR=R同理可證RoIB=R于是IAoR=RoIB=R得證定理4.4

設(shè)A、B、C和D是任意四個(gè)集合，R:A→B，S:B→C，T:C→D，則（2）IAoR=RoIB=R，其中IA和IB分別稱為A和B上的恒等關(guān)系。例4.16設(shè)A＝{1,2,3}，B＝{1,2}，C＝{2,3}，D＝{4}，R：A→B，S1：B→C，

S2：B→C，T：C→D，且R＝{<2,2>,<2,1>}，S1＝{<1,2>,<2,3>}，

S2＝{<1,3>}，T＝{<2,4>,<3,4>}。試計(jì)算：（1）Ro(S1∪S2)和(RoS1)∪(RoS2)。（2）Ro(S1∩S2)和(RoS1)∩(RoS2)。（3）(S1∪S2)oT和(S1oT)∪(S2oT)。（4）(S1∩S2)oT和(S1oT)∩(S2oT)。例4.16解（1）Ro(S1∪S2)={<2,2>,<2,1>}o({<1,2>,<2,3>}∪{<1,3>})={<2,2>,<2,3>}(RoS1)∪(RoS2)={<2,2>,<2,3>}（2）(S1∪S2)oT=({<1,2>,<2,3>}∪{<1,3>})o{<2,4>,<3,4>}={<1,4>,<2,4>}(S1oT)∪(S2oT)={<1,4>,<2,4>}（3）Ro(S1∩S2)＝{<2,2>,<2,1>}o({<1,2>,<2,3>}∩{<1,3>})=Φ

(RoS1)∩(RoS2)={<2,2>,<2,3>}∩{<2,3>}={<2,3>}（4）(S1∩S2)oT=({<1,2>,<2,3>}∩{<1,3>}){<2,4>,<3,4>}=Φ

(S1oT)∩(S2oT)={<1,4>,<2,4>}∩{<1,4>}={<1,4>}例4.16（續(xù)）“o”對“∪”滿足分配律“o”對“∩”不滿足分配律

定理4.5分析與定理4.4的證明思路類似，可以根據(jù)“集合與集合關(guān)系的判定與證明方法”直接證明即可。此處證明略。問題引入問題假設(shè)A={1,2,3}，A上的關(guān)系

R＝{<1，2>，<2，3>}

S＝{<2，1>，<3，2>}則R和S具有怎樣的關(guān)系？<a,b>∈R

<b,a>∈S稱R和S互為逆關(guān)系已知R，求其逆關(guān)系的運(yùn)算稱為關(guān)系的逆運(yùn)算。定義4.9設(shè)A，B是兩個(gè)集合，R：A→B，則從B到A的關(guān)系

R-1＝{<b,a>|<a,b>∈R}稱為R的逆關(guān)系(InverseRelation)，運(yùn)算“-1”稱為逆運(yùn)算(InverseOperation)。逆運(yùn)算的定義由定義4.9知：(R-1)-1=R；Φ-1=Φ；(A×B)?1＝B×A解題小貼士—關(guān)系R的R?1的計(jì)算方法將R中所有序偶中兩個(gè)元素的位置交換即得R?1。例4.17例4.17設(shè)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）計(jì)算R-1，并畫出R和R-1的關(guān)系圖。（2）寫出R和R-1的關(guān)系矩陣。（3）計(jì)算(RoS)-1和S-1oR-1。例4.17（續(xù)）(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)系圖分別見下面的左圖與右圖。R1234abdcBAR-1abcd1243AB例4.2.7（續(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>}（2）R和R-1的關(guān)系矩陣為：注意將R的關(guān)系圖中有向邊的方向改變成相反方向即得R-1的關(guān)系圖，反之亦然。將R的關(guān)系矩陣轉(zhuǎn)置即得R-1的關(guān)系矩陣，即R和R-1的關(guān)系矩陣互為轉(zhuǎn)置矩陣。R-1的定義域與值域正好是R的值域和定義域，即domR=ranR-1，domR-1=ranR。|R|=|R-1|。(RoS)-1=S-1oR-1。定理4.6定理4.6設(shè)A、B和C是任意三個(gè)集合，R,S分別是從A到B，B到C的二元關(guān)系，則(RoS)-1=S-1oR-1

（4-9）證明?<c,a>，<c,a>∈(RoS)?1

a∈A∧c∈C∧<a,c>∈RoS

a∈A∧c∈C∧

b(b∈B∧<a,b>∈R∧<b,c>∈S)

a∈A∧c∈C∧

b(b∈B∧<b,a>∈R?1∧<c,b>∈S?1)

a∈A∧c∈C∧<c,a>∈S?1oR?1

<c,a>∈S?1oR?1即(RoS)?1＝S?1oR?1。定理4.7設(shè)R：A→B，S：A→B，則有(1)(R∪S)-1＝R-1∪S-1

(分配性)(R∩S)-1＝R-1∩S-1(R-S)-1＝R-1-S-1(2)(RC)?1＝(R?1)C

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

(3)S

R

S-1

R-1

(單調(diào)性)定理4.7設(shè)R：A→A當(dāng)2個(gè)R進(jìn)行復(fù)合運(yùn)算時(shí)，有RoR

當(dāng)3個(gè)R進(jìn)行復(fù)合運(yùn)算時(shí)，有RoRoR以此類推，當(dāng)n個(gè)R進(jìn)行復(fù)合運(yùn)算時(shí)，有問題引入是否有簡便的記法呢？＝R2＝R3＝Rn關(guān)系的冪定義4.10設(shè)R：A→A，則R的n次冪，記為Rn，定義如下：(1)R0＝IA＝{<a,a>|a∈A}；(2)R1＝R；(3)Rn+1＝Rn

R＝R

Rn。關(guān)系冪運(yùn)算的定義且Rm

Rn＝Rm+n，(Rm)n＝Rmn。顯然，Rn:A→A例4.18例4.18設(shè)A={1,2,3,4}，定義在A上的關(guān)系R={<1,1>,<1,2>,<2,3>,<3,4>}，S={<1,2>,<2,3>,<3,4>}，計(jì)算：(1)Rn(n=1,2,3,4,…)，和.

(2)Sn(n=1,2,3,4,…)，和。解（1）R1＝R，R2＝R

R＝{<1,1>,<1,2>,<1,3>,<2,4>}R3＝R2

R＝{<1,1>,<1,2>,<1,3>,<1,4>}R4＝R3

R＝{<1,1>,<1,2>,<1,3>,<1,4>}＝R3

……

Rn＝R3

(n≥3)例4.18（續(xù)）={<1,1>,<1,2>,<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}（2)S1＝S，S2＝S

S＝{<1,3>,<2,4>}S3＝S2

S＝{<1,4>}S4＝S3

S＝Φ

……，Sn＝Φ

(n≥4)例4.18（續(xù)）={<1,2>,<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}因?yàn)?/p>

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

顯然，。下面證：

。定理4.8設(shè)A是有限集合，且|A|＝n，R是A上的關(guān)系，則：定理4.8有Rk即可。對任意<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。由于|A|＝n，所以由鴿籠原理知：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后仍有證明(續(xù)1)<a0,a1>∈R，<a1,a2>∈R，…，<ai-1,ai>∈R，<aj,aj+1>∈R，…，<ak-1,ak>∈R由關(guān)系的復(fù)合運(yùn)算得，<a,b>=<a0,ak>∈Rk’，其中k’＝k-(j-i)，此時(shí)：若k'≤n，則<a,b>

；鴿籠原理：若有n＋1只鴿子住進(jìn)n個(gè)籠子，則有一個(gè)籠子至少住進(jìn)2只鴿子。若k'＞n，則重復(fù)上述做法，最終總能找到k"≤n，使得：<a,b>＝<a0,ak>∈Rk"，所以。即有：<a,b>，由此有Rk。由k的任意性知：

，證明(續(xù)2)有R8即可。設(shè)A={a0,a1,a2,a3,a4,a5}，|A|＝6，R是A上的二元關(guān)系。例取k＝8＞6＝n，

對任意<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。由于|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ù)）：由關(guān)系的復(fù)合運(yùn)算得，<a,b>=<a0,a8>∈R5，其中5＝8-(7-4)，此時(shí)：顯然5＜6，則：<a,b>.學(xué)習(xí)要求歷史人物二元關(guān)系及其表示關(guān)系的運(yùn)算1內(nèi)容導(dǎo)航CONTENTS關(guān)系的性質(zhì)關(guān)系的閉包

4.14.2

4.3

4.4關(guān)系的應(yīng)用

4.5作業(yè)

4.6問題引入本節(jié)涉及到的關(guān)系，如無特別聲明，都是假定其前域和后域相同。即都為定義在集合A上的關(guān)系，且A是非空集合。對于前后域不相同的關(guān)系，其性質(zhì)無法加以定義。R是中國人集合A上的同姓關(guān)系，S是集合P(B)上的包含關(guān)系，這兩個(gè)不同的關(guān)系間有什么聯(lián)系呢？

不同的兩個(gè)關(guān)系，卻具有相同的性質(zhì)1、自反性和反自反性

解題小貼士

R是非空集合A上的關(guān)系，則自反性和反自反性的集合表示判斷方法例4.19例4.19設(shè)A＝{a,b,c}，R1，R2和R3都是A上的關(guān)系，其中R1＝{<a,a>,<a,c>,<b,b>}，R2＝{<a,a>,<b,b>,<c,c>}，R3＝{<a,b>,<b,c>}。試判定它們是否具有自反性和反自反性，并寫出R1，R2和R3的關(guān)系矩陣，畫出相應(yīng)的關(guān)系圖。

例4.19（續(xù)）（2）

設(shè)R1，R2和R3的關(guān)系矩陣分別為MR1，MR2和MR3，則：（3）R1，R2和R3的關(guān)系圖分別是下圖的(a),(b)和(c)。accabcbab

(a)(b)(c)解題小貼士

解題小貼士—自反性和反自反性的關(guān)系圖表示判斷方法(GR是R的關(guān)系圖)，則（1）R是自反的

GR中每個(gè)結(jié)點(diǎn)都有自環(huán)。（2）R是反自反的

GR中每個(gè)結(jié)點(diǎn)都沒有自環(huán)。（3）關(guān)系R既不是自反的，也不是反自反的

GR中同時(shí)存在有自環(huán)的結(jié)點(diǎn)與沒有自環(huán)的結(jié)點(diǎn)。例4.20

2、對稱性和反對稱性

解題小貼士

例4.21例4.21設(shè)A={1,2,3,4}，R、S、T和V都是Ａ上的關(guān)系，其中R={<1,1>,<1,3>,<3,1>}，S={<1,1>,<2,3>,<2,4>}，T={<1,1>,<1,2>,<1,3>,<3,1>}，V={<1,1>,<2,2>,<3,3>,<4,4>}。（1）試判定它們是否具有對稱性和反對稱性。（2）分別寫出R,S,T和V的關(guān)系矩陣。（3）分別畫出R,S,T和V的關(guān)系圖。例4.21（續(xù)）（1）關(guān)系R是對稱的。關(guān)系S是反對稱的。關(guān)系T既不是對稱的，也不是反對稱的。

因?yàn)橛?lt;1,2>，但沒有<2,1>，即T不是對稱的；

另外有<1,3>，且有<3,1>，但是1≠3，即T不是反對稱的。關(guān)系V既是對稱的，也是反對稱的。例4.21（續(xù)）1234

(a)(b)(c)(d)123412341234（2）設(shè)R,S,T和V的關(guān)系矩陣分別為MR,MS,MT和MV，則

(3)R,S,T和Ｖ的關(guān)系圖分別是圖(a),(b),(c)和(d)。例4.21設(shè)A={1,2,3,4}，定義A上的關(guān)系R,S,T和V如下：（1）R={<1,1>,<1,3>,<3,1>}。（2）S={<1,1>,<2,3>,<2,4>}。（3）T={<1,1>,<1,2>,<1,3>,<3,1>}。（4）V={<1,1>,<2,2>,<3,3>,<4,4>}。解題小貼士

解題小貼士—對稱性和反對稱性關(guān)系圖表示判斷方法(GR是R的關(guān)系圖)，則（1）R是對稱的

GR中任何一對結(jié)點(diǎn)之間，要么有方向相反的兩條邊，要么無

任何邊。（2）R是反對稱的

GR中任何一對結(jié)點(diǎn)之間，至多有一條邊。3、傳遞性定義4.13設(shè)R是非空集合A上的關(guān)系。如果

x

y

z(x∈A∧y∈A∧z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R)=1，則稱關(guān)系R是傳遞的(Transitive)，或稱R具有傳遞性(Transitivity)。例如：同姓關(guān)系是傳遞的，父子關(guān)系不是傳遞的。

例4.22例4.22設(shè)A={1,2,3}，R、S、T和V都是Ａ上的關(guān)系，其中，R={<1,1>,<1,2>,<1,3>,<2,3>}，S={<1,2>}，T={<1,1>,<1,2>,<2,3>}，V={<1,2>,<2,3>,<1,3>,<2,1>}。（1）試判定它們是否具有傳遞性。（2）分別寫出R，S，T和V的關(guān)系矩陣。（3）分別畫出R，S，T和V的關(guān)系圖。

例4.22解（2）設(shè)R,S,T和V的關(guān)系矩陣分別為MR,MS,MT和MV，則（3）R,S,T和Ｖ的關(guān)系圖分別是圖(a),(b),(c)和(d)。例4.22解（續(xù)）123(a)123123123(b)(c)(d)解題小貼士

解題小貼士—傳遞性的關(guān)系圖表示判斷方法(GR是R的關(guān)系圖)，則R是傳遞的

GR中任何兩個(gè)不同結(jié)點(diǎn)x，y之間，如果存在x到y(tǒng)的一條路徑，則一定有x到y(tǒng)的一條邊?？偨Y(jié)自反性反自反性對稱性反對稱性傳遞性定

義x(x∈A→<x,x>∈R)=1

x

y

z(x∈A∧y∈A∧z∈A∧(<x,y>∈R∧<y,z>∈R→<x,z>∈R))=1關(guān)

系

圖每個(gè)結(jié)點(diǎn)都有環(huán)每個(gè)結(jié)點(diǎn)都無環(huán)每對結(jié)點(diǎn)間或有方向相反的兩條邊，或無任何邊每對結(jié)點(diǎn)間至多有一條邊存在任三個(gè)結(jié)點(diǎn)x,y,z，若從x到y(tǒng)有邊，從y到z有邊，則從x到z一定有邊關(guān)系

矩陣rii=1rii=0rij=rjirij?

rji=0,i≠j如rij＝1且rjk＝1則rik＝1按定義判定法關(guān)系圖判定法關(guān)系矩陣判定法例4.23例4.23設(shè)A＝{1,2,3}，A上的關(guān)系R和S的關(guān)系矩陣為MR和MS，關(guān)系T和V的關(guān)系圖如下圖(a)和(b)。試判定它們所具有的特殊性質(zhì)。

22(a)(b)1313R是自反的、對稱的和傳遞的S是反自反的、對稱的、反對稱的和傳遞的T是反對稱的和傳遞的V是自反的、對稱的、反對稱和傳遞的例4.24例4.24判定下列關(guān)系所具有的特殊性質(zhì)。（1）集合A上的全關(guān)系。（2）集合A上的空關(guān)系。（3）集合A上的恒等關(guān)系。解(1)集合A上的全關(guān)系具有自反性，對稱性和傳遞性。(2)集合A上的空關(guān)系具有反自反性、對稱性、反對稱性和傳遞性。(3)集合A上的恒等關(guān)系具有自反性、對稱性、反對稱性和傳遞性。

例4.25例4.26例4.26設(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是自反、對稱、反對稱和傳遞的。當(dāng)R是定義在集合B上的關(guān)系時(shí)，R是對稱、反對稱和傳遞的。注意：絕對不能脫離基集（即定義關(guān)系的集合）來談?wù)撽P(guān)系的性質(zhì)。問題引入對例4.24中的關(guān)系（1）集合A上的全關(guān)系；（2）集合A上的空關(guān)系；（3）集合A上的恒等關(guān)系。除了實(shí)例化的方法外，可以直接證明嗎？可用關(guān)系性質(zhì)的定義直接證明解題小貼士—關(guān)系性質(zhì)的定義證明方法

例4.27例4.27設(shè)R集合A上的恒等關(guān)系，證明R具有自反性、對稱性、反對稱性和傳遞性。

關(guān)系性質(zhì)的定義證明方法框架待證性質(zhì)第一步中間過程最后一步R是自反的結(jié)合已知和已有定義、定理<x,x>∈RR是反自反的R是對稱的<y,x>∈RR是反對稱的x=yR是傳遞的<x,z>∈R定理4.9

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

IA

R；（2）R是反自反的

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

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

R∩R-1

IA；（5）R是傳遞的

R

R

R。定理4.9證明（2）必要性(反證法)“

”假設(shè)R∩IA≠Φ，則存在<a,b>∈R∩IA，則<a,b>∈IA。

由IA的定義可知，a=b，即<a,a>∈R，與R是反自反的矛盾。從而R∩IA＝Φ。證明（4）

證明（5）

問題引入給定集合A上的關(guān)系R和S，如果R，S都是反自反的，那么R-S還是反自反的嗎？RoS呢？關(guān)系性質(zhì)的保守性問題：是指具有某種性質(zhì)的兩個(gè)關(guān)系經(jīng)過運(yùn)算后，運(yùn)算結(jié)果是否仍具有該性質(zhì)的問題。例如設(shè)A＝{1,2,3}，R＝{<1,3>,<2,3>}，S＝{<2,3>,<3,1>}是A上的關(guān)系。顯然R，S都是反自反的。R-S＝{<1,3>}仍然是反自反的；RoS＝{<1,1>,<2,1>}不是反自反的。定理4.10設(shè)R,S是定義在A上的二元關(guān)系，則：(1)若R,S是自反的，則R-1,R∪S,R∩S,R

S也是自反的。(2)若R,S是反自反的，則R-1,R∪S,R∩S也是反自反的。(3)若R,S是對稱的，則R-1,R∪S,R∩S也是對稱的。(4)若R,S是反對稱的，則R-1,R∩S也是反對稱的。(5)若R,S是傳遞的，則R-1,R∩S也是傳遞的。4.3.3關(guān)系性質(zhì)的保守性注意：（1）逆運(yùn)算與交運(yùn)算具有較好的保守性；（2）并運(yùn)算、差運(yùn)算和復(fù)合運(yùn)算的保守性較差。構(gòu)造反例的思路正向思維：構(gòu)造集合A構(gòu)造滿足條件的R和S計(jì)算RoS和R∪S，并確定其特殊性質(zhì)是否滿足要求結(jié)束逆向思維：構(gòu)造滿足條件的RoS和R∪S構(gòu)造與R和S對應(yīng)的最簡單的集合A構(gòu)造計(jì)算結(jié)果與RoS和R∪S一致的R和S，并驗(yàn)證其特殊性質(zhì)檢查修正YN解題小貼士解題小貼士—反例法說明R，S經(jīng)過運(yùn)算后不一定具有原特殊性質(zhì)的思路（1）構(gòu)造R，S的運(yùn)算結(jié)果，如RoS，使其不具有原特殊性質(zhì)；（2）構(gòu)造最簡單的R，S的基集A，使（1）成立；（3）根據(jù)已知條件和運(yùn)算規(guī)則，構(gòu)造A上的R和S，并計(jì)算RoS，如果與（1）一致，則構(gòu)造成功，結(jié)束；否則，返回（1）。例4.28例4.28試舉例說明下列事實(shí)不一定成立。（1）R和S是反自反、反對稱和傳遞的，但是，RoS不一定具備反自反性，反對稱性；R∪S不一定具有反對稱性和傳遞性；（2）R和S是自反、對稱和傳遞的，但是RoS不一定是對稱和傳遞的，R-S不一定是自反和傳遞的。分析

（1）對不一定成立的事實(shí)，可采用反例法。按照“反例法說明R，S經(jīng)過運(yùn)算后不一定具有原特殊性質(zhì)的思路”。例4.28分析（逆向思維）①假設(shè)RoS={<1，1>，<1，2>，<2，1>}，顯然RoS不是反自反和反對稱的；②構(gòu)造使①成立的最簡單的集合A={1，2}；③因?yàn)镽和S是反自反、反對稱和傳遞的以及RoS的結(jié)果已知，所以可構(gòu)造R＝{<1，a>，<2，b>}，S＝{<a，2>，<b，1>}且a，b不能為1或者2。下面確定a和b的值。若a≠b，則RoS={<1,2>,<2,1>}是反自反的，不符合要求；若a=b，則RoS={<1,1>,<2,2>,<1,2>,<2,1>}不是反自反和反對稱的，符合要求，但與原有的RoS不一致，返回①；例4.28分析（續(xù)）①′更新RoS={<1,1>,<2,2>,<1,2>,<2,1>}；②′因?yàn)閍=b，但不能為1或者2，所以在集合A中增加一個(gè)元素，例如3，于是集合A更新為{1,2,3}；③′R＝{<1,3>,<2,3>}，S＝{<3,2>,<3,1>}是反自反、反對稱和傳遞的，且RoS={<1,1>,<2,2>,<1,2>,<2,1>}不是反自反和反對稱的。綜上所述，得到滿足條件的集合A和A上的關(guān)系R和S。類似構(gòu)造R和S，使得R∪S滿足要求。例4.28解解（1）設(shè)A={1,2,3},R＝{<1,3>,<2,3>}，S＝{<3,2>,<3,1>}是定義在A上的兩個(gè)關(guān)系。顯然R,S都是反自反的、反對稱的、傳遞的。此時(shí)RoS＝{<1,1>,<1,2>,<2,2>,<2,1>}不具備反自反性和反對稱性；R∪S＝{<3,2>,<3,1>,<1,3>,<2,3>}不具備傳遞性和反對稱性。例4.28解（續(xù)）解（2）設(shè)A＝{1,2,3}，R＝{<1,1>,<2,2>,<3,3>,<1,2>,<2,1>}，S＝{<1,1>,<2,2>,<3,3>,<3,2>,<2,3>}是A上的兩個(gè)關(guān)系。顯然R，S都是自反、對稱和傳遞的。此時(shí)RoS＝{<1,1>,<2,2>,<3,3>,<2,3>,<3,2>,<1,2>,<2,1>,<1,3>}不具備對稱性和傳遞性；R?S＝{<1,2>,<2,1>}不具備自反性和傳遞性。學(xué)習(xí)要求歷史人物二元關(guān)系及其表示關(guān)系的運(yùn)算1內(nèi)容導(dǎo)航CONTENTS關(guān)系的性質(zhì)關(guān)系的閉包

4.14.2

4.3

4.4關(guān)系的應(yīng)用

4.5作業(yè)

4.6問題引入

對于一個(gè)給定的關(guān)系，可能不具有某一個(gè)特殊性質(zhì)。但是，如果我們希望它具有該特定的性質(zhì)，那么應(yīng)該怎么做呢？例如，對給定集合A={1,2,3}上的關(guān)系R={<1,1>,<1,2>,<2,1>}，它不具有自反性。根據(jù)自反性的定義，在關(guān)系R中添加<2,2>，<3,3>或者添加<2,2>，<3,3>，<1,3>或者………得到的R’就具有自反性。關(guān)系的閉包定義4.14設(shè)R是定義在A上的關(guān)系，若存在A上的另一個(gè)關(guān)系R′使得R

R′且滿足：（1）R′是自反的(對稱的、或傳遞的)；（2）對任何自反的(對稱的、或傳遞的)關(guān)系R〞，如果R

R〞，就有R′

R〞。則稱R′為R的自反閉包(ReflexiveClosure)(對稱閉包(SymmetricClosure)、或傳遞閉包(TransitiveClosure))，分別記為r(R)(s(R)或t(R))。關(guān)系閉包的定義解題小貼士—關(guān)系R的自反/對稱/傳遞閉包的計(jì)算方法首先判斷R是否具有自反/對稱/傳遞性，①若有，則r(R)/s(R)/t(R)=R；②若無，則在R中添加最少的元素，使其具有自反/對稱/傳遞性，添加后的結(jié)果即為r(R)/s(R)/t(R)。例4.29例4.29設(shè)A={1,2}，R={<1,1>,<1,2>}是A上的關(guān)系。試判斷下列關(guān)系是否是Ｒ的自反閉包、對稱閉包和傳遞閉包。（1）R1＝{<1,1>,<2,2>,<1,2>}（2）R2＝{<1,1>,<2,2>,<1,2>,<2,1>}（3）R3＝{<1,1>,<1,2>,<2,1>}（4）R4＝{<1,1>,<1,2>}由定義4.14知r(R)＝{<1,1>,<2,2>,<1,2>}s(R)＝{<1,1>,<1,2>,<2,1>}t(R)=RR是傳遞的，不是自反和對稱的R1=r(R)，R1≠s(R)，R1≠t(R)R2≠r(R)，R2≠s(R)，R2≠t(R)R3≠r(R)，R3=s(R)，R3≠t(R)R4≠r(R)，R4≠s(R)，R4=t(R)例4.30例4.30設(shè)集合A={a,b,c,d}，R={<a,b>,<b,a>,<b,c>,<c,d>}是定義在A上的二元關(guān)系。（1）畫出R的關(guān)系圖；（2）求出r(R),s(R),t(R),并畫出其相應(yīng)的關(guān)系圖。解（1）R的關(guān)系圖見下圖；（2）r(R)＝{<a,b>,<b,a>,<b,c>,<c,d>,<a,a>,<b,b>,<c,c>,<d,d>}，其關(guān)系

圖如圖(b)所示；

s(R)＝{<a,b>,<b,a>,<b,c>,<c,d>,<c,b>,<d,c>}，其關(guān)系圖如圖(c)所示；

t(R)＝{<a,b>,<b,a>,<b,c>,<c,d>,<a,a>,<b,b>,<a,c>,<a,d>,<b,d>}，

其關(guān)系圖如圖(ｄ)所示。例4.30（續(xù)）解題小貼士解題小貼士—利用R的關(guān)系圖GR求關(guān)系自反/對稱/傳遞閉包的方法（1）在GR中沒有自環(huán)的結(jié)點(diǎn)處加上自環(huán)，可得r(R)的關(guān)系圖；（2）在GR中將每條單向邊改成雙向邊，可得s(R)的關(guān)系圖；（3）在GR中從每個(gè)結(jié)點(diǎn)出發(fā)，找到任意一條長度為2的路徑的終點(diǎn)，如果該結(jié)點(diǎn)到其終點(diǎn)沒有邊相連，就加上此邊，