關(guān)系的性質(zhì)離散數(shù)學(xué)(與“關(guān)系”有關(guān)的文檔共66張)

關(guān)系的性質(zhì)離散數(shù)學(xué)5/14/202311:49AM

DiscreteMath.,huangliujia1第一頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia2第七章二元關(guān)系7.1有序?qū)εc笛卡兒積7.2二元關(guān)系7.3關(guān)系的運(yùn)算7.4關(guān)系的性質(zhì)7.5關(guān)系的閉包7.6等價關(guān)系與劃分7.7偏序關(guān)系第二頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia3

由兩個元素x和y（允許x＝y(tǒng)）按一定順序排列成的二元組叫做一個有序?qū)?，記?lt;x,y>。注：有序?qū)Φ男再|(zhì)：1.當(dāng)xy時，<x,y><y,x>。2.<x,y>＝<u,v>的充分必要條件是x=u且y=v?！?.1有序?qū)εc笛卡爾積

設(shè)A,B是集合。由A中元作為第一元素，B中元作為第二元素組成的所有有序?qū)Φ募?，稱為集合A與B的笛卡爾積，記為A×B。即A×B＝{<x,y>|xA∧yB}。第三頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia4注：笛卡爾積的性質(zhì)：1.A×=,×A=;2.

A×BB×A,除非A=或B=或A=B;3.(A×B)×CA×(B×C),除非A=或B=

或C=

.4.

A×(B∪C)=(A×B)∪(A×C);(B∪C)×A=(B×A)∪(C×A);A×(B∩C)=(A×B)∩(A×C);(B∩C)×A=(B×A)∩(C×A);5.(AC)∧(BD)(A×B)(C×D).§7.1有序?qū)εc笛卡爾積

第四頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia5例證明A×(B∪C)=(A×B)∪(A×C)。證：任取<x,y>，<x,y>A×(B∪C)xA∧y(B∪C)xA∧(yB∨yC)(xA∧yB)∨(xA∧yC)(<x,y>A×B)∨(<x,y>A×C)<x,y>(A×B)∪(A×C)∴A×(B∪C)=(A×B)∪(A×C)例設(shè)A={1,2},求P(A)×A。解：P(A)×A

={?,{1},{2},{1,2}}×{1,2}={<?,1>,<?,2>,<{1},1>,<{1},2>,<{2},1>,<{2},2>,<{1,2},1>,<{1,2},2>}§7.1有序?qū)εc笛卡爾積

第五頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia6設(shè)A,B,C,D為任意集合，判斷下列命題是否為真。（1）A×B＝A×CB=C（2）A–(B×C)=(A–B)×(A–C)（3）(A=B)∧(C=D)A×C=B×D（4）存在集合A,使AA×A§7.1有序?qū)εc笛卡爾積

解:(1)不一定為真，(3)為真。(4)為真。當(dāng)A=,B={1},C={2,3}時，便不真。(2)不一定為真，當(dāng)A=B={1},C={2}時，A–(B×C)={1}–{<1,2>}={1},而(A–B)×(A–C)=×{1}=.

等量代入。當(dāng)A=時,使AA×A.第六頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia7一、基本概念如果一個非空集合的元素都是有序?qū)?，則稱該集合為一個二元關(guān)系。特別地，空集也是一個二元關(guān)系。注：對一個二元關(guān)系R，如果<x,y>R,則記為xRy；

如果<x,y>R，則記為xRy。設(shè)A,B為集合，A×B的任何子集所定義的二元關(guān)系稱為從A到B的二元關(guān)系。特別地，當(dāng)A=B時，稱為A上的二元關(guān)系。對任何集合A，(1)稱空集為A上的空關(guān)系。(2)A上的全域關(guān)系EA=<x,y>xA∧yA=A×A(3)A上的恒等關(guān)系IA=<x,x>xA.§7.2二元關(guān)系第七頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia8二.關(guān)系的表達(dá)方式1.集合表達(dá)式：列出關(guān)系中的所有有序?qū)?。設(shè)A=1,2,3,4,試列出下列關(guān)系R的元素。(1)R=<x,y>x是y的倍數(shù)(2)R=<x,y>(x－y)2A(3)R=<x,y>x/y是素數(shù)(4)R=<x,y>xy(5)R=<x,y>(x,yA)∧(xy)

解:(1)R={<4,4>,<4,2>,<4,1>,<3,3>,<3,1>,<2,2>,<2,1>,<1,1>}(2)R={<2,1>,<3,2>,<4,3>,<3,1>,<4,2>,<2,4>,<1,3>,<3,4>,<2,3>,<1,2>}(3)R={<2,1>,<3,1>,<4,2>}(4)R=EA-IA={<1,2>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4>,<3,1>,<3,2>,<3,4>,<4,1>,<4,2>,<4,3>}(5)R={<1,2>,<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}§7.2二元關(guān)系第八頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia92.關(guān)系矩陣法：設(shè)A={x1,x2,…xn},R是A上的關(guān)系。令：則矩陣

稱為R的關(guān)系矩陣?！?.2二元關(guān)系第九頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia10例

設(shè)A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},則R的關(guān)系矩陣為§7.2二元關(guān)系第十頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia113.關(guān)系圖法

設(shè)A={x1,x2,…xn},R是A上的關(guān)系。以A的元素作為頂點(diǎn)，當(dāng)且僅當(dāng)xiRxj時，xi向xj連一條有向邊，所得的圖形稱為R的關(guān)系圖，記為GR。例設(shè)A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},則R的關(guān)系圖為1243§7.2二元關(guān)系第十一頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia12一、基本概念設(shè)R是二元關(guān)系。定義(1)

R的定義域:domR={x|y(<x,y>R)},即R中所有有序?qū)Φ牡谝辉貥?gòu)成的集合。(2)R的值域，ranR={y|x(<x,y>R)},即R中所有有序?qū)Φ牡诙貥?gòu)成的集合。(3)

R的域:fldR=domR∪ranR。例7.5R={<1,2>,<1,3>,<2,4>,<4,3>},則

domR={1,2,4}，

ranR={2,3,4},

fldR={1,2,3,4}?！?.3關(guān)系的運(yùn)算第十二頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia13設(shè)R為二元關(guān)系，稱R-1={<x,y>|<y,x>R}為R的逆關(guān)系。設(shè)F,G為二元關(guān)系。稱為G對F的右復(fù)合(或F對G的左復(fù)合)。例如,F={<3,3>,<6,2>},G={<2,3>},則

F-1

={<3,3>,<2,6>}§7.3關(guān)系的運(yùn)算第十三頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia14設(shè)R是二元關(guān)系,A是集合(通常AdomR)§7.3關(guān)系的運(yùn)算

設(shè)R為{<1,2>,<1,3>,<2,2>,<2,4>,<3,2>},則(1)R在A上的限制:RA={<x,y>|xRy∧xA}R{1}={2,3},R=,R{2,3}={2,4}

。R

{1}={<1,2>,<1,3>},R=,R

{2,3}={<2,2>,<2,4>,<3,2>}，(2)A在R下的像:RA=ran(RA)第十四頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia15設(shè)R是A上的關(guān)系,n為自然數(shù),則R的n次冪定義為:(1)

R0={<x,x>|xA}=IA;(2)

注:1.對A上的任何關(guān)系R,都有R0=IA,R1=R。2.Rn的求法:除了根據(jù)定義按關(guān)系的復(fù)合來求之外,還可以用矩陣法和關(guān)系圖法?！?.3關(guān)系的運(yùn)算第十五頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia16設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R的各次冪,分別用矩陣和關(guān)系圖表示.解:R的關(guān)系矩陣:

R2,R3,R4

的關(guān)系矩陣分別是：

第十六頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia17可見M4=M2。故R2=R4=R6=…;R3=R5=R7=…。第十七頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia18此外,R0=IA的關(guān)系矩陣為:

用關(guān)系圖法得到R0,R1,R2,…的關(guān)系圖如下:dabcR0R1abcdR2=R4=…bcdaabcdR3=R5=…第十八頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia19關(guān)系是集合,故有關(guān)集合的所有運(yùn)算性質(zhì)對關(guān)系都成立。定理設(shè)F是關(guān)系,則(F-1)-1=F;(2)domF-1=ranF,ranF-1=domF。證:(1)∵<x,y>(F-1)-1<y,x>F-1

<x,y>F∴(F-1)-1=F。(2)∵xdomF-1y(<x,y>F-1)

y(<y,x>F)xran

F∴domF-1=ranF。同理可證ranF-1=domF。二.關(guān)系的運(yùn)算性質(zhì)第十九頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia20設(shè)F,G,H是關(guān)系，則(1)(FG)H=F(GH);(2)(FG)–1=G–1F–1.證:(1)∵<x,y>((FG)H)

t(<x,t>(FG)∧<t,y>H)

t(s(<x,s>F∧<s,t>G)∧<t,y>H)

ts(<x,s>F∧<s,t>G)∧<t,y>H)

s(<x,s>F∧t(<s,t>G∧<t,y>H))

s(<x,s>F∧<s,y>(GH))

<x,y>F(GH)∴(FG)H=F(GH)(2)∵<x,y>(FG)–1<y,x>FGt(<y,t>F∧<t,x>G)t(<x,t>G–1∧<t,y>F–1)<x,y>(G–1F–1)∴(FG)–1=G–1F–1第二十頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia21設(shè)R是A上的關(guān)系,則RIA=IAR=R.證:∵<x,y>(RIA)

t(<x,t>R∧<t,y>IA)t(<x,t>R∧t=y)<x,y>R<x,y>R<x,y>R∧yA<x,y>R∧<y,y>IA<x,y>(RIA)∴RIA=R同理可證IAR=R第二十一頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia22設(shè)F,G,H是關(guān)系,則(1)F(G∪H)=FG∪FH;(2)(G∪H)F=GF∪HF;(3)F(G∩H)FG∩FH;(4)(G∩H)FGF∩HF.證:以(3)為例.∵<x,y>F(G∩H)

t(<x,t>F∧<t,y>(G∩H))

t(<x,t>F∧<t,y>G∧<t,y>H)

t((<x,t>F∧<t,y>G)∧(<x,t>F∧<t,y>H))

t(<x,t>F∧<t,y>G)∧t(<x,t>F∧<t,y>H)

<x,y>FG∧<x,y>FH

<x,y>FG∩FH∴F(G∩H)=FG∩FH第二十二頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia23定理7.5設(shè)F為關(guān)系,A,B為集合,則(1)F(A∪B)=FA∪FB;(2)FA∪B=FA∪FB(3)F(A∩B)=FA∩FB;(4)FA∩BFA∩FB

(1)<x,y>F(A∪B)∴F(A∪B)=FA∪FB

證:以(1)和(4)為例<x,y>F∧(xA∨xB)(<x,y>F∧xA)∨(<x,y>F∧xB)<x,y>FA∨<x,y>FB<x,y>(FA∪FB)<x,y>F∧x(A∪B)第二十三頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia24(4)yFA∩Bx(<x,y>F∧(xA∩B))x(<x,y>F∧xA∧xB)x((<x,y>F∧xA)∧(<x,y>F∧xB))

x(<x,y>F∧xA)∧x(<x,y>F∧xB)yFA∧yFBy(FA∩FB)∴FA∩B=FA∩FB第二十四頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia25設(shè)R為A上的關(guān)系,m,nN,則(1)Rm

Rn=Rm+n;(2)(Rm)n=Rmn證:(1)對于任意取定的mN，關(guān)于n作數(shù)學(xué)歸納法。當(dāng)n=0時，Rm

R0=Rm

IA=Rm=Rm+0假設(shè)Rm

Rn=Rm+n,則Rm

Rn+1=Rm(Rn

R)=(Rm

Rn)R=Rm+n

R1=Rm+n+1由歸納法原理,知命題成立。(2)對任意取定的mN,關(guān)于n作數(shù)學(xué)歸納法。當(dāng)n=0時,(Rm)0=IA=R0=Rm·0假設(shè)(Rm)n=Rmn,則(Rm)n+1=(Rm)nRm=Rmn

Rm=Rmn+m=Rm(n+1)由歸納法原理,知命題成立。定理

設(shè)A是n元集合,R為A上的關(guān)系,則存在自然數(shù)s和t,使得Rs=Rt。第二十五頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia26設(shè)R為A上的關(guān)系,若存在自然數(shù)s,t(s<t),使得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。證明：見教材P112。注:定理7.6和定理7.8的(3)表明,有限集合A上的二元關(guān)系只有有限多個,而且一個關(guān)系的冪序列R0,R1R2,…是一個周期性變化的序列。見教材P113。第二十六頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia27一、關(guān)系的五種性質(zhì)

關(guān)系的性質(zhì)主要有5種:自反性,反自反性,對稱性,反對稱性和傳遞性。設(shè)R是A上的關(guān)系,若x(xA<x,x>R),則稱R在A上是自反的(Reflexive);若x(xA<x,x>R),則稱R在A上是反自反的(antiReflexive).§關(guān)系的性質(zhì)第二十七頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia28(1)A上的全域關(guān)系EA、恒等關(guān)系IA都是A上的自反關(guān)系.(2)小于等于關(guān)系LA={<x,y>x,yA∧x≤y},AR.整除關(guān)系DA={<x,y>x,yA∧x整除y},AZ*.包含關(guān)系R={<x,y>x,yA∧xy},A是集合族。都是自反關(guān)系.(3)

小于關(guān)系SA={<x,y>x,yA∧xy},AR.真包含關(guān)系R={<x,y>x,yA∧xy},A是集合族。

都是反自反關(guān)系.(4)設(shè)A={1,2,3},

R1={<1,1>,<2,2>,<3,3>,<1,2>}是A上的自反關(guān)系;

R2={<1,3>}是A上的反自反關(guān)系;

R3={<1,1>,<2,2>}既不是自反的,也不是反自反的.第二十八頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia29定義設(shè)R是A上的關(guān)系,若xy(x,yA∧<x,y>R→(y,x)R),則稱R是A上的對稱關(guān)系(Symmetric);若xy(x,yA∧<x,y>R∧(y,x)R→x=y),則稱R是A上的反對稱關(guān)系(antiSymmetric).

例(1)A上的全域關(guān)系EA,恒等關(guān)系IA及空關(guān)系都是A上的對稱關(guān)系;IA和同時也是A上的反對稱關(guān)系.(2)設(shè)A={1,2,3},則

R1={<1,1>,<2,2>}既是A上的對稱關(guān)系,也是A上的反對稱關(guān)系;

R2={<1,1>,<1,2>,<2,1>}是對稱的,但不是反對稱的;R3={<1,2>,<1,3>}是反對稱的,但不是對稱的;

R4={<1,2>,<2,1>,<1,3>}既不是對稱的也不是反對稱的。第二十九頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia30定義

設(shè)R是A上的關(guān)系,若xyz(x,y,zA∧<x,y>R∧<y,z>R→<x,z>R),則稱R是A上的傳遞關(guān)系。例

(1)A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系都是傳遞關(guān)系。(2)小于等于關(guān)系,整除關(guān)系和包含關(guān)系是傳遞關(guān)系,小于關(guān)系和真包含關(guān)系也是傳遞關(guān)系。(3)設(shè)A={1,2,3},則R1={<1,1>,<2,2>}和R2={<1,3>}都是A上的傳遞關(guān)系,但R3={<1,2>,<2,3>}不是A上的傳遞關(guān)系。第三十頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia31定理

設(shè)R為A上的關(guān)系,則(1)

R在A上自反當(dāng)且僅當(dāng)IAR(2)

R在A上反自反當(dāng)且僅當(dāng)R∩IA=(3)R在A上對稱當(dāng)且僅當(dāng)R=R-1(4)R在A上反對稱當(dāng)且僅當(dāng)R∩R-1IA(5)

R在A上傳遞當(dāng)且僅當(dāng)RRR證:(1)必要性:因R在A上自反,故<x,y>IAx,yA∧x=y<x,y>R，從而IAR。充分性:因xA<x,x>IA<x,x>R,故R在A上自反。二、各種性質(zhì)的充分必要條件第三十一頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia32(2)必要性(用反證法):假設(shè)R∩IA≠,則必存在<x,y>R∩IA,即<x,y>R且<x,y>IA。由<x,y>IA知x=y.從而<x,x>R.這與R在A上是反自反矛盾。充分性:xA<x,x>IA<x,x>R(因R∩IA=?),這說明R在A上是反自反的。(3)必要性:∵R是A上的對稱關(guān)系,<x,y>R<y,x>R<x,y>R-1,故R=R-1。充分性:由于R=R-1,<x,y>R<y,x>R-1

<y,x>R.故R在A上是對稱的。第三十二頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia33(4)

必要性:因R在A上是反對稱的,故<x,y>R∩R–1<x,y>R∧<x,y>R–1<x,y>R∧<y,x>Rx=y<x,y>IA.∴R∩R–1IA充分性:因R∩R–1IA,故<x,y>R∧<y,x>R<x,y>R∧<x,y>R–1<x,y>R∩R–1

<x,y>IA

x=y.從而R在A上是反對稱的.第三十三頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia34

(5)

必要性:因R在A上是傳遞的,故<x,y>R

Rt(<x,t>R∧<t,y>R)<x,y>R因此R

RR充分性:因R

RR,故<x,y>R∧<y,z>R<x,z>R

R<x,z>R∴R在A上是傳遞的。第三十四頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia35

例設(shè)A是集合,R1和R2是A上的關(guān)系,證明(1)

若R1和R2都是自反的和對稱的,則R1∪R2也是自反的和對稱的.(2)

若R1和R2是傳遞的,則R1∩R2也是傳遞的.證:(1)因R1和R2是A上的自反關(guān)系,故IAR1,IAR2,從而IA

R1∪R2.由定理7.9,R1∪R2在A上是自反的.由R1和R2的對稱性,有R1=R1–1和R2=R2-1,因此(R1∪R2)-1=R1-1∪R2-1=R1∪R2(見習(xí)題7.20).由定理7.9,R1∪R2在A上是對稱的.(2)由R1和R2的傳遞性,有R1R1R1和R2R2R2.由定理7.4,(R1∩R2)

(R1∩R2)

(R1R1)∩(R1R2)∩(R2

R1)∩(R2

R2)(R1∩R2)∩(R1

R2)∩(R2

R1)R1∩R2由定理7.9,R1∩R2在A上是傳遞的.第三十五頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia36性質(zhì)表示自反性反自反性對稱性反對稱性傳遞性集合表達(dá)式IA

RR∩IA=R=R–1R∩R–1IAR

RR關(guān)系矩陣主對角線元素全是1主對角線元素全是0矩陣是對稱矩陣。若rij=1,且i≠j,則rji=0.對M2中1所在的位置,M中相應(yīng)的位置都是1。關(guān)系圖每個頂點(diǎn)都有環(huán)每個頂點(diǎn)都沒有環(huán)如果兩個頂點(diǎn)之間有邊,則必是一對方向相反的邊。每對頂點(diǎn)之間至多有一條邊,(不會有雙向邊)。如果頂點(diǎn)xi到xj有邊,xj到xk有邊,則從xi到xk也有邊。三.各種性質(zhì)在關(guān)系矩陣和關(guān)系圖中的體現(xiàn)

第三十六頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia37例解:(a)該關(guān)系是對稱的.其它性質(zhì)均不具備。(b)該關(guān)系是反自反的,反對稱的,同時也是傳遞的。(c)該關(guān)系是自反的,反對稱的,但不是傳遞的。(a)(b)(c)321231231第三十七頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia38四.各種性質(zhì)與運(yùn)算之間關(guān)系性質(zhì)

運(yùn)算

自反性反自反性對稱性反對稱性傳遞性R–1√√√√√R1∩R2√√√√√R1∪R2√√√R1–R2√√√R1

R2√第三十八頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia39一.閉包的定義設(shè)R是非空集合A上的關(guān)系,R的自反閉包(對稱閉包、傳遞閉包)是A上的關(guān)系R'，它滿足：(1)

R'是自反的(對稱的、傳遞的)；(2)RR';(3)對A上任何包含R的自反關(guān)系(對稱關(guān)系、傳遞關(guān)系)R''都有R'

R''.注：R的自反閉包記為r(R)，對稱閉包記為s(R)，傳遞閉包記為t(R)。

§關(guān)系的閉包Reflexive,Symmetric,Transtive:r(R),

s(R),

t(R).第三十九頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia40二.閉包的構(gòu)造方法設(shè)R是A上的關(guān)系，則(1)r(R)=R∪R0;(2)s(R)=R∪R-1;(3)t(R)=R∪R2∪R3∪….證明：(1)由IA=R0R∪R0知，R∪R0是自反的，且RR∪R0。設(shè)R''是A上包含R的自反關(guān)系，則RR'',IAR'',因而<x,y>R∪R0<x,y>R∪IA<x,y>R''

∪R''=R''.即R∪R0R''。可見R∪R0滿足自反閉包的定義，從而r(R)=R∪R0.(2)略。第四十頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia41(3)先證R∪R2∪…t(R),為此只需證明對任意正整數(shù)n都有Rnt(R)即可。用歸納法。當(dāng)n=1時，R1

=Rt(R).假設(shè)Rnt(R),下證Rn+1t(R)事實(shí)上，由于<x,y>Rn+1=Rn

R

t(<x,t>Rn∧<t,y>R)

t(<x,t>t(R)

∧<t,y>t(R))<x,y>t(R)從而Rn+1t(R).由歸納法完成證明。

(因t(R)是傳遞的)第四十一頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia42下證R∪R2∪…是傳遞的。事實(shí)上，對任意<x,y>,<y,z>,(<x,y>R∪R2∪…)∧(<y,z>R∪R2∪…)t(<x,y>Rt)∧s(<y,z>Rs)ts(<x,z>Rt

Rs)ts(<x,z>Rt+s)

<x,z>R∪R2∪…從而R∪R2∪…是傳遞的。因t(R)是傳遞閉包，故t(R)R∪R2∪…。由以上兩方面知，t(R)＝R∪R2∪…。第四十二頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia43證：由定理7.6和定理7.10立即得證。通過關(guān)系矩陣求閉包設(shè)關(guān)系R,r(R),s(R),t(R)的關(guān)系矩陣分別為M,Mr,Ms,Mt,則：Mr=M+E,Ms=M+M',Mt=M+M2+M3+…,其中E是與M同階的單位矩陣。M'是M的轉(zhuǎn)置矩陣，矩陣元素相加時使用邏輯加。推論設(shè)R是有限集合A上的關(guān)系，則存在正整數(shù)r使得

t(R)=R∪R2∪…∪Rr.第四十三頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia44設(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的每個頂點(diǎn)，如果無環(huán)，則添加一條環(huán)，由此得到Gr;(2)對G的每條邊，如果它是單向邊，則添加一條反方向的邊。由此得到Gs;通過關(guān)系求閉包見教材P120(3)對G的每個頂點(diǎn)xi,找出從xi出發(fā)的所有2步,3步,…,n步長的有向路(n為G的頂點(diǎn)數(shù))。設(shè)路的終點(diǎn)分別為,如果從xi到無邊，則添上這條邊。如果處理完所有頂點(diǎn)后得到GtWarshall算法求t(R).第四十四頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia45設(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)充分性顯然。下證必要性。因R是包含了R的自反關(guān)系，故r(R)R。另一方面，顯然Rr(R).從而，r(R)=R。(2),(3)略(Def7.14).設(shè)R1和R2是非空集合A上的關(guān)系，且R1R2,則(1)r(R1)r(R2);(2)s(R1)s(R2);(3)t(R1)t(R2)證明略三.閉包的性質(zhì)第四十五頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia46設(shè)R是非空集合A上的關(guān)系（1）若R是自反的，則s(R)和t(R)也是自反的。（2）若R是對稱的，則r(R)和t(R)也是自反的。（3）若R是傳遞的，則r(R)也是傳遞的。證明：只證(2)。先考慮r(R).因R是A上的對稱關(guān)系。故R=R-1,同時IA=IA-1,于是(R∪IA)-1=R-1∪IA-1(根據(jù)習(xí)題7.20).從而r(R)-1=(R∪R0)-1=(R∪IA)-1=R-1∪IA-1=R∪IA=r(R)。這便說明r(R)是對稱的。下面證明t(R)的對稱性。為此，先用數(shù)學(xué)歸納法證明：若R是對稱的，則對任何正整數(shù)n,Rn也是對稱的。事實(shí)上，當(dāng)n=1時，R'=R顯然是對稱的。第四十六頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia47假設(shè)Rn是對稱的，下證Rn+1的對稱性。由于<x,y>Rn+1<x,y>Rn

R

t(<x,t>Rn)∧<t,y>R)

t(<t,x>Rn)∧<y,t>R)

<y,x>R

Rn

<y,x>Rn+1故Rn+1是對稱的。歸納法定成?，F(xiàn)在來證t(R)的對稱性。由于<x,y>t(R)n(<x,y>Rn)n(<y,x>Rn)<y,x>t(R)因此t(R)是對稱的。注：由于傳遞閉包運(yùn)算和對稱閉包運(yùn)算不保持傳遞性，故在運(yùn)算順序上它們應(yīng)放在自反閉包之后，即tsr(R)=t(s(r(R)))。第四十七頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia48二元關(guān)系的閉包仍然是二元關(guān)系，還可以求它的閉包。例如，R是A上的二元關(guān)系,r(R)是它的自反閉包，還可以求r(R)的對稱閉包。r(R)的對稱閉包記為s(r(R))，簡記為sr(R)，讀做R的自反閉包的對稱閉包。類似的，R的對稱閉包的自反閉包r(s(R))簡記為rs(R)，R的對稱閉包的傳遞閉包t(s(R))，簡記為ts(R)，……通常用R*表示R的傳遞閉包的自反閉包rt(R)，讀作“R星”。在研究形式語言和計算模型時經(jīng)常使用R*。第四十八頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia49§等價關(guān)系與劃分例7.16設(shè)A={1,2…,8},定義A上的關(guān)系R如下：驗證R是A上的等價關(guān)系。一.等價關(guān)系

設(shè)R為非空集合A上的關(guān)系。如果R是自反的,對稱的和傳遞的，則稱R為A上的等價關(guān)系。對等價關(guān)系R，若<x,y>R,則稱x等價于y，記為x～yorxRy.

解：∵xA,有,故R是自反的。x,yA,若,則,故R是對稱的。x,y,zA,若,,則故R是傳遞的。∴R是A上的一個等價關(guān)系。第四十九頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia50設(shè)R為非空集合A上的等價關(guān)系，xA,令稱xR為x在R下的等價類(簡稱為x的等價類)，有時簡記為x。x稱為該等價類的代表元。注：一個等價類是A中在等價關(guān)系R下彼此等價的所有元素的集合，等價類中各元素的地位是平等的，每個元素都可以作為其所在等價類的代表元。例如，在上例中的等價關(guān)系R下，A中元素形成了三個等價類：1=4=7={1,4,7}；2=5=8={2,5,8};3=6={3,6}.二.等價類第五十頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia51

設(shè)R為非空集合A上的等價關(guān)系，則（1）xA,x是A的非空子集。（2）x,yA，如果xRy,則x=y（3）x,yA，如果x與y不具有關(guān)系R,則x與y不相交。（4）證：(1)顯然。(2)∵zx<x,z>R

<z,x>R（R是對稱的）∴<z,x>R∧<x,y>R

<z,y>R

<y,z>R∴zy,從而x

y同理可得，y

x.故x=y三.等價類的性質(zhì)第五十一頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia52(3)反證法。

假設(shè)x∩y

，則存在zx∩y.因而z

x且z

y，即<x,z>R∧<y,z>R.根據(jù)R的對稱性和傳遞性，必有<x,z>R。這與前提條件矛盾。故原命題成立。(4)先證∵∴再證∵∴因此第五十二頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia53設(shè)R為非空集合A上的等價關(guān)系，以R的所有等價類作為元素，形成的集合稱為A關(guān)于R的商集，記為A/R，即：例如：例7.16中等價關(guān)系形成的商集為：A/R＝{{1,4,7},{2,5,8},{3,6}}四.商集設(shè)A為非空集合，若A的子集族(P(A),是由A的一些子集形成的集合)滿足下列條件：(1)

(2)xy(x,y∧x≠y→x∩y=

)(3)

則稱是A的一個劃分，而稱中的元素為A的劃分塊或類。

五.集合的劃分第五十三頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia54例7.17設(shè)A={a,b,c,d},則

1={{a,b,c},hoxgu5q}和2={{a,b},{c},4twkys5}都是A的劃分，而3={{a},{a,b,c,d}}和4={

,{a,b},{c}}都不是A的劃分。注：給定非空有限集A上的一個等價關(guān)系R，在R下彼此等價的元素構(gòu)成的子集便形成了A的一個劃分，它其實(shí)就是商集A/R,其每個類(等價塊)就是R的一個等價類；反之，任給A的一個劃分，可定義A上的關(guān)系R如下：R={<x,y>x,yA∧x與y在的同一個類中}可以驗證R是A上的一個等價關(guān)系?？梢夾上的等價關(guān)系與A的劃分是一一對應(yīng)的。第五十四頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia55求A={1,2,3}上所有的等價關(guān)系。解：先求出A的所有劃分：1={{1,2,3}};2={{1},{2,3}}；3={{2},{1,3}};4={{3},{1,2}};5={{1},{2},{3}}。與這些劃分一一對應(yīng)的等價關(guān)系是：1:→全域關(guān)系EA2:→R2={<2,3>,<3,2>}∪IA3:→R3={<1,3>,<3,1>}∪IA4:→R4={<1,2>,<2,1>}∪IA5:→恒等關(guān)系IA第五十五頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia56偏序關(guān)系與偏序集設(shè)R為非空集合A上的關(guān)系。如果R是自反的、反對稱的和傳遞的，則稱R為A上的偏序關(guān)系，記為?。對一個偏序關(guān)系?，如果<x,y>?，則記為x

?y。注：1.集合A上的恒等關(guān)系IA和空關(guān)系都是A上的偏序關(guān)系，但全域關(guān)系EA一般不是A上的偏序關(guān)系。2.實(shí)數(shù)域上的小于等于關(guān)系（大于等于關(guān)系），自然數(shù)域上的整除關(guān)系，集合的包含關(guān)系等都是偏序關(guān)系?！炱蜿P(guān)系第五十六頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia57注：在具有偏序關(guān)系的集合A中任二元素x和y之間必有下列四種情形之一：

x?y，y?x，x=y，x與y不可比。例設(shè)A={1,2,3}?是A上的整除關(guān)系，則：1?2,1?3,1＝1,2＝2,3＝3，2和3不可比；(2)?是A上的大于等于關(guān)系，則:2?1,3?1,3?2,1＝1,2＝2，3＝3。

設(shè)R為非空集合A上的偏序關(guān)系，定義(1)x,yA,x?y當(dāng)且僅當(dāng)x?y且x≠y

(2)x,yA,x與y可比當(dāng)且僅當(dāng)x?y或y?x第五十七頁，共66頁。5/14/202311:49AM

DiscreteMath.,huangliujia58設(shè)R為非空集合A上的偏序關(guān)系，如果x,yA,x與y都是可比的，則稱R為A上的全序關(guān)系。例如大于等于關(guān)系（小于等于關(guān)系）是全序集，但整除關(guān)系一般不是全序集。

帶有某種指定的偏序關(guān)系?的集合A稱為偏序集，記為<A,?>.例如整數(shù)集Z和數(shù)的小于等于關(guān)系≤構(gòu)成偏序集<z,?>