数学关系性质离散数学.pptx
《数学关系性质离散数学.pptx》由会员分享,可在线阅读,更多相关《数学关系性质离散数学.pptx(64页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、3/25/2023 1:34 AM 1第 七 章 二 元 关 系7.1有序对与笛卡儿积7.2二元关系7.3关系的运算7.4关系的性质7.5关系的闭包7.6等价关系与划分7.7偏序关系第1页/共64页3/25/2023 1:34 AM 2定义7.1由两个元素x和y(允许xy)按一定顺序排列成的二元组叫做一个有序对,记为。注:有序对的性质:1.当xy时,。2.的充分必要条件是x=u且y=v。7.1 有序对与笛卡尔积 定义7.2 设A,B是集合。由A中元作为第一元素,B中元作为第二元素组成的所有有序对的集合,称为集合A与B的笛卡尔积,记为AB。即 AB|xAyB。第2页/共64页3/25/2023
2、1:34 AM 3注:笛卡尔积的性质:1.A=,A=;2.ABBA,除非 A=或B=或A=B;3.(AB)CA(BC),除非 A=或B=或C=.4.A(BC)=(AB)(AC);(BC)A=(BA)(CA);A(BC)=(AB)(AC);(BC)A=(BA)(CA);5.(AC)(BD)(AB)(CD).7.1有序对与笛卡尔积第3页/共64页3/25/2023 1:34 AM 4例 证明A(BC)=(AB)(AC)。证:任取,A(BC)xAy(BC)xA(yByC)(xAyB)(xAyC)(AB)(AC)(AB)(AC)A(BC)=(AB)(AC)例7.2 设 A=1,2,求 P(A)A。解:
3、P(A)A =,1,2,1,21,2=,7.1有序对与笛卡尔积第4页/共64页3/25/2023 1:34 AM 5例7.3 设A,B,C,D为任意集合,判断下列命题是否为真。(1)ABACB=C(2)A(BC)=(AB)(AC)(3)(A=B)(C=D)AC=BD(4)存在集合A,使 AAA7.1有序对与笛卡尔积解:(1)不一定为真,(3)为真。(4)为真。当A=,B=1,C=2,3时,便不真。(2)不一定为真,当A=B=1,C=2时,A(BC)=1=1,而(AB)(AC)=1=.等量代入。当A=时,使AAA.第5页/共64页3/25/2023 1:34 AM 6一、基本概念定义7.3 如果
4、一个非空集合的元素都是有序对,则称该集合为一个二元关系。特别地,空集也是一个二元关系。注:对一个二元关系R,如果R,则记为xRy;如果R,则记为xRy。定义7.4 设A,B为集合,AB的任何子集所定义的二元关系称为从A到B的二元关系。特别地,当A=B时,称为A上的二元关系。定义7.5 对任何集合A,(1)称空集为A上的空关系。(2)A上的全域关系EA=xAyA=AA(3)A上的恒等关系IA=xA.7.2二元关系第6页/共64页3/25/2023 1:34 AM 7二.关系的表达方式1.集合表达式:列出关系中的所有有序对。例7.4 设A=1,2,3,4,试列出下列关系R的元素。(1)R=x是y的
5、倍数(2)R=(xy)2A(3)R=x/y是素数(4)R=xy(5)R=(x,yA)(xy)解:(1)R=,(2)R=,(3)R=,(4)R=EA-IA=,(5)R=,7.2二元关系第7页/共64页3/25/2023 1:34 AM 82.关系矩阵法:设A=x1,x2,xn,R 是 A 上的关系。令:则矩阵 称为R 的关系矩阵。7.2二元关系第8页/共64页3/25/2023 1:34 AM 9例 设A=1,2,3,4,R=,则R的关系矩阵为7.2二元关系第9页/共64页3/25/2023 1:34 AM 103.关系图法 设A=x1,x2,xn,R是A上的关系。以A的元素作为顶点,当且仅当x
6、iRxj时,xi 向xj 连一条有向边,所得的图形称为R的关系图,记为GR。例7.6 设 A=1,2,3,4,R=,则R的关系图为12437.2二元关系第10页/共64页3/25/2023 1:34 AM 11一、基本概念定义7.6设R是二元关系。定义(1)R的定义域:domR=x|y(R),即R中所有有序对的第一元素构成的集合。(2)R的值域,ranR=y|x(R),即R中所有有序对的第二元素构成的集合。(3)R的域:fld R=dom Rran R。例7.5R=,则domR=1,2,4,ranR=2,3,4,fld R=1,2,3,4。7.3 关系的运算第11页/共64页3/25/2023
7、 1:34 AM 12定义7.7 设R为二元关系,称 R-1=|R为R的逆关系。定义7.8 设F,G为二元关系。称为G 对F 的右复合(或F 对G 的左复合)。例如,F=,G=,则 F-1=,7.3 关系的运算第12页/共64页3/25/2023 1:34 AM 13定义7.9设R是二元关系,A是集合(通常AdomR)7.3 关系的运算例7.7设R为,则(1)R在A上的限制:RA=|xRyxAR1=2,3,R=,R2,3=2,4。R1=,R=,R2,3=,,(2)A在R下的像:RA=ran(RA)第13页/共64页3/25/2023 1:34 AM 14定义7.10 设R是A上的关系,n为自然
8、数,则R的n次幂定义为:(1)R0=|xA=IA;(2)注:1.对A上的任何关系R,都有 R0=IA,R1=R。2.Rn的求法:除了根据定义按关系的复合来求之外,还可以用矩阵法和关系图法。7.3 关系的运算第14页/共64页3/25/2023 1:34 AM 15例7.8 设A=a,b,c,d,R=,求R的各次幂,分别用矩阵和关系图表示.解:R的关系矩阵:R2,R3,R4 的关系矩阵分别是:第15页/共64页3/25/2023 1:34 AM 16可见M4=M2。故R2=R4=R6=;R3=R5=R7=。第16页/共64页3/25/2023 1:34 AM 17此外,R0=IA的关系矩阵为:用
9、关系图法得到 R0,R1,R2,的关系图如下:dabcR0R1abcdR2=R4=bcdaabcdR3=R5=第17页/共64页3/25/2023 1:34 AM 18关系是集合,故有关集合的所有运算性质对关系都成立。定理7.1 设F是关系,则(1)(F-1)-1=F;(2)dom F-1=ran F,ran F-1=domF。证:(1)(F-1)-1F-1F(F-1)-1=F。(2)xdomF-1y(F-1)y(F)xran FdomF-1=ran F。同理可证 ran F-1=dom F。二.关系的运算性质第18页/共64页3/25/2023 1:34 AM 19定理7.2 设F,G,H是
10、关系,则(1)(FG)H=F(GH);(2)(FG)1=G1F1.证:(1)(FG)H)t(FG)H)t(s(FG)H)ts(FG)H)s(Ft(GH)s(F(GH)F(GH)(FG)H=F(GH)(2)(FG)1FGt(FG)t(G1F1)(G1F1)(FG)1=G1F1第19页/共64页3/25/2023 1:34 AM 20定理7.3 设R是A上的关系,则 RIA=IAR=R.证:(RIA)t(RIA)t(Rt=y)RRRyARIA(RIA)RIA=R同理可证 IAR=R第20页/共64页3/25/2023 1:34 AM 21定理7.4 设F,G,H是关系,则(1)F(GH)=FGFH
11、;(2)(GH)F=GFHF;(3)F(GH)FGFH;(4)(GH)FGFHF.证:以(3)为例.F(GH)t(F(GH)t(FGH)t(FG)(FH)t(FG)t(FH)FGFH FGFHF(GH)=FGFH第21页/共64页3/25/2023 1:34 AM 22定理7.5设F为关系,A,B为集合,则(1)F(AB)=FAFB;(2)FAB=FAFB(3)F(AB)=FAFB;(4)FABFAFB(1)F(AB)F(AB)=FAFB证:以(1)和(4)为例F(xAxB)(FxA)(FxB)FAFB(FAFB)Fx(AB)第22页/共64页3/25/2023 1:34 AM 23(4)yF
12、ABx(F(xAB)x(FxAxB)x(FxA)(FxB)x(FxA)x(FxB)yFAyFBy(FAFB)FAB=FAFB第23页/共64页3/25/2023 1:34 AM 24定理7.7设R为A上的关系,m,nN,则(1)RmRn=Rm+n;(2)(Rm)n=Rmn证:(1)对于任意取定的mN,关于n作数学归纳法。当n=0时,RmR0=RmIA=Rm=Rm+0假设RmRn=Rm+n,则RmRn+1=Rm(RnR)=(RmRn)R=Rm+nR1=Rm+n+1由归纳法原理,知命题成立。(2)对任意取定的mN,关于n作数学归纳法。当n=0时,(Rm)0=IA=R0=Rm0假设(Rm)n=Rmn
13、,则(Rm)n+1=(Rm)nRm=RmnRm=Rmn+m=Rm(n+1)由归纳法原理,知命题成立。定理7.6 设A是n元集合,R为A上的关系,则存在自然数s和t,使得Rs=Rt。第24页/共64页3/25/2023 1:34 AM 25定理7.8设R为A上的关系,若存在自然数s,t(st),使得Rs=Rt,则(1)kN都有Rs+k=Rt+k(2)k,iN都有Rs+kp+i=Rs+i,其中p=ts(3)令S=R0,R1,Rt1,则对qN都有RqS。证明:见教材P112。注:定理7.6和定理7.8的(3)表明,有限集合A上的二元关系只有有限多个,而且一个关系的幂序列R0,R1R2,是一个周期性变
14、化的序列。例7.9见教材P113。第25页/共64页3/25/2023 1:34 AM 26一、关系的五种性质 关系的性质主要有5种:自反性,反自反性,对称性,反对称性和传递性。定义7.11 设R是A上的关系,若x(xAR),则称 R在A上是自反的(Reflexive);若x(xAR),则称R在A上是反自反的(antiReflexive).7.4 关系的性质第26页/共64页3/25/2023 1:34 AM 27例7.10(1)A上的全域关系EA、恒等关系IA都是A上的自反关系.(2)小于等于关系 LA=x,yAxy,AR.整除关系 DA=x,yAx整除y,AZ*.包含关系 R=x,yAxy
15、,A 是集合族。都是自反关系.(3)小于关系 SA=x,yAxy,AR.真包含关系 R=x,yAxy,A是集合族。都是反自反关系.(4)设 A=1,2,3,R1=,是A上的自反关系;R2=是A上的反自反关系;R3=,既不是自反的,也不是反自反的.第27页/共64页3/25/2023 1:34 AM 28定义7.12 设R是A上的关系,若xy(x,yAR(y,x)R),则称R是A上的对称关系(Symmetric);若 xy(x,yAR(y,x)Rx=y),则称R是A上的反对称关系(antiSymmetric).例7.11(1)A上的全域关系EA,恒等关系IA及空关系都是A上的对称关系;IA和同时
16、也是A上的反对称关系.(2)设A=1,2,3,则 R1=,既是A上的对称关系,也是A上的反对称关系;R2=,是对称的,但不是反对称的;R3=,是反对称的,但不是对称的;R4=,既不是对称的也不是反对称的。第28页/共64页3/25/2023 1:34 AM 29定义7.13设R是A上的关系,若xyz(x,y,zARRR),则称R是A上的传递关系。例7.12(1)A上的全域关系EA,恒等关系IA和空关系都是传递关系。(2)小于等于关系,整除关系和包含关系是传递关系,小于关系和真包含关系也是传递关系。(3)设A=1,2,3,则R1=,和R2=都是A上的传递关系,但R3=,不是A上的传递关系。第29
17、页/共64页3/25/2023 1:34 AM 30定理7.9 设R为A上的关系,则(1)R在A上自反当且仅当 IAR(2)R在A上反自反当且仅当 RIA=(3)R在A上对称当且仅当 R=R-1(4)R在A上反对称当且仅当 RR-1IA(5)R在A上传递当且仅当 RRR证:(1)必要性:因R在A上自反,故IAx,yAx=yR,从而IAR。充分性:因xAIAR,故R在A上自反。二、各种性质的充分必要条件第30页/共64页3/25/2023 1:34 AM 31(2)必要性(用反证法):假设RIA,则必存在RIA,即R且IA。由IA知x=y.从而R.这与R在A上是反自反矛盾。充分性:xAIAR(因
18、RIA=),这说明R在A上是反自反的。(3)必要性:R是A上的对称关系,RRR-1,故R=R-1。充分性:由于R=R-1,RR-1 R.故R在A上是对称的。第31页/共64页3/25/2023 1:34 AM 32(4)必要性:因R在A上是反对称的,故RR1RR1RRx=yIA.RR1IA 充分性:因 RR1 IA,故RRRR1RR1IAx=y.从而 R在A上是反对称的.第32页/共64页3/25/2023 1:34 AM 33(5)必要性:因R在A上是传递的,故RRt(RR)R因此RRR充分性:因RRR,故RRRRRR在A上是传递的。第33页/共64页3/25/2023 1:34 AM 34
19、 例7.13 设A是集合,R1和R2是A上的关系,证明(1)若R1和R2都是自反的和对称的,则R1R2也是自反的和对称的.(2)若R1和R2是传递的,则R1R2也是传递的.证:(1)因R1和R2是A上的自反关系,故IAR1,IAR2,从而IAR1R2.由定理7.9,R1R2在A上是自反的.由R1和R2的对称性,有R1=R11和R2=R2-1,因此(R1R2)-1=R1-1R2-1=R1R2(见习题7.20).由定理7.9,R1R2在A上是对称的.(2)由R1和R2的传递性,有R1R1R1和R2R2R2.由定理7.4,(R1R2)(R1R2)(R1R1)(R1R2)(R2R1)(R2R2)(R1
20、R2)(R1R2)(R2R1)R1R2由定理7.9,R1R2在A上是传递的.第34页/共64页3/25/2023 1:34 AM 35 性质表示性质表示自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递性传递性集合表达式集合表达式IA RRIA=R=R1 RR1 IAR R R关系矩阵关系矩阵主主对对角角线线元元素素全是全是1 1主主对对角角线线元元素素全是全是0 0矩阵是对称矩阵。矩阵是对称矩阵。若若rij=1,且且ij,则则 rji=0.对对M2中中1所所在在的的位位置置,M中中相相应应的的位位置都是置都是1。关系图关系图每每个个顶顶点点都都有有环环每每个个顶顶点点都都没没有环有
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 关系 性质 离散数学
限制150内