離散數(shù)學教案

1、學習目標：1 .深刻理解序偶、笛卡爾積、關系、集合的劃分與覆蓋、等價關系、等價 類、商集、相容關系、（最大）相容類、偏序關系、極大元、極小元、上（下） 界、上（下）確界、最大（?。┰?、全序關系、良序關系等概念；2 .掌握集合的交、并、差、補、對稱差的運算及其運算規(guī)律；3 .掌握關系的交、并、逆、復合運算、閉包運算及其性質(zhì)；4 .掌握關系的矩陣表示和關系圖；5 .深刻理解關系的自反性、反自反性、對稱性、反對稱性和傳遞性，掌握 其判別方法；6 .掌握集合的覆蓋與劃分的聯(lián)系與區(qū)別；7 .掌握偏序關系的判別及其哈斯圖的畫法；會求偏序集中給定集合的極大 元、極小元、上（下）界、上（下）確界、最大（?。┰?/p>

2、。主要內(nèi)容：1 .集合的基本概念及其運算2 .序偶與笛卡爾積3 .關系及其表示4 .關系的性質(zhì)及其判定方法5 .復合關系和逆關系6 .關系的閉包運算7 .等價關系與相容關系8 .偏序關系重點：（1 .關系的性質(zhì)及其判別；2 .關系的復合運算及其性質(zhì)；3 .等價關系與等價類、等價關系與集合的劃分的聯(lián)系；4 .偏序關系判別及其哈斯圖的畫法、偏序集中特異位置元素的理解。 難點：1 .關系的傳遞性及其判別；2 .等價關系的特性；3 .偏序關系的哈斯圖的畫法；偏序集中特異位置元素的求法。教學手段：通過多個實例的精講幫助同學理解重點和難點的內(nèi)容，并通過大量的練習使同學們鞏固和掌握關系的性質(zhì)及其判別、關系的

3、復合運算及其性質(zhì)、等價關系 的特性、偏序關系的哈斯圖的畫法及偏序集中特異位置元素的求法。習題：習題：4, 6：習題：3 (8), 4 (12), 6 (m)；習題：1 (2)、(4), 3：習題：1, 4；習題：2, 5, 6；習題：2, 5, 6；習題：1 (1) - (6)；習題：3 (2)、 (4), 4(3)；習題：1 , 4, 5。集合的基本概念集合(set)(或稱為集)是數(shù)學中的一個最基本的概念。所謂集合，就是指具有共同性 質(zhì)的或適合一定條件的事物的全體，組成集合的這些''事物稱為集合的元素。集合常用大寫字母表示，集合的元素常用小寫字母表示,若4是集合，”是A的元

4、素，則稱屬于A ,記作oeA：若。不是4的元素，則稱。不屬于4,記作。若組成集 合的元素個數(shù)是有限的，則稱該集合為有限集(Finite Set),否則稱為無限集(Infinite Set)。常見集合專用字符的約定：N自然數(shù)集合(非負整數(shù)集) .。一有理數(shù)集合(Q+，Q_) 月一分數(shù)集合(以，F(xiàn) ) 。一復數(shù)集合。一奇數(shù)集合/ (或Z)整數(shù)集合(人，/_) /?一實數(shù)集合(，R_)腳標+和-是對正、負的區(qū)分P素數(shù)集合E偶數(shù)集合塞集定義3.1.1對于每一個集合A ,由A的所有子集組成的集合，稱為集合4的事集(PowerSet),記為 P(4)或2A.即P(A) = 5怛q4。例如：A = a,b,

5、c, P(A) = 0,a,Z?，c，b,c,a,c,a,c。定理3.1.1如果有限集4有個元素，則其需集P(A)有2"個元素。證明A的所有由8個元素組成的子集數(shù)為從個元素中取個的組合數(shù)。& _ (一1)(-2一(”一攵 + 1)另外，因A,故P(A)的元素個數(shù)N可表示為N = l + C：+C：+ &+ +, = £&i-0又因得 2" = zcJl-0故P（A）的元素個數(shù)是2” .人們常常給有限集A的子集編碼，用以表示A的密集的各個元素。具體方法是：設A = %, %,則A子集8按照含4記1、不含%記0（i = 1,2,的規(guī)定 依次寫成

6、一個位二進制數(shù)，便得子集8的編碼。例如，若8 = %,4,則B的編碼是100-01,當然還可將它化成十進制數(shù)。如果 =4,那么這個十進制數(shù)為9,此時特別記8 = %,%為線。集合的對稱差運算定義3.2.1設A、8是兩個集合，要么屬于A ,要么屬于8,但不能同時屬于A和 8的所有元素組成的集合，稱為A和8的對稱差集，記為A3 .即力 8 = (A - 8) U (8 - A) = x| x e Avx e 8例如,若如= l,2,c,d, B = l,b,3,d),則如8 = 2,c,瓦3 0對稱差的定義如圖3-1所示。圖3-1由對稱差的定義容易推得如下性質(zhì)：< 1) A 8 = 8 A(

7、2) A。=力(3) 44 = 0(4) 48 = (An月)U(無D8)(5) (A3)9C = A9(3C)證明(5) (A8)C=ka 3)nQu(nc) =（AnB）u（AnB）nc）u（AnB）u（AnB）nc=（AnBnou（AnBnc）u（AUB）n（AU）nc 但（auB）n（AU初nc=（AUB）nAU（AU）n5）nc=（AnA）u（An5）u（AnB）u（BnB）nc=su（An8）uo?n 月）uomc=（AnBnc）u（AnBnc）故 （43）C=（AnBnc）u（AnBnc）u（An5nc）u（An5nc）又=（An©c）uin（Bc）j=An（BAc）u

8、（Bnc）UAn（BAc）u（Bno=An（Buc）n（Buc）U（AnBnc）u（An5nc）j 因為 Ani（Buc）n（uc）=An（5nB）u（Bnc）u（cn5）u（cnc）=aci（月 ncucrw=（An5nc）u（AncnB）故 A0（BC）=（Annc）u（AnBno u（an8ne）u（口 n 月 n。）因此 （A3）C = A（88C）對稱差運算的結合性亦可用圖3-2說明。(A8)C = A(3C)圖3-2對稱差運算的結合性從文氏圖3-3亦可以看出以下關系式成立。AUB=（An 豆）u（3nmu（An8）=(A 3)U(An3)圖 3-3 AJB序偶與笛卡爾積3.4.1

9、序偶在日常生活中，有許多事物是成對出現(xiàn)的，而且這種成對出現(xiàn)的事物，具有一定的順 序。例如，上，下；1V2:男生9名而女生6：中國地處亞洲；平面上點的坐標等。一般 的說，兩個具有固定次序的客體組成一個序偶（Ordered Pair）,記作（X,），）。上述各例可分 別表示為上，下）：（1,2）；（9,6）：中國，亞洲）：O等。序偶可以看作是具有兩個元素的集合，但它與一般集合不同的是序偶具有確定的次序。 在集合中，。力=似。,但對序偶，當4Hb時，.Q）、G 0定義3.4.1兩個序偶相等，（%» = （,口”當且僅當x =這里指出：序偶（4,與中兩個元素不一定來自同一個集合，它們可以代表

10、不同類型的 事物。例如，”代表操作碼，代表地址碼，則序偶（。力）就代表一條單地址指令：當然 亦可將。代表地址碼，8代表操作碼，與仍代表一條單地址指令。但上述這種約定， 一經(jīng)確定，序偶的次序就不能再予以變化了。在序偶4,。）中，稱第一元素，Z?稱第二 元素。序偶的概念可以推廣到有序三元組的情況。有序三元組是一個序偶，其第一元素本身也是一個序偶，可形式化表示為X,y,z)。由序偶相等的定義,可以知道蒼當且僅當 (x, y)=(/)，2 =卬，即工=,丫 =匕2 =卬，我們約定有序三元組可記作(X,y,Z)。注 意：x,»,z)Xx,y,z，因為(x,y,z不是有序三元組。同理，有序四元組

11、被定義 為一個序偶，其第一元素為有序三元組，故有序四元組有形式為x,y,z),w),可記作 (工乂乙卬)，且(x,y,Z,w)= (p,qj,s) Ox = p/y = qz = r/w=s這樣，有序元組(Ordered n-tuple)定義為和七，玉-1，4)，記 作 冷，七T，)，且魯，12,，4)=仆1，為,，以=玉=X八/=為八八Z =片一般地，有序元組(3,看，皿中的士稱作有序元組的第i個坐標。3.4.2 笛卡爾積定義342設A和8是任意兩個集合，若序偶的第一個成員是A的元素，第二個成員是 8的元素，所有這樣的序偶集合，稱為集合A和8的笛卡爾乘枳或直積(Cartesian Produ

12、ct),記作 A。3。即4 x B = «, y)x A a y e B例 3.4.1 若 A = 1,2,8 = ”也c,求 Ax8,3x8 以及(Ax8)n(8x A)解 Ax8 = °,(1力),(1，0，(2,2,外2,c)Bx B =,9,0 ,9,c)&，b) ®,c)4 = «由,42,(九1),仇2),伯1),42) (Ax3)n(3xA) = ° 顯然，我們有：(1) AxB BxA；(2)如果同= ?,因=，則 |Ax8| = |8x A| = |A|同= "?。我們約定：若A =?；? =。，則由笛卡爾積

13、定義可知：(AxB)xC = (x,y),z)|(x,Ax8八z wC(x,y,訃 eAaeBazeCAx(8xC) = (x,y,zk£ A 八y,ze8xC由于(x,y,z»不是三元組，所以(AxB)xC Ax(BxC)定理3.4.1設A、8和。為任意三個集合，則有(1)Ax(BJC) = (AxB)J(AxC)(2) Ax(BnC) = (AxB)n(AxC)(3) (AU3)xC = (AxC)U(BxC)(4) (ACB)xC = (AxC)r(.BxC)證明(1)設(x,)，)wAx(BUC)ox£AAye3UC< => x e A a (

14、y e B v y e C)< => (x e A a y g B) v (x e A a y e C)< => (x,) e A x 3 v (x, y) e 4 x C< =>«,» £(4x8)U(4xC)因此，Ax(BUC) = (AxB)U(AxC)o(4)設«,yw(An3)xCox£Ar)3/ywC<=>(xeAAxeB)AyeCo (x e A a y g C) a (x e B a y e C)O(x, y) £ AxC/(x, yeBxCO(X»£

15、(4xC)n(BxC)因此，(An3)xC = (AxC)n(3xC)。定理342設A、B和。為三個非空集合，則有AxC .BxC <>CxA.CxB 證明設對任意的x,»,(X, » £ AxC <=> x £ A 八)，6 C=>xeB/yeC<=><x,y)£3xC因此，AxC c BxCo反之，若AxCqBxC,取yeC,則對Vx,有X"<=>X£Aa>£CO(X,»"xC=> x, y) g Bx C <=&

16、gt; x g B a y g C<=>xeB因此，AB定理的第二部分Aq8oCxA = Cx8,證明類似。定理3.4.3設4、B、C和。為四個非空集合，則AxBqCxO的充要條件為 AqC且Bq。證明若AxBqCxO,對任意的xeA,ye8,有(x g A) A(y gB)<=><x, y)eAxB => (x,» w Cx。<=>(xeC)A(yeD)即 AjC,BjD »反之，若AqC且BqO,設任意有(x, y) £ A x 3 <=> (x £ 4) (y £ 8)=>

17、(xeC) A(y e D)=> (x, y) eCxD因此，AxBcCxDo對于有限個集合可以進行多次笛卡爾積運算。為了與有序元組一致，我們約 定：A X & X A3 = (A X A? ) X 4A, x A2 x A3 x A4 = (A, x A2 x A3) x A4= (4xA2)xA3)xA4一般地，A x&xx4 =(AxA2XxA_i)xA= <,，,乙)|玉 GA, AX2gA2 A.-.AX/? G4故A x& xxA是有序元組構成的集合。特別地，同一集合的次直積AxAxxA,記為這里A"=A'ixA。 V'

18、例如，1,23=1,2內(nèi)1,2 = (1,1),1,2,2,1,2,2人與2«2,1),1),(2,1),2),(2,2),1),(2,2),2)= (1,1,1),(1,1,2),(1,2,1),(1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2)此處，同=2,卜=2、=8。一般地，若圖= ?,則卜= ?”。關系及其表示351關系的定義在日常生活中我們都熟悉關系這詞的含義，例如，父子關系、上下級關系、朋友關系 等。我們知道，序偶可以表達兩個客體、三個客體或個客體之間的聯(lián)系，因此可以用序 偶表達關系這個概念。例如，機票與艙位之間有對號關系。設x表示機

19、票的集合，y表示艙位的集合，則對 于任意的xwX和)，£丫，必有x與y有對號關系和x與)，沒有對號關系兩種情況的一種。令R表示“對號”關系，則上述問題可以表達為xRy或kRv，亦可記為或心»任火，因此，我們看到對號關系R是序偶的集合。定義3.5.1設x、丫是任意兩個集合，則稱直積Xxy的任一子集為從x到y(tǒng)的一個 二元關系(BinaryRelation)。二元關系亦簡稱關系，記為R，RqXxY ,x到y(tǒng)的二元關系r,如圖3-4所示。X1圖3-4集合x到y(tǒng)的二元關系是第一坐標取自x、第二坐標取自y的序偶集合。如果序偶 也說X與)，有關系R,記為xRy；如果序偶則說X與y沒有關

20、系R ,記為xRy。當x=y時，關系欠是XxX的子集，這時稱?為集合x上的二元關系。例 3.5.1 (1)設 A = ,/?, B = 2,5,8,則4xB = (a2),(a5)，e，8，e，2，e，5,(女 8),令N=02)，m，8)，e，2).=-5,«,2),一5»及- =,2因為與工AxB,叫£AxB, &工AxB ,所以，&和冬均是由A到8的關 系。(2) >=(,»卜是實數(shù)且x>y是實數(shù)集上的大于關系。定義3.5.2設R為X到V的二元關系，由C，y)wR的所有x組成的集合稱為R的定 義域或前域(Domain),

21、記作dom R或O(H),即dom R = x|(3j)(x, y) e R)使卜,的所有y組成的集合稱為R的值域(Range),記作ran R ,即ran/? = y|(3x)(x, y) e H)。R的定義域和值域一起稱作R的域(Field),記作FLDR,即 FLD R = dom R|J ran R顯然，dom R q X , ran R 三 y , FLD R =dom RU ran R q X U y例 3.5.2 設 A = 1,3,7, B = 1,2,6 , =1,2,1,6,7,2,求 dom H , ran H 和 FLD H。解 dom" =1,7，ran &

22、quot;=2,6, FLD "= 1,2,6,7, 例353設乂=2,3,4,5，求集合X上的關系“<"、dom<及ran<0解<=(2,3),2,4,2,5,3,4),(3,5),(4,5»dom< =2,3,4ran< = 3,4,53.5.2幾種特殊的關系1 .空關系對任意集合X, Y, gXxY ,XxX,所以。是由X到y(tǒng)的關系，也是X 上的關系，稱為空關系(Empty Relation)。2 .全域關系 )因為XxyXxy, xxXqXxX,所以Xxy是一個由x到y(tǒng)的關系，稱為 由X到V的全域關系(Universal

23、 Relation)。XxX是X上的一個關系，稱為X上的全域關 系，通常記作E* ,即Ex =(xpx.)|xpxy eXo例3.5.4若"=/,?,$/表示家庭中父、母、子、女四個人的集合，確定”上的全 域關系和空關系，另外再確定上的一個關系，并指出該關系的前域和值域。解設上同一家庭的成員的關系為4 ,“I=(/,力 (£ 昉 ,(/, $),(/, 4,(肛力,(孫肛 m S), w,(s J), SM,(5, s),d,(dm、, (d, s), 設上的互不相識的關系為“2，”2=。，則用為全域關系，”2為空關系。設”上的長幼關系為“3，dom H3 =/,?ran

24、g =$，3 .恒等關系定義3.5.3設G是X上的二元關系且滿足& =乂*k£乂),則稱&是X上的 恒等關系(Identical Relation)。例如,A = 1,2,3,則2,2),(3,3) °因為關系是序偶的集合，因此，可以進行集合的所有運算。定理351若。和S是從集合X到集合丫的兩個關系，則。、S的并、交、補、差 仍是X到V的關系。證明因為。式XxY,SXxy,故QUSqXxKQflS q Xxy« = (XxY-S)工 XxY。-s =(Qn«) = Xxy例 3.5.5 若4 = 1,2,3,4), /?, = x, y)

25、|(x,)/2 e A,x, y e A,尺2 = x，|(x y)/3 e A,x,y e A,求凡&，RU&，R-&和R。解 K =3,1，4,2),尺2 =4,1),0C g = 0W& =3,1,4,2,4,1Ri _ R- = R 1A*1Ri = ea - R= 1,1,1,2,1,3,1,4,2,1,2,2,2,3,2,4)，(3,2),(3,3),3,4,4,1),4,3),4,4)3.5.3關系的表示I1 .集合表示法因為關系是序偶的集合，因此可用表示集合的列舉法或描述法來表示關系。例如，例 3.5.1的(1)中的關系, &和氏3及例中

26、的關系，均是用列舉法表示的關系：而例 3.5.1的(2)中的關系和例中的關系鳥，&都是用描述法表示的關系。有限集合間的二元關系R除了可以用序偶集合的形式表達以外，還可用矩陣和圖形表 示，以便引入線性代數(shù)和圖論的知識來討論。2 .矩陣表示法設給定兩個有限集合x=±,x2,，(，丫川小刈，”，則對應于從x到y(tǒng) 的二元關系R有一個關系矩陣Mr =，其中'1當即0=.、(i = 12,?； ) =o,0當(和yR如果R是有限集合x上的二元關系或x和y含有相同數(shù)量的有限個元素，則Mr是方 陣。例 3.5.6 若=。，4，0，04，8 =例,與,4,R =, (。2也)，(3，與

27、，(44也)，6也 ,寫出關系矩陣“內(nèi)解- i o r0 1 1Mr= 1 0 00 1 0- 0 1 °J5X3例3.5.7設X = 1,2,3,4,寫出集合X上的大于關系>的關系矩陣。解 >=2,1),(3,1),(3,2),4,4(4,2),(4,3»- 0 0 0 0-10 0 0M =>110011103.關系圖表示法有限集合的二元關系也可用圖形來表示。設集合X =玉,，毛)到玉,另外做個結點分別記作加刈力做一有向弧，其箭頭指向力,如果用小接起來的圖稱為R的關系圖。例3.5.8畫出例的關系圖。解本題的關系圖如圖3-11所示：如果x/力，則從結點七

28、至結點則.力之間沒有線段連接。用這種方法連4。0丫 = )1，%，一,，北上的一個二元關系為R，首先我們在平面上做出？個結點分別記作圖3-11例3.5.8的關系圖例 3.5.9 設=1,2,3,4,5,=畫出例的關系圖。解 因為氏是人上的關系，故只需畫出A中的每個元素即可。如果。/勺，就畫一條由勺到的有向弧。若=%，則畫出的是一條自回路。本題的關系圖如圖3-12所示。圖3-12例3.5.9的關系圖關系圖主要表達結點與結點之間的鄰接關系，故關系圖與結點位置和線段的長短無 關。從X到y(tǒng)的關系R是XxY的子集，即RqXxY ,而 xxYq(xuy)x(xuy),所以，Rq(xuy)x(xuy)

29、76; 令 z = xuy，則 RqZxZ。因此，我們今后通常限于討論同一集合上的關系。關系的性質(zhì)及其判定方法3.6.1 關系的性質(zhì)定義361設R是定義在集合X上的二元關系，如果(1)對于每一個X£X,都有X&,則稱R是自反的(Reflexive).即 R在X上自反=(Vx)(xwX -四)(2)對于每一個XWX,都有晶,則稱R是反自反的(Antireflexive)°即R 在 X 上反自反=(Va)(x e X -> xRx)(3)對于任意e X ,若就有yRv ,則稱R是時稱的(Symmetric)。即 R 在 X 上對稱=(Vx)(Vy)(x £

30、; X) a (y e X) a (xRy) T (y&)(4)對于任意,若xRy , yRx .必有x = y,則稱R在X上是反對稱的 (Antisymmetric) o 即R在 X 上反對稱o(Vx)(Vy)(xeX)A(yeX)八(xHy)人(y&) f (x = y)(5)對于任意x,y,zeX ,若xRy, yRz.,就有xRz,則稱R在X上是傳遞的 (Transitive)o HPR 在 X 上傳遞o(Vx)(Vy)(Vz)(x e X) A(y e X) a(z X)/(xRy) a()火z) f (x&)例3.6.1設4 = 1,2,3,則集合A上的關系

31、N=(1,1),(2,2),(2,1),(3,3»是自反而不是反自反的關系:一 =(1,2),(1,3),2,1)(2,3)是反自反而不是自反的關系; (6=0,1),(1,3),(2,1),(2,3)是既不是自反也不是反自反的關系：是對稱的而不是反對稱的關系；& =(1,1),1,3),(2,1),(2,3)是反對稱的而不是對稱的關系；« =(1,1),(2,2),(3,3)是既對稱也反對稱的關系：與=(1,2),2,3),(3,2»是既不對稱也不反對稱關系。=(1,1),(1,2),(2,1),(2,2), .=1,2)(3,2»是可傳遞的關

32、系:是不可傳遞的關系,因為l,2w&o, (2/卜時,但。.”心)。由定義3.6.1及例可知：(1)對任意一個關系R,若R自反則它一定不反自反，若R反自反則它也一定不自 反：但R不自反，它未必反自反，若R不反自反，也未必自反。(2)存在著既對稱也反對稱的關系。圖3-5表明了自反與反自反、對稱與反對稱性之間的關系。圖3-5例3.6.2集合之間的£關系是自反的、反對稱的和可傳遞的。因為：1）對于任意集合A ,均有AqA成立，所以£是自反的；2）對于任意集合48,若且8qA,則A = B,所以q是反對稱的；3）對于任意集合A8,C,若且則AqC,所以£是可傳遞

33、的。（2）平面上三角形集合中的相似關系是自反的、對稱的和可傳遞的。因為：任意一 個三角形都與自身相似：若三角形A相似于三角形8,則三角形8必相似于三角形A ； 若三角形A相似于三角形8,且三角形8相似于三角形C，則三角形A必相似于三角形C.（3）人類的祖先關系是反自反、反對稱和可傳遞的。（4）實數(shù)集上的“>”關系是反自反、反對稱和可傳遞的。（5）實數(shù)集上的“ £ ”關系是自反、反對稱和可傳遞的。（6）實數(shù)集上的“=”關系是自反、對稱、反對稱和可傳遞的。（7）人群中的父子關系是反自反和反對稱的。（8）正整數(shù)集上的整除關系是自反、反對稱和可傳遞的。（9）。是反自反、對稱、反對稱和可

34、傳遞的。（10）任意非空集合上的全關系是自反的、對稱的和可傳遞的。例3.6.3設整數(shù)集Z上的二元關系R定義如下：R = x, y|x, y e N, （x y） / 2 是整數(shù),驗證R在Z上是自反和對稱的。證明VxwZ,（xx）/2 = 0,即故R是自反的。又設如果xRy,即（x y）/2是整數(shù)，則（y x）/2也必是整數(shù)，即 y&，因此R是對稱的。3.6.2 由關系圖、關系矩陣判別關系的性質(zhì)例3.6.4集合A = 1,2,3,4, A上的關系R的關系矩陣為：R的關系圖如圖3-6所示。討論R的性質(zhì)。圖3-6解從R的關系矩陣和關系圖容易看出，R是自反的、對稱的°一般地，我們有：

35、（1）若關系R是自反的，當且僅當其關系矩陣的主對角線上的所有元素都是1：其關 系圖上每個結點都有自環(huán)。<（2）若關系R是對稱的，當且僅當其關系矩陣是對稱矩陣；其關系圖上任意兩個結 點間若有定向弧，必是成對出現(xiàn)的。（3）若關系R是反自反的，當且僅當其關系矩陣的主對角線上的元素皆為0：關系圖 上每個結點都沒有自環(huán)。（4）若關系R是反對稱的，當且僅當其關系矩陣中關于主對角線對稱的元素不能同 時為1：其關系圖上任意兩個不同結點間至多出現(xiàn)一條定向弧。（5）若關系R是可傳遞的，當且僅當其關系矩陣滿足：若弓二1 且。=1，則 =1：其關系圖滿足：對手j,j手k,若有弧由指向,且又有弧由。，指向,則必有

36、一條弧由/指向火。 /A<A例3.6.5圖3-7是由關系圖所表示的A = a,b,c上的5個二元關系。(1)(2)圖3-7請判斷它們的性質(zhì)。解是反對稱、傳遞但不是對稱的關系，而且是既不自反也不反自反的關系：(2)是自反、傳遞、反對稱的關系，但不是對稱也不是反自反的關系：(3)是反自反但不是對稱、不是反對稱、不是自反也不是傳遞的關系：(4)是不自反、不反自反但是傳遞的關系，而且既是對稱也是反對稱的關系；(5)是自反、反對稱但不是傳遞、不是對稱也不是反自反的關系。)復合關系和逆關系3.7.1復合關系1.復合關系的定義定義3.7.1設R是從x到丫的關系，s是從y到z的關系，則RoS稱為R和s的

37、復合關 系(Compositive Relation)表示為RoS = (x,z)|xwX/z wZ(子)(丁 £丫人工式)”)&)從/?和S求RoS,稱為關系的復合運算.復合運算是關系的二元運算，它能夠由兩個關系生成一個新的關系，以此類推。例 如，R是從x到y(tǒng)的關系，s是從丫到z的關系，p是從z到卬的關系，則(n。5)。夕 是從x到w的關系。例 3.7.1 設 R 是由 A = 1,2,3,4,到 8 = 2,3,4的關系,S 是由 8 到 C = 3,5,6的關系，分別定義為:. = (叫=6 = 24),3,3),4,2)jS = LI b 整除c = (2,6), (

38、3,3), (3,6)于是復合關系R°S = (3,3),3,6,4,6)。例3.7.2設A是所有人的集合。4=(4,I£ A, 4是國勺兄弟,& = 僅,c)也c £ A, b是cfl勺父親,那么H=(acla,cw A, 是必叔伯;而&。&= (ac) la.ce A, 4 是c 的祖父。例3.7.3設一和凡是集合A = 0,1,2,3上的關系，=他川人i+1 或片2 , 一 =(i，3 = j+2求凡。&、R? ° R、(凡。4)。凡和(凡。凡)。凡° I，/ JI 工JII1解 4 =0,1,。,2),2

39、3),0,0,2,1»g=00%(3)6。4=(2,1),2,0),3,2)(«。取咽=(1,1),1,0),2,2)=(0,2),(0,1),(1,3),(1,1),(0,0),(2,2)(4。用喇=(0,3),0,1),0,2,"2),(0,0),2,3,21)2.關系的復合運算的性質(zhì)定理3.7設r是由集合x到y(tǒng)的關系，則&。冗=。4 =尺，定理3.7.2設r是從x到y(tǒng)的關系，s是從y到z的關系，則有(1)dom(7?o5) cdom/?(2) ran(7?oS)cranS(3)若 ran/? H dom5 = 0 , 則 R。S = 0。證(1)和(

40、2)是顯然的，下面我們證明(3)0用反證法。反設RoS，。，則必存在xeX,zeZ,使C0£尺。5,從而小£丫，使(X,), G R,(y,z)£ S,故 y erani?且 y e dom5 ,所以 y e ran?Qdom5 ,這就與 ran7?ndomS =0矛盾，因此，K。5 = °。定理3.7.3(1)設&、R?和R3分別是從x到丫、y到z和z到w的關系，則(«。&)° & =為。(6 °&)即關系的復合運算滿足結合律。(2)設飛和R?都是從x到y(tǒng)的關系，s是從y到z的關系，則1)(

41、KU&”s = (&oS)u(&oS)2)(n4”sq(aos)n(&os)(3)設s是從x到丫的關系，舄和&都是從y到z的關系，則1) So(4U&) = (SoR1)U(So&)2)5。(為。叫)三(s*)n(s°&)證我們只證明(2),其它證明類似。1)X W(0 U 鳥)。S(< => (3y)(.V E y A(X,» £ 4 U R2 A( y' z) £ S)< => (3y)(.y £ y 八X, y) W K V (x, y) w

42、4) A(y, z£ S)< => (3y)(.V £ 丫 a * » g/?, a(.v,z)gS)v (3y)(y w 丫 八(x,» w &) a 什,zw S)O(x wR1 °Sv(x,z)wa oSO-Z）w （凡。S）U（4°S） 所以（KU&”s=（及。s）u（&oS）2）V（x*（Nng）。S< => （3y）（.v £ 丫 5,y） £ 4 n 與人（乂 z） £ S）< =>Gy）（y £ 丫a（x,y） wR 八

43、（x,y）e& a（y,z）eS）=> （x, z）£ Ri ° S 八（x,公 wR?oSO（X,Z）（R oS）n（4 oS）所以（為n&）os±（4os）n（&os）。注意：一般來說，（i）（為n4）。5工（4°s）n（叫 cS）：（2）關系的復合運算不滿足交換律。例374 （1）設4 = /,C, 3 = x,y,z,仆和R?都是從4到8的關系，S是從8到 A 的關系，N =（，（，>），鳥=（,x）,（a,z»，S = «M，（y,c）,c）,則（.s=他奶,（K°s）n（鳥。s

44、）=e，s，e，c»,可見，（4n叫）。5三（飛。5）0（&。5）,但（與04）。5。（4。5）0（4。5）。（2）設4 = 泊了），用和R?都是集合A上的關系，4=（。力）,&=電”,則4。與=（4,）,而與。凡=色力,所以由于關系的復合運算滿足結合律，所以（%。4）。& =仆。（叫。&）可以寫成與。&。&。一般地,若&是一由A到4的關系,&是由4到4的關系，R”是一由4到4m的關系，則不加括號的表達式飛。&。（唯一地表示一由A到4+1的關 系，在計算這一關系時，可以運用結合律將其中任意兩個相鄰的關系先結合。特

45、別地，當A = A? = = A“+ = A , /?=&=K” = H，即R是集合4上的關系時，復合關系凡°&。c=RcR；c/?簡記作R，它也是集A上的一個關系。 n3.7.2復合關系的矩陣表示及圖形表示因為關系可用矩陣表示，所以復合關系也可用矩陣表示。已知從集合x= 內(nèi)到集合丫 = ?。?,，尤上的關系為R，關系矩陣 從集合丫 = %為，£到集合Z = q,Z2,q的關系s,關系矩陣Ms=%，表示復合關系RoS的矩陣M/S可構造如下：若犯eV,使得且,則（/zJeRoS。在集合丫中能夠滿 足這樣條件的元素可能不止X 一個，例如另有力,也滿足（玉,x）

46、e R且（匕4）e S。在 所有這樣的情況下，（ZrzJeRoS都是成立的。這樣，當我們掃描加長的第i行和Mg的 第k列時，若發(fā)現(xiàn)至少有一個這樣的J,使得第i行的第/個位置上的記入值和第k列的第 j個位置上的記入值都是1時，則加播的第i行和第k列上的記入值為1：否則為因 此加松.可以用類似于矩陣乘法的方法得到：n其中'% =/（%八%） J-l式中V代表邏輯加，滿足0v0 = 0，0vl = b lv0 = l, lvl = l：八代表邏輯乘，滿足0a0 = 0, 0a1 = 0> 1八0 = 0，1八1 = 1。例3.7.5給定集合4 = 1,2,3,4,5，在集合A上定義兩種

47、關系:夫=(1,2),3,4),2,2), 5 = (4,2),(2,5),3,1,1,3»,求RoS和S。/?的矩陣。01 0 0Mr-s0 = 010 0 10 0 10 0 00 0 00 0 0Ms.k因為關系可用圖形表示，所以復合關系也可用圖形表示。例376例中的兩個關系R與S的復合RoS很容易通過下而的關系圖(見圖3-8)得至上圖3-8 RoS示意圖由該圖立即可得 RoS = (3,3),3,6,4,6»03.7.3逆關系關系是序偶的集合，由于序偶的有序性，關系還有一些特殊的運算°定義3.7.2設R是從X到y(tǒng)的二元關系，若將K中每一序偶的元素順序互換,

48、 得到的集合稱為R的逆關系(Inverse Relation),記為即例如，在實數(shù)集上，關系“<"的逆關系是從逆關系的定義，我們?nèi)菀卓闯?R尸=K.定理3.7.4設H、叫和&都是從X到y(tǒng)的二元關系，則下列各式成立，(1)(與U&)-1 =R/UR>(2)(坊(3) (XxYyx=YxX(4) (R)T=K 這里反= XxY-R(R& 尸=R” R：證明卜,»£(/?為)-' O()'，XwRl UR?o(y,x) e R (y、x) w R?u>x, y) e Rl vX,» e R；(4) (x

49、,y)e()-1 O(y,x)£Ro(y/)R<=> (x, y)電 R-i = (x, y) e K(5)因為R】_R,=R1n瓦, B4一故有(r&)t=(4 n耳尸=r： n(商t=rn可=r”r； 其它自證。定理3.7.5設R為從x到y(tǒng)的關系，s是從y到z的關系，則 (1)(Rosy'=s-loR-i(2) & U & = RU R：證明(1)卜1(夫。5尸0卜,加火。5<=> (3y)(.V £ 丫 ax, yg R a(> z) g S)<=> (3y)(y e Y 人(y g K a&q

50、uot;o(z,x)eST°/Ti所以(RoS)T =S-%R”(2)自證。定理3.7.6設R是X上的二元關系，則(1)K是對稱的，當且僅當寵=/?”；（2） A是反對稱的，當且僅當ACIR-I墨G：(3) A是傳遞的，當且僅當R2qR；(4) R是自反的，當且僅當4 7尺；(5) R是反自反的，當且僅當4口尺=。證明(1)若是對稱的，則對Vx,yeX,k,g R'所以，R = R-i ：若 R = R1 則對Dx,yeX,(x, y £ R <=> (y £ K <=> (y £ R所以，R是對稱的。 (3)若改 口 R

51、 ,則對Vx,y,zeX ,(x,yw R w R O Qc,z) w R? =>(x,z)g/?所以，R是傳遞的； 若K是傳遞的，V(x,z)wR' O(3y)(yeX a(x,»gR八(y,z)£R) =>(Xz)sR所以，RFR。其它證明留為作業(yè)。關系A-的圖形，是關系R圖形中將其弧的箭頭方向反置.R"的關系矩陣M小是 KMr的轉(zhuǎn)置矩陣。例 3.7.7 設/? = (1,。),2力),3,叫是 4 = 1,2,3到 8 = 。/© 的二元關系，S 是8到。=尤>"的二元關系，且5 = (。同，色司,(»

52、,求H°S和K。解 -5 = (1,孫(1,»,(2,孫(3,必(30K =«1）,（九2）,31 0 01或從 ,% = 0 1 0 , Ms= 11 0 00o oi ric*I0100=1001故取到RoS同樣的序元素;'i o r而M/=010 A0 0 0故取到R-l同樣的序元素。例378給定集合乂=。力1, R是X上的二元關系，R的關系矩陣1 0 1Mr= 1 1 01 1 1求R-I和R。/?"的關系矩陣'1 1 f解 M =0111 0 111 Fl0 G 0ij Lii ii i1 = 111ij |_i 1 i關系的閉

53、包運算關系作為集合，在其上已經(jīng)定義了并、交、差、補、復合及逆運算?，F(xiàn)在再來考慮一種 新的關系運算一關系的閉包運算，它是由已知關系，通過增加最少的序偶生成滿足某種指 定性質(zhì)的關系的運算.例如，設4 = 力,c, A上的二元關系R = aa),(aS，e，c),c,c),則A上含R且最小的自反關系是：r(R) = RJb,b)iA上含R且最小的對稱關系是：s(R) = RU(bO)；A上含R且最小的傳遞關系是：«H) = RUe，c). <定義3.8.1設R是X上的二元關系，如果有另一個X上的關系R滿足：(1)R是自反的(對稱的，傳遞的)；(2) R2R；(3)對于任何X上的自反的

54、(對稱的，傳遞的)關系R，若R"R ,就有 R" 0 R 0則稱關系-為R的自反(對稱,傳遞)閉包(Reflexive (Symmetric, Transitive) Closure).記作 7"(尺(R)。顯然，自反(對稱，傳遞)閉包是包含R的最小自反(對稱，傳遞)關系。定理3.8.1設R是X上的二元關系，那么(1)R是自反的，當且僅當r(R) = H(3) R是對稱的，當且僅當s(H) = R(4) R是傳遞的，當且僅當/(R) = H證明(1)若R是自反的，-R，對任何包含R的自反關系R"有R"&R,故r(R) = R；若r(R)

55、 = R，根據(jù)閉包定義，R必是自反的。(2)、(3)的證明完全類似。F而討論由給定關系R,求取”的方法。定理382設R是集合X上的二元關系，則(1) r(R) = RJIxi(2) s(r)= rurt(3) r(R) = 0w, z(R)通常也記作R十. l-i證明(1)令寵=RU/x，VxeX,因為故x,x)£R，于是R在X上是自反的。又R±RU/x即RqR °若有自反關系R"且n R，顯然有R"?/、，于是RFRU，x =R，所以 r(R) = RU/x ,(2)令 R = R(J R" ,因為(RU Qi )7 = R-i U

56、 (R-i 尸=A7U R = R U A所以R是對稱的。若/r是對稱的且V(x, y) R ,則(X,» e R或(X, y) e R-l 0當(x,»wR時,(x,y) g R"：當(X,»wRT 時，(y eR, 0 wR", (x,y) e R" »因此 R u R",故 s(R) = RJR-o(3)令R =先證”是傳遞的。r-1, (y,z)wR,則存在自然數(shù)攵，有您»£川, (y,z)w、，因此 x,zeRiqCjR'，所以，R是傳遞的。顯然，R 3 R,若有傳遞關系R&q

57、uot;且R = R,則存在自然數(shù)機，有3»£區(qū)"，則叫eX (i = l,2,1一1),使得(x,q),q，3,4i，»£R，因此32，他,生)，(4i，»*，由于R"是傳遞 關系，則x,y)R",所以A"nR'。故/=0叱。/-I例 3.8.1 設 X=x,y,z, R 是 X 上的二元關系，H = (x,y),y,z),(z,x),求r(©,s(H)/(R)。解 r(R) = RJIx =(x,y),y,z”(Z,x),(x,»，G，»,(Z,z)s(r) = RJRT為了求得/(R),先寫出箱=x(V,白,»* =。,<y,y),明W = 6，y)，y，z，z,x) = RR，=R、oR = R?繼續(xù)這個運算有：R = R4 =.= R3n+lR2=k=.= R3+2r3=r6= r3"3( = 1,2,)/(r) = Or =rUR2UR3U,"RUR2U