离散数学课件第三章集合与关系-2电子教案

3-7复合(fùhé)关系和逆关系二元关系是以序偶为元素(yuánsù)的集合，所以可以对它进行集合运算。此外还有一种新的运算：关系的复合定义3-7.1设R是从集合A到集合B上的二元关系，S是从集合B到集合C上的二元关系，则R◦S称为R和S的复合关系，表示为R◦S={<x，z>x∈A∧z∈C∧y(y∈B∧<x，y>∈R∧<y，z>∈S)}第一页，共82页。复合关系(guānxì)举例例：A={1，2，3，4}，B={3，5，7}，C={1，2，3}R={<2,7>，<3,5>，<4,3>}，S={<3,3>，<7,2>}则R◦S={<2，2>，<4，3>}如图所示：第二页，共82页。复合(fùhé)关系的结合律定理(dìnglǐ)：设R1A1A2,R2A2A3,R3A3A4,则(R1◦R2)◦R3=R1◦(R2◦R3)。例：设A={1,2,3,4,5}A上的二元关系R={<1,2>,<3,4>,<2,2>}S={<4,2>,<2,5>,<3,1>,<1,3>}

则

R◦S={<1,5>,<3,2>,<2,5>}

S◦R={<4,2>,<3,2>,<1,4>}≠R◦S

(R◦S)◦R={<3,2>}

R◦(S◦R)={<3,2>}第三页，共82页。复合(fùhé)关系的矩阵表示（自学）两个(liǎnɡɡè)关系的复合可通过相应矩阵相乘获得。第四页，共82页。复合(fùhé)关系练习练习(liànxí)：R是A上的二元关系，试证R是传递的充要条件是R◦RR证：‘’：<x,z>R◦R必y使得(shǐde)<x,y>R，<y,z>R∵R是传递的∴<x,z>R∴R◦RR‘’：<x,y>R,<y,z>R必有<x,z>R◦R∵R◦RR∴<x,z>R∴由x,y,z任意性知xyz(<x,y>R∧<y,z>R<x,z>R)∴R是传递的第五页，共82页。逆关系(guānxì)定义3-7.2设R是A到B的二元关系(guānxì)，则R的逆是B到A的二元关系(guānxì)，记为Rc，其中Rc={<y,x>|<x,y>R}。注：（1）xRyyRcx（2）互换R的关系(guānxì)矩阵的行和列，即得Rc的关系(guānxì)矩阵。即MRc＝MRT（3）颠倒R的关系(guānxì)图中每条弧线的箭头方向，即得Rc的关系(guānxì)图。第六页，共82页。逆关系(guānxì)举例例1整数集上的‘<’关系(guānxì)的逆是‘>’关系(guānxì)集合族上的‘’关系(guānxì)的逆是‘’空关系(guānxì)的逆是空关系(guānxì)AB的全域关系(guānxì)的逆是BA的全域关系(guānxì)例2A={0,1,2,3}，R={<0,0>,<0,3>,<3,2>,<1,3>}则Rc={<0,0>,<3,0>,<2,3>,<3,1>}第七页，共82页。定理(dìnglǐ)定理：设R,R2,R1是A到B的关系(guānxì)，则a）(Rc)c=Rb）(R1∪R2)c=R1c∪R2cc）(R1∩R2)c=R1c∩R2d）(~R)c=~(Rc),~R=AB-R即R的补的逆等于逆的补e）(R1-R2)c=R1c-R2cf)(AB)c=BA第八页，共82页。定理(dìnglǐ)定理3-7.2设R、S分别(fēnbié)是A到B、B到C的关系，则(R◦S)c=Sc◦Rc

证：设<c,a>是(R◦S)c的任一元素(yuánsù)，则<c,a>(R◦S)c<a,c>R◦S b(<a,b>RΛ<b,c>S)b(c,b>ScΛ<b,a>Rc)<c,a>Sc◦Rc第九页，共82页。定理(dìnglǐ)定理(dìnglǐ)3-7.3R是A上的二元关系(a)R是对称的R=Rc(b)R是反对称的R∩RcIA证：(a)‘’：任取<a,b>R，因为R是对称(duìchèn)的，所以<a,b>R<b,a>R<a,b>Rc‘’：任取<a,b>R，则<b,a>Rc∵R=Rc∴<b,a>R∴R是对称(duìchèn)的(b)略第十页，共82页。3-8关系(guānxì)的闭包运算设R是A上的关系，我们希望(xīwàng)R具有某些有用的性质，比如说自反性。如果R不具有自反性，我们通过在R中添加一部分有序对来改造R，得到新的关系R’，使得R’具有自反性。但又不希望(xīwàng)R’与R相差太多，换句话说，添加的有序对要尽可能的少。满足这些要求的R’就称为R的自反闭包。通过添加有序对来构造的闭包除自反闭包外还有对称闭包和传递闭包。第十一页，共82页。各种(ɡèzhǒnɡ)闭包的定义定义(dìngyì)3-8.1设R是非空集合A上的关系，R的自反（对称或传递）闭包是A上的关系R’，使得R’满足以下条件：

（1）R’是自反的（对称的或传递的）

（2）RR’

（3）对A上任何包含R的自反（对称或传递）关系R”，有R’R”。

一般将R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R)。

第十二页，共82页。注：R的自反闭包记为r(R),若R是自反的，则R=r(R),反之(fǎnzhī)也成立。R的对称闭包记为s(R),若R是对称的，则R=s(R),反之(fǎnzhī)也成立。R的传递闭包记为t(R),若R是传递的，则R=t(R),反之(fǎnzhī)也成立。第十三页，共82页。构造(gòuzào)闭包的方法下面的定理给出了构造闭包的方法：①自反(zìfǎn)闭包r(R)=R∪IA<用关系图解释>②对称闭包s(R)=R∪Rc③传递闭包t(R)==R∪R2∪R3∪…

第十四页，共82页。证明(zhèngmíng)r(R)=R∪IA证：设R’=R∪IA∵①xA,<x,x>R’∴R’具有(jùyǒu)自反性②RR’③设R”是自反的，且RR”∵R’’是自反的，∴IAR” 又∵RR”∴R’=IA∪RR”综上所述，R’满足自反闭包定义的三个条件，∴r(R)=R’=R∪IA第十五页，共82页。证明(zhèngmíng)s(R)=R∪Rc证明：设R’=R∪Rc①R’c=(R∪Rc)c=Rc∪(Rc)c=Rc∪R=R’，所以(suǒyǐ)R’是对称的②R’=R∪RcR③设R”是对称的，且RR”，要证R’R”任取<a,b>∈R∪Rc<a,b>∈R∨<a,b>∈Rc<a,b>∈R”∨<b,a>∈R<a,b>∈R”∨<b,a>∈R”<a,b>∈R”∨<a,b>∈R”<a,b>∈R”∴R’=R∪RcR”综上所述，由定义知道，R’即R∪Rc为R的对称闭包。第十六页，共82页。证t(R)==R∪R2∪R3∪…(R为A上的二元关系）证：(1)证t(R)：①先用归纳法证，对n>0,Rnt(R)a)由定义(dìngyì)Rt(R)b)设Rnt(R)成立，要证Rn+1t(R)任取<a,b>∈Rn+1=Rn◦R，∴存在c∈A,使<a,c>∈Rn,<c,b>∈R∵由归纳假设和基础步骤知<a,c>∈t(R)，<c,b>∈t(R）∵t(R)是传递的，∴<a,b>∈t(R)即Rn+1t(R)∴对一切n，Rnt(R) 第十七页，共82页。②根据(gēnjù)①的结论，证t(R)：任取<a,b>∈∴存在一个n，使<a,b>∈Rnt(R)∴<a,b>∈t(R)∴t(R)第十八页，共82页。(2)证t(R)①设<a,b>,<b,c>是的任意元素必s,t,使得<a,b>∈Rs,<b,c>∈Rt∴<a,c>∈Rt◦Rs=Rt+s∴<a,c>∈∴是传递的②∵t(R)是包含(bāohán)R的最小传递关系∴t(R)由（1），（2）得t(R)=第十九页，共82页。闭包运算举例(jǔlì)题：设A={a,b,c},R是A上的二元关系，且给定(ɡěidìnɡ)R={<a,b>,<b,c>,<c,a>},求r(R),s(R),t(R)。解：r(R)=R∪IA={<a,b>,<b,c>,<c,a>,<a,a>,<b,b>,<c,c>}s(R)=R∪Rc={<a,b>,<b,a>,<b,c>,<c,b>,<c,a>,<a,c>}t(R)=R∪R2∪R3∪…=R∪R2∪R3（因为R4=R,R5=R2,R6=R3,…)={<a,a>,<b,b>,<c,c>,<a,b>,<b,c>,<c,a>,<a,c>,<b,a>,<c,b>}第二十页，共82页。定理3-8.5设R为X上二元关系，X=n，那么(nàme)，存在一个正整数k≤n，使得t(Ｒ)=RR2R3...Rk例：P123例题2第二十一页，共82页。求R+的算法(suànfǎ)——Warshall算法(suànfǎ)A←Mi=1对i列中出现1的各行，分别被‘或’上i行i=i+1i≤n结束Y例：P124例题(lìtí)3第二十二页，共82页。P125例题(lìtí)4设有一字母(zìmǔ)表V={A,B,C,D,e,d,f}并给定下面六条规则：A->Af,B->Dde,C->e,A->B,B->De,D->BfR为定义在V上的二元关系且xiRxj，即是从xi出发用一条规则推出一串字符，使其第一个字符恰为xj。说明每个字母(zìmǔ)连续应用上述规则可能推出的头字符。第二十三页，共82页。闭包运算的性质(xìngzhì)设R为集合X上的任一二元关系，那么a)rs(R)=sr(R)自反对称(duìchèn)闭包等于对称(duìchèn)自反闭包b)tr(R)=rt(R)传递自反闭包等于自反传递闭包c)ts(R)st(R)传递对称(duìchèn)闭包包含对称(duìchèn)传递闭包

第二十四页，共82页。证明(zhèngmíng)rs(R)=sr(R)证：rs(R)=r(s(R))=r(R∪Rc)=Ix∪R∪Rc=Ix∪R∪Rc∪Ix

=(Ix∪R)∪(Rc∪Ixc)=(Ix∪R)∪(R∪Ix)c=s(Ix∪R)=sr(R)第二十五页，共82页。证明(zhèngmíng)rt(R)=tr(R)证：rt(R)=r(R∪R2∪…)=IX∪R∪R2∪…

tr(R)=t(R∪IX)=IX∪R∪(IX∪R)2∪…∪(IX∪R)n∪…=IX∪R∪R2∪…∪Rn∪…∴rt(R)=tr(R)注：以上证明(zhèngmíng)引用了公式：（证明(zhèngmíng)略）(R∪IX)n=IX∪R∪R2∪…∪Rn∪…第二十六页，共82页。证明(zhèngmíng)st(R)ts(R)证：①先证R对称(duìchèn)t(R)对称(duìchèn)t(R)-1=(RR2R3…)-1=R-1(R2)-1(R3)-1…=R-1(R-1)2(R-1)3…((F◦G)-1=G-1◦F-1，定理3-7.2)=RR2R3…=t(R)t(R)对称(duìchèn).②因为Rs(R),故st(R)st(s(R))而st(s(R))=sts(R)=s(ts(R))=ts(R)st(R)ts(R).第二十七页，共82页。注：st(R)ts(R)未必(wèibì)成立。反例：设R={<a,b>,<c,b>}则s(R)={<a,b>,<b,a>,<c,b>,<b,c>}t(s(R))={<a,b>,<b,a>,<c,b>,<b,c>,<a,a>,<a,c>,<b,b>,<c,a>,<c,c>…}s(t(R))=s{<a,b>,<c,b>}={<a,b>,<b,a>,<c,b>,<b,c>}t(s(R))注意：先做传递，再做对称，有可能(kěnéng)破坏传递性。第二十八页，共82页。3-9集合的划分(huàfēn)和覆盖除了把两个集合相互比较外，还常把一个集合分成若干子集(zǐjí)讨论。定义3-9.1设A为非空集，S={S1…Sm},SiA，Si(i=1…m)且S1∪S2∪...∪Sm=A，称S是A的覆盖.若再加Si∩Sj=(i,j=1…m,i<>j)则称S是A的划分,m称为划分的秩。第二十九页，共82页。集合(jíhé)的划分和覆盖举例例1设A={1,2,3,4,5}，下面哪些是覆盖，哪些是划分(huàfēn)：(1)X={{1,2},{3},{4,5}}(2)Y={{1,2},{2,3},{4,5}}(3)Z={{1,2,3},{4}}(4)U={{1,2,3,4,5}}(5)V={{1},{2},{3},{4},{5}}U称为A的最小划分(huàfēn)，V称为A的最大划分(huàfēn)。第三十页，共82页。交叉(jiāochā)划分定义3-9.2若S1={A1…Am},S2={B1…Bn}是A的二个划分,则S={Ai∩Bj|AiS1∧BjS2}称为A的交叉(jiāochā)划分。定理3-9.1设{A1,A2,…,Am}与{B1,B2,…,Bn}为同一集合A的两个划分。则其交叉(jiāochā)划分Ai∩Bj亦是原集合的一种划分。第三十一页，共82页。交叉划分(huàfēn)举例例：设B是所有生物的集合(jíhé),可划分成{A,P}, 其中A表示所有动物Animal的集合(jíhé),P表示所有植物Plant的集合(jíhé)。B也可划分成{F,L},其中F表示史前First生物,L表示史后Last生物。它们的交叉划分为: D={A∩F,A∩L,P∩F,P∩L},其中A∩F是史前动物,A∩L是史后动物,P∩F是史前植物,P∩L是史后植物。第三十二页，共82页。加细定义3-9.3设S,S’是集合A的二个划分，若S的每一块均是S’中某块的子集，S是S’的加细。例:A=正整数集S={{1,3,5,7…},{2,4,6…}}S’={{1,5,9…},{3,7，11…},{2,4,6…}}则S’是S的细分定理3-9.2任何(rènhé)两种划分的交叉划分，都是原来各划分的一种加细。第三十三页，共82页。练习(liànxí)：3-9（2）证明：1.aA，a与a在同一分块中，故必有aRa。故R是自反的。2.若a与b在同一分块中，b与a也必在同一分块中，即aRbbRa，故R是对称的。3.若a与b在同一分块中，b与c在同一分块中，根据划分的定义，b属于(shǔyú)且仅属于(shǔyú)一个分块，故a与c必在同一分块中。即aRb∧bRcaRc，故R是传递的。第三十四页，共82页。3-10等价(děngjià)关系与等价(děngjià)类等价关系是一类重要的二元关系。

定义3-10.1若集合A上的二元关系R是自反的，对称的和传递的，称R是等价关系。若R是等价关系，aRb，可读为“a等价于b”。例如，数中的相等(xiāngděng)关系，是等价关系集合中的相等(xiāngděng)关系，是等价关系命题演算中‘’关系，是等价关系全域关系是等价关系，空集上任何关系是等价关系。第三十五页，共82页。等价关系举例(jǔlì)例：设A={1,2,…,8}，如下定义(dìngyì)A上的关系R：

R={<x，y>|x，y∈A∧x≡y(mod3)}

其中x≡y(mod3)叫做模3同余，即x除以3的余数与y除以3的余数相等。不难验证R为A上的等价关系，因为①x∈A，有x≡x(mod3)，②x，y∈A，若x≡y(mod3)，则有y≡x(mod3)，

③x，y，z∈A，若x≡y(mod3)，y≡z(mod3)，则有x≡z(mod3)。

该关系的关系图如下：第三十六页，共82页。等价关系举例(jǔlì)（续）不难看出，上述关系图被分为三个互不相连通的部分。每部分中的数两两都有关系，不同部分中的数则没有(méiyǒu)关系。每一部分中的所有的顶点构成一个等价类。

第三十七页，共82页。等价(děngjià)类定义3-10.2设R是A上的等价关系，对aA，集合(jíhé)[a]R={x|xRa}称为a关于R的等价类，简记为[a]，a称为等价类[a]R的表示元素。从以上定义可以知道，a的等价类是A中所有与a等价的元素构成的集合(jíhé)。上例中的等价类是：

[1]=[4]=[7]={1,4,7}

[2]=[5]=[8]={2,5,8}

[3]=[6]={3,6}第三十八页，共82页。例：设I是整数集，R是模3同余关系，即R={<x,y>|xI∧yI∧xy(mod3)}不难验证(yànzhèng)R是等价关系，其等价类为[0]R={…-6,-3,0,3,6…}[1]R={…-2,1,4…}[2]R={…-4,-1,2,5…}等价类的每一元素均可作本等价类的表示元素。第三十九页，共82页。定理3-10.1设给定集合(jíhé)A上的等价关系R，对于a,bA有aRbiff[a]R=[b]R证：‘’∵a[a]R=[b]R根据等价类定义∴aRb‘’∵aRb ∴x[a]RxRaxRbx[b]R由x的任意性知，[a]R=[b]R第四十页，共82页。商集定义3-10.3集合A上的等价关系R，其等价类集合{[a]R|aA}，称为A关于(guānyú)R的商集，记为A/R。例1：A={1,2,…,8}，R={<x，y>|x，y∈A∧x≡y(mod3)}则A/R={{1,4,7},{2,5,8},{3,6}}例2：A为正整数集合，R是模3同余关系，则A/R={[0]R,[1]R,[2]R}，其中[0]R={…-6,-3,0,3,6…}[1]R={…-2,1,4…}[2]R={…-4,-1,2,5…}第四十一页，共82页。显然：商集是集合的集合。商集的每个元素是等价关系的一个等价类。等价类中的每个元素都是集合A上的元素。同一(tóngyī)等价类中的任意两个元素都具有关系R。第四十二页，共82页。商集举例(jǔlì)例：设集合(jíhé)S={a,b,c,d,e,f,g}，S上的等价关系R如下表所示，求商集S/R。

abcdefga√√√

b√√√

c√√√

d

√√

e

√√

f

√√g

√√S/R={{a,b,c},{d,e},{f,g}}思考(sīkǎo)：R=?第四十三页，共82页。根据等价类对集合(jíhé)进行划分定理3-10.2集合A上的等价关系R决定(juédìng)了A的一个划分，即为商集A/R。证明A/R={[a]R|aA}（1）根据(gēnjù)等价类定义，aA，[a]RA∴∪[a]RA∵aA，aRa∴a[a]R∴A∪[a]R∴∪[a]R=A∴A/R是一个覆盖第四十四页，共82页。根据等价类对集合进行(jìnxíng)划分（2）证：需证a,bA，若[a]R[b]R，则[a]R∩[b]R=。反证法：若[a]R∩[b]R则c[a]R∩[b]R∴cRa且cRb∵R是对称、传递的∴aRb 则[a]R=[b]R，这与前提(qiántí)矛盾。∴由（1），（2）得A/R是一个划分。第四十五页，共82页。定理3-10.3集合(jíhé)A的任一划分S确定了A的一个等价关系R。证明设S={S1，S2，…Sm}（构造性证明）定义关系R:aRb当且仅当a,b在S的同一块(yīkuài)中，现证R是等价关系。(1)aA，a与a在同一块(yīkuài)中∴aRa，自反性成立。(2)a,bA，若aRb，则a与b在同一块(yīkuài)中，则b与a也在同一块(yīkuài)∴bRa，即aRbbRa∴对称性成立第四十六页，共82页。(3)a,b,cA，若aRb，bRc，则a与b在同一块(yīkuài)，b与c在同一块(yīkuài)∵Si∩Sj=(ij)∴a与c在同一块(yīkuài)，即aRb∧bRcaRc∴传递性成立综上所述，R是A的一个等价关系，且A/R=S第四十七页，共82页。定理(dìnglǐ)3-10.3举例例：A={a,b,c,d,e}，S={{a,b},{c},{d,e}}，求由S确定(quèdìng)的等价关系。

解：设R1={a,b}{a,b}={<a,a>,<a,b>,<b,a>,<b,b>}R2={c}{c}={<c,c>} R3={d,e}{d,e}={<d,d>,<d,e>,<e,d>,<e,e>}则R=R1∪R2∪R3是由S确定(quèdìng)的等价关系。若S={{a},{b},{c,d,e}}，则由S确定(quèdìng)的等价关系是什么？第四十八页，共82页。定理(dìnglǐ)3-10.4设R1，R2是非空集合A上的等价关系，则R1=R2A/R1=A/R2。证明(zhèngmíng)‘’：若R1=R2∵A/R1={[a]R1|aA}，A/R2={[a]R2|aA}则x[a]R1<x,a>R1<x,a>R2x[a]R2，∴[a]R1[a]R2同理可证，[a]R2[a]R1∴[a]R1=[a]R2∴A/R1=A/R2第四十九页，共82页。‘’：aA，[a]R1

A/R1

∵A/R1=A/R2∴必[c]R2A/R2，使[a]R1=[c]R2∴a,bA<a,b>R1a[a]R1∧b[a]R1

a[c]R2∧b[c]R2

<a,b>R2

∴R1R2同理可证：R2R1∴R1=R2综上所述，R1=R2A/R1=A/R2第五十页，共82页。例：设Π和Π’是非空集A的划分,R、R’是分别(fēnbié)由Π、Π’确定的等价关系，试证Π’细分ΠR’R证：‘’：<a,b>R’则a、b在Π’的同一块(yīkuài)中，∵Π’细分Π∴a、b在Π的同一块(yīkuài)∴<a,b>R∴R’R‘’：设Si’Π’aSi’，则Si’=[a]R’={x|xR’a}∴xSi’xR’axRax[a]R∴[a]R’[a]R∴由Si’的任意性，知Π’细分Π∴Π’细分ΠR’R第五十一页，共82页。加细（细分）图解(tújiě)第五十二页，共82页。3-11相容(xiānɡrónɡ)关系定义3-11.1设R是集合A上的二元关系，若R是自反(zìfǎn)的和对称的，称R是相容关系。例：所有等价关系是相容关系；在一群人的集合中,朋友关系也是相容关系。第五十三页，共82页。相容关系(guānxì)的表示方法因为相容(xiānɡrónɡ)关系是自反和对称的,其关系矩阵是对称的且主对角线元素全为1,因此我们可仅用下三角矩阵T来表示和存储就够了,即关系矩阵可以简化为“阶梯形”。相容(xiānɡrónɡ)关系的关系图可简记为：①用无向边代替二有向边②自回路省略第五十四页，共82页。相容关系的表示(biǎoshì)方法(P135例题)111000111110111100011110010110000001x1x6x4x3x2x5相容关系r的矩阵(jǔzhèn)及图形表示第五十五页，共82页。定义3-11.2设R是集合A上的相容(xiānɡrónɡ)关系,若CA,若任意a,bC,有aRb,则称C是由R产生的相容(xiānɡrónɡ)类。例：上例相容(xiānɡrónɡ)关系r产生的相容(xiānɡrónɡ)类。第五十六页，共82页。最大相容(xiānɡrónɡ)类定义3-11.3设R为定义在集合A上的相容关系，如果不能真包含在任何其他相容类中的相容类，称作(chēnɡzuò)最大相容类，记为CR。例：P137例题1a3a4a2a5a7a6a1第五十七页，共82页。相容关系(guānxì)的确定利用相容关系的关系图来确定相容类和最大相容类是方便的。极大完全子图的顶点(dǐngdiǎn)集合就是最大相容类。所谓极大完全子图是指每对顶点(dǐngdiǎn)都有边相连的多边形,而最大相容类外的任何顶点(dǐngdiǎn)不可能与类内的所有顶点(dǐngdiǎn)相连。另外孤立顶点(dǐngdiǎn),以及不在极大完全子图两个顶点(dǐngdiǎn)及其连线,也是最大相容类。第五十八页，共82页。例设给定(ɡěidìnɡ)的相容关系图表示成下图,写出所有的最大相容类。解最大相容(xiānɡrónɡ)类：{h},{a,b},{d,e,f},{b,c,d,f,g}。第五十九页，共82页。完全(wánquán)覆盖定义3-11.4设R为定义在集合A上的相容关系，其最大相容类的集合称作集合A的完全(wánquán)覆盖，记为CR(A)。例1：123456A的完全(wánquán)覆盖是：{{1，2，3，4}，{5，6}，{5，2}，{6，3}}第六十页，共82页。3-12序关系(guānxì)定义3-12.1若集合A上的二元关系R是自反的、反对称的和传递的，则称R是A的偏序关系，记作。设为偏序关系，如果<x,y>∈，则记作xy，读作“小于或等于”。序偶<A,>称为偏序集合。注意这里的“小于或等于”不是指数的大小，而是在偏序关系中的顺序性。x“小于或等于”y的含义是：依照这个序，x排在y的前边或者x就是y。根据不同(bùtónɡ)偏序的定义，对序有着不同(bùtónɡ)的解释。例如整除关系是偏序关系，36的含义是3整除6。大于或等于关系也是偏序关系，针对这个关系写54是说大于或等于4,关系中5排在4的前边，也就是5比4大。第六十一页，共82页。盖住定义3-12.2在偏序集<A，>中，如果x,yA，xy，xy，且没有其他元素z满足xz、zy，则称元素y盖住元素x。并且把所有(suǒyǒu)具备盖住性质的续偶集合记作COVA，COVA={<x,y>|y盖住x}例：A为正整数m＝12的因子的集合，并设为整除关系，求COVA。(P140)第六十二页，共82页。哈斯图（偏序集合(jíhé)图）对于给定(ɡěidìnɡ)的偏序集<A，>，它的盖住关系是唯一的，所以可以用哈斯图表示偏序集合图。哈斯图作图规则：用小圆圈代表元素。如果xy，且xy，则将代表y的小圆圈画在代表x的小圆圈之上。如果<x,y>COVA,则在x与y之间用直线连接。第六十三页，共82页。哈斯图举例(jǔlì)例：画出偏序集<{1,2,3,4,5,6,7,8,9}，R整除(zhěngchú)>的哈斯图。

第六十四页，共82页。哈斯图举例(jǔlì)（续）例：A={a,b,c}，画出<ρ(A),>的哈斯图。{a}{b}{c}{a,b}{a,c}{b,c}{a,b,c}第六十五页，共82页。哈斯图举例(jǔlì)（续）例：已知偏序集<A,R>的哈斯图如图所示，试求出集合(jíhé)A和关系R的表达式。解：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

abcdefhg第六十六页，共82页。偏序集中的特殊(tèshū)元素定义(dìngyì)3-12.5,3-12.6设<A，>为偏序集，B是A的子集，y∈B。若x(x∈B→yx)成立，则称y为B的最小元。若x(x∈B→xy)成立，则称y为B的最大元。若bB,且B中不存在任何元素x,使bx且bx称b是B的极大元。若bB,且B中不存在任何元素x,使bx且xb称b是B的极小元。第六十七页，共82页。例：设偏序集<A，>如图所示，求A的极小(jíxiǎo)元，最小元，极大元，最大元。abcdefhg解:极小元：a,b,c,g。极大元：a,f,h。

没有最小元与最大元。

由这个例子可以知道(zhīdào)，哈斯图中的孤立顶点既是极小元也是极大元。第六十八页，共82页。baedc解：A不存在最大、最小元；极大(jídà)元素为d,e,极小元素为a,b；B的最大元素为c，没有最小元素；极大(jídà)元素为c,极小元素为a,b。例：设A={a,b,c,d,e}、B={a,b,c}，则各自的最大最小元素、极大极小(jíxiǎo)元素是哪些？第六十九页，共82页。最小元是B中最小的元素，它与B中其它元素都可比；而极小元不一定与B中元素可比，只要没有比它小的元素，它就是极小元。对于有穷集B，极小元一定存在，但最小元不一定存在。最小元如果存在，一定是唯一的，但极小元可能有多个(duōɡè)。如果B中只有一个极小元，则它一定是B的最小元。如果B中存在最小元，则它一定是B的唯一极小元。类似的，极大元与最大元也有这种区别。

第七十页，共82页。定理3-12.1设<A,>是一偏序集合(jíhé)，且BA，若B有最大（最小）元，则是唯一的。证：设a,b都是B的最大元素，那么ab,ba，从偏序关系的反对称性，得a=b。最小元证明情况与此类似。第七十一页，共82页。上界、下界(xiàjiè)定义3-12.7，3-12.8设<A，>为偏序集，BA，y∈A。

（1）若x(x∈B→xy)成立(chénglì)，则称y为B的上界。

（2）若x(x∈B→yx)成立(chénglì)，则称y为B的下界。

（3）令C＝{y|y为B的上界}，则称C的最小元为B的最小上界或上确界。

（4）令D＝{y|y为B的下界}，则称D的最大元为B的最大下界或下确界。第七十二页，共82页。设<A,>为有序集，BA。的哈斯图如下(rúxià)所示。A={a，b，c，d，