《离散数学课件第三章集合与关系课件》由会员分享，可在线阅读，更多相关《离散数学课件第三章集合与关系课件（82页珍藏版）》请在金锄头文库上搜索。
1、3-7 3-7 复合关系和逆关系复合关系和逆关系 二元关系是以序偶为元素的集合，所以可以对二元关系是以序偶为元素的集合，所以可以对它进行集合运算。它进行集合运算。 此外还有一种新的运算：此外还有一种新的运算：关系的复合关系的复合定义定义3-7.13-7.1 设设R R是从集合是从集合A A到集合到集合B B上的二元关系，上的二元关系，S S是从集合是从集合B B到集合到集合C C上的二元关系，则上的二元关系，则R RS S称为称为R R和和S S的的复合关系复合关系，表示为，表示为 R RS= xS= z xAzCxAzC y(yBy(yBxRRS) zS) 复合关系举例复合关系举例例：例：A
2、=1A=1，2 2，3 3，44，B=3B=3，5 5，77，C=1C=1，2 2，33R=R=，S=S=，则则 R RS=2S=2，43如图所示：如图所示：复合关系的结合律复合关系的结合律定理：定理：设设R R1 1 A A1 1 A A2 2, R, R2 2 A A2 2 A A3 3, R, R3 3 A A3 3 A A4 4, , 则则 (R(R1 1R R2 2) )R R3 3 = R = R1 1(R(R2 2R R3 3) )。例：例：设设A=1,2,3,4,5A=1,2,3,4,5 A A上的二元关系上的二元关系R=,R=, S=, S=, 则则 R RS=S=, S S
3、R=R=, , R RS S (R(RS)S)R=R= R R(S(SR)=R)=复合关系的矩阵表示（自学）复合关系的矩阵表示（自学）两个关系的复合可通过相应矩阵相乘获得。两个关系的复合可通过相应矩阵相乘获得。复合关系练习复合关系练习练习：练习：R R是是A A上的二元关系，试证上的二元关系，试证R R是传递的充要条是传递的充要条件是件是R RR R R R证：证： ： R RR R 必必 y y使得使得 R R， R R R R是传递的是传递的 R R R RR R R R ： R, R, R R 必有必有 R R R R R R R R R R R R 由由x,y,zx,y,z任意性知任意
4、性知 x x y y z(z( RR R R R)R) R R是传递的是传递的 逆关系逆关系定义定义3-7.23-7.2 设设R R是是A A到到B B的二元关系，则的二元关系，则R R的逆的逆是是B B到到A A的二元关系，记为的二元关系，记为R Rc c，其中，其中R Rc c =| =| RR。注注 ：（1 1）xRyxRyyRyRc cx x （2 2）互互换换R R的的关关系系矩矩阵阵的的行行和和列列，即即得得R Rc c的的关系矩阵。关系矩阵。 即即 M M M MR R R Rc c c cM M M MR R R RT T T T （3 3）颠颠倒倒R R的的关关系系图图中中每
5、每条条弧弧线线的的箭箭头头方方向向，即得即得R Rc c的关系图。的关系图。逆关系举例逆关系举例例例1 1 整数集上的整数集上的 关系关系 集合族上的集合族上的 关系的逆是关系的逆是 空关系的逆是空关系空关系的逆是空关系 A A B B的全域关系的逆是的全域关系的逆是B B A A的全域关系的全域关系例例2 2 A=0,1,2,3 A=0,1,2,3，R=,R=, 则则 R Rc c = , = , 定理定理定理：定理：定理：定理：设设R,R2,R1R,R2,R1是是A A到到B B的关系，则的关系，则a a） (R (Rc c) )c c=R=Rb b） (R1R2) (R1R2)c c =
6、 R1= R1c cR2R2c cc c） (R1R2) (R1R2)c c = R1 = R1c cR2R2d d） (R) (R)c c = (R = (Rc c), R=A), R=A B-R B-R 即即R R的补的补的逆等于逆的补的逆等于逆的补e e） (R1-R2) (R1-R2)c c =R1 =R1c c -R2 -R2c cf)f) (A (A B)B)c c = B= B A A定理定理定理定理3-7.23-7.2 设设R R、S S分别是分别是A A到到B B、B B到到C C的关系，的关系， 则则(R(RS)S)c c=S=Sc c R Rc c 证：设证：设 是是(R
7、(RS)S)c c 的任一元素，的任一元素， 则则 (R(RS)S)c c R RS S b(b( RR S)S) b(c,bb(c,b S Sc c R Rc c) ) S Sc c R Rc c定理定理定理定理3-7.33-7.3 R R是是A A上的二元关系上的二元关系(a) R(a) R是对称的是对称的 R=RR=Rc c(b) R(b) R是反对称的是反对称的 RR RRc c I IA A证：证：(a)(a)：任取任取 R R，因为，因为R R是对称的，是对称的， 所所以以 R R R R R R c c ：任取任取 R R ， 则则 R Rc c R=R R=Rc c R R R
8、 R是对称的是对称的 (b) (b)略略3-8 3-8 关系的闭包运算关系的闭包运算 设设R R是是A A上的关系，我们希望上的关系，我们希望R R具有某些有用的具有某些有用的性质，比如说自反性。如果性质，比如说自反性。如果R R不具有自反性，我们不具有自反性，我们通过在通过在R R中添加一部分有序对来改造中添加一部分有序对来改造R R，得到新的关，得到新的关系系RR，使得，使得RR具有自反性。但又不希望具有自反性。但又不希望RR与与R R相相差太多，换句话说，添加的有序对要尽可能的少。差太多，换句话说，添加的有序对要尽可能的少。满足这些要求的满足这些要求的RR就称为就称为R R的自反闭包。的
9、自反闭包。通过添加通过添加有序对来构造有序对来构造的的闭包闭包除自反闭包外还有对称闭包和除自反闭包外还有对称闭包和传递闭包。传递闭包。各种闭包的定义各种闭包的定义定义定义3-8.1 3-8.1 设设R R是非空集合是非空集合A A上的关系，上的关系，R R的自反的自反（对称或传递）闭包是（对称或传递）闭包是A A上的关系上的关系RR，使得，使得RR满满足以下条件：足以下条件：（1 1）RR是自反的（对称的或传递的）是自反的（对称的或传递的）（2 2）R R R R （3 3）对对A A上任何包含上任何包含R R的自反（对称或传递）的自反（对称或传递）关系关系R”R”，有，有 R R R” R”
10、。 一般将一般将R R的的自反闭包记作自反闭包记作r(R)r(R)，对称闭包记作对称闭包记作s(R)s(R)，传递闭包记作传递闭包记作t(R)t(R)。注：注：注：注： R R的的 自自 反反 闭闭 包包 记记 为为 r(Rr(R),),若若 R R是是 自自 反反 的的 ， 则则R=R=r(Rr(R),),反之也成立。反之也成立。 R R的的 对对 称称 闭闭 包包 记记 为为 s(Rs(R),),若若 R R是是 对对 称称 的的 ， 则则R=R=s(Rs(R),),反之也成立。反之也成立。 R R的的 传传 递递 闭闭 包包 记记 为为 t(Rt(R),),若若 R R是是 传传 递递
11、的的 ， 则则R=R=t(Rt(R),),反之也成立。反之也成立。构造闭包的方法构造闭包的方法下面的定理给出了下面的定理给出了构造闭包的方法构造闭包的方法： 自反闭包自反闭包 r(R)=RI r(R)=RIA A 对称闭包对称闭包 s(R)=RR s(R)=RRc c 传递闭包传递闭包 t(R)= = RR t(R)= = RR2 2RR3 3 证明证明 r(R)=RI r(R)=RIA A证：设证：设R = RIR = RIA A x x A,A, R R RR具有自反性具有自反性 R R RR 设设R”R”是自反的，且是自反的，且R R R”R” R R是自反的，是自反的，IIA A R”
12、 R” 又又RR R” R” R=IR=IA ARR R”R” 综上所述，综上所述，RR满足自反闭包定义的三个条件满足自反闭包定义的三个条件， r(R)= R= RI r(R)= R= RIA A 证明证明 s(R)=RRs(R)=RRc c 证明：设证明：设 R= RR R= RRc c R Rc c= =(RR(RRc c) )c c=R=Rc c(R(Rc c) )c c= R= Rc cR=R R=R ， 所以所以RR是对称的是对称的 R=RRR=RRc c R R 设设 R”R”是是 对对 称称 的的 ， 且且 R R R” R” ， 要要 证证 RR R”R” 任取任取RRRRc
13、cRRRRc c R”R R”R R”R” R”R” R”R” R”R” R”R” RR= =RRRRc c R”R”综上所述，由定义知道，综上所述，由定义知道，RR即即RRRRc c为为R R的对称闭包。的对称闭包。证证 t(R)= = RR t(R)= = RR2 2RR3 3(R(R为为A A上的二元关系）上的二元关系）证：证：(1)(1)证证 t(R)t(R)： 先用归纳法证，对先用归纳法证，对 n0, Rn0, Rn n t(R)t(R) a) a)由定义由定义 R R t(R) t(R) b) b)设设R Rn n t(R) t(R)成立，要证成立，要证R Rn+1n+1 t(R)
14、 t(R) 任取任取RRn+1n+1=R=Rn nR R， 存在存在cA,cA,使使RRn n,R ,R 由归纳假设和基础步骤知由归纳假设和基础步骤知 t(R) t(R) ，t(Rt(R） t(R) t(R)是传递的，是传递的， t(R)t(R) 即即 R Rn+1 n+1 t(R)t(R) 对一切对一切n n， R Rn n t t(R)(R) 根据根据的结论，证的结论，证 t(R)t(R)： 任取任取 存在一个存在一个n n，使，使RRn n t(R) t(R) t(R) t(R) t(R) t(R) (2)(2) 证证 t(R) t(R) 设设,是是 的任意元素的任意元素 必必 s,s,
15、 t,t,使得使得RRs s,R,Rt t R Rt tR Rs s = R= Rt+s t+s 是传递的是传递的 t(R) t(R)是包含是包含R R的最小传递关系的最小传递关系 t(R) t(R) 由（由（1 1），（），（2 2）得）得 t(R) t(R) = = 闭包运算举例闭包运算举例题：题：设设A=a,b,c, RA=a,b,c, R是是A A上的二元关系，且给定上的二元关系，且给定R=, R=, 求求r(R),s(R),t(R)r(R),s(R),t(R)。解：解：r(R)r(R)= R I= R IA A = ,= , , , s(R)s(R)= R R= R Rc c = ,
16、= , t(R)t(R)=RR=RR2 2RR3 3 = RR = RR2 2RR3 3 （因为（因为R R4 4=R,R=R,R5 5=R=R2 2,R,R6 6=R=R3 3,),) = = , , , , , , 定理定理3-8.53-8.5 设设R R为为X X上二元关系，上二元关系， X X =n=n，那么，存，那么，存在一个正整数在一个正整数knkn，使得，使得 t(t()= R )= R R R2 2 R R3 3 . . R Rk k例：例：P123P123例题例题2 2求求R R+ +的算法的算法WarshallWarshall算法算法AM i=1AM i=1 对对i i列中
17、出现列中出现1 1的各行，分别被的各行，分别被或或上上i i行行 i=i+1 i=i+1 in in 结束结束Y例：例：P124P124例题例题3 3 P125P125例题例题4 4 设有一字母表设有一字母表V=A,B,C,D,e,d,fV=A,B,C,D,e,d,f并给定下面并给定下面六条规则：六条规则： A-Af, B-Dde, C-e, A-B, B-De, D-BfA-Af, B-Dde, C-e, A-B, B-De, D-Bf R R为定义在为定义在V V上的二元关系且上的二元关系且x xi iRxRxj j，即是从，即是从x xi i出出发用一条规则推出一串字符，使其第一个字符恰
18、为发用一条规则推出一串字符，使其第一个字符恰为x xj j 。说明每个字母连续应用上述规则可能推出的头。说明每个字母连续应用上述规则可能推出的头字符。字符。闭包运算的性质闭包运算的性质设设R R为集合为集合X X上的任一二元关系，那么上的任一二元关系，那么 a)rs(R)=sr(R)a)rs(R)=sr(R) 自反对称闭包等于对称自反闭包自反对称闭包等于对称自反闭包 b)tr(R)=rt(R)b)tr(R)=rt(R) 传递自反闭包等于自反传递闭包传递自反闭包等于自反传递闭包 c)ts(R)c)ts(R) st(R)st(R) 传递对称闭包包含对称传递闭包传递对称闭包包含对称传递闭包 证明证明
19、 rs(R)=sr(R) rs(R)=sr(R) 证：证： rs(R)= r(s(R) rs(R)= r(s(R) = r(RR = r(RRc c) ) = I = Ix xRRRRc c = I = Ix xRRRRc cIIx x = (I= (Ix xR)(RR)(Rc cIIx xc c) ) = (I = (Ix xR)R)(RI(RIx x) )c c = s(I = s(Ix xR)R) = sr(R) = sr(R)证明证明 rt(R)=tr(R)rt(R)=tr(R)证：证：rt(R) =rt(R) = r(RR r(RR2 2) = I = IX XRRRR2 2 tr(
20、R) =tr(R) = t( RI t( RIX X) ) = I = IX XR(IR(IX XR)R)2 2(I(IX XR)R)n n = I = IX XRRRR2 2RRn n rt(R)=tr(R) rt(R)=tr(R)注：以上证明引用了公式：（证明略）注：以上证明引用了公式：（证明略） ( RI( RIX X) )n n = I= IX XRRRR2 2RRn n证明证明st(R) st(R) ts(R)ts(R)证：证： 先证先证R R对称对称t( R )t( R )对称对称t t( R )( R )-1 -1 = (= (R R R R2 2 R R3 3 )-1-1= =
21、 R R-1-1 (R(R2 2) )-1-1 (R(R3 3) )-1-1 = = R R-1-1 (R(R-1-1) )2 2 (R(R-1-1) )3 3 ( (F(FG)G)-1-1=G=G-1-1F F-1-1，定理定理3-7.23-7.2 ) ) = R = R R R2 2 R R3 3 = t = t( R ) ( R ) t( R )t( R )对称对称. . 因为因为 R R s(R), s(R),故故 st( R ) st( R ) st(s( R st(s( R ) ) 而而st(s( R )= sts(R) = s(st(s( R )= sts(R) = s(t ts
22、( R )s( R ) = ts( R ) ) = ts( R ) st( R ) st( R ) ts( R ). ts( R ).注：注： st(R) st(R) ts(R)ts(R)未必成立。未必成立。反例：设反例：设R= , R= , 则则s(R)= , s(R)= , t(s(R)= , t(s(R)= , , , s(t(R)= s , s(t(R)= s , = = , , t(s(R) t(s(R)注意：先做传递，再做对称，有可能破坏传递性。注意：先做传递，再做对称，有可能破坏传递性。3-9 3-9 集合的划分和覆盖集合的划分和覆盖除了把两个集合相互比较外，还常把一个集合除了把
23、两个集合相互比较外，还常把一个集合分成若干子集讨论。分成若干子集讨论。定义定义3-9.1 3-9.1 设设A A为非空集，为非空集，S=SS=S1 1SSm m,S,Si i A A，S Si i (i=1m)(i=1m)且且S S1 1SS2 2.S.Sm m=A=A，称，称S S是是A A的覆盖的覆盖. .若再加若再加S Si iSSj j= = (i,j=1m,ij)(i,j=1m,ij)则称则称S S是是A A的划分的划分,m,m称为称为划分的秩划分的秩。集合的划分和覆盖举例集合的划分和覆盖举例例例例例1 1 1 1 设设A=1,2,3,4,5A=1,2,3,4,5，下面哪些是覆盖，哪
24、些是，下面哪些是覆盖，哪些是划分：划分： (1) X = 1,2,3,4,5(1) X = 1,2,3,4,5 (2) Y = 1,2,2,3,4,5 (2) Y = 1,2,2,3,4,5 (3) Z = 1,2,3,4 (3) Z = 1,2,3,4 (4) U = 1,2,3,4,5 (4) U = 1,2,3,4,5 (5) V = 1,2,3,4,5 (5) V = 1,2,3,4,5 U U称为称为A A的的最小划分最小划分，V V称为称为A A的的最大划分最大划分。交叉划分交叉划分定义定义3-9.2 3-9.2 若若S S1 1=A=A1 1AAm m,S,S2 2=B=B1 1
25、BBn n 是是A A的二个划的二个划分分, ,则则 S=A S=Ai iBBj j|A|Ai i S S1 1BBj j S S2 2 称为称为A A的交叉划分的交叉划分。定理定理3-9.1 3-9.1 设设 A A1 1,A,A2 2,A,Am m 与与BB1 1,B,B2 2,B,Bn n 为同为同一集合一集合A A的两个划分。则其交叉划分的两个划分。则其交叉划分A Ai iBBj j亦是原集亦是原集合的一种划分。合的一种划分。交叉划分举例交叉划分举例例：设设B B是所有生物的集合是所有生物的集合, , 可划分成可划分成A, P,A, P, 其其中中A A表表示示所所有有动动物物Anim
26、alAnimal的的集集合合, , P P表表示示所所有有植植物物PlantPlant的集合。的集合。B B也也可可划划分分成成 F, F, L,L,其其中中F F表表示示史史前前FirstFirst生生物物, ,L L表示史后表示史后LastLast生物。生物。它们的交叉划分为它们的交叉划分为 : : D = AF, AL, PF, PL, D = AF, AL, PF, PL, 其中其中AFAF是史前动物是史前动物, AL, AL是史后动物是史后动物, , PFPF是史前植物是史前植物, PL, PL是史后植物。是史后植物。加细加细定定义义3-9.33-9.3 设设S,SS,S是是集集合合
27、A A的的二二个个划划分分，若若S S的的每每一块均是一块均是SS中某块的子集，中某块的子集，S S是是SS的的加细。加细。 例例: :A=A=正整数集正整数集 S=1,3,5,7,2,4,6S=1,3,5,7,2,4,6 S=1,5,9,3,7 S=1,5,9,3,7，11,2,4,611,2,4,6则则 S S是是S S的细分的细分定定理理3-9.23-9.2 任任何何两两种种划划分分的的交交叉叉划划分分，都都是是原原来来各各划分的一种加细。划分的一种加细。练习：练习： 3-9 3-9（2 2）证明：证明： 1. 1. a a A A，a a与与a a在同一分块中，故必有在同一分块中，故必
28、有aRaaRa。故故R R是自反的。是自反的。 2. 2. 若若a a与与b b在同一分块中，在同一分块中，b b与与a a也必在同一分也必在同一分块中，即块中，即 aRb aRb bRa bRa，故，故R R是对称的。是对称的。 3. 3. 若若a a与与b b在同一分块中，在同一分块中，b b与与c c在同一分块中，在同一分块中， 根据划分的定义，根据划分的定义，b b属于且仅属于一个分块，故属于且仅属于一个分块，故a a与与c c必在同一分块中。必在同一分块中。 即即 aRb aRb bRc bRc aRc aRc，故，故R R是传递的。是传递的。3-10 3-10 等价关系与等价类等价
29、关系与等价类等价关系是一类重要的二元关系。等价关系是一类重要的二元关系。定义定义3-10.13-10.1 若集合若集合A A上的二元关系上的二元关系R R是是自反的自反的，对对称的称的和和传递的传递的，称，称R R是是等价关系等价关系。若。若R R是等价关系，是等价关系，aRbaRb，可读为，可读为“a“a等价于等价于b”b”。例如，例如， 数中的相等关系，是等价关系数中的相等关系，是等价关系 集合中的相等关系，是等价关系集合中的相等关系，是等价关系 命题演算中命题演算中关系，是等价关系关系，是等价关系 全域关系是等价关系，空集上任何关系是全域关系是等价关系，空集上任何关系是等价关系。等价关系
30、。等价关系举例等价关系举例例：例： 设设A=1,2,8A=1,2,8，如下定义，如下定义A A上的关系上的关系R R：R=xR=|xy|x，yAxy(mod 3)yAxy(mod 3)其中其中xy(mod 3)xy(mod 3)叫做叫做模模3 3同余同余，即，即x x除以除以3 3的余数与的余数与y y除以除以3 3的余数相等。不难验证的余数相等。不难验证R R为为A A上的等价关系，上的等价关系，因为因为 xA xA，有，有xx(mod 3)xx(mod 3)， x x，yAyA，若，若xy(mod 3)xy(mod 3)，则有，则有yx(mod 3)yx(mod 3)， x x，y y，z
31、AzA，若，若xy(mod 3)xy(mod 3)，yz(mod 3)yz(mod 3)，则有则有xz(mod 3)xz(mod 3)。该关系的关系图如下：该关系的关系图如下：等价关系举例（续）等价关系举例（续） 不难看出，上述关系图被分为三个互不相连通不难看出，上述关系图被分为三个互不相连通的部分。每部分中的数两两都有关系，不同部分中的部分。每部分中的数两两都有关系，不同部分中的数则没有关系。的数则没有关系。每一部分中的所有的顶点构成一每一部分中的所有的顶点构成一个等价类。个等价类。等价类等价类定义定义3-10.23-10.2 设设R R是是A A上的等价关系，上的等价关系，对对 a a A
32、 A，集合，集合aaR R=x|xRa=x|xRa称为称为a a关于关于R R的等价类的等价类，简记为，简记为aa，a a 称为等价类称为等价类aaR R的的表示元素表示元素。 从以上定义可以知道，从以上定义可以知道，a a的等价类是的等价类是A A中所有与中所有与a a等价的元素构成的集合。等价的元素构成的集合。上例中的等价类是：上例中的等价类是：1=4=7=1,4,71=4=7=1,4,72=5=8=2,5,82=5=8=2,5,83=6=3,63=6=3,6例：例：设设I I是整数集，是整数集，R R是模是模3 3同余关系，同余关系， 即即R=|xR=|x IyIy IxIx y(mod
33、3)y(mod3) 不难验证不难验证R R是等价关系，其等价类为是等价关系，其等价类为 0 0R R = -6,-3,0,3,6= -6,-3,0,3,6 1 1R R = -2,1,4= -2,1,4 2 2R R = -4,-1,2,5= -4,-1,2,5 等价类的每一元素均可作本等价类的表示元素。等价类的每一元素均可作本等价类的表示元素。定理定理3-10.13-10.1 设给定集合设给定集合A A上的等价关系上的等价关系R R，对于对于a,b a,b A A 有有 aRb iff a aRb iff aR R=b=bR R 证：证： a a aaR R=b=bR R 根据等价类定义根据
34、等价类定义 aRb aRb aRb aRb x x aaR R xRa xRa xRb xRb x x bbR R 由由x x的任意性知，的任意性知，aaR R=b=bR R商集商集定定义义3-10.33-10.3 集集合合A A上上的的等等价价关关系系R R，其其等等价价类类集集合合aaR R|a |a AA，称为，称为A A关于关于R R的商集的商集，记为记为A/RA/R。例例1 1： A=1,2,8 A=1,2,8， R= x R= |xy|x，yAxy(mod 3) yAxy(mod 3) 则则A/R=A/R= 1,4,7,2,5,8,3,6 1,4,7,2,5,8,3,6 例例2 2
35、： A A为正整数集合，为正整数集合，R R是模是模3 3同余关系，同余关系， 则则A/R=A/R= 0 0R R,1,1R R,2,2R R ， 其中其中 00R R = -6,-3,0,3,6= -6,-3,0,3,6 1 1R R = -2,1,4= -2,1,4 2 2R R = -4,-1,2,5= -4,-1,2,5显然：显然：商集是集合的集合。商集是集合的集合。商集的每个元素是等价关系的一个等价类。商集的每个元素是等价关系的一个等价类。等价类中的每个元素都是集合等价类中的每个元素都是集合A A上的元素。上的元素。同一等价类中的任意两个元素都具有关系同一等价类中的任意两个元素都具有
36、关系R R。商集举例商集举例例：设集合例：设集合S = a, b, c, d, e, f, gS = a, b, c, d, e, f, g，S S上的等上的等价关系价关系R R如下表所示，求商集如下表所示，求商集S/RS/R。abcdefgabcdefgS/RS/R = a, b, c, d, e, f, g = a, b, c, d, e, f, g 思考：思考：R=?根据等价类对集合进行划分根据等价类对集合进行划分定理定理3-10.2 3-10.2 集合集合A A上的等价关系上的等价关系R R决定了决定了A A的一个划的一个划分，即为商集分，即为商集A/RA/R。证明证明 A/R= a
37、A/R= aR R|a|a A A （1 1）根据等价类定义，根据等价类定义， a a A A，aaR R A A a aR R A A a a A A，aRa aRa a a aaR R A A aaR R a aR R=A =A A/RA/R是一个覆盖是一个覆盖 根据等价类对集合进行划分根据等价类对集合进行划分（2 2）证：需证证：需证 a,ba,b A A， 若若aaR R bbR R ， 则则 aaR RbbR R= = 。 反证法：若反证法：若aaR RbbR R 则则 c c aaR RbbR R cRa cRa 且且 cRb cRb R R是对称、传递的是对称、传递的 aRb a
38、Rb 则则 a aR R=b=bR R ，这与前提矛盾。，这与前提矛盾。 由（由（1 1），（），（2 2） 得得A/RA/R是一个划分。是一个划分。定理定理3-10.3 3-10.3 集合集合A A的任一的任一划分划分S S确定确定了了A A的一个的一个等价等价关系关系R R。证明证明 设设S=SS=S1 1，S S2 2，SSm m （构造性证明）（构造性证明）定义关系定义关系R: aRbR: aRb当且仅当当且仅当a,ba,b在在S S的同一块中，的同一块中， 现证现证R R是等价关系。是等价关系。 (1)(1) a a A A， a a与与a a在同一块中在同一块中 aRa aRa，自
39、反性成立自反性成立。 (2)(2) a,ba,b A A ，若，若aRbaRb，则，则a a与与b b在同一块中，则在同一块中，则b b与与a a也在同一块也在同一块 bRa bRa，即，即 aRb aRbbRa bRa 对称性成立对称性成立(3) (3) a,b,ca,b,c A A，若，若aRbaRb， bRc bRc，则，则a a与与b b在同一块，在同一块，b b与与c c在同一块在同一块 S Si iSSj j= = (i (i j) j) a a与与c c在同一块，即在同一块，即aRbbRcaRbbRcaRc aRc 传递性成立传递性成立综上所述，综上所述，R R是是A A的一个等
40、价关系，且的一个等价关系，且A/R=SA/R=S定理定理3-10.33-10.3举例举例例例： A=a,b,c,d,eA=a,b,c,d,e，S= S= a,b,c,d,e a,b,c,d,e ，求由求由S S确定的等价关系。确定的等价关系。 解：解：设设 R1=a,bR1=a,b a,b= , a,b= , R2=cR2=c c= c= R3=d,eR3=d,e d,e=d,e= , , 则则 R=R1R2R3 R=R1R2R3是由是由S S确定的等价关系。确定的等价关系。 若若S=a,b,c,d,eS=a,b,c,d,e，则由，则由S S确定的等价关确定的等价关系是什么？系是什么？定理定理
41、3-10.43-10.4 设设R1R1，R2R2是非空集合是非空集合A A上的等价关系，上的等价关系，则则R1=R2 R1=R2 A/R1=A/R2A/R1=A/R2。证明证明 ：若：若R1=R2 R1=R2 A/R1=a A/R1=aR1R1|a|a AA，A/R2=aA/R2=aR2R2|a|a A A 则则 x x aaR1R1 R1 R1 R2R2 x x aaR2R2 ， a aR1R1 a aR2R2 同理可证，同理可证， a aR2R2 a aR1R1 a aR1R1 = a = aR2R2 A/R1 = A/R2 A/R1 = A/R2 ： a a A A， a aR1R1 A
42、/R1 A/R1 A/R1= A/R2 A/R1= A/R2 必必 ccR2R2 A/R2A/R2，使，使 a aR1R1 =c =cR2R2 a,ba,b A A R1R1 a a aaR1R1bb aaR1R1 a a ccR2R2bb ccR2R2 R2R2 R1R1 R2 R2 同理可证：同理可证：R2R2 R1R1 R1 = R2 R1 = R2综上所述，综上所述，R1=R2 R1=R2 A/R1=A/R2A/R1=A/R2例：例：设设和和是非空集是非空集A A的划分的划分,R,R、RR是分别由是分别由、确定的等价关系，试证确定的等价关系，试证 细分细分 R R R R 证：证： R
43、R 则则a a、b b在在的同一块中，的同一块中， 细分细分 a a、b b在在的同一块的同一块 R R R R R R ：设：设 S Si i a a S Si i， 则则 S Si i=a=aRR=x|xRa=x|xRa x x S Si i xRa xRaxRaxRax x aaR R aaRR aaR R 由由 S Si i的任意性，知的任意性，知 细分细分 细分细分 R R R R加细（细分）图解加细（细分）图解3-11 3-11 相容关系相容关系定义定义3-11.13-11.1 设设R R是集合是集合A A上的二元关系，若上的二元关系，若R R是自反是自反的和对称的，称的和对称的，
44、称R R是是相容关系相容关系。例：例：所有等价关系是相容关系；所有等价关系是相容关系； 在一群人的集合中在一群人的集合中, , 朋友关系也是相容关系。朋友关系也是相容关系。相容关系的表示方法相容关系的表示方法 因为相容关系是自反和对称的因为相容关系是自反和对称的, , 其关系矩阵是其关系矩阵是对称的且主对角线元素全为对称的且主对角线元素全为1,1, 因此我们可仅用下因此我们可仅用下三角矩阵三角矩阵T T来表示和存储就够了来表示和存储就够了, , 即关系矩阵可以即关系矩阵可以简化为简化为“阶梯形阶梯形”。 相容关系的关系图可简记为：相容关系的关系图可简记为： 用无向边代替用无向边代替二有向边二有
45、向边 自回路省略自回路省略相容关系的表示方法相容关系的表示方法(P135(P135例题例题) )1 11 11 10 0001 11 11 11 11 10 01 11 11 11 100011 11100101 11 1000000 01 1x1x6x4x3x2x5相容关系相容关系r r的矩阵及图形表示的矩阵及图形表示定义定义3-11.23-11.2 设设R R是集合是集合A A上的相容关系上的相容关系, , 若若C C A, A, 若任意若任意a,ba,b C, C, 有有aRb,aRb, 则称则称C C是由是由R R产生的产生的相容类。相容类。例：上例相容关系例：上例相容关系r r产生的
46、相容类。产生的相容类。最大相容类最大相容类定义定义3-11.33-11.3 设设R R为定义在集合为定义在集合A A上的相容关系，如上的相容关系，如果不能真包含在任何其他相容类中的相容类，称作果不能真包含在任何其他相容类中的相容类，称作最大相容类最大相容类，记为记为C CR R。例：例：P137P137例题例题1 1a3a4a2a5a7a6a1相容关系的确定相容关系的确定 利用相容关系的关系图来确定相容类和最大相利用相容关系的关系图来确定相容类和最大相容类是方便的。容类是方便的。 极大完全子图的顶点集合就是最大相容类。极大完全子图的顶点集合就是最大相容类。 所谓极大完全子图是指每对顶点都有边相
47、连的所谓极大完全子图是指每对顶点都有边相连的多边形多边形, ,而最大相容类外的任何顶点不可能与类内而最大相容类外的任何顶点不可能与类内的所有顶点相连。的所有顶点相连。 另外另外孤立顶点孤立顶点, , 以及不在极大完全子图以及不在极大完全子图两个顶两个顶点及其连线点及其连线, , 也是最大相容类。也是最大相容类。例例 设给定的相容关系图表示成下图设给定的相容关系图表示成下图, , 写出所有的写出所有的最大相容类。最大相容类。解解 最大相容类：最大相容类：h, a, b, d, e, f, h, a, b, d, e, f, b, c, d, f, g b, c, d, f, g。完全覆盖完全覆盖
48、定义定义3-11.43-11.4 设设R R为定义在集合为定义在集合A A上的相容关系，其最上的相容关系，其最大相容类的集合称作集合大相容类的集合称作集合A A的的完全覆盖完全覆盖，记为记为C CR R(A)(A)。例例1 1：123456A A的完全覆盖是：的完全覆盖是： 1 1，2 2，3 3，44，55，66，55，22，66，333-12 3-12 序关系序关系定义定义3-12.1 3-12.1 若集合若集合A A上的二元关系上的二元关系R R是是自反自反的、的、反反对称对称的和的和传递传递的，则称的，则称R R是是A A的的偏序关系偏序关系，记作记作 。设设 为偏序关系，如果为偏序关
49、系，如果 ，则记作，则记作x yx y，读作读作“小于或等于小于或等于”。序偶序偶称为称为偏序集合偏序集合。 注意这里的注意这里的“小于或等于小于或等于”不是指数的大小，不是指数的大小，而是在偏序关系中的顺序性。而是在偏序关系中的顺序性。x“x“小于或等于小于或等于”y”y的的含义是：依照这个序，含义是：依照这个序，x x排在排在y y的前边或者的前边或者x x就是就是y y。根据不同偏序的定义，对序有着不同的解释。根据不同偏序的定义，对序有着不同的解释。例如例如整除关系是偏序关系，整除关系是偏序关系，3 63 6的含义是的含义是3 3整除整除6 6。大于。大于或等于关系也是偏序关系，针对这个
50、关系写或等于关系也是偏序关系，针对这个关系写5 45 4是是说大于或等于说大于或等于4,4,关系中关系中5 5排在排在4 4的前边，也就是的前边，也就是5 5比比4 4大。大。盖住盖住定义定义3-12.23-12.2 在偏序集在偏序集A 中，如果中，如果x,yx,y A A ， x yx y， x x y y，且没有其他元素，且没有其他元素z z满足满足x zx z、z yz y，则称元素，则称元素y y盖住盖住元素元素x x。并且把所有具备盖住。并且把所有具备盖住性质的续偶集合记作性质的续偶集合记作COV ACOV A， COV A=|COV A=|y y盖住盖住x x 例：例：A A为正整
51、数为正整数m m1212的因子的集合，并设的因子的集合，并设 为整除为整除关系，求关系，求COV ACOV A。(P140)(P140)哈斯图（偏序集合图）哈斯图（偏序集合图） 对于给定的偏序集对于给定的偏序集A ，它的盖住关系是，它的盖住关系是唯一的，所以唯一的，所以可以用哈斯图表示偏序集合图可以用哈斯图表示偏序集合图。哈斯图作图规则：哈斯图作图规则： 用小圆圈代表元素。用小圆圈代表元素。 如果如果 x yx y，且且x x y y，则将代表则将代表y y的小圆圈画的小圆圈画在代表在代表x x的小圆圈之上。的小圆圈之上。 如果如果 COV A,COV A,则在则在x x与与y y之间用直线连
52、之间用直线连接。接。哈斯图举例哈斯图举例例：画出偏序集例：画出偏序集 1,2,3,4,5,6,7,8,9 的哈斯图。的哈斯图。哈斯图举例（续）哈斯图举例（续）例：例：A=a,b,cA=a,b,c， 画出画出 (A), 的哈斯图。的哈斯图。abca,ba,cb,ca,b,c哈斯图举例（续）哈斯图举例（续）例：已知偏序集例：已知偏序集的哈斯图如图所示，试求出的哈斯图如图所示，试求出集合集合A A和关系和关系R R的表达式。的表达式。解：解：A=a,b,c,d,e,f,g,h A=a,b,c,d,e,f,g,h R=, R=, , ,IIA A abcdefhg偏序集中的特殊元素偏序集中的特殊元素定
53、义定义3-12.5,3-12.63-12.5,3-12.6 设设A 为偏序集，为偏序集，B B是是A A的子的子集，集，yByB。 若若 x(xByx(xBy x)x)成立，则称成立，则称y y为为B B的最小元的最小元。 若若 x(xBxx(xBx y) y)成立，则称成立，则称y y为为B B的最大元。的最大元。 若若b b B B, ,且且B B中不存在任何元素中不存在任何元素x,x,使使b b x x且且b x b x 称称b b是是B B的极大元的极大元。 若若b b B B, ,且且B B中不存在任何元素中不存在任何元素x,x,使使b b x x且且x b x b 称称b b是是B
54、 B的极小元的极小元。例：设偏序集例：设偏序集A 如图所示，求如图所示，求A A的极小元，最的极小元，最小元，极大元，最大元。小元，极大元，最大元。 abcdefhg解解: :极小元：极小元：a,b,c,ga,b,c,g。 极大元：极大元：a,f,ha,f,h。 没有最小元与最大元。没有最小元与最大元。 由这个例子可以知道，由这个例子可以知道，哈斯图中的孤立顶点既是极哈斯图中的孤立顶点既是极小元也是极大元小元也是极大元。bae edc解：解：A A不存在最大、最小元；极大元素为不存在最大、最小元；极大元素为d,e,d,e,极极小元素为小元素为a,ba,b； B B的最大元素为的最大元素为c c
55、，没有最小元素；极大元素，没有最小元素；极大元素为为c, c, 极小元素为极小元素为a,ba,b。例：设例：设A=a,b,c,d,eA=a,b,c,d,e、B=a,b,cB=a,b,c，则各自的最大，则各自的最大最小元素、极大极小元素是最小元素、极大极小元素是哪些？哪些？ 最小元是最小元是B B中最小的元素中最小的元素，它与，它与B B中其它元素都中其它元素都可比；而极小元不一定与可比；而极小元不一定与B B中元素可比，中元素可比，只要没有只要没有比它小的元素，它就是极小元比它小的元素，它就是极小元。对于有穷集。对于有穷集B B，极极小元一定存在，但最小元不一定存在小元一定存在，但最小元不一定
56、存在。最小元如果。最小元如果存在，一定是唯一的，但极小元可能有多个。如果存在，一定是唯一的，但极小元可能有多个。如果B B中只有一个极小元，则它一定是中只有一个极小元，则它一定是B B的最小元。如果的最小元。如果B B中存在最小元，则它一定是中存在最小元，则它一定是B B的唯一极小元。类似的唯一极小元。类似的，极大元与最大元也有这种区别。的，极大元与最大元也有这种区别。 定理定理定理定理3-12.13-12.13-12.13-12.1 设设是一偏序集合，且是一偏序集合，且B B A A，若，若B B有最大（最小）元，则是唯一的。有最大（最小）元，则是唯一的。 证：证： 设设a,ba,b都是都是
57、B B的最大元素，的最大元素， 那么那么a b,b aa b,b a，从偏序关系的反对称性，从偏序关系的反对称性，得得a=ba=b。 最小元证明情况与此类似。最小元证明情况与此类似。上界、下界上界、下界定义定义定义定义3-12.73-12.73-12.73-12.7，3-12.8 3-12.8 3-12.8 3-12.8 设设A 为偏序集，为偏序集，B BA A，yAyA。（1 1） 若若 x(xBx y)x(xBx y)成立，则称成立，则称y y为为B B的的上界上界。 （2 2） 若若 x(xBy x)x(xBy x)成立，则称成立，则称y y为为B B的的下界下界。 （3 3） 令令C
58、Cy|yy|y为为B B的上界的上界 ，则称，则称C C的最小元的最小元为为B B的最小上界或上确界的最小上界或上确界。 （4 4） 令令D Dy|yy|y为为B B的下界的下界 ，则称，则称D D的最大元的最大元为为B B的最大下界或下确界的最大下界或下确界。 设设A, 为有序集，为有序集，B B A A。 的哈斯图如下所示。的哈斯图如下所示。 A= a A= a，b b，c c，d d，e e，f f，g g，h h，i i，j j，k ,k , B B=a=a，b b，c c，d d，e e，f f，g g BB=h=h，i i，j j，k k jkhifgedcbajkhifgedcb
59、aBB B的上界的上界BB的的下下下下界界B 由定义可知，由定义可知，B B的最小元一定是的最小元一定是B B的下界，同时的下界，同时也是也是B B的最大下界的最大下界。同样的，。同样的，B B的最大元一定是的最大元一定是B B的的上界，同时也是上界，同时也是B B的最小上界的最小上界。但。但反过来不一定正反过来不一定正确确，B B的下界不一定是的下界不一定是B B的最小元，因为它可能不是的最小元，因为它可能不是B B中的元素。同样的，中的元素。同样的，B B的上界也不一定是的上界也不一定是B B的最大的最大元。元。 序关系（注意）序关系（注意） （1 1）B B的最大（小）元素和极大（小）元
60、素必须的最大（小）元素和极大（小）元素必须是子集是子集B B的元素，而的元素，而B B的上界（下界）和最小上界的上界（下界）和最小上界（最大下界）可以是也可以不是（最大下界）可以是也可以不是B B的元素。的元素。 （2 2）上界和下界可以存在也可以不存在，可以唯上界和下界可以存在也可以不存在，可以唯一也可以不唯一。一也可以不唯一。 （3 3）极大元素和极小元素可以唯一也可以不唯一。极大元素和极小元素可以唯一也可以不唯一。 （4 4）最大元素、最小元素可以存在也可以不存在，最大元素、最小元素可以存在也可以不存在，但若存在则唯一。但若存在则唯一。 （5 5）对于非空有限偏序集合，其极大元素和极小对
61、于非空有限偏序集合，其极大元素和极小元素总是存在。元素总是存在。序关系（说明）序关系（说明）1 1、设、设是偏序集合，是偏序集合，B B是是A A的子集，的子集，（a a）如如果果b b是是B B的的最最大大元元素素，那那么么b b是是B B的的极极大大元元素素，且极大元素唯一。且极大元素唯一。（b b）如果）如果b b是是B B的最大元素，那么的最大元素，那么b b是是B B的最小上界。的最小上界。（c c）如果）如果b b是是B B的上界且的上界且b b B,B,则则b b是是B B的最大元素。的最大元素。（对对最最小小元元素素、极极小小元元素素和和最最大大下下界界也也存存在在类类似似的的
62、关系）关系）2 2、对、对来说，它的逆来说，它的逆也是一个偏序集也是一个偏序集合，偏序合，偏序 的的P P中的最大元素、极大元素、上中的最大元素、极大元素、上界、最小上界，是界、最小上界，是 P P中的最小元素、极小中的最小元素、极小元素、下界、最大下界，反之亦然。元素、下界、最大下界，反之亦然。拟序拟序定义：定义：若集合若集合A A上的二元关系上的二元关系R R是反自反的、传递的，是反自反的、传递的，则称则称R R是是A A的的拟序关系拟序关系，序偶，序偶称为拟序集合。称为拟序集合。全序关系全序关系 在偏序集合在偏序集合中，中， B B A A，若每一，若每一a a、b b B B，都有，都
63、有a ba b或或b a,b a,称称B B为为链（即链（即B B中任意两元中任意两元素都有关系）素都有关系）；若；若B B中任意两元素都是无关的，则中任意两元素都是无关的，则称称 B 是是反链。反链。定义定义3-12.4 3-12.4 在偏序集在偏序集中中，若是链，则称，若是链，则称为为全序全序( (线序线序) )集合集合， 称为称为全序全序( (线序线序) )关系。关系。全序（线序）举例全序（线序）举例例：例： 是一全序集合；是一全序集合； 1,2,3,6, 不是一个全序集合；不是一个全序集合； P= P=,a,a,b,a,b,c,a,a,b,a,b,c上的包含关系上的包含关系 ，P, 是
64、全序集。其哈斯图如下：是全序集。其哈斯图如下：注：注： 全序集合的哈斯图是一竖立的结点序列，每全序集合的哈斯图是一竖立的结点序列，每相邻的结点用一条弧连接。相邻的结点用一条弧连接。aa,b,ca,b,ca,b良序良序定义定义3-12.93-12.9 任一任一偏序集合偏序集合，假如它的每个非空子，假如它的每个非空子集，都有最小元素，则这种偏序集合是集，都有最小元素，则这种偏序集合是良序集合。良序集合。例：例：n=1,2,3,n,n=1,2,3,n,对于小于等于关系来说是对于小于等于关系来说是良序集合。但良序集合。但I, 不是良序集合。不是良序集合。定理定理3-12.23-12.2 每一个良序集合
65、，一定是全序集合。每一个良序集合，一定是全序集合。证明：证明：设设A 是良序集，那么对任意两个元素是良序集，那么对任意两个元素x,y x,y A A可构成子集可构成子集x,yx,y ，必存在最小元素，这，必存在最小元素，这个最小元素不是个最小元素不是x x就是就是y y，因此一定有，因此一定有x yx y或或 y x y x 。定理定理3-12.33-12.3 每一个有限的全序集合，一定是良每一个有限的全序集合，一定是良序集合。序集合。证明：证明：设设A=aA=a1 1,a,a2 2,a,an n ，令，令A 是全序集，现是全序集，现假定假定A 不是良序集合，那么必存在一个非空集不是良序集合，那么必存在一个非空集合合B B A A，在，在B B中不存在最小元素，由于中不存在最小元素，由于B B是一个有是一个有限集合，故一定可以找到两个元素限集合，故一定可以找到两个元素x x与与y y是无关的，是无关的，由于由于 是全序集，是全序集，x,yAx,yA，所以，所以x,yx,y必有关系，必有关系，得出矛盾。故得出矛盾。故A 是良序集合。是良序集合。上述结论对于无限的全序集合不一定成立。上述结论对于无限的全序集合不一定成立。
