二元关系(II)PPT课件.ppt

《二元关系(II)PPT课件.ppt》由会员分享，可在线阅读，更多相关《二元关系(II)PPT课件.ppt（45页珍藏版）》请在三一文库上搜索。

1、,二元关系,2,关系的闭包,闭包的定义 闭包的构造方法 闭包的性质 闭包的相互关系,3,闭包的定义,定义 设R是非空集合A上的关系，R的自反（对称或传递）闭包是A上的关系R，使得 R满足以下条件： （1）R是自反的（对称的或传递的） （2）RR （3）对A上任何包含R的自反（对称或传递）关系R有R R。 一般将R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R)。,4,设A=a,b,c,d, R=, ,则R和r(R),s(R),t(R)分别是什么？,5,闭包的构造方法,定理 设R为A上的关系，则有 （1）r(R)RR0 （2）s(R)RR-1 （3）t(R)RR2R3 证明思路

2、 (1)和(2)：证明右边的集合满足闭包定义的三个条件。 (3)采用集合相等的证明方法。 证明左边包含右边，即t(R)包含每个Rn。 证明右边包含左边，即RR2具有传递的性质。,6,推论,推论 设R为有穷集A上的关系，则存在正整数r使得 t(R)=RR2Rr 证明 由定理7.6和7.10(3)得证。 例题 求整数集合Z上的关系R | a|a|ab |ab s(R)RR-1|a|a|ab,7,通过关系矩阵求闭包的方法,设关系R，r(R)，s(R)，t(R)的关系矩阵分别为M，Mr，Ms和Mt，则 Mr ME对角线上的值都改为1 Ms MM若aij1，则令aji1 Mt MM2M3沃舍尔算法 其中

3、E是和M同阶的单位矩阵，M是M的转置矩阵。 注意在上述等式中矩阵的元素相加时使用逻辑加。,8,通过关系图求闭包的方法,设关系R，r(R)，s(R)，t(R)的关系图分别记为G，Gr，Gs，Gt，则Gr，Gs，Gt的顶点集与G的顶点集相等。 除了G的边以外，以下述方法添加新的边。 1)考察G的每个顶点，如果没有环就加上一个环。最终得到的是Gr。 2)考察G的每一条边，如果有一条xi到xj的单向边，ij，则在G中加一条边xj到xi的反方向边。最终得到Gs。 3)考察G的每个顶点xi，找出从xi出发的所有2步，3步，n步长的路径（n为G中的顶点数）。 设路径的终点为 。如果没有从xi到 (l=1,2

4、,k)的边，就加上这条边。当检查完所有的顶点后就得到图Gt。,9,例设A=a,b,c,d，R=,，则R和r(R)，s(R)，t(R)的关系图如下图所示。其中r(R)，s(R)，t(R)的关系图就是使用上述方法直接从R的关系图得到的。,10,闭包的主要性质,定理 设R是非空集合A上的关系，则 （1）R是自反的当且仅当r(R)R。 （2）R是对称的当且仅当s(R)R。 （3）R是传递的当且仅当t(R)R。 证明 （1）充分性。 因为Rr(R)，所以R是自反的。 必要性。 显然有R r(R)。 由于R是包含R的自反关系，根据自反闭包定义有r(R)R。 从而得到r(R)=R。,11,闭包的主要性质,定

5、理 设R1和R2是非空集合A上的关系，且R1 R2，则 （1）r(R1) r(R2) （2）s(R1) s(R2) （3）t(R1) t(R2) 证明：(1)任取，有 r(R1) R1IA R1 IA R2 IA R2IA r(R2),12,关系性质与闭包运算之间的联系,定理 设R是非空集合A上的关系， （1）若R是自反的，则s(R)与t(R)也是自反的。 （2）若R是对称的，则r(R)与t(R)也是对称的。 （3）若R是传递的，则r(R)是传递的。 证明：只证（2）。,13,（2）若R是对称的，则r(R)与t(R)也是对称的。 证明r(R)是对称的。 由于R是A上的对称关系，所以RR-1，同

6、时IAIA-1。 r(R)-1(RR0)-1 (RIA)-1 R-1IA-1 RIA r(R) 所以，r(R)是对称的。,14,（2）若R是对称的，则r(R)与t(R)也是对称的。 下面证明t(R)的对称性。 任取 t(R) n(Rn) n(Rn) （因为Rn是对称的） t(R) 所以，t(R)是对称的。,15,从这里可以看出，如果计算关系R的自反、对称、传递的闭包，为了不失去传递性，传递闭包运算应该放在对称闭包运算的后边，若令tsr(R)表示R的自反、对称、传递闭包，则 tsr(R)=t(s(r(R),反例 A=1，2，3，R= 是传递的 s(R)=, 显然s(R)不是传递的。,16,等价关

7、系与划分,定义 设R为非空集合上的关系。如果R是自反的、对称的和传递的，则称R为A上的等价关系。设R是一个等价关系，若R，称x等价于y，记做xy。 举例 (1)平面上三角形集合中，三角形的相似关系。 (2)人群中的同性关系。,17,例 设A1,2,8，如下定义A上的关系R：R|x，yAxy(mod 3)其中xy(mod 3)叫做x与y模3相等，即x除以3的余数与y除以3的余数相等。不难验证R为A上的等价关系，因为 xA，有xx(mod 3) x,yA，若xy(mod 3)，则有yx(mod 3) x,y,zA，若xy(mod 3)，yz(mod 3)，则有xz(mod 3),18,等价类,定义

8、 设R为非空集合A上的等价关系，xA，令xR=y|yAxRy称xR为x关于R的等价类，简称为x的等价类，简记为x或 x 。,x的等价类是A中所有与x等价的元素构成的集合。 上例中的等价类是： 1471,4,7 2582,5,8 363,6,19,整数集合Z上的模n等价关系,设x是任意整数，n为给定的正整数，则存在唯一的整数q和r，使得xqn+r其中0rn-1，称r为x除以n的余数。 例如n3，那么8除以3的余数为1，因为 -8-33+1 对于任意的整数x和y，定义模n相等关系xy xy(mod n) 不难验证它是整数集合Z上的等价关系。 将Z中的所有整数根据它们除以n的余数分类如下： 余数为0

9、的数，其形式为nz，zZ余数为1的数，其形式为nz+1，zZ 余数是n-1的数，其形式为nz+n-1，zZ 以上构成了n个等价类，使用等价类的符号可记为inz+i|zZ，i=0，1，n-1,20,等价类的性质,定理 设R是非空集合A上的等价关系，则 （1）xA，x是A的非空子集。 （2）x,yA，如果xRy，则xy。 （3）x,yA，如果R，则x与y不交。 （4）x|xAA。 证明 略,21,商集,定义 设R为非空集合A上的等价关系，以R的所有等价类作为元素的集合称为A关于R的商集记做A/R，即 A/R=xR|xA 上例中的商集为 1,4,7,2,5,8,3,6 整数集合Z上模n等价关系的商集

10、是 nz+i|zZ|i=0,1,n-1,22,划分,定义设A为非空集合，若A的子集族(P(A)，是A的子集构成的集合) 满足下面的条件： （1） （2）xy(x,yxyxy) （3）=A 则称是A的一个划分，称中的元素为A的划分块。,说明,设集合是A的非空子集的集合，若这些非空子集两两不相交，且它们的并等于A，则称是集合A的划分。,23,例 设Aa,b,c,d，给定1,2,3,4,5,6,如下：1=a,b,c,d2=a,b,c,d3=a,a,b,c,d4=a,b,c5=,a,b,c,d6=a,a,b,c,d判断哪一个是A的划分 1和2是A的划分，其它都不是A的划分。 因为3中的子集a和a,b,

11、c,d有交，4A，5中含有空集，而6根本不是A的子集族。,24,商集与划分,商集就是A的一个划分，并且不同的商集将对应于不同的划分。 反之，任给A的一个划分，如下定义A上的关系R： R=|x,yAx与y在的同一划分块中 则不难证明R为A上的等价关系，且该等价关系所确定的商集就是。 由此可见，A上的等价关系与A的划分是一一对应的。,25,例 给出A1,2,3上所有的等价关系,这些划分与A上的等价关系之间的一一对应是：1对应于全域关系EA，5的对应于恒等关系IA，2，3和4分别对应于等价关系R2，R3和R4。 其中 R2=,IAR3=,IAR4=,IA,26,例题 问集合Aa,b,c,d上有多少个

12、不同的等价关系？ 解答 只要求出A上的全部划分，即为等价关系。 划分为一个块的情况：1种，即a,b,c,d 划分为两个块的情况：7种，即 a,b,c,d，a,c,b,d，a,d,b,c a,b,c,d，b,a,c,d，c,a,b,d，d,a,b,c 划分为三个块的情况：6种，即 a,b,c,d，a,c,b,d，a,d,b,c, a,b,c,d，a,c,b,d，a,d,b,c 划分为四个块的情况：1种，即a,b,c,d 因此，共有15种不同的等价关系。,27,偏序关系,定义设R为非空集合A上的关系。如果R是自反的、反对称的和传递的，则称R为A上的偏序关系，记作。 设为偏序关系，如果，则记作xy，

13、读作“x小于或等于y”。 注意 这里的“小于或等于”不是指数的大小，而是在偏序关系中的顺序性。x“小于或等于”y的含义是：依照这个序，x排在y的前边或者x就是y。根据不同偏序的定义，对序有着不同的解释。 偏序关系举例 集合A上的恒等关系IA小于或等于关系 整除关系包含关系,28,可比,定义 设R为非空集合A上的偏序关系，定义 (1) x,yA，xy xyxy。 (2) x,yA，x与y可比 xyyx。 其中xy读作x“小于”y。这里所说的“小于”是指在偏序中x排在y的前边。 在具有偏序关系的集合A中任取两个元素x和y，可能有下述几种情况发生： xy(或yx)，xy，x与y不是可比的。 例如A1

14、，2，3，是A上的整除关系，则有 12，13， 1=1，2=2，3=3， 2和3不可比。,29,全序关系,定义 设R为非空集合A上的偏序关系，如果x,yA，x与y都是可比的，则称R为A上的全序关系(或线序关系)。 例如 数集上的小于或等于关系是全序关系，因为任何两个数总是可比大小的。 整除关系一般来说不是全序关系，如集合1,2,3上的整除关系就不是全序关系，因为2和3不可比。,30,偏序集,定义 集合A和A上的偏序关系一起叫做偏序集，记作。 例如 整数集合Z和数的小于或等于关系构成偏序集 集合A的幂集P(A)和包含关系R构成偏序集。,31,覆盖,定义 设为偏序集。 x,yA，如果 xy 且不存

15、在 zA使得xzy，则称y覆盖x。 例如 1,2,4,6集合上的整除关系， 有2覆盖1，4和6都覆盖2。但4不覆盖1，因为有124。6也不覆盖4，因为46不成立。,32,哈斯图,利用偏序关系的自反性、反对称性和传递性所得到的偏序集合图，称为哈斯图。 画偏序集的哈斯图的方法 (1)用小圆圈代表元素。 (2)x,yA，若xy，则将x画在y的下方。 (3)对于A中的两个不同元素x和y，如果y覆盖x，就用一条线段连接x和y。,33,例 画出偏序集和的哈斯图。,a,34,例 已知偏序集的哈斯图如右图所示，试求出集合A和关系R的表达式。,解答 A=a,b,c,d,e,f,g,h R=,IA,35,偏序集中

16、的特殊元素,定义 设为偏序集，BA，yB。 （1）若x(xByx)成立，则称y为B的最小元。 （2）若x(xBxy)成立，则称y为B的最大元。 （3）若x(xBxyxy)成立，则称y为B的极小元。 （4）若x(xByxxy)成立，则称y为B的极大元。,无 无 24,26 2,3,12 6 12 6,6 无 6 2,3,6 6 6 6,36,特殊元素的性质,最小元是B中最小的元素，它与B中其它元素都可比。 极小元不一定与B中元素可比，只要没有比它小的元素，它就是极小元。 对于有穷集B，极小元一定存在，但最小元不一定存在。最小元如果存在，一定是唯一的。 极小元可能有多个，但不同的极小元之间是不可比

17、的（无关系）。 如果B中只有一个极小元，则它一定是B的最小元。 哈斯图中，集合B的极小元是B中各元素中的最底层。,37,例 设偏序集如右图所示，求A的极小元、最小元、极大元、最大元。,解答 极小元：a,b,c,g 极大元：a,f,h。 没有最小元与最大元,说明,哈斯图中的孤立顶点既是极小元也是极大元。,38,例 设X为集合，AP(X)X，且A。若|X|n，问：（1）偏序集是否存在最大元？（2）偏序集是否存在最小元？（3）偏序集中极大元和极小元的一般形式是什么？并说明理由。 解答 不存在最小元和最大元，因为n2。 考察幂集P(X)的哈斯图，最底层的顶点是空集，记作第0层。由底向上，第1层是单元集

18、，第2层是二元子集，由|X|=n，则第n1层是X的n1元子集，第n层，也就是最高层只有一个顶点X。偏序集与相比，恰好缺少第0层与第n层(因为X是n元集)。因此的极小元就是X的所有单元集，即x，xX；而极大元恰好少一个元素，即X-x，xX。,39,上界、下界,定义 设为偏序集，BA，yA。 （1）若 x(xBxy)成立，则称y为B的上界。 （2）若 x(xByx)成立，则称y为B的下界。 （3）令Cy|y为B的上界，则称C的最小元为B的最小上界或上确界。 （4）令Dy|y为B的下界，则称D的最大元为B的最大下界或下确界。,40,上界与下界举例,无 无 无 无,12,24,36 2,3,6 12

19、6,6,12,24,36 无 6 无,6,12,24,36 2,3,6 6 6,考虑右图中的偏序集。令Bb，c，d，则B的下界和最大下界都不存在，上界有d和f，最小上界为d。,41,上界与下界的性质,B的最小元一定是B的下界，同时也是B的最大下界。 B的最大元一定是B的上界，同时也是B的最小上界。 B的下界不一定是B的最小元，因为它可能不是B中的元素。 B的上界也不一定是B的最大元。 B的上界、下界、最小上界、最大下界都可能不存在。如果存在，最小上界与最大下界是唯一的。,42,作业,习题： 1.4.16 2.P.109: 证明例题4.29给出的关系是SS上的等价关系。,43,习题,设R是复数集

20、合C上的关系，且满足xRyx-ya+bi，a和b为给定的非负整数，试确定R的性质并证明之。 解答 （1）当ab0时，满足自反性、对称性、反对称性和传递性，不满足反自反性。 （2）当a、b不全为0时，只满足反自反性、反对称性。,44,例题 设I为整数集，R|xy(mod k)，证明R是等价关系。 证明 设任意a,b,cI (1)因为aa0，所以R。 (2)若ab(mod k)，abkt(t为整数)，则 ba-kt，所以ba(mod k)。 (3)若ab(mod k)，bc(mod k)，则 abkt，bcks(t和s为整数)， acabbcktksk(ts)， 所以ac(mod k) 因此，R是等价关系。,个人观点供参考，欢迎讨论,