(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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 1.5 离散数学
限制150内