二元关系 精.ppt

《二元关系 精.ppt》由会员分享，可在线阅读，更多相关《二元关系 精.ppt（35页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第1页，本讲稿共35页关系的闭包关系的闭包q闭包的定义闭包的定义q闭包的构造方法闭包的构造方法q闭包的性质闭包的性质q闭包的相互关系闭包的相互关系第2页，本讲稿共35页闭包的定义闭包的定义定义定义 设设R R是非空集合是非空集合A A上的关系，上的关系，R R的的自反自反（对称对称或或传递传递）闭包闭包是是A A上的关系上的关系RR，使得，使得 R R满足以下条件：满足以下条件：（1 1）RR是是自反自反的（的（对称对称的或的或传递传递的）的）（2 2）R R RR（3 3）对）对A A上任何包含上任何包含R R的的自反自反（对称对称或或传递传递）关系）关系RR有有RR R R。一般将一般将R

2、 R的的自反闭包自反闭包记作记作r(R)r(R)，对称闭包对称闭包记作记作s(R)s(R)，传递闭包，传递闭包记作记作t(R)t(R)。第3页，本讲稿共35页闭包的构造方法闭包的构造方法定理定理 设设R R为为A A上的关系，则有上的关系，则有（1 1）r(R)r(R)RRR R0 0（2 2）s(R)s(R)RRR R-1-1（3 3）t(R)t(R)RRR R2 2RR3 3 第4页，本讲稿共35页q设设A=a,b,c,d,R=,A=a,b,c,d,R=,则则R R和和r(R),s(R),t(R)r(R),s(R),t(R)分别是什么？分别是什么？r(R)=RR r(R)=RR0 0=,=

3、,s(R)=RR s(R)=RR-1-1=,=,第5页，本讲稿共35页 t(R)=RR t(R)=RR2 2RR3 3 R=,R=,R R2 2=,=,R R3 3=,=,R R4 4=R=R2 2;R;R5 5=R=R3 3。t(R)=RR t(R)=RR2 2RR3 3 t(R)=,t(R)=,，,第6页，本讲稿共35页通过关系矩阵求闭包的方法通过关系矩阵求闭包的方法设关系设关系R R，r(R)r(R)，s(R)s(R)，t(R)t(R)的关系矩阵分别为的关系矩阵分别为M M，M Mr r，M Ms s和和M Mt t，则，则M Mr r M ME E对角线上的值都改为对角线上的值都改为1

4、 1M Ms s M MMM若若a aijij1 1，则令，则令a ajiji1 1M Mt t M MM M2 2M M3 3沃舍尔算法沃舍尔算法其中其中E E是和是和M M同阶的单位矩阵，同阶的单位矩阵，MM是是M M的转置矩阵。的转置矩阵。注意在上述等式中矩阵的元素相加时使用逻辑加。注意在上述等式中矩阵的元素相加时使用逻辑加。第7页，本讲稿共35页等价关系与划分等价关系与划分(Equivalence&Partition)(Equivalence&Partition)定义定义 设设R R为非空集合上的关系。如果为非空集合上的关系。如果R R满足满足 自反性自反性、对称性对称性和和传递性，传

5、递性，则称则称R R为为A A上的上的等价关系等价关系。设设R R是一个等价关系，若是一个等价关系，若RR，称，称x x等价等价y y，记做，记做x xy y。举例举例 (1)(1)平面上三角形集合中，三角形的全等、相似关系。平面上三角形集合中，三角形的全等、相似关系。(2)(2)正整数集合中的整除关系不是等价关系。正整数集合中的整除关系不是等价关系。第8页，本讲稿共35页例例 设设A A1,2,1,2,8,8，如下定义，如下定义A A上的关系上的关系R R：R Rx|xy|x，yAxy(mod 3)yAxy(mod 3)其中其中xy(mod 3)xy(mod 3)叫做叫做x x与与y y模模

6、3 3同余同余，即，即x x除以除以3 3的余数与的余数与y y除以除以3 3的余数相等。不难验证的余数相等。不难验证R R为为A A上的等价关系，因为上的等价关系，因为 xAxA，有，有xx(mod 3)xx(mod 3)x,yAx,yA，若，若xy(mod 3)xy(mod 3)，则有，则有yx(mod 3)yx(mod 3)x,y,zAx,y,zA，若，若xy(mod 3)xy(mod 3)，yz(mod 3)yz(mod 3)，则有，则有xz(mod 3)xz(mod 3)第9页，本讲稿共35页等价类等价类定义定义 设设R R为非空集合为非空集合A A上的等价关系，上的等价关系，xAx

7、A，令，令xxR R=y|yAxRy=y|yAxRy称称xxR R为为x x关于关于R R的的等价类等价类，简称为，简称为x x的等价类，简记为的等价类，简记为xxqx x的等价类是的等价类是A A中所有与中所有与x x等价的元素构成的集合。等价的元素构成的集合。q上例中的等价类是：上例中的等价类是：111,4,71,4,7=4=477222,5,82,5,8=558833663,6 3,6 第10页，本讲稿共35页整数集合整数集合Z Z上的模上的模n n等价关系等价关系设设x x是任意整数，是任意整数，n n为给定的正整数，则存在唯一的整数为给定的正整数，则存在唯一的整数q q和和r r，使

8、得，使得x xqn+rqn+r其中其中0rn-10rn-1，称，称r r为为x x除以除以n n的余数的余数。例如例如n n3 3，那么，那么8 8除以除以3 3的余数为的余数为1 1，因为，因为-8-8-33+1-33+1对于任意的整数对于任意的整数x x和和y y，定义模，定义模n n的同余关系为的同余关系为x xy y xy(mod n)xy(mod n)不难验证它是整数集合不难验证它是整数集合Z Z上的等价关系。上的等价关系。将将Z Z中的所有整数根据它们除以中的所有整数根据它们除以n n的余数分类如下：的余数分类如下：余数为余数为0 0的数，其形式为的数，其形式为knkn，kZkZ余

9、数为余数为1 1的数，其形式为的数，其形式为kn+1kn+1，kZkZ 余数是余数是n-1n-1的数，其形式为的数，其形式为kn+(n-1)kn+(n-1)，kZkZ以上构成了以上构成了n n个等价类，使用等价类的符号可记为个等价类，使用等价类的符号可记为iikn+i|kZkn+i|kZ，i=0i=0，1 1，n-1n-1第11页，本讲稿共35页等价类的性质等价类的性质定理定理 设设R R是非空集合是非空集合A A上的等价关系，则上的等价关系，则（1 1）xAxA，xx是是A A的非空子集。的非空子集。（2 2）x,yAx,yA，如果，如果xRyxRy，则，则xxyy。（3 3）x,yAx,y

10、A，如果，如果 R R，则，则xx与与yy不交。不交。（4 4）x|xAx|xAA A。证明证明 略略第12页，本讲稿共35页商集商集定义定义 设设R R为非空集合为非空集合A A上的等价关系，以上的等价关系，以R R的所有等价类作为的所有等价类作为元素构成的集合称为元素构成的集合称为A A关于关于R R的的商集商集记做记做A/RA/R，即，即A/R=xA/R=xR R|xA|xA上例中的商集为上例中的商集为A/A/=0,1,2=1,4,7,2,5,8,3,6=0,1,2=1,4,7,2,5,8,3,6整数集合整数集合Z Z上模上模n n同余等价关系的商集是同余等价关系的商集是 Z/Z/=0,

11、1,=0,1,n-1,n-1 Zn=0,1,Zn=0,1,n-1,n-1第13页，本讲稿共35页划分划分定义定义设设A A为非空集合，若为非空集合，若A A的若干子集的若干子集A A1 1,A,A2 2,满足下面的条件：满足下面的条件：（1 1）非空非空:A Ai i;（2 2）两两不交两两不交:A Ai iAAj j(i(ij);j);（3 3）覆盖：）覆盖：AAi i=A=A则称则称A A1 1,A,A2 2,是是A A的一个的一个划分划分。说明说明q设集合设集合是是A A的非空子集的集合，若这些非空子集两两不相的非空子集的集合，若这些非空子集两两不相交，且它们的并等于交，且它们的并等于A

12、 A，则称则称是集合是集合A A的划分的划分。第14页，本讲稿共35页例例 设设A Aa,b,c,da,b,c,d，给定，给定1 1,2 2,3 3,4 4,5 5,6 6,如下：如下：1 1=a,b,c,d=a,b,c,d2 2=a,b,c,d=a,b,c,d3 3=a,a,b,c,d=a,a,b,c,d4 4=a,b,c=a,b,c5 5=,a,b,c,d,a,b,c,d6 6=a,a,b,c,d=a,a,b,c,d判断哪一个是判断哪一个是A A的划分的划分1 1和和2 2是是A A的划分，其它都不是的划分，其它都不是A A的划分。的划分。因为因为3 3中的子集中的子集aa和和a,b,c,

13、da,b,c,d有交，有交，4 4AA，5 5中含有中含有空集，而空集，而6 6根本不是根本不是A A的子集族。的子集族。第15页，本讲稿共35页商集与划分商集与划分q商集就是商集就是A A的一个划分，并且不同的商集将对应于不同的划的一个划分，并且不同的商集将对应于不同的划分。分。q反之，任给反之，任给A A的一个划分的一个划分，如下定义，如下定义A A上的关系上的关系R R：R=|x,yAxR=|x,yAx与与y y在在的同一划分块中的同一划分块中 则不难证明则不难证明R R为为A A上的等价关系，且该等价关系所确定的商上的等价关系，且该等价关系所确定的商集就是集就是。q由此可见，由此可见，

14、A A上的等价关系与上的等价关系与A A的划分是一一对应的的划分是一一对应的。第16页，本讲稿共35页例例 给出给出A A1,2,31,2,3上所有的等价关系上所有的等价关系这些划分与这些划分与A A上的等价关系之间的一一对应是：上的等价关系之间的一一对应是：1 1对应于全域关系对应于全域关系E EA A，5 5的对应于恒等关系的对应于恒等关系I IA A，2 2，3 3和和4 4分别对应于等价关系分别对应于等价关系R R2 2，R R3 3和和R R4 4。其中其中 R R2 2=,I=,IA AR R3 3=,I=,IA AR R4 4=,I=,IA A第17页，本讲稿共35页例题例题 问

15、集合问集合A Aa,b,c,da,b,c,d上有多少个不同的等价关系？上有多少个不同的等价关系？解答解答 只要求出只要求出A A上的全部划分，即为等价关系。上的全部划分，即为等价关系。划分为一个块的情况：划分为一个块的情况：1 1种，即种，即a,b,c,da,b,c,d划分为两个块的情况：划分为两个块的情况：7 7种，即种，即a,b,c,da,b,c,d，a,c,b,da,c,b,d，a,d,b,ca,d,b,ca,b,c,da,b,c,d，b,a,c,db,a,c,d，c,a,b,dc,a,b,d，d,a,b,cd,a,b,c划分为三个块的情况：划分为三个块的情况：6 6种，即种，即a,b,

16、c,da,b,c,d，a,c,b,da,c,b,d，a,d,b,c,a,d,b,c,a,b,c,da,b,c,d，a,c,b,da,c,b,d，a,d,b,ca,d,b,c划分为四个块的情况：划分为四个块的情况：1 1种，即种，即a,b,c,da,b,c,d因此，共有因此，共有1515种不同的等价关系。种不同的等价关系。第18页，本讲稿共35页 偏序关系偏序关系(Partial Order)(Partial Order)定义定义设设R R为非空集合为非空集合A A上的关系。如果上的关系。如果R R满足满足 自反性自反性、反对称性反对称性和和传递性传递性，则称则称R R为为A A上的上的偏序关系

17、偏序关系，记作，记作。设设为偏序关系，如果为偏序关系，如果，则记作，则记作xyxy，读作，读作“x x小小于或等于于或等于y y”。注意注意 这里的这里的“小于或等于小于或等于”不是指数的大小，而是在偏序关系不是指数的大小，而是在偏序关系中的中的顺序顺序。x x“小于或等于小于或等于”y y的含义是：依照这个序，的含义是：依照这个序，x x排在排在y y的前边或者的前边或者x x就是就是y y。根据不同偏序的定义，对序有着不同的。根据不同偏序的定义，对序有着不同的解释。解释。偏序关系举例偏序关系举例集合集合A A上的恒等关系上的恒等关系I IA A小于或等于关系小于或等于关系整除关系整除关系包

18、含关系包含关系 第19页，本讲稿共35页可比可比定义定义 设设R R为非空集合为非空集合A A上的偏序关系，定义上的偏序关系，定义(1)(1)x,yAx,yA，x xy y xyxy xyxy。(2)(2)x,yAx,yA，x x与与y y可比可比 xyyx xyyx。其中其中x xy y读作读作x x“小于小于”y y。这里所说的。这里所说的“小于小于”是指在偏序是指在偏序中中x x排在排在y y的前边。的前边。q在具有偏序关系的集合在具有偏序关系的集合A A中任取两个元素中任取两个元素x x和和y y，可能有下述几，可能有下述几种情况发生：种情况发生：x xy(y(或或y yx)x)，x

19、xy y，x x与与y y不可比。不可比。q例如例如A A11，2 2，33，是是A A上的整除关系，则有上的整除关系，则有1 12 2，1 13 3，1=11=1，2=22=2，3=33=3，2 2和和3 3不可比。不可比。第20页，本讲稿共35页全序关系全序关系定义定义 设设R R为非空集合为非空集合A A上的偏序关系，如果上的偏序关系，如果 x,yAx,yA，x x与与y y都是都是可比的，则称可比的，则称R R为为A A上的上的全序关系全序关系 (或或线序关系线序关系Linear Linear orderorder)。例如例如数集上的小于或等于关系是全序关系，因为任何两个数总是数集上的

20、小于或等于关系是全序关系，因为任何两个数总是可比大小的。可比大小的。整除关系一般来说不是全序关系，如集合整除关系一般来说不是全序关系，如集合1,2,31,2,3上的整除上的整除关系就不是全序关系，因为关系就不是全序关系，因为2 2和和3 3不可比。不可比。第21页，本讲稿共35页偏序集偏序集（PosetPoset）定义定义 集合集合A A和和A A上的偏序关系上的偏序关系一起叫做一起叫做偏序集偏序集，记作，记作。例如例如 整数集合整数集合Z Z和数的小于或等于关系和数的小于或等于关系构成偏序集构成偏序集集合集合A A的幂集的幂集P(A)P(A)和包含关系和包含关系 构成偏序集构成偏序集P(A)

21、,。第22页，本讲稿共35页覆盖覆盖定义定义 设设为偏序集。为偏序集。x,yAA，如果，如果 xy 且不存在且不存在 zAA使得使得xzy，则称，则称y覆盖覆盖x。例如例如 1,2,4,61,2,4,6集合上的整除关系，集合上的整除关系，有有2 2覆盖覆盖1 1，4 4和和6 6都覆盖都覆盖2 2。但。但4 4不覆盖不覆盖1 1，因为有，因为有1 12 24 4。6 6也不覆盖也不覆盖4 4，因为，因为4 46 6不成立。不成立。第23页，本讲稿共35页哈斯图哈斯图(Hasse Diagram)(Hasse Diagram)q利用偏序关系的自反性、反对称性和传递性所得到的偏序利用偏序关系的自反

22、性、反对称性和传递性所得到的偏序集合图，称为集合图，称为哈斯图哈斯图。q画偏序集画偏序集A的哈斯图的方法的哈斯图的方法(1)(1)用小圆圈代表元素。用小圆圈代表元素。(2)(2)x,yAx,yA，若，若x xy y，则将，则将x x画在画在y y的下方。的下方。(3)(3)对于对于A A中的两个不同元素中的两个不同元素x x和和y y，如果，如果y y覆盖覆盖x x，就用一条，就用一条线段连接线段连接x x和和y y。第24页，本讲稿共35页例例 画出偏序集画出偏序集1,2,3,4,5,6,7,8,9 和和P(a,b,c),的哈斯图。的哈斯图。a第25页，本讲稿共35页例例 已知偏序集已知偏序

23、集的哈斯图如右的哈斯图如右图所示，试求出集合图所示，试求出集合A A和关系和关系R R的的表达式。表达式。解答解答A=a,b,c,d,e,f,g,hA=a,b,c,d,e,f,g,hR=R=,IIA A 第26页，本讲稿共35页偏序集中的特殊元素偏序集中的特殊元素定义定义 设设A为偏序集，为偏序集，B B A A，yByB。（1 1）若）若 x(xByx)x(xByx)成立，则称成立，则称y y为为B B的的最小元最小元。（2 2）若）若 x(xBxy)x(xBxy)成立，则称成立，则称y y为为B B的的最大元最大元。（3 3）若）若 x(xBxyxx(xBxyxy)y)成立，则称成立，则称

24、y y为为B B的的极小元极小元。（4 4）若）若 x(xByxxx(xByxxy)y)成立，则称成立，则称y y为为B B的的极大元极大元。363242126B最大元最小元极大元极小元2,3,6,12,24,366,122,3,66无无 无无 24,26 2,312 12 6 6 12 6 6 6 无无 6 2,3 6 6 6 6 6 6第27页，本讲稿共35页特殊元素的性质特殊元素的性质q最小元是最小元是B B中最小的元素，它与中最小的元素，它与B B中其它元素都可比。中其它元素都可比。q极小元不一定与极小元不一定与B B中元素可比，只要没有比它小的元素，它中元素可比，只要没有比它小的元素

25、，它就是极小元。就是极小元。q对于有穷集对于有穷集B B，极小元一定存在，但最小元不一定存在。最，极小元一定存在，但最小元不一定存在。最小元如果存在，一定是唯一的。小元如果存在，一定是唯一的。q极小元可能有多个，但不同的极小元之间是不可比的（无极小元可能有多个，但不同的极小元之间是不可比的（无关系）。关系）。q如果如果B B中只有一个极小元，则它一定是中只有一个极小元，则它一定是B B的最小元。的最小元。q哈斯图中，集合哈斯图中，集合B B的极小元是的极小元是B B中各元素中的最底层。中各元素中的最底层。第28页，本讲稿共35页例例 设偏序集设偏序集如右图所示，如右图所示，求求A A的极小元、

26、最小元、极大元、的极小元、最小元、极大元、最大元。最大元。解答解答极小元：极小元：a,b,c,ga,b,c,g极大元：极大元：a,f,ha,f,h。没有最小元与最大元没有最小元与最大元说明说明哈斯图中的孤立顶点既是极小元也是极大元。哈斯图中的孤立顶点既是极小元也是极大元。第29页，本讲稿共35页上界、下界上界、下界定义定义 设设A为偏序集，为偏序集，B B A A，yAyA。（1 1）若）若 x(xBxy)x(xBxy)成立，则称成立，则称y y为为B B的的上界上界。（2 2）若）若 x(xByx)x(xByx)成立，则称成立，则称y y为为B B的的下界下界。（3 3）令）令C Cy|yy

27、|y为为B B的上界的上界，则称，则称C C的最小元为的最小元为B B的的最小上界最小上界或或上确界上确界。（4 4）令）令D Dy|yy|y为为B B的下界的下界，则称，则称D D的最大元为的最大元为B B的的最大下界最大下界或或下确界下确界。第30页，本讲稿共35页上界与下界举例上界与下界举例363242126B上界下界上确界下确界2,3,6,12,24,366,122,3,66 无无 无无 无无 无无12,24,36 2,3,612,24,36 2,3,6 12 6 12 66,12,24,36 6,12,24,36 无无 6 6 无无6,12,24,366,12,24,36 2,3,6

28、 6 6 2,3,6 6 6q考虑右图中的偏序集。令考虑右图中的偏序集。令B Bbb，c c，dd，则则B B的下界和最大下界都的下界和最大下界都不存在，上界有不存在，上界有d d和和f f，最小上界最小上界为为d d。第31页，本讲稿共35页上界与下界的性质上界与下界的性质qB B的最小元一定是的最小元一定是B B的下界，同时也是的下界，同时也是B B的最大下界。的最大下界。qB B的最大元一定是的最大元一定是B B的上界，同时也是的上界，同时也是B B的最小上界。的最小上界。qB B的下界不一定是的下界不一定是B B的最小元，因为它可能不是的最小元，因为它可能不是B B中的元素。中的元素。

29、qB B的上界也不一定是的上界也不一定是B B的最大元。的最大元。qB B的上界、下界、最小上界、最大下界都可能不存在。如果的上界、下界、最小上界、最大下界都可能不存在。如果存在，最小上界与最大下界是唯一的。存在，最小上界与最大下界是唯一的。第32页，本讲稿共35页作业作业习题：习题：1.4.16 1.4.16 2.P.109:2.P.109:证明例题证明例题4.294.29给出的关系是给出的关系是SSSS上的等价上的等价关系。关系。第33页，本讲稿共35页习题习题q设设R R是复数集合是复数集合C C上的关系，且满足上的关系，且满足xRyxRyx-yx-ya+bia+bi，a a和和b b为

30、给定的非负整数，试确定为给定的非负整数，试确定R R的性质并证明之。的性质并证明之。解答解答（1 1）当）当a ab b0 0时，满足自反性、对称性、反对称性和传递时，满足自反性、对称性、反对称性和传递性，不满足反自反性。性，不满足反自反性。（2 2）当）当a a、b b不全为不全为0 0时，只满足反自反性、反对称性。时，只满足反自反性、反对称性。第34页，本讲稿共35页例例题题 设设I I为为整整数数集集，R R|xy(mod|xy(mod k)k)，证证明明R R是是等等价价关关系。系。证明证明 设任意设任意a,b,cIa,b,cI(1)(1)因为因为a aa a0 0，所以，所以RR。(2)(2)若若ab(mod k)ab(mod k)，a ab bkt(tkt(t为整数为整数)，则，则b ba a-kt-kt，所以，所以ba(mod k)ba(mod k)。(3)(3)若若ab(mod k)ab(mod k)，bc(mod k)bc(mod k)，则，则a ab bktkt，b bc cks(tks(t和和s s为整数为整数)，a ac ca ab bb bc cktktksksk(tk(ts)s)，所以所以ac(mod k)ac(mod k)因此，因此，R R是等价关系。是等价关系。第35页，本讲稿共35页