DM专题关系的概念与关系的运算.ppt

1,有序对与笛卡儿积,定义2.1设A和B是任意两个集合，用A中元素为第一元素，B中元素为第二元素构成有序对，所有这样的有序对组成的集合称为集合A和B的笛卡尔积，或成为集合A和B的直乘积，记作AB，即AB=|xAyB.,2,笛卡儿积,例1A=1,2,3,B=a,b,cAB=,BA=,3,由两个元素x和y，按照一定的顺序组成的二元组称为有序对，记作.有序对性质:(1)有序性（当xy时）(2)与相等的充分必要条件是=x=uy=v.,有序对的性质,4,笛卡儿积的性质,(1)不适合交换律ABBA(AB,A,B)(2)不适合结合律(AB)CA(BC)(A,B,C)(3)对于并或交运算满足分配律A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)(4)若A或B中有一个为空集，则AB就是空集.A=B=(5)若|A|=m,|B|=n,则|AB|=mn,5,二元关系,定义2.3如果一个集合满足以下条件之一：(1)集合非空,且它的元素都是有序对(2)集合是空集则称该集合为一个二元关系,简称为关系，记作R.如果R,可记作xRy；如果R,则记作xy实例：R=,S=,a,b.R是二元关系,当a,b不是有序对时，S不是二元关系根据上面的记法，可以写1R2,aRb等.,6,A到B的关系与A上的关系,定义2.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个不同的二元关系.,7,关系的运算,关系R中有序对的第一元素所允许选取对象集合称为关系R的定义域，记作Dom(R)，第二元素所允许选取对象集合称为关系R的值域，记作Ran(R)，定义2.6关系的定义域、值域与域分别定义为domR=x|y(R)ranR=y|x(R)fldR=domRranR,例5设A=1,2,3,4,B=1,2,3,4，A到B的关系R=,则domR=1,2,4ranR=2,3,4fldR=1,2,3,4,8,A上重要关系的实例,定义2.5设A为集合,(1)是A上的关系，称为空关系(2)全域关系EA=|xAyA=AA恒等关系IA=|xA小于等于关系LA=|x,yAxy,A为实数子集整除关系DB=|x,yBx整除y,A为非0整数子集包含关系R=|x,yAxy,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=rijmn,其中rij=1R.2.关系图若A=x1,x2,xm，R是从A上的关系，R的关系图是GR=,其中A为结点集，R为边集.如果属于关系R，在图中就有一条从xi到xj的有向边.注意：关系矩阵适合表示从A到B的关系或A上的关系（A,B为有穷集）关系图适合表示有穷集A上的关系,11,实例,例4A=1,2,3,4,R=,R的关系矩阵MR和关系图GR如下：,12,关系运算(交、并、补),关系的交、并、补运算,13,关系运算(逆与合成),定义2.7关系的逆运算R1=|R定义2.8设A，B，C是三个集合，R是从A到B的一个二元关系，S是从B到C的一个二元关系，则R与S的合成运算RS=|yB(RS),例6R=,S=,R1=,RS=,SR=,14,合成的图示法,利用图示（不是关系图）方法求合成RS=,SR=,15,关系运算(限制与像),定义2.9设R为二元关系,A是集合(1)R在A上的限制记作RA,其中RA=|xRyxA(2)A在R下的像记作RA,其中RA=ran(RA)说明：R在A上的限制RA是R的子关系，即RARA在R下的像RA是ranR的子集，即RAranR,16,实例,例7设R=,则R1=,R=R2,3=,R1=2,3R=R3=2,17,关系的性质,定义2.11设R为A上的关系,(1)若x(xAR),则称R在A上是自反的.(2)若x(xAR),则称R在A上是反自反的.,实例：自反：小于等于关系LA,整除关系DA反自反：实数集上的小于关系、幂集上的真包含关系.A=1,2,3,R1,R2,R3是A上的关系,其中R1,R2,R3R2自反，R3反自反，R1既不是自反的也不是反自反的.,18,对称性与反对称性,定义2.12设R为A上的关系,(1)设R是集合A上的二元关系，对任意的a,bA,若有R,就必有R，则称R为A上对称的关系。(2)若有R,且R，就必有b=a，则称R为A上反对称的关系。,实例：对称关系：A上的全域关系EA,恒等关系IA和空关系是对称关系：恒等关系IA和空关系也是A上的反对称关系.设A1,2,3,R1,R2,R3和R4都是A上的关系,其中R1,，R2,R3,，R4,R1：对称和反对称；R2：只有对称；R3：只有反对称；R4：不对称、不反对称,19,传递性,定义2.13若R是集合A上的二元关系，对任意a,b,cA,若有R,且R，就必有R,则称R为A上的传递关系。,实例：A上的全域关系EA,恒等关系IA和空关系，小于等于和小于关系，整除关系，包含与真包含关系设A1,2,3,R1,R2,R3是A上的关系,其中R1,R2,R3R1和R3是A上的传递关系,R2不是A上的传递关系.,20,关系性质成立的充要条件,定理2.9设R为A上的关系,则(1)R在A上自反当且仅当IAR(2)R在A上反自反当且仅当RIA=(3)R在A上对称当且仅当R=R1(4)R在A上反对称当且仅当RR1IA(5)R在A上传递当且仅当RRR,21,关系性质的三种等价条件,22,关系的性质和运算之间的联系,23,关系的闭包,主要内容闭包定义闭包的构造方法集合表示矩阵表示图表示闭包的性质,24,闭包定义,定义2.14设R是非空集合A上的关系,R的自反(对称或传递)闭包是A上的关系R,使得R满足以下条件：(1)R是自反的(对称的或传递的)(2)RR(3)对A上任何包含R的自反(对称或传递)关系R有RRR的自反闭包记作r(R),对称闭包记作s(R),传递闭包记作t(R).,定理2.10设R为A上的关系,则有(1)r(R)=RR0(2)s(R)=RR1(3)t(R)=RR2R3说明：对有穷集A(|A|=n)上的关系,(3)中的并最多不超过Rn,25,证明,证只证(1)和(3).(1)由IA=R0RR0知RR0是自反的,且满足RRR0设R是A上包含R的自反关系,则有RR和IAR.从而有RR0R.RR0满足闭包定义,所以r(R)=RR0.,(1)先证RR2t(R)成立.用归纳法证明对任意正整数n有Rnt(R).n=1时有R1=Rt(R).假设Rnt(R)成立,那么对任意的Rn+1=RnRt(RnR)t(t(R)t(R)t(R)这就证明了Rn+1t(R).由归纳法命题得证.,26,证明,再证t(R)RR2成立,为此只须证明RR2传递.任取,则RR2RR2t(Rt)s(Rs)ts(RtRs)ts(Rt+s)RR2从而证明了RR2是传递的.,27,闭包的矩阵表示和图表示,设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms和Mt则Mr=M+EMs=M+MMt=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的边,就加上这条边,得到图Gt,28,实例,例9设A=a,b,c,d,R=,R和r(R),s(R),t(R)的关系图如下图所示.,29,等价关系与划分,主要内容等价关系的定义与实例等价类及其性质商集与集合的划分等价关系与划分的一一对应,30,等价关系的定义与实例,定义2.15设R为非空集合上的关系.如果R是自反的、对称的和传递的,则称R为A上的等价关系.设R是一个等价关系,若R,称x等价于y,记做xy.,实例非空集合上的恒等、全域关系都是的等价关系设A=1,2,8,如下定义A上的关系R：R=|x,yAxy(mod3)其中xy(mod3)叫做x与y模3相等,即x除以3的余数与y除以3的余数相等.不难验证R为A上的等价关系,因为(1)xA,有xx(mod3)(2)x,yA,若xy(mod3),则有yx(mod3)(3)x,y,zA,若xy(mod3),yz(mod3),则有xz(mod3),31,模3等价关系的关系图,等价关系的实例,32,等价类定义,定义2.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,6,33,等价类的性质,定理2.14设R是非空集合A上的等价关系,则(1)xA,x是A的非空子集(2)x,yA,如果xRy,则x=y(3)x,yA,如果xy,则x与y不交(4)x|xA=A,例设集合A=1,2,3,4上的等价关系R=,试画出R的等价关系图，并求出A中各元素的R等价类。,34,商集与划分,定义2.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,定义2.18设A为非空集合,若A的子集族(P(A)满足:(1)(2)xy(x,yxyxy=)(3)=A则称是A的一个划分,称中的元素为A的划分块.,35,划分实例,例10设Aa,b,c,d,给定1,2,3,4,5,6如下：1=a,b,c,d2=a,b,c,d3=a,a,b,c,d4=a,b,c5=,a,b,c,d6=a,a,b,c,d则1和2是A的划分,其他都不是A的划分.,商集与划分,37,偏序关系,主要内容偏序关系偏序关系的定义偏序关系的实例偏序集与哈斯图偏序集中的特殊元素及其性质极大元、极小元、最大元、最小元上界、下界、最小上界、最大下界,38,定义与实例,定义2.19偏序关系：非空集合A上的自反、反对称和传递的关系，记作.设为偏序关系,如果,则记作xy,读作x“小于或等于”y.实例集合A上的恒等关系IA是A上的偏序关系.实数集上小于或等于关系,整除关系和包含关系也是相应集合上的偏序关系.例设集合A=1,2,3上的二元关系R=,试画出R的关系图来验证R是偏序关系。,39,覆盖与偏序集,定义2.20 x,yA,如果xy且不存在zA使得xzy,则称y覆盖x.例如1,2,4,6集合上整除关系,2覆盖1,4和6覆盖2,4不覆盖1.,定义2.21集合A和A上的偏序关系一起叫做偏序集,记作.实例:,40,哈斯图,哈斯图:对于给定的偏序集，可以先利用偏序关系求出所有的覆盖关系元素对，然后根据此画出一个简化的偏序关系图，这种简化的关系图称为哈斯图。特点：(1)每个结点没有环(2)两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前(3)具有覆盖关系的两个结点之间连边,41,实例,例12偏序集和的哈斯图.,42,例13已知偏序集的哈斯图如下图所示,试求出集合A和关系R的表达式.,解A=a,b,c,d,e,f,g,hR=,IA,实例,43,偏序集中的特殊元素,定义2.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的极大元应该不小于B中其他各元素，即它大于等于B中的一些元素，而与B中另一些元素无关系。(2)对于有穷集，极小元和极大元一定存在，可能存在多个.(3)最小元和最大元不一定存在，如果存在一定惟一.(4)最小元一定是极小元；最大元一定是极大元.(5)孤立结点既是极小元，也是极大元.,44,例13已知偏序集的哈斯图如下图所示,试求出以