(1.5)--离散数学离散数学.ppt

《(1.5)--离散数学离散数学.ppt》由会员分享，可在线阅读，更多相关《(1.5)--离散数学离散数学.ppt（135页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、2024/1/202024/1/20离散数学离散数学1 1离 散 数 学2024/1/202024/1/20离散数学离散数学2 2问题引入问题引入问题引入问题引入问题问题问题问题1 1：现实生活中事物之间的关系如何用数学方：现实生活中事物之间的关系如何用数学方：现实生活中事物之间的关系如何用数学方：现实生活中事物之间的关系如何用数学方法刻划，如何用计算机进行处理？法刻划，如何用计算机进行处理？法刻划，如何用计算机进行处理？法刻划，如何用计算机进行处理？问题问题问题问题2 2：购买汽车的选择（价位、油耗、颜色）购买汽车的选择（价位、油耗、颜色）购买汽车的选择（价位、油耗、颜色）购买汽车的选择（价

2、位、油耗、颜色）序号序号 价位价位油耗油耗颜色颜色1 1中中高高红红2 2中中低低黑黑3 3高高低低黑黑4 4低低高高黑黑5 5高高高高黑黑6 6 中中高高兰兰2024/1/202024/1/20离散数学离散数学3 3 第四章第四章 二元关系和函数二元关系和函数 4.14.1 集合的笛卡尔积与二元关系集合的笛卡尔积与二元关系集合的笛卡尔积与二元关系集合的笛卡尔积与二元关系 4.24.2 关系的运算关系的运算关系的运算关系的运算 4.34.3 关系的性质关系的性质关系的性质关系的性质 4.44.4 关系的闭包关系的闭包关系的闭包关系的闭包 4.54.5 等价关系和偏序关系等价关系和偏序关系等价关

3、系和偏序关系等价关系和偏序关系 4.64.6 函数的定义和性质函数的定义和性质函数的定义和性质函数的定义和性质 4.74.7 函数的复合和反函数函数的复合和反函数函数的复合和反函数函数的复合和反函数2024/1/202024/1/20离散数学离散数学4 44.1 4.1 集合的笛卡尔积与二元关系集合的笛卡尔积与二元关系内容：内容：有序对，笛卡儿积，二元关系。重点：重点：(1)掌握有序对的概念，(2)笛卡儿积及性质，(3)二元关系的定义及三种表示法，(4)一些特殊的二元关系。了解：了解：有序 元组和 阶笛卡儿积。2024/1/202024/1/20离散数学离散数学5 54.1 4.1 集合的笛卡

4、尔积与二元关系集合的笛卡尔积与二元关系一、二元关系的概念有序对（序偶）：有序对（序偶）：有序对（序偶）：有序对（序偶）：由两个元素由两个元素由两个元素由两个元素x x 和和和和y y 按一定按一定按一定按一定顺序顺序顺序顺序排成排成排成排成 的二元组。记作：的二元组。记作：的二元组。记作：的二元组。记作：。其中。其中。其中。其中x x是它的第是它的第是它的第是它的第 一元素，一元素，一元素，一元素，y y是它的第二元素。是它的第二元素。是它的第二元素。是它的第二元素。特点：特点：特点：特点：(1)(1)当当当当x x y y 时，时，时，时，(2)(2)=当且仅当当且仅当当且仅当当且仅当x x

5、=u u,y y=v v 如平面直角坐标系点的坐标。如平面直角坐标系点的坐标。如平面直角坐标系点的坐标。如平面直角坐标系点的坐标。2024/1/202024/1/20离散数学离散数学6 6一、二元关系的概念（续）笛卡尔积：笛卡尔积：笛卡尔积：笛卡尔积：设设设设A A、B B为两集合，为两集合，为两集合，为两集合，以以以以A A中元素为第一元中元素为第一元中元素为第一元中元素为第一元 素，素，素，素，B B中元素为第二元素构成的二元有中元素为第二元素构成的二元有中元素为第二元素构成的二元有中元素为第二元素构成的二元有 序对的全体叫做序对的全体叫做序对的全体叫做序对的全体叫做A A和和和和B B的

6、笛卡儿积。的笛卡儿积。的笛卡儿积。的笛卡儿积。记作：记作：记作：记作：A A B B 符号化符号化符号化符号化 A A B B=|x x A A y y B B 例例1:已知已知 =，求，求 x,y.解解 3y 4=2,x+5=y y=2,x=3 2024/1/202024/1/20离散数学离散数学7 7一、二元关系的概念（续）一般地，若一般地，若一般地，若一般地，若|A A|=|=mm,|,|B B|=|=n n,则则则则|A A B B|=|=|B B A A|=|=mnmn 例例2:A=1,2,3,B=a,b,c A B=,B A=,设设A=,P(A)A=,2024/1/202024/1

7、/20离散数学离散数学8 8一、二元关系的概念（续）笛卡尔积运算的性质：笛卡尔积运算的性质：笛卡尔积运算的性质：笛卡尔积运算的性质：(1)(1)(1)(1)如果如果如果如果A A,B B中有一个空集，则笛卡儿积是空集，中有一个空集，则笛卡儿积是空集，中有一个空集，则笛卡儿积是空集，中有一个空集，则笛卡儿积是空集，即：即：即：即：B B=A A =(3)(3)(3)(3)不满足结合律：不满足结合律：不满足结合律：不满足结合律：当当当当A A,B B,C C都不是空集时，有都不是空集时，有都不是空集时，有都不是空集时，有 (A A B B)C C A A (B B C C)。(2)(2)(2)(2

8、)不满足交换律：不满足交换律：不满足交换律：不满足交换律：当当当当A A B B，且且且且A A,B B都不是空集时，有都不是空集时，有都不是空集时，有都不是空集时，有 A A B B B B A A。2024/1/202024/1/20离散数学离散数学9 9一、二元关系的概念（续）(4)(4)(4)(4)笛卡尔积运算对笛卡尔积运算对笛卡尔积运算对笛卡尔积运算对或或或或 运算满足分配律，运算满足分配律，运算满足分配律，运算满足分配律，即即即即A A (B BC C)=(A A B B)(A A C C)(B BC C)A=A=(B B A A)(C C A A)A A (B B C C)=(A

9、 A B B)(A A C C)(B B C C)A=A=(B B A A)(C C A A)证明：证明：证明：证明：(B BC C)A A x x B BC C y y A A (x x B B x x C C)y y A A (x x B B y y A A)(x x C C y y A A)(B B A A)(C C A A)(B B A A)(C C A A)2024/1/202024/1/20离散数学离散数学1010解解(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

10、=D?为什么？为什么？(2)不一定不一定.反例如下：反例如下：A=1，B=2,C=D=,则则 A C=B D 但是但是 A B.一、二元关系的概念（续）2024/1/202024/1/20离散数学离散数学1111一、二元关系的概念（续）推广：推广：推广：推广：n n阶笛卡尔积阶笛卡尔积阶笛卡尔积阶笛卡尔积 A A1 1 A A2 2 A An n =|x x1 1 A A1 1 x x2 2 A A2 2 x xn n A An n 2024/1/202024/1/20离散数学离散数学1212一、二元关系的概念（续）二元关系的数学定义：二元关系的数学定义：二元关系的数学定义：二元关系的数学定义

11、：如果一个集合为如果一个集合为如果一个集合为如果一个集合为 （1 1 1 1）空集空集空集空集,或者或者或者或者 （2 2 2 2）它的元素都是二元有序对，）它的元素都是二元有序对，）它的元素都是二元有序对，）它的元素都是二元有序对，则这个集合称为一个二元关系，记作：则这个集合称为一个二元关系，记作：则这个集合称为一个二元关系，记作：则这个集合称为一个二元关系，记作：R R 如果如果如果如果 R R ，记作记作记作记作 x x R yR y 如果如果如果如果 R R ，记作记作记作记作 x R yx R y实例：实例：实例：实例：R R=,=,S S=,=,a a,b b.R R是二元关系是二

12、元关系是二元关系是二元关系,当当当当a a,b b不是有序对时，不是有序对时，不是有序对时，不是有序对时，S S不是二元关系不是二元关系不是二元关系不是二元关系根据上面的记法，可以写根据上面的记法，可以写根据上面的记法，可以写根据上面的记法，可以写 1 1R R2,2,aRbaRb,a R c a R c 等等等等.2024/1/202024/1/20离散数学离散数学1313一、二元关系的概念（续）从从从从A A到到到到B B的二元关系：的二元关系：的二元关系：的二元关系：设设设设A A、B B为集合，为集合，为集合，为集合，A A B B的的的的任何子集任何子集任何子集任何子集所定义的二元关

13、系所定义的二元关系所定义的二元关系所定义的二元关系叫做从叫做从叫做从叫做从A A到到到到B B的的的的 二元关系。二元关系。二元关系。二元关系。特别地，若特别地，若特别地，若特别地，若A A=B B，叫作，叫作，叫作，叫作A A上的二元关系。上的二元关系。上的二元关系。上的二元关系。例例4：A=0,1,B=1,2,3,R1=,R2=AB,R3=,R4=.那么那么 R1,R2,R3,R4是从是从 A 到到 B 的二元关系的二元关系,R3和和R4同时也是同时也是 A上的二元关系上的二元关系.2024/1/202024/1/20离散数学离散数学1414一、二元关系的概念（续）若若若若|A A|=n

14、n，则，则，则，则|A A A A|=n n2 2 ，A A A A的所有子集有的所有子集有的所有子集有的所有子集有 个，个，个，个，因此，因此，因此，因此，A A上有上有上有上有 个不同的二元关系。个不同的二元关系。个不同的二元关系。个不同的二元关系。例如例如例如例如|A A|=3,|=3,则则则则 A A上有上有上有上有=512=512个不同的二元关系个不同的二元关系个不同的二元关系个不同的二元关系.2024/1/202024/1/20离散数学离散数学1515一、二元关系的概念（续）A A的的的的3 3种特殊关系种特殊关系种特殊关系种特殊关系：空关系空关系空关系空关系，全域关系全域关系全域

15、关系全域关系E EA A，恒等关系恒等关系恒等关系恒等关系I IA A空关系空关系空关系空关系即空集即空集即空集即空集恒等关系恒等关系恒等关系恒等关系I IA A=|x x A A 全域关系全域关系全域关系全域关系E EA A =|x x A A y y A A =A A A A例如例如例如例如,A A=1,2,=1,2,则则则则E EA A=,=,I IA A=,=,2024/1/202024/1/20离散数学离散数学1616一、二元关系的概念（续）常用关系：常用关系：常用关系：常用关系：（1 1）设）设）设）设A A R R,A A上上上上小于等于关系小于等于关系小于等于关系小于等于关系：

16、L LA A x x,y y A A x x y y。（2 2）设）设）设）设B B Z Z+,B B上上上上整除关系整除关系整除关系整除关系：D DB B x x,y y B B x x y y。（3 3）幂集）幂集）幂集）幂集P P(A A)上的上的上的上的包含关系包含关系包含关系包含关系R R:R R x x,y y P P(A A)x x y y。2024/1/202024/1/20离散数学离散数学1717一、二元关系的概念（续）例例例例5 5：设：设：设：设A A=2,3,6,8=2,3,6,8，求，求，求，求L LA A，D DA A。解：解：解：解：L LA A ,D DA A=

17、,=,2024/1/202024/1/20离散数学离散数学1818一、二元关系的概念（续）例例例例6 6：设：设：设：设A A=a a,b b，写出，写出，写出，写出P P(A A)上的包含关系上的包含关系上的包含关系上的包含关系R R。解：解：解：解：P P(A A)=)=,a a,b b,a a,b b R R=,2024/1/202024/1/20离散数学离散数学1919二、二元关系的表示方法1 1、关系矩阵关系矩阵关系矩阵关系矩阵 设设设设A A=x x1 1,x x2 2,x xn n ，R R是是是是A A上的关系，上的关系，上的关系，上的关系，r rij ij=1 1 若若若若x

18、 xi i R R x xj j0 0 若若若若x xi i R R x xj j令令令令 (i,ji,j=1,2,=1,2,n n)则则则则(r rij ij)n n n n=是是是是R R的关系矩阵的关系矩阵的关系矩阵的关系矩阵 2024/1/202024/1/20离散数学离散数学2020二、二元关系的表示方法（续）例例例例7 7：设：设：设：设A A=1,2,3,4,=1,2,3,4,R R=1,2,1,3,2,2,2,4,3,4,4,2 是是是是A A上的关系，试写出上的关系，试写出上的关系，试写出上的关系，试写出R R的的的的 关系矩阵并画出关系图。关系矩阵并画出关系图。关系矩阵并画

19、出关系图。关系矩阵并画出关系图。解：解：解：解：关系矩阵关系矩阵关系矩阵关系矩阵 2024/1/202024/1/20离散数学离散数学2121二、二元关系的表示方法（续）2 2、关系图关系图关系图关系图 以以以以V V=A A=x x1 1,x x2 2,x xn n 为顶点的集合，为顶点的集合，为顶点的集合，为顶点的集合，以以以以E E=|x xi i A A x xj j A A x xi i R R x xj j 为有向边的为有向边的为有向边的为有向边的集合集合集合集合，组成的有向图，组成的有向图，组成的有向图，组成的有向图G G=。注意：注意：注意：注意：A A,B B为有穷集，为有穷

20、集，为有穷集，为有穷集，关系矩阵适于表示从关系矩阵适于表示从关系矩阵适于表示从关系矩阵适于表示从A A到到到到B B的关系或者的关系或者的关系或者的关系或者A A上的关系，上的关系，上的关系，上的关系，关系图适于表示关系图适于表示关系图适于表示关系图适于表示A A上的关系。上的关系。上的关系。上的关系。2024/1/202024/1/20离散数学离散数学2222二、二元关系的表示方法（续）例例例例7 7：设：设：设：设A A=1,2,3,4,=1,2,3,4,R R=1,2,1,3,2,2,2,4,3,4,4,2 是是是是A A上的关系，试写出上的关系，试写出上的关系，试写出上的关系，试写出R

21、 R的的的的 关系矩阵并画出关系图。关系矩阵并画出关系图。关系矩阵并画出关系图。关系矩阵并画出关系图。解：解：解：解：关系矩阵关系矩阵关系矩阵关系矩阵 关系图关系图关系图关系图 1 1 2 24 4 3 32024/1/202024/1/20离散数学离散数学2323内容：内容：关系的定义域，值域，逆关系，合成关系。重点：重点：(1)掌握逆关系，合成关系的概念及求法，(2)掌握关系 次幂的概念及性质。一般：一般：关系的定义域，值域。4.2 4.2 关系的运算关系的运算2024/1/202024/1/20离散数学离散数学2424问题：问题：问题：问题：学生成绩查询系统学生成绩查询系统学生成绩查询系

22、统学生成绩查询系统 学生成绩数据库学生成绩数据库学生成绩数据库学生成绩数据库 学号、姓名、课程、分数学号、姓名、课程、分数学号、姓名、课程、分数学号、姓名、课程、分数 数据的查询、选择、合并、删除、连接、数据的查询、选择、合并、删除、连接、数据的查询、选择、合并、删除、连接、数据的查询、选择、合并、删除、连接、修改等修改等修改等修改等2024/1/202024/1/20离散数学离散数学2525集合运算在关系数据库中的应用集合运算在关系数据库中的应用集合运算在关系数据库中的应用集合运算在关系数据库中的应用表表表表1 1：数据表：数据表：数据表：数据表R R和数据表和数据表和数据表和数据表S S2

23、024/1/202024/1/20离散数学离散数学26261 1、数据表的并、数据表的并、数据表的并、数据表的并R RS S2024/1/202024/1/20离散数学离散数学27272 2、数据表的交、数据表的交、数据表的交、数据表的交RSRS2 2、数据表的差、数据表的差、数据表的差、数据表的差R-SR-S2024/1/202024/1/20离散数学离散数学2828 关系数据库中的这些集合运算都可以通过相应的关系数据库中的这些集合运算都可以通过相应的关系数据库中的这些集合运算都可以通过相应的关系数据库中的这些集合运算都可以通过相应的数据库编程语言来实现数据库编程语言来实现数据库编程语言来实

24、现数据库编程语言来实现.数学集合在关系数据库中的作用十分明显数学集合在关系数据库中的作用十分明显数学集合在关系数据库中的作用十分明显数学集合在关系数据库中的作用十分明显,能够利能够利能够利能够利用已知的数据表通过该运算产生新的结构相同的数用已知的数据表通过该运算产生新的结构相同的数用已知的数据表通过该运算产生新的结构相同的数用已知的数据表通过该运算产生新的结构相同的数据表据表据表据表,使用结果数据表可以进行某些记录的删除操作使用结果数据表可以进行某些记录的删除操作使用结果数据表可以进行某些记录的删除操作使用结果数据表可以进行某些记录的删除操作,又可以进行提取操作又可以进行提取操作又可以进行提取

25、操作又可以进行提取操作,来快速提取满足特殊要求的数来快速提取满足特殊要求的数来快速提取满足特殊要求的数来快速提取满足特殊要求的数据等据等据等据等.2024/1/202024/1/20离散数学离散数学2929集合运算与实体构造：集合运算与实体构造：集合运算与实体构造：集合运算与实体构造：两个圆柱实体的并、差、交运算结果两个圆柱实体的并、差、交运算结果两个圆柱实体的并、差、交运算结果两个圆柱实体的并、差、交运算结果2024/1/202024/1/20离散数学离散数学3030关系关系关系关系R R的定义域：的定义域：的定义域：的定义域：dom R dom R=x x|y y(R R)，即即即即R R

26、中所有有序对的第一元素构成的集合。中所有有序对的第一元素构成的集合。中所有有序对的第一元素构成的集合。中所有有序对的第一元素构成的集合。一、关系的定义域与值域4.2 4.2 关系的运算关系的运算关系关系关系关系R R的值域：的值域：的值域：的值域：ran R ran R=y y|x x(R R)，即即即即R R中所有有序对的第二元素构成的集合。中所有有序对的第二元素构成的集合。中所有有序对的第二元素构成的集合。中所有有序对的第二元素构成的集合。关系关系关系关系R R的域：的域：的域：的域：fld R fld R=dom Rdom Rran R ran R 例如例如例如例如 R R=,=,则则则

27、则 dom Rdom R=1,2,4=1,2,4，ran Rran R=2,3,4=2,3,4，fld Rfld R=1,2,3,4=1,2,3,42024/1/202024/1/20离散数学离散数学3131一、关系的定义域与值域（续）例例例例8 8：分别求出下列关系的定义域和值域。：分别求出下列关系的定义域和值域。：分别求出下列关系的定义域和值域。：分别求出下列关系的定义域和值域。(1)(1)R R1 1=|x x,y y Z Z x x y y;(2)(2)R R2 2=|x x,y y Z Z x x2 2+y y2 2 =1;=1;(3)(3)R R3 3=|x x,y y 1,2,3

28、,41,2,3,4 x x y y 解解解解：(1)(1)domdom R R1 1=ranran R R1 1=Z Z(2)(2)R R2 2=,(3)(3)R R3 3=,dom dom R R2 2=ranran R R2 2=0,1,-1 =0,1,-1 dom dom R R3 3=2,3,4=2,3,4，ranran R R3 3=1,2,3 =1,2,3 2024/1/202024/1/20离散数学离散数学32321 1、逆：逆：逆：逆：2 2、合成：合成：合成：合成：任意两个关系任意两个关系任意两个关系任意两个关系F F与与与与G G的合成，记作：的合成，记作：的合成，记作：的

29、合成，记作：F F G G F F G G=|z z(xGz xGz zFy zFy)二、关系的常用运算 F F是任意关系，是任意关系，是任意关系，是任意关系，F F 的逆的逆的逆的逆F F -1 1=|yFx yFx 例如例如例如例如 R R=,=,S S=,=,R R 1 1=,=,R R S S=,=,S S R R=,=,2024/1/202024/1/20离散数学离散数学33333 3、限制：限制：限制：限制：4 4、象：象：象：象：二、关系的常用运算 关系关系关系关系F F在集合在集合在集合在集合A A上的限制，记作：上的限制，记作：上的限制，记作：上的限制，记作：F F A A

30、F F A A=|xFy xFy x x A A 集合集合集合集合A A在在在在F F 下的象，记作：下的象，记作：下的象，记作：下的象，记作：F F A A F F A A=ran ran(F F A A)例如例如 R=,R 1=,，R1=2,4 R =，R1,2=2,3,42024/1/202024/1/20离散数学离散数学3434二、关系的常用运算（续）例例例例9 9：设：设：设：设F F,G G是是是是N N上的关系，其定义为上的关系，其定义为上的关系，其定义为上的关系，其定义为 F F=|x x,y y N N y=y=x x2 2 G G=|x x,y y N N y=y=x x+

31、1+1 求求求求G G 1 1,F F G G,G G F F,F F 1,2,1,2,F F 1,21,2。解：解：解：解：G G 1 1=|x x,y y N N y=y=x x+1+1 列出列出列出列出G G 1 1中的元素即为中的元素即为中的元素即为中的元素即为 G G 1 1=,2024/1/202024/1/20离散数学离散数学3535二、关系的常用运算（续）例例例例9 9：设：设：设：设F F,G G是是是是N N上的关系，其定义为上的关系，其定义为上的关系，其定义为上的关系，其定义为 F F=|x x,y y N N y=y=x x2 2 G G=|x x,y y N N y=

32、y=x x+1+1 求求求求G G 1 1,F F G G,G G F F,1,2,1,2,F F 1,21,2。解：为了求解：为了求解：为了求解：为了求F F G G可以先直观表示如下：可以先直观表示如下：可以先直观表示如下：可以先直观表示如下：对任何对任何对任何对任何x x N N x x x x+1=+1=z z z z2 2=y y G GF F因此因此因此因此F F G G=|x x,y y N N y y=(=(x x+1)1)2 2 即即即即 y y=(=(x x+1)+1)2 2 2024/1/202024/1/20离散数学离散数学3636二、关系的常用运算（续）例例例例9 9

33、：设：设：设：设F F,G G是是是是N N上的关系，其定义为上的关系，其定义为上的关系，其定义为上的关系，其定义为 F F=|x x,y y N N y=y=x x2 2 G G=|x x,y y N N y=y=x x+1+1 求求求求G G 1 1,F F G G,G G F F,F F 1,2,1,2,F F 1,21,2。解：为了求解：为了求解：为了求解：为了求G G F F可以先直观表示如下：可以先直观表示如下：可以先直观表示如下：可以先直观表示如下：对任何对任何对任何对任何x x N N x x x x2 2=z z z z+1=+1=y yF FG G因此因此因此因此G G F

34、 F=|x x,y y N N y y=x x2 2+1+1 即即即即 y y=x x2 2+1+12024/1/202024/1/20离散数学离散数学3737二、关系的常用运算（续）例例例例9 9：设：设：设：设F F,G G是是是是N N上的关系，其定义为上的关系，其定义为上的关系，其定义为上的关系，其定义为 F F=|x x,y y N N y=y=x x2 2 G G=|x x,y y N N y=y=x x+1+1 求求求求G G 1 1,F F G G,G G F F,F F 1,2,1,2,F F 1,21,2。解：解：解：解：F F 1,2=1,2=,F F 1,21,2 =r

35、anran(F F 1,2)=1,2)=1,4 1,4 注意：注意：F A F,FA ranF 2024/1/202024/1/20离散数学离散数学3838三、关系运算的性质1 1、(F F 1 1)1 1=F F2 2、domdom F F 1 1=ranran F F,ran ran F F 1 1=dom F =dom F 3 3、(F F G G)HH =F F (G G HH )4 4、(F F G G)1 1=G G 1 1 F F 1 1 5 5、F F (G GHH)=(F F G G)(F F HH)6 6、F F (G G HH)(F F G G)(F F HH)8 8、(

36、G G HH)F F (G G F F)(HH F F)7 7、(G GHH)F F=(G G F F)(HH F F)2024/1/202024/1/20离散数学离散数学3939三、关系运算的性质（续）4 4、(F F G G)1 1=G G 1 1 F F 1 1的证明。的证明。的证明。的证明。对任意对任意对任意对任意 (F F G G)1 1 F F G G z z(G G F F)z z(G G 1 1 F F 1 1)z z(F F 1 1 G G 1 1)G G 1 1 F F 1 12024/1/202024/1/20离散数学离散数学4040三、关系运算的性质（续）6 6、F F

37、 (G G HH)(F F G G)(F F HH)的证明。的证明。的证明。的证明。对任意对任意对任意对任意 F F (G G HH)z z(G G HH F F)z z(G G H H F F)z z(G G F F)(H H F F)z z(G G F F)z z(HH F F)F F G G F F HH (F F G G)(F F HH)2024/1/202024/1/20离散数学离散数学4141四、关系的幂运算设设设设R R是是是是A A上的关系，上的关系，上的关系，上的关系，n n为自然数，则：为自然数，则：为自然数，则：为自然数，则：(1)(1)R R0 0=|x x A A (

38、2)(2)R Rn n=R Rn n-1-1 R R,n n 1 1定理 (1)(1)R Rm m R Rn n=R Rm+nm+n (2)(2)(R Rmm)n n =R Rmnmn其中其中其中其中mm,n n为自然数。为自然数。为自然数。为自然数。2024/1/202024/1/20离散数学离散数学4242四、关系的幂运算（续）例例例例1010：设：设：设：设A A=a a,b b,c c,d d ，A A上的一个关系上的一个关系上的一个关系上的一个关系 R R=,求求求求R R0 0，R R2 2，R R3 3。解：解：解：解：R R0 0 =,由由由由R R的关系图知的关系图知的关系图

39、知的关系图知R R2 2 =R R R R=,a a b bd d c cR R3 3 =,2024/1/202024/1/20离散数学离散数学4343R R3 3 =R R2 2 R R=,四、关系的幂运算（续）例例例例1010：设：设：设：设A A=a a,b b,c c,d d ，A A上的一个关系上的一个关系上的一个关系上的一个关系 R R=,求求求求R R0 0，R R2 2，R R3 3。R R2 2 =R R R R=,R R的关系矩阵的关系矩阵的关系矩阵的关系矩阵2024/1/202024/1/20离散数学离散数学4444R0,R1,R2,R3,的关系图如下图所示的关系图如下图

40、所示2024/1/202024/1/20离散数学离散数学4545考虑如下关系的区别考虑如下关系的区别考虑如下关系的区别考虑如下关系的区别（1 1）实数的小于等于关系）实数的小于等于关系）实数的小于等于关系）实数的小于等于关系（2 2）实数的小于关系）实数的小于关系）实数的小于关系）实数的小于关系（3 3）网站之间的连接关系）网站之间的连接关系）网站之间的连接关系）网站之间的连接关系（4 4）同学关系）同学关系）同学关系）同学关系（5 5）长幼关系与朋友关系）长幼关系与朋友关系）长幼关系与朋友关系）长幼关系与朋友关系2024/1/202024/1/20离散数学离散数学46464.3 4.3 关系

41、的性质关系的性质内容：关系的自反性，反自反性，对称性，反内容：关系的自反性，反自反性，对称性，反对称性，传递性。对称性，传递性。重点：重点：(1)(1)掌握自反性，反自反性，对称性，掌握自反性，反自反性，对称性，反对称性，传递性的定义及关系矩阵和关系图反对称性，传递性的定义及关系矩阵和关系图的特征，的特征，(2)(2)掌握关系五种性质的判断和验证。掌握关系五种性质的判断和验证。2024/1/202024/1/20离散数学离散数学47474.3 4.3 关系的性质关系的性质1 1、自反性（、自反性（、自反性（、自反性（reflexive ）：）：）：）：x x A A，有有有有 R R 设设设设

42、R R是是是是A A上的关系上的关系上的关系上的关系R R的关系矩阵：主对角线元素全为的关系矩阵：主对角线元素全为的关系矩阵：主对角线元素全为的关系矩阵：主对角线元素全为1 1R R的关系图：每个顶点都有环的关系图：每个顶点都有环的关系图：每个顶点都有环的关系图：每个顶点都有环2 2、反自反性：、反自反性：、反自反性：、反自反性：x x A A，有有有有 R RR R的关系矩阵：主对角线元素全为的关系矩阵：主对角线元素全为的关系矩阵：主对角线元素全为的关系矩阵：主对角线元素全为0 0R R的关系图：每个顶点都没有环的关系图：每个顶点都没有环的关系图：每个顶点都没有环的关系图：每个顶点都没有环完

43、全完全完全完全否定否定否定否定2024/1/202024/1/20离散数学离散数学4848例如例如例如例如 A A=1,2,3,=1,2,3,R R1 1,R R2 2,R R3 3是是是是A A上的关系上的关系上的关系上的关系,其中其中其中其中 R R1 1,R R2 2,R R3 3R2自反自反,R3反自反反自反,R1既不是自反也不是反自反的既不是自反也不是反自反的2024/1/202024/1/20离散数学离散数学49493 3、对称性（、对称性（、对称性（、对称性（symmetric ）：）：）：）：若若若若 R R，则，则，则，则 R RR R的关系矩阵：对称阵的关系矩阵：对称阵的关

44、系矩阵：对称阵的关系矩阵：对称阵R R的关系图：若两个顶点间有边，则一定的关系图：若两个顶点间有边，则一定的关系图：若两个顶点间有边，则一定的关系图：若两个顶点间有边，则一定 是一对方向相反的边。是一对方向相反的边。是一对方向相反的边。是一对方向相反的边。4 4、反对称性、反对称性、反对称性、反对称性(transitive):若若若若 R R且且且且x x y y，则则则则 R RR R的关系矩阵：若的关系矩阵：若的关系矩阵：若的关系矩阵：若r rij ij=1=1，且，且，且，且i i j j，则，则，则，则r rji ji=0=0R R的关系图：若两个顶点间有边，则一定的关系图：若两个顶点

45、间有边，则一定的关系图：若两个顶点间有边，则一定的关系图：若两个顶点间有边，则一定 是只有一条有向边。是只有一条有向边。是只有一条有向边。是只有一条有向边。关系的性质2024/1/202024/1/20离散数学离散数学5050例如：例如：例如：例如：设设设设A A1,2,3,1,2,3,R R1 1,R R2 2,R R3 3和和和和R R4 4都是都是都是都是A A上的关系上的关系上的关系上的关系,其中其中其中其中 R R1 1,，R R2 2,R R3 3,，R R4 4,R1 对称、反对称对称、反对称.R2 对称，不反对称对称，不反对称.R3 反对称，不对称反对称，不对称.R4 不对称、

46、也不反对称不对称、也不反对称.2024/1/202024/1/20离散数学离散数学51515 5、传递性：、传递性：、传递性：、传递性：若若若若 R R且且且且 R R，则，则，则，则 R RR R的关系图：若顶点的关系图：若顶点的关系图：若顶点的关系图：若顶点x xi i 到到到到x xj j 有边，有边，有边，有边，x xj j 到到到到x xk k 有边，有边，有边，有边，则则则则x xi i 到到到到x xk k 有边。有边。有边。有边。关系的性质2024/1/202024/1/20离散数学离散数学5252例如：例如：例如：例如：设设设设A A1,2,3,1,2,3,R R1 1,R

47、R2 2,R R3 3是是是是A A上的关系上的关系上的关系上的关系,其中其中其中其中 R R1 1,R R2 2,R R3 3,R R4 4=R R1 1、R R3 3和和和和 R R4 4 是是是是A A上的传递关系上的传递关系上的传递关系上的传递关系 R R2 2不是不是不是不是A A上的传递关系上的传递关系上的传递关系上的传递关系2024/1/202024/1/20离散数学离散数学5353例例例例1111：设：设：设：设A A=1,2,3=1,2,3，A A上的关系上的关系上的关系上的关系 （1 1 1 1）R R1 1=,=,（2 2）R R2 2=,=,（3 3）R R3 3=,=

48、,（4 4）R R4 4=,=,判断以上关系各有哪些判断以上关系各有哪些判断以上关系各有哪些判断以上关系各有哪些性质？性质？性质？性质？解解解解：(1)(1)既不是自反又不是反自反，是对称的，不是传递既不是自反又不是反自反，是对称的，不是传递既不是自反又不是反自反，是对称的，不是传递既不是自反又不是反自反，是对称的，不是传递的；的；的；的；(2)(2)是反自反的，反对称的，传递的；是反自反的，反对称的，传递的；是反自反的，反对称的，传递的；是反自反的，反对称的，传递的；(3)(3)既不是自反既不是自反既不是自反既不是自反又不是反自反的，既是对称又是反对称的，传递的；又不是反自反的，既是对称又是

49、反对称的，传递的；又不是反自反的，既是对称又是反对称的，传递的；又不是反自反的，既是对称又是反对称的，传递的；(4)(4)是自反的，既不是对称又不是反对称的，不是传递的。是自反的，既不是对称又不是反对称的，不是传递的。是自反的，既不是对称又不是反对称的，不是传递的。是自反的，既不是对称又不是反对称的，不是传递的。关系的性质2024/1/202024/1/20离散数学离散数学5454 若若若若A A中有三个元素中有三个元素中有三个元素中有三个元素x x,y y,z z，满足满足满足满足xRyxRy且且且且yRzyRz，即即即即(x x y y)/3)/3 Z Z且且且且(y y z z)/3)/

50、3 Z Z，则有则有则有则有(x x z z)/3)/3 Z Z，于是于是于是于是xRzxRz，R R是是是是传递的传递的传递的传递的。例例例例1212：设：设：设：设A A=1,2,10=1,2,10，对于对于对于对于A A上的关系上的关系上的关系上的关系 R R=|(|(x x y y)/3)/3 Z Z ，R R具有哪些性质？具有哪些性质？具有哪些性质？具有哪些性质？关系的性质解解解解：对对对对任意任意任意任意x x A A，有，有，有，有(x x x x)/3=0)/3=0 Z Z，则，则，则，则 R R，R R是是是是自反的自反的自反的自反的。若若若若xRyxRy，即，即，即，即(x