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

1、第7章 二元關(guān)系離 散 數(shù) 學(xué)本章說明本章的主要內(nèi)容有序?qū)εc笛卡兒集二元關(guān)系的定義和表示法關(guān)系的運(yùn)算關(guān)系的性質(zhì)等價(jià)關(guān)系與劃分偏序關(guān)系本章與后續(xù)各章的關(guān)系本章是函數(shù)的基礎(chǔ)本章是圖論的基礎(chǔ) 本章內(nèi)容7.1 有序?qū)εc笛卡兒積7.2 二元關(guān)系7.3 關(guān)系的運(yùn)算7.4 關(guān)系的性質(zhì)7.6 等價(jià)關(guān)系與劃分7.7 偏序關(guān)系 本章小結(jié) 習(xí)題 作業(yè)7.1 有序?qū)εc笛卡兒積 由兩個(gè)元素x和y（允許x=y）按一定順序排列成的二元組叫做一個(gè)有序?qū)?ordered pair)或序偶，記作，其中x是它的第一元素，y是它的第二元素。有序?qū)哂幸韵滦再|(zhì)： （1）當(dāng)xy時(shí)，。 （2）的充分必要條件是xu且yv。 說明有序?qū)χ械脑?/p>

2、素是有序的集合中的元素是無序的例 已知，求x和y。 由有序?qū)ο嗟鹊某湟獥l件有 x+25 2x+y4 解得 x3,y-2。 解答 設(shè)A，B為集合,用A中元素為第一元素，B中元素為第二元素構(gòu)成有序?qū)?。所有這樣的有序?qū)M成的集合叫做A和B的笛卡兒積(Cartesian product)，記作AB。笛卡兒積的符號化表示為AB|xAyB 笛卡兒積的定義A表示某大學(xué)所有學(xué)生的集合，B表示大學(xué)開設(shè)的所有課程的集合，則AB可以用來表示該校學(xué)生選課的所有可能情況。令A(yù)是直角坐標(biāo)系中x軸上的點(diǎn)集，B是直角坐標(biāo)系中y軸上的點(diǎn)集，于是AB就和平面點(diǎn)集一一對應(yīng)。 舉例笛卡爾積舉例設(shè)A=a,b, B=0,1,2，則AB=

3、,BA=, 舉例說明如果|A|=m,|B|=n,則|AB|=mn。笛卡兒積的運(yùn)算性質(zhì) (1)對任意集合A，根據(jù)定義有A, A(2)一般的說，笛卡兒積運(yùn)算不滿足交換律，即ABBA (當(dāng) A B AB 時(shí))(3)笛卡兒積運(yùn)算不滿足結(jié)合律，即(AB)CA(BC)(當(dāng) A B C 時(shí))(4)笛卡兒積運(yùn)算對并和交運(yùn)算滿足分配律，即A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)(5)AC BD AB CDA(BC)=(AB)(AC)的證明任取 A(BC) xA yBC xA (yByC) (xAyB) (xAyC) AB AC (AB)(A

4、C) 所以 A(BC)=(AB)(AC)關(guān)于ACBD ABCD的討論該性質(zhì)的逆命題不成立，可分以下情況討論。（1）當(dāng)A=B=時(shí)，顯然有AC 和 BD 成立。（2）當(dāng)A且B時(shí)，也有AC和BD成立，證明如下：任取xA，由于B,必存在yB,因此有 xAyB AB CD xCyD xC從而證明了 AC。同理可證 BD。關(guān)于ACBD ABCD的討論該性質(zhì)的逆命題不成立，可分以下情況討論。（3）當(dāng)A而B時(shí)，有AC成立，但不一定有BD成立。 反例：令A(yù),B1,C3,D4。（4）當(dāng)A而B時(shí)，有BD成立，但不一定有AC成立。 反例略。 例例7.2 設(shè)A=1,2,求P(A)A。 P(A)A ,1,2,1,21,2

5、 , , 解答例例7.3 設(shè)A，B，C，D為任意集合，判斷以下命題是否為真，并說明理由。(1) ABAC BC(2) A-(BC)(A-B)(A-C)(3) ABCD ACBD(4) 存在集合A，使得A = AA(1) 不一定為真。當(dāng)A，B1,C2時(shí)，有 ABAC，但BC。(2) 不一定為真。當(dāng)A=B=1,C2時(shí)，有 A-(BC)11 (A-B)(A-C)1(3) 為真。由等量代入的原理可證。 (4) 為真。當(dāng)A時(shí)，有 A=AA 成立。 解答7.2 二元關(guān)系(binary relation) 如果一個(gè)集合滿足以下條件之一：（1）集合非空，且它的元素都是有序?qū)Γ?）集合是空集 則稱該集合為一個(gè)二

6、元關(guān)系，記作R。二元關(guān)系也可簡稱為關(guān)系。對于二元關(guān)系R，如果R，可記作xRy；如果R，則記作xRy。設(shè)R1,，R2,a,b。則R1是二元關(guān)系，R2不是二元關(guān)系，只是一個(gè)集合，除非將a和b定義為有序?qū)?。根?jù)上面的記法可以寫1R12，aR1b，aR1c等。 舉例集合A上的二元關(guān)系的數(shù)目依賴于A中的元素?cái)?shù)。如果|A|=n，那么|AA|=n2， AA的子集就有 個(gè)。每一個(gè)子集代表一個(gè)A上的二元關(guān)系，所以A上有 個(gè)不同的二元關(guān)系。例如|A|=3，則A上有 個(gè)不同的二元關(guān)系。7.2 二元關(guān)系定義7.4 設(shè)A，B為集合，AB的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系；特別當(dāng)A=B時(shí)，則叫做A上的二元關(guān)

7、系。 A=0,1，B=1,2,3，那么 R1=，R2=AB，R3= ，R4=等都是從A到B的二元關(guān)系，而R3和R4同時(shí)也是A上的二元關(guān)系。 舉例說明常用的關(guān)系 對任意集合A，定義全域關(guān)系 EA=|xAyA=AA 恒等關(guān)系 IA=|xA空關(guān)系 設(shè) A=1,2，那么EA=,IA=, 舉例其它常用的關(guān)系小于或等于關(guān)系：LA=|x,yAxy，其中 AR。整除關(guān)系：DB=|x,yBx整除y，其中 AZ* Z*是非零整數(shù)集包含關(guān)系：R|x,yAxy，其中 A是集合族。 (1)設(shè) A=1,2,3，Ba,b則 LA=, DA=, (2)令A(yù)=P(B)=,a,b,a,b，則A上的包含關(guān)系是 R, , , 舉例例

8、 設(shè)A=1,2,3,4，下面各式定義的R都是A上的關(guān)系，試用列元素法表示R。(1) R= | x是y的倍數(shù)(2) R= | (x-y)2A(3) R= | x/y是素?cái)?shù)(4) R= | xy 解答(1)R=, (2)R=,(3)R=,(4)R=EA-IA=, , 關(guān)系的表示方法關(guān)系的三種表示方法：集合表達(dá)式關(guān)系矩陣關(guān)系圖關(guān)系矩陣和關(guān)系圖可以表示有窮集上的關(guān)系。關(guān)系矩陣和關(guān)系圖的定義設(shè)A=x1,x2,xn,R是A上的關(guān)系。令 則 是R的關(guān)系矩陣，記作MR。 設(shè)A=x1,x2,xn,R是A上的關(guān)系。令圖G=，其中頂點(diǎn)集合V=A，邊集為E。對于 xi,xjV，滿足 E xiRxj稱圖G為R的關(guān)系圖，

9、記作 GR。關(guān)系矩陣和關(guān)系圖的實(shí)例設(shè) A=1,2,3,4，R=,，則R的關(guān)系矩陣和關(guān)系圖分別是 7.3 關(guān)系的運(yùn)算 設(shè)R是二元關(guān)系。(1)R中所有有序?qū)Φ牡谝辉貥?gòu)成的集合稱為R的定義域(domain)，記為dom R。形式化表示為：dom R x | y(R )(2)R中所有有序?qū)Φ牡诙貥?gòu)成的集合稱為R的值域(range) ，記作ran R。形式化表示為ran Ry | x(R)(3)R的定義域和值域的并集稱為R的域(field)，記作fld R。形式化表示為fld Rdom R ran R 求R=,的定義域、值域和域。 解答dom R1,2,4 ran R2,3,4 fld R1,2,

10、3,4 關(guān)系的逆和右復(fù)合運(yùn)算 設(shè)R為二元關(guān)系，R的逆關(guān)系，簡稱R的逆(inverse)，記作R-1,其中R-1|R 設(shè)F,G為二元關(guān)系，G對F的右復(fù)合(composite)記作FG，其中FG | t(FG) 設(shè)F,G=，則F-1 ,FGGF說明可以把二元關(guān)系看作一種作用，R可以解釋為x通過R的作用變到y(tǒng)。FG表示兩個(gè)作用的連續(xù)發(fā)生。關(guān)系的限制和像 設(shè)R為二元關(guān)系，A是集合(1) R在A上的限制(restriction)記作RA，其中RA=|xRyxA (2) A在R下的像(image)記作RA，其中RA=ran(RA) 說明R在A上的限制RA是R的子關(guān)系。A在R下的像RA是ran R的子集。例

11、設(shè)R，R1，R R2,3，R12,3R R32關(guān)系與集合的說明關(guān)系是集合，集合運(yùn)算對于關(guān)系也是適用的。 規(guī)定：關(guān)系運(yùn)算中逆運(yùn)算優(yōu)先于其它運(yùn)算所有的關(guān)系運(yùn)算都優(yōu)先于集合運(yùn)算，優(yōu)先權(quán)的運(yùn)算以括號決定運(yùn)算順序。 例如：ran F-1FGFHran (FA)例題設(shè)A表示是學(xué)校的所有學(xué)生的集合，B表示學(xué)校的所有課程的集合，并設(shè)R1由所有有序?qū)M成，其中a是選修課程b的學(xué)生。R2由所有的有序?qū)?gòu)成，其中課程b是a的必修課。則關(guān)系R1R2、R1R2、R1R2、R1R2、R2R1的含義為R1R2：a是一個(gè)學(xué)生，他或者選修了課程b，或者課程b是他的必修課。R1R2：a是一個(gè)學(xué)生，他選修了課程b并且課程b也是a的

12、必修課。 R1R2：學(xué)生a已經(jīng)選修了課程b，但課程b不是a的必修課，或者課程b是a的必修課，但是a沒有選修它。R1R2：學(xué)生a已經(jīng)選修了課程b，但課程b不是a的必修課。 R2R1：課程b是學(xué)生a的必修課，但是a沒有選修它。 定理 設(shè)F是任意的關(guān)系，則 (1)(F-1)-1F (2)dom F-1ran F，ran F-1dom F (1)任取，由逆的定義有 (F-1)-1 F-1 F (2)任取x xdom F-1 y(F-1) y(F) xran F 所以有 dom F-1ran F證明定理 設(shè)F，G，H是任意的關(guān)系，則(1)(FG)HF(GH)(2)(FG)-1G-1 F-1證明(1)任取

13、， (FG)H t(FG(t,y)H) t(s(FG)H) ts(FGH) s(Ft(GH) s(FGH) F(GH)定理 設(shè)F，G，H是任意的關(guān)系，則(1)(FG)HF(GH)(2)(FG)-1G-1F-1證明(2)任取， (FG)-1 FG t(FG) t(F-1G-1) G-1 F-1定理定理7.3 設(shè)R為A上的關(guān)系，則R IAIA RR證明(1)任取， R IA t(R(t,y)IA) t(Rty) R R RyA RIA) R IA綜上所述，有 RIAR同理可證 IARR定理 設(shè)F，G，H是任意的關(guān)系，則(1) F(GH)FGFH(2) (GH)FGFHF(3) F(GH)FGFH(

14、4) (GH)FGFHF證明(3) F(GH) t(F(t,y)GH) t(F(t,y)G(t,y)H) t(F(t,y)G) (F(t,y)H) t(F(t,y)G) t(F(t,y)H) FG FH FGFH定理的推論由數(shù)學(xué)歸納法不難證明定理7.4的結(jié)論對于有限多個(gè)關(guān)系的并和交也是成立的，即有R(R1R2Rn)RR1RR2RRn( R1R2Rn)RR1RR2RRnRR(R1R2Rn)RR1RR2RRn ( R1R2Rn)RR1RR2RRnR 定理 設(shè)F為關(guān)系，A,B為集合，則(1) F(AB)FAFB (2) FABFAFB (3) F(AB)FAFB (4) FABFAFB 定理7.5

15、(1)的證明(1) F(AB)FAFB 證明任取， F(AB) F x(AB) F (xAxB) (FxA) (FxB) FA FB FAFB 所以有 F(AB)FAFB。 定理7.5 (4)的證明(4) FABFAFB 證明任取y， yFAB x(FxAB) x(FxAxB) x(FxA)(FxB) x(FxA) x(FxB) yFA yFB yFAFB所以有 FABFAFB 關(guān)系的冪運(yùn)算 設(shè)R為A上的關(guān)系，n為自然數(shù)，則R的n次冪定義為：（1） R0|xAIA（2） Rn+1Rn R說明對于A上的任何關(guān)系R1和R2都有R10R20IA 即：A上任何關(guān)系的0次冪都相等，都等于A上的恒等關(guān)系I

16、A。對于A上的任何關(guān)系R都有R1R，因?yàn)镽1R0 RIA RRRn的計(jì)算給定A上的關(guān)系R和自然數(shù)n，怎樣計(jì)算Rn呢？若n是0或1，結(jié)果是很簡單的。下面考慮n2的情況。如果R是用集合表達(dá)式給出的，可以通過n-1次右復(fù)合計(jì)算得到Rn。如果R是用關(guān)系矩陣M給出的，則Rn的關(guān)系矩陣是Mn，即n個(gè)矩陣M之積。與普通矩陣乘法不同的是，其中的相加是邏輯加，即1+11，1+00+11，0+00如果R是用關(guān)系圖G給出的，可以直接由圖G得到Rn的關(guān)系圖G。G的頂點(diǎn)集與G相同。考察G的每個(gè)頂點(diǎn)xi，如果在G中從xi出發(fā)經(jīng)過n步長的路徑到達(dá)頂點(diǎn)xj，則在G中加一條從xi到xj的邊。當(dāng)把所有這樣的便都找到以后，就得到圖

17、G。 例 設(shè)Aa,b,c,d，R,，求R的各次冪，分別用矩陣和關(guān)系圖表示。 解答例因此M4M2，即R4R2。因此可以得到R2R4R6R3R5R7 用關(guān)系圖的方法得到R0, R1, R2, R3,的關(guān)系圖如下圖所示。冪運(yùn)算的性質(zhì) 設(shè)A為n元集，R是A上的關(guān)系，則存在自然數(shù)s和t,使得Rs=Rt。R為A上的關(guān)系，對任何自然數(shù)k，Rk都是AA的子集。證明又知|AA|=n2，|P(AA)|= ，即AA的不同子集僅 個(gè)。當(dāng)列出R的各次冪R0，R1，R2， ，時(shí)，必存在自然數(shù)s和t使得Rs=Rt。說明該定理說明有窮集上只有有窮多個(gè)不同的二元關(guān)系。當(dāng)t足夠大時(shí)，Rt必與某個(gè)Rs(st)相等。R4=R2。 定

18、理 設(shè)R是A上的關(guān)系，m,nN，則(1)Rm RnRm+n(2)(Rm)nRmn證明(1)對于任意給定的mN,施歸納于n。若n=0，則有所以對一切m,nN有 Rm RnRm+n。Rm R0Rm IARmRm+0假設(shè)Rm Rn=Rm+n，則有Rm Rn+1Rm (Rn R)(Rm Rn)RRm+n+1，定理 設(shè)R是A上的關(guān)系，m,nN，則(1)Rm RnRm+n(2)(Rm)nRmn證明(2)對于任意給定的mN,施歸納于n。若n=0，則有所以對一切m,nN 有(Rm)n=Rmn。(Rm)0IAR0Rm0假設(shè)(Rm)nRmn，則有(Rm)n+1(Rm)n RmRmn+mRm(n+1)定理定理7.8

19、 設(shè)R是A上的關(guān)系，若存在自然數(shù)s,t(st)使得Rs=Rt，則(1) 對任何kN有 Rs+k=Rt+k(2) 對任何k,iN有 Rs+kp+i=Rs+i，其中p=t-s(3) 令S=R0，R1，Rt-1，則對于任意的qN有 RqS證明(1) Rs+kRs RkRt RkRt+k(2)對k歸納。若k=0，則有 Rs+0 p+iRs+i假設(shè) Rs+kp+iRs+i，其中pt-s，則Rs+(k+1)p+iRs+kp+i+pRs+i Rp=Rs+p+iRs+t-s+iRt+iRs+i由歸納法命題得證。Rs+kp+i Rp定理定理7.8 設(shè)R是A上的關(guān)系，若存在自然數(shù)s,t(st)使得Rs=Rt，則(

20、1) 對任何kN有 Rs+k=Rt+k(2) 對任何k,iN有 Rs+kp+i=Rs+i，其中p=t-s(3) 令S=R0，R1，Rt-1，則對于任意的qN有 RqS證明(3)任取qN，若qt，顯然有RqS，若qt，則存在自然數(shù)k和i使得qs+kp+i其中0ip-1,pt-s。于是RqRs+kp+iRs+i而s+is+p-1s+t-s-1t-1這就證明了 RqS。定理的說明有窮集A上的關(guān)系R的冪序列R0，R1，是一個(gè)周期性變化的序列。就象正弦函數(shù)一樣，利用它的周期性可以將R的高次冪化簡為R的低次冪。 設(shè)A=a,b,d,e,f，R=,。求出最小的自然數(shù)m和n，使得mn且Rm=Rn。 解答由R的定

21、義可以看出A中的元素可分成兩組，即a,b和d,e,f。它們在R的右復(fù)合運(yùn)算下有下述變化規(guī)律：ababdefdef對于a或b,每個(gè)元素的變化周期是2。對于d，e，f，每個(gè)元素的變化周期是3。因此必有Rm=Rm+6，其中6是2和3的最小公倍數(shù)。取m=0,n=6即滿足題目要求。7.4 關(guān)系的性質(zhì)自反性反自反性對稱性反對稱性傳遞性自反性和反自反性 設(shè)R為A上的關(guān)系，(1)若x(xAR)，則稱R在A上是自反(reflexivity)的。(2)若x(xAR)，則稱R在A上是反自反(irreflexivity)的。例如 全域關(guān)系EA，恒等關(guān)系IA，小于等于關(guān)系LA，整除關(guān)系DA都是為A上的自反關(guān)系。包含關(guān)系

22、R是給定集合族A上的自反關(guān)系。小于關(guān)系和真包含關(guān)系都是給定集合或集合族上的反自反關(guān)系。例 設(shè)A=1,2,3，R1，R2，R3是A上的關(guān)系，其中R1,R2,R3說明R1，R2和R3是否為A上的自反關(guān)系和反自反關(guān)系。解答 R1既不是自反的也不是反自反的，R2是自反的，R3是反自反的。對稱性和反對稱性 設(shè)R為A上的關(guān)系，（1）若xy(x,yARR)，則稱R為A上對稱(symmetry)的關(guān)系。（2）若xy(x,yARRx=y)，則稱R為A上的反對稱(antisymmetry)關(guān)系。 例如 A上的全域關(guān)系EA，恒等關(guān)系IA和空關(guān)系都是A上的對稱關(guān)系。恒等關(guān)系IA和空關(guān)系也是A上的反對稱關(guān)系。但全域關(guān)系

23、EA一般不是A上的反對稱關(guān)系，除非A為單元集或空集。例 設(shè)A1,2,3，R1，R2，R3和R4都是A上的關(guān)系，其中R1,R2,R3,R4,說明R1，R2，R3和R4是否為A上對稱和反對稱的關(guān)系。解答 R1既是對稱也是反對稱的。R2是對稱的但不是反對稱的。R3是反對稱的但不是對稱的。R4既不是對稱的也不是反對稱的。傳遞性 設(shè)R為A上的關(guān)系，若xyz(x,y,zARRR)則稱R是A上的傳遞(transitivity)關(guān)系。例如 A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系都是A上的傳遞關(guān)系。小于等于關(guān)系，整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的傳遞關(guān)系。小于關(guān)系和真包含關(guān)系仍舊是相應(yīng)集合上的傳遞關(guān)系。 例

24、設(shè)A1,2,3，R1，R2，R3是A上的關(guān)系，其中R1,R2,R3說明R1，R2和R3是否為A上的傳遞關(guān)系。解答 R1和R3是A上的傳遞關(guān)系，R2不是A上的傳遞關(guān)系。 關(guān)系性質(zhì)的等價(jià)描述 設(shè)R為A上的關(guān)系，則（1）R在A上自反當(dāng)且僅當(dāng) IA R（2）R在A上反自反當(dāng)且僅當(dāng) RIA（3）R在A上對稱當(dāng)且僅當(dāng) RR-1（4）R在A上反對稱當(dāng)且僅當(dāng) RR-1 IA（5）R在A上傳遞當(dāng)且僅當(dāng) RRR 說明利用該定理可以從關(guān)系的集合表達(dá)式來判斷或證明關(guān)系的性質(zhì)。分析關(guān)系性質(zhì)的證明方法定理7.9 (1)的證明（1） R在A上自反當(dāng)且僅當(dāng) IA R必要性。 任取，有 IA x,yA xy R 所以 IA R

25、充分性。 任取x，有 xA IA R 所以 R在A上是自反的。定理7.9 (2)的證明（2）R在A上反自反當(dāng)且僅當(dāng) RIA充分性。 任取x，有 xA IA R (RIA= ) 所以 R在A上是反自反的。必要性。用反證法。 假設(shè)RIA， 必存在RIA。 由于IA是A上恒等關(guān)系， 可知 xA且R。 這與R在A上是反自反的相矛盾。定理7.9 (3)的證明（3） R在A上對稱當(dāng)且僅當(dāng) RR-1必要性。任取，有 R R(因?yàn)镽在A上對稱) R-1 所以 RR-1充分性。 任取， 由 RR-1 得 R R-1 R 所以 R在A上是對稱的。定理7.9 (4)的證明（4） R在A上反對稱當(dāng)且僅當(dāng) RR-1 I

26、A必要性。 任取，有 RR-1 R R-1 R R xy (R是反對稱的) IA所以 RR-1 IA充分性。任取, R R R R-1 RR-1 IA (RR-1 IA) xy所以 R在A上是反對稱的。定理7.9 (5)的證明（5） R在A上傳遞當(dāng)且僅當(dāng) RRR必要性。任取，有 RR t(RR) R(因?yàn)镽在A上是傳遞的)所以 RRR。充分性。任取,R，則 RR RR R (因?yàn)镽RR)所以 R在A上是傳遞的。例 設(shè)A是集合，R1和R2是A上的關(guān)系，證明：(1)若R1，R2是自反的和對稱的，則R1R2也是自反的和對稱的。(2)若R1和R2是傳遞的，則R1R2也是傳遞的。例7.13 (1)的證明

27、(1)若R1，R2是自反的和對稱的，則R1R2也是自反的和對稱的。證明由于R1和R2是A上的自反關(guān)系，故有IA R1 和 IA R2從而得到 IA R1R2。根據(jù)定理7.9可知 R1R2在A上是自反的。再由R1和R2的對稱性有R1R1-1 和 R2R2-1根據(jù)練習(xí)七第18題的結(jié)果有(R1R2)-1R1-1R2-1R1R2從而證明了R1R2也是A上對稱的關(guān)系。例7.13 (2)的證明(2)若R1和R2是傳遞的，則R1R2也是傳遞的。證明由R1和R2的傳遞性有R1 R1 R1 和 R2 R2 R2 (R1R2)(R1R2) R1 R1R1 R2R2 R1R2 R2 (R1R2)R1 R2R2 R1

28、 (將前面的包含式代入) R1R2從而證明了R1R2也是A上的傳遞關(guān)系。 關(guān)系性質(zhì)的特點(diǎn)自反性反自反性對稱性反對稱性傳遞性集合表達(dá)式IA RRIARR-1RR-1 IARRR關(guān)系矩陣主對角線元素全是1主對角線元素全是0 矩陣是對稱矩陣 若rij1，且ij，則rji0 對M2中1所在位置，M中相應(yīng)的位置都是1 關(guān)系圖每個(gè)頂點(diǎn)都有環(huán)每個(gè)頂點(diǎn)都沒有環(huán) 如果兩個(gè)頂點(diǎn)之間有邊，一定是一對方向相反的邊(無單邊) 如果兩點(diǎn)之間有邊，一定是一條有向邊(無雙向邊) 如果頂點(diǎn)xi到xj有邊，xj到xk有邊，則從xi到xk也有邊 例 判斷下圖中關(guān)系的性質(zhì)，并說明理由。 （1）對稱的，不是自反的，不是反自反的，不是反

29、對稱的，不是傳遞的。（2）是反自反的，不是自反的，是反對稱的，不是對稱的，是傳遞的。（3）是自反的，不是反自反的，是反對稱的，不是對稱的，不是傳遞的。關(guān)系的性質(zhì)和運(yùn)算之間的關(guān)系自反性反自反性對稱性反對稱性傳遞性R1-1R1R2R1R2R1R2R1 R27.5 關(guān)系的閉包閉包（closure）的定義閉包的構(gòu)造方法閉包的性質(zhì)閉包的相互關(guān)系閉包的定義 設(shè)R是非空集合A上的關(guān)系，R的自反（對稱或傳遞）閉包是A上的關(guān)系R，使得 R滿足以下條件：（1）R是自反的（對稱的或傳遞的）（2）RR（3）對A上任何包含R的自反（對稱或傳遞）關(guān)系R有R R。一般將R的自反閉包記作r(R)，對稱閉包記作s(R)，傳遞閉

30、包記作t(R)。閉包的構(gòu)造方法 設(shè)R為A上的關(guān)系，則有（1）r(R)RR0（2）s(R)RR-1（3）t(R)RR2R3 證明思路(1)和(2)：證明右邊的集合滿足閉包定義的三個(gè)條件。(3)采用集合相等的證明方法。證明左邊包含右邊，即t(R)包含每個(gè)Rn。證明右邊包含左邊，即RR2具有傳遞的性質(zhì)。 定理7.10 (1)的證明（1）r(R)RR0證明由IAR0 RR0，可知RR0是自反的，RRR0。設(shè)R是A上包含R的自反關(guān)系， 則有RR和IAR。 任取，必有 RR0 RIA RRR 所以 RR0 R。綜上所述，r(R)RR0。定理7.10 (2)的證明（2）s(R)RR-1證明 RRR-1。證明

31、RR-1是對稱的， 任取，有 RR-1 RR-1 R-1R RR-1 所以 RR-1 是對稱的。綜上所述，s(R)RR-1。設(shè)R是包含R的對稱關(guān)系， 任取，有 RR-1 RR-1 RR RR RR R 所以 RR-1 R。定理7.10 (3)的證明（3）t(R)RR2R3 證明先證RR2 t(R)成立，為此只需證明對任意的正整數(shù)n有 Rn t(R)即可。用歸納法。n1時(shí)，有 R1R t(R)。假設(shè)Rnt(R)成立，那么對任意的有 Rn+1Rn R t(RnR) t(t(R)t(R) t(R) （因?yàn)閠(R)是傳遞的）這就證明了Rn+1 t(R)。由歸納法命題得證。定理7.10 (3)的證明（3

32、）t(R)RR2R3 證明再證t(R)RR2成立，為此只須證明RR2是傳遞的。任取,，則 RR2 RR2 t(Rt) s(Rs) ts(Rt Rs) ts(Rt Rs) ts(Rt+s) RR2從而證明了RR2是傳遞的。推論推論 設(shè)R為有窮集A上的關(guān)系，則存在正整數(shù)r使得t(R)=RR2Rr證明 由定理7.6和7.10(3)得證。 例題 求整數(shù)集合Z上的關(guān)系R | ab的自反閉包和對稱閉包。解答 r(R)RR0|ab|ab |ab s(R)RR-1|ab|ba |ab通過關(guān)系矩陣求閉包的方法設(shè)關(guān)系R，r(R)，s(R)，t(R)的關(guān)系矩陣分別為M，Mr，Ms和Mt，則Mr ME對角線上的值都改

33、為1Ms MM若aij1，則令aji1Mt MM2M3沃舍爾算法其中E是和M同階的單位矩陣，M是M的轉(zhuǎn)置矩陣。注意在上述等式中矩陣的元素相加時(shí)使用邏輯加。通過關(guān)系圖求閉包的方法設(shè)關(guān)系R，r(R)，s(R)，t(R)的關(guān)系圖分別記為G，Gr，Gs，Gt，則Gr，Gs，Gt的頂點(diǎn)集與G的頂點(diǎn)集相等。除了G的邊以外，以下述方法添加新的邊。1)考察G的每個(gè)頂點(diǎn)，如果沒有環(huán)就加上一個(gè)環(huán)。最終得到的是Gr。2)考察G的每一條邊，如果有一條xi到xj的單向邊，ij，則在G中加一條邊xj到xi的反方向邊。最終得到Gs。3)考察G的每個(gè)頂點(diǎn)xi，找出從xi出發(fā)的所有2步，3步，n步長的路徑（n為G中的頂點(diǎn)數(shù)）。

34、設(shè)路徑的終點(diǎn)為 。如果沒有從xi到 (l=1,2,k)的邊，就加上這條邊。當(dāng)檢查完所有的頂點(diǎn)后就得到圖Gt。例 設(shè)A=a,b,c,d，R=,，則R和r(R)，s(R)，t(R)的關(guān)系圖如下圖所示。其中r(R)，s(R)，t(R)的關(guān)系圖就是使用上述方法直接從R的關(guān)系圖得到的。 Warshall 算法輸入：M（R的關(guān)系矩陣）輸出：MT（t(R)的關(guān)系矩陣）1.MTM2.for k 1 to n do3.for i 1 to n do4.for j 1 to n do5. MTi,jMTi,j+MTi,k*MTk,j注意：算法中矩陣加法和乘法中的元素相加都使用邏輯加。Warshall 算法 舉例例

35、 設(shè)A=a,b,c,d，R=,， 求t(R)。分析 k1 時(shí)，MTi,jMTi,j+MTi,1*MT1,j MT1,jMT1,j+MT1,1*MT1,j MT2,jMT2,j+MT2,1*MT1,j 將第1行加到第2行上 MT3,jMT3,j+MT3,1*MT1,j MT4,jMT4,j+MT4,1*MT1,j 得到M1。Warshall 算法 舉例k1時(shí)，第1列中只有M2,11，將第1行加到第2行上。k2時(shí)，第2列中M1,2 M2,2M4,21，將第2行分別加到第1,2,4行上。Warshall 算法 舉例k3時(shí)，第3列中M1,3M2,3M4,31，將第3行分別加到第1,2,4行上。k4時(shí)，

36、第4列中M1,4 M2,4M3,4M4,41，將第4行分別加到第1,2,3,4行上。閉包的主要性質(zhì) 設(shè)R是非空集合A上的關(guān)系，則（1）R是自反的當(dāng)且僅當(dāng)r(R)R。（2）R是對稱的當(dāng)且僅當(dāng)s(R)R。（3）R是傳遞的當(dāng)且僅當(dāng)t(R)R。證明 （1）充分性。 因?yàn)镽r(R)，所以R是自反的。必要性。顯然有R r(R)。由于R是包含R的自反關(guān)系，根據(jù)自反閉包定義有r(R)R。從而得到r(R)=R。閉包的主要性質(zhì) 設(shè)R1和R2是非空集合A上的關(guān)系，且R1 R2，則（1）r(R1) r(R2)（2）s(R1) s(R2)（3）t(R1) t(R2)證明：(1)任取，有 r(R1) R1IA R1 IA

37、 R2 IA R2IA r(R2)命題命題若R是對稱的，則Rn也是對稱的，其中n是任何正整數(shù)。證明用歸納法。n=1，R1R顯然是對稱的。假設(shè)Rn是對稱的，則對任意的，有 Rn+1 Rn R t(RnR) t(RnR) RRn R1+nRn+1所以Rn+1是對稱的。由歸納法命題得證。關(guān)系性質(zhì)與閉包運(yùn)算之間的聯(lián)系 設(shè)R是非空集合A上的關(guān)系，（1）若R是自反的，則s(R)與t(R)也是自反的。（2）若R是對稱的，則r(R)與t(R)也是對稱的。（3）若R是傳遞的，則r(R)是傳遞的。證明：只證（2）。 定理7.13 (2)的證明（2）若R是對稱的，則r(R)與t(R)也是對稱的。證明r(R)是對稱的

38、。由于R是A上的對稱關(guān)系，所以RR-1，同時(shí)IAIA-1。r(R)-1(RR0)-1(RIA)-1R-1IA-1RIAr(R)所以，r(R)是對稱的。定理7.13 (2)的證明（2）若R是對稱的，則r(R)與t(R)也是對稱的。下面證明t(R)的對稱性。任取 t(R) n(Rn) n(Rn) （因?yàn)镽n是對稱的） t(R)所以，t(R)是對稱的。定理的討論從這里可以看出，如果計(jì)算關(guān)系R的自反、對稱、傳遞的閉包，為了不失去傳遞性，傳遞閉包運(yùn)算應(yīng)該放在對稱閉包運(yùn)算的后邊，若令tsr(R)表示R的自反、對稱、傳遞閉包，則tsr(R)=t(s(r(R) 自反性對稱性傳遞性r(R)s(R)(反例)t(R

39、)反例 A=1，2，3，R= 是傳遞的s(R)=,顯然s(R)不是傳遞的。7.6 等價(jià)關(guān)系與劃分 設(shè)R為非空集合上的關(guān)系。如果R是自反的、對稱的和傳遞的，則稱R為A上的等價(jià)關(guān)系(equivalent relation)。設(shè)R是一個(gè)等價(jià)關(guān)系，若R，稱x等價(jià)于y，記做xy。 舉例 (1)平面上三角形集合中，三角形的相似關(guān)系。(2)人群中的同性關(guān)系。例 設(shè)A1,2,8，如下定義A上的關(guān)系R：R|x，yAxy(mod 3)其中xy(mod 3)叫做x與y模3相等，即x除以3的余數(shù)與y除以3的余數(shù)相等。不難驗(yàn)證R為A上的等價(jià)關(guān)系，因?yàn)閤A，有xx(mod 3)x,yA，若xy(mod 3)，則有yx(m

40、od 3)x,y,zA，若xy(mod 3)，yz(mod 3)，則有xz(mod 3)等價(jià)類 設(shè)R為非空集合A上的等價(jià)關(guān)系，xA，令xR=y|yAxRy稱xR為x關(guān)于R的等價(jià)類，簡稱為x的等價(jià)類，簡記為x或 x 。x的等價(jià)類是A中所有與x等價(jià)的元素構(gòu)成的集合。 例7.16中的等價(jià)類是：1471,4,72582,5,8363,6 整數(shù)集合Z上的模n等價(jià)關(guān)系設(shè)x是任意整數(shù)，n為給定的正整數(shù)，則存在唯一的整數(shù)q和r，使得xqn+r其中0rn-1，稱r為x除以n的余數(shù)。例如n3，那么8除以3的余數(shù)為1，因?yàn)?-8-33+1對于任意的整數(shù)x和y，定義模n相等關(guān)系xy xy(mod n)不難驗(yàn)證它是整數(shù)

41、集合Z上的等價(jià)關(guān)系。將Z中的所有整數(shù)根據(jù)它們除以n的余數(shù)分類如下：余數(shù)為0的數(shù)，其形式為nz，zZ余數(shù)為1的數(shù)，其形式為nz+1，zZ 余數(shù)是n-1的數(shù)，其形式為nz+n-1，zZ以上構(gòu)成了n個(gè)等價(jià)類，使用等價(jià)類的符號可記為inz+i|zZ，i=0，1，n-1等價(jià)類的性質(zhì) 設(shè)R是非空集合A上的等價(jià)關(guān)系，則（1）xA，x是A的非空子集。（2）x,yA，如果xRy，則xy。（3）x,yA，如果R，則x與y不交。（4）x|xAA。證明（1） 由等價(jià)類的定義可知， xA有xA。又由于等價(jià)關(guān)系的自反性有xx，即x非空。 定理（2）x,yA，如果xRy，則x=y。任取z，則有 zx R R(因?yàn)镽是對稱的

42、) R R R(因?yàn)镽是傳遞的) R (因?yàn)镽是對稱的) zy。所以 xy。同理可證 yx。因此，x=y。定理（3）x,yA，如果R，則x與y不交。假設(shè) xy ，則存在 zxy，從而有 zxzy，即RR成立。根據(jù)R的對稱性和傳遞性，必有R，與R矛盾，即假設(shè)錯誤，原命題成立。 定理（4）x|xAA。 先證 x|xAA任取y，yx|xA x(xAyx) yA (因?yàn)閤A)從而有x|xA A。再證 Ax|xA任取y，yA yyyA yx|xA從而有Ax|xA成立。綜上所述得 x|xAA。商集 設(shè)R為非空集合A上的等價(jià)關(guān)系，以R的所有等價(jià)類作為元素的集合稱為A關(guān)于R的商集(quotient set)，

43、記做A/R，即A/R=xR|xA1,4,7,2,5,8,3,6整數(shù)集合Z上模n等價(jià)關(guān)系的商集是nz+i|zZ|i=0,1,n-1劃分 設(shè)A為非空集合，若A的子集族(P(A)，是A的子集構(gòu)成的集合) 滿足下面的條件：（1）（2）xy(x,yxyxy)（3）=A則稱是A的一個(gè)劃分(partitions)，稱中的元素為A的劃分塊。說明設(shè)集合是A的非空子集的集合，若這些非空子集兩兩不相交，且它們的并等于A，則稱是集合A的劃分。例 設(shè)Aa,b,c,d，給定1,2,3,4,5,6,如下：1=a,b,c,d2=a,b,c,d3=a,a,b,c,d4=a,b,c5=,a,b,c,d6=a,a,b,c,d判斷哪

44、一個(gè)是A的劃分1和2是A的劃分，其它都不是A的劃分。因?yàn)?中的子集a和a,b,c,d有交，4A，5中含有空集，而6根本不是A的子集族。商集與劃分商集就是A的一個(gè)劃分，并且不同的商集將對應(yīng)于不同的劃分。反之，任給A的一個(gè)劃分，如下定義A上的關(guān)系R：R=|x,yAx與y在的同一劃分塊中則不難證明R為A上的等價(jià)關(guān)系，且該等價(jià)關(guān)系所確定的商集就是。由此可見，A上的等價(jià)關(guān)系與A的劃分是一一對應(yīng)的。 例 給出A1,2,3上所有的等價(jià)關(guān)系這些劃分與A上的等價(jià)關(guān)系之間的一一對應(yīng)是：1對應(yīng)于全域關(guān)系EA，5的對應(yīng)于恒等關(guān)系IA，2，3和4分別對應(yīng)于等價(jià)關(guān)系R2，R3和R4。 其中 R2=,IAR3=,IAR4=

45、,IA例題例題 問集合Aa,b,c,d上有多少個(gè)不同的等價(jià)關(guān)系？解答 只要求出A上的全部劃分，即為等價(jià)關(guān)系。劃分為一個(gè)塊的情況：1種，即a,b,c,d劃分為兩個(gè)塊的情況：7種，即a,b,c,d，a,c,b,d，a,d,b,ca,b,c,d，b,a,c,d，c,a,b,d，d,a,b,c劃分為三個(gè)塊的情況：6種，即a,b,c,d，a,c,b,d，a,d,b,c,a,b,c,d，a,c,b,d，a,d,b,c劃分為四個(gè)塊的情況：1種，即a,b,c,d因此，共有15種不同的等價(jià)關(guān)系。7.7 偏序(partial order)關(guān)系 設(shè)R為非空集合A上的關(guān)系。如果R是自反的、反對稱的和傳遞的，則稱R為A

46、上的偏序關(guān)系，記作。設(shè)為偏序關(guān)系，如果，則記作xy，讀作“x小于或等于y”。注意 這里的“小于或等于”不是指數(shù)的大小，而是在偏序關(guān)系中的順序性。x“小于或等于”y的含義是：依照這個(gè)序，x排在y的前邊或者x就是y。根據(jù)不同偏序的定義，對序有著不同的解釋。偏序關(guān)系舉例集合A上的恒等關(guān)系IA小于或等于關(guān)系整除關(guān)系包含關(guān)系 可比 設(shè)R為非空集合A上的偏序關(guān)系，定義(1) x,yA，xy xyxy。(2) x,yA，x與y可比 xyyx。其中xy讀作x“小于”y。這里所說的“小于”是指在偏序中x排在y的前邊。在具有偏序關(guān)系的集合A中任取兩個(gè)元素x和y，可能有下述幾種情況發(fā)生：xy(或yx)，xy，x與y

47、不是可比的。例如A1，2，3，是A上的整除關(guān)系，則有12，13，1=1，2=2，3=3，2和3不可比。全序關(guān)系 設(shè)R為非空集合A上的偏序關(guān)系，如果x,yA，x與y都是可比的，則稱R為A上的全序關(guān)系(或線序關(guān)系)。例如數(shù)集上的小于或等于關(guān)系是全序關(guān)系，因?yàn)槿魏蝺蓚€(gè)數(shù)總是可比大小的。整除關(guān)系一般來說不是全序關(guān)系，如集合1,2,3上的整除關(guān)系就不是全序關(guān)系，因?yàn)?和3不可比。 偏序集 集合A和A上的偏序關(guān)系一起叫做偏序集，記作。例如 整數(shù)集合Z和數(shù)的小于或等于關(guān)系構(gòu)成偏序集集合A的冪集P(A)和包含關(guān)系R構(gòu)成偏序集。覆蓋(cover) 設(shè)為偏序集。 x,yA，如果 xy 且不存在 zA使得xzy，則

48、稱y覆蓋x。例如 1,2,4,6集合上的整除關(guān)系，有2覆蓋1，4和6都覆蓋2。但4不覆蓋1，因?yàn)橛?24。6也不覆蓋4，因?yàn)?6不成立。哈斯圖(Hasse diagram)利用偏序關(guān)系的自反性、反對稱性和傳遞性所得到的偏序集合圖，稱為哈斯圖。畫偏序集的哈斯圖的方法(1)用小圓圈代表元素。(2)x,yA，若xy，則將x畫在y的下方。(3)對于A中的兩個(gè)不同元素x和y，如果y覆蓋x，就用一條線段連接x和y。例 畫出偏序集和的哈斯圖。 例 已知偏序集的哈斯圖如右圖所示，試求出集合A和關(guān)系R的表達(dá)式。 解答A=a,b,c,d,e,f,g,hR=,IA 偏序集中的特殊元素 設(shè)為偏序集，BA，yB。（1）

49、若x(xByx)成立，則稱y為B的最小元。（2）若x(xBxy)成立，則稱y為B的最大元。（3）若x(xBxyxy)成立，則稱y為B的極小元。（4）若x(xByxxy)成立，則稱y為B的極大元。363242126B最大元最小元極大元極小元2,3,6,12,24,366,122,3,66無 無 24,26 2,312 6 12 6 6 無 6 2,3 6 6 6 6特殊元素的性質(zhì)最小元是B中最小的元素，它與B中其它元素都可比。極小元不一定與B中元素可比，只要沒有比它小的元素，它就是極小元。對于有窮集B，極小元一定存在，但最小元不一定存在。最小元如果存在，一定是唯一的。極小元可能有多個(gè)，但不同的極

50、小元之間是不可比的（無關(guān)系）。如果B中只有一個(gè)極小元，則它一定是B的最小元。哈斯圖中，集合B的極小元是B中各元素中的最底層。例 設(shè)偏序集如右圖所示，求A的極小元、最小元、極大元、最大元。 解答極小元：a,b,c,g極大元：a,f,h。沒有最小元與最大元說明哈斯圖中的孤立頂點(diǎn)既是極小元也是極大元。 例 設(shè)X為集合，AP(X)X，且A。若|X|n，問：（1）偏序集是否存在最大元？（2）偏序集是否存在最小元？（3）偏序集中極大元和極小元的一般形式是什么？并說明理由。解答 不存在最小元和最大元，因?yàn)閚2?？疾靸缂疨(X)的哈斯圖，最底層的頂點(diǎn)是空集，記作第0層。由底向上，第1層是單元集，第2層是二元子

51、集，由|X|=n，則第n1層是X的n1元子集，第n層，也就是最高層只有一個(gè)頂點(diǎn)X。偏序集與相比，恰好缺少第0層與第n層(因?yàn)閄是n元集)。因此的極小元就是X的所有單元集，即x，xX；而極大元恰好少一個(gè)元素，即X-x，xX。 上界、下界 設(shè)為偏序集，BA，yA。（1）若 x(xBxy)成立，則稱y為B的上界。（2）若 x(xByx)成立，則稱y為B的下界。（3）令Cy|y為B的上界，則稱C的最小元為B的最小上界或上確界。（4）令Dy|y為B的下界，則稱D的最大元為B的最大下界或下確界。 上界與下界舉例363242126B上界下界上確界下確界2,3,6,12,24,366,122,3,66 無 無 無 無12,24,36 2,3,6 12 66,12,24,36 無 6 無6,