主要內(nèi)容7.1

有序?qū)εc笛卡兒積7.2

二元關(guān)系7.3

關(guān)系的運(yùn)算7.4關(guān)系的性質(zhì)第七章二元關(guān)系7.5

關(guān)系的閉包7.6等價(jià)關(guān)系與劃分7.7

偏序關(guān)系17.1有序?qū)εc笛卡兒積定義7.1由兩個(gè)元素x和y，按照一定的順序組成的二元組稱為有序?qū)?，記?lt;x,y>.有序?qū)π再|(zhì):(1)有序性<x,y><y,x>〔當(dāng)xy時(shí)〕

(2)<x,y>與<u,v>相等的充分必要條件是<x,y>=<u,v>x=uy=v.2笛卡兒積定義7.2設(shè)A,B為集合，A與B的笛卡兒積記作A

B，且

A

B={<x,y>|x

A

y

B}.例1

A={1,2,3},B={a,b,c}A

B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}

B

A={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>,<b,3>,<c,3>}

A={

},B=

P(A)

A={<

,

>,<{

},

>}P(A)

B=

3笛卡兒積的性質(zhì)(1)不適合交換律ABBA(AB,A,B)(2)不適合結(jié)合律(AB)CA(BC)(A,B,C)(3)對(duì)于并或交運(yùn)算滿足分配律A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)(4)假設(shè)A或B中有一個(gè)為空集，那么AB就是空集.A=B=(5)假設(shè)|A|=m,|B|=n,那么|AB|=mn4笛卡爾積圖示ABCA

(B

C)=(A

B)

(A

C)A

CBD

A

B

CDBACD5性質(zhì)證明證明A

(B

C)=(A

B)

(A

C)證任取<x,y><x,y>∈A×(B∪C)

x∈A∧y∈B∪C

x∈A∧(y∈B∨y∈C)

(x∈A∧y∈B)∨(x∈A∧y∈C)

<x,y>∈A×B∨<x,y>∈A×C

<x,y>∈(A×B)∪(A×C)所以有A×(B∪C)=(A×B)∪(A×C).6實(shí)例例2(1)證明A=B,C=DAC=BD(2)AC=BD是否推出A=B,C=D?為什么？解(1)任取<x,y><x,y>ACxAyCxByD<x,y>BD(2)不一定.反例如下：A={1}，B={2},C=D=,那么AC=BD但是AB.77.2二元關(guān)系定義7.3如果一個(gè)集合滿足以下條件之一：(1)集合非空,且它的元素都是有序?qū)?2)集合是空集那么稱該集合為一個(gè)二元關(guān)系,簡(jiǎn)稱為關(guān)系，記作R.如果<x,y>∈R,可記作xRy；如果<x,y>R,那么記作xy實(shí)例：R={<1,2>,<a,b>},S={<1,2>,a,b}.R是二元關(guān)系,當(dāng)a,b不是有序?qū)r(shí)，S不是二元關(guān)系根據(jù)上面的記法，可以寫(xiě)1R2,aRb等.注意：關(guān)系是笛卡爾積的子集8A到B的關(guān)系與A上的關(guān)系定義7.4設(shè)A,B為集合,A×B的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系,當(dāng)A=B時(shí)那么叫做A上的二元關(guān)系.例3A={0,1},B={1,2,3},那么R1={<0,2>},R2=A×B,R3=,R4={<0,1>}R1,R2,R3,R4是從A到B的二元關(guān)系,R3和R4也是A上的二元關(guān)系.計(jì)數(shù):|A|=n,|A×A|=n2,A×A的子集有個(gè).所以A上有個(gè)不同的二元關(guān)系.例如|A|=3,那么A上有512個(gè)不同的二元關(guān)系.9A上重要的關(guān)系的實(shí)例定義7.5設(shè)A為集合,(1)是A上的關(guān)系，稱為空關(guān)系(2)全域關(guān)系EA={<x,y>|x∈A∧y∈A}=A×A例如A={1,2},那么EA={<1,1>,<1,2>,<2,1>,<2,2>}恒等關(guān)系IA={<x,x>|x∈A}例如A={1,2},那么IA={<1,1>,<2,2>}小于等于關(guān)系LA={<x,y>|x,y∈A∧x≤y},A為實(shí)數(shù)子集例如A={1,2,3},B={a,b},那么

LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}10A上重要關(guān)系的實(shí)例(續(xù))定義7.5設(shè)A為集合,(2)(續(xù))整除關(guān)系DB={<x,y>|x,y∈B∧x整除y},B為非0整數(shù)子集例如A={1,2,3},B={a,b},那么DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}包含關(guān)系R={<x,y>|x,y∈A∧xy},A是集合族.例如A=P(B)={,{a},,{a,b}},那么A上的包含關(guān)系是R={<,>,<,{a}>,<,>,<,{a,b}>,<{a},{a}>,<{a},{a,b}>,<,>,<,{a,b}>,<{a,b},{a,b}>}類(lèi)似的還可以定義：大于等于關(guān)系,小于關(guān)系,大于關(guān)系,真包含關(guān)系等.11關(guān)系的表示1.關(guān)系矩陣假設(shè)A={x1,x2,…,xm}，B={y1,y2,…,yn}，R是從A到B的關(guān)系，R的關(guān)系矩陣是布爾矩陣MR=[rij]mn,其中rij=1<xi,yj>R.2.關(guān)系圖假設(shè)A={x1,x2,…,xm}，R是從A上的關(guān)系，R的關(guān)系圖是GR=<A,R>,其中A為結(jié)點(diǎn)集，R為邊集.如果<xi,xj>屬于關(guān)系R，在圖中就有一條從xi到xj的有向邊.注意：(1)關(guān)系矩陣適合表示從A到B的關(guān)系或A上的關(guān)系〔A,B為有窮集〕(2)關(guān)系圖適合表示有窮集A上的關(guān)系12實(shí)例例4A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R是A上的關(guān)系，其關(guān)系矩陣MR和關(guān)系圖GR如下：137.3關(guān)系的運(yùn)算關(guān)系的根本運(yùn)算1.定義域、值域與域定義7.6關(guān)系的定義域、值域與域分別定義為domR={x|y(<x,y>R)}ranR={y|x(<x,y>R)}fldR=domRranR例5R={<1,2>,<1,3>,<2,4>,<4,3>},那么domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}14定義域,值域,域(舉例)設(shè)A={1,2,3,4,5,6},B={a,b,c,d},R是從A到B關(guān)系 R={<2,a>,<2,b>,<3,b>,<4,d?,<6,d>}, 那么domR=??? ranR=???{2,3,4,6}{a,b,d}152.關(guān)系運(yùn)算——逆與合成定義7.7關(guān)系的逆運(yùn)算R

1={<y,x>|<x,y>

R}定義7.8關(guān)系的合成運(yùn)算R

S={<x,z>|

y(<x,y>

R

<y,z>

S)}

例6

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

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

R

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

R

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

S

R={<1,2>,<1,4>,<3,2>,<3,3>}16合成的圖示法利用圖示〔不是關(guān)系圖〕方法求合成R={<1,2>,<2,3>,<1,4>,<2,2>}S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}RS=???SR=???{<1,3>,<2,2>,<2,3>}{<1,2>,<1,4>,<3,2>,<3,3>}173.關(guān)系運(yùn)算——限制與像定義7.9設(shè)R為二元關(guān)系,A是集合(1)R在A上的限制記作R?A,其中

R?A={<x,y>|xRy∧x∈A}(2)A在R下的像記作R[A],其中

R[A]=ran(R?A)說(shuō)明：R在A上的限制R?A是R的子關(guān)系，即R?A

RA在R下的像R[A]是ranR

的子集，即R[A]

ranR

18實(shí)例(1)R?A={<x,y>|xRy∧x∈A}(2)R[A]=ran(R?A)例7設(shè)R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2>},那么R?{1}={<1,2>,<1,3>}R?=R?{2,3}={<2,2>,<2,4>,<3,2>}R[{1}]={2,3}R[]=R[{3}]={2}194.關(guān)系運(yùn)算的性質(zhì)(1)定理7.1設(shè)F是任意的關(guān)系,那么(1)(F1)1=F(2)domF1=ranF,ranF1=domF證明(1)任取<x,y>,由逆的定義有<x,y>∈(F1)1<y,x>∈F1<x,y>∈F.所以有(F1)1=F.(2)任取x,x∈domF1y(<x,y>∈F1)y(<y,x>∈F)x∈ranF所以有domF1=ranF.同理可證ranF1=domF.20定理7.2設(shè)F,G,H是任意的關(guān)系,那么(1)(FG)H=F(GH)(2)(FG)1=G1F1證明(1)任取<x,y>,<x,y>(FG)Ht(<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)關(guān)系運(yùn)算的性質(zhì)(2)21定理7.2證明(續(xù))定理7.2設(shè)F,G,H是任意的關(guān)系,那么(1)(FG)H=F(GH)(2)(FG)1=G1F1(2)任取<x,y>,<x,y>∈(FG)1<y,x>∈FGt(<y,t>∈F∧<t,x>∈G)t(<x,t>∈G1∧<t,y>∈F1)<x,y>∈G1F1所以(FG)1=G1F1拆解靠攏封裝22關(guān)系運(yùn)算的性質(zhì)(3)定理7.3設(shè)R為A上的關(guān)系,那么

RIA=IAR=R證任取<x,y>

<x,y>∈RIA

t(<x,t>∈R∧<t,y>∈IA)t(<x,t>∈R∧t=y∧y∈A)<x,y>∈R23關(guān)系運(yùn)算的性質(zhì)(4)定理7.4

(1)F

(G

H)=F

G∪F

H(2)(G∪H)

F=G

F∪H

F(3)F

(G∩H)

F

G∩F

H

(4)(G∩H)

F

G

F∩H

F只證(3)任取<x,y>,

<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>∈F

G∧<x,y>∈F

H

<x,y>∈F

G∩F

H所以有F

(G∩H)

F

G∩F

H24推廣定理7.4的結(jié)論可以推廣到有限多個(gè)關(guān)系

R

(R1∪R2∪…∪Rn)=R

R1∪R

R2∪…∪R

Rn

(R1∪R2∪…∪Rn)

R=R1

R∪R2

R∪…∪Rn

R

R

(R1∩R2∩…∩Rn)

R

R1∩R

R2∩…∩R

Rn

(R1∩R2∩…∩Rn)

R

R1

R∩R2

R∩…∩Rn

R

25關(guān)系運(yùn)算的性質(zhì)(5)定理7.5設(shè)F為關(guān)系,A,B為集合,那么限制與像的運(yùn)算存在下面的性質(zhì)：(1)F?(A∪B)=F?A∪F?B(2)F[A∪B]=F[A]∪F[B](3)F?(A∩B)=F?A∩F?B(4)F[A∩B]F[A]∩F[B]26證明(1)F?(A∪B)=F?A∪F?B證明：

(1)任取<x,y>

<x,y>∈F?(A∪B)

<x,y>∈F∧x∈A∪B

<x,y>∈F∧(x∈A∨x∈B)

(<x,y>∈F∧x∈A)∨(<x,y>∈F∧x∈B)

<x,y>∈F?A∨<x,y>∈F?B

<x,y>∈F?A∪F?B所以有F?(A∪B)=F?A∪F?B.27證明(4)F[A∩B]

F[A]∩F[B]證明：(4)任取y,y∈F[A∩B]

x(<x,y>∈F∧x∈A∩B)

x(<x,y>∈F∧x∈A∧x∈B)

x((<x,y>∈F∧x∈A)∧(<x,y>∈F∧x∈B))

x(<x,y>∈F∧x∈A)∧

x(<x,y>∈F∧x∈B)

y∈F[A]∧y∈F[B]

y∈F[A]∩F[B]

所以有F[A∩B]

F[A]∩F[B].

285.關(guān)系的冪運(yùn)算定義7.10設(shè)R為A上的關(guān)系,n為自然數(shù),那么R的n次冪定義為：(1)R0={<x,x>|x∈A}=IA(2)Rn+1=RnR注意：(1)對(duì)于A上的任何關(guān)系R1和R2，都有R10=R20=IA(2)對(duì)于A上的任何關(guān)系R，都有R1=R29

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

R與R2的關(guān)系矩陣分別是：冪的求法30R3和R4的矩陣是：因此M4=M2,即R4=R2.因此可以得到

R2=R4=R6=…，R3=R5=R7=…

R0的關(guān)系矩陣是冪的求法(續(xù))注意：僅是本例特有的結(jié)果，并非普遍規(guī)律31關(guān)系圖R0,R1,R2,R3,…的關(guān)系圖如以下圖所示：R0R1R2=R4=…R3=R5=…32冪運(yùn)算的性質(zhì)1定理7.6設(shè)A為n元集,R是A上的關(guān)系,那么存在自然數(shù)s和t,使得Rs=Rt.證明：R為A上的關(guān)系,由于|A|=n,A上的不同關(guān)系只有個(gè).列出R的各次冪

R0,R1,R2,…,,…,必存在自然數(shù)s和t使得Rs=Rt

33定理7.7設(shè)R是A上的關(guān)系,m,n∈N,那么(1)RmRn=Rm+n(2)(Rm)n=Rmn證用歸納法(1)對(duì)于任意給定的m∈N,施歸納于n.假設(shè)n=0,那么有RmR0=RmIA=Rm=Rm+0假設(shè)RmRn=Rm+n成立,那么有RmRn+1=Rm(RnR)=(RmRn)R=Rm+n+1,所以對(duì)一切m,n∈N有RmRn=Rm+n.冪運(yùn)算的性質(zhì)234冪運(yùn)算的性質(zhì)的證明(續(xù))定理7.7設(shè)R是A上的關(guān)系,m,n∈N,那么(1)RmRn=Rm+n(2)(Rm)n=Rmn(2)對(duì)于任意給定的m∈N,施歸納于n.假設(shè)n=0,那么有(Rm)0=IA=R0=Rm×0假設(shè)(Rm)n=Rmn成立,那么有(Rm)n+1=(Rm)nRm=(Rmn)Rn=Rmn+m=Rm(n+1)所以對(duì)一切m,n∈N有(Rm)n=Rmn.35定理7.8設(shè)R是A上的關(guān)系,假設(shè)存在自然數(shù)s,t(s<t)使得Rs=Rt,那么(1)對(duì)任何k∈N有Rs+k=Rt+k(2)對(duì)任何k,i∈N有Rs+kp+i=Rs+i,其中p=ts(3)令S={R0,R1,…,Rt1},那么對(duì)于任意的q∈N有Rq∈S證明：(1)Rs+k=RsRk=RtRk=Rt+k(2)對(duì)k歸納.假設(shè)k=0,那么有Rs+0p+i=Rs+i假設(shè)Rs+kp+i=Rs+i,其中p=ts,那么Rs+(k+1)p+i=Rs+kp+i+p=Rs+kp+iRp=Rs+iRp=Rs+p+i=Rs+ts+i=Rt+i=Rs+i由歸納法命題得證.冪運(yùn)算的性質(zhì)336證明定理7.8設(shè)R是A上的關(guān)系,假設(shè)存在自然數(shù)s,t(s<t)使得Rs=Rt,那么(3)令S={R0,R1,…,Rt1},那么對(duì)于任意的q∈N有Rq∈S證明：(3)任取q∈N,假設(shè)q<t,顯然有Rq∈S,假設(shè)q≥t,那么必存在自然數(shù)k和i使得q=s+kp+i,其中0≤i≤p1于是

Rq=Rs+kp+i=Rs+i而s+i≤s+p1=s+ts1=t1從而證明了Rq∈S.377.4關(guān)系的性質(zhì)定義7.11設(shè)R為A上的關(guān)系,(1)假設(shè)x(x∈A→<x,x>R),那么稱R在A上是自反的.(2)假設(shè)x(x∈A→<x,x>R),那么稱R在A上是反自反的.實(shí)例：自反：全域關(guān)系EA,恒等關(guān)系IA,小于等于關(guān)系LA,整除關(guān)系DA反自反：實(shí)數(shù)集上的小于關(guān)系、冪集上的真包含關(guān)系.A={1,2,3},R1,R2,R3是A上的關(guān)系,其中R1＝{<1,1>,<2,2>}R2＝{<1,1>,<2,2>,<3,3>,<1,2>}R3＝{<1,3>}R2自反，R3反自反，R1既不是自反的也不是反自反的.38對(duì)稱性與反對(duì)稱性定義7.12設(shè)R為A上的關(guān)系,

(1)假設(shè)xy(x,y∈A∧<x,y>∈R→<y,x>∈R),那么稱R為A上對(duì)稱的關(guān)系.(2)假設(shè)xy(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y),那么稱R為A上的反對(duì)稱關(guān)系.實(shí)例：對(duì)稱關(guān)系：A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系反對(duì)稱關(guān)系：A上的恒等關(guān)系IA和空關(guān)系設(shè)A＝{1,2,3},R1,R2,R3和R4都是A上的關(guān)系,其中R1＝{<1,1>,<2,2>}，R2＝{<1,1>,<1,2>,<2,1>}R3＝{<1,2>,<1,3>}，R4＝{<1,2>,<2,1>,<1,3>}R1：對(duì)稱和反對(duì)稱；R2：對(duì)稱；R3：反對(duì)稱；R4：不對(duì)稱、不反對(duì)稱解讀：xy時(shí)，如果有<x,y>∈R，那么必有<y,x>R39傳遞性定義7.13設(shè)R為A上的關(guān)系,假設(shè)

xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),那么稱R是A上的傳遞關(guān)系.實(shí)例：A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系，小于等于和小于關(guān)系，整除關(guān)系，包含與真包含關(guān)系……設(shè)A＝{1,2,3},R1,R2,R3是A上的關(guān)系,其中R1＝{<1,1>,<2,2>}R2＝{<1,2>,<2,3>}R3＝{<1,3>}R1和R3是A上的傳遞關(guān)系,R2不是A上的傳遞關(guān)系.40關(guān)系性質(zhì)成立的充要條件定理7.9設(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上對(duì)稱當(dāng)且僅當(dāng)R=R1(4)R在A上反對(duì)稱當(dāng)且僅當(dāng)R∩R1IA(5)R在A上傳遞當(dāng)且僅當(dāng)RRR41證明(1)定理7.9設(shè)R為A上的關(guān)系,那么(1)R在A上自反當(dāng)且僅當(dāng)IAR證明：必要性任取<x,y>,由于R在A上自反必有

<x,y>∈IAx,y∈A∧x=y<x,y>∈R從而證明了IAR充分性.任取x,有

x∈A<x,x>∈IA<x,x>∈R因此R在A上是自反的.42證明(3)定理7.9設(shè)R為A上的關(guān)系,那么(3)R在A上對(duì)稱當(dāng)且僅當(dāng)R=R1證明：必要性.任取<x,y>,

<x,y>∈R<y,x>∈R<x,y>∈R1所以R=R1充分性.任取<x,y>,由R=R1得

<x,y>∈R<y,x>∈R1<y,x>∈R所以R在A上是對(duì)稱的43證明(4)定理7.9設(shè)R為A上的關(guān)系,那么(4)R在A上反對(duì)稱當(dāng)且僅當(dāng)R∩R1IA證明：必要性.任取<x,y>,有<x,y>∈R∩R1<x,y>∈R∧<x,y>∈R1<x,y>∈R∧<y,x>∈Rx=yx,yA<x,y>∈IA這就證明了R∩R1IA充分性.任取<x,y>,有<x,y>∈R∧<y,x>∈R<x,y>∈R∧<x,y>∈R1<x,y>∈R∩R1<x,y>∈IAx=y從而證明了R在A上是反對(duì)稱的.44證明定理7.9設(shè)R為A上的關(guān)系,那么(5)R在A上傳遞當(dāng)且僅當(dāng)RRR證明：必要性.任取<x,y>有

<x,y>∈RRt(<x,t>∈R∧<t,y>∈R)<x,y>∈R所以RRR充分性.任取<x,y>,<y,z>∈R,那么

<x,y>∈R∧<y,z>∈R<x,z>∈RR<x,z>∈R所以R在A上是傳遞的45

自反性反自反性對(duì)稱性反對(duì)稱性傳遞性集合IA

RR∩IA=

R=R

1R∩R

1

IAR

R

R關(guān)系矩陣主對(duì)角線元素全是1主對(duì)角線元素全是0矩陣是對(duì)稱矩陣若rij＝1,且i≠j,則rji＝0M2中1位置,在M中相應(yīng)位置都是1關(guān)系圖每個(gè)頂點(diǎn)都有環(huán)每個(gè)頂點(diǎn)都沒(méi)有環(huán)兩點(diǎn)之間有邊,是一對(duì)方向相反的邊兩點(diǎn)之間有邊,并且是一條有向邊點(diǎn)xi到xj有邊,xj到xk有邊,則xi到xk也有邊關(guān)系性質(zhì)的三種等價(jià)條件五種性質(zhì)在關(guān)系矩陣和關(guān)系圖中的特點(diǎn)：46自反性反自反性對(duì)稱性反對(duì)稱性傳遞性R1

1

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1

R2

×√√√×R1

R2

√××××關(guān)系的性質(zhì)和運(yùn)算之間的聯(lián)系五種性質(zhì)與運(yùn)算的聯(lián)系：其中：(1)

√表示經(jīng)過(guò)某關(guān)系經(jīng)過(guò)該運(yùn)算后，這種性質(zhì)仍然能保持(2)

×表示經(jīng)過(guò)某關(guān)系經(jīng)過(guò)該運(yùn)算后，這種性質(zhì)不一定能保持477.5關(guān)系的閉包

主要內(nèi)容1.閉包定義2.閉包的構(gòu)造方法集合表示矩陣表示圖表示3.閉包的性質(zhì)48什么是閉包閉包(closure):包含具有指定性質(zhì)的對(duì)象的最小集合。1.“具有指定性質(zhì)的對(duì)象”。例:(平面上的凸點(diǎn)的集合)2.“最小”:任何包含同樣對(duì)象,具有同樣性質(zhì)的其它集合都包含該閉包集合。49三種常見(jiàn)閉包的定義定義7.14設(shè)R是非空集合A上的關(guān)系,R的自反(對(duì)稱或傳遞)閉包是A上的關(guān)系R

,使得R

滿足以下條件：(1)

R

是自反的(對(duì)稱的或傳遞的)(2)

R

R

(3)對(duì)A上任何包含R的自反(對(duì)稱或傳遞)關(guān)系R

有R

R

R的自反閉包記作r(R),對(duì)稱閉包記作s(R),傳遞閉包記作t(R).

解讀：限制了閉包是“最小”的。50閉包相關(guān)定理7.10定理7.10設(shè)R為A上的關(guān)系,那么有(1)r(R)=R∪R0(2)s(R)=R∪R1(3)t(R)=R∪R2∪R3∪…說(shuō)明：對(duì)有窮集A(|A|=n)上的關(guān)系,(3)中的并最多不超過(guò)Rn證明(1)：思路——證明滿足R∪R0閉包定義由IA=R0R∪R0知R∪R0是自反的,且滿足RR∪R0設(shè)R是A上包含R的自反關(guān)系,那么有RR和IAR.從而有R∪R0R.R∪R0滿足閉包定義,所以r(R)=R∪R0.51閉包相關(guān)定理7.10(續(xù))定理7.10證明.只證(1)和(3).(3)t(R)=R∪R2∪R3∪…證明：①先證R∪R2∪…

t(R)成立.用歸納法證明對(duì)任意正整數(shù)n有Rn

t(R).n=1時(shí)有R1=R

t(R).假設(shè)Rn

t(R)成立.那么對(duì)任意的<x,y>

<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+1

t(R).52證明定理7.10(3)(續(xù))定理7.10證明.只證(1)和(3).(3)t(R)=R∪R2∪R3∪…證明：②再證t(R)R∪R2∪…成立,為此只須證明R∪R2∪…傳遞.任取<x,y>,<y,z>,那么<x,y>∈R∪R2∪…∧<y,z>∈R∪R2∪…t(<x,y>∈Rt)∧s(<y,z>∈Rs)ts(<x,z>∈RtRs)ts(<x,z>∈Rt+s)<x,z>∈R∪R2∪…從而證明了R∪R2∪…是傳遞的.53閉包的矩陣表示1.矩陣表示設(shè)關(guān)系R,r(R),s(R),t(R)的關(guān)系矩陣分別為M,Mr,Ms和Mt那么:(1)Mr=M+E(2)Ms=M+M'(3)Mt=M+M2+M3+…E是單位矩陣,M'是轉(zhuǎn)置矩陣，相加時(shí)使用邏輯加.54閉包運(yùn)算舉例例:設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}.求r(R),s(R).解:abcd55閉包運(yùn)算舉例(續(xù)1，求r(R)和s(R))解(續(xù)1):abcdabcdabcdr(R)=RIAG(r(R))G(s(R))56傳遞閉包的計(jì)算(Warshall算法)設(shè)關(guān)系R的傳遞閉包為t(R)，其矩陣表示為Mt。輸入：M輸出：Mt(1)用關(guān)系矩陣M表示關(guān)系R(2)置變量j=1(3)對(duì)于所有i，如果mij=1,對(duì)可k=1,2,…,n,置mik=mik+mjk(布爾加〕即：將第i行與第j行相加，所得結(jié)果寫(xiě)回第i行。(4)j=j+1;(5)如果j≤n,轉(zhuǎn)至步驟(3),否那么停止。R

M，j=1結(jié)束開(kāi)始mij=1mik=mik+mjk++j<=nYNYN57Warshall算法應(yīng)用舉例例：設(shè)關(guān)系R的關(guān)系矩陣表示如以下圖M所示，求它的傳遞閉包。0100101000010000MA

M，j=1結(jié)束開(kāi)始mij=1mik=mik+mjk++j<=nYNYN58Warshall算法應(yīng)用舉例(續(xù))j=1

m21=1，i=2;第i行：1010第j行：0100+1110相加之后寫(xiě)回第i行：0100101000010000MA

M，j=1結(jié)束開(kāi)始m21

=1m2k=m2k+m1k++j<=nYNYNmij1布爾加：0＋0=00＋1=11+0=11＋0=1

1+1=159Warshall算法應(yīng)用舉例(續(xù))j=j+1∧n=4

j=1

+1=2

j<=n0100101000010000MA

M，j=1結(jié)束開(kāi)始m21

=1m2k=m2k+m1k++j<=nYNYNmij160Warshall算法應(yīng)用舉例(續(xù))j=2

m12=1;i=1第i行：0100第j行：1110+1110相加之后寫(xiě)入第i行：0100101000010000MA

M，j=1結(jié)束開(kāi)始m12=1m1k=m1k+m2k++j<=nYNYNmij111注意：第j行中存在m22=1,仍然需要再作一次加法。61Warshall算法應(yīng)用舉例(續(xù))j=j+1∧n=4j=2+1=2j<=n0100101000010000MA

M，j=1結(jié)束開(kāi)始m22=1m2k=m2k+m2k++j<=nYNYNmij11162Warshall算法應(yīng)用舉例(續(xù))0100101000010000M111訪問(wèn)m22之后，將依次訪問(wèn):第3列：m13,m23第4列：m14,m24,m34mij11A

M，j=1結(jié)束開(kāi)始mij=1mik=mik+mjk++j<=nYNYNj=4

j<=n不成立，程序運(yùn)行結(jié)束63Warshall算法舉例例：設(shè)A={a,b,c,d,e},R={<a,b>,<b,c>,<c,a>,<d,e>,<e,a>},求t(R)64閉包的關(guān)系圖表示2.關(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),假設(shè)沒(méi)環(huán)就加一個(gè)環(huán)，得到Gr(2)考察G的每條邊,假設(shè)有一條xi到xj的單向邊,i≠j,那么在G中加一條xj到xi的反向邊,得到Gs(3)考察G的每個(gè)頂點(diǎn)xi,找xi可達(dá)的所有頂點(diǎn)xj(允許i=j)，如果沒(méi)有從xi到xj的邊,就加上這條邊,得到圖Gt65實(shí)例例9設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},求R和r(R),

s(R),

t(R)的關(guān)系圖.Rr(R)s(R)t(R)665.閉包的性質(zhì)1定理7.11設(shè)R是非空集合A上的關(guān)系,那么(1)R是自反的當(dāng)且僅當(dāng)r(R)=R.(2)R是對(duì)稱的當(dāng)且僅當(dāng)s(R)=R.(3)R是傳遞的當(dāng)且僅當(dāng)t(R)=R.證明：(1)根據(jù)閉包的定義，有Rr(R)。R是自反的，即R是包含了R的自反關(guān)系，于是有r(R)R。所以，r(R)=R。定理7.12設(shè)R1和R2是非空集合A上的關(guān)系,且R1R2,那么(1)r(R1)r(R2)(2)s(R1)s(R2)(3)t(R1)t(R2)67定理7.13設(shè)R是非空集合A上的關(guān)系,(1)假設(shè)R是自反的,那么s(R)與t(R)也是自反的(2)假設(shè)R是對(duì)稱的,那么r(R)與t(R)也是對(duì)稱的(3)假設(shè)R是傳遞的,那么r(R)是傳遞的.說(shuō)明：如果需要進(jìn)行多個(gè)閉包運(yùn)算，比方求R的自反、對(duì)稱、傳遞的閉包tsr(R)，運(yùn)算順序如下：tsr(R)=t(r(s(R)))閉包的性質(zhì)2原因：t(R)最后才計(jì)算，是為了不失傳遞性。68定理7.13設(shè)R是非空集合A上的關(guān)系,(2)假設(shè)R是對(duì)稱的,那么r(R)與t(R)也是對(duì)稱的證明：先證r(R)是對(duì)稱的。習(xí)題七第20題的結(jié)論：(R1∪R2)-1=R1-1∪R2-1r(R)-1=(R∪IA)-1=R-1∪IA-1=R∪IA(∵R是對(duì)稱的∴R-1=R)=r(R)∴r(R)是對(duì)稱的閉包的性質(zhì)2證明69定理7.13設(shè)R是非空集合A上的關(guān)系,(2)假設(shè)R是對(duì)稱的,那么r(R)與t(R)也是對(duì)稱的證明：再證t(R)是對(duì)稱的。預(yù)備結(jié)論：如果R是對(duì)稱的，那么Rn也是對(duì)稱的。用歸納法.n=1時(shí)，R1=R，所以R1是對(duì)稱的。現(xiàn)假設(shè)Rn是對(duì)稱的，那么對(duì)任取<x,y>，<x,y>Rn+1t(<x,t>Rn<t,y>R)t(<t,x>Rn<y,t>R)<y,x>RRn<y,x>Rn+1∴Rn+1是對(duì)稱的，預(yù)備結(jié)論成立閉包的性質(zhì)2證明(續(xù)1)70定理7.13設(shè)R是非空集合A上的關(guān)系,(2)假設(shè)R是對(duì)稱的,那么r(R)與t(R)也是對(duì)稱的證明：再證t(R)是對(duì)稱的。預(yù)備結(jié)論：如果R是對(duì)稱的，那么Rn也是對(duì)稱的。任取<x,y>，<x,y>t(R)n(<x,y>Rn)(∵t(R)=R∪R2∪R3∪…)n(<y,x>Rn)<y,x>t(R)∴t(R)是對(duì)稱的，結(jié)論成立閉包的性質(zhì)2證明(續(xù)2)717.6等價(jià)關(guān)系與劃分

主要內(nèi)容1.

等價(jià)關(guān)系的定義與實(shí)例2.

等價(jià)類(lèi)及其性質(zhì)3.

商集與集合的劃分4.

等價(jià)關(guān)系與劃分的一一對(duì)應(yīng)72等價(jià)關(guān)系的定義與實(shí)例定義7.15設(shè)R為非空集合上的關(guān)系.如果R是自反的、對(duì)稱的和傳遞的,那么稱R為A上的等價(jià)關(guān)系.設(shè)R是一個(gè)等價(jià)關(guān)系,假設(shè)<x,y>∈R,稱x等價(jià)于y,記做x～y.實(shí)例設(shè)A={1,2,…,8},如下定義A上的關(guān)系R：R={<x,y>|x,y∈A∧x≡y(mod3)}其中x≡y(mod3)叫做x與y模3相等,即x除以3的余數(shù)與y除以3的余數(shù)相等.不難驗(yàn)證R為A上的等價(jià)關(guān)系,因?yàn)?1)x∈A,有x≡x(mod3)(2)x,y∈A,假設(shè)x≡y(mod3),那么有y≡x(mod3)(3)x,y,z∈A,假設(shè)x≡y(mod3),y≡z(mod3),那么有x≡z(mod3)73設(shè)A={1,2,…,8},如下定義A上的關(guān)系R：R={<x,y>|x,y∈A∧x≡y(mod3)}模3等價(jià)關(guān)系的關(guān)系圖：等價(jià)關(guān)系的實(shí)例74等價(jià)類(lèi)定義定義7.16設(shè)R為非空集合A上的等價(jià)關(guān)系,

x∈A，令

[x]R

={y|y∈A∧xRy}稱[x]R為x關(guān)于R的等價(jià)類(lèi),簡(jiǎn)稱為x的等價(jià)類(lèi),簡(jiǎn)記為[x]或?qū)嵗?/p>

A={1,2,…,8}上模3等價(jià)關(guān)系的等價(jià)類(lèi)：[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}75等價(jià)類(lèi)的性質(zhì)定理7.14設(shè)R是非空集合A上的等價(jià)關(guān)系,那么(1)xA,[x]是A的非空子集(2)x,yA,如果xRy,那么[x]=[y](3)x,yA,如果xy,那么[x]∩[y]=(4)∪{[x]|xA}=A證明：(1)由定義,xA有[x]A.又x[x],即[x]非空.(2)任取z,那么有z∈[x]<x,z>∈R<z,x>∈R∴<z,x>R∧<x,y>R<z,y>R<y,z>R從而證明了z∈[y].綜上所述必有[x][y].同理可證[y][x].這就得到了[x]=[y].性質(zhì)2說(shuō)明：彼此等價(jià)的元素屬于同一個(gè)等價(jià)類(lèi)。性質(zhì)1說(shuō)明：A中每個(gè)元素所生成的等價(jià)類(lèi)非空。76等價(jià)類(lèi)的性質(zhì)證明(續(xù)1)定理7.14設(shè)R是非空集合A上的等價(jià)關(guān)系,那么(3)x,yA,如果xy,那么[x]∩[y]=證明：(3)假設(shè)[x]∩[y]≠,那么存在z[x]∩[y],從而有z[x]∧z[y],即<x,z>R∧<y,z>R成立.根據(jù)R的對(duì)稱性和傳遞性必有<x,y>R,與xy矛盾性質(zhì)3說(shuō)明：彼此不等價(jià)的元素屬于不同的等價(jià)類(lèi)，且等價(jià)類(lèi)之間無(wú)公共元素。77等價(jià)類(lèi)的性質(zhì)證明(續(xù))定理7.14設(shè)R是非空集合A上的等價(jià)關(guān)系,那么(4)∪{[x]|xA}=A證明：(4)先證∪{[x]|xA}A.任取y,y∪{[x]|xA}x(xA∧y[x])y[x]∧[x]AyA從而有∪{[x]|x∈A}A再證A∪{[x]|x∈A}.任取y,yAy[y]∧yAy∈∪{[x]|xA}從而有∪{[x]|x∈A}A成立.綜上所述得∪{[x]|xA}=A.性質(zhì)4說(shuō)明：所有等價(jià)類(lèi)的并集等于A。78商集與劃分定義7.17設(shè)R為非空集合A上的等價(jià)關(guān)系,以R的所有等價(jià)類(lèi)作為元素的集合稱為A關(guān)于R的商集,記做A/R,

A/R={[x]R

|x∈A}實(shí)例：設(shè)A={1,2,…,8}，A關(guān)于模3等價(jià)關(guān)系R的商集為

A/R={{1,4,7},{2,5,8},{3,6}}A關(guān)于恒等關(guān)系和全域關(guān)系的商集為：

A/IA

={{1},{2},…,{8}}，A/EA

={{1,2,…,8}79劃分及其舉例定義7.18設(shè)A為非空集合,假設(shè)A的子集族π(πP(A))滿足:(1)π(2)xy(x,yπ∧x≠y→x∩y=)(3)∪π=A那么稱π是A的一個(gè)劃分,稱π中的元素為A的劃分塊.例10設(shè)A＝{a,b,c,d},給定1,2,3,4,5,6如下：1={{a,b,c},46c4664}2={{a,b},{c},666qkgw}3={{a},{a,b,c,d}}4={{a,b},{c}}5={,{a,b},{c,d}}6={{a,{a}},{b,c,d}}那么1和2是A的劃分,其他都不是A的劃分.80例11給出A＝{1,2,3}上所有的等價(jià)關(guān)系實(shí)例123

1

123

5123

2123

4123

3

1對(duì)應(yīng)EA,

5

對(duì)應(yīng)IA,

2,

3

和

4分別對(duì)應(yīng)R2,R3和R4.

R2={<2,3>,<3,2>}∪IA

R3={<1,3>,<3,1>}∪IA

R4={<1,2>,<2,1>}∪IA解先做出A的劃分,從左到右分別記作

1,

2,

3,

4,

5.81等價(jià)關(guān)系與劃分是一一對(duì)應(yīng)的定理:設(shè)A,那么(1)R是A上的等價(jià)關(guān)系A(chǔ)/R是A的劃分；等價(jià)類(lèi)就是劃分塊。(2)是A的劃分R是A上的等價(jià)關(guān)系，其中xRyB(BxByB)R稱為由劃分所定義的等價(jià)關(guān)系(同塊關(guān)系).“劃分”的概念和“等價(jià)關(guān)系”的概念,在本質(zhì)上是相同的。82定義：設(shè)R是集合A上的二元關(guān)系,假設(shè)R是自反的和對(duì)稱的,那么稱R是相容關(guān)系。例：在一群人的集合中,年齡相等是相容關(guān)系,朋友關(guān)系也是相容關(guān)系。注意:(1)等價(jià)關(guān)系是具有傳遞性的相容關(guān)系;(2)相容關(guān)系是的關(guān)系矩陣是對(duì)稱的，且主對(duì)角線元素全為1。(3)相容關(guān)系也可以看作是“同組關(guān)系”，但允許集合中的元素可以同時(shí)是假設(shè)干組中的成員。相容關(guān)系83例設(shè)A={cat,teacher,cold,desk,knife,by} 那么R={?x,y?|x,yA且x和y至少有一個(gè)相同的字母} 是A上的一個(gè)相容關(guān)系,簡(jiǎn)記A中元素依次為a,b,c,d,e,f,那么R的關(guān)系矩陣MR和對(duì)應(yīng)簡(jiǎn)化的下三角矩陣TR為: abcdefa111000b111110 1MR=c111100 11d011110 TR=011e010110 0101f000001 00000相容類(lèi){a,b},{a,c},{b,c},{f},{b,d,e}等abcdefabcdebcdef相容關(guān)系舉例84在相容關(guān)系的關(guān)系圖上,每個(gè)頂點(diǎn)都有自環(huán)且每?jī)蓚€(gè)頂點(diǎn)間的弧線都是成對(duì)出現(xiàn)的。為簡(jiǎn)化相容關(guān)系的關(guān)系圖,不畫(huà)自環(huán),并用無(wú)箭頭的單線段代替來(lái)回弧線,使之成為無(wú)向圖。s上例的關(guān)系圖如下:相容關(guān)系的關(guān)系圖85相容類(lèi)定義:設(shè)R是集合A上的相容關(guān)系,假設(shè)CA,并且任意a,bC都有aRb,那么稱C是由R產(chǎn)生的相容類(lèi).例：在上例的相容關(guān)系可產(chǎn)生相容類(lèi){a,b},{a,c},{b,c},{f},{b,d,e}等。A={cat,teacher,cold,desk,knife,by}86相容類(lèi)與等價(jià)類(lèi)(劃分)的比較

(1)[a]R≠;(2)B,C(B,C

BCBC=)(3)∪[a]R

=A等價(jià)類(lèi)

相容類(lèi)

?√√√√×87最大相容類(lèi)最大相容類(lèi):不能再增加新的元素構(gòu)成新相容類(lèi)的相容類(lèi)，記為CR。也可以這樣理解最大相容類(lèi)CR:(等價(jià)定義)對(duì)x∈CR,x必與CR中所有元素有相容關(guān)系,而在差集A–CR中沒(méi)有任何元素與CR中所有元素都是相容的。88最大相容類(lèi)的求法求法：通過(guò)極大完全子圖求最大相容類(lèi)定義：在R的關(guān)系圖表示中，極大完全子圖是指每對(duì)頂點(diǎn)都有邊相連的多邊形?！皹O大”的含義是:如果一個(gè)極大完全子圖在添加任何新的頂點(diǎn)后就不再成為極大完全子圖。每個(gè)極大完全子圖的頂點(diǎn)集合就是一個(gè)最大相容類(lèi)。最大相容類(lèi)外的任何元素不可能與類(lèi)內(nèi)的所有元素具有R關(guān)系。另外孤立頂點(diǎn),以及不在極大完全子圖兩個(gè)頂點(diǎn)及其連線,也是最大相容類(lèi)。89n=1 n=2n=3 n=4 n=5

上圖給出了n=1,2,3,4,5時(shí)的極大完全子圖。注意：對(duì)于集合A上的相容關(guān)系R,如果我們能夠找到關(guān)系圖GR所有的極大完全子圖,也就找到關(guān)系R中所有的最大相容類(lèi)。極大完全子圖舉例190例：設(shè)給定關(guān)系R的相容關(guān)系圖表示成以下圖,寫(xiě)出所有的最大相容類(lèi)。方法：找到一個(gè)較小的完全子圖，逐步擴(kuò)充頂點(diǎn)，直到不能繼續(xù)擴(kuò)充為止。解：R的最大相容類(lèi)：極大完全子圖舉例2{h}{a,b}{d,e,f}{b,c,d,f,g}91完全覆蓋定義：設(shè)={A1,A2,…,An}是集合A的覆蓋,假設(shè)Ai,Aj(Ai,Aj∧AiAj)那么稱為A的完全覆蓋。即：完全覆蓋中的任意元素不能是其它元素的子集。 續(xù)上例：3={{a},{b,e},{b,c,d}}， 4={{a},{b,c},{b,d,e}}92從相容類(lèi)定義可知,A中任一元素a可組成相容類(lèi){a},并且必包含在一個(gè)最大相容類(lèi)CR中。如果由所有最大相容類(lèi)構(gòu)造一個(gè)集合族,那么A中每個(gè)元素至少屬于的一個(gè)成員之中,所以最大相容類(lèi)集合必覆蓋集合A。我們由此給出完全覆蓋的另一等價(jià)定義。定義2：設(shè)R是集合A上的相容關(guān)系,其最大相容類(lèi)的集合稱為集合A的完全覆蓋,記作CR(A)。完全覆蓋的等價(jià)定義93覆蓋的幾點(diǎn)注意1.集合A的覆蓋不是唯一的。對(duì)給定的相容關(guān)系R,可以構(gòu)造不同的相容類(lèi)的集合,使它們都是A的覆蓋。2.給定集合A上的一個(gè)覆蓋,必可在A上構(gòu)造對(duì)應(yīng)于此覆蓋的一個(gè)相容關(guān)系,但是不同的覆蓋卻能構(gòu)造相同的相容關(guān)系。

確定一個(gè)覆蓋確定相容關(guān)系確定一個(gè)相容關(guān)系確定覆蓋94舉例例：設(shè)A={a,b,c,d},集合

1={{a,b,c},{c,d}}和

2={{a,b},{a,c},{b,c},{c,d}}是A的不同覆蓋,但它們可以產(chǎn)生相同的相容關(guān)系： R={<a,a>,<a,b>,<b,a,>,<b,b>,<b,c>,<c,b>,<a,c>,<c,a>,<c,c>,<c,d>,<d,c>,<d,d>}。3.但正如等價(jià)關(guān)系與劃分之間的聯(lián)系一樣,集合A上的相容關(guān)系R確定唯一的完全覆蓋CR(A),A上的完全覆蓋CR(A)確定唯一的相容關(guān)系R。95定理證明定理：設(shè)={A1,A2,…,An}是A的覆蓋,由決定的關(guān)系 R=(A1A1)∪(A2A2)∪…∪(AnAn)是A的的一個(gè)相容關(guān)系。證明：因?yàn)锳=A1∪A2∪…∪An, 自反性：對(duì)任一xA,必有某i使xAi, 那么?x,x?AiAiR,因此R是自反的。 對(duì)稱性：又對(duì)任意x,yA且?x,y?R,必存在j, 使?x,y?AjAj,即x,yAj, 那么?y,x?AjAjR,因此R是對(duì)稱的。 所以得證R是A上的一個(gè)相容關(guān)系。967.7偏序關(guān)系

主要內(nèi)容1.偏序關(guān)系偏序關(guān)系的定義偏序關(guān)系的實(shí)例2.偏序集與哈斯圖3.偏序集中的特殊元素及其性質(zhì)極大元、極小元、最大元、最小元上界、下界、最小上界、最大下界97定義與實(shí)例定義7.19偏序關(guān)系：非空集合A上的自反、反對(duì)稱和傳遞的關(guān)系，記作?.設(shè)?為偏序關(guān)系,如果<x,y>∈?,那么記作x?y,讀作x“小于或等于”y.實(shí)例集合A上的恒等關(guān)系IA是A上的偏序關(guān)系.小于或等于關(guān)系,整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的偏序關(guān)系.注意：并非指一般的數(shù)的大小，而是指偏序關(guān)系中的順序性。98相關(guān)概念定義7.20設(shè)R為非空集合A上的偏序關(guān)系,(1)x,y∈A,x與y可比x?y∨y?x(2)任取元素x和y,可能有下述幾種情況發(fā)生：

x?y(或y?x),x＝y(tǒng),x與y不是可比的定義7.21R為非空集合A上的偏序關(guān)系,(1)x,y∈A,x與y都是可比的，那么稱R為全序〔或線序〕關(guān)系實(shí)例：數(shù)集上的小于或等于關(guān)系是全序關(guān)系；整除關(guān)系不是正整數(shù)集合上的全序關(guān)系定義7.22x,y∈A,如果x?y且不存在z∈A使得x?z?y,那么稱y覆蓋x.例如{1,2,4,6}集合上整除關(guān)系,2覆蓋1,4和6覆蓋2,4不覆蓋1.99偏序集與哈斯圖定義7.23集合A和A上的偏序關(guān)系?一起叫做偏序集,記作<A,?>.實(shí)例:<Z,≤>,<P(A),R>哈斯圖:利用偏序關(guān)系的自反、反對(duì)稱、傳遞性進(jìn)行簡(jiǎn)化的關(guān)系圖特點(diǎn)：(1)每個(gè)結(jié)點(diǎn)沒(méi)有環(huán) (2)兩個(gè)連通的結(jié)點(diǎn)之間的序關(guān)系通過(guò)結(jié)點(diǎn)位置的上下表示，位置低的元素的順序在前(3)具有覆蓋關(guān)系的兩個(gè)結(jié)點(diǎn)之間連邊注意：偏序集是一個(gè)有序?qū)Α?00實(shí)例1例12偏序集<{1,2,3,4,5,6,7,8,9},

R整除>和<P({a,b,c}),R

>的哈斯圖.

101例13偏序集<A,R>的哈斯圖如以下圖所示,試求出集合A和關(guān)系R的表達(dá)式.

解A={a,b,c,d,e,f,g,h}R={<b,d>,<b,e>,<b,f>,<c,d>,<c,e>,<c,f>,<d,f>,<e,f>,<g,h>}∪IA實(shí)例2102偏序集中的特殊元素

定義7.24設(shè)<A,?>為偏序集,BA,y∈B(1)假設(shè)x(x∈B→y?x)成立,那么稱y為B的最小元(2)假設(shè)x(x∈B→x?y)成立,那么稱y為B的最大元(3)假設(shè)x(x∈B∧x?y→x=y)成立,那么稱y為B的極小元(4)假設(shè)x(x∈B∧y?x→x=y)成立,那么稱y為B的極大元性質(zhì)：(1)對(duì)于有窮集，極小元和極大元一定存在，可能存在多個(gè).(2)最小元和最大元不一定存在，如果存在一定惟一.(3)最小元一定是極小元；最大元一定是極大元.(4)孤立結(jié)點(diǎn)既是極小元，也是極大元.103定義7.25設(shè)<A,?>為偏序集,BA,y∈A(1)假設(shè)x(x∈B→x?y)成立,那么稱y為B的上界(2)假設(shè)x(x∈B→y?x)成立,那么稱y為B的下界(3)令C＝{y|y為B的上界},C的最小元為B的最小上界或上確界(4)令D＝{y|y為B的下界},D的最大元為B的最大下界或下確界性質(zhì)：(1)下界、上界、下確界、上確界不一定存在(2)下界、上界存在不一定惟一(3)下確界、上確界如果存在，那么惟一(4)集合的最小元是其下確界，最大元是其上確界；反之未必.偏序集中的特殊元素(續(xù))

104實(shí)例例14設(shè)偏序集<A,?>如下圖，求A的極小元、最小元、極大元、最大元，設(shè)B＝{b,c,d},求B的下界、上界、下確界、上確界.解極小元：a,b,c,g；極大元：a,f,h；沒(méi)有最小元與最大元.B的下界和最大下界都不存在；上界有d和f,最小上界為d.

105實(shí)例例15設(shè)X為集合,A＝P(X)－{}－{X},且A≠.假設(shè)|X|=n,n≥2.問(wèn)：(1)偏序集<A,R>是否存在最大元？(2)偏序集<A,R>是否存在最小元？(3)偏序集<A,R>中極大元和極小元的一般形式是什么？并說(shuō)明理由.解：(1)<A,R>不存在最大元,因?yàn)閚≥2.(2)<A,R>不存在最小元,因?yàn)閚≥2.(3)<A,R>的極小元就是X的所有單元集,即{x},x∈X.<A,R>的極大元恰好比X少一個(gè)元素,即X{x},x∈X.106第七章習(xí)題課

主要內(nèi)容有序?qū)εc笛卡兒積的定義與性質(zhì)二元關(guān)系、從A到B的關(guān)系、A上的關(guān)系關(guān)系的表示法：關(guān)系表達(dá)式、關(guān)系矩陣、關(guān)系圖關(guān)系的運(yùn)算：定義域、值域、域、逆、合成、限制、像、冪關(guān)系運(yùn)算的性質(zhì):A上關(guān)系的自反、反自反、對(duì)稱、反對(duì)稱、傳遞的性質(zhì)A上關(guān)系的自反、對(duì)稱、傳遞閉包A上的等價(jià)關(guān)系、等價(jià)類(lèi)、商集與A的劃分A上的偏序關(guān)系與偏序集107根本要求熟練掌握關(guān)系的三種表示法能夠判定關(guān)系的性質(zhì)〔等價(jià)關(guān)系或偏序關(guān)系〕掌握含有關(guān)系運(yùn)算的集合等式掌握等價(jià)關(guān)系、等價(jià)類(lèi)、商集、劃分、哈斯圖、偏序集等概念計(jì)算AB,do