离散数学第2章-关系

1,世间万物都存在着联系.利用集合刻划这种联系的数学模型关系.“关系”的相关内容对今后学习数据结构、数据库等许多课程都是很重要的.,1,Chapter2关系,2,例学生A=张三,李四,王五;课程B=英语,数学实验,离散数学,数据结构,汇编语言;成绩C=优,良,合格,不合格.,2,2.1关系的概念,2.1.1n元关系的定义,选课(A与B之间的关系):R=(张三,离散数学),(张三,数据结构),(张三,英语),(李四,数据结构),(王五,数学实验),(王五,汇编语言).,课程得分(A,B与C之间的关系):,R=(张三,离散数学,优),(张三,数据结构,良),(张三,英语,优),(李四,数据结构,优),(王五,数学实验,合格),(王五,汇编语言,良).,3,定义特别地,若,则称R为A上的n元关系.n=2:2元关系.例设A=0,1,2,3,4,A上的关系R=(x,y)|x=y+1或y=x/2,试用列举法求出R.解R=(1,0),(2,1),(3,2),(4,3)(0,0),(2,1),(4,2),3,4,2元关系:两个集合A和B(可以相同)间的关系A到B的关系:A到A,即A上的关系:A到B的空关系AB与全关系ABAB.例A=a,b,B=1,2,3,Theorem|A|=m,|B|=n,则A到B的关系有2mn个.提示|AB|=mn.若|A|=m,则A上的关系有2m2个.,4,2.1.2二元关系,?,?,5,关系符号:设RAB,若(x,y)R,则称元素x与y有关系R,可记为xRy:例实数集合R上的大于“”关系:例整数集合Z上的模k同余关系k:定义：A上的恒等关系:例若A=a,b,c,则IA=(a,a),(b,b),(c,c).,k|(x-y)x除以k的余数=y除以k的余数.,6,定义域:设RAB,domR=x|xA,存在yB,使得(x,y)R即R中所有有序对中第一位置元素组成的集合,它显然是A的子集.例R=(1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2),(4,4)domR=1,2,3,4.值域:设RAB,ranR=y|yB,存在xA,使得(x,y)R即R中所有有序对中第二位置元素组成的集合,它是B的子集.在上例中,ranR=1,2,3,4.,6,2.1.3关系的定义域与值域,7,1、关系图情形1R是A到B(包括A上)的关系例A=a,b,c,d,B=1,2,3,R=(a,2),(a,3),(c,2),(d,2).,7,2.1.4关系的表示,(除集合表示外),8,情形2R是A上的关系例A=a,b,c,d,R=(a,b),(a,c),(c,a),(d,c),(d,d).,8,9,2、关系矩阵例A=a,b,c,d,B=1,2,3,R=(a,2),(a,3),(c,2),(d,2).,9,10,例A=a,b,c,B=1,2,3,f:AB,f(a)=2,f(b)=3,f(c)=3.备注一般来说,A到B的关系不是A到B的函数.,2.1.5函数的关系(集合)定义,11,函数:A到B有关系f,并满足以下条件,(1)domf=A;(2)例判断自然数集合N上的下列关系能否构成函数.f=(x,y)|x,yN,x+ybR3=(a,b)|a=bora=-bR4=(a,b)|a=bR5=(a,b)|a=b+1R6=(a,b)|a+b3,R3,R4,R6,R1,R2,R4,R5,a=b,判断下列整数集上的关系的对称性和反对称性?,解：,对称性：,反对称性：,41,A上的对称关系与反对称关系的区别与联系:一、R既对称又反对称?二、R对称但不是反对称?三、R不是对称的但是反对称?四、R既不是对称的又不是反对称?,41,42,定义设RAA,对于任意x,y,zA,若(x,y)R且(y,z)R,均有(x,z)R,则称R是A上的传递关系,或称R是传递的,或称R具有传递性.例A=a,b,c,d,R=(a,a),(a,b),(b,b),(b,c),(a,c),(c,a)是否传递?,42,2.3.5传递性,(c,c)R,43,例Z上的整除关系|是传递的;P(X)上的包含关系是传递的;不传递关系的例子:TheoremR传递RRR.Proof()设(x,y)RR,则存在zA,使得(x,z)R,(z,y)R.因为R传递,所以(x,y)R.()任意(x,y)R,(y,z)R，由复合的定义可知(x,z)RR,因为RRR，故(x,z)R。,43,父子关系?,44,R1=(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)R2=(1,1),(1,2),(2,1)R3=(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4)R4=(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)R5=(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)R6=(3,4),R4,R5,R6.,判断下列1,2,3,4上的关系的传递性?,解：,45,R1=(a,b)|abR2=(a,b)|abR3=(a,b)|a=bora=-bR4=(a,b)|a=bR5=(a,b)|a=b+1R6=(a,b)|a+b3,R1,R2,R3,R4,(2,1)(1,0)(2,0)?,(2,1)(1,2)(2,2)?,a=b,判断下列整数集上的关系的传递性?,解：,46,例A=a,b,c,d,问题如何根据R的关系矩阵及关系图去判断R是否传递?,R1=(a,b),(a,c)传递?,R2=(a,b)也传递.,=RRR,47,例A=0,1,2,3,4,5,R=(x,y)|x,yA,x+y=5.解(1)自反?(2)反自反?(3)对称?(4)反对称?(5)传递?,47,48,最后考察关系的运算对性质的保持.,48,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,T,49,练习P5811.11.R=(a,a),(b,a),(a,b),(b,c)(b,b)R,无自反性(a,a)R,无反自反性(b,c)R,但(c,b)R,无对称性(a,b)R,(b,a)R,无反对称性(a,b)R,(b,c)R,但(a,c)R,无传递性作业习题2.3P58:3,8,50,例设A=a,b,c,R=(a,a),(b,a),(b,c),(c,a),(a,c),求出所有包含R的自反关系.解R1=R(b,b),(c,c);R2=R(b,b),(c,c),(a,b);R3=R(b,b),(c,c),(c,b);R4=R(b,b),(c,c),(a,b),(c,b).R1称为R的自反闭包.,50,2.4关系的闭包,2.4.1自反闭包,51,自反闭包:设RAA,最小的包含R的自反关系,记为r(R).自反闭包r(R)满足3个条件:(1)包含R；(2)自反性；(3)最小性.Theorem问题自反闭包r(R)的关系图?,51,每一点都画上环,证：,关系矩阵？,52,对称闭包:设RAA,最小的包含R的对称关系,记为s(R).对称闭包s(R)满足3个条件:(1)包含R；(2)对称性；(3)最小性.Theorem问题对称闭包s(R)的关系图?,52,2.4.2对称闭包,有边必须为双向边,证：,关系矩阵？,53,传递闭包:设RAA,最小的包含R的传递关系,记为t(R).传递闭包t(R)满足3个条件:(1)包含R;(2)传递性;(3)最小性.例设A=a,b,c,R=(a,b),(b,c),(b,a),求t(R).解t(R)=(a,b),(b,c),(b,a),(a,c),(a,a),(b,b).,53,2.4.2传递闭包,54,TheoremTheorem若|A|=n1,RAA,则例设R是某城市所有地铁站集合的关系,如果从a站能不换车到b站,那么(a,b)R,当n是整数时,Rn是什么?t(R)是什么?备注当元素较多时,常利用Warshall(1962)算法求传递闭包t(R).,54,为什么？,55,定义为：,从到有一条路径，经过的顶点在中,设已有，计算,第k列元素遍乘第k行元素加到矩阵,1,1,1,1,1,W1,W2,W3,56,一、关系的闭包运算与其他运算之间的联系Theorem(1)(2)(3)备注,证（3）,57,二、闭包运算与关系的性质的联系Theorem(1)R自反,则r(R),s(R)及t(R)自反.(2)R对称,则r(R),s(R)及t(R)对称.(3)R传递,则r(R),t(R)传递,s(R)不一定传递.备注R自反r(R)=RR对称s(R)=RR传递t(R)=R,57,58,下表列举关系的性质与闭包运算的联系:,58,59,三、多重闭包运算对于多重闭包运算,规定从右至左依次进行运算,如Theorem(1)(2)(3)证明(1)作业习题2.4P64:2,8,10.,59,60,等价关系是一种非常重要的特殊关系,它是相等关系“=”、全等关系“”等的一种推广.等价关系以及根据它对集合进行划分是粗糙集(roughset)理论的基础,粗糙集理论是智能信息处理的重要方法之一.,60,2.5等价关系,61,定义:设RAA,若R具有自反性、对称性以及传递性,则称R为A上的等价关系.等价类:设R为A上的等价关系,对于任意aA:例设A=a,b,c,R=(a,a),(b,b),(c,c),(b,c),(c,b),则R具有自反性、对称性以及传递性,因此R为A上的等价关系.,61,2.5.1等价关系的定义,62,例试验证Z上的模3同余关系R是等价关系：,62,证：,自反性:,x-x=0,对称性:,若3xy3yx;,传递性:,若3x-y且3y-z,3xz=(xy)+(yz).,由定义3是等价关系.,30;,63,Theorem设R和S为A上的等价关系,则R-1及RS为A上的等价关系.设R和S是集合A上的两个等价关系,下表列出了等价关系与关系运算的联系:,63,传递性,自反性传递性,自反性,对称性传递性,自反性,64,等价类:设R为A上的等价关系,对于任意aA:,2.5.2等价类,例Z上的模3同余关系R:,65,Theorem设R为A上的等价关系,对于任意x,yA,则Proof()(),65,同理可证,66,Theorem设R为A上的等价关系,对于任意x,yA,则提示(反证)商集:A/R=xR|xA,66,Theorem设R是集合A上的等价关系，则A关于R的商集A/R是集合A的划分.(1)每个等价类非空;(2)不同的等价类不相交;(3)所有等价类的并就是A.,定理已证得,自反性,67,商集:A/R=xR|xA,67,例：,应用:,证明:11,111,1111,中没有平方数.,证,但,68,给定集合A的一个划分,按下面的方式可以得出A上的一个关系R:(x,y)Rx和y在划分的同一个块.思考R是等价关系?例设A=a,b,c,=a,b,c,则R=(a,a),(b,b),(c,c),(b,c),(c,b),它是A上的一个等价关系.,68,69,Theorem对于任意集合A,集合A上的所有划分组成的集合X与其上的所有等价关系组成的集合Y是对等的.课堂练习P68,12.解可由集合A的所有划分个数得出:一个块的划分:1两个块的划分:,三个块的划分:四个块的划分:1作业习题2.5P68:2,9.,69,70,偏序:设RAA,R具有自反性、反对称性和传递性.例R,?例P(X),?例N+,|?备注借用数的表示偏序.(A,)称为偏序集.,70,2.7偏序关系,2.7.1偏序关系的定义,71,定义:设是A上的偏序,若对任意x,yA,有xy或yx,则称是线性序关系,简称线性序,又称为全序.显然,实数集R上的数的小于等于关系是线性序.,71,满足特殊性质的关系见下表:,72,Hasse图用于表示元素间的相对位置(或次序)关系.例A=1,2,3,A上的数的小于等于是其上的偏序关系.画出其关系图.备注:哈斯图表明了偏序集中的元素按相对大小进行的排序.,72,2.7.2偏序集的Hasse图,73,y盖住x:设(A,)是偏序集,x,yA,(1)xy(xy:xy且xy);(2)满足xz且zy的元素z不存在.记COV(A)=(x,y)|x,yA且y盖住x.例设X=a,b,则A=P(X)=,a,b,a,b,集合P(X)上的包含关系“”是其上的偏序关系,求COV(A).解根据定义知,a盖住,b盖住,a,b盖住a,73,a,b盖住b.,COV(A)=(,a),(,b),(a,a,b),(b,a,b).,74,Hasse图的画法:(1)用黑点代表A中元素;(2)y盖住x,y画在x的上方,且用线段连接x和y.,74,COV(A)=(,a),(,b),(a,a,b),(b,a,b).,75,备注a与b没有关系“”,不能比较“大小”?从Hasse图看,两元素x,y,何时有“xy”?x在下方,可以连到上方的y.,76,例(P76:2)解很容易得出R是偏序.(a,b)R,b盖住a.(a,c)R,c不盖住a.同理,(a,d)R,d盖住a;(a,e)R,e不盖住a;(b,c)R,c盖住b;(b,e)R,e不盖住b;(c,e)R,e盖住c;(d,e)R,e盖住d.,76,77,课堂练习X=a,b,c,(P(X),)的Hasse图?,78,设(A,)是偏序集,SA,S中处于特殊位置的元素对于有些问题的讨论是很重要的.备注建议在理解特殊元素时,将偏序“”当作“小于等于”,虽然它一般不是数的小于等于.一、最大元和最小元S的最大元b:S的最小元b:,78,2.7.3偏序集中的特殊元素,79,存在性?(R,),S=Z?(P(X),),S=P(X)?(Z+,|),S=Z+?唯一性?Theorem若S存在最大(小)元,则唯一.,79,AX.,1|x,S=2,