数学关系性质离散数学学习教案.pptx

《数学关系性质离散数学学习教案.pptx》由会员分享，可在线阅读，更多相关《数学关系性质离散数学学习教案.pptx（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数学数学(shxu)关系性质离散数学关系性质离散数学(shxu)第一页，共64页。2/7/2023 2:47 AM 2第 七 章 二 元 关 系7.1有序对与笛卡儿积7.2二元关系7.3关系的运算7.4关系的性质(xngzh)7.5关系的闭包7.6等价关系与划分7.7偏序关系第1页/共64页第二页，共64页。2/7/2023 2:47 AM 3定义7.1由两个元素x和y（允许(ynx)xy）按一定顺序排列成的二元组叫做一个有序对，记为。注：有序对的性质：1.当xy时，。2.的充分必要条件是x=u且y=v。7.1 7.1 有序对与笛卡尔积有序对与笛卡尔积有序对与笛卡尔积有序对与笛卡尔积

2、定义7.2 设A,B是集合。由A中元作为(zuwi)第一元素，B中元作为(zuwi)第二元素组成的所有有序对的集合，称为集合A与B的笛卡尔积，记为AB。即 AB|xAyB。第2页/共64页第三页，共64页。2/7/2023 2:47 AM 4注：笛卡尔积的性质(xngzh)：1.A=,A=;2.AB BA,除非 A=或 B=或 A=B;3.(AB)C A(BC),除非 A=或 B=或C=.4.A(BC)=(AB)(AC);(BC)A=(BA)(CA);A(BC)=(AB)(AC);(BC)A=(BA)(CA);5.(A C)(B D)(AB)(CD).7.1有序对与笛卡尔积有序对与笛卡尔积第3

3、页/共64页第四页，共64页。2/7/2023 2:47 AM 5例 证明(zhngmng)A(BC)=(AB)(AC)。证：任取，A(BC)xA y(BC)xA (yB yC)(xA yB)(xA yC)(AB)(AC)(AB)(AC)A(BC)=(AB)(AC)例7.2 设 A=1,2,求 P(A)A。解：P(A)A =,1,2,1,21,2 =,7.17.1有序对与笛卡尔积 第4页/共64页第五页，共64页。2/7/2023 2:47 AM 6例7.3 设A,B,C,D为任意集合，判断下列命题是否(sh fu)为真。（1）ABAC B=C（2）A (BC)=(A B)(A C)（3）(A

4、=B)(C=D)AC=BD（4）存在集合A,使 AAA7.1有序对与笛卡尔积有序对与笛卡尔积解:(1)不一定(ydng)为真，(3)为真。(4)为真。当A=,B=1,C=2,3时，便不真。(2)不一定(ydng)为真，当A=B=1,C=2时，A(BC)=1=1,而(AB)(AC)=1=.等量代入。当A=时,使AAA.第5页/共64页第六页，共64页。2/7/2023 2:47 AM 7一、基本概念定义7.3 如果一个非空集合的元素都是有序对，则称该集合为一个二元关系。特别地，空集也是一个二元关系。注：对一个二元关系R，如果R,则记为xRy；如果R，则记为xRy。定义7.4 设A,B为集合，AB

5、的任何子集(z j)所定义的二元关系称为从A到B的二元关系。特别地，当A=B时，称为A上的二元关系。定义7.5 对任何集合A，(1)称空集为 A上的空关系。(2)A上的全域关系EA=xA yA=AA(3)A上的恒等关系IA=xA.7.27.2二元关系二元关系第6页/共64页第七页，共64页。2/7/2023 2:47 AM 8二.关系的表达方式1.集合表达式：列出关系中的所有有序对。例7.4 设A=1,2,3,4,试列出下列(xili)关系R的元素。(1)R=x是y的倍数(2)R=(xy)2A(3)R=x/y是素数(4)R=xy(5)R=(x,yA)(xy)解:(1)R=,(2)R=,(3)R

6、=,(4)R=EA-IA=,(5)R=,7.27.2二元关系二元关系第7页/共64页第八页，共64页。2/7/2023 2:47 AM 92.关系(gun x)矩阵法：设A=x1,x2,xn,R 是 A 上的关系(gun x)。令：则矩阵(j zhn)称为(chn wi)R 的关系矩阵。7.27.2二元关系二元关系第8页/共64页第九页，共64页。2/7/2023 2:47 AM 10例 设A=1,2,3,4,R=,则 R的关系(gun x)矩阵为7.27.2二元关系二元关系第9页/共64页第十页，共64页。2/7/2023 2:47 AM 113.关系图法(tf)设A=x1,x2,xn,R是

7、A上的关系。以A的元素作为顶点，当且仅当xiRxj时，xi向xj连一条有向边，所得的图形称为R的关系图，记为GR。例7.6设A=1,2,3,4,R=,则R的关系图为12437.27.2二元关系二元关系第10页/共64页第十一页，共64页。2/7/2023 2:47 AM 12一、基本概念定义7.6 设R是二元关系。定义(1)R的定义域:domR=x|y(R),即R中所有有序对的第一元素(yun s)构成的集合。(2)R的值域，ranR=y|x(R),即R中所有有序对的第二元素(yun s)构成的集合。(3)R的域:fld R=dom Rran R。例7.5 R=,则 domR=1,2,4，ra

8、nR=2,3,4,fld R=1,2,3,4。7.3 关系(gun x)的运算第11页/共64页第十二页，共64页。2/7/2023 2:47 AM 13定义7.7 设R为二元关系，称 R-1=|R为R的逆关系。定义7.8 设F,G为二元关系。称为 G 对 F 的右复合(fh)(或 F 对 G 的左复合(fh)。例如,F=,G=,则 F-1=,7.3 关系(gun x)的运算第12页/共64页第十三页，共64页。2/7/2023 2:47 AM 14定义(dngy)7.9设R是二元关系,A是集合(通常AdomR)7.3 关系(gun x)的运算例7.7设R为,则(1)R在A上的限制:RA=|x

9、RyxAR1=2,3,R=,R2,3=2,4。R1=,R=,R2,3=,，(2)A在R下的像:RA=ran(RA)第13页/共64页第十四页，共64页。2/7/2023 2:47 AM 15定义(dngy)7.10 设R是A上的关系,n为自然数,则R的n次幂定义(dngy)为:(1)R0=|xA=IA;(2)注:1.对A上的任何关系R,都有 R0=IA,R1=R。2.Rn的求法:除了根据定义(dngy)按关系的复合来求之外,还可以用矩阵法和关系图法。7.3 关系(gun x)的运算第14页/共64页第十五页，共64页。2/7/2023 2:47 AM 16例7.8 设A=a,b,c,d,R=,

10、求R的各次幂,分别用矩阵和关系(gun x)图表示.解:R的关系(gun x)矩阵:R2,R3,R4 的关系(gun x)矩阵分别是：第15页/共64页第十六页，共64页。2/7/2023 2:47 AM 17可见(kjin)M4=M2。故R2=R4=R6=;R3=R5=R7=。第16页/共64页第十七页，共64页。2/7/2023 2:47 AM 18此外,R0=IA的关系矩阵为:用关系图法(t f)得到 R0,R1,R2,的关系图如下:dabcR0R1abcdR2=R4=bcdaabcdR3=R5=第17页/共64页第十八页，共64页。2/7/2023 2:47 AM 19关系是集合,故有

11、关集合的所有运算(yn sun)性质对关系都成立。定理7.1 设F是关系,则(F-1)-1=F;(2)dom F-1=ran F,ran F-1=dom F。证:(1)(F-1)-1 F-1 F (F-1)-1=F。(2)xdom F-1 y(F-1)y(F)xran F dom F-1=ran F。同理可证 ran F-1=dom F。二.关系的运算(yn sun)性质第18页/共64页第十九页，共64页。2/7/2023 2:47 AM 20定理(dngl)7.2 设F,G,H是关系，则(1)(FG)H=F(GH);(2)(FG)1=G1F1.证:(1)(FG)H)t(FG)H)t(s(F

12、G)H)ts(FG)H)s(Ft(GH)s(F(GH)F(GH)(FG)H=F(GH)(2)(FG)1 FG t(FG)t(G1F1)(G1F1)(FG)1=G1F1第19页/共64页第二十页，共64页。2/7/2023 2:47 AM 21定理(dngl)7.3 设R是A上的关系,则 RIA=IAR=R.证:(RIA)t(RIA)t(Rt=y)RRRyARIA(RIA)RIA=R同理可证 IAR=R第20页/共64页第二十一页，共64页。2/7/2023 2:47 AM 22定理(dngl)7.4 设F,G,H是关系,则(1)F(GH)=FGFH;(2)(GH)F=GFHF;(3)F(GH)

13、FGFH;(4)(GH)F GFHF.证:以(3)为例.F(GH)t(F(GH)t(FGH)t(FG)(FH)t(FG)t(FH)FGFH FGFH F(GH)=FGFH第21页/共64页第二十二页，共64页。2/7/2023 2:47 AM 23定理(dngl)7.5设F为关系,A,B为集合,则(1)F(AB)=FAFB;(2)FAB=FAFB(3)F(AB)=FAFB;(4)FABFAFB(1)F(AB)F(AB)=FAFB证:以(1)和(4)为例F(xAxB)(FxA)(FxB)FAFB(FAFB)Fx(AB)第22页/共64页第二十三页，共64页。2/7/2023 2:47 AM 24

14、(4)yFABx(F(xAB)x(FxAxB)x(FxA)(FxB)x(FxA)x(FxB)yFAyFBy(FAFB)FAB=FAFB第23页/共64页第二十四页，共64页。2/7/2023 2:47 AM 25定理7.7设R为A上的关系,m,nN,则(1)RmRn=Rm+n;(2)(Rm)n=Rmn证:(1)对于任意取定的mN，关于(guny)n作数学归纳法。当n=0时，RmR0=RmIA=Rm=Rm+0假设RmRn=Rm+n,则RmRn+1=Rm(RnR)=(RmRn)R=Rm+nR1=Rm+n+1由归纳法原理,知命题成立。(2)对任意取定的mN,关于(guny)n作数学归纳法。当n=0时

15、,(Rm)0=IA=R0=Rm0假设(Rm)n=Rmn,则(Rm)n+1=(Rm)nRm=RmnRm=Rmn+m=Rm(n+1)由归纳法原理,知命题成立。定理7.6 设A是n元集合,R为A上的关系,则存在(cnzi)自然数s和t,使得Rs=Rt。第24页/共64页第二十五页，共64页。2/7/2023 2:47 AM 26定理7.8设R为A上的关系,若存在自然数s,t(st),使得Rs=Rt,则(1)kN都有Rs+k=Rt+k(2)k,iN都有Rs+kp+i=Rs+i,其中p=ts(3)令S=R0,R1,Rt1,则对qN都有RqS。证明：见教材P112。注:定理7.6和定理7.8的(3)表明,

16、有限集合(jh)A上的二元关系只有有限多个,而且一个关系的幂序列R0,R1R2,是一个周期性变化的序列。例7.9见教材P113。第25页/共64页第二十六页，共64页。2/7/2023 2:47 AM 27一、关系的五种(w zhn)性质 关系的性质主要有5种:自反性,反自反性,对称性,反对称性和传递性。定义7.11 设R是A上的关系,若x(xAR),则称 R在A上是自反的(Reflexive);若x(xAR),则称R在A上是反自反的(antiReflexive).7.4 关系(gun x)的性质第26页/共64页第二十七页，共64页。2/7/2023 2:47 AM 28例7.10(1)A上

17、的全域关系EA、恒等关系IA都是A上的自反关系.(2)小于等于关系 LA=x,yAxy,AR.整除关系 DA=x,yAx整除y,AZ*.包含关系 R=x,yAxy,A 是集合(jh)族。都是自反关系.(3)小于关系 SA=x,yAxy,AR.真包含关系 R=x,yAxy,A是集合(jh)族。都是反自反关系.(4)设 A=1,2,3,R1=,是A上的自反关系;R2=是A上的反自反关系;R3=,既不是自反的,也不是反自反的.第27页/共64页第二十八页，共64页。2/7/2023 2:47 AM 29定义7.12 设R是A上的关系,若xy(x,yAR(y,x)R),则称 R是A上的对称关系(Sym

18、metric);若 xy(x,yAR(y,x)Rx=y),则称 R 是A上的反对称关系(antiSymmetric).例7.11(1)A上的全域关系EA,恒等关系IA 及空关系都是A上的对称 关系;IA 和同时(tngsh)也是 A上的反对称关系.(2)设A=1,2,3,则 R1=,既是A上的对称关系,也是A上的反对称关系;R2=,是对称的,但不是反对称的;R3=,是反对称的,但不是对称的;R4=,既不是对称的也不是反对称的。第28页/共64页第二十九页，共64页。2/7/2023 2:47 AM 30定义7.13 设R是A上的关系,若xyz(x,y,zARRR),则称R是A上的传递关系。例7

19、.12(1)A上的全域关系EA,恒等关系IA和空关系都是传递关系。(2)小于等于(dngy)关系,整除关系和包含关系是传递关系,小于关系和真包含关系也是传递关系。(3)设A=1,2,3,则R1=,和 R2=都是A上的传递关系,但R3=,不是A上的传递关系。第29页/共64页第三十页，共64页。2/7/2023 2:47 AM 31定理7.9 设R为A上的关系,则(1)R在A上自反当且仅当 IA R(2)R在A上反自反当且仅当 RIA=(3)R在A上对称(duchn)当且仅当 R=R-1(4)R在A上反对称(duchn)当且仅当 RR-1IA(5)R在A上传递当且仅当 R RR证:(1)必要性:

20、因 R 在A上自反,故 IAx,yAx=yR，从而IAR。充分性:因xAIAR,故R在A上自反。二、各种性质的充分(chngfn)必要条件第30页/共64页第三十一页，共64页。2/7/2023 2:47 AM 32(2)必要性(用反证法):假设RIA,则必存在RIA,即R且IA。由IA知x=y.从而(cngr)R.这与R在A上是反自反矛盾。充分性:xAIAR(因RIA=),这说明R在A上是反自反的。(3)必要性:R是A上的对称关系,RRR-1,故R=R-1。充分性:由于R=R-1,RR-1R.故R在A上是对称的。第31页/共64页第三十二页，共64页。2/7/2023 2:47 AM 33(

21、4)必要性:因R在A上是反对(fndu)称的,故RR1RR1RRx=yIA.RR1IA充分性:因RR1IA,故RRRR1RR1IAx=y.从而R在A上是反对(fndu)称的.第32页/共64页第三十三页，共64页。2/7/2023 2:47 AM 34(5)必要性:因R在A上是传递(chund)的,故RRt(RR)R因此RRR充分性:因RRR,故RRRRRR在A上是传递(chund)的。第33页/共64页第三十四页，共64页。2/7/2023 2:47 AM 35 例7.13 设 A 是集合,R1 和 R2 是 A 上的关系,证明(1)若 R1 和 R2 都是自反的和对称的,则 R1R2 也是

22、自反的和对称的.(2)若 R1 和 R2 是传递的,则 R1R2 也是传递的.证:(1)因 R1 和 R2 是 A 上的自反关系,故 IA R1,IA R2,从而 IA R1R2.由定理(dngl)7.9,R1R2 在A上是自反的.由 R1 和 R2 的对称性,有 R1=R11 和 R2=R2-1,因此 (R1R2)-1=R1-1R2-1=R1R2 (见习题7.20).由定理(dngl)7.9,R1R2 在A上是对称的.(2)由 R1 和 R2 的传递性,有 R1 R1 R1 和 R2 R2 R2.由定理(dngl)7.4,(R1R2)(R1R2)(R1 R1)(R1 R2)(R2 R1)(R

23、2 R2)(R1R2)(R1 R2)(R2 R1)R1R2由定理(dngl)7.9,R1R2 在 A 上是传递的.第34页/共64页第三十五页，共64页。2/7/2023 2:47 AM 36 性质表示性质表示自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性集合表达式集合表达式IA RRIA=R=R1 RR1 IAR R R关系矩阵关系矩阵主主对对角角线线元元素素全是全是1 1主主对对角角线线元元素素全是全是0 0矩阵是对称矩阵。矩阵是对称矩阵。若若rij=1,且且ij,则则 rji=0.对对M2中中1所所在在的的位位置置,M中中相相应应的的位位置都是置都是1。关系图关系图

24、每每个个顶顶点点都都有有环环每每个个顶顶点点都都没没有环有环如如果果两两个个顶顶点点之之间间有有边边,则则必必是是一一对方向相反的边。对方向相反的边。每每对对顶顶点点之之间间至至多多有有一一条条边边,(,(不不会会有有双双向向边边)。如如果果顶顶点点xi到到xj有有边边,xj到到 xk有有边边,则则从从xi到到 xk也有边。也有边。三.各种性质(xngzh)在关系矩阵和关系图中的体现 第35页/共64页第三十六页，共64页。2/7/2023 2:47 AM 37例7.14 判断图7.3中关系的性质解:(a)该关系是对称的.其它性质均不具备(jbi)。(b)该关系是反自反的,反对称的,同时也是传

25、递的。(c)该关系是自反的,反对称的,但不是传递的。(a)(b)(c)321231231第36页/共64页第三十七页，共64页。2/7/2023 2:47 AM 38四.各种性质与运算(yn sun)之间关系 性质性质 运算运算 自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性R1R1R2R1R2 R1 R2 R1 R2 第37页/共64页第三十八页，共64页。2/7/2023 2:47 AM 39一.闭包的定义定义7.14 设R是非空集合A上的关系,R的自反闭包(对称(duchn)闭包、传递闭包)是 A上的关系 R，它满足：(1)R 是自反的(对称(duchn)的、传递的

26、)；(2)R R;(3)对A上任何包含 R 的自反关系(对称(duchn)关系、传递关系)R 都有R R .注：R的自反闭包记为 r(R)，对称(duchn)闭包记为 s(R)，传递闭包记 为 t(R)。7.5 7.5 7.5 7.5 关系关系关系关系(gun x)(gun x)(gun x)(gun x)的闭包的闭包的闭包的闭包Reflexive,Symmetric,Transtive:r(R),s(R),t(R).第38页/共64页第三十九页，共64页。2/7/2023 2:47 AM 40二二二二.闭包的构造方法闭包的构造方法定理7.10设R是A上的关系，则(1)r(R)=RR0;(2)

27、s(R)=RR-1;(3)t(R)=RR2R3.证明：(1)由IA=R0RR0知，RR0是自反的，且RRR0。设R是A上包含R的自反关系，则RR,IAR,因而(ynr)RR0RIARR=R.即RR0R。可见RR0满足自反闭包的定义，从而r(R)=RR0.(2)略。第39页/共64页第四十页，共64页。2/7/2023 2:47 AM 41(3)先证RR2t(R),为此只需证明对任意正整数n都有Rnt(R)即可。用归纳法。当n=1时，R1=Rt(R).假设Rnt(R),下证Rn+1t(R)事实上，由于Rn+1=RnRt(RnR)t(t(R)t(R)t(R)从而(cngr)Rn+1t(R).由归纳

28、法完成证明。(因t(R)是传递(chund)的)第40页/共64页第四十一页，共64页。2/7/2023 2:47 AM 42下证RR2是传递的。事实上，对任意(rny),(RR2)(RR2)t(Rt)s(Rs)ts(RtRs)ts(Rt+s)RR2从而RR2是传递的。因t(R)是传递闭包，故t(R)RR2。由以上两方面知，t(R)RR2。第41页/共64页第四十二页，共64页。2/7/2023 2:47 AM 43 证：由定理(dngl)7.6和定理(dngl)7.10立即得证。通过关系矩阵求闭包设关系R,r(R),s(R),t(R)的关系矩阵分别(fnbi)为M,Mr,Ms,Mt,则：Mr

29、=M+E,Ms=M+M,Mt=M+M2+M3+,其中E是与M同阶的单位矩阵。M是M的转置矩阵，矩阵元素相加时使用逻辑加。推论推论推论推论 设设设设R R R R是有限集合是有限集合是有限集合是有限集合A A A A 上的关系上的关系上的关系上的关系(gun x)(gun x)(gun x)(gun x)，则存在正整数，则存在正整数，则存在正整数，则存在正整数r r r r使得使得使得使得 t(R)=RR2Rr.t(R)=RR2Rr.t(R)=RR2Rr.t(R)=RR2Rr.第42页/共64页第四十三页，共64页。2/7/2023 2:47 AM 44设关系(gunx)R,r(R),s(R),

30、t(R)的关系(gunx)图分别记为G,Gr,Gs,Gt,则Gr,Gs,Gt的顶点集与G的顶点集相同。除了G的边外，依下述方法添加新边：(1)对G的每个顶点，如果无环，则添加一条环，由此得到Gr;(2)对G的每条边，如果它是单向边，则添加一条反方向的边。由此得到Gs;通过通过通过通过(tnggu)(tnggu)(tnggu)(tnggu)关系求闭关系求闭关系求闭关系求闭包包包包例7.15见教材(jioci)P120(3)对G的每个顶点xi,找出从xi 出发的所有2步,3步,n步长的有向路(n为G的顶点数)。设路的终点分别为,如果从xi 到无边，则添上这条边。如果处理完所有顶点后得到GtWars

31、hall算法求t(R).第43页/共64页第四十四页，共64页。2/7/2023 2:47 AM 45定理(dngl)7.11设R是非空集合A上的关系，则(1)R是自反的当且仅当r(R)=R(2)R是对称的当且仅当s(R)=R(3)R是传递的当且仅当t(R)=R证：(1)充分性显然。下证必要性。因R是包含了R的自反关系，故r(R)R。另一方面，显然Rr(R).从而，r(R)=R。(2),(3)略(Def7.14).定理(dngl)7.12设R1和R2是非空集合A上的关系，且R1R2,则(1)r(R1)r(R2);(2)s(R1)s(R2);(3)t(R1)t(R2)证明略三三三三.闭包的性质闭

32、包的性质闭包的性质闭包的性质(xngzh)(xngzh)(xngzh)(xngzh)第44页/共64页第四十五页，共64页。2/7/2023 2:47 AM 46定理7.13设R是非(shfi)空集合A上的关系（1）若R是自反的，则s(R)和t(R)也是自反的。（2）若R是对称的，则r(R)和t(R)也是自反的。（3）若R是传递的，则r(R)也是传递的。证明：只证(2)。先考虑r(R).因R是A上的对称关系。故R=R-1,同时IA=IA-1,于是(RIA)-1=R-1IA-1(根据习题7.20).从而r(R)-1=(RR0)-1=(RIA)-1=R-1IA-1=RIA=r(R)。这便说明r(R

33、)是对称的。下面证明t(R)的对称性。为此，先用数学归纳法证明：若R是对称的，则对任何正整数n,Rn也是对称的。事实上，当n=1时，R=R显然是对称的。第45页/共64页第四十六页，共64页。2/7/2023 2:47 AM 47假设Rn是对称的，下证Rn+1的对称性。由于Rn+1RnRt(Rn)R)t(Rn)R)RRnRn+1故Rn+1是对称的。归纳(gun)法定成。现在来证t(R)的对称性。由于t(R)n(Rn)n(Rn)t(R)因此t(R)是对称的。注：由于传递闭包运算和对称闭包运算不保持传递性，故在运算顺序上它们应放在自反闭包之后，即tsr(R)=t(s(r(R)。第46页/共64页第

34、四十七页，共64页。2/7/2023 2:47 AM 48n n 二元关系的闭包仍然是二元关系，还可以求它的闭包。n n 例如，R是A上的二元关系,r(R)是它的自反闭包，还可以求r(R)的对称(duchn)闭包。r(R)的对称(duchn)闭包记为s(r(R)，简记为sr(R)，读做R的自反闭包的对称(duchn)闭包。n n 类似的，R的对称(duchn)闭包的自反闭包r(s(R)简记为rs(R)，R的对称(duchn)闭包的传递闭包t(s(R)，简记为ts(R)，n n 通常用R*表示R的传递闭包的自反闭包rt(R)，读作“R星”。n n在研究形式语言和计算模型时经常使用R*。第47页/

35、共64页第四十八页，共64页。2/7/2023 2:47 AM 497.6 等价关系与划分(hu fn)例7.16设A=1,2,8,定义A上的关系R如下：验证R是A上的等价关系。一.等价关系(gun x)定义7.15 设R为非空集合A上的关系(gun x)。如果R是自反的,对称的和传递的，则称R为A上的等价关系(gun x)。对等价关系(gun x)R，若R,则称 x 等价于y，记为x y or xRy.解：xA,有,故R是自反的。x,yA,若,则,故R是对称的。x,y,zA,若,则故R是传递(chund)的。R是A上的一个等价关系。第48页/共64页第四十九页，共64页。2/7/2023 2

36、:47 AM 50定义7.16设R为非空集合A上的等价关系，xA,令称xR为x在R下的等价类(简称为x的等价类)，有时简记为x。x称为该等价类的代表元。注：一个等价类是A中在等价关系R下彼此等价的所有元素的集合，等价类中各元素的地位是平等的，每个元素都可以作为其所在(suzi)等价类的代表元。例如，在上例中的等价关系R下，A中元素形成了三个等价类：1=4=7=1,4,7；2=5=8=2,5,8;3=6=3,6.二二二二.等价等价等价等价(dngji)(dngji)(dngji)(dngji)类类类类第49页/共64页第五十页，共64页。2/7/2023 2:47 AM 51定理7.14 设 R

37、 为非空集合 A上的等价关系，则 （1）xA,x是A的非空子集。（2）x,yA，如果xRy,则 x=y （3）x,yA，如果x与y不具有关系 R,则 x 与 y 不相交。（4）证：(1)显然(xinrn)。(2)zx R R（R是对称的）RR R R zy,从而 x y 同理可得，y x.故 x=y三三三三.等价等价等价等价(dngji)(dngji)(dngji)(dngji)类的性类的性类的性类的性质质质质第50页/共64页第五十一页，共64页。2/7/2023 2:47 AM 52(3)反证法。假设 xy，则存在 zxy.因而 z x 且z y，即RR.根据(gnj)R的对称性和传递性，

38、必有R。这与前提条件矛盾。故原命题成立。(4)先证再证因此(ync)第51页/共64页第五十二页，共64页。2/7/2023 2:47 AM 53定义(dngy)7.17设R为非空集合A上的等价关系，以R的所有等价类作为元素，形成的集合称为A关于R的商集，记为A/R，即：例如：例7.16中等价关系形成的商集为：A/R1,4,7,2,5,8,3,6四四四四.商集商集商集商集定义7.18设A为非空集合，若A的子集族(P(A),是由A的一些子集形成的集合)满足下列条件(tiojin)：(1)(2)xy(x,yxyxy=)(3)则称是A的一个划分，而称中的元素为A的划分块或类。五.集合(jh)的划分第

39、52页/共64页第五十三页，共64页。2/7/2023 2:47 AM 54例7.17设A=a,b,c,d,则1=a,b,c,d和2=a,b,c,d都是A的划分，而3=a,a,b,c,d和4=,a,b,c都不是A的划分。注：给定非空有限集A上的一个等价关系R，在R下彼此等价的元素构成的子集便形成了A的一个划分，它其实就是商集A/R,其每个类(等价块)就是R的一个等价类；反之，任给A的一个划分，可定义A上的关系R如下：R=x,yAx与y在的同一个类中可以验证(ynzhng)R是A上的一个等价关系。可见A上的等价关系与A的划分是一一对应的。第53页/共64页第五十四页，共64页。2/7/2023

40、2:47 AM 55例7.18求A=1,2,3上所有的等价关系。解：先求出A的所有划分(hufn)：1=1,2,3;2=1,2,3；3=2,1,3;4=3,1,2;5=1,2,3。与这些划分(hufn)一一对应的等价关系是：1:全域关系EA2:R2=,IA3:R3=,IA4:R4=,IA5:恒等关系IA第54页/共64页第五十五页，共64页。2/7/2023 2:47 AM 56一.偏序关系与偏序集二.定义7.19 设R为非空集合A上的关系。如果R是自反的、反对称的和三.传递(chund)的，则称 R 为 A上的偏序关系，记为 。四.对一个偏序关系 ，如果 ，则记为 x y。五.注：六.1.集

41、合A上的恒等关系IA和空关系都是A上的偏序关系，但全域关系EA 一般不是A上的偏序关系。七.2.实数域上的小于等于关系（大于等于关系），自然数域上的整除关系，集合的包含关系等都是偏序关系。7.7 7.7 7.7 7.7 偏序关系偏序关系偏序关系偏序关系(gun x)(gun x)(gun x)(gun x)第55页/共64页第五十六页，共64页。2/7/2023 2:47 AM 57注：在具有偏序关系的集合(jh)A中任二元素x和y之间必有下列四种情形之一：xy，yx，x=y，x与y不可比。例设A=1,2,3是A上的整除关系，则：12,13,11,22,33，2和3不可比；(2)是A上的大于等

42、于关系，则:21,31,32,11,22，33。定义定义(dngy)7.20 设设R为非空集合为非空集合A上的偏序关系，定义上的偏序关系，定义(dngy)(1)x,yA,xy当且仅当xy且xy(2)x,yA,x与y可比当且仅当xy或yx第56页/共64页第五十七页，共64页。2/7/2023 2:47 AM 58定义7.21设R为非空集合A上的偏序关系，如果(rgu)x,yA,x与y都是可比的，则称R为A上的全序关系。例如大于等于关系（小于等于关系）是全序集，但整除关系一般不是全序集。定义7.22带有某种指定的偏序关系的集合A称为偏序集，记为.例如整数集Z和数的小于等于关系构成偏序集;集合A的

43、幂集P(A)和集合的包含关系构成偏序集.定义7.23设为偏序集，x,yA,如果(rgu)xy且不存在zA,使得xzy,则称y覆盖x。例如A=1,2,4,6上的整除关系，有2覆盖1，4和6都覆盖2，但4不覆盖1，6不覆盖4。第57页/共64页第五十八页，共64页。2/7/2023 2:47 AM 59 利用偏序关系的自反性、反对称性和传递性可简化偏序关系的关系图，得到偏序集的哈斯图。设有偏序集,其哈斯图的画法如下：(1)以 A 的元素作为顶点，适当排列各顶点的顺序,使得对 x,y A，若x y,则将 x 画在 y 的下方。(2)对A中两个(lin)不同元素 x 和 y,如果 y 覆盖x,则用一条

44、线段连接 x 和 y.例7.19 画出偏序集1,2,3,9,R整除 和 的哈斯图.二二.哈斯图哈斯图解：它们的哈斯图分别解：它们的哈斯图分别(fnbi)(fnbi)为图为图A A、图、图B B表示如下：表示如下：847236951图Aa,ba,b,cabb,cca,c图B第58页/共64页第五十九页，共64页。2/7/2023 2:47 AM 60例7.20已知偏序集的哈斯图如下：求集合(jh)A和关系R的表达式。二二.哈斯图哈斯图aedfhgbc解 A=a,b,c,d,e,f,g,h,R=,IA.第59页/共64页第六十页，共64页。2/7/2023 2:47 AM 61定义7.24设为偏序

45、集，BA,yB.(1)若x(xByx)成立，则称y是B的最小元；(2)若x(xBxy)成立，则称y是B的最大元；(3)若x(xBxyx=y)成立，则称y是B的极小元；(4)若x(xByxx=y)成立，则称y是B的极大元；注：极大(极小)元未必是最大(最小)元。极大(极小)元未必与B中任何元素都可比；(2)对有限集B，极大(极小)元一定存在，但最大(最小)元不一定存在;(3)最大(最小)元如果存在，必定(bdng)是唯一的;而极大(极小)元一般不唯一。但如果B中只有一个极大(极小)元,则它一定是B的最大(最小)元。三三.偏序集中的特殊偏序集中的特殊(tsh)(tsh)元素元素第60页/共64页第

46、六十一页，共64页。2/7/2023 2:47 AM 62解：极大元：a,f,h;极小(jxio)元:a,b,c,g;无最大元和最小元。例例例例7.21 7.21 7.21 7.21 求上例中求上例中求上例中求上例中A A A A的极大元、极小的极大元、极小的极大元、极小的极大元、极小(j xio)(j xio)(j xio)(j xio)元、最大元、最小元，元、最大元、最小元，元、最大元、最小元，元、最大元、最小元，例7.22设x为集合，A=p(x)-x,且A,若|x|=n,问：(1)偏序集是否有最大元？(2)偏序集是否有最小元？(3)偏序集中极大元和极小元的一般形式(xngsh)是什么？解

47、：首先，因A,故n2,x中单个元素构成的子集都在 A中，他们在 R下互相不可比，因此A中无最大元和最小元。第61页/共64页第六十二页，共64页。2/7/2023 2:47 AM 63 其次考察其次考察(P(x),R(P(x),R)的哈斯图。的哈斯图。其最低层是空集其最低层是空集(kn j)(kn j)，记为第，记为第0 0层，由底向上，第层，由底向上，第1 1层是单元层是单元集，第集，第2 2层是二元子集，层是二元子集，,第第n-1n-1层是层是x x的所有的所有n-1n-1元子集，最顶层即第元子集，最顶层即第n n层，只有一个顶点层，只有一个顶点x x。偏序集偏序集A,R 的哈斯图是由的哈

48、斯图是由P(x)P(x)的哈斯图去掉第的哈斯图去掉第0 0层与第层与第n n层得到的层得到的,故故x x的所有单元集都是的所有单元集都是A,R 的极小元，的极小元，x x的所有的所有n-1n-1元子集元子集都是都是A,R 的极大元。的极大元。第62页/共64页第六十三页，共64页。2/7/2023 2:47 AM 64定义定义定义定义(dngy)7.25 (dngy)7.25 设设设设A,为偏序集，为偏序集，为偏序集，为偏序集，B BA,yA,yA.A.(1)若 x(xBxy)成立,则称y为B的上界;(2)若 x(xByx)成立，则称y为B的下界；(3)令 Cy|y为B的上界，则称C的最小元为B的最小上界或上确界；(4)令 Dy|y为B的下界，则称D的最大元为B的最大下界或下确界.注：B的最大元(最小元)必定是B的上界(下界)，也是B的上确界(下确界)。2.B的上界和上确界都未必(wib)是B的最大元，因它们可能不在B中。同理，下界和下确也未必(wib)是B的最小元。3.B的上界、上确界、下界、下确界都可能不存在。但如果上确界(下确界)存在，则它是唯一的。第63页/共64页第六十四页，共64页。