二元關系PPT學習教案

1、會計學1二元關系二元關系q 本章的主要內(nèi)容 有序?qū)εc笛卡兒集 二元關系的定義和表示法 關系的運算 關系的性質(zhì) 等價關系與劃分 偏序關系q 本章與后續(xù)各章的關系 本章是函數(shù)的基礎 本章是圖論的基礎 第1頁/共128頁第2頁/共128頁（2）的充分必要條件是xu且yv。說明q有序?qū)χ械脑厥怯行虻膓集合中的元素是無序的第3頁/共128頁例7.1 已知，求x和y。 由有序?qū)ο嗟鹊某湟獥l件有由有序?qū)ο嗟鹊某湟獥l件有 x+2x+25 5 2 2x+yx+y4 4 解得解得 x x3,y3,y-2-2。 解答第4頁/共128頁qA A表示某大學所有學生的集合，表示某大學所有學生的集合，B B表示大學開設的

2、所表示大學開設的所有課程的集合，有課程的集合，則則A AB B可以用來表示該校學生選課的所有可能情況可以用來表示該校學生選課的所有可能情況。q令令A A是直角坐標系中是直角坐標系中x x軸上的點集，軸上的點集，B B是直角坐標系中是直角坐標系中y y軸上的點集，軸上的點集，于是于是A AB B就和平面點集一一對應。就和平面點集一一對應。 舉例第5頁/共128頁設設A=a,b, B=0,1,2A=a,b, B=0,1,2，則則A AB=,B=,B BA=, A=, 舉例說明q如果|A|=m,|B|=n,則|AB|=mn。第6頁/共128頁分配律，即A(BC)=(AB)(AC)(BC)A=(BA)

3、(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)(5)AC BD AB CD第7頁/共128頁第8頁/共128頁 CD xCyD xC從而證明了 AC。同理可證 BD。第9頁/共128頁第10頁/共128頁例7.2 設A=1,2,求P(A)A。 P(A)P(A)A A ,1,2,1,2,1,2,1,21,21,2 ,2, , 解答第11頁/共128頁例7.3 設A，B，C，D為任意集合，判斷以下命題是否為真，并說明理由。(1) ABAC BC(2) A-(BC)(A-B)(A-C)(3) ABCD ACBD(4) 存在集合A，使得A = AA(1) (1) 不一定為真。當不一定

4、為真。當A A，B B1,C1,C22時，有時，有 A AB BA AC C，但但BCBC。(2) (2) 不一定為真。當不一定為真。當A=B=1,CA=B=1,C22時，有時，有 A-(B A-(BC)C)1111 ( (A-B)A-B)(A-C)(A-C)11(3) (3) 為真。由等量代入的原理可證。為真。由等量代入的原理可證。 (4) (4) 為真。當為真。當A A時，有時，有 A A= =A AA A 成立。成立。 解答第12頁/共128頁定義定義7.37.3 如果一個集合滿足以下條件之一：如果一個集合滿足以下條件之一：（1 1）集合非空，且它的元素都是有序?qū)Γ┘戏强?，且它的元素?/p>

5、是有序?qū)Γ? 2）集合是空集）集合是空集 則稱該集合為一個則稱該集合為一個二元關系二元關系，記作，記作R R。二元關系也可簡稱為二元關系也可簡稱為關系關系。對于二元關系。對于二元關系R R，如果如果 Rx,yR，可記作可記作xRyxRy；如果如果 x,y R R，則記作則記作xRyxRy。設設R R1 1,，R R2 2,a,b,a,b。則則R R1 1是二元關系，是二元關系，R R2 2不是二元關系，只是一個集合，不是二元關系，只是一個集合，除非將除非將a a和和b b定義為有序?qū)Α６x為有序?qū)?。根?jù)上面的記法可以寫根據(jù)上面的記法可以寫1 1R R1 12 2，aRaR1 1b b，aRaR

6、1 1c c等。等。 舉例第13頁/共128頁集合A上的二元關系的數(shù)目依賴于A中的元素數(shù)。如果|A|=n，那么|AA|=n2， AA的子集就有 個。每一個子集代表一個A上的二元關系，所以A上有 個不同的二元關系。例如|A|=3，則A上有 個不同的二元關系。定義定義7.4 7.4 設設A A，B B為集合，為集合，A AB B的任何子集所定義的二元關系叫做的任何子集所定義的二元關系叫做從從A A到到B B的二元關系的二元關系；特別當；特別當A=BA=B時，則叫做時，則叫做A A上的二元關系上的二元關系。 A=0,1A=0,1，B=1,2,3B=1,2,3，那么那么 R R1 1=，R R2 2=

7、A=AB B，R R3 3= = ，R R4 4=等都是從等都是從A A到到B B的二元關系，而的二元關系，而R R3 3和和R R4 4同時也是同時也是A A上的上的二元關系。二元關系。 舉例22n22n232說明第14頁/共128頁設設 A=1,2A=1,2，那么那么E EA A=,=,I IA A=,=, 舉例第15頁/共128頁(1)(1)設設 A=1,2,3A=1,2,3，B Ba,ba,b則則 L LA A=,=, D DA A=, =, (2)(2)令令A=P(B)=A=P(B)=,a,b,a,b,a,b,a,b，則則A A上的包含關系是上的包含關系是 R R ,a,b, , ,

8、 , , 舉例第16頁/共128頁解答(1)(1)R=, R=, (2)(2)R=,R=,(3)(3)R=,R=,(4)R=E(4)R=EA A-I-IA A=,=, , , 第17頁/共128頁第18頁/共128頁設設A=xA=x1 1,x,x2 2, ,x,xn n,R,R是是A A上的關系。令上的關系。令 n)n), ,1,2,1,2,j j(i,(i,RxRx若x若x0 0RxRx若x若x1 1 r rj ji ij ji iij ijnnnnn2n2n1n12n2n222221211n1n12121111ij ijr rr rr rr rr rr rr rr rr r) )(r (r

9、則則 是是R R的的關系矩陣關系矩陣，記作，記作M MR R。 設設A=xA=x1 1,x,x2 2, ,x,xn n,R,R是是A A上的關系。令圖上的關系。令圖G=G=，其中頂點其中頂點集合集合V=AV=A，邊集為邊集為E E。對于對于 x xi i,x,xj jVV，滿足滿足 E E x xi iRxRxj j稱圖稱圖G G為為R R的的關系圖關系圖，記作，記作 G GR R。第19頁/共128頁設設 A=1,2,3,4A=1,2,3,4，R=,R=,，則則R R的關系矩陣和關系圖分別是的關系矩陣和關系圖分別是 0 00 01 10 00 00 00 00 01 11 10 00 00

10、00 01 11 1MMR R第20頁/共128頁x(R)(3)R的定義域和值域的并集稱為R的域(field)，記作fld R。形式化表示為fld Rdom R ran R 例7.5 求R=,的定義域、值域和域。 解答dom R1,2,4 ran R2,3,4 fld R1,2,3,4 第21頁/共128頁,G=，則F-1 ,FGGF說明q可以把二元關系看作一種作用，R可以解釋為x通過R的作用變到y(tǒng)。qFG表示兩個作用的連續(xù)發(fā)生。第22頁/共128頁說明qR在A上的限制RA是R的子關系。qA在R下的像RA是ran R的子集。第23頁/共128頁設設R R，R1，R R2,3 ，R12,3R R

11、32第24頁/共128頁nran F-1nFGFHnran (FA)第25頁/共128頁anR1 R2：學生a已經(jīng)選修了課程b，但課程b不是a的必修課，或者課程b是a的必修課，但是a沒有選修它。nR1R2：學生a已經(jīng)選修了課程b，但課程b不是a的必修課。nR2R1：課程b是學生a的必修課，但是a沒有選修它。第26頁/共128頁(1)(1)任取任取 x,y，由逆的定義有由逆的定義有 x,y(F(F-1-1) )-1-1 F F-1-1 F F (2)(2)任取任取x x x xdom dom F F-1-1 y y(x,(FF-1-1) ) y y(F) ,xF) xran F xran F 所

12、以有所以有 dom Fdom F-1-1ran Fran F證明第27頁/共128頁證明(1)(1)任取任取 x,y， x,y( (F F G)G) H H t t(x,(FF G(G(t t,y)H),y)H) t t( ( s s(x,(FFG)G)H),yH) t t s s(x,(FFGGH),yH) s s(x,(FF t t(GGH) ,yH) s s(x,(FFG,yG H) H) x,yF F ( (G G H)H)第28頁/共128頁證明(2)(2)任取任取 x,y， x,y(F(F G)G)-1-1 FF G G t t(y,(FFG),xG) t t(F,yF-1-1x,

13、GG-1-1) ) G G-1 -1 F F-1-1第29頁/共128頁證明(1)(1)任取任取 x,y， x,y R R I IA A t(x,t(R(R(t t,y)I,y)IA A) ) t(x,t(RRt ty)y) R R x,yR R RyARyA RI RIA A) ) R R I IA A綜上所述，有綜上所述，有 R R I IA AR R同理可證同理可證 I IA A R RR R第30頁/共128頁證明(3) (3) x,yF F ( (GH)GH) t t(x,(F(F(t t,y)GH),y)GH) t t(x,(F(F(t t,y)G(,y)G(t t,y)H),y)

14、H) t t( ( (x,F(F(t t,y)G,y)G) ) ( (x,F(F(t t,y)H,y)H) ) ) t t(x,(F(F(t t,y)G) ,y)G) t t(x,(F(F(t t,y)H),y)H) F F G G F F H H x,yF F GFGF H H第31頁/共128頁第32頁/共128頁第33頁/共128頁證明任取任取 x,y， F(AB) F(AB) F x(AB) F x(AB) F (xAxB) F (xAxB) (FxA) (FxB) (FxA) (FxB) F FA FA FB B F FAFAFB B 所以有所以有 F(AB)F(AB)FAFBFAF

15、B。 第34頁/共128頁證明任取任取y y， yFAB yFAB x x(F,yFx xAB)AB) x x(F,yFx xAAx xB) B) x x(F,yFx xA)(A)(F,yFx xB) B) x x(F,yFx xA) A) x x(F,yFx xB) B) yFA yFB yFA yFB yFAFByFAFB所以有所以有 FABFAB FAFB FAFB 第35頁/共128頁說明q對于A上的任何關系R1和R2都有R10R20IA 即：A上任何關系的0次冪都相等，都等于A上的恒等關系IA。q對于A上的任何關系R都有R1R，因為R1R0 RIA RR第36頁/共128頁n如果R是

16、用關系圖G給出的，可以直接由圖G得到Rn的關系圖G。G的頂點集與G相同?？疾霨的每個頂點xi，如果在G中從xi出發(fā)經(jīng)過n步長的路徑到達頂點xj，則在G中加一條從xi到xj的邊。當把所有這樣的便都找到以后，就得到圖G。第37頁/共128頁解答0 00 00 00 01 10 00 00 00 01 10 01 10 00 01 10 0MM0 00 00 00 01 10 00 00 00 01 10 01 10 00 01 10 00 00 00 00 01 10 00 00 00 01 10 01 10 00 01 10 0MM2 20 00 00 00 01 10 00 00 00 01

17、10 01 10 00 01 10 00 00 00 00 00 00 00 00 01 10 01 10 00 01 10 01 1MMMMMM2 23 31 10 00 00 00 01 10 00 00 00 01 10 00 00 00 01 1MM0 00 00 00 00 00 00 00 00 01 10 01 10 00 01 10 01 10 00 00 00 00 00 00 00 00 01 10 01 11 10 01 10 0第38頁/共128頁0 00 00 00 01 10 00 00 00 01 10 01 10 00 01 10 00 00 00 00 00

18、00 00 00 00 01 10 01 11 10 01 10 0MMMMMM3 34 40 00 00 00 00 00 00 00 01 10 01 10 00 01 10 01 1第39頁/共128頁R為A上的關系，對任何自然數(shù)k，Rk都是AA的子集。證明又知|AA|=n2，|P(AA)|= ，2 2n n2 2即AA的不同子集僅 個。2 2n n2 2當列出R的各次冪R0，R1，R2， ，時，2 2n n2 2R R必存在自然數(shù)s和t使得Rs=Rt。說明q該定理說明有窮集上只有有窮多個不同的二元關系。當t足夠大時，Rt必與某個Rs(st)相等。q如例7.8中的R4=R2。 第40頁/

19、共128頁證明(1)(1)對于任意給定的對于任意給定的mN,mN,施歸納于施歸納于n n。若若n=0n=0，則有則有所以對一切所以對一切m,nNm,nN有有 R Rm m R Rn nR Rm+nm+n。Rm R0 Rm IA Rm Rm+0假設Rm Rn=Rm+n，則有Rm Rn+1 Rm (Rn R)(Rm Rn)R Rm+n+1，第41頁/共128頁證明(2)(2)對于任意給定的對于任意給定的mN,mN,施歸納于施歸納于n n。若若n=0n=0，則有則有所以對一切所以對一切m,nN m,nN 有有( (R Rm m) )n n=R=Rmnmn。(Rm)0 IA R0 Rm0假設(Rm)n

20、Rmn，則有(Rm)n+1 (Rm)n Rm Rmn+m Rm(n+1)第42頁/共128頁證明(1) (1) R Rs+ks+kR Rs s R Rk kR Rt t R Rk kR Rt+kt+k(2)(2)對對k k歸納。歸納。若若k=0k=0，則有則有 R Rs+0 p+is+0 p+iR Rs+is+i假設假設 R Rs+kp+is+kp+iR Rs+is+i，其中其中p pt-st-s，則則Rs+(k+1)p+iRs+kp+i+pRs+i Rp=Rs+p+iRs+t-s+iRt+iRs+i由歸納法命題得證。Rs+kp+i Rp第43頁/共128頁證明(3)(3)任取任取qNqN，若

21、若qtqt，顯然有顯然有R Rq qSS，若若qtqt，則存在自然數(shù)則存在自然數(shù)k k和和i i使得使得q qs+kp+is+kp+i其中其中00ip-1,pip-1,pt-st-s。于是于是R Rq qR Rs+kp+is+kp+iR Rs+is+i而s+is+p-1s+t-s-1t-1這就證明了 RqS。第44頁/共128頁解答由由R R的定義可以看出的定義可以看出A A中的元素可分成兩組，即中的元素可分成兩組，即 a,ba,b和和 d,e,fd,e,f。它們在它們在R R的右復合運算下有下述變化規(guī)律：的右復合運算下有下述變化規(guī)律：ababababdefdefdefdef對于對于a a或或

22、b,b,每個元素的變化周期是每個元素的變化周期是2 2。對于。對于d d，e e，f f，每個元每個元素的變化周期是素的變化周期是3 3。因此必有。因此必有R Rm m=R=Rm+6m+6，其中其中6 6是是2 2和和3 3的最小的最小公倍數(shù)。取公倍數(shù)。取m=0,n=6m=0,n=6即滿足題目要求。即滿足題目要求。第45頁/共128頁第46頁/共128頁集合或集合族上的反自反關系。第47頁/共128頁例7.10 設A=1,2,3，R1，R2，R3是A上的關系，其中R1,R2,R3說明R1，R2和R3是否為A上的自反關系和反自反關系。解答 R1既不是自反的也不是反自反的，R2是自反的，R3是反自

23、反的。第48頁/共128頁A上的全域關系EA，恒等關系IA和空關系都是A上的對稱關系。恒等關系IA和空關系也是A上的反對稱關系。但全域關系EA一般不是A上的反對稱關系，除非A為單元集或空集。第49頁/共128頁R2是對稱的但不是反對稱的。R3是反對稱的但不是對稱的。R4既不是對稱的也不是反對稱的。第50頁/共128頁。小于關系和真包含關系仍舊是相應集合上的傳遞關系。第51頁/共128頁第52頁/共128頁說明q利用該定理可以從關系的集合表達式來判斷或證明關系的性質(zhì)。分析關系性質(zhì)的證明方法關系性質(zhì)的證明方法第53頁/共128頁充分性。 任取x，有 xA IA R 所以 R在A上是自反的。第54頁

24、/共128頁充分性。 任取x，有 xA IA R (RIA= ) 所以 R在A上是反自反的。必要性。用反證法。 假設RIA， 必存在RIA。 由于IA是A上恒等關系， 可知 xA且R。 這與R在A上是反自反的相矛盾。第55頁/共128頁所以 RR-1充分性。 任取， 由 RR-1 得 R R-1 R 所以 R在A上是對稱的。第56頁/共128頁 xy (R是反對稱的) IA所以 RR-1 IA充分性。任取, R R R R-1 RR-1 IA (RR-1 IA) xy所以 R在A上是反對稱的。第57頁/共128頁 RR R (因為RRR)所以 R在A上是傳遞的。第58頁/共128頁第59頁/共

25、128頁證明由于由于R R1 1和和R R2 2是是A A上的自反關系，故有上的自反關系，故有I IA A R R1 1 和和 I IA A R R2 2從而得到從而得到 I IA A R R1 1RR2 2。根據(jù)定理根據(jù)定理7.97.9可知可知 R R1 1RR2 2在在A A上是自反的。上是自反的。再由再由R R1 1和和R R2 2的對稱性有的對稱性有R R1 1R R1 1-1 -1 和和 R R2 2R R2 2-1-1根據(jù)練習七第根據(jù)練習七第1818題的結果有題的結果有( (R R1 1RR2 2) )-1-1R R1 1-1-1RR2 2-1-1R R1 1RR2 2從而證明了從

26、而證明了R R1 1RR2 2也是也是A A上對稱的關系。上對稱的關系。第60頁/共128頁證明由由R R1 1和和R R2 2的傳遞性有的傳遞性有R R1 1 R R1 1 R R1 1 和和 R R2 2 R R2 2 R R2 2再使用定理再使用定理7.47.4得得 ( (R R1 1RR2 2) ) (R(R1 1RR2 2) ) R R1 1 R R1 1RR1 1 R R2 2RR2 2 R R1 1RR2 2 R R2 2 (R(R1 1RR2 2)R)R1 1 R R2 2RR2 2 R R1 1 ( (將前面的包含式代入將前面的包含式代入) ) R R1 1RR2 2從而證明

27、了從而證明了R R1 1RR2 2也是也是A A上的傳遞關系。上的傳遞關系。 第61頁/共128頁自反性自反性反自反性反自反性對稱性對稱性反對稱性反對稱性傳遞性傳遞性集合表達式集合表達式I IA A R RRIRIA AR RR R-1-1RRRR-1 -1 I IA AR R R R R R關系矩陣關系矩陣主對角線主對角線元素全是元素全是1 1主對角線主對角線元素全是元素全是0 0 矩陣是對矩陣是對稱矩陣稱矩陣 若若r rijij1 1，且且ijij，則則r rjiji0 0 對對M M2 2中中1 1所所在位置，在位置，M M中相應的位中相應的位置都是置都是1 1 關系圖關系圖每個頂點每個

28、頂點都有環(huán)都有環(huán)每個頂點每個頂點都沒有環(huán)都沒有環(huán) 如果兩個如果兩個頂點之間頂點之間有邊，一有邊，一定是一對定是一對方向相反方向相反的邊的邊( (無單無單邊邊) ) 如果兩點之如果兩點之間有邊，一間有邊，一定是一條有定是一條有向邊向邊( (無雙無雙向邊向邊) ) 如果頂點如果頂點x xi i到到x xj j有邊，有邊，x xj j到到x xk k有邊有邊，則從，則從x xi i到到x xk k也有邊也有邊 第62頁/共128頁（1）對稱的，不是自反的，不是反自反的，不是反對稱的，不是傳遞的。（2）是反自反的，不是自反的，是反對稱的，不是對稱的，是傳遞的。（3）是自反的，不是反自反的，是反對稱的，

29、不是對稱的，不是傳遞的。第63頁/共128頁自反性自反性反自反性反自反性對稱性對稱性反對稱性反對稱性傳遞性傳遞性R R1 1-1-1R R1 1RR2 2R R1 1RR2 2R R1 1R R2 2R R1 1 R R2 2第64頁/共128頁第65頁/共128頁。一般將R的自反閉包記作r(R)，對稱閉包記作s(R)，傳遞閉包記作t(R)。第66頁/共128頁含每個Rn。證明右邊包含左邊，即RR2具有傳遞的性質(zhì)。第67頁/共128頁證明由由I IA AR R0 0 RRRR0 0，可知可知RRRR0 0是自反的，是自反的，R R RRRR0 0。設設R R是是A A上包含上包含R R的自反關

30、系，的自反關系， 則有則有R R R R和和I IA A R R。 任取任取 x,y，必有必有 x,yRRRR0 0 RIRIA A RRRRR R 所以所以 RRRR0 0 R R。綜上所述，綜上所述，r(R)r(R)RRRR0 0。第68頁/共128頁證明 R R RRRR-1-1。證明證明RRRR-1-1是對稱的，是對稱的， 任取任取 x,y，有有 x,yRRRR-1-1 RRRR-1-1 RR-1-1RR y,xRRRR-1-1 所以所以 RRRR-1-1 是對稱的是對稱的。綜上所述，s(R)RR-1。設設R R是包含是包含R R的的對稱關系，對稱關系， 任取任取 x,y，有有 x,y

31、RRRR-1-1 RRRR-1-1 RRRR RRRR RRRR Rx,yR 所以所以 RRRR-1 -1 R R。第69頁/共128頁證明先證先證RR2RR2 t(R) t(R)成立，為此只需證明對任意的正成立，為此只需證明對任意的正整數(shù)整數(shù)n n有有 R Rn n t(R)t(R)即可。用歸納法。即可。用歸納法。n n1 1時，有時，有 R R1 1R R t(R) t(R)。假設假設R Rn n t(R)t(R)成立，那么對任意的成立，那么對任意的 x,y有有 Rx,yRn+1n+1R Rn n R R t t(x,(RRn nR),yR) t t(x,(t(R)t(R),yt t(R)

32、(R) t(R) t(R) （因為因為t(R)t(R)是傳遞的）是傳遞的）這就證明了這就證明了R Rn+1 n+1 t(R)t(R)。由歸納法命題得證。由歸納法命題得證。第70頁/共128頁證明再證再證t(R)t(R) RRRR2 2成立，為此只須證明成立，為此只須證明RRRR2 2是傳是傳遞的。遞的。任取任取 ,x,y,，則則 RRx,yRR2 2 RR RR2 2 t t(R(Rt t) ) s s(R(Rs s) ) t t s s(R(Rt t R Rs s) ) t t s s(R(Rt t R Rs s) ) t t s s(R(Rt t+ +s s) ) RR RR2 2從而證明

33、了從而證明了RRRR2 2是傳遞的。是傳遞的。第71頁/共128頁|abs(R)RR-1|ab|ba|ab第72頁/共128頁注意在上述等式中矩陣的元素相加時使用邏輯加。第73頁/共128頁一條邊xj到xi的反方向邊。最終得到Gs。3)考察G的每個頂點xi，找出從xi出發(fā)的所有2步，3步，n步長的路徑（n為G中的頂點數(shù)）。設路徑的終點為。如果沒有從xi到 (l=1,2,k)的邊，就加上這條邊。當檢查完所有的頂點后就得到圖Gt。k k2 21 1j jj jj jx x, , ,x x, ,x xI Ij jx x第74頁/共128頁第75頁/共128頁第76頁/共128頁0 00 01 10

34、01 10 00 00 00 01 10 01 10 00 01 10 0MM0 00 00 01 10 01 10 00 00 00 01 11 11 10 00 01 10 0MM1 1分析分析 k k1 1 時，時，M MT T i i,jM,jMT T i i,j+M,j+MT T i i, ,1 1 * *M MT T 1 1,j,j M MT T 1 1,jM,jMT T 1 1,j+M,j+MT T 1 1, ,1 1 * *M MT T 1 1,j,j M MT T 2 2,jM,jMT T 2 2,j+M,j+MT T 2 2, ,1 1 * *M MT T 1 1,j ,j

35、 將第將第1 1行加到第行加到第2 2行上行上 M MT T 3 3,jM,jMT T 3 3,j+M,j+MT T 3 3, ,1 1 * *M MT T 1 1,j,j M MT T 4 4,jM,jMT T 4 4,j+M,j+MT T 4 4, ,1 1 * *M MT T 1 1,j,j 得到得到M M1 1。第77頁/共128頁0 00 01 10 01 10 00 00 00 01 10 01 10 00 01 10 0MM0 00 00 01 10 01 10 00 00 00 01 11 11 10 00 01 10 0MM1 10 01 11 11 11 10 00 00

36、00 01 11 11 10 01 11 11 1MM2 2k1時，第1列中只有M2,11，將第1行加到第2行上。k2時，第2列中M1,2 M2,2M4,21，將第2行分別加到第1,2,4行上。第78頁/共128頁0 01 11 11 11 10 00 00 00 01 11 11 10 01 11 11 1MM2 21 11 11 11 11 10 00 00 01 11 11 11 11 11 11 11 1MM3 31 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 1MM4 4k3時，第3列中M1,3M2,3M4,31，將第3行分別加到第1,2

37、,4行上。k4時，第4列中M1,4 M2,4M3,4M4,41，將第4行分別加到第1,2,3,4行上。第79頁/共128頁顯然有R r(R)。由于R是包含R的自反關系，根據(jù)自反閉包定義有r(R)R。從而得到r(R)=R。第80頁/共128頁 R2 IA R2IA r(R2)第81頁/共128頁 t(RnR) RRn R1+nRn+1所以Rn+1是對稱的。由歸納法命題得證。第82頁/共128頁第83頁/共128頁r(R)所以，r(R)是對稱的。第84頁/共128頁第85頁/共128頁tsr(R)=t(s(r(R) 自反性自反性對稱性對稱性傳遞性傳遞性r(R)r(R)s(R)s(R)( (反例反例

38、) )t(R)t(R)反例 A=1，2，3，R= 是傳遞的s(R)=,顯然s(R)不是傳遞的。第86頁/共128頁第87頁/共128頁x,y,zA，若xy(mod 3)，yz(mod 3)，則有xz(mod 3)第88頁/共128頁qx x的等價類是的等價類是A A中所有與中所有與x x等價的元素構成的集合。等價的元素構成的集合。 q例例7.167.16中的等價類是：中的等價類是：1144771,4,71,4,72255882,5,82,5,833663,6 3,6 第89頁/共128頁Zn數(shù)分類如下：余數(shù)為0的數(shù)，其形式為nz，zZ余數(shù)為1的數(shù)，其形式為nz+1，zZ余數(shù)是n-1的數(shù)，其形式

39、為nz+n-1，zZ以上構成了n個等價類，使用等價類的符號可記為inz+i|zZ，i=0，1，n-1第90頁/共128頁證明（1） 由等價類的定義可知，xA有xA。又由于等價關系的自反性有xx，即x非空。第91頁/共128頁 zy。所以 xy。同理可證 yx。因此，x=y。第92頁/共128頁第93頁/共128頁從而有Ax|xA成立。綜上所述得 x|xAA。第94頁/共128頁第95頁/共128頁說明q設集合是A的非空子集的集合，若這些非空子集兩兩不相交，且它們的并等于A，則稱是集合A的劃分。第96頁/共128頁的劃分。因為3中的子集a和a,b,c,d有交，4A，5中含有空集，而6根本不是A的

40、子集族。第97頁/共128頁第98頁/共128頁這些劃分與這些劃分與A A上的等價關系之間的一一對應是：上的等價關系之間的一一對應是：1 1對應于全域關系對應于全域關系E EA A，5 5的對應于恒等關系的對應于恒等關系I IA A，2 2，3 3和和4 4分別對應于等價關系分別對應于等價關系R R2 2，R R3 3和和R R4 4。 其中其中 R R2 2=,I=,IA AR R3 3=,I=,IA AR R4 4=,I=,IA A第99頁/共128頁d,a,b,c劃分為三個塊的情況：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劃分為四個塊的情況：1種，即a,b,c,d因此，共有15種不同的等價關系。第100頁/共128頁或者x就是y。根據(jù)不同偏序的定義，對序有著不同的解釋。偏序關系舉例集合A上的恒等關系IA小于或等于關系整除關系包含關系第101頁/共128頁xy(或yx)，xy，x與y不是可比的。n例如A1，2，3，是A上的整除關系，則有12，13，1=1，2=2，3=3，2和3不可比。第102頁/共128頁是全序關系，因為2和3不可比。第103頁/共128頁第104頁/共128頁第105頁/共128頁第106頁/共1