《离散数学集合的笛卡儿积与二元关系.ppt》由会员分享，可在线阅读，更多相关《离散数学集合的笛卡儿积与二元关系.ppt（38页珍藏版）》请在三一办公上搜索。
1、1,第4章 二元关系与函数,4.1 集合的笛卡儿积与二元关系4.2 关系的运算4.3 关系的性质4.4 关系的闭包4.5 等价关系和偏序关系4.6 函数的定义和性质4.7 函数的复合和反函数,2,4.1 集合的笛卡儿积和二元关系,有序对 笛卡儿积及其性质 二元关系的定义 二元关系的表示,3,有序对,定义 由两个元素 x 和 y，按照一定的顺序组成的 二元组称为有序对，记作实例：平面直角坐标系中点的坐标有序对性质 1）有序性（当x y时）2）与 相等的充分必要条件是=x=u y=v,例1=，求 x,y.解 3y 4=2,x+5=y y=2,x=3,4,有序 n 元组,定义 一个有序 n(n3)元
2、组 是一个有序对，其中第一个元素是一个有序 n-1元组，即=,xn 实例：空间直角坐标系中的坐标 n 维向量是有序 n元组.当 n=1时,形式上可以看成有序 1 元组.,5,笛卡儿积,定义 设A,B为集合，用A中元素为第一个元素，B中元素为第二个元素，构成有序对.所有这样的有序对组成的集合叫做 A与B 的笛卡儿积 记作AB，即 AB=|xA yB 例2 A=1,2,3,B=a,b,c AB=,BA=,A=,P(A)A=,6,笛卡儿积的性质,不适合交换律 ABBA(AB,A,B)不适合结合律(AB)CA(BC)(A,B)对于并或交运算满足分配律 A(BC)=(AB)(AC)(BC)A=(BA)(
3、CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)若A或B中有一个为空集，则AB就是空集.A=B=若|A|=m,|B|=n,则|AB|=mn,7,性质的证明,证明 A(BC)=(AB)(AC)证 任取 A(BC)xAyBC xA(yByC)(xAyB)(xAyC)ABAC(AB)(AC)所以有A(BC)=(AB)(AC).,8,例题,解(1)任取 AC xA yC xB yD BD,例3(1)证明 A=B C=D AC=BD(2)AC=BD是否推出 A=B C=D?为什么？,(2)不一定.反例如下：A=1，B=2,C=D=,则 AC=BD 但是 AB.,9,例4(1)证明 A B
4、C D AC BD(2)AC BD是否推出 A B C D,解(1)任取 AC xA yC xB yD BD,(2)不一定.反例如下：A=1，B=2,C=D=,10,例5 设A、B、C、D为任意集合，判断以下等式是否成立，说明为什么。(AB)(C D)=(AC)(B D)(AB)(CD)=(AC)(B D)(A-B)(C-D)=(AC)-(BD)(AB)(CD)=(AC)(BD)解：(1)成立，因为对任意的(AB)(C D)xA B y C DxA x B y C y D AC BD,11,(2)(AB)(C D)=(AC)(B D)解：不成立，若A=D=B=C=1则有：(AB)(C D)=B
5、 C=(3)(A-B)(C-D)=(AC)-(BD)解：不成立，A=B=1 C=2 D=3(A-B)(C-D)=(AC)-(BD)=(4)(AB)(CD)=(AC)(BD)解：A=1 B=C=D=1(AB)(CD)=1,1(AC)(BD)=,12,设A1,A2,An是集合(n2),它们的n阶笛卡尔积记作A1A2 An,其中A1A2 An=x1A1,x2 A2,xnAn.当A1=A2=An时，可将它们的n阶笛卡尔积记作An例如：A=a,b,则A3=,13,二元关系：集合中两个元素之间的某种关系例1 甲、乙、丙3个人进行乒乓球比赛，任何两个人之间都要比赛一场。假设比赛结果是乙胜甲，甲胜丙，乙胜丙。
6、比赛结果可表示为：，其中表示x胜y，它表示了集合甲,乙,丙中元素之间的一种胜负关系.例2 有A、B、C3个人和四项工作G1、G2、G3、G4，已知A可以从事工作G1和G4，B可以从事工作G3，C可以从事工作G1和G2.那么，人和工作之间的对应关系可以记作 R,C,G2 它表示了集合A,B,C到工作G1,G2,G3,G4之间的关系,14,二元关系的定义,定义 如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系,简称为关系，记作R.如R,可记作 xRy；如果R,则记作x y实例：R=,S=,a,b.R是二元关系,当a,b不是有序对时，S不是二
7、元关系根据上面的记法，可以写 1R2,aRb,a c 等.,15,从A到B的关系与A上的关系,定义 设A,B为集合,AB的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做 A上的二元关系.例4 A=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个不同的二元关系.,16,A上重要关系的实例,设 A 为任意集合，是 A 上的关系，称为空关系EA,IA 分别称为全
8、域关系与恒等关系，定义如下：EA=|xAyA=AA IA=|xA例如,A=1,2,则 EA=,IA=,17,A上重要关系的实例（续）,小于等于关系 LA,整除关系DA,包含关系R定义：LA=|x,yAxy,AR，R为实数集合 DB=|x,yBx整除y,BZ+,Z+为非0整数集 R=|x,yAxy,A是集合族.类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.,18,实例,例如 A=1,2,3,B=a,b,则 LA=,DA=,A=P(B)=,a,b,a,b,则 A上的包含关系是 R=,19,关系的表示,表示方式：关系的集合表达式、关系矩阵、关系图 关系矩阵：若A=x1,x2,xm
9、，B=y1,y2,yn，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=rij mn,其中 rij=1 R.关系图：若A=x1,x2,xm，R是从A上的关系，R的关系图是GR=,其中A为结点集，R为边集.如果属于关系R，在图中就有一条从 xi 到 xj 的有向边.注意：A,B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系，关系图适于表示A上的关系,20,实例,A=1,2,3,4,R=,R的关系矩阵MR和关系图GR如下：,21,基本运算定义定义域、值域、域逆、合成、限制、像基本运算的性质幂运算定义求法性质,4.2 关系的运算,22,关系的基本运算定义,定义域、值域 和 域 domR=x|
10、y(R)ranR=y|x(R)fldR=domR ranR 例1 R=,则 domR=1,2,4 ranR=2,3,4 fldR=1,2,3,4,23,关系的基本运算定义（续）,定义 设F、G为任意的关系，A为集合，则逆与合成 F1=|F FG=|z(G F)例2 R=,S=,R1=,SR=,RS=,24,合成运算的图示方法,利用图示（不是关系图）方法求合成 RS=,SR=,RS,SR,25,限制与像,定义 F 在A上的限制 FA=|xFy xA A 在F下的像 FA=ran(FA)实例 R=,R1=,R1=2,4 R=R1,2=2,3,4注意：FAF,FA ranF,26,例.设F、G是N上
11、的关系，其定义为 F=x,y N y=x2 G=x,y N y=x+1求G1、FG、GF、F1,2、F1,2解：G1=y,xN y=x+1 G1=,对任何xN有 y=z2=(x+1)2，所以 FG=x,y N y=(x+1)2 GF=x,y N y=x2+1 F1,2=,F 1,2=ran(F1,2)=1,4,27,例.设F=,求FF、Fa、Fa解：FF=Fa=A=aFA=ran(FA)=ran=a,28,关系基本运算的性质,定理4.1 设F是任意的关系,则(1)(F1)1=F(2)domF1=ranF,ranF1=domF证(1)任取,由逆的定义有(F 1)1 F1 F所以有(F1)1=F(
12、2)任取x,xdomF1 y(F1)y(F)xranF 所以有domF1=ranF.同理可证 ranF1=domF.,29,(3)(FG)H=F(GH)(4)(FG)1=G1F1 证(3)任取,(FG)H t(H FG)t(H s(G)F)t s(H G F)s(Ft(HG)s(FGH)F(GH)所以(FG)H=F(GH),关系基本运算的性质（续）,30,(4)任取,(FG)1 FG t(G(t,x)F)t(F1(t,y)G1)G1F1 所以(FG)1=G1F1,关系基本运算的性质（续）,31,关系基本运算的性质（续）,定理4.2 设F、G、H为任意的二元关系，则有：F(G H)=F G FH
13、(G H)F=G F HF(合成运算对运算满足分配律）3.F(G H)F G FH4.(G H)F G F HF(合成运算对 运算分配后是包含关系）,32,A上关系的幂运算,设R为A上的关系,n为自然数,则 R 的 n次幂定义为：(1)R0=|xA=IA(2)Rn=Rn-1R,n1注意：对于A上的任何关系R1和R2都有 R10=R20=IA 对于A上的任何关系 R 都有 R1=R,33,幂的求法,(1)对于集合表示的关系R，计算 Rn 就是n个R左复合.(2)矩阵表示就是n个矩阵相乘,其中相加采用逻辑加.例3 设A=a,b,c,d,R=,求R的各次幂,分别用矩阵和关系图表示.解 R与R2的关系
14、矩阵分别为,34,同理，R0=IA,R3和R4的矩阵分别是：因此M4=M2,即R4=R2.因此可以得到R2=R4=R6=,R3=R5=R7=对于有穷集A，A上关系R的不同幂只有有限个。,幂的求法（续）,35,R0,R1,R2,R3,的关系图如下图所示,幂的求法（续）,36,幂运算的性质,定理3 设A为n元集,R是A上的关系,则存在自然数 s 和 t,使得 Rs=Rt.证 R为A上的关系,由于|A|=n,A上的不同关系只有 个.当列出 R 的各次幂 R0,R1,R2,必存在自然数 s 和 t 使得 Rs=Rt.,37,定理4 设 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+n+1,所以对一切m,nN有RmRn=Rm+n.,幂运算的性质（续）,38,(接上页证明)(2)对于任意给定的 mN,施归纳于n.若n=0,则有(Rm)0=IA=R0=Rm0 假设(Rm)n=Rmn,则有(Rm)n+1=(Rm)nRm=(Rmn)Rm=Rmn+m=Rm(n+1)所以对一切 m,nN 有(Rm)n=Rmn.,幂运算的性质（续）,
