离散数学屈婉玲第七章-PPT.ppt

离散数学屈婉玲第七章7.1有序对与笛卡儿积有序对与笛卡儿积定义定义7.1由两个元素由两个元素x 和和y，按照一定的顺序组成的二元组，按照一定的顺序组成的二元组称为有序对，记作称为有序对，记作.有序对性质有序对性质:(1)有序性有序性（当（当x y时）时）(2)与与相等的充分必要条件是相等的充分必要条件是=x=u y=v.2笛卡儿积笛卡儿积定义定义7.2设设A,B为集合，为集合，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 就是空集就是空集.A=B=(5)A C B DA B C D.(6)若若|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如果一个集合满足以下条件之一：如果一个集合满足以下条件之一：(1)集合非空集合非空,且它的元素都是有序对且它的元素都是有序对(2)集合是空集集合是空集则称该集合为一个二元关系则称该集合为一个二元关系,简称为关系，记作简称为关系，记作R.如果如果R,可记作可记作xRy；如果；如果 R,则记作则记作xy实例：实例：R=,S=,a,b.R是二元关系是二元关系,当当a,b不是有序对时，不是有序对时，S不是二元关系不是二元关系根据上面的记法，可以写根据上面的记法，可以写1R2,aRb,a c等等.7大家应该也有点累了，稍作休息大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流8A到到B的关系与的关系与A上的关系上的关系定义定义7.4设设A,B为集合为集合,AB的任何子集所定义的二元关系叫做从的任何子集所定义的二元关系叫做从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个不同的二元关系个不同的二元关系.9A上重要关系的实例上重要关系的实例定义定义7.5设设A 为集合为集合,(1)是是A上的关系，称为空关系上的关系，称为空关系(2)全域关系全域关系EA=|xAyA=AA 恒等关系恒等关系IA=|xA小于等于关系小于等于关系 LA=|x,yAxy,A为实数子集为实数子集 整除关系整除关系DB=|x,yBx整除整除y,A为非为非0整数子集整数子集 包含关系包含关系 R=|x,yAx y,A是集合族是集合族.10实例实例例如例如,A=1,2,则则EA=,IA=,例如例如A=1,2,3,B=a,b,则则LA=,DA=,例如例如A=P(B)=,a,b,a,b,则则A上的包含关系是上的包含关系是R=,类似的还可以定义：类似的还可以定义：大于等于关系大于等于关系,小于关系小于关系,大于关系大于关系,真包含关系等真包含关系等.11关系的表示关系的表示1.关系矩阵关系矩阵若若A=x1,x2,xn，R是是A上的关系，上的关系，R的关系矩阵是布尔的关系矩阵是布尔矩阵矩阵MR=(rij)n n,其中其中rij=1 R2.关系图关系图若若A=x1,x2,xm，R是从是从A上的关系，上的关系，R的关系图是的关系图是GR=,其中其中A为结点集，为结点集，R为边集为边集.如果如果属于属于关系关系R，在图中就有一条从，在图中就有一条从xi 到到xj 的有向边的有向边.注意：注意：l关系矩阵适合表示有穷集关系矩阵适合表示有穷集A上的关系（可推广为从上的关系（可推广为从A到到B的的关系）关系）l关系图适合表示有穷集关系图适合表示有穷集A上的关系上的关系12实例实例例例4 A=1,2,3,4,R=,R的关系矩阵的关系矩阵MR和关系图和关系图GR如下：如下：137.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,414关系运算关系运算(逆与合成逆与合成)定义定义7.7关系的逆运算关系的逆运算 R 1=|R 定义定义7.8关系的合成运算关系的合成运算 F G=|t(F G)例例6R=,S=,R 1=,R S=,S R=,15合成的图示法合成的图示法利用图示（不是关系图）方法求合成利用图示（不是关系图）方法求合成R S=,S R=,16关系运算关系运算(限制与像限制与像)定义定义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 ranR17实例实例例例7设设R=,则则R 1=,R=R 2,3=,R1=2,3R=R3=218关系运算的性质关系运算的性质定理定理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.19定理定理7.2设设F,G,H是任意的关系是任意的关系,则则(1)(F G)H=F(G H)(2)(F G)1=G 1 F 1关系运算的性质关系运算的性质证证(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)20证明证明(2)任取任取,(F G)1F G t(FG)t(G 1F 1)G 1 F 1所以所以(F G)1=G 1 F 121关系运算的性质关系运算的性质定理定理7.3设设R为为A上的关系上的关系,则则R IA=IA R=R证证任取任取R IA t(RIA)t(Rt=yyA)R22关系运算的性质关系运算的性质定理定理7.4(1)F(G H)=F GF H (2)(GH)F=G FH F(3)F(GH)F GF H (4)(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 H23推广推广定理定理7.4的结论可以推广到有限多个关系的结论可以推广到有限多个关系R(R1R2Rn)=R R1R R2R Rn(R1R2Rn)R=R1 RR2 RRn RR(R1R2Rn)R R1R R2R Rn(R1R2Rn)R R1 RR2 RRn R24关系运算的性质关系运算的性质定理定理7.5设设F 为关系为关系,A,B为集合为集合,则则(1)F (AB)=F AF B(2)F AB=F AF B(3)F (AB)=F AF B(4)F AB F AF B25证明证明证证只证只证(1)和和(4).(1)任取任取F (AB)FxABF(xAxB)(FxA)(FxB)F AF BF AF B所以有所以有F (AB)=F AF B.26证明证明(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.27关系的幂运算关系的幂运算定义定义7.10设设R 为为A 上的关系上的关系,n为自然数为自然数,则则R 的的n 次幂定义为：次幂定义为：(1)R0=|xA=IA(2)Rn+1=Rn R注意：注意：l对于对于A上的任何关系上的任何关系R1和和R2都有都有R10=R20=IAl对于对于A上的任何关系上的任何关系R 都有都有R1=R28例例8设设A=a,b,c,d,R=,求求R的各次幂的各次幂,分别用矩阵和关系图表示分别用矩阵和关系图表示.解解 R 与与 R2的关系矩阵分别是：的关系矩阵分别是：幂的求法幂的求法29R3和和R4的矩阵是：的矩阵是：因此因此M4=M2,即即R4=R2.因此可以得到因此可以得到R2=R4=R6=，R3=R5=R7=R0的关系矩阵是的关系矩阵是幂的求法幂的求法30关系图关系图R0,R1,R2,R3,的关系图如下图所示的关系图如下图所示.R0R1R2=R4=R3=R5=31幂运算的性质幂运算的性质定理定理7.6设设A 为为n 元集元集,R 是是A上的关系上的关系,则存在自然数则存在自然数s 和和t,使得使得Rs=Rt.证证R 为为A上的关系上的关系,由于由于|A|=n,A上的不同关系只有上的不同关系只有个个.列出列出R 的各次幂的各次幂 R0,R1,R2,必存在自然数必存在自然数s 和和t 使得使得Rs=Rt 32定理定理7.7设设R 是是A上的关系上的关系,m,nN,则则(1)Rm Rn=Rm+n(2)(Rm)n=Rmn幂运算的性质幂运算的性质证证用归纳法用归纳法(1)对于任意给定的对于任意给定的mN,施归纳于施归纳于n.若若n=0,则有则有Rm R0=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.33证明证明(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.34定理定理7.8设设R是是A上的关系上的关系,若存在自然数若存在自然数s,t(st)使得使得Rs=Rt,则则(1)对任何对任何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由归纳法命题得证由归纳法命题得证.35证明证明(3)任取任取 qN,若若 q t,显然有显然有 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.367.4关系的性质关系的性质定义定义7.11设设R 为为A上的关系上的关系,(1)若若 x(xA R),则称则称R 在在A 上是自反的上是自反的.(2)若若 x(xA R),则称则称R 在在A 上是反自反的上是反自反的.实例：实例：自反：全域关系自反：全域关系EA,恒等关系恒等关系IA,小于等于关系小于等于关系LA,整除关系整除关系DA反自反：实数集上的小于关系、幂集上的真包含关系反自反：实数集上的小于关系、幂集上的真包含关系.A=1,2,3,R1,R2,R3是是A上的关系上的关系,其中其中 R1,R2,R3R2自反自反，R3反自反，反自反，R1既不是自反的也不是反自反的既不是自反的也不是反自反的.37对称性与反对称性对称性与反对称性定义定义7.12设设R 为为A上的关系上的关系,(1)若若 x y(x,yARR),则称则称R 为为A上对上对称的关系称的关系.(2)若若 x y(x,yARRx=y),则称则称R 为为A上的反对称关系上的反对称关系.实例：对称关系：实例：对称关系：A上的全域关系上的全域关系EA,恒等关系恒等关系IA和空关系和空关系反对称关系：恒等关系反对称关系：恒等关系IA和空关系也是和空关系也是A上的反对称关系上的反对称关系.设设A1,2,3,R1,R2,R3和和R4都是都是A上的关系上的关系,其中其中 R1,，R2,R3,，R4,R1：对称和反对称；：对称和反对称；R2：只有对称；：只有对称；R3：只有反对称；：只有反对称；R4：不对称、不反对称：不对称、不反对称38传递性传递性定义定义7.13设设R为为A上的关系上的关系,若若 x y z(x,y,zARRR),则称则称R 是是A上的传递关系上的传递关系.实例：实例：A上的全域关系上的全域关系EA,恒等关系恒等关系IA和空关系和空关系，小于等小于等于和小于关系，整除关系，包含与真包含关系于和小于关系，整除关系，包含与真包含关系设设A1,2,3,R1,R2,R3是是A上的关系上的关系,其中其中 R1,R2,R3R1和和R3是是A上的传递关系上的传递关系,R2不是不是A上的传递关系上的传递关系.39关系性质成立的充要条件关系性质成立的充要条件定理定理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上传递当且仅当上传递当且仅当 R R R 40证明证明证明证明只证只证(1)、(3)、(4)、(5)(1)必要性必要性任取任取,由于由于R 在在A上自反必有上自反必有IA x,yAx=y R从而证明了从而证明了IA R充分性充分性.任取任取x,有有xA IA R因此因此R 在在A上是自反的上是自反的.41证明证明(3)必要性必要性.任取任取,R R R 1所以所以R=R 1充分性充分性.任取任取,由由R=R 1得得R R 1R所以所以R在在A上是对称的上是对称的42证明证明(4)必要性必要性.任取任取,有有RR 1RR 1RR x=y x,y AIA这就证明了这就证明了RR 1 IA充分性充分性.任取任取,RR RR 1RR 1IAx=y从而证明了从而证明了R在在A上是反对称的上是反对称的.43证明证明(5)必要性必要性.任取任取有有R R t(RR)R所以所以R R R充分性充分性.任取任取,R,则则RR R R R所以所以R 在在A上是传递的上是传递的44关系性质的三种等价条件关系性质的三种等价条件45关系性质的判别关系性质的判别例例9判断下列各图的性质判断下列各图的性质(a)(b)(c)解：解：(a)对称对称(b)反自反、反对称、传递反自反、反对称、传递(c)自反、反对称自反、反对称46关系的性质和运算之间的联系关系的性质和运算之间的联系477.5关系的闭包关系的闭包主要内容主要内容l闭包定义闭包定义l闭包的构造方法闭包的构造方法集合表示集合表示矩阵表示矩阵表示图表示图表示l闭包的性质闭包的性质48闭包定义闭包定义定义定义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说明：对有穷集说明：对有穷集A(|A|=n)上的关系上的关系,(3)中的并最多不超过中的并最多不超过Rn49证明证明证证只证只证(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 t(RnR)t(t(R)t(R)t(R)这就证明了这就证明了Rn+1 t(R).由归纳法命题得证由归纳法命题得证.50证明证明再证再证t(R)RR2成立成立,为此只须证明为此只须证明RR2传递传递.任取任取,则则RR2RR2 t(Rt)s(Rs)t s(Rt Rs)t s(Rt+s)RR2从而证明了从而证明了RR2是传递的是传递的.51闭包的矩阵表示和图表示闭包的矩阵表示和图表示设关系设关系R,r(R),s(R),t(R)的关系矩阵分别为的关系矩阵分别为M,Mr,Ms 和和Mt 则则Mr=M+E Ms=M+M Mt=M+M2+M3+E 是单位矩阵是单位矩阵,M 是是转置矩阵，相加时使用逻辑加转置矩阵，相加时使用逻辑加.设关系设关系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 可达的所有顶点可达的所有顶点xj(允许允许i=j)，如果没有从如果没有从xi 到到xj的边的边,就加上这条边就加上这条边,得到图得到图Gt52实例实例例例9设设A=a,b,c,d,R=,R和和r(R),s(R),t(R)的关系图如下图所示的关系图如下图所示.Rr(R)s(R)t(R)53求传递闭包的算法求传递闭包的算法算法算法Warshall输人：输人：M（R的关系矩阵）的关系矩阵）输出：输出：MT（t(R)的关系矩阵）的关系矩阵）1MTM2fork1tondo3fori1tondo4forj1tondo5MTi,jMTi,j+MTi,k MTk,j54实例实例设设A=a,b,c,d,R=,R的传递闭包的矩阵如下：的传递闭包的矩阵如下：55闭包的性质闭包的性质定理定理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,则则(1)r(R1)r(R2)(2)s(R1)s(R2)(3)t(R1)t(R2)证明证明 略略56定理定理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)闭包的性质闭包的性质证明证明 略略577.6 等价关系与划分等价关系与划分主要内容主要内容l等价关系的定义与实例等价关系的定义与实例l等价类及其性质等价类及其性质l商集与集合的划分商集与集合的划分l等价关系与划分的一一对应等价关系与划分的一一对应587.6等价关系与划分等价关系与划分定义定义7.15设设R为非空集合上的关系为非空集合上的关系.如果如果R是自反的、对称的和是自反的、对称的和传递的传递的,则称则称R为为A上的等价关系上的等价关系.设设R 是一个等价关系是一个等价关系,若若R,称称x等价于等价于y,记做记做xy.实例实例设设A=1,2,8,如下定义如下定义A上的关系上的关系R：R=|x,yAx 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)59模模 3等价关系的关系图等价关系的关系图等价关系的实例等价关系的实例60等价类定义等价类定义定义定义7.16设设R为非空集合为非空集合A上的等价关系上的等价关系,xA，令，令xR=y|yAxRy称称xR 为为x关于关于R的等价类的等价类,简称为简称为x的等价类的等价类,简记为简记为x或或实例实例A=1,2,8上模上模3等价关系的等价类：等价关系的等价类：1=4=7=1,4,72=5=8=2,5,83=6=3,661等价类的性质等价类的性质定理定理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从而证明了从而证明了zy.综上所述必有综上所述必有x y.同理可证同理可证y x.这就得到了这就得到了x=y.62证明证明(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.63商集与划分商集与划分定义定义7.17设设R 为非空集合为非空集合A上的等价关系上的等价关系,以以R 的所有等价的所有等价类作为元素的集合称为类作为元素的集合称为A关于关于R的商集的商集,记做记做A/R,A/R=xR|xA实例实例设设A=1,2,8，A关于模关于模3等价关系等价关系R的商集为的商集为A/R=1,4,7,2,5,8,3,6A关于恒等关系和全域关系的商集为：关于恒等关系和全域关系的商集为：A/IA=1,2,8，A/EA=1,2,8定义定义7.18设设A为非空集合为非空集合,若若A的子集族的子集族(P(A)满足满足:(1)(2)x y(x,y xyxy=)(3)=A则称则称是是A的一个划分的一个划分,称称中的元素为中的元素为A的划分块的划分块.64划分实例划分实例例例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的划分的划分.65例例11给出给出A1,2,3上所有的等价关系上所有的等价关系实例实例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.667.7偏序关系偏序关系主要内容主要内容l偏序关系偏序关系偏序关系的定义偏序关系的定义偏序关系的实例偏序关系的实例l偏序集与哈斯图偏序集与哈斯图l偏序集中的特殊元素及其性质偏序集中的特殊元素及其性质极大元、极小元、最大元、最小元极大元、极小元、最大元、最小元上界、下界、最小上界、最大下界上界、下界、最小上界、最大下界67定义与实例定义与实例定义定义7.19偏序关系：非空集合偏序关系：非空集合A上的自反、反对称和传递的关系，上的自反、反对称和传递的关系，记作记作.设设 为偏序关系为偏序关系,如果如果,则记作则记作x y,读作读作x“小于或等于小于或等于”y.实例实例集合集合A上的恒等关系上的恒等关系IA是是A上的偏序关系上的偏序关系.小于或等于关系小于或等于关系,整除关系和包含关系也是相应集合上的偏整除关系和包含关系也是相应集合上的偏序关系序关系.68相关概念相关概念定义定义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上的偏序关系上的偏序关系,(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.69偏序集与哈斯图偏序集与哈斯图定义定义7.23集合集合A和和A上的偏序关系上的偏序关系 一起叫做偏序集一起叫做偏序集,记作记作.实例实例:,哈斯图哈斯图:利用偏序关系的自反、反对称、传递性进行简化的利用偏序关系的自反、反对称、传递性进行简化的关系图关系图特点：特点：(1)每个结点没有环每个结点没有环(2)两个连通的结点之间的序关系通过结点位置的高低表两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前示，位置低的元素的顺序在前(3)具有覆盖关系的两个结点之间连边具有覆盖关系的两个结点之间连边70实例实例例例12偏序集偏序集和和的的哈斯图哈斯图.71例例13已知偏序集已知偏序集的哈斯图如下图所示的哈斯图如下图所示,试求出集合试求出集合A和关系和关系R的表达式的表达式.解解A=a,b,c,d,e,f,g,h R=,IA实例实例72偏序集中的特殊元素偏序集中的特殊元素定义定义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 为为B的极大元的极大元性质：性质：(1)对于有穷集，极小元和极大元一定存在，可能存在多个对于有穷集，极小元和极大元一定存在，可能存在多个.(2)最小元和最大元不一定存在，如果存在一定惟一最小元和最大元不一定存在，如果存在一定惟一.(3)最小元一定是极小元；最大元一定是极大元最小元一定是极小元；最大元一定是极大元.(4)孤立结点既是极小元，也是极大元孤立结点既是极小元，也是极大元.73定义定义7.25设设为偏序集为偏序集,B A,yA(1)若若 x(xBx y)成立成立,则称则称y为为B的上界的上界(2)若若 x(xBy x)成立成立,则称则称y为为B的下界的下界(3)令令Cy|y为为B的上界的上界,C的最小元为的最小元为B的最小上界或上确界的最小上界或上确界(4)令令Dy|y为为B的下界的下界,D的最大元为的最大元为B的最大下界或下确界的最大下界或下确界偏序集中的特殊元素偏序集中的特殊元素性质：性质：(1)下界、上界、下确界、上确界不一定存在下界、上界、下确界、上确界不一定存在(2)下界、上界存在不一定惟一下界、上界存在不一定惟一(3)下确界、上确界如果存在，则惟一下确界、上确界如果存在，则惟一(4)集合的最小元是其下确界，最大元是其上确界；反之不对集合的最小元是其下确界，最大元是其上确界；反之不对.74实例实例例例14设偏序集设偏序集，求，求A的极小元、最小元、极大元、最的极小元、最小元、极大元、最大元，设大元，设Bb,c,d,求求B的下界、上界、下确界、上确界的下界、上界、下确界、上确界.解解极小元：极小元：a,b,c,g；极大元：极大元：a,f,h；没有最小元与最大元没有最小元与最大元.B的下界和最大下界都不存在；的下界和最大下界都不存在；上界有上界有d 和和f,最小上界为最小上界为d.75实例实例例例15设设X为集合为集合,AP(X)X,且且A.若若|X|=n,n2.问：问：(1)偏序集偏序集是否存在最大元？是否存在最大元？(2)偏序集偏序集是否存在最小元？是否存在最小元？(3)偏序集偏序集中极大元和极小元的一般形式是什么？中极大元和极小元的一般形式是什么？并说明理由并说明理由.解解(1)不存在最小元和最大元不存在最小元和最大元,因为因为n2.(2)的极小元就是的极小元就是X 的所有单元集的所有单元集,即即x,xX.(3)的极大元恰好比的极大元恰好比X 少一个元素少一个元素,即即X x,xX.76调度问题调度问题有穷任务集有穷任务集T，m台相同的机器，台相同的机器，T上存在偏序上存在偏序，若，若t1 t2,任务任务t1完成后完成后t2才能开始才能开始 t T,l(t)是是t 需要的时间，需要的时间，d(t)是是t 的截止时间，的截止时间，l(t),d(t)Z+开始时间为开始时间为0，:T0,1,表示对任务集表示对任务集T 的一个调度，的一个调度，完成所有任务的时间：完成所有任务的时间：D=max(t)+l(t)|t T 可行调度可行调度 满足：满足：(1)t T,(t)+l(t)d(t)每个任务都在截止时间之前完成每个任务都在截止时间之前完成(2)i,0 i D,|t T|(t)i(t)+l(t)|m至多至多m个任务并行个任务并行(3)t,t T,t t(t)+l(t)(t)任务安排满足偏序任务安排满足偏序77寻找最优调度寻找最优调度112112t6t5t4t3t2t1t6t4t5t3t2t1D=6t6t4t5t3t2t1D=5例例16 m=2,T=t1,t2,t6l(ti)如图所示，如图所示，d(ti)=7拓扑排序拓扑排序:m=1，ti 都相等都相等78第七章第七章 习题课习题课主要内容主要内容l有序对与笛卡儿积的定义与性质有序对与笛卡儿积的定义与性质l二元关系、从二元关系、从A到到B的关系、的关系、A上的关系上的关系l关系的表示法：关系表达式、关系矩阵、关系图关系的表示法：关系表达式、关系矩阵、关系图l关系的运算：定义域、值域、域、逆、合成、限制、像、幂关系的运算：定义域、值域、域、逆、合成、限制、像、幂l关系运算的性质关系运算的性质:A上关系的自反、反自反、对称、反对称、上关系的自反、反自反、对称、反对称、传递的性质传递的性质lA上关系的自反、对称、传递闭包上关系的自反、对称、传递闭包lA上的等价关系、等价类、商集与上的等价关系、等价类、商集与A的划分的划分lA上的偏序关系与偏序集上的偏序关系与偏序集79基本要求基本要求l熟练掌握关系的三种表示法熟练掌握关系的三种表示法l能够判定关系的性质（等价关系或偏序关系）能够判定关系的性质（等价关系或偏序关系）l掌握含有关系运算的集合等式掌握含有关系运算的集合等式l掌握等价关系、等价类、商集、划分、哈斯图、偏序集等掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念概念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+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划分成等价类：划分成等价类：A/R=,833设设R是是Z上的模上的模n 等价关系等价关系,即即 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练习练习55设设R是是A上的二元关系，上的二元关系，设设 S=|c(R R).证明如果证明如果R是等价关系，则是等