第4章 二元关系与函数优秀课件.ppt

《第4章 二元关系与函数优秀课件.ppt》由会员分享，可在线阅读，更多相关《第4章 二元关系与函数优秀课件.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第1页，本讲稿共33页4.1 集合的笛卡儿积和二元关系集合的笛卡儿积和二元关系n 有序对有序对n 笛卡儿积及其性质笛卡儿积及其性质n 二元关系的定义二元关系的定义n 二元关系的表示二元关系的表示2第2页，本讲稿共33页有序对有序对定义定义 由两个元素由两个元素 x 和和 y，按照一定的顺序组成的，按照一定的顺序组成的 二元组称为二元组称为有序对有序对，记作，记作实例：平面直角坐标系中点的坐标实例：平面直角坐标系中点的坐标有序对性质有序对性质 1）有序性有序性 （当（当x y时）时）2）与与 相等的充分必要条件是相等的充分必要条件是 =x=u y=v例例1 =，求，求 x,y.解解 3y 4=

2、2,x+5=y y=2,x=3 3第3页，本讲稿共33页有序有序 n 元组元组定义定义 一个一个有序有序 n(n 3)元组元组 是一个是一个有序对，其中第一个元素是一个有序有序对，其中第一个元素是一个有序 n-1元组，即元组，即 =,xn 实例实例：空间直角坐标系中的坐标空间直角坐标系中的坐标 n 维向量是有序维向量是有序 n元组元组.当当 n=1时时,形式上可以看成有序形式上可以看成有序 1 元组元组.4第4页，本讲稿共33页笛卡儿积笛卡儿积定义定义 设设A,B为集合，用为集合，用A中元素为第一个元素，中元素为第一个元素，B中元中元素为第二个元素，构成有序对素为第二个元素，构成有序对.所有这

3、样的有序对组成所有这样的有序对组成的集合叫做的集合叫做 A与与B 的的笛卡儿积笛卡儿积 记作记作A B，即即 A B=|x A y B 例例2 A=1,2,3,B=a,b,c A B=,B A=,A=,P(A)A=,5第5页，本讲稿共33页笛卡儿积的性质笛卡儿积的性质不适合交换律不适合交换律 A B B A (A B,A,B)不适合结合律不适合结合律 (A B)C A(B C)(A,B)对于并或交运算满足分配律对于并或交运算满足分配律 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)若若A或或B中有一个为空

4、集，则中有一个为空集，则A B就是空集就是空集.A=B=若若|A|=m,|B|=n,则则|A B|=mn 6第6页，本讲稿共33页性质的证明性质的证明证明证明 A(B C)=(A B)(A C)证证 任取任取 A(BC)xAyBC xA(yByC)(xAyB)(xAyC)ABAC (AB)(AC)所以有所以有A(BC)=(AB)(AC).7第7页，本讲稿共33页例题例题 解解(1)任取任取 A C x A y C x B y D B D 例例3 (1)证明证明 A=B C=D A C=B D (2)A C=B D是否推出是否推出 A=B C=D?为什么？为什么？(2)不一定不一定.反例如下：反

5、例如下：A=1，B=2,C=D=,则则 A C=B D 但是但是 A B.8第8页，本讲稿共33页例例4 (1)证明证明 A B C D A C B D (2)A C B D是否推出是否推出 A B C D 解解(1)任取任取 A C x A y C x B y D B D (2)不一定不一定.反例如下：反例如下：A=1，B=2,C=D=9第9页，本讲稿共33页二元关系二元关系：集合中两个元素之间的某种关系：集合中两个元素之间的某种关系例例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之间的关系之间的关系10第10页，本讲稿共33

7、页二元关系的定义二元关系的定义定义定义 如果一个集合满足以下条件之一：如果一个集合满足以下条件之一：（1）集合非空）集合非空,且它的元素都是有序对且它的元素都是有序对（2）集合是空集）集合是空集则称该集合为一个则称该集合为一个二元关系二元关系,简称为简称为关系关系，记作，记作R.如如R,可记作可记作 xRy；如果；如果 R,则记作则记作x y实例：实例：R=,S=,a,b.R是二元关系是二元关系,当当a,b不是有序对时，不是有序对时，S不是二元关不是二元关系系根据上面的记法，可以写根据上面的记法，可以写 1R2,aRb,a c 等等.11第11页，本讲稿共33页从从A到到B的关系与的关系与A上

8、上的关系的关系定义定义 设设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个不同的二元关系个不同的二

9、元关系.12第12页，本讲稿共33页A上重要关系的实例上重要关系的实例设设 A 为任意集合，为任意集合，是是 A 上的关系，称为上的关系，称为空关系空关系EA,IA 分别称为分别称为全域关系全域关系与与恒等关系恒等关系，定义如下：，定义如下：EA=|xAyA=AA IA=|xA例如例如,A=1,2,则则 EA=,IA=,13第13页，本讲稿共33页A上重要关系的实例（续）上重要关系的实例（续）小于等于关系小于等于关系 LA,整除关系整除关系DA,包含关系包含关系R 定义：定义：LA=|x,yAxy,A R，R为实数集合为实数集合 DB=|x,yBx整除整除y,B Z*,Z*为非为非0整数集整数

10、集 R=|x,yAx y,A是集合族是集合族.类似的还可以定义大于等于关系类似的还可以定义大于等于关系,小于关系小于关系,大于关系大于关系,真真包含关系等等包含关系等等.14第14页，本讲稿共33页实例实例例如例如 A=1,2,3,B=a,b,则则 LA=,DA=,A=P(B)=,a,b,a,b,则则 A上的包含关系是上的包含关系是 R=,15第15页，本讲稿共33页关系的表示关系的表示表示方式：关系的集合表达式、关系矩阵、关系图表示方式：关系的集合表达式、关系矩阵、关系图 关系矩阵关系矩阵：若：若A=x1,x2,xm，B=y1,y2,yn，R是从是从A到到B的关系，的关系，R的关系矩阵是布尔

11、矩阵的关系矩阵是布尔矩阵MR=rij m n,其中其中 rij=1 R.关系图关系图：若：若A=x1,x2,xm，R是从是从A上的关系，上的关系，R的的关系图是关系图是GR=,其中其中A为结点集，为结点集，R为边集为边集.如果如果属于关系属于关系R，在图中就有一条从，在图中就有一条从 xi 到到 xj 的有向边的有向边.注意：注意：A,B为有穷集，关系矩阵适于表示从为有穷集，关系矩阵适于表示从A到到B的关的关系或者系或者A上的关系，关系图适于表示上的关系，关系图适于表示A上的关系上的关系 16第16页，本讲稿共33页实例实例A=1,2,3,4,R=,R的关系矩阵的关系矩阵MR和关系图和关系图G

12、R如下：如下：17第17页，本讲稿共33页n基本运算定义基本运算定义定义域、值域、域定义域、值域、域逆、合成、限制、像逆、合成、限制、像n基本运算的性质基本运算的性质n幂运算幂运算定义定义求法求法性质性质4.2 关系的运算关系的运算18第18页，本讲稿共33页关系的基本运算定义关系的基本运算定义定义域定义域、值域值域 和和 域域 domR=x|y(R)ranR=y|x(R)fldR=domR ranR 例例1 R=,则则 domR=1,2,4 ranR=2,3,4 fldR=1,2,3,4 19第19页，本讲稿共33页关系的基本运算定义（续）关系的基本运算定义（续）逆逆与与合成合成 R 1=|

13、R R S=|z(S R)例例2 R=,S=,R 1=,R S=,S R=,20第20页，本讲稿共33页合成运算的图示方法合成运算的图示方法 利用图示（不是关系图）方法求合成利用图示（不是关系图）方法求合成 R S=,S R=,21第21页，本讲稿共33页限制与像限制与像定义定义 F 在在A上的上的限制限制 F A=|xFy x A A 在在F下的下的像像 FA=ran(F A)实例例 R=,R 1=,R1=2,4 R=R1,2=2,3,4注意：注意：F A F,FA ranF 22第22页，本讲稿共33页关系基本运算的性质关系基本运算的性质 定理定理1 设设F是任意的关系是任意的关系,则则(

14、1)(F 1)1=F(2)domF 1=ranF,ranF 1=domF证证 (1)任取任取,由逆的定义有由逆的定义有 (F 1)1 F 1 F所以有所以有(F 1)1=F (2)任取任取x,xdomF 1 y(F 1)y(F)xranF 所以有所以有domF 1=ranF.同理可证同理可证 ranF 1=domF.23第23页，本讲稿共33页定理定理2 设设F,G,H是任意的关系是任意的关系,则则 (1)(F G)H=F(G H)(2)(F G)1=G 1 F 1 证证(1)任取任取,(F G)H t(H F G)t(H s(G)F)t s(H G F)s(F t(HG)s(FG H)F(G

15、 H)所以所以(F G)H=F(G H)关系基本运算的性质（续）关系基本运算的性质（续）24第24页，本讲稿共33页(2)任取任取,(F G)1 F G t(G(t,x)F)t(F 1(t,y)G 1)G 1 F 1 所以所以(F G)1=G 1 F 1 关系基本运算的性质（续）关系基本运算的性质（续）25第25页，本讲稿共33页关系基本运算的性质（续）关系基本运算的性质（续）设设F、G、H为任意的二元关系，则有：为任意的二元关系，则有：1.F (G H)=F G F H2.(G H)F=G F H F(合成运算对合成运算对 运算满足分配律）运算满足分配律）3.F (G H)F G F H4.

16、(G H)F G F H F(合成运算对合成运算对 运算分配后是包含关系）运算分配后是包含关系）26第26页，本讲稿共33页A上关系的幂运算上关系的幂运算设设R为为A上的关系上的关系,n为自然数为自然数,则则 R 的的 n次幂次幂定义为：定义为：(1)R0=|xA=IA (2)Rn+1=Rn R 注意：注意：对于对于A上的任何关系上的任何关系R1和和R2都有都有 R10=R20=IA 对于对于A上的任何关系上的任何关系 R 都有都有 R1=R 27第27页，本讲稿共33页幂的求法幂的求法(1)对于集合表示的关系对于集合表示的关系R，计算，计算 Rn 就是就是n个个R左复合左复合.(2)矩阵表示

17、就是矩阵表示就是n个矩阵相乘个矩阵相乘,其中相加采用逻辑加其中相加采用逻辑加.例例3 设设A=a,b,c,d,R=,求求R的各次幂的各次幂,分别用矩阵和关系图表示分别用矩阵和关系图表示.解解 R与与R2的关系矩阵分别为的关系矩阵分别为28第28页，本讲稿共33页同理，同理，R0=IA,R3和和R4的矩阵分别是：的矩阵分别是：因此因此M4=M2,即即R4=R2.因此可以得到因此可以得到R2=R4=R6=,R3=R5=R7=对于有穷集对于有穷集A，A上关系上关系R的不同幂只有有限个。的不同幂只有有限个。幂的求法（续）幂的求法（续）29第29页，本讲稿共33页R0,R1,R2,R3,的关系图如下图所

18、示的关系图如下图所示幂的求法（续）幂的求法（续）30第30页，本讲稿共33页幂运算的性质幂运算的性质定理定理3 设设A为为n元集元集,R是是A上的关系上的关系,则存在自然则存在自然数数 s 和和 t,使得使得 Rs=Rt.证证 R为为A上的关系上的关系,由于由于|A|=n,A上的不同关系只上的不同关系只有有 个个.当列出当列出 R 的各次幂的各次幂 R0,R1,R2,必存在自然数必存在自然数 s 和和 t 使得使得 Rs=Rt.31第31页，本讲稿共33页定理定理4 设设 R 是是 A 上的关系上的关系,m,nN,则则 (1)Rm Rn=Rm+n (2)(Rm)n=Rmn 证证 用归纳法用归纳

19、法 (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.幂运算的性质（续）幂运算的性质（续）32第32页，本讲稿共33页(接上页证明接上页证明)(2)对于任意给定的对于任意给定的 mN,施归纳于施归纳于n.若若n=0,则有则有(Rm)0=IA=R0=Rm0 假设假设(Rm)n=Rmn,则有则有(Rm)n+1=(Rm)n Rm=(Rmn)Rm=Rmn+m=Rm(n+1)所以对一切所以对一切 m,nN 有有(Rm)n=Rmn.幂运算的性质（续）幂运算的性质（续）33第33页，本讲稿共33页