离散数学第七章二元关系ppt课件

《离散数学第七章二元关系ppt课件》由会员分享，可在线阅读，更多相关《离散数学第七章二元关系ppt课件（91页珍藏版）》请在装配图网上搜索。

1、主要内容主要内容l有序对与笛卡儿积有序对与笛卡儿积l二元关系的定义与表示法二元关系的定义与表示法l关系的运算关系的运算l关系的性质关系的性质l关系的闭包关系的闭包l等价关系与划分等价关系与划分l偏序关系偏序关系第七章第七章 二元关系二元关系17.1有序对与笛卡儿积有序对与笛卡儿积定义定义7.1由两个元素由两个元素x 和和y，按照一定的顺序组成的二元组，按照一定的顺序组成的二元组称为称为有序对有序对，记作，记作.有序对性质有序对性质:(1)有序性有序性（当（当x y时）时）(2)与与相等的充分必要条件是相等的充分必要条件是=x=u y=v.2笛卡儿积笛卡儿积定义定义7.2设设A,B为集合，为集合

2、，A与与B的的笛卡儿积笛卡儿积记作记作A B，且，且A B=|x A y B.例例1A=1,2,3,B=a,b,c A B=,B A=,A=,B=P(A)A=,P(A)B=3笛卡儿积的性质笛卡儿积的性质(1)不适合交换律不适合交换律A B B A(A B,A,B)(2)不适合结合律不适合结合律(A B)C A(B C)(A,B,C)(3)对于并或交运算满足分配律对于并或交运算满足分配律A(B C)=(A B)(A C)(B C)A=(B A)(C A)A(B C)=(A B)(A C)(B C)A=(B A)(C A)(4)若若A 或或B 中有一个为空集，则中有一个为空集，则A B 就是空集就

3、是空集.A=B=(5)若若|A|=m,|B|=n,则则|A B|=mn4性质证明性质证明证明证明A(B C)=(A B)(A C)证证任取任取A(BC)xAyBC xA(yByC)(xAyB)(xAyC)ABAC(AB)(AC)所以有所以有A(BC)=(AB)(AC).5实例实例例例2(1)证明证明A=B,C=D A C=B D(2)A C=B D是否推出是否推出A=B,C=D?为什么？为什么？解解(1)任取任取 A Cx A y Cx B y D B D(2)不一定不一定.反例如下：反例如下：A=1，B=2,C=D=,则则A C=B D但是但是A B.67.2 二元关系二元关系定义定义7.3

4、如果一个集合满足以下条件之一：如果一个集合满足以下条件之一：(1)集合非空集合非空,且它的元素都是有序对且它的元素都是有序对(2)集合是空集集合是空集则称该集合为一个则称该集合为一个二元关系二元关系,简称为关系，记作简称为关系，记作R.如果如果R,可记作可记作xRy；如果；如果 R,则记作则记作xy实例：实例：R=,S=,a,b.R是二元关系是二元关系,当当a,b不是有序对时，不是有序对时，S不是二元关系不是二元关系根据上面的记法，可以写根据上面的记法，可以写1R2,aRb,a c等等.7A到到B的关系与的关系与A上的关系上的关系定义定义7.4设设A,B为集合为集合,AB的任何子集所定义的二元

5、关系叫做的任何子集所定义的二元关系叫做从从A到到B的二元关系的二元关系,当当A=B时则叫做时则叫做A上的二元关系上的二元关系.例例3A=0,1,B=1,2,3,那那么么R1=,R2=AB,R3=,R4=R1,R2,R3,R4是是从从A 到到B 的的二二元元关关系系,R3和和R4也也是是A上上的的二二元元关关系系.计计数数:|A|=n,|AA|=n2,AA的的子子集集有有个个.所所以以A上上有有个个不不同同的的二二元元关关系系.例例如如|A|=3,则则A上上有有=512个个不不同同的的二二元元关关系系.8A上重要关系的实例上重要关系的实例定义定义7.5设设A 为集合为集合,(1)是是A上的关系，

6、称为上的关系，称为空关系空关系(2)全域关系全域关系EA=|xAyA=AA 恒等关系恒等关系IA=|xA小于等于关系小于等于关系 LA=|x,yAxy,A为实数子集为实数子集 整除关系整除关系DB=|x,yBx整除整除y,A为非为非0整数子集整数子集 包含关系包含关系 R=|x,yAx y,A是集合族是集合族.9实例实例例如例如,A=1,2,则则EA=,IA=,例如例如A=1,2,3,B=a,b,则则LA=,DA=,例如例如A=P(B)=,a,b,a,b,则则A上的包含关系是上的包含关系是R=,类似的还可以定义：类似的还可以定义：大于等于关系大于等于关系,小于关系小于关系,大于关系大于关系,真

7、包含关系等真包含关系等.10关系的表示关系的表示1.关系矩阵关系矩阵若若A=x1,x2,xm，B=y1,y2,yn，R是从是从A到到B的的关系，关系，R的关系矩阵是布尔矩阵的关系矩阵是布尔矩阵MR=rijm n,其中其中rij=1 R.2.关系图关系图若若A=x1,x2,xm，R是从是从A上的关系，上的关系，R的关系图是的关系图是GR=,其中其中A为结点集，为结点集，R为边集为边集.如果如果属于属于关系关系R，在图中就有一条从，在图中就有一条从xi 到到xj 的有向边的有向边.注意：注意：l关系矩阵适合表示从关系矩阵适合表示从A到到B的关系或的关系或A上的关系（上的关系（A,B为有为有穷集）穷

8、集）l关系图适合表示有穷集关系图适合表示有穷集A上的关系上的关系11实例实例例例4 A=1,2,3,4,R=,R的关系矩阵的关系矩阵MR和关系图和关系图GR如下：如下：127.3 关系的运算关系的运算关系的基本运算关系的基本运算定义定义7.6关系的关系的定义域定义域、值域值域与与域域分别定义为分别定义为domR=x|y(R)ranR=y|x(R)fldR=domR ranR 例例5R=,则则domR=1,2,4ranR=2,3,4fldR=1,2,3,413关系运算关系运算(逆与合成逆与合成)定义定义7.7关系的关系的逆运逆运算算 R 1=|R 定义定义7.8关系的关系的合成合成运算运算 R

9、S=|y(R S)例例6R=,S=,R 1=,R S=,S R=,14合成的图示法合成的图示法利用图示（不是关系图）方法求合成利用图示（不是关系图）方法求合成R S=,S R=,15关系运算关系运算(限制与像限制与像)定义定义7.9设设R为二元关系为二元关系,A是集合是集合(1)R在在A上的上的限制限制记作记作 R A,其中其中R A=|xRyxA(2)A在在R下的下的像像记作记作RA,其中其中RA=ran(R A)说明：说明：lR在在A上的限制上的限制R A是是R 的子关系，即的子关系，即R A RlA在在R下的像下的像RA是是ranR 的子集，即的子集，即RA ranR16实例实例例例7设

10、设R=,则则R 1=,R=R 2,3=,R1=2,3R=R3=217关系运算的性质关系运算的性质定理定理7.1设设F是任意的关系是任意的关系,则则(1)(F 1)1=F(2)domF 1=ranF,ranF 1=domF证证(1)任取任取,由逆的定义有由逆的定义有(F 1)1F 1F.所以有所以有(F 1)1=F.(2)任取任取x,xdomF 1 y(F 1)y(F)xranF所以有所以有domF 1=ranF.同理可证同理可证ranF 1=domF.18定理定理7.2设设F,G,H是任意的关系是任意的关系,则则(1)(F G)H=F(G H)(2)(F G)1=G 1 F 1关系运算的性质关

11、系运算的性质证证(1)任取任取,(F G)H t(F GH)t(s(FG)H)t s(FGH)s(F t(GH)s(FG H)F(G H)所以所以(F G)H=F(G H)19证明证明(2)任取任取,(F G)1F G t(FG)t(G 1F 1)G 1 F 1所以所以(F G)1=G 1 F 120关系运算的性质关系运算的性质定理定理7.3设设R为为A上的关系上的关系,则则R IA=IA R=R证证任取任取R IA t(RIA)t(Rt=yyA)R21关系运算的性质关系运算的性质定理定理7.4(1)F(G H)=F GF H (2)(GH)F=G FH F(3)F(GH)F GF H (4)

12、(GH)F G FH F只证只证(3)任取任取,F(GH)t(FGH)t(FGH)t(FG)(FH)t(FG)t(FH)F GF HF GF H所以有所以有F(GH)=F GF H22推广推广定理定理7.4的结论可以推广到有限多个关系的结论可以推广到有限多个关系R(R1R2Rn)=R R1R R2R Rn(R1R2Rn)R=R1 RR2 RRn RR(R1R2Rn)R R1R R2R Rn(R1R2Rn)R R1 RR2 RRn R23关系运算的性质关系运算的性质定理定理7.5设设F 为关系为关系,A,B为集合为集合,则则(1)F (AB)=F AF B(2)F AB=F AF B(3)F (

13、AB)=F AF B(4)F AB F AF B24证明证明证证只证只证(1)和和(4).(1)任取任取F (AB)FxABF(xAxB)(FxA)(FxB)F AF BF AF B所以有所以有F (AB)=F AF B.25证明证明(4)任取任取y,yF AB x(FxAB)x(FxAxB)x(FxA)(FxB)x(FxA)x(FxB)yF AyF ByF AF B所以有所以有F AB=F AF B.26关系的幂运算关系的幂运算定义定义7.10设设R 为为A 上的关系上的关系,n为自然数为自然数,则则R 的的n 次幂次幂定义为：定义为：(1)R0=|xA=IA(2)Rn+1=Rn R注意：注

14、意：l对于对于A上的任何关系上的任何关系R1和和R2都有都有R10=R20=IAl对于对于A上的任何关系上的任何关系R 都有都有R1=R27例例8设设A=a,b,c,d,R=,求求R的各次幂的各次幂,分别用矩阵和关系图表示分别用矩阵和关系图表示.解解 R 与与 R2的关系矩阵分别是：的关系矩阵分别是：幂的求法幂的求法28R3和和R4的矩的矩阵阵是：是：因此因此M4=M2,即即R4=R2.因此可以得到因此可以得到R2=R4=R6=，R3=R5=R7=R0的关系矩阵是的关系矩阵是幂的求法幂的求法29关系图关系图R0,R1,R2,R3,的关系图如下图所示的关系图如下图所示.R0R1R2=R4=R3=

15、R5=30幂运算的性质幂运算的性质定理定理7.6设设A 为为n 元集元集,R 是是A上的关系上的关系,则存在自然数则存在自然数s 和和t,使得使得Rs=Rt.证证R 为为A上的关系上的关系,由于由于|A|=n,A上的不同关系只有上的不同关系只有个个.列出列出R 的各次幂的各次幂 R0,R1,R2,必存在自然数必存在自然数s 和和t 使得使得Rs=Rt 31定理定理7.7设设R 是是A上的关系上的关系,m,nN,则则(1)Rm Rn=Rm+n(2)(Rm)n=Rmn幂运算的性质幂运算的性质证证用归纳法用归纳法(1)对于任意给定的对于任意给定的mN,施归纳于施归纳于n.若若n=0,则有则有Rm R

16、0=Rm IA=Rm=Rm+0 假设假设Rm Rn=Rm+n,则有则有Rm Rn+1=Rm (Rn R)=(Rm Rn)R=Rm+n+1,所以对一切所以对一切m,nN有有Rm Rn=Rm+n.32证明证明(2)对于任意给定的对于任意给定的mN,施归纳于施归纳于n.若若n=0,则有则有(Rm)0=IA=R0=Rm0假设假设(Rm)n=Rmn,则有则有(Rm)n+1=(Rm)n Rm=(Rmn)Rn =Rmn+m=Rm(n+1)所以对一切所以对一切m,nN有有(Rm)n=Rmn.33定理定理7.8设设R是是A上的关系上的关系,若存在自然数若存在自然数s,t(st)使得使得Rs=Rt,则则(1)对对

17、任何任何kN有有Rs+k=Rt+k(2)对对任何任何k,iN有有Rs+kp+i=Rs+i,其中其中p=t s(3)令令S=R0,R1,Rt 1,则对则对于任意的于任意的qN有有RqS幂运算的性质幂运算的性质证证(1)Rs+k=Rs Rk=Rt Rk=Rt+k(2)对对k归纳归纳.若若k=0,则有则有Rs+0p+i=Rs+i假设假设Rs+kp+i=Rs+i,其中其中p=t s,则则Rs+(k+1)p+i=Rs+kp+i+p=Rs+kp+i Rp=Rs+i Rp=Rs+p+i=Rs+t s+i=Rt+i=Rs+i由归纳法命题得证由归纳法命题得证.34证明证明(3)任取任取 qN,若若 q t,显然

18、有显然有 RqS,若若q t,则存在自然数则存在自然数 k 和和 i 使得使得 q=s+kp+i,其中其中0ip 1.于是于是Rq=Rs+kp+i=Rs+i 而而s+i s+p 1=s+t s 1=t 1从而从而证明了证明了RqS.357.4关系的性质关系的性质定义定义7.11设设R 为为A上的关系上的关系,(1)若若 x(xA R),则称则称R 在在A 上是上是自反自反的的.(2)若若 x(xA R),则称则称R 在在A 上是上是反自反反自反的的.实例：实例：自反：全域关系自反：全域关系EA,恒等关系恒等关系IA,小于等于关系小于等于关系LA,整除关系整除关系DA反自反：实数集上的小于关系、

19、幂集上的真包含关系反自反：实数集上的小于关系、幂集上的真包含关系.A=1,2,3,R1,R2,R3是是A上的关系上的关系,其中其中 R1,R2,R3R2自反自反，R3反自反，反自反，R1既不是自反的也不是反自反的既不是自反的也不是反自反的.36对称性与反对称性对称性与反对称性定义定义7.12设设R 为为A上的关系上的关系,(1)若若 x y(x,yARR),则称则称R 为为A上上对对称称的关系的关系.(2)若若 x y(x,yARRx=y),则称则称R 为为A上的上的反对称反对称关系关系.实例：对称关系：实例：对称关系：A上的全域关系上的全域关系EA,恒等关系恒等关系IA和空关系和空关系反对称

20、关系：恒等关系反对称关系：恒等关系IA和空关系也是和空关系也是A上的反对称关系上的反对称关系.设设A1,2,3,R1,R2,R3和和R4都是都是A上的关系上的关系,其中其中 R1,，R2,R3,，R4,R1：对称和反对称；：对称和反对称；R2：只有对称；：只有对称；R3：只有反对称；：只有反对称；R4：不对称、不反对称：不对称、不反对称37传递性传递性定义定义7.13设设R为为A上的关系上的关系,若若 x y z(x,y,zARRR),则称则称R 是是A上的上的传递传递关系关系.实例：实例：A上的全域关系上的全域关系EA,恒等关系恒等关系IA和空关系和空关系，小于等小于等于和小于关系，整除关系

21、，包含与真包含关系于和小于关系，整除关系，包含与真包含关系设设A1,2,3,R1,R2,R3是是A上的关系上的关系,其中其中 R1,R2,R3R1和和R3是是A上的传递关系上的传递关系,R2不是不是A上的传递关系上的传递关系.38关系性质成立的充要条件关系性质成立的充要条件定理定理7.9设设R为为A上的关系上的关系,则则(1)R 在在A上自反当且仅当上自反当且仅当 IA R(2)R 在在A上反自反当且仅当上反自反当且仅当 RIA=(3)R 在在A上对称当且仅当上对称当且仅当 R=R 1(4)R 在在A上反对称当且仅当上反对称当且仅当 RR 1 IA(5)R 在在A上传递当且仅当上传递当且仅当

22、R R R 39证明证明证明证明只证只证(1)、(3)、(4)、(5)(1)必要性必要性任取任取,由于由于R 在在A上自反必有上自反必有IA x,yAx=y R从而证明了从而证明了IA R充分性充分性.任取任取x,有有xA IA R因此因此R 在在A上是自反的上是自反的.40证明证明(3)必要性必要性.任取任取,R R R 1所以所以R=R 1充分性充分性.任取任取,由由R=R 1得得R R 1R所以所以R在在A上是对称的上是对称的41证明证明(4)必要性必要性.任取任取,有有RR 1RR 1RR x=y x,y AIA这就证明了这就证明了RR 1 IA充分性充分性.任取任取,RR RR 1R

23、R 1IAx=y从而证明了从而证明了R在在A上是反对称的上是反对称的.42证明证明(5)必要性必要性.任取任取有有R R t(RR)R所以所以R R R充分性充分性.任取任取,R,则则RR R R R所以所以R 在在A上是传递的上是传递的43自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性集合集合IA RRIA=R=R 1RR 1 IAR R R关系关系矩阵矩阵主对角主对角线元素线元素全是全是1主对角线主对角线元素全是元素全是0矩阵是矩阵是对称矩阵对称矩阵若若rij1,且且ij,则则rji0M2中中1位置位置,M中相应中相应位置都是位置都是1关系关系图图每个顶每个顶点都有点

24、都有环环每个顶点每个顶点都没有环都没有环两点之间两点之间有边有边,是是一对方向一对方向相反的边相反的边两点之间有两点之间有边边,是一条是一条有向边有向边点点xi到到xj有有边边,xj 到到xk有边有边,则则xi到到xk也有边也有边关系性质的三种等价条件关系性质的三种等价条件44自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性R1 1R1R2R1R2R1 R2R1 R2关系的性质和运算之间的联系关系的性质和运算之间的联系457.5关系的闭包关系的闭包主要内容主要内容l闭包定义闭包定义l闭包的构造方法闭包的构造方法集合表示集合表示矩阵表示矩阵表示图表示图表示l闭包的性质闭包的性

25、质46闭包定义闭包定义定义定义7.14设设R是非空集合是非空集合A上的关系上的关系,R的的自反自反(对称对称或或传递传递)闭闭包包是是A上的关系上的关系R,使得使得R 满足以下条件：满足以下条件：(1)R 是自反的是自反的(对称的或传递的对称的或传递的)(2)R R(3)对对A上任何包含上任何包含R的自反的自反(对称或传递对称或传递)关系关系R 有有RR R的自反闭包记作的自反闭包记作r(R),对称闭包记作对称闭包记作s(R),传递闭包记作传递闭包记作t(R).定理定理7.10设设R为为A上的关系上的关系,则有则有(1)r(R)=RR0(2)s(R)=RR 1(3)t(R)=RR2R3说明：对

26、有穷集说明：对有穷集A(|A|=n)上的关系上的关系,(3)中的并最多不超过中的并最多不超过Rn47证明证明证证只证只证(1)和和(3).(1)由由IA=R0 RR0知知RR0是自反的是自反的,且满足且满足R RR0设设R 是是A上包含上包含R的自反关系的自反关系,则有则有R R 和和IA R .从而有从而有RR0 R.RR0满足闭包定义满足闭包定义,所以所以r(R)=RR0.(1)先证先证RR2 t(R)成立成立.用归纳法证明对任意正整数用归纳法证明对任意正整数n 有有Rn t(R).n=1时有时有R1=R t(R).假设假设Rn t(R)成立成立,那么对任意的那么对任意的Rn+1=Rn R

27、 t(RnR)t(t(R)t(R)t(R)这就证明了这就证明了Rn+1 t(R).由归纳法命题得证由归纳法命题得证.48证明证明再证再证t(R)RR2成立成立,为此只须证明为此只须证明RR2传递传递.任取任取,则则RR2RR2 t(Rt)s(Rs)t s(Rt Rs)t s(Rt+s)RR2从而证明了从而证明了RR2是传递的是传递的.49闭包的矩阵表示和图表示闭包的矩阵表示和图表示设关系设关系R,r(R),s(R),t(R)的关系矩阵分别为的关系矩阵分别为M,Mr,Ms 和和Mt 则则Mr=M+E Ms=M+M Mt=M+M2+M3+E 是单位矩阵是单位矩阵,M 是是转置矩阵，相加时使用转置矩

28、阵，相加时使用逻辑加逻辑加.设关系设关系R,r(R),s(R),t(R)的关系图分别记为的关系图分别记为G,Gr,Gs,Gt,则则Gr,Gs,Gt 的顶点集与的顶点集与G 的顶点集相等的顶点集相等.除了除了G 的边以外的边以外,以下以下述述方法添加新的边：方法添加新的边：(1)考察考察G 的每个顶点的每个顶点,若没环就加一个环，得到若没环就加一个环，得到Gr(2)考察考察G 的每条边的每条边,若有一条若有一条xi 到到xj 的单向边的单向边,ij,则在则在G中加一条中加一条xj 到到xi 的反向边的反向边,得到得到Gs(3)考察考察G 的每个顶点的每个顶点xi,找找xi 可达的所有顶点可达的所

29、有顶点xj(允许允许i=j)，如果没有从如果没有从xi 到到xj的边的边,就加上这条边就加上这条边,得到图得到图Gt50实例实例例例9设设A=a,b,c,d,R=,R和和r(R),s(R),t(R)的关系图如下图所示的关系图如下图所示.Rr(R)s(R)t(R)51闭包的性质闭包的性质定理定理7.11设设R是非空集合是非空集合A上的关系上的关系,则则(1)R是自反的当且仅当是自反的当且仅当r(R)=R.(2)R是对称的当且仅当是对称的当且仅当s(R)=R.(3)R是传递的当且仅当是传递的当且仅当t(R)=R.定理定理7.12设设R1和和R2是非空集合是非空集合A上的关系上的关系,且且R1 R2

30、,则则(1)r(R1)r(R2)(2)s(R1)s(R2)(3)t(R1)t(R2)证明证明 略略52定理定理7.13设设R是非空集合是非空集合A上的关系上的关系,(1)若若R是自反的是自反的,则则s(R)与与t(R)也是自反的也是自反的(2)若若R是对称的是对称的,则则r(R)与与t(R)也是对称的也是对称的(3)若若R是传递的是传递的,则则r(R)是传递的是传递的.说明：如果需要进行多个闭包运算，比如求说明：如果需要进行多个闭包运算，比如求R的自反、对的自反、对称、传递的闭包称、传递的闭包tsr(R)，运算顺序如下：，运算顺序如下：tsr(R)=rts(R)=trs(R)闭包的性质闭包的性

31、质证明证明 略略537.6 等价关系与划分等价关系与划分主要内容主要内容l等价关系的定义与实例等价关系的定义与实例l等价类及其性质等价类及其性质l商集与集合的划分商集与集合的划分l等价关系与划分的一一对应等价关系与划分的一一对应54等价关系的定义与实例等价关系的定义与实例定义定义7.15设设R为非空集合上的关系为非空集合上的关系.如果如果R是自反的、对称的和是自反的、对称的和传递的传递的,则称则称R为为A上的上的等价关系等价关系.设设R 是一个等价关系是一个等价关系,若若R,称称x等价于等价于y,记做记做xy.实例实例设设A=1,2,8,如下定义如下定义A上的关系上的关系R：R=|x,yAx

32、y(mod3)其中其中x y(mod3)叫做叫做x与与y 模模3相等相等,即即x除以除以3的余数与的余数与y除以除以3的余数相等的余数相等.不难验证不难验证R 为为A上的等价关系上的等价关系,因为因为(1)xA,有有 x x(mod3)(2)x,yA,若若x y(mod3),则有则有y x(mod3)(3)x,y,zA,若若x y(mod3),y z(mod3),则有则有x z(mod3)55模模 3等价关系的关系图等价关系的关系图等价关系的实例等价关系的实例56等价类定义等价类定义定义定义7.16设设R为非空集合为非空集合A上的等价关系上的等价关系,xA，令，令xR=y|yAxRy称称xR

33、为为x关于关于R的等价类的等价类,简称为简称为x的的等价类等价类,简记为简记为x或或实例实例A=1,2,8上模上模3等价关系的等价类：等价关系的等价类：1=4=7=1,4,72=5=8=2,5,83=6=3,657等价类的性质等价类的性质定理定理7.14设设R是非空集合是非空集合A上的等价关系上的等价关系,则则(1)x A,x是是A的非空子集的非空子集(2)x,y A,如果如果xRy,则则x=y(3)x,y A,如果如果x y,则则x与与y不交不交(4)x|x A=A证证(1)由定义由定义,x A有有x A.又又x x,即即x非空非空.(2)任取任取z,则有则有zxR R R R R R从而证

34、明了从而证明了zy.综上所述必有综上所述必有x y.同理可证同理可证y x.这就得到了这就得到了x=y.58证明证明(3)假设假设xy,则存在则存在z xy,从而有从而有z xz y,即即 R R成立成立.根据根据R的对称性和传递性必有的对称性和传递性必有 R,与与xy矛盾矛盾(4)先证先证x|x A A.任取任取y,y x|x A x(x Ay x)y xx A y A 从而有从而有x|xA A再证再证A x|xA.任取任取y,y A y yy A yx|x A从而有从而有x|xA A成立成立.综上所述得综上所述得x|x A=A.59商集与划分商集与划分定义定义7.18设设A为非空集合为非空

35、集合,若若A的子集族的子集族(P(A)满足满足:(1)(2)x y(x,y xyxy=)(3)=A则称则称是是A的一个的一个划分划分,称称中的元素为中的元素为A的的划分块划分块.60划分实例划分实例例例10设设Aa,b,c,d,给定给定 1,2,3,4,5,6如下：如下：1=a,b,c,d 2=a,b,c,d 3=a,a,b,c,d 4=a,b,c 5=,a,b,c,d 6=a,a,b,c,d 则则 1和和 2是是A的划分的划分,其他都不是其他都不是A的划分的划分.61例例11给出给出A1,2,3上所有的等价关系上所有的等价关系实例实例1 123 31 1 123 351 123 321 12

36、3 341 123 331对应对应EA,5对应对应IA,2,3和和4分别对应分别对应R2,R3和和R4.R2=,IAR3=,IAR4=,IA解解先做出先做出A的划分的划分,从左到右分别记作从左到右分别记作 1,2,3,4,5.62例例12给出给出A1,2,3,4上所有的等价关系上所有的等价关系实例实例1 123 31 1 123 351 123 321 123 341 123 331对应对应EA,5对应对应IA,2,3和和4分别对应分别对应R2,R3和和R4.R2=,IAR3=,IAR4=,IA解解先做出先做出A的划分的划分,从左到右分别记作从左到右分别记作 1,2,3,4,5.63例例12给

37、出给出A1,2,3,4上所有的等价关系上所有的等价关系实例实例1对应对应EA ,2,3,4和和5分别对应分别对应R2,R3，R4和和R5R2=,IAR3=,IAR4=,IAR5=,IA解解 先做出先做出A的划分的划分,可分别记作可分别记作 1 15.1 123 34 411 123 334 41 123 324 41 123 344 41 123 34 4 564例例12给出给出A1,2,3,4上所有的等价关系上所有的等价关系实例实例(续续)6,7,8和和9分别对应分别对应R6,R7,R8和和R9R6=,IAR7=,IAR8=,IAR9=IA解解先做出先做出A的划分的划分,可分别记作可分别记作

38、 1 9.81 123 34 41 123 34 461 123 374 41 123 34 49657.7偏序关系偏序关系主要内容主要内容l偏序关系偏序关系偏序关系的定义偏序关系的定义偏序关系的实例偏序关系的实例l偏序集与哈斯图偏序集与哈斯图l偏序集中的特殊元素及其性质偏序集中的特殊元素及其性质极大元、极小元、最大元、最小元极大元、极小元、最大元、最小元上界、下界、最小上界、最大下界上界、下界、最小上界、最大下界66定义与实例定义与实例定义定义7.19偏序关系偏序关系：非空集合：非空集合A上的自反、反对称和传递的关系，上的自反、反对称和传递的关系，记作记作.设设 为偏序关系为偏序关系,如果如

39、果,则记作则记作x y,读作读作x“小于或等于小于或等于”y.实例实例集合集合A上的恒等关系上的恒等关系IA是是A上的偏序关系上的偏序关系.小于或等于关系小于或等于关系,整除关系和包含关系也是相应集合上的偏整除关系和包含关系也是相应集合上的偏序关系序关系.67相关概念相关概念定义定义7.20设设R 为非空集合为非空集合A上的偏序关系上的偏序关系,(1)x,yA,x与与y可比可比x yy x (2)任取元素任取元素x 和和y,可能有下述几种情况发生：可能有下述几种情况发生：x y(或或y x),xy,x与与y不是可比的不是可比的定义定义7.21R 为非空集合为非空集合A上的偏序关系上的偏序关系,

40、(1)x,yA,x与与y都是可比的，则称都是可比的，则称R为为全序全序（或线序）（或线序）实例：数集上的小于或等于关系是全序关系实例：数集上的小于或等于关系是全序关系,整除关系不是正整除关系不是正整数集合上的全序关系整数集合上的全序关系定义定义7.22x,yA,如果如果x y 且不存在且不存在zA 使得使得x z y,则称则称y覆盖覆盖x.例如例如1,2,4,6集合上整除关系集合上整除关系,2覆盖覆盖1,4和和6覆盖覆盖2,4不覆盖不覆盖1.68相关概念相关概念定义定义7.22x,yA,如果如果x y 且不存在且不存在zA 使得使得x z y,则称则称y覆盖覆盖x.盖住关系盖住关系:CovA=

41、|xA yA y 覆盖覆盖x例如例如1,2,4,6集合上整除关系集合上整除关系,2覆盖覆盖1,4和和6覆盖覆盖2,4不覆盖不覆盖1.上例的盖住关系为上例的盖住关系为:CovA=,69例例1求关系图和哈斯图求关系图和哈斯图设设A=2,3,6,12,24,36，“”是是A上的整除关系上的整除关系R，写出盖住关系，并画出其一般的关系图和哈斯图。写出盖住关系，并画出其一般的关系图和哈斯图。解解:由题意可得整除关系由题意可得整除关系R如下：如下：R=,。从而得出该偏序集从而得出该偏序集的一般关系图如下：的一般关系图如下：70例例1求关系图和哈斯图求关系图和哈斯图(续续)关系图关系图哈斯图哈斯图2 23

42、36 61212363624242 23 36 612123636242471偏序集与哈斯图偏序集与哈斯图定义定义7.23集合集合A和和A上的偏序关系上的偏序关系 一起叫做一起叫做偏序集偏序集,记作记作.实例实例:,哈斯图哈斯图:利用偏序关系的自反、反对称、传递性进行简化的利用偏序关系的自反、反对称、传递性进行简化的关系图关系图特点：特点：(1)每个结点没有环每个结点没有环(2)两个连通的结点之间的序关系通过结点位置的高低表两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前示，位置低的元素的顺序在前(3)具有覆盖关系的两个结点之间连边具有覆盖关系的两个结点之间连边72实例

43、实例例例12偏序集偏序集和和的的哈斯图哈斯图.73例例13已知偏序集已知偏序集的哈斯图如下图所示的哈斯图如下图所示,试求出集合试求出集合A和关系和关系R的表达式的表达式.解解A=a,b,c,d,e,f,g,h R=,IA实例实例74偏序集中的特殊元素偏序集中的特殊元素定义定义7.24设设为偏序集为偏序集,B A,yB(1)若若 x(xBy x)成立成立,则称则称y 为为B的的最小元最小元(2)若若 x(xBx y)成立成立,则称则称y 为为B的的最大元最大元(3)若若 x(xBx yx=y)成立成立,则称则称y 为为B的的极小元极小元(4)若若 x(xBy xx=y)成立成立,则称则称y 为为

44、B的的极大元极大元性质：性质：(1)对于有穷集，极小元和极大元一定存在，可能存在多个对于有穷集，极小元和极大元一定存在，可能存在多个.(2)最小元和最大元不一定存在，如果存在一定惟一最小元和最大元不一定存在，如果存在一定惟一.(3)最小元一定是极小元；最大元一定是极大元最小元一定是极小元；最大元一定是极大元.(4)孤立结点既是极小元，也是极大元孤立结点既是极小元，也是极大元.75定义定义7.25设设为偏序集为偏序集,B A,yA(1)若若 x(xBx y)成立成立,则称则称y为为B的的上界上界(2)若若 x(xBy x)成立成立,则称则称y为为B的的下界下界(3)令令Cy|y为为B的上界的上界

45、,C的最小元为的最小元为B的的最小上界最小上界或或上确上确界界(4)令令Dy|y为为B的下界的下界,D的最大元为的最大元为B的的最大下界最大下界或或下确下确界界偏序集中的特殊元素偏序集中的特殊元素性质：性质：(1)下界、上界、下确界、上确界不一定存在下界、上界、下确界、上确界不一定存在(2)下界、上界存在不一定惟一下界、上界存在不一定惟一(3)下确界、上确界如果存在，则惟一下确界、上确界如果存在，则惟一(4)集合的最小元是其下确界，最大元是其上确界；反之不对集合的最小元是其下确界，最大元是其上确界；反之不对.76实例实例例例14设偏序集设偏序集，求，求A的极小元、最小元、极大元、最的极小元、最

46、小元、极大元、最大元，设大元，设Bb,c,d,求求B的下界、上界、下确界、上确界的下界、上界、下确界、上确界.解解极小元：极小元：a,b,c,g；极大元：极大元：a,f,h；没有最小元与最大元没有最小元与最大元.B的下界和最大下界都不存在；的下界和最大下界都不存在；上界有上界有d 和和f,最小上界为最小上界为d.77实例实例例例15设设X为集合为集合,AP(X)X,且且A.若若|X|=n,n2.问：问：(1)偏序集偏序集是否存在最大元？是否存在最大元？(2)偏序集偏序集是否存在最小元？是否存在最小元？(3)偏序集偏序集中极大元和极小元的一般形式是什么？中极大元和极小元的一般形式是什么？并说明理

47、由并说明理由.解解(1)不存在最小元和最大元不存在最小元和最大元,因为因为n2.(2)的极小元就是的极小元就是X 的所有单元集的所有单元集,即即x,xX.(3)的极大元恰好比的极大元恰好比X 少一个元素少一个元素,即即X x,xX.78第七章第七章 习题课习题课主要内容主要内容l有序对与笛卡儿积的定义与性质有序对与笛卡儿积的定义与性质l二元关系、从二元关系、从A到到B的关系、的关系、A上的关系上的关系l关系的表示法：关系表达式、关系矩阵、关系图关系的表示法：关系表达式、关系矩阵、关系图l关系的运算：定义域、值域、域、逆、合成、限制、像、关系的运算：定义域、值域、域、逆、合成、限制、像、幂幂l关

48、系运算的性质关系运算的性质:A上关系的自反、反自反、对称、反对上关系的自反、反自反、对称、反对称、传递的性质称、传递的性质lA上关系的自反、对称、传递闭包上关系的自反、对称、传递闭包lA上的等价关系、等价类、商集与上的等价关系、等价类、商集与A的划分的划分lA上的偏序关系与偏序集上的偏序关系与偏序集79基本要求基本要求l熟练掌握关系的三种表示法熟练掌握关系的三种表示法l能够判定关系的性质（等价关系或偏序关系）能够判定关系的性质（等价关系或偏序关系）l掌握含有关系运算的集合等式掌握含有关系运算的集合等式l掌握等价关系、等价类、商集、划分、哈斯图、偏序集等掌握等价关系、等价类、商集、划分、哈斯图、

49、偏序集等概念概念l计算计算A B,domR,ranR,fldR,R 1,R S,Rn,r(R),s(R),t(R)l求等价类和商集求等价类和商集A/Rl给定给定A的划分的划分，求出，求出 所对应的等价关系所对应的等价关系l求偏序集中的极大元、极小元、最大元、最小元、上界、求偏序集中的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界下界、上确界、下确界l掌握基本的证明方法掌握基本的证明方法证明涉及关系运算的集合等式证明涉及关系运算的集合等式证明关系的性质、证明关系是等价关系或偏序关系证明关系的性质、证明关系是等价关系或偏序关系80练习练习11设设A=1,2,3,R=|x,y A且且x+

50、2y 6，S=,求求:(1)R的集合表达式的集合表达式(2)R 1(3)domR,ranR,fldR(4)R S,R3(5)r(R),s(R),t(R)81解答解答(1)R=,(2)R 1=,(3)domR=1,2,3,ranR=1,2,fldR=1,2,3(4)R S=,R3=,(5)r(R)=,s(R)=,t(R)=,82练习练习22设设A=1,2,3,4，在，在A A上定义二元关系上定义二元关系R：,R x+y=u+v，求求R导出的划分导出的划分.A A=,根据根据中的中的x+y=2,3,4,5,6,7,8将将A划分成等划分成等（AA）/R=,833设设R是是Z上的模上的模n 等价关系等

51、价关系,即即 x yx y(modn),试给出由试给出由R确定的确定的Z的划分的划分.练习练习3解解设除以设除以n 余数为余数为r 的整数构成等价类的整数构成等价类r，则，则r=kn+r|k Z,r=0,1,n 1=r|r=0,1,n 1 84图11练习练习44设偏序集设偏序集的哈斯图如图所示的哈斯图如图所示.(1)写出写出A和和R的集合表达式的集合表达式(2)求该偏序集中的极大元、极小元、最大元、最小元求该偏序集中的极大元、极小元、最大元、最小元解解(1)A=a,b,c,d,e R=,IA(2)极大元和最大元是极大元和最大元是a,极小元极小元是是d,e；没有最小元没有最小元.abcde85练

52、习练习55设设R是是A上的二元关系，上的二元关系，设设 S=|c(R R).证明如果证明如果R是等价关系，则是等价关系，则S也是等价关系。也是等价关系。证证 R是是A上的等价关系上的等价关系.(1)证自反证自反任取任取x,x A R x(R R)S(2)证对称证对称任取任取,S c(R R)c(R R)S(3)证传递证传递任取任取,S S c(R R)d(R R)R R S866设偏序集设偏序集和和，定义，定义A B上二元关系上二元关系T:TxRu ySv证明证明T为偏序关系为偏序关系.练习练习6证证(1)自反性自反性任取任取,A B x A y B xRx ySy T(2)反对称性反对称性任

53、取任取,T TxRu ySv uRx vSy(xRu uRx)(ySv vSy)x=u y=v=(3)传递性传递性任取任取,T TxRu ySv uRw vSt(xRu uRw)(ySv vSt)xRw yStT 87关系性质的证明方法关系性质的证明方法1.证明证明R在在A上自反上自反任取任取x,x A.R前提前提推理过程推理过程结论结论2.证明证明R在在A上对称上对称任取任取，R.R前提前提推理过程推理过程结论结论883.证明证明R在在A上反对称上反对称任取任取，R R.x=y前提前提推理过程推理过程结论结论4.证明证明R在在A上传递上传递任取任取,，R R.R前提前提推理过程推理过程结论结

54、论关系性质的证明方法关系性质的证明方法897R,S为为A上的关系，证明上的关系，证明R S t(R)t(S)练习练习7证证 只需证明对于任意正整数只需证明对于任意正整数n,Rn Sn.对对n归纳归纳.n=1,显然为真显然为真.假设对于假设对于n，命题为真，任取，命题为真，任取 Rn+1 Rn R t(Rn R)t(Sn S)Sn S Sn+1 90l数学归纳法（主要用于幂运算）数学归纳法（主要用于幂运算）l证明中用到关系运算的定义和公式证明中用到关系运算的定义和公式,如：如：x domR y(R)y ranR x(R)R R 1 R S t(R S)R A x A R y R A x(x A R)r(R)=R IA s(R)=R R 1 t(R)=R R2 关系等式或包含式的证明方法关系等式或包含式的证明方法91