關(guān)系與序關(guān)系課件

第二章關(guān)系與序關(guān)系2.1關(guān)系的概念[二元關(guān)系]一對(duì)對(duì)象之間的關(guān)系稱為二元關(guān)系。第二章關(guān)系與序關(guān)系2.1關(guān)系的概念12.1關(guān)系的概念[例]

teachers={a,b,c}，students={x,y,z}

建立教學(xué)關(guān)系T:aTxiffaTEACHINGx用序偶集合表示為：T={<a,x>,<a,z>,<b,y>,<c,y>,<c,z>}Tteachersstudents圖示為：2.1關(guān)系的概念[例]teachers={a,b,c}，22.1關(guān)系的概念[例]

Subroutines={a,b,c,d,e}子程序間調(diào)用關(guān)系Calling={<a,a>,<a,b>,<a,d>,<b,a>,<b,c>,<c,c>,<c,e>,<d,d>}CallingSubroutinesSubroutines圖示為：2.1關(guān)系的概念[例]Subroutines={a,b,32.1關(guān)系的概念[二元關(guān)系的集合定義]任何一個(gè)序偶的集合R={<x,y>|xXyY}都確定了一種二元關(guān)系，稱為從X到Y(jié)的二元關(guān)系。

<x,y>R可記為xRy，顯然RXY

<x,y>R可記為xRy當(dāng)X=Y即X與Y同一時(shí)，稱R為X上的一個(gè)二元關(guān)系。從X到Y(jié)的任何二元關(guān)系，都可用一個(gè)序偶集合來表示：R={<x,y>|xXyYxRy}2.1關(guān)系的概念[二元關(guān)系的集合定義]任何一個(gè)序偶的集合42.1關(guān)系的概念[例]

F={<x,y>|x是y的父親}

S={<x,y>|x,y為正整數(shù)且x可整除y}T={<y2,y>|y為實(shí)數(shù)}2.1關(guān)系的概念[例]52.1關(guān)系的概念[定義域]設(shè)二元關(guān)系S。由<x,y>S的所有對(duì)象x組成的集合稱為S的定義域，記為Dom(S)。[值域]由<x,y>S的所有對(duì)象y組成的集合稱為S的值域，記為Ran(S)(Range(S))。記

F(S)=D(S)R(S)，稱為S的域。描述：Dom(S)={x|(y)(<x,y>S)}Ran(S)={y|(x)(<x,y>S)}2.1關(guān)系的概念[定義域]設(shè)二元關(guān)系S。由<x,y>62.1關(guān)系的概念若干特殊關(guān)系：①X到Y(jié)的全域關(guān)系：Ex,y=XY

特別地：

Ex,x=XX②空關(guān)系：

③恒等關(guān)系：Ix={<xi,xi>|xiX}[例]設(shè)X={1,2,3,4}，求X上的關(guān)系“>”(大于)及其定義域、值域。2.1關(guān)系的概念若干特殊關(guān)系：72.2關(guān)系的表示方法(1)集合表示法借用集合的各種描述方法對(duì)表示關(guān)系的序偶集合進(jìn)行描述(2)關(guān)系矩陣設(shè)X={x1,x2,…,xm}，Y={y1,y2,…,yn}，m,n<+R是X到Y(jié)的二元關(guān)系。構(gòu)造矩陣MR=[mij]mn，mij

=<xi,yj>R0其它2.2關(guān)系的表示方法(1)集合表示法MR=[mij]m82.2關(guān)系的表示方法[例]非0行對(duì)應(yīng)元素構(gòu)成D(S)非0列對(duì)應(yīng)元素構(gòu)成R(S)2.2關(guān)系的表示方法[例]非0行對(duì)應(yīng)元素構(gòu)成D(S)92.2關(guān)系的表示方法(3)關(guān)系圖表示法用結(jié)點(diǎn)表示X、Y上的元素；若<x,y>R則從結(jié)點(diǎn)x到結(jié)點(diǎn)y畫一條弧。[例]上述Teaching關(guān)系的關(guān)系圖：2.2關(guān)系的表示方法(3)關(guān)系圖表示法102.2關(guān)系的表示方法[例]設(shè)X={1,2,3,4}，X上的關(guān)系“>”：2.2關(guān)系的表示方法[例]設(shè)X={1,2,3,4}，X112.3關(guān)系的性質(zhì)[定義]設(shè)R是X上的二元關(guān)系，則：①R是自反的

(x)(xXxRx)②R是對(duì)稱的

(x)(y)(x,yXxRyyRx)③R是傳遞的

(x)(y)(z)(x,y,zXxRyyRz

xRz)④R是反自反的

(x)(xX?(xRx))⑤R是反對(duì)稱的

(x)(y)(x,yXxRyyRx

x=y)2.3關(guān)系的性質(zhì)[定義]設(shè)R是X上的二元關(guān)系，則：122.3關(guān)系的性質(zhì)[例]整數(shù)集合上的若干關(guān)系及其性質(zhì)整除=≤＜自反性對(duì)稱性傳遞性反自反性反對(duì)稱性判定關(guān)系“＜”的反對(duì)稱性的前提條件總為F,理論上反對(duì)稱性成立。2.3關(guān)系的性質(zhì)[例]整數(shù)集合上的若干關(guān)系及其性質(zhì)整除=132.3關(guān)系的性質(zhì)存在著既非自反也非反自反的關(guān)系，如：存在著既對(duì)稱又反對(duì)稱的關(guān)系，如：2.3關(guān)系的性質(zhì)存在著既非自反也非反自反的關(guān)系，如：存在著142.3關(guān)系的性質(zhì)存在著既非對(duì)稱又非反對(duì)稱的關(guān)系，如：2.3關(guān)系的性質(zhì)存在著既非對(duì)稱又非反對(duì)稱的關(guān)系，如：152.3關(guān)系的性質(zhì)從關(guān)系矩陣和關(guān)系圖看關(guān)系的性質(zhì)：R是自反的：MR的對(duì)角元均為1；關(guān)系圖為自環(huán)圖。R是對(duì)稱的：MR為對(duì)稱矩陣；關(guān)系圖中弧成對(duì)出現(xiàn)。R是反自反的：MR的對(duì)角元均為0；關(guān)系圖為無自環(huán)圖。R是反對(duì)稱的：MR為反對(duì)稱矩陣；關(guān)系圖中只出現(xiàn)單向弧。2.3關(guān)系的性質(zhì)從關(guān)系矩陣和關(guān)系圖看關(guān)系的性質(zhì)：162.4集合的劃分與覆蓋[定義]給定集合S，A={A1,A2,…,An}，AiS，i=1..n。②若①成立且AiAj=(若ij)，則說A是S的一個(gè)劃分，并稱A1,A2,…,An為此劃分的塊。2.4集合的劃分與覆蓋[定義]給定集合S，A={A1,A172.4集合的劃分與覆蓋[例]

N={0,1,2,3,4,……}自然數(shù)集合。取A0={0,6,12,18,……}A1={1,7,13,19,……}A2={2,8,14,20,……}……A5={5,11,17,23,……}則A={A0，A1，A2，A3，A4，A5}是N的一個(gè)劃分。2.4集合的劃分與覆蓋[例]N={0,1,2,3,4,182.4集合的劃分與覆蓋[例]

S={a,b,c}取A={{a},,{c}}B={{a,b},{c}}C={{a,b,c}}均構(gòu)成對(duì)S的劃分。顯然有|A|>|B|>|C|

可以將A稱為最大劃分；將C稱為最小劃分。2.4集合的劃分與覆蓋[例]S={a,b,c}192.5等價(jià)關(guān)系[等價(jià)關(guān)系]

集合X上的關(guān)系R若具有自反性、對(duì)稱性和傳遞性，則稱R為X上的一個(gè)等價(jià)關(guān)系。[例]

N上的模6同余關(guān)系

R={<x,y>|x,yN(xy)=6L，L為整數(shù)}自反性：對(duì)稱性：傳遞性：2.5等價(jià)關(guān)系[等價(jià)關(guān)系]集合X上的關(guān)系R若具有自反性、202.5等價(jià)關(guān)系[定理]N上的模m同余關(guān)系是等價(jià)關(guān)系。[證明]自反性：xx=0，故xx=mL，這里L(fēng)=0。對(duì)稱性：設(shè)xRy

即xy=mL，L為整數(shù)則yx=mL，故yRx。

傳遞性：設(shè)xRy

且yRz，即

xy=mL1，yz=mL2，L1、L2

為整數(shù)

則xz=mL1+mL2=m(L1+L2)

故xRz2.5等價(jià)關(guān)系[定理]N上的模m同余關(guān)系是等價(jià)關(guān)系。212.5等價(jià)關(guān)系[等價(jià)類]

設(shè)R為X上的一個(gè)等價(jià)關(guān)系，對(duì)任何xX，所有與x有關(guān)系R的元素的集合，稱為X上由x生成的R–等價(jià)類。記為[x]R。[x]R={y|yXxRy}[例]

X={1,2,3,4,5,6,7}，R為X上的模3同余關(guān)系。則[1]R={1,4,7}，[2]R={2,5}，[3]R={3,6}2.5等價(jià)關(guān)系[等價(jià)類]設(shè)R為X上的一個(gè)等價(jià)關(guān)系，對(duì)任何222.5等價(jià)關(guān)系[性質(zhì)]設(shè)R為X上的一個(gè)等價(jià)關(guān)系，則①

X中的任何一個(gè)元素，至少屬于一個(gè)等價(jià)類。②若x,yX，則x,y或?qū)偻坏葍r(jià)類，或?qū)賰蓚€(gè)不同等價(jià)類但此兩個(gè)不同等價(jià)類的交集為（不相交）。[證明]2.5等價(jià)關(guān)系[性質(zhì)]設(shè)R為X上的一個(gè)等價(jià)關(guān)系，則232.5等價(jià)關(guān)系[結(jié)論]對(duì)X上的等價(jià)關(guān)系R，①任意xX屬于且只屬于一個(gè)等價(jià)類；②若xRy，則[x]R=[y]R，否則[x]R[y]R=。2.5等價(jià)關(guān)系[結(jié)論]對(duì)X上的等價(jià)關(guān)系R，①任意xX242.5等價(jià)關(guān)系[定理]

集合X上的一個(gè)等價(jià)關(guān)系R產(chǎn)生對(duì)此集合的一個(gè)劃分，該劃分的塊對(duì)應(yīng)于R的等價(jià)類。[證明]由上述結(jié)論得到。將該劃分記作：X/R={[x]R|xX}2.5等價(jià)關(guān)系[定理]集合X上的一個(gè)等價(jià)關(guān)系R產(chǎn)生對(duì)此集252.5等價(jià)關(guān)系[定理]X上的任意劃分均可確定一個(gè)等價(jià)關(guān)系。[證明]設(shè)X上的一個(gè)劃分為A={A1,A2,…,An}，定義

R={<x,y>|x,yX(Ai)(AiAxAiyAi)}

可以證明R具有自反性：對(duì)稱性：傳遞性：2.5等價(jià)關(guān)系[定理]X上的任意劃分均可確定一個(gè)等價(jià)關(guān)系262.5等價(jià)關(guān)系[討論]X上由不同方法定義的等價(jià)關(guān)系R1、R2，若產(chǎn)生的等價(jià)類相同，則R1=R2。不等價(jià)關(guān)系也能產(chǎn)生劃分。2.5等價(jià)關(guān)系[討論]272.6相容關(guān)系[相容關(guān)系]

X上的二元關(guān)系R，若R是自反的、對(duì)稱的，則稱R為X上的一個(gè)相容關(guān)系，記作。[例]

X={2661,243,315,648,455}R={<x,y>|x,yX，x與y至少含有一個(gè)相同數(shù)字}容易看出，R具有自反性、對(duì)稱性。

R不具有傳遞性：如<2661,243>,<243,455>R但<2661,455>R因此R不是等價(jià)關(guān)系，R是一個(gè)相容關(guān)系。2.6相容關(guān)系[相容關(guān)系]X上的二元關(guān)系R，若R是自反的282.6相容關(guān)系[相容類]

設(shè)Ai

X，是X上的一個(gè)相容關(guān)系。稱Ai是X上的一個(gè)相容類當(dāng)且僅當(dāng)Ai中任二元素相容。即(x)(y)(x,yAi

x

y)。[最大相容類]

設(shè)Ai是X上的一個(gè)相容類，若X-Ai中不存在與Ai中所有元素相容的元素，則稱Ai為X的一個(gè)最大相容類。最大相容類不一定是含有最多元素個(gè)數(shù)的相容類在相容關(guān)系的關(guān)系圖中，最大相容類對(duì)應(yīng)于一個(gè)最大完全子圖。2.6相容關(guān)系[相容類]設(shè)AiX，是X上的一個(gè)292.7關(guān)系的運(yùn)算(1)關(guān)系的一般運(yùn)算[定義]

設(shè)R、S是X到Y(jié)的二元關(guān)系，定義運(yùn)算如下：RS={<x,y>|xRyxSy}RS={<x,y>|xRyxSy}RS={<x,y>|xRyxSy}~R=XYR2.7關(guān)系的運(yùn)算(1)關(guān)系的一般運(yùn)算302.7關(guān)系的運(yùn)算(2)

關(guān)系的復(fù)合運(yùn)算[復(fù)合關(guān)系]

設(shè)二元關(guān)系R:XY，S:YZ，則稱R☉S={<x,z>|xXzZ(y)(yYxRyySz)}

為R和S的(右)復(fù)合關(guān)系，或(右)復(fù)合運(yùn)算結(jié)果。注意關(guān)系的復(fù)合運(yùn)算定義中的右復(fù)合和左復(fù)合給出的構(gòu)造定義不同：右復(fù)合R☉S中右邊的S在R之后進(jìn)行第二步復(fù)合構(gòu)造。在函數(shù)理論中，與右復(fù)合函數(shù)S*R對(duì)應(yīng)：S*R=R☉S即

S*R(x)=S(R(x))2.7關(guān)系的運(yùn)算(2)關(guān)系的復(fù)合運(yùn)算312.7關(guān)系的運(yùn)算[例]

X={x1,x2,x3}，Y={y1,y2,y3,y4}，Z={z1,z2,z3}R={<x1,y1>,<x2,y3>,<x2,y4>}S={<y1,z3>,<y2,z1>,<y4,z2>}顯然有：Dom(R☉S)Dom(R)Ran(R☉S)Ran(S)R☉S={<x1,z3>,<x2,z2>}2.7關(guān)系的運(yùn)算[例]X={x1,x2,x3}，Y=322.7關(guān)系的運(yùn)算關(guān)系的復(fù)合運(yùn)算沒有交換律。[定理]

關(guān)系復(fù)合運(yùn)算的結(jié)合律：設(shè)二元關(guān)系R：XY，S：YZ，P：ZW，則有(R☉S)☉P=R☉(S☉P)[證明]2.7關(guān)系的運(yùn)算關(guān)系的復(fù)合運(yùn)算沒有交換律。332.7關(guān)系的運(yùn)算[定理]

關(guān)系復(fù)合運(yùn)算與一般運(yùn)算的結(jié)合律：設(shè)二元關(guān)系R1：XY，R2,R3：YZ，R4：ZW，則有R1☉(R2R3)=(R1☉R2)(R1☉R3)R1☉(R2R3)(R1☉R2)(R1☉R3)(R2R3)☉R4=(R2☉R4)(R3☉R4)(R2R3)☉R4(R2☉R4)(R3☉R4)[證明]按照定義轉(zhuǎn)換為邏輯運(yùn)算，證明邏輯等值式。2.7關(guān)系的運(yùn)算[定理]關(guān)系復(fù)合運(yùn)算與一般運(yùn)算的結(jié)合律：342.7關(guān)系的運(yùn)算[關(guān)系的冪運(yùn)算]設(shè)R為X上的二元關(guān)系，R☉R☉…☉R記為Rn，規(guī)定Rn=Rn1☉R，R0=IX2.7關(guān)系的運(yùn)算[關(guān)系的冪運(yùn)算]設(shè)R為X上的二元關(guān)系，R352.7關(guān)系的運(yùn)算(3)關(guān)系的逆運(yùn)算[逆關(guān)系]

設(shè)二元關(guān)系R：XY，定義

R-1={<y,x>|xXyY<x,y>R}為R的逆關(guān)系。[性質(zhì)](R-1)-1=R (RS)-1=R-1S-1

(R☉S)-1=S-1☉R-1 (RS)-1=R-1S-1

R=SR-1=S-1 (~R)-1=~(R-1)RSR-1S-1 -1=2.7關(guān)系的運(yùn)算(3)關(guān)系的逆運(yùn)算362.7關(guān)系的運(yùn)算(3)關(guān)系的逆運(yùn)算[逆關(guān)系]

設(shè)二元關(guān)系R：XY，定義R-1={<y,x>|xXyY<x,y>R}為R的逆關(guān)系。[性質(zhì)](R-1)-1=R，-1= (RS)-1=R-1S-1

，(RS)-1=R-1S-1

(~R)-1=~(R-1)(R☉S)-1=S-1☉R-1

R=SR-1=S-1 RSR-1S-1 2.7關(guān)系的運(yùn)算(3)關(guān)系的逆運(yùn)算372.7關(guān)系的運(yùn)算(4)關(guān)系的閉包運(yùn)算[閉包]

設(shè)R為X上的二元關(guān)系，若另有一關(guān)系R，滿足：①

R是自反的；②

RR；③對(duì)于任何自反（對(duì)稱/傳遞）的關(guān)系R，若RR，則RR。則稱R為R的自反（對(duì)稱/傳遞）閉包，記為r(R)(s(R)/t(R))。2.7關(guān)系的運(yùn)算(4)關(guān)系的閉包運(yùn)算382.7關(guān)系的運(yùn)算[例]整數(shù)集上的“＜”關(guān)系的自反閉包是“≤

”，對(duì)稱閉包是“≠

”，傳遞閉包仍然是“＜”。[例]整數(shù)“=”的自反、對(duì)稱、傳遞閉包都是它本身。[例]有關(guān)系矩陣求Mr(R)、Ms(R)、Mt(R)2.7關(guān)系的運(yùn)算[例]整數(shù)集上的“＜”關(guān)系的自反閉包是392.7關(guān)系的運(yùn)算2.7關(guān)系的運(yùn)算402.7關(guān)系的運(yùn)算[定理]設(shè)R為X上的二元關(guān)系，則①r(R)=RIx②s(R)=RR-1[證明]

③

①②2.7關(guān)系的運(yùn)算[定理]設(shè)R為X上的二元關(guān)系，則[證明]412.8偏序關(guān)系[偏序關(guān)系]

集合A上的一個(gè)關(guān)系R滿足自反性、反對(duì)稱性和傳遞性時(shí)，稱R是A上的一個(gè)偏序關(guān)系，記為“”，用二元組〈A,〉表示該偏序結(jié)構(gòu)，或稱之為偏序集。[例]

A={2,3,6,8},“”={<x,y>|x,yA(x整除y)}

“”={……..}

容易驗(yàn)證，上述關(guān)系為偏序關(guān)系。2.8偏序關(guān)系[偏序關(guān)系]集合A上的一個(gè)關(guān)系R滿足自反性422.8偏序關(guān)系x、y之間存在偏序關(guān)系時(shí)，說x、y（在該關(guān)系下）可比較，否則說x、y

不可比較。上例中，2和3不可比較（在上述定義的“”下）。[蓋住]

蓋住（緊鄰遮蓋）。設(shè)〈A,〉，x，yA，

y蓋住xxyxy(z)((xzzy)(x=zy=z))

記covA={<x,y>|x,yA(y蓋住x)}2.8偏序關(guān)系x、y之間存在偏序關(guān)系時(shí)，說x、y（在該關(guān)432.8偏序關(guān)系表達(dá)偏序關(guān)系的Hasse圖設(shè)有偏序關(guān)系<A,>①用結(jié)點(diǎn)表示集合元素②若<x,y>covA，則用線段連接結(jié)點(diǎn)x,y，且令x(小者)在y的下方。2.8偏序關(guān)系表達(dá)偏序關(guān)系的Hasse圖442.8偏序關(guān)系[例]

Hasse圖如右圖①

默認(rèn)aa,bb,cc②

ac,cb③

abacbHasseDiagram由畫法可見：①自反關(guān)系為默認(rèn)；②反對(duì)稱關(guān)系體現(xiàn)在“上”、“下”位置上；③由上到下的可達(dá)性表達(dá)了傳遞性。2.8偏序關(guān)系[例]Hasse圖如右圖acbHas452.8偏序關(guān)系上述Hasse圖表示的對(duì)應(yīng)關(guān)系集合為：{<a,a>,<b,b>,<c,c>,<a,c>,<c,b>,<a,b>}對(duì)應(yīng)關(guān)系圖如下：acbHasseDiagramacb關(guān)系圖2.8偏序關(guān)系上述Hasse圖表示的對(duì)應(yīng)關(guān)系集合為：a462.8偏序關(guān)系[例]由偏序關(guān)系的關(guān)系圖構(gòu)造相應(yīng)的Hasse圖cab關(guān)系圖dabcHasseDiagramd2.8偏序關(guān)系[例]由偏序關(guān)系的關(guān)系圖構(gòu)造相應(yīng)的Hass472.8偏序關(guān)系[例]{2,3,6,12,24,36}上的整除關(guān)系的Hasse圖。2624HasseDiagram361232.8偏序關(guān)系[例]{2,3,6,12,24,36}上的482.8偏序關(guān)系[例]

A的冪集上的關(guān)系的Hasse圖。A={a}{a}{a,b}A={a,b}{a}2.8偏序關(guān)系[例]A的冪集上的關(guān)系的Hasse圖。492.8偏序關(guān)系[例]

A的冪集上的關(guān)系的Hasse圖。{a,b,c}A={a,b,c}{a}{c}{a,b}{a,c}{b,c}2.8偏序關(guān)系[例]A的冪集上的關(guān)系的Hasse圖。502.8偏序關(guān)系[最大最小元]

對(duì)偏序集<A,>y0A為最小元(x)(xAy0x)y0A為最大元(x)(xAxy0)[定理]

<

A,>中最大(最小)元若存在則唯一。[證明][極大極小元]

對(duì)<

A,>y0A為極小元(x)(xAxy0?(x

y0))y0A為極大元(x)(xAxy0?(y0x))2.8偏序關(guān)系[最大最小元]對(duì)偏序集<A,>512.8偏序關(guān)系[例]{2,3,6,12,24,36}上的整除關(guān)系的Hasse圖。2624361232,3為極小元24,36為極大元沒有最小元和最大元2.8偏序關(guān)系[例]{2,3,6,12,24,36}上的522.8偏序關(guān)系[例]

A的冪集上的關(guān)系的Hasse圖。{a,b,c}A={a,b,c}{a}{c}{a,b}{a,c}{b,c}

為最小元{a,b,c}為最大元2.8偏序關(guān)系[例]A的冪集上的關(guān)系的Hasse圖。532.8偏序關(guān)系[上下界]

對(duì)<

A,>,BA,aA

a是B的一個(gè)上界(x)(xBx

a)

a是B的一個(gè)下界(x)(xBax)說明：a不一定是B的元素，即可能aA-BB的上(下)界不一定存在，存在也不一定唯一。2.8偏序關(guān)系[上下界]對(duì)<A,>,BA,542.8偏序關(guān)系[例]{2,3,6,12,24,36}上的整除關(guān)系的Hasse圖。262436123令B1={2,3,6}B1的上界是6,12,24,366B1，而12,24,36B1

B1沒有下界令B2={2,6,12,24}

B2的上界是24，下界是22.8偏序關(guān)系[例]{2,3,6,12,24,36}上的552.8偏序關(guān)系[上確界]

對(duì)<A,>,BA,aA是B的一個(gè)上界。

a是B的上確界(y)(y是B的上界a

y)上確界若存在則唯一。[下確界]

對(duì)<A,>,BA,bA是B的一個(gè)下界。

b是B的下確界(x)(x是B的下界xb)下確界若存在則唯一。2.8偏序關(guān)系[上確界]對(duì)<A,>,BA,562.8偏序關(guān)系[例]{2,3,6,12,24,36}上的整除關(guān)系的Hasse圖。262436123令B1={2,3,6}B1的上界是6,12,24,36

B1的上確界是6

B1沒有下界也沒有下確界令B2={2,6,12,24}

B2的上界和上確界是24

B2的下界和下確界是22.8偏序關(guān)系[例]{2,3,6,12,24,36}上的572.8偏序關(guān)系[鏈與反鏈]

對(duì)<A,>,BA,若B中任兩個(gè)元素之間都是可比較的，則稱B是A中的一條鏈。若B中任兩個(gè)元素之間都是不可比較的，則稱B是A中的一條反鏈。262436123[例]右邊所示Hasse圖中，{2,6,12,24}是一條鏈{2,3}和{24,36}是反鏈注意：{2,3,24,36}并非反鏈2.8偏序關(guān)系[鏈與反鏈]對(duì)<A,>,BA,582.8偏序關(guān)系[例]在正整數(shù)上定義關(guān)系R：

<x,y>Riffx和y的最大公因子是1。討論R的關(guān)系性質(zhì)。[解]自反性：<2,2>的最大公因子是2，故<2,2>R即R非自反；對(duì)稱性：成立；傳遞性：<2,1>R且<1,2>R但<2,2>R即R非傳遞；反對(duì)稱性：<2,1>R且<1,2>R故R非反對(duì)稱。2.8偏序關(guān)系[例]在正整數(shù)上定義關(guān)系R：592.8偏序關(guān)系[例]設(shè)關(guān)系R定義在所有8bits字符構(gòu)成的集合上：若字符char1和char2的前4bits相同，則它們之間有關(guān)系R。①證明R是一個(gè)等價(jià)關(guān)系；②共有多少個(gè)等價(jià)類？③列出每個(gè)等價(jià)類的一個(gè)成員。[解]

①證明R是自反的、對(duì)稱的和傳遞的；

②等價(jià)類數(shù)目：24=16；

③0000,0001,0010,0011,…,1110,11112.8偏序關(guān)系[例]設(shè)關(guān)系R定義在所有8bits字符構(gòu)成602.9其他次序關(guān)系(1)全序關(guān)系[全序關(guān)系]

設(shè)偏序集<A,>，若A是一條鏈，則稱“”為A上的一個(gè)全序關(guān)系，此時(shí)稱<A,>是一個(gè)全序集合。(2)偏序關(guān)系的逆關(guān)系[定義]設(shè)偏序集<A,>，定義A上的關(guān)系“”

xyx,yAyx

集合A和關(guān)系“”仍然構(gòu)成一個(gè)偏序集<A,>。2.9其他次序關(guān)系(1)全序關(guān)系612.9其他次序關(guān)系(3)擬序關(guān)系[擬序關(guān)系]

集合A上的關(guān)系R滿足反自反性和傳遞性時(shí)，稱為A上的一個(gè)擬序關(guān)系，用二元組<A,<>表示該結(jié)構(gòu)。擬序關(guān)系是反對(duì)稱的，也稱為嚴(yán)格偏序關(guān)系。[定理]若R為A上的偏序關(guān)系，則R-IA為A上的擬序關(guān)系。若R為A上的擬序關(guān)系，則RIA為A上的偏序關(guān)系。2.9其他次序關(guān)系(3)擬序關(guān)系622.9其他次序關(guān)系[定理]設(shè)有擬序集<A,<>，對(duì)任何x,y,zA,①

x<y,x=y,y<x

中至多有一種情況成立(三分律)；②

xyx

則x=y，這里xy

表示x<y

或x=y。[證明]利用擬序集的反自反性和傳遞性。2.9其他次序關(guān)系[定理]設(shè)有擬序集<A,<>，對(duì)任632.9其他次序關(guān)系(4)詞典次序設(shè)字母表為X，“”為X上的自然次序。顯然

<X,>為全序集合。①長(zhǎng)度為2的詞庫A=XX在A上定義全序關(guān)系S：

<x1,y1>S<x2,y2>(x1<x2)(x1=x2y1y2)<x1,y1>S<x2,y2><x2,y2>S<x1,y1>2.9其他次序關(guān)系(4)詞典次序642.9其他次序關(guān)系②長(zhǎng)度不大于n的詞庫A=XX2…..Xn在A上定義全序關(guān)系S：設(shè)<x1,x2,…,xp>,<y1,y2,…,yq>A,其中pqn。

<x1,x2,…,xp>S<y1,y2,…,yq>當(dāng)且僅當(dāng)下列三個(gè)條件之一得到滿足：(ⅰ)<x1,x2,…,xp>=<y1,y2,…,yp>(ⅱ)x1y1且在X中有x1y1(ⅲ)xi=yi,i=1..k,k<p,xi+1yi+1且在X中有

xi+1yi+1否則<y1,y2,…,yq>S<x1,x2,…,xp>2.9其他次序關(guān)系②長(zhǎng)度不大于n的詞庫A=XX2…652.9其他次序關(guān)系(5)格[格]設(shè)偏序集合<A,>,若其中任何二個(gè)元素在A中都有上、下確界，則稱<A,>為一個(gè)格。[例]如下的Hasse圖描述了三個(gè)格：2.9其他次序關(guān)系(5)格662.9其他次序關(guān)系[例]如下的Hasse圖描述的不是格：（沒有下確界）[例]<I+,>，I+正整數(shù)，a“”biffa

整除b。任何{x,y}I+，其上確界為其最小公倍數(shù)，下確界為其最大公約數(shù)，均存在于I+

中。故<I+,>為格。2.9其他次序關(guān)系[例]如下的Hasse圖描述的不是格672.9其他次序關(guān)系[上下確界]

設(shè)

<A,>為格，對(duì)任意a,bA，記a,b的上確界元素為ab，下確界元素為ab。[性質(zhì)]設(shè)<A,>為格，對(duì)任意a,b,c,dA，有①

a

ab,ab

a②

若a

b,c

d，則ac

bd,ac

bd③

ab=ba,ab=ba

（交換律）④

a(bc)=(ab)c,a(bc)=(ab)c（結(jié)合律）⑤

a(ab)=a,a(ab)=a

（吸收律）2.9其他次序關(guān)系[上下確界]設(shè)<A,>為格，對(duì)682.9其他次序關(guān)系(6)良序集合[良序集合]

設(shè)偏序集合<A,>

，若其任意非空子集都在該子集中存在最小元，則稱<A,>為良序集合。[例]如圖的偏序集不是良序集。2.9其他次序關(guān)系(6)良序集合692.9其他次序關(guān)系[定理]每個(gè)良序集合本身也是一個(gè)全序集合。有限階的全序集合是一個(gè)良序集合。[證明]2.9其他次序關(guān)系[定理]每個(gè)良序集合本身也是一個(gè)全序集70第二章關(guān)系與序關(guān)系2.1關(guān)系的概念[二元關(guān)系]一對(duì)對(duì)象之間的關(guān)系稱為二元關(guān)系。第二章關(guān)系與序關(guān)系2.1關(guān)系的概念712.1關(guān)系的概念[例]

teachers={a,b,c}，students={x,y,z}

建立教學(xué)關(guān)系T:aTxiffaTEACHINGx用序偶集合表示為：T={<a,x>,<a,z>,<b,y>,<c,y>,<c,z>}Tteachersstudents圖示為：2.1關(guān)系的概念[例]teachers={a,b,c}，722.1關(guān)系的概念[例]

Subroutines={a,b,c,d,e}子程序間調(diào)用關(guān)系Calling={<a,a>,<a,b>,<a,d>,<b,a>,<b,c>,<c,c>,<c,e>,<d,d>}CallingSubroutinesSubroutines圖示為：2.1關(guān)系的概念[例]Subroutines={a,b,732.1關(guān)系的概念[二元關(guān)系的集合定義]任何一個(gè)序偶的集合R={<x,y>|xXyY}都確定了一種二元關(guān)系，稱為從X到Y(jié)的二元關(guān)系。

<x,y>R可記為xRy，顯然RXY

<x,y>R可記為xRy當(dāng)X=Y即X與Y同一時(shí)，稱R為X上的一個(gè)二元關(guān)系。從X到Y(jié)的任何二元關(guān)系，都可用一個(gè)序偶集合來表示：R={<x,y>|xXyYxRy}2.1關(guān)系的概念[二元關(guān)系的集合定義]任何一個(gè)序偶的集合742.1關(guān)系的概念[例]

F={<x,y>|x是y的父親}

S={<x,y>|x,y為正整數(shù)且x可整除y}T={<y2,y>|y為實(shí)數(shù)}2.1關(guān)系的概念[例]752.1關(guān)系的概念[定義域]設(shè)二元關(guān)系S。由<x,y>S的所有對(duì)象x組成的集合稱為S的定義域，記為Dom(S)。[值域]由<x,y>S的所有對(duì)象y組成的集合稱為S的值域，記為Ran(S)(Range(S))。記

F(S)=D(S)R(S)，稱為S的域。描述：Dom(S)={x|(y)(<x,y>S)}Ran(S)={y|(x)(<x,y>S)}2.1關(guān)系的概念[定義域]設(shè)二元關(guān)系S。由<x,y>762.1關(guān)系的概念若干特殊關(guān)系：①X到Y(jié)的全域關(guān)系：Ex,y=XY

特別地：

Ex,x=XX②空關(guān)系：

③恒等關(guān)系：Ix={<xi,xi>|xiX}[例]設(shè)X={1,2,3,4}，求X上的關(guān)系“>”(大于)及其定義域、值域。2.1關(guān)系的概念若干特殊關(guān)系：772.2關(guān)系的表示方法(1)集合表示法借用集合的各種描述方法對(duì)表示關(guān)系的序偶集合進(jìn)行描述(2)關(guān)系矩陣設(shè)X={x1,x2,…,xm}，Y={y1,y2,…,yn}，m,n<+R是X到Y(jié)的二元關(guān)系。構(gòu)造矩陣MR=[mij]mn，mij

=<xi,yj>R0其它2.2關(guān)系的表示方法(1)集合表示法MR=[mij]m782.2關(guān)系的表示方法[例]非0行對(duì)應(yīng)元素構(gòu)成D(S)非0列對(duì)應(yīng)元素構(gòu)成R(S)2.2關(guān)系的表示方法[例]非0行對(duì)應(yīng)元素構(gòu)成D(S)792.2關(guān)系的表示方法(3)關(guān)系圖表示法用結(jié)點(diǎn)表示X、Y上的元素；若<x,y>R則從結(jié)點(diǎn)x到結(jié)點(diǎn)y畫一條弧。[例]上述Teaching關(guān)系的關(guān)系圖：2.2關(guān)系的表示方法(3)關(guān)系圖表示法802.2關(guān)系的表示方法[例]設(shè)X={1,2,3,4}，X上的關(guān)系“>”：2.2關(guān)系的表示方法[例]設(shè)X={1,2,3,4}，X812.3關(guān)系的性質(zhì)[定義]設(shè)R是X上的二元關(guān)系，則：①R是自反的

(x)(xXxRx)②R是對(duì)稱的

(x)(y)(x,yXxRyyRx)③R是傳遞的

(x)(y)(z)(x,y,zXxRyyRz

xRz)④R是反自反的

(x)(xX?(xRx))⑤R是反對(duì)稱的

(x)(y)(x,yXxRyyRx

x=y)2.3關(guān)系的性質(zhì)[定義]設(shè)R是X上的二元關(guān)系，則：822.3關(guān)系的性質(zhì)[例]整數(shù)集合上的若干關(guān)系及其性質(zhì)整除=≤＜自反性對(duì)稱性傳遞性反自反性反對(duì)稱性判定關(guān)系“＜”的反對(duì)稱性的前提條件總為F,理論上反對(duì)稱性成立。2.3關(guān)系的性質(zhì)[例]整數(shù)集合上的若干關(guān)系及其性質(zhì)整除=832.3關(guān)系的性質(zhì)存在著既非自反也非反自反的關(guān)系，如：存在著既對(duì)稱又反對(duì)稱的關(guān)系，如：2.3關(guān)系的性質(zhì)存在著既非自反也非反自反的關(guān)系，如：存在著842.3關(guān)系的性質(zhì)存在著既非對(duì)稱又非反對(duì)稱的關(guān)系，如：2.3關(guān)系的性質(zhì)存在著既非對(duì)稱又非反對(duì)稱的關(guān)系，如：852.3關(guān)系的性質(zhì)從關(guān)系矩陣和關(guān)系圖看關(guān)系的性質(zhì)：R是自反的：MR的對(duì)角元均為1；關(guān)系圖為自環(huán)圖。R是對(duì)稱的：MR為對(duì)稱矩陣；關(guān)系圖中弧成對(duì)出現(xiàn)。R是反自反的：MR的對(duì)角元均為0；關(guān)系圖為無自環(huán)圖。R是反對(duì)稱的：MR為反對(duì)稱矩陣；關(guān)系圖中只出現(xiàn)單向弧。2.3關(guān)系的性質(zhì)從關(guān)系矩陣和關(guān)系圖看關(guān)系的性質(zhì)：862.4集合的劃分與覆蓋[定義]給定集合S，A={A1,A2,…,An}，AiS，i=1..n。②若①成立且AiAj=(若ij)，則說A是S的一個(gè)劃分，并稱A1,A2,…,An為此劃分的塊。2.4集合的劃分與覆蓋[定義]給定集合S，A={A1,A872.4集合的劃分與覆蓋[例]

N={0,1,2,3,4,……}自然數(shù)集合。取A0={0,6,12,18,……}A1={1,7,13,19,……}A2={2,8,14,20,……}……A5={5,11,17,23,……}則A={A0，A1，A2，A3，A4，A5}是N的一個(gè)劃分。2.4集合的劃分與覆蓋[例]N={0,1,2,3,4,882.4集合的劃分與覆蓋[例]

S={a,b,c}取A={{a},,{c}}B={{a,b},{c}}C={{a,b,c}}均構(gòu)成對(duì)S的劃分。顯然有|A|>|B|>|C|

可以將A稱為最大劃分；將C稱為最小劃分。2.4集合的劃分與覆蓋[例]S={a,b,c}892.5等價(jià)關(guān)系[等價(jià)關(guān)系]

集合X上的關(guān)系R若具有自反性、對(duì)稱性和傳遞性，則稱R為X上的一個(gè)等價(jià)關(guān)系。[例]

N上的模6同余關(guān)系

R={<x,y>|x,yN(xy)=6L，L為整數(shù)}自反性：對(duì)稱性：傳遞性：2.5等價(jià)關(guān)系[等價(jià)關(guān)系]集合X上的關(guān)系R若具有自反性、902.5等價(jià)關(guān)系[定理]N上的模m同余關(guān)系是等價(jià)關(guān)系。[證明]自反性：xx=0，故xx=mL，這里L(fēng)=0。對(duì)稱性：設(shè)xRy

即xy=mL，L為整數(shù)則yx=mL，故yRx。

傳遞性：設(shè)xRy

且yRz，即

xy=mL1，yz=mL2，L1、L2

為整數(shù)

則xz=mL1+mL2=m(L1+L2)

故xRz2.5等價(jià)關(guān)系[定理]N上的模m同余關(guān)系是等價(jià)關(guān)系。912.5等價(jià)關(guān)系[等價(jià)類]

設(shè)R為X上的一個(gè)等價(jià)關(guān)系，對(duì)任何xX，所有與x有關(guān)系R的元素的集合，稱為X上由x生成的R–等價(jià)類。記為[x]R。[x]R={y|yXxRy}[例]

X={1,2,3,4,5,6,7}，R為X上的模3同余關(guān)系。則[1]R={1,4,7}，[2]R={2,5}，[3]R={3,6}2.5等價(jià)關(guān)系[等價(jià)類]設(shè)R為X上的一個(gè)等價(jià)關(guān)系，對(duì)任何922.5等價(jià)關(guān)系[性質(zhì)]設(shè)R為X上的一個(gè)等價(jià)關(guān)系，則①

X中的任何一個(gè)元素，至少屬于一個(gè)等價(jià)類。②若x,yX，則x,y或?qū)偻坏葍r(jià)類，或?qū)賰蓚€(gè)不同等價(jià)類但此兩個(gè)不同等價(jià)類的交集為（不相交）。[證明]2.5等價(jià)關(guān)系[性質(zhì)]設(shè)R為X上的一個(gè)等價(jià)關(guān)系，則932.5等價(jià)關(guān)系[結(jié)論]對(duì)X上的等價(jià)關(guān)系R，①任意xX屬于且只屬于一個(gè)等價(jià)類；②若xRy，則[x]R=[y]R，否則[x]R[y]R=。2.5等價(jià)關(guān)系[結(jié)論]對(duì)X上的等價(jià)關(guān)系R，①任意xX942.5等價(jià)關(guān)系[定理]

集合X上的一個(gè)等價(jià)關(guān)系R產(chǎn)生對(duì)此集合的一個(gè)劃分，該劃分的塊對(duì)應(yīng)于R的等價(jià)類。[證明]由上述結(jié)論得到。將該劃分記作：X/R={[x]R|xX}2.5等價(jià)關(guān)系[定理]集合X上的一個(gè)等價(jià)關(guān)系R產(chǎn)生對(duì)此集952.5等價(jià)關(guān)系[定理]X上的任意劃分均可確定一個(gè)等價(jià)關(guān)系。[證明]設(shè)X上的一個(gè)劃分為A={A1,A2,…,An}，定義

R={<x,y>|x,yX(Ai)(AiAxAiyAi)}

可以證明R具有自反性：對(duì)稱性：傳遞性：2.5等價(jià)關(guān)系[定理]X上的任意劃分均可確定一個(gè)等價(jià)關(guān)系962.5等價(jià)關(guān)系[討論]X上由不同方法定義的等價(jià)關(guān)系R1、R2，若產(chǎn)生的等價(jià)類相同，則R1=R2。不等價(jià)關(guān)系也能產(chǎn)生劃分。2.5等價(jià)關(guān)系[討論]972.6相容關(guān)系[相容關(guān)系]

X上的二元關(guān)系R，若R是自反的、對(duì)稱的，則稱R為X上的一個(gè)相容關(guān)系，記作。[例]

X={2661,243,315,648,455}R={<x,y>|x,yX，x與y至少含有一個(gè)相同數(shù)字}容易看出，R具有自反性、對(duì)稱性。

R不具有傳遞性：如<2661,243>,<243,455>R但<2661,455>R因此R不是等價(jià)關(guān)系，R是一個(gè)相容關(guān)系。2.6相容關(guān)系[相容關(guān)系]X上的二元關(guān)系R，若R是自反的982.6相容關(guān)系[相容類]

設(shè)Ai

X，是X上的一個(gè)相容關(guān)系。稱Ai是X上的一個(gè)相容類當(dāng)且僅當(dāng)Ai中任二元素相容。即(x)(y)(x,yAi

x

y)。[最大相容類]

設(shè)Ai是X上的一個(gè)相容類，若X-Ai中不存在與Ai中所有元素相容的元素，則稱Ai為X的一個(gè)最大相容類。最大相容類不一定是含有最多元素個(gè)數(shù)的相容類在相容關(guān)系的關(guān)系圖中，最大相容類對(duì)應(yīng)于一個(gè)最大完全子圖。2.6相容關(guān)系[相容類]設(shè)AiX，是X上的一個(gè)992.7關(guān)系的運(yùn)算(1)關(guān)系的一般運(yùn)算[定義]

設(shè)R、S是X到Y(jié)的二元關(guān)系，定義運(yùn)算如下：RS={<x,y>|xRyxSy}RS={<x,y>|xRyxSy}RS={<x,y>|xRyxSy}~R=XYR2.7關(guān)系的運(yùn)算(1)關(guān)系的一般運(yùn)算1002.7關(guān)系的運(yùn)算(2)

關(guān)系的復(fù)合運(yùn)算[復(fù)合關(guān)系]

設(shè)二元關(guān)系R:XY，S:YZ，則稱R☉S={<x,z>|xXzZ(y)(yYxRyySz)}

為R和S的(右)復(fù)合關(guān)系，或(右)復(fù)合運(yùn)算結(jié)果。注意關(guān)系的復(fù)合運(yùn)算定義中的右復(fù)合和左復(fù)合給出的構(gòu)造定義不同：右復(fù)合R☉S中右邊的S在R之后進(jìn)行第二步復(fù)合構(gòu)造。在函數(shù)理論中，與右復(fù)合函數(shù)S*R對(duì)應(yīng)：S*R=R☉S即

S*R(x)=S(R(x))2.7關(guān)系的運(yùn)算(2)關(guān)系的復(fù)合運(yùn)算1012.7關(guān)系的運(yùn)算[例]

X={x1,x2,x3}，Y={y1,y2,y3,y4}，Z={z1,z2,z3}R={<x1,y1>,<x2,y3>,<x2,y4>}S={<y1,z3>,<y2,z1>,<y4,z2>}顯然有：Dom(R☉S)Dom(R)Ran(R☉S)Ran(S)R☉S={<x1,z3>,<x2,z2>}2.7關(guān)系的運(yùn)算[例]X={x1,x2,x3}，Y=1022.7關(guān)系的運(yùn)算關(guān)系的復(fù)合運(yùn)算沒有交換律。[定理]

關(guān)系復(fù)合運(yùn)算的結(jié)合律：設(shè)二元關(guān)系R：XY，S：YZ，P：ZW，則有(R☉S)☉P=R☉(S☉P)[證明]2.7關(guān)系的運(yùn)算關(guān)系的復(fù)合運(yùn)算沒有交換律。1032.7關(guān)系的運(yùn)算[定理]

關(guān)系復(fù)合運(yùn)算與一般運(yùn)算的結(jié)合律：設(shè)二元關(guān)系R1：XY，R2,R3：YZ，R4：ZW，則有R1☉(R2R3)=(R1☉R2)(R1☉R3)R1☉(R2R3)(R1☉R2)(R1☉R3)(R2R3)☉R4=(R2☉R4)(R3☉R4)(R2R3)☉R4(R2☉R4)(R3☉R4)[證明]按照定義轉(zhuǎn)換為邏輯運(yùn)算，證明邏輯等值式。2.7關(guān)系的運(yùn)算[定理]關(guān)系復(fù)合運(yùn)算與一般運(yùn)算的結(jié)合律：1042.7關(guān)系的運(yùn)算[關(guān)系的冪運(yùn)算]設(shè)R為X上的二元關(guān)系，R☉R☉…☉R記為Rn，規(guī)定Rn=Rn1☉R，R0=IX2.7關(guān)系的運(yùn)算[關(guān)系的冪運(yùn)算]設(shè)R為X上的二元關(guān)系，R1052.7關(guān)系的運(yùn)算(3)關(guān)系的逆運(yùn)算[逆關(guān)系]

設(shè)二元關(guān)系R：XY，定義

R-1={<y,x>|xXyY<x,y>R}為R的逆關(guān)系。[性質(zhì)](R-1)-1=R (RS)-1=R-1S-1

(R☉S)-1=S-1☉R-1 (RS)-1=R-1S-1

R=SR-1=S-1 (~R)-1=~(R-1)RSR-1S-1 -1=2.7關(guān)系的運(yùn)算(3)關(guān)系的逆運(yùn)算1062.7關(guān)系的運(yùn)算(3)關(guān)系的逆運(yùn)算[逆關(guān)系]

設(shè)二元關(guān)系R：XY，定義R-1={<y,x>|xXyY<x,y>R}為R的逆關(guān)系。[性質(zhì)](R-1)-1=R，-1= (RS)-1=R-1S-1

，(RS)-1=R-1S-1

(~R)-1=~(R-1)(R☉S)-1=S-1☉R-1

R=SR-1=S-1 RSR-1S-1 2.7關(guān)系的運(yùn)算(3)關(guān)系的逆運(yùn)算1072.7關(guān)系的運(yùn)算(4)關(guān)系的閉包運(yùn)算[閉包]

設(shè)R為X上的二元關(guān)系，若另有一關(guān)系R，滿足：①

R是自反的；②

RR；③對(duì)于任何自反（對(duì)稱/傳遞）的關(guān)系R，若RR，則RR。則稱R為R的自反（對(duì)稱/傳遞）閉包，記為r(R)(s(R)/t(R))。2.7關(guān)系的運(yùn)算(4)關(guān)系的閉包運(yùn)算1082.7關(guān)系的運(yùn)算[例]整數(shù)集上的“＜”關(guān)系的自反閉包是“≤

”，對(duì)稱閉包是“≠

”，傳遞閉包仍然是“＜”。[例]整數(shù)“=”的自反、對(duì)稱、傳遞閉包都是它本身。[例]有關(guān)系矩陣求Mr(R)、Ms(R)、Mt(R)2.7關(guān)系的運(yùn)算[例]整數(shù)集上的“＜”關(guān)系的自反閉包是1092.7關(guān)系的運(yùn)算2.7關(guān)系的運(yùn)算1102.7關(guān)系的運(yùn)算[定理]設(shè)R為X上的二元關(guān)系，則①r(R)=RIx②s(R)=RR-1[證明]

③

①②2.7關(guān)系的運(yùn)算[定理]設(shè)R為X上的二元關(guān)系，則[證明]1112.8偏序關(guān)系[偏序關(guān)系]

集合A上的一個(gè)關(guān)系R滿足自反性、反對(duì)稱性和傳遞性時(shí)，稱R是A上的一個(gè)偏序關(guān)系，記為“”，用二元組〈A,〉表示該偏序結(jié)構(gòu)，或稱之為偏序集。[例]

A={2,3,6,8},“”={<x,y>|x,yA(x整除y)}

“”={……..}

容易驗(yàn)證，上述關(guān)系為偏序關(guān)系。2.8偏序關(guān)系[偏序關(guān)系]集合A上的一個(gè)關(guān)系R滿足自反性1122.8偏序關(guān)系x、y之間存在偏序關(guān)系時(shí)，說x、y（在該關(guān)系下）可比較，否則說x、y

不可比較。上例中，2和3不可比較（在上述定義的“”下）。[蓋住]

蓋?。ňo鄰遮蓋）。設(shè)〈A,〉，x，yA，

y蓋住xxyxy(z)((xzzy)(x=zy=z))

記covA={<x,y>|x,yA(y蓋住x)}2.8偏序關(guān)系x、y之間存在偏序關(guān)系時(shí)，說x、y（在該關(guān)1132.8偏序關(guān)系表達(dá)偏序關(guān)系的Hasse圖設(shè)有偏序關(guān)系<A,>①用結(jié)點(diǎn)表示集合元素②若<x,y>covA，則用線段連接結(jié)點(diǎn)x,y，且令x(小者)在y的下方。2.8偏序關(guān)系表達(dá)偏序關(guān)系的Hasse圖1142.8偏序關(guān)系[例]

Hasse圖如右圖①

默認(rèn)aa,bb,cc②

ac,cb③

abacbHasseDiagram由畫法可見：①自反關(guān)系為默認(rèn)；②反對(duì)稱關(guān)系體現(xiàn)在“上”、“下”位置上；③由上到下的可達(dá)性表達(dá)了傳遞性。2.8偏序關(guān)系[例]Hasse圖如右圖acbHas1152.8偏序關(guān)系上述Hasse圖表示的對(duì)應(yīng)關(guān)系集合為：{<a,a>,<b,b>,<c,c>,<a,c>,<c,b>,<a,b>}對(duì)應(yīng)關(guān)系圖如下：acbHasseDiagramacb關(guān)系圖2.8偏序關(guān)系上述Hasse圖表示的對(duì)應(yīng)關(guān)系集合為：a1162.8偏序關(guān)系[例]由偏序關(guān)系的關(guān)系圖構(gòu)造相應(yīng)的Hasse圖cab關(guān)系圖dabcHasseDiagramd2.8偏序關(guān)系[例]由偏序關(guān)系的關(guān)系圖構(gòu)造相應(yīng)的Hass1172.8偏序關(guān)系[例]{2,3,6,12,24,36}上的整除關(guān)系的Hasse圖。2624HasseDiagram361232.8偏序關(guān)系[例]{2,3,6,12,24,36}上的1182.8偏序關(guān)系[例]

A的冪集上的關(guān)系的Hasse圖。A={a}{a}{a,b}A={a,b}{a}2.8偏序關(guān)系[例]A的冪集上的關(guān)系的Hasse圖。1192.8偏序關(guān)系[例]

A的冪集上的關(guān)系的Hasse圖。{a,b,c}A={a,b,c}{a}{c}{a,b}{a,c}{b,c}2.8偏序關(guān)系[例]A的冪集上的關(guān)系的Hasse圖。1202.8偏序關(guān)系[最大最小元]

對(duì)偏序集<A,>y0A為最小元(x)(xAy0x)y0A為最大元(x)(xAxy0)[定理]

<

A,>中最大(最小)元若存在則唯一。[證明][極大極小元]

對(duì)<

A,>y0A為極小元(x)(xAxy0?(x

y0))y0A為極大元(x)(xAxy0?(y0x))2.8偏序關(guān)系[最大最小元]對(duì)偏序集<A,>1212.8偏序關(guān)系[例]{2,3,6,12,24,36}上的整除關(guān)系的Hasse圖。2624361232,3為極小元24,36為極大元沒有最小元和最大元2.8偏序關(guān)系[例]{2,3,6,12,24,36}上的1222.8偏序關(guān)系[例]

A的冪集上的關(guān)系的Hasse圖。{a,b,c}A={a,b,c}{a}{c}{a,b}{a,c}{b,c}

為最小元{a,b,c}為最大元2.8偏序關(guān)系[例]A的冪集上的關(guān)系的Hasse圖。1232.8偏序關(guān)系[上下界]

對(duì)<

A,>,BA,aA

a是B的一個(gè)上界(x)(xBx

a)

a是B的一個(gè)下界(x)(xBax)說明：a不一定是B的元素，即可能aA-BB的上(下)界不一定存在，存在也不一定唯一。2.8偏序