第十单元 关系王元元.pptVIP

第十章 关 系 重点:关系的性质﹑运算及二种特殊的关系 重点:关系的性质﹑运算及二种特殊的关系 重点:关系的性质﹑运算及二种特殊的关系 集合笛卡儿积 例10-1 10.1.1 关系的基本概念 例10-2（关系的表示） 例5.3 特殊的二元关系 10.1.1 关系的基本概念 10.1.1 关系的基本概念 例10-3 关系图 例： 例： 用关系图表示A={1,2,3,4,5}上的空关系、相等关系、全关系和小于关系。 关系矩阵 10.1.2 关系的基本运算 10.1.2 关系的基本运算 例 10.1.2 关系的基本运算 10.1.2 关系的基本运算 10.1.2 关系的基本运算 10.1.2 关系的基本运算 10.1.2 关系的基本运算 例5.6 （1）兄弟关系和父子关系的合成是叔侄关系。设《红楼梦》中人物的兄弟关系为R，父子关系为S，那么 R={贾宝玉，贾环,贾政，贾赦，…} S={贾政 ,贾宝玉,贾政,贾环，贾赦，贾琏，…} 求R?S 例 例 性质 定理10-4 合成运算关系图 例10－6 （1）A={a1, a2 , a3 , a4 , a5} B={b1, b2 , b3 , b4 , b5} C={c1, c2 , c3 , c4} R={a2, b1 , a2, b2 , a3, b3 , a4, b3 , a5, b4 } S={b3, c2 , b4, c1 , b4, c4 } 幂运算 定理10-5 10.1.3 关系的基本特性 例10-7 ： 10.1.3 关系的基本特性 例10-7 ： 例10-7 ： 关系的基本特性与关系图、关系矩阵的联系 10.1.3 关系的基本特性 例10-7 ： 10.1.3 关系的基本特性 例10-7 ： 关系的基本特性与关系图、关系矩阵的联系 10.1.3 关系的基本特性 例10-7 ： 关系的基本特性与关系图、关系矩阵的联系 定理10-8 例10-7 ： 例10-7 ： 一个计算机网络在波士顿、芝加哥、丹佛、底特律、纽约和圣地亚哥设有数据中心。从波士顿和芝加哥，波士顿和底特律，芝加哥到底特律，底特律到丹佛，纽约到圣地亚哥，都有单向的数据线。 如果存在一条从数据中心a到b的电话线， a,b∈R. 问R是否具有传递性，如果没有，怎样添加最少的数据线使R具有传递性. 10.1.4 关系特性闭包 10.1.4 关系特性闭包 10.1.4 关系特性闭包 A={1,2,3} R={1,1,1,2,2,1,3,2} 怎样添加最少的元素使R具有自反性？ 构造关系R闭包的方法 例10-8 例1 整数集上的关系 R={a,b|ab} 的自反闭包是什么？ A={1,2,3} R={1,1,1,2,2,2,2,3， 3,1,3,2} 怎样添加最少的元素使R具有对称性？ 构造关系R闭包的方法 例10-8 例2 整数集上的关系 R={a,b|ab} 的对称闭包是什么？ A={1,2,3} R={1,3,1,4,2,1,3,2} 怎样添加最少的元素使R具有传递性？ 构造关系R闭包的方法 10.1.4 关系特性闭包 例10-8 10.1.4 关系特性闭包 10.1.4 关系特性闭包 10.1.4 关系特性闭包 10.2 等价关系 例 （1）三角形相似关系。 （2）同寝室关系。 （3）命题公式间的逻辑等价关系。 （4）集合间的包含关系。 例10-9： 等价类 10.2 等价关系 例10-10 等价类性质 等价类性质 等价类性质 划分 例10-11 设A是你们学校恰好主修一个专业的学生的集合，R={x,y|x和y主修同一个专业} 等价关系与划分 等价关系与划分 等价关系与划分 等价关系与划分 等价关系与划分 10.3 序关系 例10-17： 一般有序集表示 序关系的关系图简化 序关系的关系图简化 例 画出下列序关系的关系图 例:有序集{a, b, c, d, e, f, g, h}, ≤ 设A, ≤为有序集，B ? A。 B最大元不一定存在； B的最大元如果存在，则唯一。 例:有序集{a, b, c, d, e, f, g, h}, ≤ 例： 例： 链和反链 3．设A={1,2,3,4,5}，A上偏序关系 R={〈1，2〉，〈1，3〉，〈1，5〉，〈2，3〉，〈2，5〉，〈3，5〉，〈4，3〉，〈4，5〉}∪EA; (1)作出偏序关系R的哈斯图 (2)令B={2,3,4,5}，求B的最大元，最小元，极小元，下界，上确界。 3）由于序关系传递，我们还可将由传递关系可推定的边也省去，即若a≤b, b≤c, 则肯定应有a≤c，但省略a到c的有向边。