离散数学-二元关系.ppt

主要内容主要内容l有序有序对对与笛卡儿与笛卡儿积积l二元关系的定二元关系的定义义与表示法与表示法l关系的运算关系的运算l关系的性关系的性质质l关系的关系的闭闭包包l等价关系与划分等价关系与划分l偏序关系偏序关系第七章第七章 二元关系二元关系1.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=jump3.笛卡儿笛卡儿积积的性的性质质(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|=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.6.7.2 二元关系二元关系定定义义7.3如果一个集合如果一个集合满满足以下条件之一：足以下条件之一：(1)集合非空集合非空,且它的元素都是有序且它的元素都是有序对对(2)集合是空集集合是空集则则称称该该集合集合为为一个一个二元关系二元关系,简简称称为为关系，关系，记记作作R.如果如果R,可可记记作作xRy；如果；如果 R,则记则记作作xRy实实例：例：R=,S=,a,b.R是二元关系是二元关系,当当a,b不是有序不是有序对时对时，S不是二元关系不是二元关系根据上面的根据上面的记记法，可以写法，可以写1R2,aRb,aSb等等.7.A到到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个不同的二元关系个不同的二元关系.jump8.A上重要关系的上重要关系的实实例例定定义义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是集合族是集合族.9.实实例例例如例如,A=1,2,则则EA=,IA=,例如例如A=1,2,3,B=a,b,则则LA=,DA=,例如例如A=P(B)=,a,b,a,b,则则A上的包含关系是上的包含关系是R=,类类似的似的还还可以定可以定义义：大于等于关系大于等于关系,小于关系小于关系,大于关系大于关系,真包含关系等真包含关系等.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为为有有穷穷集）集）l关系关系图图适合表示有适合表示有穷穷集集A上的关系上的关系11.实实例例例例4 A=1,2,3,4,R=,R的关系矩的关系矩阵阵MR和关系和关系图图GR如下：如下：jumpjump112.7.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 S=|y(R S)例例6R=,S=,R 1=,R S=,S R=,jump14.合成的合成的图图示法示法利用利用图图示（不是关系示（不是关系图图）方法求合成）方法求合成:R=,S=,则则：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)例例7设设R=,则则R 1=,R=R 2,3=,R1=2,3R=R3=2说说明：明：lR在在A上的上的限制限制R A是是R 的子关系，的子关系，即即R A RlA在在R下的下的像像RA是是ranR 的子集，的子集，即即RA ranR16.关系运算的性关系运算的性质质定理定理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.17.定理定理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)18.证证明明(2)任取任取,(F G)1F G t(FG)t(G 1F 1)G 1 F 1所以所以(F G)1=G 1 F 119.关系运算的性关系运算的性质质定理定理7.3设设R为为A上的关系上的关系,则则R IA=IA R=R证证:任取任取R IA t(RIA)t(Rt=yyA)R20.关系运算的性关系运算的性质质定理定理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 H21.推广推广定理定理7.4的的结论结论可以推广到有限多个关系可以推广到有限多个关系R(R1R2Rn)=R R1R R2R Rn(R1R2Rn)R=R1 RR2 RRn RR(R1R2Rn)R R1R R2R Rn(R1R2Rn)R R1 RR2 RRn R22.关系运算的性关系运算的性质质定理定理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 B请请将教材将教材P109定理定理7.5(2)的的RAB改改为为F AB！23.证证明明(1)F (AB)=F AF B证证(1)任取任取F (AB)FxABF(xAxB)(FxA)(FxB)F AF BF AF B所以有所以有F (AB)=F AF B.24.证证明明(4)F AB F AF B证证：任取：任取 yF AB x(FxAB)x(FxAxB)x(FxA)(FxB)x(FxA)x(FxB)yF AyF ByF AF B所以有所以有F AB F AF B.25.关系的关系的幂幂运算运算定定义义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=R26.例例8设设A=a,b,c,d,R=,求求R的各次的各次幂幂,分分别别用矩用矩阵阵和关系和关系图图表示表示.解解 R 与与 R2的关系矩的关系矩阵阵分分别别是：是：幂幂的求法的求法27.R3和和R4的矩的矩阵阵是：是：因此因此M4=M2,即即R4=R2.因此可以得到因此可以得到R2=R4=R6=，R3=R5=R7=R0的关系矩的关系矩阵阵是是幂幂的求法的求法28.关系关系图图R0,R1,R2,R3,的关系的关系图图如下如下图图所示所示.R0R1R2=R4=R3=R5=29.幂幂运算的性运算的性质质定理定理7.6设设A 为为n 元集元集,R 是是A上的关系上的关系,则则存在自然数存在自然数s 和和t,使得使得Rs=Rt.证证R 为为A上的关系上的关系,由于由于|A|=n,A上的不同关系只有上的不同关系只有个个.列出列出R 的各次的各次幂幂 R0,R1,R2,必存在自然数必存在自然数s 和和t，使得使得Rs=Rt.该该定理定理说说明有明有穷穷集上只有有集上只有有穷穷多个不同的二元关系。当多个不同的二元关系。当t足足够够大大时时Rt必与某个必与某个Rs（st）相等。）相等。30.定理定理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.31.证证明明(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.32.定理定理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由由归纳归纳法命法命题题得得证证.33.证证明明(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.34.7.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既不是自反的也不是反自反的既不是自反的也不是反自反的.35.对对称性与反称性与反对对称性称性定定义义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：不：不对对称、不反称、不反对对称称36.传递传递性性定定义义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上的上的传递传递关系关系.37.关系性关系性质质成立的充要条件成立的充要条件定理定理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 jump38.证证明明证证明明只只证证(1)、(3)、(4)、(5)(1)必要性必要性任取任取,由于由于R 在在A上自反必有上自反必有IA x,yAx=y R从而从而证证明了明了IA R充分性充分性.任取任取x,有有xA IA R因此因此R 在在A上是自反的上是自反的.39.证证明明(3)必要性必要性.任取任取,R R R 1所以所以R=R 1充分性充分性.任取任取,由由R=R 1得得R R 1R所以所以R在在A上是上是对对称的称的40.证证明明(4)必要性必要性.任取任取,有有RR 1RR 1RR x=y x,y AIA这这就就证证明了明了RR 1 IA充分性充分性.任取任取,RR RR 1RR 1IAx=y从而从而证证明了明了R在在A上是反上是反对对称的称的.41.证证明明(5)必要性必要性.任取任取有有R R t(RR)R所以所以R R R充分性充分性.任取任取,R,则则RR R R R所以所以R 在在A上是上是传递传递的的42.自反性自反性反自反性反自反性对对称性称性反反对对称性称性传递传递性性集合集合IA RRIA=R=R 1RR 1 IAR R R关系关系矩矩阵阵主主对对角角线线元素元素全是全是1主主对对角角线线元素全是元素全是0矩矩阵阵是是对对称矩称矩阵阵若若rij1,且且ij,则则rji0M2中中1位置位置,M中相中相应应位位置都是置都是1关系关系图图每个每个顶顶点都有点都有环环每个每个顶顶点点都没有都没有环环两点之两点之间间有有边边,是是一一对对方向方向相反的相反的边边两点之两点之间间有有边边,是一条有是一条有向向边边点点xi到到xj有有边边,xj 到到xk有有边边,则则xi到到xk也有也有边边关系性关系性质质的三种等价条件的三种等价条件jump43.自反性自反性反自反性反自反性对对称性称性反反对对称性称性传递传递性性R1 1R1R2R1R2R1 R2R1 R2关系的性关系的性质质和运算之和运算之间间的的联联系系44.7.5关系的关系的闭闭包包主要内容主要内容l闭闭包定包定义义l闭闭包的构造方法包的构造方法集合表示集合表示矩矩阵阵表示表示图图表示表示l闭闭包的性包的性质质45.闭闭包定包定义义定定义义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)中的并最多不超中的并最多不超过过Rn46.证证明明证证只只证证(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).由由归纳归纳法命法命题题得得证证.47.证证明明再再证证t(R)RR2成立成立,为为此只此只须证须证明明RR2传递传递.任取任取,则则RR2RR2 t(Rt)s(Rs)t s(Rt Rs)t s(Rt+s)RR2从而从而证证明了明了RR2是是传递传递的的.48.闭闭包的矩包的矩阵阵表示和表示和图图表示表示设设关系关系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的的边边,就加上就加上这这条条边边,得到得到图图Gt49.实实例例例例9设设A=a,b,c,d,R=,R和和r(R),s(R),t(R)的关系的关系图图如下如下图图所示所示.Rr(R)s(R)t(R)50.闭闭包的性包的性质质定理定理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)证证明明 略略51.定理定理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)闭闭包的性包的性质质证证明明 略略52.7.6 等价关系与划分等价关系与划分主要内容主要内容l等价关系的定等价关系的定义义与与实实例例l等价等价类类及其性及其性质质l商集与集合的划分商集与集合的划分l等价关系与划分的一一等价关系与划分的一一对应对应53.等价关系的定等价关系的定义义与与实实例例定定义义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)54.模模 3等价关系的关系等价关系的关系图图等价关系的等价关系的实实例例55.等价等价类类定定义义定定义义7.16设设R为为非空集合非空集合A上的等价关系上的等价关系,xA，令，令xR=y|yAxRy称称xR 为为x关于关于R的等价的等价类类,简简称称为为x的的等价等价类类,简记为简记为x或或因此，因此，x的等价的等价类类是是A中所有与中所有与x等价的元素构成的集合。等价的元素构成的集合。实实例例A=1,2,8上模上模3等价关系的等价等价关系的等价类类：1=4=7=1,4,72=5=8=2,5,83=6=3,656.等价等价类类的性的性质质定理定理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.57.证证明明(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.58.商集与划分商集与划分定定义义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的的划分划分块块.59.划分划分实实例例例例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 上面哪些是上面哪些是A的划分的划分?1和和 2是是A的划分的划分,其他都不是其他都不是A的划分的划分.60.例例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.61.7.7偏序关系偏序关系主要内容主要内容l偏序关系偏序关系偏序关系的定偏序关系的定义义偏序关系的偏序关系的实实例例l偏序集与哈斯偏序集与哈斯图图l偏序集中的特殊元素及其性偏序集中的特殊元素及其性质质极大元、极小元、最大元、最小元极大元、极小元、最大元、最小元上界、下界、最小上界、最大下界上界、下界、最小上界、最大下界62.定定义义与与实实例例定定义义7.19偏序关系偏序关系：非空集合：非空集合A上的自反、反上的自反、反对对称和称和传递传递的关系，的关系，记记作作.设设 为为偏序关系偏序关系,如果如果,则记则记作作x y,读读作作x“小于或等于小于或等于”y.实实例例集合集合A上的恒等关系上的恒等关系IA是是A上的偏序关系上的偏序关系.小于或等于关系小于或等于关系,整除关系和包含关系也是相整除关系和包含关系也是相应应集合上的偏集合上的偏序关系序关系.63.相关概念相关概念定定义义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.64.偏序集与哈斯偏序集与哈斯图图定定义义7.23集合集合A和和A上的偏序关系上的偏序关系 一起叫做一起叫做偏序集偏序集,记记作作.实实例例:,哈斯哈斯图图:利用偏序关系的自反、反利用偏序关系的自反、反对对称、称、传递传递性性进进行行简简化的化的关系关系图图特点：特点：(1)每个每个结结点没有点没有环环(2)两个两个连连通的通的结结点之点之间间的序关系通的序关系通过结过结点位置的高低表点位置的高低表示，位置低的元素的示，位置低的元素的顺顺序在前序在前(3)具有覆盖关系的两个具有覆盖关系的两个结结点之点之间连边间连边65.实实例例例例12偏序集偏序集和和的的哈斯哈斯图图.66.例例13已知偏序集已知偏序集的哈斯的哈斯图图如下如下图图所示所示,试试求出集合求出集合A和关系和关系R的表达式的表达式.解解A=a,b,c,d,e,f,g,h R=,IA实实例例67.偏序集中的特殊元素偏序集中的特殊元素定定义义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)孤立孤立结结点既是极小元，也是极大元点既是极小元，也是极大元.68.定定义义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)集合的最小元是其下确界，最大元是其上确界；反之不集合的最小元是其下确界，最大元是其上确界；反之不对对.69.实实例例例例14设设偏序集偏序集，求，求A的极小元、最小元、极大元、最的极小元、最小元、极大元、最大元，大元，设设Bb,c,d,求求B的下界、上界、下确界、上确界的下界、上界、下确界、上确界.解解极小元：极小元：a,b,c,g；极大元：极大元：a,f,h；没有最小元与最大元没有最小元与最大元.B的下界和最大下界都不存在；的下界和最大下界都不存在；上界有上界有d 和和f,最小上界最小上界为为d.70.实实例例例例15设设X为为集合集合,AP(X)X,且且A.若若|X|=n,n2.问问：(1)偏序集偏序集是否存在最大元？是否存在最大元？(2)偏序集偏序集是否存在最小元？是否存在最小元？(3)偏序集偏序集中极大元和极小元的一般形式是什么？中极大元和极小元的一般形式是什么？并并说说明理由明理由.解解(1)不存在最小元和最大元不存在最小元和最大元,因因为为n2.(2)的极小元就是的极小元就是X 的所有的所有单单元集元集,即即x,xX.(3)的极大元恰好比的极大元恰好比X 少一个元素少一个元素,即即X x,xX.71.第七章第七章 习题课习题课主要内容主要内容l有序有序对对与笛卡儿与笛卡儿积积的定的定义义与性与性质质l二元关系、从二元关系、从A到到B的关系、的关系、A上的关系上的关系l关系的表示法：关系表达式、关系矩关系的表示法：关系表达式、关系矩阵阵、关系、关系图图l关系的运算：定关系的运算：定义义域、域、值值域、域、逆、合成、限制、域、域、逆、合成、限制、像、像、幂幂l关系运算的性关系运算的性质质:A上关系的自反、反自反、上关系的自反、反自反、对对称、反称、反对对称、称、传递传递的性的性质质lA上关系的自反、上关系的自反、对对称、称、传递闭传递闭包包lA上的等价关系、等价上的等价关系、等价类类、商集与、商集与A的划分的划分lA上的偏序关系与偏序集上的偏序关系与偏序集72.基本要求基本要求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掌握基本的掌握基本的证证明方法明方法证证明涉及关系运算的集合等式明涉及关系运算的集合等式证证明关系的性明关系的性质质、证证明关系是等价关系或偏序关系明关系是等价关系或偏序关系73.关系性关系性质质的的证证明方法明方法1.证证明明R在在A上自反上自反任取任取x,x A.R前提前提推理推理过过程程结论结论2.证证明明R在在A上上对对称称任取任取，R.R前提前提推理推理过程程结论74.3.证证明明R在在A上反上反对对称称任取任取，R R.x=y前提前提推理推理过过程程结论结论4.证证明明R在在A上上传递传递任取任取,，R R.R前提前提推理推理过过程程结论结论关系性关系性质质的的证证明方法明方法75.练习练习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)76.解答解答(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)=,77.练习练习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=,78.3设设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 79.图11练习练习44设设偏序集偏序集的哈斯的哈斯图图如如图图所示所示.(1)写出写出A和和R的集合表达式的集合表达式(2)求求该该偏序集中的极大元、极小元、最大元、最小元偏序集中的极大元、极小元、最大元、最小元解解(1)A=