离散数学及其应用第5章-关系模型与理论(下)课件.ppt

1、2022-7-23计算机应用技术研究所计算机应用技术研究所11离散数学离散数学Discrete Mathematics汪荣贵汪荣贵 教授教授合肥工业大学计算机与信息学院合肥工业大学计算机与信息学院2022-7-23计算机应用技术研究所计算机应用技术研究所2第第5 5章章 关系模型与理论关系模型与理论(下下)2022-7-232022-7-23 关系的基本性质关系的基本性质3 3 关系模型的应用关系模型的应用5 5 关系的性质闭包关系的性质闭包4 4&本章学习内容本章学习内容2022-7-23计算机应用技术研究所计算机应用技术研究所4关系的基本性质关系的基本性质&关系的基本性质关系的基本性质J

2、关系的自反与反自反关系的自反与反自反4 关系的对称与反对称关系的对称与反对称4 关系的传递性关系的传递性4 关系性质的判定关系性质的判定2022-7-232022-7-23&自反与反自反自反与反自反2022-7-232022-7-23&例题例题2022-7-232022-7-23&例题例题2022-7-232022-7-23&例题例题2022-7-232022-7-23&例题例题2022-7-232022-7-23&例题例题2022-7-232022-7-23&小小 结结&关系的基本性质关系的基本性质4 关系的自反与反自反关系的自反与反自反J 关系的对称与反对称关系的对称与反对称4 关系的传递

3、性关系的传递性4 关系性质的判定关系性质的判定2022-7-232022-7-23&对称与反对称对称与反对称2022-7-232022-7-23&例例 题题2022-7-232022-7-23&例例 题题2022-7-232022-7-23&例例 题题2022-7-232022-7-23&例题例题【例题】试判断下列关系是否具有对称性和反对称性.（1）对任意集合A，其幂集Q（A）上的包含关系；（2）整数集Z上的整除关系.【分析】（1）当两个集合不相等时，如果有其中一个集合包含于另一个，则反过来必然没有包含关系，故有反对称性但没有对称性；（2）当整数a和整数b不等时，若a整除b，则必有b不能整除a

4、，故有反对称性但没有对称性.【解】对任意集合A，其幂集P(A)上的包含关系具有反对称性；整数集Z上的整除关系具有反对称性.2022-7-232022-7-23&小小 结结&关系的基本性质关系的基本性质4 关系的自反与反自反关系的自反与反自反4 关系的对称与反对称关系的对称与反对称J 关系的传递性关系的传递性4 关系性质的判定关系性质的判定2022-7-232022-7-23&传递性的定义传递性的定义2022-7-232022-7-23&例例 题题2022-7-232022-7-23&例例 题题2022-7-232022-7-23&例例 题题2022-7-232022-7-23&小小 结结&关系

5、的基本性质关系的基本性质4 关系的自反与反自反关系的自反与反自反4 关系的对称与反对称关系的对称与反对称4 关系的传递性关系的传递性J 关系性质的判定关系性质的判定2022-7-232022-7-23&关系性质的判断关系性质的判断2022-7-232022-7-23&关系性质的判断关系性质的判断2022-7-232022-7-23&关系性质的判断关系性质的判断2022-7-232022-7-23&关系性质的判定关系性质的判定2022-7-232022-7-23&关系性质的判定关系性质的判定2022-7-232022-7-23&关系性质的判定关系性质的判定2022-7-232022-7-23&例

6、例 题题【例题】试举例说明下列事实：R和S是反自反、反对称和传递的，但是R S不一定具有反自反性和反对称性；RS不一定具有反对称性和传递性；【解】设A=1,2,3，R和S是定义在A上的两个关系：R=1,2,2,3,1,3；S=3,2,3,1,2,1 显然R，S都是反自反的、反对称和传递的.但R S=1,1,2,2,2,1,1,2 不具有反自反性和反对称性；RS=1,2,2,3,1,3,3,2,3,1,2,1 不具有反对称性和传递性.2022-7-232022-7-23&例例 题题【例题】试举例说明下列事实：R和S是自反、对称和传递的，但是R S不一定具有对称性和传递性；R-S不一定具有自反性和

7、传递性.【解】设A=1,2,3，R和S是定义在A上的两个关系：R=1,1,2,2,3,3,1,2,2,1；S=1,1,2,2,3,2,2,3 显然R，S都是自反、对称和传递的.但是：R S=1,1,2,2,3,3,2,3,3,2 1,2,2,1,1,3 不具有对称性和传递性；R-S=1,2,2,1 不具有自反性和传递性.2022-7-232022-7-23&例例 题题【例题】试判断下图关系的性质【解】图a的关系在集合1,2,3上是对称的，因为结点1与2，1与3之间的有向边是成对出现且方向相反；因为有的点有自环，有的点没有自环，故不是自反的，也不是反自反的；因为 2,1 R，1,3 R，若是传递

8、关系，必有 2,3 R.然而结点2没有一条指向结点3的有向边，故不是传递的；因为 2,1 R且 1,2 R，但 12，故不是反对称的.2022-7-232022-7-23&例例 题题【解】图b的关系是反自反的，因为每个顶点都没有自环；是反对称的，因为两条边都是单向边；是传递的，因为不存在顶a,b,c1,2,3，使得a到b有边，b到c有边，但a到c没有边.同理可知，图c的关系是自反的、反对称的，但不是传递的.2022-7-232022-7-23&例例 题题【例题】设A=1,2,3,4,6,12，A上的整除关系记为R，则R是自反的、对称的、反自反的、反对称的、传递的吗？画出A中关系R的关系.【解】

9、关系R是A中的关系，所以它的关系图如下图所示.从图中容易看出，R是自反、反对称和传递的，不是反自反的，也不是对称的.容易验证，一般正整数集合中整除关系都具有自反性、反对称性、传递性，而不具有反自反性和对称性.2022-7-232022-7-23&例例 题题2022-7-232022-7-23&例例 题题2022-7-232022-7-23本节内容到此结束2022-7-232022-7-23 关系的基本性质关系的基本性质3 3 关系模型的应用关系模型的应用5 5 关系的性质闭包关系的性质闭包4 4&本章学习内容本章学习内容2022-7-23计算机应用技术研究所计算机应用技术研究所42关系的性质闭

10、包关系的性质闭包&关系的闭包运算关系的闭包运算J 关系闭包的概念关系闭包的概念4 传递闭包的构造传递闭包的构造4 关系闭包的性质关系闭包的性质2022-7-232022-7-23&关系闭包的概念关系闭包的概念2022-7-232022-7-23&构造方法构造方法2022-7-232022-7-23&例例 题题2022-7-232022-7-23&例例 题题2022-7-232022-7-23&构造方法构造方法2022-7-232022-7-23&例例 题题2022-7-232022-7-23&例例 题题2022-7-232022-7-23&例例 题题【例题】设集合A=1,2,3,4，R是A上的

11、关系，且有：R=1,2,2,2,3,4.试画出R的关系图，并根据关系图求出r(R)，s(R)和t(R).【解】R的关系图如左图所示.从关系图上看，如果每个结点都有自环，那么该关系就具有自反性.故可在R的关系图的结点1，3和4处添加自环，即得到r(R)的关系图，如右图所示，故有：r(R)=1,2,2,2,2,3,3,4,1,1,3,3,4,4.2022-7-232022-7-23&例例 题题【解】如果关系图的任何一对结点之间要么有方向相反的两条边，要么没有边，那么该关系的关系就具有对称性.故可在R的关系图中添加2到1、3到2和4到3的有向边，即得到s(R)的关系图，如下图所示，故有：s(R)=1

12、,2,2,2,2,3,3,4,2,1,3,2,4,3；2022-7-232022-7-23&例例 题题2022-7-232022-7-23&总总 结结&关系的闭包运算关系的闭包运算4 关系闭包的概念关系闭包的概念J 传递闭包的构造传递闭包的构造4 关系闭包的性质关系闭包的性质2022-7-232022-7-23&传递闭包的构造传递闭包的构造2022-7-232022-7-23&传递闭包的构造传递闭包的构造2022-7-232022-7-23&例题例题2022-7-232022-7-23&例题例题2022-7-232022-7-23&沃舍尔算法沃舍尔算法2022-7-232022-7-23&沃舍

13、尔算法沃舍尔算法2022-7-232022-7-23&沃舍尔算法沃舍尔算法2022-7-232022-7-23&沃舍尔算法沃舍尔算法2022-7-232022-7-23&例题例题2022-7-232022-7-23&例题例题&关系的闭包运算关系的闭包运算4 关系闭包的概念关系闭包的概念4 传递闭包的构造传递闭包的构造J 关系闭包的性质关系闭包的性质2022-7-232022-7-23&闭包的性质闭包的性质【定理】若R是A上关系，则（1）R是自反的，当且仅当r(R)=R；（2）R是对称的，当且仅当s(R)=R；（3）R是传递的，当且仅当t(R)=R.【证明】（1）必要性：显然有Rr(R)，又因R

14、是包含了R的自反关系，根据自反闭包定义有r（R）R，从而得到r(R)=R.充分性显然成立.（2）（3）的证明同（1）.2022-7-232022-7-23&闭包的性质闭包的性质【定理】若R是A上关系，则（1）R是自反的，则s(R)和t(R)也是自反的；（2）R是对称的，则r(R)和t(R)也是对称的；（3）R是传递的，则r(R)也是传递的.2022-7-232022-7-23&闭包的性质闭包的性质2022-7-232022-7-23&闭包的性质闭包的性质2022-7-232022-7-23&闭包与集合运算闭包与集合运算2022-7-232022-7-23&闭包与集合运算闭包与集合运算2022-

15、7-232022-7-23&多重闭包的性质多重闭包的性质2022-7-232022-7-23&多重闭包的性质多重闭包的性质2022-7-232022-7-23本章内容到此结束2022-7-232022-7-23 关系的基本性质关系的基本性质3 3 关系模型的应用关系模型的应用5 5 关系的性质闭包关系的性质闭包4 4&本章学习内容本章学习内容&关系模型的应用关系模型的应用J关系代数模型关系代数模型4关系演算模型关系演算模型2022-7-232022-7-23&关系代数模型关系代数模型 关系数据模型是一种以二维表的方式表示数据的多元关系结构以及相关的关系操作。二维表又称表，它由表框架及表元组两部

16、分组成。表框架由表名及若干个命名属性列构成。表中每行数据称为元组。元组由若干个分量组成，其每个分量对应表框架中的一个属性值，一个表框架可以储存若干个元组，它们构成了一个完整的二维表。2022-7-232022-7-23&关系代数模型关系代数模型 关系数据模型中的基本操作共有六种，三种定位操作与三种执行操作，即：表的列指定、表的行选择、两表的合并、选择操作、删除操作、插入操作。二维表上的六种基本操作可对应关系的五种运算，因为选择操作不涉及逻辑运算，可在关系代数中忽略。其中一些操作可以关系的集合运算与复合运算实现。&关系模型的应用关系模型的应用4 关系代数模型关系代数模型J 关系演算模型关系演算模

17、型2022-7-232022-7-23&关系演算模型关系演算模型 对于任意给定的一个二维表，可用一个多元谓词对其进行表示。其中谓词中个体变元即是表的属性，而表中的元组就是使该谓词为真的赋值，不在表中元组则是使该谓词为假的赋值。例如，对于下表的学生基本信息表，其中表中属性sno、sn、sd、sa分别表示学生对象的学号、姓名、系别和年龄信息。可用谓词S（sno，sn，sd，sa）对该表进行表示，表中元组（07001，张曼英，CS，19）、（07002，丁一明，CS，20）、（07003，王爱国，CS，18）、（07004，李强，CS，18）是该谓词公式全部成真赋值，即不在表中的元组均为该谓词成假赋值 2022-7-232022-7-23&关系演算模型关系演算模型2022-7-232022-7-23&例题例题2022-7-232022-7-23本章内容到此结束