《《月号离散数学》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《月号离散数学》PPT课件.ppt（45页珍藏版）》请在金锄头文库上搜索。
1、第第4章章 二元关系与函数二元关系与函数4.4 4.4 关系的闭包关系的闭包4.5 4.5 等价关系和偏序关系等价关系和偏序关系14.4 关系的闭包关系的闭包n闭包定义闭包定义n闭包的构造方法闭包的构造方法 集合表示集合表示 矩阵表示矩阵表示 图表示图表示2闭包定义闭包定义定义定义设设R是非空集合是非空集合A上的关系上的关系,R的的自反（对自反（对称称或或传递）闭包传递）闭包是是A上的关系上的关系R ,使得使得R 满足满足以下条件：以下条件：（1）R 是是自反自反的（的（对称对称的或的或传递传递的）的）（2）R R （3）对）对A上任何包含上任何包含R的自反（对称或传递）的自反（对称或传递）关
2、系关系R 有有RR .一般将一般将R 的自反闭包记作的自反闭包记作r(R),对称闭包记作对称闭包记作s(R),传递闭包记作传递闭包记作t(R).3闭包的构造方法闭包的构造方法1.集合并运算集合并运算定理定理1设设R为为A上的关系上的关系,则有则有(1)r(R)=RR0(2)s(R)=RR 1(3)t(R)=RR2R3说明：说明：对于有穷集合对于有穷集合A (|A|=n)上的关系上的关系,(3)中的并最中的并最多多不超过不超过Rn.4性质性质是自反的，是对称的 ，是传递的。5解法一解法一 例例1、设 求。6例例1、设 求。7(参考第二节例3) 例例1、设 求。8(参考第二节例3) 例例1、设 求
3、。9设关系设关系R,r(R),s(R),t(R)的关系矩阵分别为的关系矩阵分别为M,Mr,Ms 和和Mt ,则则Mr =M +E Ms =M +MMt =M +M2+M3+E 是和是和M 同阶的单位矩阵同阶的单位矩阵,M是是M 的转置矩阵的转置矩阵.注意在上述等式中矩阵的元素相加时使用逻辑加注意在上述等式中矩阵的元素相加时使用逻辑加.闭包的构造方法（续）闭包的构造方法（续）2.利用关系矩阵利用关系矩阵10闭包的构造方法（续）闭包的构造方法（续）设关系设关系R,r(R),s(R),t(R)的关系图分别记为的关系图分别记为G,Gr,Gs,Gt ,则则Gr,Gs,Gt 的顶的顶点集与点集与G 的顶点
4、集相等的顶点集相等.除了除了G 的边以外的边以外,以下述方法添加新边：以下述方法添加新边：考察考察G的每个顶点的每个顶点,如果没有环就加上一个环，最如果没有环就加上一个环，最终得到终得到Gr .考察考察G的每条边的每条边,如果有一条如果有一条xi 到到xj 的单向边的单向边,ij,则在则在G中加一条中加一条xj 到到xi 的反方向边，最终得到的反方向边，最终得到Gs.考察考察G的每个顶点的每个顶点xi,找从找从xi 出发的每一条路径，出发的每一条路径，如果从如果从xi 到路径中任何结点到路径中任何结点xj 没有边，就加上这条没有边，就加上这条边边.当检查完所有的顶点后就得到图当检查完所有的顶点
5、后就得到图Gt .11(1)的关系图：在没有环的结点上加上环， (2)的关系图：把单向边改为双向边， (3)以到达的终点添加一条有向边，直到添加完毕。 ，分别找出可的关系图：对每个结点没有有向边，则到，若闭包的构造方法（续）闭包的构造方法（续）3.利用关系图利用关系图12例例1、设 求。解法二解法二先画出的关系图。 的关系图，再画出 13解法二解法二例例1、设 求。14解法二解法二例例1、设 求。15解法二解法二例例1、设 求。16解法三解法三利用关系矩阵(略)。 例例1、设 求。174.5 等价关系与偏序关系等价关系与偏序关系n等价关系的定义与实例等价关系的定义与实例n等价类及其性质等价类及
6、其性质n商集与集合的划分商集与集合的划分n等价关系与划分的一一对应等价关系与划分的一一对应n偏序关系偏序关系n偏序集与哈斯图偏序集与哈斯图n偏序集中的特定元素偏序集中的特定元素18等价关系的定义等价关系的定义定义定义设设R 为非空集合上的关系为非空集合上的关系.如果如果R 是是自反的、对称的和传递的自反的、对称的和传递的,则称则称R 为为A 上的上的等价关系等价关系.设设R 是一个等价关系是一个等价关系,若若R,称称x 等价于等价于y,记做记做xy.19(2) 三角形的全等关系，三角形的相似 关系是等价关系。 (3) 在一个班级里“年龄相等”的关系 是等价关系。 例、例、(1) 集合是等价关系
7、。 上的恒等关系，全域关系 20等价关系的验证等价关系的验证验证模验证模3相等关系相等关系R 为为A上的等价关系上的等价关系,因为因为自反性自反性 xA,有有x x(mod3)对称性对称性 x,yA,若若x y(mod3),则有则有y x(mod3)传递性传递性 x,y,zA,若若x y(mod3),y z(mod3),则有则有xz(mod3)实例实例设设A=1,2,8,如下定义如下定义A上的关系上的关系R：R =|x,yAxy(mod3)其中其中xy(mod3)叫做叫做x 与与y 模模3相等相等,即即x 除以除以3的的余数与余数与y 除以除以3的余数相等的余数相等.21A上模上模3等价关系的
8、关系图等价关系的关系图设设A=1,2,8,R=|x,yAxy(mod3)22例例3、设 ，上的自反关系，且当是是等价关系。 ，证明时，有已知已知只要证只要证是等价关系，是等价关系，是自反的，要证是自反的，要证是对称的和传递的即可。是对称的和传递的即可。若有是对称的。，所以是自反的)， (及，由由于是等价关系。 是自反，对称，传递的，故有若所以的对称性，由， ，所以，又是传递的。 23等价类等价类定义定义设设R为非空集合为非空集合A上的等价关系上的等价关系, xA，令，令xR =y |yAxRy 称称xR 为为x 关于关于R 的的等价类等价类,简称为简称为x 的等价类的等价类,简简记为记为x.实
9、例实例A=1,2,8上模上模3等价关系的等价类：等价关系的等价类：1=4=7=1,4,72=5=8=2,5,83=6=3,624等价类的性质等价类的性质 定理定理1设设R是非空集合是非空集合A上的等价关系上的等价关系,则则(1) xA,x是是A的非空子集的非空子集.(2) x,yA,如果如果x R y,则则x=y.(3) x,yA,如果如果x y,则则x与与y不交不交.(4)x|xA=A，即所有等价类的并集就即所有等价类的并集就是是A. 25实例实例A=1,2,8上模上模3等价关系的等价类：等价关系的等价类：1=4=7=1,4,7，2=5=8=2,5,8，3=6=3,6以上以上3类两两不交，类
10、两两不交，1,4,7 2,5,8 3,6=1,2,826商集商集定义定义设设R为非空集合为非空集合A上的等价关系上的等价关系,以以R的所有的所有等价类作为元素的集合称为等价类作为元素的集合称为A关于关于R的的商集商集,记做记做A/R,A/R =xR |xA 实例实例A=1,2,8,A关于模关于模3等价关系等价关系R的商集为的商集为A/R =1,4,7,2,5,8,3,6 A关于恒等关系和全域关系的商集为：关于恒等关系和全域关系的商集为：A/IA =1,2,8A/EA =1,2,827集合的划分集合的划分定义定义设设A为非空集合为非空集合,若若A的子集族的子集族( P(A)满足下面条件：满足下面
11、条件：(1) (2) x y (x,yxyxy=)(3)=A 则称则称是是A的一个的一个划分划分,称称中的元素为中的元素为A的的划分划分块块.28例题例题例例1设设Aa,b,c,d,给定给定1,2,3,4,5,6如下：如下：1=a,b,c,d，2=a,b,c,d3=a,a,b,c,d,4=a,b,c5=,a,b,c,d,6=a,a,b,c,d则则1和和2是是A的划分的划分,其他都不是其他都不是A 的划分的划分.为什么？为什么？29等价关系与划分的一一对应等价关系与划分的一一对应商集商集A/R 就是就是A 的一个划分的一个划分不同的商集对应于不同的划分不同的商集对应于不同的划分任给任给A 的一个
12、划分的一个划分,如下定义如下定义A 上的关系上的关系R：R =|x,yAx 与与y 在在的同一划分块中的同一划分块中则则R 为为A上的等价关系上的等价关系,且该等价关系确定的商集且该等价关系确定的商集就是就是.例例2给出出A1,2,3上所有的等价关系上所有的等价关系求解思路：先做出求解思路：先做出A的所有的所有划分划分,然后根据划分写然后根据划分写出出对应的等价关系的等价关系.30等价关系与划分之间的对应等价关系与划分之间的对应1,2和和3分别对应等价关系分别对应等价关系R1,R2和和R3.R1=,IA，R2=,IAR3=,IA4对应于对应于全域关系全域关系EA，5对应于对应于恒等关系恒等关系
13、IA31实例实例例例3设设A=1,2,3,4，在，在A A上定义二元关系上定义二元关系R：, R x+y=u+v，求求R 导出的划分导出的划分. 解解A A=,32实例（续）实例（续）根据根据的的x +y =2,3,4,5,6,7,8将将A A划分成划分成7个个等价类：等价类：(A A)/R=, 33偏序关系偏序关系定义定义非空集合非空集合A上的上的自反自反、反对称和、反对称和传递传递的关系，的关系，称为称为A上的上的偏序关系偏序关系，记作，记作 .设设 为偏序关系为偏序关系,如如果果,则记作则记作x y,读作读作x“小于或等于小于或等于”y.实例实例集合集合A上的恒等关系上的恒等关系IA 是
14、是A上的偏序关系上的偏序关系.小于或等于关系小于或等于关系,整除关系和包含关系也是相应整除关系和包含关系也是相应集合上的偏序关系集合上的偏序关系.34相关概念相关概念x与与y 可比可比：设：设R为非空集合为非空集合A上的偏序关系上的偏序关系,x,y A,x与与y可比可比x y y x.结论：任取两个元素结论：任取两个元素x和和y,可能有下述情况：可能有下述情况：x y (或或y x),xy,x与与y不是可比的不是可比的.全序关系全序关系：R为非空集合为非空集合A上的偏序上的偏序, x,y A,x与与y 都是可比的，都是可比的，则称则称R 为为全序全序（或（或线序线序）实例：数集上的小于或等于关
15、系是全序关系实例：数集上的小于或等于关系是全序关系整除关系不是正整数集合上的全序关系整除关系不是正整数集合上的全序关系35覆盖覆盖：设：设R为非空集合为非空集合A上的偏序关系上的偏序关系,x,yA,如如果果x y且不存在且不存在z A 使得使得x z y,则称则称y 覆盖覆盖x.实例：实例：1,2,4,6集合上的整除关系集合上的整除关系,2覆盖覆盖1,4和和6覆盖覆盖2.4不覆盖不覆盖1.相关概念（续）相关概念（续）36偏序集与哈斯图偏序集与哈斯图定义定义集合集合A和和A上的偏序关系上的偏序关系 一起叫做一起叫做偏序集偏序集,记记作作.实例：整数集和小于等于关系构成偏序集实例：整数集和小于等于
16、关系构成偏序集，幂，幂集集P(A)和包含关系构成偏序集和包含关系构成偏序集.哈斯图哈斯图：利用偏序自反、反对称、传递性简化的关：利用偏序自反、反对称、传递性简化的关系图系图特点：每个结点没有环，两个连通的结点之间的序特点：每个结点没有环，两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺关系通过结点位置的高低表示，位置低的元素的顺序在前，具有覆盖关系的两个结点之间连边序在前，具有覆盖关系的两个结点之间连边37哈斯图实例哈斯图实例例例438A=a,b,c,d,e,f,g,hR=,IA哈斯图实例（续）哈斯图实例（续）例例5已知偏序集已知偏序集的哈斯图如右图所示的哈斯图如右图所示,试
17、求出集合试求出集合A和关系和关系R的表达式的表达式.39偏序集的特定元素偏序集的特定元素定义定义设设为偏序集为偏序集,B A,yB.(1)若若 x(xBy x)成立成立,则称则称y 为为B 的的最小元最小元.(2)若若 x(xBx y)成立成立,则称则称y 为为B 的的最大元最大元.(3)若若x (xBx y)成立成立,则称则称y 为为B的的极小元极小元.(4)若若x (xBy x)成立成立,则称则称y 为为B的的极大元极大元.40特殊元素的性质特殊元素的性质n 对于有穷集，极小元和极大元必存在，可能存在对于有穷集，极小元和极大元必存在，可能存在 多个多个. n 最小元和最大元不一定存在，如果
18、存在一定惟一最小元和最大元不一定存在，如果存在一定惟一.n 最小元一定是极小元；最大元一定是极大元最小元一定是极小元；最大元一定是极大元. n 孤立结点既是极小元，也是极大元孤立结点既是极小元，也是极大元. 41定义定义设设为偏序集为偏序集,B A,y A.(1)若若 x(xBx y)成立成立,则称则称y 为为B的的上界上界.(2)若若 x(xBy x)成立成立,则称则称y 为为B的的下界下界.(3)令令Cy |y为为B的上界的上界,则称则称C的最小元为的最小元为B的的最小上界最小上界或或上确界上确界.(4)令令Dy |y为为B的下界的下界,则称则称D的最大元为的最大元为B的的最大下界最大下界
19、或或下确界下确界.偏序集的特定元素偏序集的特定元素(续续)42n下界、上界、下确界、上确界不一定存在下界、上界、下确界、上确界不一定存在n下界、上界存在不一定惟一下界、上界存在不一定惟一n下确界、上确界如果存在，则惟一下确界、上确界如果存在，则惟一n集合的最小元就是它的下确界，最大元就是它的集合的最小元就是它的下确界，最大元就是它的上确界；反之不对上确界；反之不对. 特殊元素的性质特殊元素的性质43实例实例例例6设偏序集设偏序集如如下图所示，下图所示，求求A 的极小元、的极小元、最小元、极大元、最大元最小元、极大元、最大元.设设Bb,c,d,求求B 的的下界、上界、下确界、上确界下界、上界、下确界、上确界.极小元：极小元：a,b,c,g；极大元：极大元：a,f,h；没有最小元与最大元没有最小元与最大元.B的下界和最大下界都的下界和最大下界都不存在不存在,上界有上界有d 和和f,最小上界为最小上界为d.44n作业P114页 4.1445
