离散数学 第四章 二元关系和函数精选文档.ppt

《离散数学 第四章 二元关系和函数精选文档.ppt》由会员分享，可在线阅读，更多相关《离散数学 第四章 二元关系和函数精选文档.ppt（30页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

2、y 4=2,x+5=y y=2,x=3 本讲稿第三页，共三十页3有序有序 n 元组元组定义定义 一个一个有序有序 n(n 3)元组元组 是一个是一个有序对，其中第一个元素是一个有序有序对，其中第一个元素是一个有序 n-1元组，即元组，即 =,xn 当当 n=1时时,形式上可以看成有序形式上可以看成有序 1 元组元组.实例实例 n 维向量是有序维向量是有序 n元组元组.本讲稿第四页，共三十页4笛卡儿积笛卡儿积定义定义 设设A,B为集合，为集合，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

3、=,本讲稿第五页，共三十页5笛卡儿积的性质笛卡儿积的性质不适合交换律不适合交换律 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中有一个为空集，则中有一个为空集，则A B就是空集就是空集.A=B=若若|A|=m,|B|=n,则则|A B|=mn 本讲稿第六页，共三十页6性质的证明性质的证明证明证明 A(B C)=(A B)(A C)证证 任取任取 A

4、(BC)xAyBC xA(yByC)(xAyB)(xAyC)ABAC (AB)(AC)所以有所以有A(BC)=(AB)(AC).本讲稿第七页，共三十页7例题例题 解解(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)不一定不一定.反例如下：反例如下：A=1，B=2,C=D=,则则 A C=B D 但是但是 A B.本讲稿第八页，共三十页8二元关系的定义二元关系的定义定义定义 如果一个集合满足以下条件之一：如果一个集合满足以下条件之一：（1）集合非空）集

5、合非空,且它的元素都是有序对且它的元素都是有序对（2）集合是空集）集合是空集则称该集合为一个则称该集合为一个二元关系二元关系,简称为简称为关系关系，记作，记作R.如如R,可记作可记作 xRy；如果；如果 R,则记作则记作x y实例：实例：R=,S=,a,b.R是二元关系是二元关系,当当a,b不是有序对时，不是有序对时，S不是二元关系不是二元关系根据上面的记法，可以写根据上面的记法，可以写 1R2,aRb,a c 等等.本讲稿第九页，共三十页9从从A到到B的关系与的关系与A上上的关系的关系定义定义 设设A,B为集合为集合,AB的任何子集所定义的二元的任何子集所定义的二元关系叫做关系叫做从从A到到

6、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个不同的二元关系个不同的二元关系.本讲稿第十页，共三十页10A上重要关系的实例上重要关系的实例设设 A 为任意集合，为任意集合，是是 A 上的关系，

7、称为上的关系，称为空关系空关系EA,IA 分别称为分别称为全域关系全域关系与与恒等关系恒等关系，定义如下：，定义如下：EA=|xAyA=AA IA=|xA例如例如,A=1,2,则则 EA=,IA=,本讲稿第十一页，共三十页11A上重要关系的实例（续）上重要关系的实例（续）小于等于关系小于等于关系 LA,整除关系整除关系DA,包含关系包含关系R 定义：定义：LA=|x,yAxy,A R，R为实数集合为实数集合 DB=|x,yBx整除整除y,B Z*,Z*为非为非0整数集整数集 R=|x,yAx y,A是集合族是集合族.类似的还可以定义大于等于关系类似的还可以定义大于等于关系,小于关系小于关系,大

8、于关系大于关系,真包含关系等等真包含关系等等.本讲稿第十二页，共三十页12实例实例例如例如 A=1,2,3,B=a,b,则则 LA=,DA=,A=P(B)=,a,b,a,b,则则 A上的包含关系是上的包含关系是 R=,本讲稿第十三页，共三十页13关系的表示关系的表示表示方式：关系的集合表达式、关系矩阵、关系图表示方式：关系的集合表达式、关系矩阵、关系图 关系矩阵关系矩阵：若：若A=a1,a2,am，B=b1,b2,bn，R是从是从A到到B的关系，的关系，R的关系矩阵是布尔矩阵的关系矩阵是布尔矩阵MR=rij m n,其其中中 rij=1 R.关系图关系图：若：若A=x1,x2,xm，R是从是从

9、A上的关系，上的关系，R的关的关系图是系图是GR=,其中其中A为结点集，为结点集，R为边集为边集.如果如果属于关系属于关系R，在图中就有一条从，在图中就有一条从 xi 到到 xj 的有向边的有向边.注意：注意：A,B为有穷集，关系矩阵适于表示从为有穷集，关系矩阵适于表示从A到到B的关系的关系或者或者A上的关系，关系图适于表示上的关系，关系图适于表示A上的关系上的关系 本讲稿第十四页，共三十页14实例实例A=1,2,3,4,R=,R的关系矩阵的关系矩阵MR和关系图和关系图GR如下：如下：本讲稿第十五页，共三十页15n基本运算定义基本运算定义定义域、值域、域定义域、值域、域逆、合成、限制、像逆、合

10、成、限制、像n基本运算的性质基本运算的性质n幂运算幂运算定义定义求法求法性质性质4.2 关系的运算关系的运算本讲稿第十六页，共三十页16关系的基本运算定义关系的基本运算定义定义域定义域、值域值域 和和 域域 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 本讲稿第十七页，共三十页17关系的基本运算定义（续）关系的基本运算定义（续）逆逆与与合成合成 R 1=|R R S=|y(R S)例例2 R=,S=,R 1=,R S=,S R=,本讲稿第十八页，共三十页18合成运算的图示方法合

11、成运算的图示方法 利用图示（不是关系图）方法求合成利用图示（不是关系图）方法求合成 R S=,S R=,本讲稿第十九页，共三十页19限制与像限制与像定义定义 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 本讲稿第二十页，共三十页20关系基本运算的性质关系基本运算的性质 定理定理1 设设F是任意的关系是任意的关系,则则(1)(F 1)1=F(2)domF 1=ranF,ranF 1=domF证证 (1)任取任取,由逆的定义有由逆的定义有 (F

12、 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.本讲稿第二十一页，共三十页21定理定理2 设设F,G,H是任意的关系是任意的关系,则则 (1)(F G)H=F(G H)(2)(F G)1=G 1 F 1 证证(1)任取任取,(F G)H t(F GH)t(s(FG)H)t s(FGH)s(F t(GH)s(FG H)F(G H)所以所以(F G)H=F(G H)关系基本运算的性质（续）关系基本运算的性质（续）本讲稿第二十二页，共三十页22(2)任取任

13、取,(F G)1 F G t(F(t,x)G)t(G 1(t,y)F 1)G 1 F 1 所以所以(F G)1=G 1 F 1 关系基本运算的性质（续）关系基本运算的性质（续）本讲稿第二十三页，共三十页23A上关系的幂运算上关系的幂运算设设R为为A上的关系上的关系,n为自然数为自然数,则则 R 的的 n次幂次幂定义为：定义为：(1)R0=|xA=IA (2)Rn+1=Rn R 注意：注意：对于对于A上的任何关系上的任何关系R1和和R2都有都有 R10=R20=IA 对于对于A上的任何关系上的任何关系 R 都有都有 R1=R 本讲稿第二十四页，共三十页24幂的求法幂的求法对于集合表示的关系对于集

14、合表示的关系R，计算，计算 Rn 就是就是n个个R右复合右复合.矩阵表示就是矩阵表示就是n个矩阵相乘个矩阵相乘,其中相加采用逻辑加其中相加采用逻辑加.例例3 设设A=a,b,c,d,R=,求求R的各次幂的各次幂,分别用矩阵和关系图表示分别用矩阵和关系图表示.解解 R与与R2的关系矩阵分别为的关系矩阵分别为本讲稿第二十五页，共三十页25同理，同理，R0=IA,R3和和R4的矩阵分别是：的矩阵分别是：因此因此M4=M2,即即R4=R2.因此可以得到因此可以得到R2=R4=R6=,R3=R5=R7=幂的求法（续）幂的求法（续）本讲稿第二十六页，共三十页26R0,R1,R2,R3,的关系图如下图所示的

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

16、法 (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.幂运算的性质（续）幂运算的性质（续）本讲稿第二十九页，共三十页29(接上页证明接上页证明)(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.幂运算的性质（续）幂运算的性质（续）本讲稿第三十页，共三十页30