離散數(shù)學課件第三章集合與關系

1、3-7 復合關系和逆關系,二元關系是以序偶為元素的集合，所以可以對它進行集合運算。 此外還有一種新的運算：關系的復合 定義3-7.1 設R是從集合A到集合B上的二元關系，S是從集合B到集合C上的二元關系，則RS稱為R和S的復合關系，表示為 RS= xAzC y(yBRS),復合關系舉例,例：A=1，2，3，4，B=3，5，7，C=1，2，3 R=，S=， 則 RS=， 如圖所示,復合關系的結(jié)合律,定理：設R1 A1 A2, R2 A2 A3, R3 A3 A4, 則 (R1R2)R3 = R1(R2R3,例：設A=1,2,3,4,5 A上的二元關系R=, S=, 則 RS=, SR=, RS

2、(RS)R= R(SR),復合關系的矩陣表示（自學,兩個關系的復合可通過相應矩陣相乘獲得,復合關系練習,練習：R是A上的二元關系，試證R是傳遞的充要條件是RRR,證： ：RR 必y使得 R，R R是傳遞的 R RRR ：R, R 必有R R R RR R 由x,y,z任意性知 xyz(RRR) R是傳遞的,逆關系,定義3-7.2 設R是A到B的二元關系，則R的逆是B到A的二元關系，記為Rc，其中Rc =|R。 注 ：（1）xRyyRcx （2）互換R的關系矩陣的行和列，即得Rc的關系矩陣。 即 MRcMRT （3）顛倒R的關系圖中每條弧線的箭頭方向，即得Rc的關系圖,逆關系舉例,例1 整數(shù)集上

3、的 關系 集合族上的 關系的逆是 空關系的逆是空關系 AB的全域關系的逆是BA的全域關系 例2 A=0,1,2,3，R=, 則 Rc = ,定理,定理：設R,R2,R1是A到B的關系，則 a） (Rc)c=R b） (R1R2)c = R1cR2c c） (R1R2)c = R1cR2 d） (R)c = (Rc), R=AB-R 即R的補的逆等于逆的補 e） (R1-R2)c =R1c -R2c f) (AB)c = BA,定理,定理3-7.2 設R、S分別是A到B、B到C的關系， 則(RS)c=Sc Rc,證：設 是(RS)c 的任一元素， 則 (RS)c RS b(RS) b(c,bSc

4、Rc) Sc Rc,定理,定理3-7.3 R是A上的二元關系 (a) R是對稱的 R=Rc (b) R是反對稱的 RRcIA,證：(a)：任取R，因為R是對稱的， 所以RRR c ：任取R ， 則Rc R=Rc R R是對稱的 (b)略,3-8 關系的閉包運算,設R是A上的關系，我們希望R具有某些有用的性質(zhì)，比如說自反性。如果R不具有自反性，我們通過在R中添加一部分有序?qū)砀脑霷，得到新的關系R，使得R具有自反性。但又不希望R與R相差太多，換句話說，添加的有序?qū)σM可能的少。滿足這些要求的R就稱為R的自反閉包。通過添加有序?qū)順?gòu)造的閉包除自反閉包外還有對稱閉包和傳遞閉包,各種閉包的定義,定義3

5、-8.1 設R是非空集合A上的關系，R的自反（對稱或傳遞）閉包是A上的關系R，使得R滿足以下條件：（1）R是自反的（對稱的或傳遞的）（2）R R （3）對A上任何包含R的自反（對稱或傳遞）關系R”，有 R R”。 一般將R的自反閉包記作r(R)，對稱閉包記作s(R)，傳遞閉包記作t(R,注： R的自反閉包記為r(R),若R是自反的，則R=r(R),反之也成立。 R的對稱閉包記為s(R),若R是對稱的，則R=s(R),反之也成立。 R的傳遞閉包記為t(R),若R是傳遞的，則R=t(R),反之也成立,構(gòu)造閉包的方法,下面的定理給出了構(gòu)造閉包的方法： 自反閉包 r(R)=RIA 對稱閉包 s(R)=

6、RRc 傳遞閉包 t(R)= = RR2R3,證明 r(R)=RIA,證：設R = RIA xA,R R具有自反性 RR 設R”是自反的，且RR” R是自反的，IAR” 又RR” R=IARR” 綜上所述，R滿足自反閉包定義的三個條件， r(R)= R= RIA,證明 s(R)=RRc,證明：設 R= RRc Rc=(RRc)c=Rc(Rc)c= RcR=R ， 所以R是對稱的 R=RRcR 設R”是對稱的，且RR” ，要證 RR” 任取RRcRRc R”R R”R” R”R” R” R=RRcR” 綜上所述，由定義知道，R即RRc為R的對稱閉包,證 t(R)= = RR2R3(R為A上的二元

7、關系,證：(1)證 t(R)： 先用歸納法證，對n0, Rn t(R) a)由定義 R t(R) b)設Rn t(R)成立，要證Rn+1 t(R) 任取Rn+1=RnR， 存在cA,使Rn,R 由歸納假設和基礎步驟知 t(R) ，t(R） t(R)是傳遞的， t(R) 即 Rn+1 t(R) 對一切n， Rn t(R,根據(jù)的結(jié)論，證 t(R)： 任取 存在一個n，使Rn t(R) t(R) t(R,2) 證 t(R) 設,是 的任意元素 必s,t,使得Rs,Rt RtRs = Rt+s 是傳遞的 t(R)是包含R的最小傳遞關系 t(R) 由（1），（2）得 t(R),閉包運算舉例,題：設A=a

8、,b,c, R是A上的二元關系，且給定R=, 求r(R),s(R),t(R)。 解：r(R)= R IA = , s(R)= R Rc = , t(R)=RR2R3 = RR2R3 （因為R4=R,R5=R2,R6=R3,) = , ,定理3-8.5 設R為X上二元關系，X=n，那么，存在一個正整數(shù)kn，使得 t()= R R2 R3 . Rk 例：P123例題2,求R+的算法Warshall算法,例：P124例題3,P125例題4,設有一字母表V=A,B,C,D,e,d,f并給定下面六條規(guī)則： A-Af, B-Dde, C-e, A-B, B-De, D-Bf R為定義在V上的二元關系且xi

9、Rxj，即是從xi出發(fā)用一條規(guī)則推出一串字符，使其第一個字符恰為xj 。說明每個字母連續(xù)應用上述規(guī)則可能推出的頭字符,閉包運算的性質(zhì),設R為集合X上的任一二元關系，那么 a)rs(R)=sr(R) 自反對稱閉包等于對稱自反閉包 b)tr(R)=rt(R) 傳遞自反閉包等于自反傳遞閉包 c)ts(R)st(R) 傳遞對稱閉包包含對稱傳遞閉包,證明 rs(R)=sr(R,證： rs(R)= r(s(R) = r(RRc) = IxRRc = IxRRcIx = (IxR)(RcIxc) = (IxR)(RIx)c = s(IxR) = sr(R,證明 rt(R)=tr(R,證：rt(R) = r(

10、RR2) = IXRR2 tr(R) = t( RIX) = IXR(IXR)2(IXR)n = IXRR2Rn rt(R)=tr(R,注：以上證明引用了公式：（證明略） ( RIX)n = IXRR2Rn,證明st(R) ts(R,證： 先證R對稱t( R )對稱 t( R )-1 = (RR2R3)-1 = R-1(R2)-1(R3)-1 = R-1(R-1)2(R-1)3 (FG)-1=G-1F-1，定理3-7.2 ) = R R2 R3 = t( R ) t( R )對稱. 因為 R s(R),故 st( R ) st(s( R ) 而st(s( R )= sts(R) = s(ts(

11、 R ) = ts( R ) st( R ) ts( R,注： st(R)ts(R)未必成立。 反例：設R= , 則s(R)= , t(s(R)= , , s(t(R)= s , = , t(s(R,注意：先做傳遞，再做對稱，有可能破壞傳遞性,3-9 集合的劃分和覆蓋,除了把兩個集合相互比較外，還常把一個集合分成若干子集討論。 定義3-9.1 設A為非空集，S=S1Sm,SiA，Si (i=1m)且S1S2.Sm=A，稱S是A的覆蓋. 若再加SiSj= (i,j=1m,ij)則稱S是A的劃分,m稱為劃分的秩,集合的劃分和覆蓋舉例,例1 設A=1,2,3,4,5，下面哪些是覆蓋，哪些是劃分： (

12、1) X = 1,2,3,4,5 (2) Y = 1,2,2,3,4,5 (3) Z = 1,2,3,4 (4) U = 1,2,3,4,5 (5) V = 1,2,3,4,5 U稱為A的最小劃分，V稱為A的最大劃分,交叉劃分,定義3-9.2 若S1=A1Am,S2=B1Bn是A的二個劃分,則 S=AiBj|AiS1BjS2 稱為A的交叉劃分。 定理3-9.1 設 A1,A2,Am與B1,B2,Bn為同一集合A的兩個劃分。則其交叉劃分AiBj亦是原集合的一種劃分,交叉劃分舉例,例：設B是所有生物的集合, 可劃分成A, P,其中A表示所有動物Animal的集合, P表示所有植物Plant的集合。

13、 B也可劃分成 F, L,其中F表示史前First生物,L表示史后Last生物。 它們的交叉劃分為 : D = AF, AL, PF, PL, 其中AF是史前動物, AL是史后動物, PF是史前植物, PL是史后植物,加細,定義3-9.3 設S,S是集合A的二個劃分，若S的每一塊均是S中某塊的子集，S是S的加細。 例:A=正整數(shù)集 S=1,3,5,7,2,4,6 S=1,5,9,3,7，11,2,4,6 則 S是S的細分 定理3-9.2 任何兩種劃分的交叉劃分，都是原來各劃分的一種加細,練習： 3-9（2,證明： 1. aA，a與a在同一分塊中，故必有aRa。故R是自反的。 2. 若a與b在同

14、一分塊中，b與a也必在同一分塊中，即 aRb bRa，故R是對稱的。 3. 若a與b在同一分塊中，b與c在同一分塊中， 根據(jù)劃分的定義，b屬于且僅屬于一個分塊，故a與c必在同一分塊中。 即 aRb bRc aRc，故R是傳遞的,3-10 等價關系與等價類,等價關系是一類重要的二元關系。定義3-10.1 若集合A上的二元關系R是自反的，對稱的和傳遞的，稱R是等價關系。若R是等價關系，aRb，可讀為“a等價于b”。 例如， 數(shù)中的相等關系，是等價關系 集合中的相等關系，是等價關系 命題演算中關系，是等價關系 全域關系是等價關系，空集上任何關系是等價關系,等價關系舉例,例： 設A=1,2,8，如下定

15、義A上的關系R：R=|x，yAxy(mod 3)其中xy(mod 3)叫做模3同余，即x除以3的余數(shù)與y除以3的余數(shù)相等。不難驗證R為A上的等價關系，因為 xA，有xx(mod 3)， x，yA，若xy(mod 3)，則有yx(mod 3)， x，y，zA，若xy(mod 3)，yz(mod 3)，則有xz(mod 3)。該關系的關系圖如下,等價關系舉例（續(xù),不難看出，上述關系圖被分為三個互不相連通的部分。每部分中的數(shù)兩兩都有關系，不同部分中的數(shù)則沒有關系。每一部分中的所有的頂點構(gòu)成一個等價類,等價類,定義3-10.2 設R是A上的等價關系，對aA，集合aR=x|xRa稱為a關于R的等價類，簡

16、記為a， a 稱為等價類aR的表示元素。 從以上定義可以知道，a的等價類是A中所有與a等價的元素構(gòu)成的集合。上例中的等價類是：1=4=7=1,4,72=5=8=2,5,83=6=3,6,例：設I是整數(shù)集，R是模3同余關系， 即R=|xIyIxy(mod3) 不難驗證R是等價關系，其等價類為 0R = -6,-3,0,3,6 1R = -2,1,4 2R = -4,-1,2,5 等價類的每一元素均可作本等價類的表示元素,定理3-10.1 設給定集合A上的等價關系R， 對于a,b A 有 aRb iff aR=bR 證： aaR=bR 根據(jù)等價類定義 aRb aRb xaR xRa xRb xbR

17、 由x的任意性知，aR=bR,商集,定義3-10.3 集合A上的等價關系R，其等價類集合aR|a A，稱為A關于R的商集，記為A/R。 例1： A=1,2,8， R= |x，yAxy(mod 3) 則A/R= 1,4,7,2,5,8,3,6 例2： A為正整數(shù)集合，R是模3同余關系， 則A/R= 0R,1R,2R ， 其中 0R = -6,-3,0,3,6 1R = -2,1,4 2R = -4,-1,2,5,顯然： 商集是集合的集合。 商集的每個元素是等價關系的一個等價類。 等價類中的每個元素都是集合A上的元素。 同一等價類中的任意兩個元素都具有關系R,商集舉例,例：設集合S = a, b,

18、 c, d, e, f, g，S上的等價關系R如下表所示，求商集S/R,S/R = a, b, c, d, e, f, g,思考：R=,根據(jù)等價類對集合進行劃分,定理3-10.2 集合A上的等價關系R決定了A的一個劃分，即為商集A/R,證明 A/R= aR|aA （1）根據(jù)等價類定義，aA，aR A aR A aA，aRa aaR A aR aR=A A/R是一個覆蓋,根據(jù)等價類對集合進行劃分,2）證：需證 a,bA， 若aRbR ， 則 aRbR= 。 反證法：若aRbR 則caRbR cRa 且 cRb R是對稱、傳遞的 aRb 則 aR=bR ，這與前提矛盾。 由（1），（2） 得A/R

19、是一個劃分,定理3-10.3 集合A的任一劃分S確定了A的一個等價關系R,證明 設S=S1，S2，Sm（構(gòu)造性證明） 定義關系R: aRb當且僅當a,b在S的同一塊中， 現(xiàn)證R是等價關系。 (1) aA， a與a在同一塊中 aRa，自反性成立。 (2) a,bA ，若aRb，則a與b在同一塊中，則b與a也在同一塊 bRa，即 aRbbRa 對稱性成立,3) a,b,cA，若aRb， bRc，則a與b在同一塊，b與c在同一塊 SiSj= (ij) a與c在同一塊，即aRbbRcaRc 傳遞性成立 綜上所述，R是A的一個等價關系，且A/R=S,定理3-10.3舉例,例： A=a,b,c,d,e，S

20、= a,b,c,d,e ，求由S確定的等價關系。 解：設 R1=a,ba,b= , R2=cc= R3=d,ed,e= , 則 R=R1R2R3是由S確定的等價關系。 若S=a,b,c,d,e，則由S確定的等價關系是什么,定理3-10.4 設R1，R2是非空集合A上的等價關系，則R1=R2 A/R1=A/R2,證明 ：若R1=R2 A/R1=aR1|aA，A/R2=aR2|aA 則 xaR1 R1 R2 xaR2 ， aR1 aR2 同理可證， aR2 aR1 aR1 = aR2 A/R1 = A/R2,aA， aR1 A/R1 A/R1= A/R2 必 cR2A/R2，使 aR1 =cR2

21、a,bA R1 aaR1baR1 acR2bcR2 R2 R1 R2 同理可證：R2R1 R1 = R2 綜上所述，R1=R2 A/R1=A/R2,例：設和是非空集A的劃分,R、R是分別由、確定的等價關系，試證 細分 R R,證：R 則a、b在的同一塊中， 細分 a、b在的同一塊 R R R ：設 Si aSi， 則 Si=aR=x|xRa xSi xRaxRaxaR aRaR 由 Si的任意性，知 細分 細分 R R,加細（細分）圖解,3-11 相容關系,定義3-11.1 設R是集合A上的二元關系，若R是自反的和對稱的，稱R是相容關系。 例：所有等價關系是相容關系； 在一群人的集合中, 朋友

22、關系也是相容關系,相容關系的表示方法,因為相容關系是自反和對稱的, 其關系矩陣是對稱的且主對角線元素全為1, 因此我們可僅用下三角矩陣T來表示和存儲就夠了, 即關系矩陣可以簡化為“階梯形”。 相容關系的關系圖可簡記為： 用無向邊代替二有向邊 自回路省略,相容關系的表示方法(P135例題,x1,x6,x4,x3,x2,x5,相容關系r的矩陣及圖形表示,定義3-11.2 設R是集合A上的相容關系, 若CA, 若任意a,bC, 有aRb, 則稱C是由R產(chǎn)生的相容類。 例：上例相容關系r產(chǎn)生的相容類,最大相容類,定義3-11.3 設R為定義在集合A上的相容關系，如果不能真包含在任何其他相容類中的相容類

23、，稱作最大相容類，記為CR。 例：P137例題1,相容關系的確定,利用相容關系的關系圖來確定相容類和最大相容類是方便的。 極大完全子圖的頂點集合就是最大相容類。 所謂極大完全子圖是指每對頂點都有邊相連的多邊形,而最大相容類外的任何頂點不可能與類內(nèi)的所有頂點相連。 另外孤立頂點, 以及不在極大完全子圖兩個頂點及其連線, 也是最大相容類,例 設給定的相容關系圖表示成下圖, 寫出所有的最大相容類,解 最大相容類：h, a, b, d, e, f, b, c, d, f, g,完全覆蓋,定義3-11.4 設R為定義在集合A上的相容關系，其最大相容類的集合稱作集合A的完全覆蓋，記為CR(A)。 例1,A

24、的完全覆蓋是： 1，2，3，4，5，6，5，2，6，3,3-12 序關系,定義3-12.1 若集合A上的二元關系R是自反的、反對稱的和傳遞的，則稱R是A的偏序關系，記作 。設 為偏序關系，如果 ，則記作x y，讀作“小于或等于”。序偶稱為偏序集合。 注意這里的“小于或等于”不是指數(shù)的大小，而是在偏序關系中的順序性。x“小于或等于”y的含義是：依照這個序，x排在y的前邊或者x就是y。根據(jù)不同偏序的定義，對序有著不同的解釋。例如整除關系是偏序關系，3 6的含義是3整除6。大于或等于關系也是偏序關系，針對這個關系寫5 4是說大于或等于4,關系中5排在4的前邊，也就是5比4大,蓋住,定義3-12.2

25、在偏序集中，如果x,yA ， x y， x y，且沒有其他元素z滿足x z、 z y，則稱元素y蓋住元素x。并且把所有具備蓋住性質(zhì)的續(xù)偶集合記作COV A， COV A=|y蓋住x 例：A為正整數(shù)m12的因子的集合，并設 為整除關系，求COV A。(P140,哈斯圖（偏序集合圖,對于給定的偏序集 ，它的蓋住關系是唯一的，所以可以用哈斯圖表示偏序集合圖。 哈斯圖作圖規(guī)則： 用小圓圈代表元素。 如果 x y，且x y，則將代表y的小圓圈畫在代表x的小圓圈之上。 如果 COV A,則在x與y之間用直線連接,哈斯圖舉例,例：畫出偏序集 的哈斯圖,哈斯圖舉例（續(xù),例：A=a,b,c， 畫出 的哈斯圖,哈

26、斯圖舉例（續(xù),例：已知偏序集的哈斯圖如圖所示，試求出集合A和關系R的表達式,解：A=a,b,c,d,e,f,g,h R=, ,IA,偏序集中的特殊元素,定義3-12.5,3-12.6 設為偏序集，B是A的子集，yB。 若 x(xBy x)成立，則稱y為B的最小元。 若 x(xBx y)成立，則稱y為B的最大元。 若bB,且B中不存在任何元素x,使bx且b x 稱b是B的極大元。 若bB,且B中不存在任何元素x,使bx且x b 稱b是B的極小元,例：設偏序集如圖所示，求A的極小元，最小元，極大元，最大元,解:極小元：a,b,c,g。 極大元：a,f,h。 沒有最小元與最大元。 由這個例子可以知道

27、，哈斯圖中的孤立頂點既是極小元也是極大元,解：A不存在最大、最小元；極大元素為d,e,極小元素為a,b； B的最大元素為c，沒有最小元素；極大元素為c, 極小元素為a,b,例：設A=a,b,c,d,e、B=a,b,c，則各自的最大最小元素、極大極小元素是哪些,最小元是B中最小的元素，它與B中其它元素都可比；而極小元不一定與B中元素可比，只要沒有比它小的元素，它就是極小元。對于有窮集B，極小元一定存在，但最小元不一定存在。最小元如果存在，一定是唯一的，但極小元可能有多個。如果B中只有一個極小元，則它一定是B的最小元。如果B中存在最小元，則它一定是B的唯一極小元。類似的，極大元與最大元也有這種區(qū)別

28、,定理3-12.1 設是一偏序集合，且BA，若B有最大（最?。┰?，則是唯一的。 證： 設a,b都是B的最大元素， 那么a b,b a，從偏序關系的反對稱性，得a=b。 最小元證明情況與此類似,上界、下界,定義3-12.7，3-12.8 設為偏序集，BA，yA。（1） 若 x(xBx y)成立，則稱y為B的上界。 （2） 若 x(xBy x)成立，則稱y為B的下界。 （3） 令Cy|y為B的上界，則稱C的最小元為B的最小上界或上確界。 （4） 令Dy|y為B的下界，則稱D的最大元為B的最大下界或下確界,設為有序集，BA。 的哈斯圖如下所示。 A= a，b，c，d，e，f，g，h，i，j，k , B=a，b，c，d，e，f，g B=h，i，j，k,B,由定義可知，B的最小元一定是B的下界，同時也是B的最大下界。同樣的，B的最大元一定是B的上界，同時也是B的最小上界。但反過來不一定正確，B的下界不一定是B的最小元，因為它可能不是B中的元素。同樣的，B的上界也不一定是B的最大元,序關系（注意,1）B的最大（小）元素和極大（?。┰乇仨毷亲蛹疊的元素，而B的上界（下界）和最小上界（最