《数学关系性质离散数学.pptx》由会员分享，可在线阅读，更多相关《数学关系性质离散数学.pptx（64页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、3/25/2023 1:34 AM 1第 七 章 二 元 关 系7.1有序对与笛卡儿积7.2二元关系7.3关系的运算7.4关系的性质7.5关系的闭包7.6等价关系与划分7.7偏序关系第1页/共64页3/25/2023 1:34 AM 2定义7.1由两个元素x和y（允许xy）按一定顺序排列成的二元组叫做一个有序对，记为。注：有序对的性质：1.当xy时，。2.的充分必要条件是x=u且y=v。7.1 有序对与笛卡尔积 定义7.2 设A,B是集合。由A中元作为第一元素，B中元作为第二元素组成的所有有序对的集合，称为集合A与B的笛卡尔积，记为AB。即 AB|xAyB。第2页/共64页3/25/2023
2、1:34 AM 3注：笛卡尔积的性质：1.A=,A=;2.ABBA,除非 A=或B=或A=B;3.(AB)CA(BC),除非 A=或B=或C=.4.A(BC)=(AB)(AC);(BC)A=(BA)(CA);A(BC)=(AB)(AC);(BC)A=(BA)(CA);5.(AC)(BD)(AB)(CD).7.1有序对与笛卡尔积第3页/共64页3/25/2023 1:34 AM 4例 证明A(BC)=(AB)(AC)。证：任取，A(BC)xAy(BC)xA(yByC)(xAyB)(xAyC)(AB)(AC)(AB)(AC)A(BC)=(AB)(AC)例7.2 设 A=1,2,求 P(A)A。解：
3、P(A)A =,1,2,1,21,2=,7.1有序对与笛卡尔积第4页/共64页3/25/2023 1:34 AM 5例7.3 设A,B,C,D为任意集合，判断下列命题是否为真。（1）ABACB=C（2）A(BC)=(AB)(AC)（3）(A=B)(C=D)AC=BD（4）存在集合A,使 AAA7.1有序对与笛卡尔积解:(1)不一定为真，(3)为真。(4)为真。当A=,B=1,C=2,3时，便不真。(2)不一定为真，当A=B=1,C=2时，A(BC)=1=1,而(AB)(AC)=1=.等量代入。当A=时,使AAA.第5页/共64页3/25/2023 1:34 AM 6一、基本概念定义7.3 如果
4、一个非空集合的元素都是有序对，则称该集合为一个二元关系。特别地，空集也是一个二元关系。注：对一个二元关系R，如果R,则记为xRy；如果R，则记为xRy。定义7.4 设A,B为集合，AB的任何子集所定义的二元关系称为从A到B的二元关系。特别地，当A=B时，称为A上的二元关系。定义7.5 对任何集合A，(1)称空集为A上的空关系。(2)A上的全域关系EA=xAyA=AA(3)A上的恒等关系IA=xA.7.2二元关系第6页/共64页3/25/2023 1:34 AM 7二.关系的表达方式1.集合表达式：列出关系中的所有有序对。例7.4 设A=1,2,3,4,试列出下列关系R的元素。(1)R=x是y的
5、倍数(2)R=(xy)2A(3)R=x/y是素数(4)R=xy(5)R=(x,yA)(xy)解:(1)R=,(2)R=,(3)R=,(4)R=EA-IA=,(5)R=,7.2二元关系第7页/共64页3/25/2023 1:34 AM 82.关系矩阵法：设A=x1,x2,xn,R 是 A 上的关系。令：则矩阵 称为R 的关系矩阵。7.2二元关系第8页/共64页3/25/2023 1:34 AM 9例 设A=1,2,3,4,R=,则R的关系矩阵为7.2二元关系第9页/共64页3/25/2023 1:34 AM 103.关系图法 设A=x1,x2,xn,R是A上的关系。以A的元素作为顶点，当且仅当x
6、iRxj时，xi 向xj 连一条有向边，所得的图形称为R的关系图，记为GR。例7.6 设 A=1,2,3,4,R=,则R的关系图为12437.2二元关系第10页/共64页3/25/2023 1:34 AM 11一、基本概念定义7.6设R是二元关系。定义(1)R的定义域:domR=x|y(R),即R中所有有序对的第一元素构成的集合。(2)R的值域，ranR=y|x(R),即R中所有有序对的第二元素构成的集合。(3)R的域:fld R=dom Rran R。例7.5R=,则domR=1,2,4，ranR=2,3,4,fld R=1,2,3,4。7.3 关系的运算第11页/共64页3/25/2023
7、 1:34 AM 12定义7.7 设R为二元关系，称 R-1=|R为R的逆关系。定义7.8 设F,G为二元关系。称为G 对F 的右复合(或F 对G 的左复合)。例如,F=,G=,则 F-1=,7.3 关系的运算第12页/共64页3/25/2023 1:34 AM 13定义7.9设R是二元关系,A是集合(通常AdomR)7.3 关系的运算例7.7设R为,则(1)R在A上的限制:RA=|xRyxAR1=2,3,R=,R2,3=2,4。R1=,R=,R2,3=,，(2)A在R下的像:RA=ran(RA)第13页/共64页3/25/2023 1:34 AM 14定义7.10 设R是A上的关系,n为自然
8、数,则R的n次幂定义为:(1)R0=|xA=IA;(2)注:1.对A上的任何关系R,都有 R0=IA,R1=R。2.Rn的求法:除了根据定义按关系的复合来求之外,还可以用矩阵法和关系图法。7.3 关系的运算第14页/共64页3/25/2023 1:34 AM 15例7.8 设A=a,b,c,d,R=,求R的各次幂,分别用矩阵和关系图表示.解:R的关系矩阵:R2,R3,R4 的关系矩阵分别是：第15页/共64页3/25/2023 1:34 AM 16可见M4=M2。故R2=R4=R6=;R3=R5=R7=。第16页/共64页3/25/2023 1:34 AM 17此外,R0=IA的关系矩阵为:用
9、关系图法得到 R0,R1,R2,的关系图如下:dabcR0R1abcdR2=R4=bcdaabcdR3=R5=第17页/共64页3/25/2023 1:34 AM 18关系是集合,故有关集合的所有运算性质对关系都成立。定理7.1 设F是关系,则(1)(F-1)-1=F;(2)dom F-1=ran F,ran F-1=domF。证:(1)(F-1)-1F-1F(F-1)-1=F。(2)xdomF-1y(F-1)y(F)xran FdomF-1=ran F。同理可证 ran F-1=dom F。二.关系的运算性质第18页/共64页3/25/2023 1:34 AM 19定理7.2 设F,G,H是
10、关系，则(1)(FG)H=F(GH);(2)(FG)1=G1F1.证:(1)(FG)H)t(FG)H)t(s(FG)H)ts(FG)H)s(Ft(GH)s(F(GH)F(GH)(FG)H=F(GH)(2)(FG)1FGt(FG)t(G1F1)(G1F1)(FG)1=G1F1第19页/共64页3/25/2023 1:34 AM 20定理7.3 设R是A上的关系,则 RIA=IAR=R.证:(RIA)t(RIA)t(Rt=y)RRRyARIA(RIA)RIA=R同理可证 IAR=R第20页/共64页3/25/2023 1:34 AM 21定理7.4 设F,G,H是关系,则(1)F(GH)=FGFH
11、;(2)(GH)F=GFHF;(3)F(GH)FGFH;(4)(GH)FGFHF.证:以(3)为例.F(GH)t(F(GH)t(FGH)t(FG)(FH)t(FG)t(FH)FGFH FGFHF(GH)=FGFH第21页/共64页3/25/2023 1:34 AM 22定理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页3/25/2023 1:34 AM 23(4)yF
12、ABx(F(xAB)x(FxAxB)x(FxA)(FxB)x(FxA)x(FxB)yFAyFBy(FAFB)FAB=FAFB第23页/共64页3/25/2023 1:34 AM 24定理7.7设R为A上的关系,m,nN,则(1)RmRn=Rm+n;(2)(Rm)n=Rmn证:(1)对于任意取定的mN，关于n作数学归纳法。当n=0时，RmR0=RmIA=Rm=Rm+0假设RmRn=Rm+n,则RmRn+1=Rm(RnR)=(RmRn)R=Rm+nR1=Rm+n+1由归纳法原理,知命题成立。(2)对任意取定的mN,关于n作数学归纳法。当n=0时,(Rm)0=IA=R0=Rm0假设(Rm)n=Rmn
13、,则(Rm)n+1=(Rm)nRm=RmnRm=Rmn+m=Rm(n+1)由归纳法原理,知命题成立。定理7.6 设A是n元集合,R为A上的关系,则存在自然数s和t,使得Rs=Rt。第24页/共64页3/25/2023 1:34 AM 25定理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)表明,有限集合A上的二元关系只有有限多个,而且一个关系的幂序列R0,R1R2,是一个周期性变
14、化的序列。例7.9见教材P113。第25页/共64页3/25/2023 1:34 AM 26一、关系的五种性质 关系的性质主要有5种:自反性,反自反性,对称性,反对称性和传递性。定义7.11 设R是A上的关系,若x(xAR),则称 R在A上是自反的(Reflexive);若x(xAR),则称R在A上是反自反的(antiReflexive).7.4 关系的性质第26页/共64页3/25/2023 1:34 AM 27例7.10(1)A上的全域关系EA、恒等关系IA都是A上的自反关系.(2)小于等于关系 LA=x,yAxy,AR.整除关系 DA=x,yAx整除y,AZ*.包含关系 R=x,yAxy
15、,A 是集合族。都是自反关系.(3)小于关系 SA=x,yAxy,AR.真包含关系 R=x,yAxy,A是集合族。都是反自反关系.(4)设 A=1,2,3,R1=,是A上的自反关系;R2=是A上的反自反关系;R3=,既不是自反的,也不是反自反的.第27页/共64页3/25/2023 1:34 AM 28定义7.12 设R是A上的关系,若xy(x,yAR(y,x)R),则称R是A上的对称关系(Symmetric);若 xy(x,yAR(y,x)Rx=y),则称R是A上的反对称关系(antiSymmetric).例7.11(1)A上的全域关系EA,恒等关系IA及空关系都是A上的对称关系;IA和同时
16、也是A上的反对称关系.(2)设A=1,2,3,则 R1=,既是A上的对称关系,也是A上的反对称关系;R2=,是对称的,但不是反对称的;R3=,是反对称的,但不是对称的;R4=,既不是对称的也不是反对称的。第28页/共64页3/25/2023 1:34 AM 29定义7.13设R是A上的关系,若xyz(x,y,zARRR),则称R是A上的传递关系。例7.12(1)A上的全域关系EA,恒等关系IA和空关系都是传递关系。(2)小于等于关系,整除关系和包含关系是传递关系,小于关系和真包含关系也是传递关系。(3)设A=1,2,3,则R1=,和R2=都是A上的传递关系,但R3=,不是A上的传递关系。第29
17、页/共64页3/25/2023 1:34 AM 30定理7.9 设R为A上的关系,则(1)R在A上自反当且仅当 IAR(2)R在A上反自反当且仅当 RIA=(3)R在A上对称当且仅当 R=R-1(4)R在A上反对称当且仅当 RR-1IA(5)R在A上传递当且仅当 RRR证:(1)必要性:因R在A上自反,故IAx,yAx=yR，从而IAR。充分性:因xAIAR,故R在A上自反。二、各种性质的充分必要条件第30页/共64页3/25/2023 1:34 AM 31(2)必要性(用反证法):假设RIA,则必存在RIA,即R且IA。由IA知x=y.从而R.这与R在A上是反自反矛盾。充分性:xAIAR(因
18、RIA=),这说明R在A上是反自反的。(3)必要性:R是A上的对称关系,RRR-1,故R=R-1。充分性:由于R=R-1,RR-1 R.故R在A上是对称的。第31页/共64页3/25/2023 1:34 AM 32(4)必要性:因R在A上是反对称的,故RR1RR1RRx=yIA.RR1IA 充分性:因 RR1 IA,故RRRR1RR1IAx=y.从而 R在A上是反对称的.第32页/共64页3/25/2023 1:34 AM 33(5)必要性:因R在A上是传递的,故RRt(RR)R因此RRR充分性:因RRR,故RRRRRR在A上是传递的。第33页/共64页3/25/2023 1:34 AM 34
19、 例7.13 设A是集合,R1和R2是A上的关系,证明(1)若R1和R2都是自反的和对称的,则R1R2也是自反的和对称的.(2)若R1和R2是传递的,则R1R2也是传递的.证:(1)因R1和R2是A上的自反关系,故IAR1,IAR2,从而IAR1R2.由定理7.9,R1R2在A上是自反的.由R1和R2的对称性,有R1=R11和R2=R2-1,因此(R1R2)-1=R1-1R2-1=R1R2(见习题7.20).由定理7.9,R1R2在A上是对称的.(2)由R1和R2的传递性,有R1R1R1和R2R2R2.由定理7.4,(R1R2)(R1R2)(R1R1)(R1R2)(R2R1)(R2R2)(R1
20、R2)(R1R2)(R2R1)R1R2由定理7.9,R1R2在A上是传递的.第34页/共64页3/25/2023 1:34 AM 35 性质表示性质表示自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性集合表达式集合表达式IA RRIA=R=R1 RR1 IAR R R关系矩阵关系矩阵主主对对角角线线元元素素全是全是1 1主主对对角角线线元元素素全是全是0 0矩阵是对称矩阵。矩阵是对称矩阵。若若rij=1,且且ij,则则 rji=0.对对M2中中1所所在在的的位位置置,M中中相相应应的的位位置都是置都是1。关系图关系图每每个个顶顶点点都都有有环环每每个个顶顶点点都都没没有环有
21、环如如果果两两个个顶顶点点之之间间有有边边,则则必必是是一一对方向相反的边。对方向相反的边。每每对对顶顶点点之之间间至至多多有有一一条条边边,(,(不不会会有有双双向向边边)。如如果果顶顶点点xi到到xj有有边边,xj到到 xk有有边边,则则从从xi到到 xk也有边。也有边。三.各种性质在关系矩阵和关系图中的体现第35页/共64页3/25/2023 1:34 AM 36例7.14 判断图7.3中关系的性质解:(a)该关系是对称的.其它性质均不具备。(b)该关系是反自反的,反对称的,同时也是传递的。(c)该关系是自反的,反对称的,但不是传递的。(a)(b)(c)321231231第36页/共64
22、页3/25/2023 1:34 AM 37四.各种性质与运算之间关系 性质性质 运算运算 自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性R1R1R2R1R2 R1 R2 R1 R2 第37页/共64页3/25/2023 1:34 AM 38一.闭包的定义定义7.14设R是非空集合A上的关系,R的自反闭包(对称闭包、传递闭包)是A上的关系R，它满足：(1)R 是自反的(对称的、传递的)；(2)RR;(3)对A上任何包含R的自反关系(对称关系、传递关系)R 都有RR.注：R的自反闭包记为r(R)，对称闭包记为s(R)，传递闭包记为t(R)。7.5 关系的闭包Reflexive
23、,Symmetric,Transtive:r(R),s(R),t(R).第38页/共64页3/25/2023 1:34 AM 39二.闭包的构造方法定理7.10设R是A上的关系，则(1)r(R)=RR0;(2)s(R)=RR-1;(3)t(R)=RR2R3.证明：(1)由IA=R0RR0知，RR0是自反的，且RRR0。设R是A上包含R的自反关系，则RR,IAR,因而RR0RIARR=R.即RR0R。可见RR0满足自反闭包的定义，从而r(R)=RR0.(2)略。第39页/共64页3/25/2023 1:34 AM 40(3)先证RR2t(R),为此只需证明对任意正整数n都有Rnt(R)即可。用归
24、纳法。当n=1时，R1=Rt(R).假设Rnt(R),下证Rn+1t(R)事实上，由于Rn+1=RnRt(RnR)t(t(R)t(R)t(R)从而Rn+1t(R).由归纳法完成证明。(因t(R)是传递的)第40页/共64页3/25/2023 1:34 AM 41下证RR2是传递的。事实上，对任意,(RR2)(RR2)t(Rt)s(Rs)ts(RtRs)ts(Rt+s)RR2从而RR2是传递的。因t(R)是传递闭包，故t(R)RR2。由以上两方面知，t(R)RR2。第41页/共64页3/25/2023 1:34 AM 42 证：由定理7.6和定理7.10立即得证。通过关系矩阵求闭包设关系R,r(
25、R),s(R),t(R)的关系矩阵分别为M,Mr,Ms,Mt,则：Mr=M+E,Ms=M+M,Mt=M+M2+M3+,其中E是与M同阶的单位矩阵。M是M的转置矩阵，矩阵元素相加时使用逻辑加。推论 设R R是有限集合A A 上的关系，则存在正整数r r使得 t(R)=RRt(R)=RR2 2RRr r.第42页/共64页3/25/2023 1:34 AM 43设关系R,r(R),s(R),t(R)的关系图分别记为G,Gr,Gs,Gt,则Gr,Gs,Gt的顶点集与G的顶点集相同。除了G的边外，依下述方法添加新边：(1)对G的每个顶点，如果无环，则添加一条环，由此得到Gr;(2)对G的每条边，如果它
26、是单向边，则添加一条反方向的边。由此得到Gs;通过关系求闭包例7.15见教材P120(3)对G的每个顶点xi,找出从xi 出发的所有2步,3步,n步长的有向路(n为G的顶点数)。设路的终点分别为,如果从xi 到无边，则添上这条边。如果处理完所有顶点后得到GtWarshall算法求t(R).第43页/共64页3/25/2023 1:34 AM 44定理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).从
27、而，r(R)=R。(2),(3)略(Def7.14).定理7.12设R1和R2是非空集合A上的关系，且R1R2,则(1)r(R1)r(R2);(2)s(R1)s(R2);(3)t(R1)t(R2)证明略三.闭包的性质第44页/共64页3/25/2023 1:34 AM 45定理7.13设R是非空集合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)
28、.从而r(R)-1=(RR0)-1=(RIA)-1=R-1IA-1=RIA=r(R)。这便说明r(R)是对称的。下面证明t(R)的对称性。为此，先用数学归纳法证明：若R是对称的，则对任何正整数n,Rn也是对称的。事实上，当n=1时，R=R显然是对称的。第45页/共64页3/25/2023 1:34 AM 46假设Rn是对称的，下证Rn+1的对称性。由于Rn+1RnRt(Rn)R)t(Rn)R)RRnRn+1故Rn+1是对称的。归纳法定成。现在来证t(R)的对称性。由于t(R)n(Rn)n(Rn)t(R)因此t(R)是对称的。注：由于传递闭包运算和对称闭包运算不保持传递性，故在运算顺序上它们应放
29、在自反闭包之后，即tsr(R)=t(s(r(R)。第46页/共64页3/25/2023 1:34 AM 47 二元关系的闭包仍然是二元关系，还可以求它的闭包。例如，R是A上的二元关系,r(R)是它的自反闭包，还可以求r(R)的对称闭包。r(R)的对称闭包记为s(r(R)，简记为sr(R)，读做R的自反闭包的对称闭包。类似的，R的对称闭包的自反闭包r(s(R)简记为rs(R)，R的对称闭包的传递闭包t(s(R)，简记为ts(R)，通常用R*表示R的传递闭包的自反闭包rt(R)，读作“R星”。在研究形式语言和计算模型时经常使用R*。第47页/共64页3/25/2023 1:34 AM 487.6
30、等价关系与划分例7.16设A=1,2,8,定义A上的关系R如下：验证R是A上的等价关系。一.等价关系 定义7.15 设R为非空集合A上的关系。如果R是自反的,对称的和传递的，则称R为A上的等价关系。对等价关系R，若R,则称x 等价于y，记为x y or xRy.解：xA,有,故R是自反的。x,yA,若,则,故R是对称的。x,y,zA,若,则故R是传递的。R是A上的一个等价关系。第48页/共64页3/25/2023 1:34 AM 49定义7.16设R为非空集合A上的等价关系，xA,令称xR为x在R下的等价类(简称为x的等价类)，有时简记为x。x 称为该等价类的代表元。注：一个等价类是A中在等价
31、关系R下彼此等价的所有元素的集合，等价类中各元素的地位是平等的，每个元素都可以作为其所在等价类的代表元。例如，在上例中的等价关系R下，A中元素形成了三个等价类：1=4=7=1,4,7；2=5=8=2,5,8;3=6=3,6.二.等价类第49页/共64页3/25/2023 1:34 AM 50定理7.14 设R为非空集合A上的等价关系，则（1）xA,x是A的非空子集。（2）x,yA，如果xRy,则x=y（3）x,yA，如果x与y不具有关系R,则x与y不相交。（4）证：(1)显然。(2)zxRR（R是对称的）RRRRzy,从而xy同理可得，yx.故x=y三.等价类的性质第50页/共64页3/25/
32、2023 1:34 AM 51(3)反证法。假设xy，则存在zxy.因而zx且zy，即RR.根据R的对称性和传递性，必有R。这与前提条件矛盾。故原命题成立。(4)先证再证因此第51页/共64页3/25/2023 1:34 AM 52定义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的一些子集形成的集合)满足下列条件：(1)(2)xy(x,yxyxy=)(3)则称是A的一个划分，而称中的元素为
33、A的划分块或类。五.集合的划分第52页/共64页3/25/2023 1:34 AM 53例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在的同一个类中可以验证R是A上的一个等价关系。可见A上的等价关系与A的划分是一一对应的。第53页/共64页3/25/2023 1:34 AM 54例7
34、.18求A=1,2,3上所有的等价关系。解：先求出A的所有划分：1=1,2,3;2=1,2,3；3=2,1,3;4=3,1,2;5=1,2,3。与这些划分一一对应的等价关系是：1:全域关系EA2:R2=,IA3:R3=,IA4:R4=,IA5:恒等关系IA第54页/共64页3/25/2023 1:34 AM 55一.偏序关系与偏序集定义7.19设R为非空集合A上的关系。如果R是自反的、反对称的和传递的，则称R为A上的偏序关系，记为。对一个偏序关系，如果，则记为x y。注：1.集合A上的恒等关系IA和空关系都是A上的偏序关系，但全域关系EA一般不是A上的偏序关系。2.实数域上的小于等于关系（大于
35、等于关系），自然数域上的整除关系，集合的包含关系等都是偏序关系。7.7 偏序关系第55页/共64页3/25/2023 1:34 AM 56注：在具有偏序关系的集合A中任二元素x和y之间必有下列四种情形之一：xy，yx，x=y，x与y不可比。例设A=1,2,3(1)是A上的整除关系，则：12,13,11,22,33，2和3不可比；(2)是A上的大于等于关系，则:21,31,32,11,22，33。定义7.20 设R为非空集合A上的偏序关系，定义(1)x,yA,xy当且仅当xy且xy(2)x,yA,x与y可比当且仅当xy或yx第56页/共64页3/25/2023 1:34 AM 57定义7.21设
36、R为非空集合A上的偏序关系，如果x,yA,x与y都是可比的，则称R为A上的全序关系。例如大于等于关系（小于等于关系）是全序集，但整除关系一般不是全序集。定义7.22带有某种指定的偏序关系的集合A称为偏序集，记为.例如整数集Z和数的小于等于关系构成偏序集;集合A的幂集P(A)和集合的包含关系构成偏序集.定义7.23设为偏序集，x,yA,如果xy且不存在zA,使得xzy,则称y覆盖x。例如A=1,2,4,6上的整除关系，有2覆盖1，4和6都覆盖2，但4不覆盖1，6不覆盖4。第57页/共64页3/25/2023 1:34 AM 58 利用偏序关系的自反性、反对称性和传递性可简化偏序关系的关系图，得到
37、偏序集的哈斯图。设有偏序集,其哈斯图的画法如下：(1)以A的元素作为顶点，适当排列各顶点的顺序,使得对x,yA，若xy,则将x画在y的下方。(2)对A中两个不同元素x和y,如果y覆盖x,则用一条线段连接x和y.例7.19画出偏序集1,2,3,9,R整除和的哈斯图.二.哈斯图解：它们的哈斯图分别为图解：它们的哈斯图分别为图A A、图、图B B表示如下：表示如下：847236951图Aa,ba,b,cabb,cca,c图B第58页/共64页3/25/2023 1:34 AM 59例7.20已知偏序集的哈斯图如下：求集合A和关系R的表达式。二.哈斯图aedfhgbc解 A=a,b,c,d,e,f,g
38、,h,R=,IA.第59页/共64页3/25/2023 1:34 AM 60定义7.24设为偏序集，BA,yB.(1)若x(xByx)成立，则称y是B的最小元；(2)若x(xBxy)成立，则称y是B的最大元；(3)若x(xBxyx=y)成立，则称y是B的极小元；(4)若x(xByxx=y)成立，则称y是B的极大元；注：(1)极大(极小)元未必是最大(最小)元。极大(极小)元未必与B中任何元素都可比；(2)对有限集B，极大(极小)元一定存在，但最大(最小)元不一定存在;(3)最大(最小)元如果存在，必定是唯一的;而极大(极小)元一般不唯一。但如果B中只有一个极大(极小)元,则它一定是B的最大(最
39、小)元。三.偏序集中的特殊元素第60页/共64页3/25/2023 1:34 AM 61解：极大元：a,f,h;极小元:a,b,c,g;无最大元和最小元。例7.217.21 求上例中A A的极大元、极小元、最大元、最小元，例7.22设x为集合，A=p(x)-x,且A,若|x|=n,问：(1)偏序集是否有最大元？(2)偏序集是否有最小元？(3)偏序集中极大元和极小元的一般形式是什么？解：首先，因A,故n2,x中单个元素构成的子集都在 A中，他们在 R下互相不可比，因此A中无最大元和最小元。第61页/共64页3/25/2023 1:34 AM 62 其次考察(P(x),R)的哈斯图。其最低层是空集
40、，记为第0层，由底向上，第1层是单元集，第2层是二元子集，,第n-1层是x的所有n-1元子集，最顶层即第n层，只有一个顶点x。偏序集 的哈斯图是由P(x)P(x)的哈斯图去掉第0 0层与第n n层得到的,故x x的所有单元集都是 的极小元，x x的所有n-1n-1元子集都是 的极大元。第62页/共64页3/25/2023 1:34 AM 63定义7.25 设为偏序集，B A,y A.(1)若 x(xBxy)成立,则称y为B的上界;(2)若 x(xByx)成立，则称y为B的下界；(3)令 Cy|y为B的上界，则称C的最小元为B的最小上界或上确界；(4)令 Dy|y为B的下界，则称D的最大元为B的最大下界或下确界.注：1.B的最大元(最小元)必定是B的上界(下界)，也是B的上确界(下确界)。2.B的上界和上确界都未必是B的最大元，因它们可能不在B中。同理，下界和下确也未必是B的最小元。3.B的上界、上确界、下界、下确界都可能不存在。但如果上确界(下确界)存在，则它是唯一的。第63页/共64页3/25/2023 1:34 AM Discrete Math.,huang liujia64感谢您的观看！第64页/共64页