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

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

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

2、 3y 4=2,x+5=y y=2,x=3 第3页，此课件共30页哦3有序有序 n 元组元组定义定义 一个一个有序有序 n(n 3)元组元组 是一个是一个有序对，其中第一个元素是一个有序有序对，其中第一个元素是一个有序 n-1元组，即元组，即 =,xn 当当 n=1时时,形式上可以看成有序形式上可以看成有序 1 元组元组.实例实例 n 维向量是有序维向量是有序 n元组元组.第4页，此课件共30页哦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

3、(A)A=,第5页，此课件共30页哦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页，此课件共30页哦6性质的证明性质的证明证明证明 A(B C)=(A B)(A C)证证

4、任取任取 A(BC)xAyBC xA(yByC)(xAyB)(xAyC)ABAC (AB)(AC)所以有所以有A(BC)=(AB)(AC).第7页，此课件共30页哦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页，此课件共30页哦8二元关系的定义二元关系的定义定义定义 如果一个集合满足以下条件之一：如果一个集合满足以下条件之一：（

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

6、关系叫做从从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个不同的二元关系个不同的二元关系.第10页，此课件共30页哦10A上重要关系的实例上重要关系的实例设设 A 为任意集合，为任意集合

7、，是是 A 上的关系，称为上的关系，称为空关系空关系EA,IA 分别称为分别称为全域关系全域关系与与恒等关系恒等关系，定义如下：，定义如下：EA=|xAyA=AA IA=|xA例如例如,A=1,2,则则 EA=,IA=,第11页，此课件共30页哦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页，此课件共30页哦12实例实例例如例如 A=1,2,3,B=a,b,则则 LA=,DA=,A=P(B)=,a,b,a,b,则则 A上的包含关系是上的包含关系是 R=,第13页，此课件共30页哦13关系的表示关系的表示表示方式：关系的集合表达式、关系矩阵、关系图表示方式：关系的集合表达式、关系矩阵、关系图 关系矩阵关系矩阵：若：若A=a1,a2,am，B=b1,b2,bn，R是是从从A到到B的关系，的关系，R的关系矩阵是布尔矩阵的关系矩阵是布尔矩阵MR=rij m n,其中其中 rij=1 R.关系图关系图：若：若A=

9、x1,x2,xm，R是从是从A上的关系，上的关系，R的关的关系图是系图是GR=,其中其中A为结点集，为结点集，R为边集为边集.如果如果属于关系属于关系R，在图中就有一条从，在图中就有一条从 xi 到到 xj 的有向边的有向边.注意：注意：A,B为有穷集，关系矩阵适于表示从为有穷集，关系矩阵适于表示从A到到B的关系或的关系或者者A上的关系，关系图适于表示上的关系，关系图适于表示A上的关系上的关系 第14页，此课件共30页哦14实例实例A=1,2,3,4,R=,R的关系矩阵的关系矩阵MR和关系图和关系图GR如下：如下：第15页，此课件共30页哦15n基本运算定义基本运算定义定义域、值域、域定义域、

10、值域、域逆、合成、限制、像逆、合成、限制、像n基本运算的性质基本运算的性质n幂运算幂运算定义定义求法求法性质性质4.2 关系的运算关系的运算第16页，此课件共30页哦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页，此课件共30页哦17关系的基本运算定义（续）关系的基本运算定义（续）逆逆与与合成合成 R 1=|R R S=|y(R S)例例2 R=,S=,R 1=,R S=,S R=,第18页，此

11、课件共30页哦18合成运算的图示方法合成运算的图示方法 利用图示（不是关系图）方法求合成利用图示（不是关系图）方法求合成 R S=,S R=,第19页，此课件共30页哦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页，此课件共30页哦20关系基本运算的性质关系基本运算的性质 定理定理1 设设F是任意的关系是任意的关系,则则(1)(F 1)1=F(2)domF 1=ranF,ranF 1=domF证证 (1

12、)任取任取,由逆的定义有由逆的定义有 (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.第21页，此课件共30页哦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)关系基本运算的性质（续）关系基本运算的性质（续）

13、第22页，此课件共30页哦22(2)任取任取,(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 关系基本运算的性质（续）关系基本运算的性质（续）第23页，此课件共30页哦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页，此课件共30页哦2

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

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

16、)(Rm)n=Rmn 证证 用归纳法用归纳法 (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页，此课件共30页哦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页，此课件共30页哦30