集合论与关系精选文档.ppt

《集合论与关系精选文档.ppt》由会员分享，可在线阅读，更多相关《集合论与关系精选文档.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、集合论与关系本讲稿第一页，共六十一页3.1、集合的基本概念集合的基本概念 不产生歧义的对象的汇集一块便构成集合不产生歧义的对象的汇集一块便构成集合.集合常用集合常用枚举法枚举法:湖大教学楼湖大教学楼=复临复临,中楼中楼,东楼东楼,北楼北楼,前进楼前进楼 描述法描述法:偶数集偶数集=除以除以2余为余为0的所有整数的所有整数 子集子集A B:A中的每个元素都是中的每个元素都是B的元素的元素 幂集幂集P(A)=A的所有子集的集合的所有子集的集合=2A.如如A=1,2,3 A000=,A001=3,A010=2,A011=2,3,A100=1,A101=1,3,A110=1,2,A111=1,2,3

2、其有其有23个个,即即2|A|个个本讲稿第二页，共六十一页3.2、集合的运算与性质集合的运算与性质1、A B=由同时属于由同时属于A与与B的元素组成的元素组成2、A B=由属于由属于A或属于或属于B的元素组成的元素组成3、A-B=由属于由属于A但不属于但不属于B的元素组成的元素组成4、A=全集全集U中不属于中不属于A的元素组成的元素组成=U-AA BA BA-B AA B本讲稿第三页，共六十一页3.2、集合的运算与性质集合的运算与性质定定义义3.1.1 如如果果集集合合A中中任任何何元元素素都都是是B的的元元素素，则则称称A是是B的的子集，记为子集，记为A B，也称，也称B包含包含A，记为，记

3、为B A。定定义义3.2.3 设设A、B是是两两个个集集合合，若若A B、B A则则A=B，即即两两个集合相等。个集合相等。以下性质可根据相等定义得到，与命题逻辑性质一样以下性质可根据相等定义得到，与命题逻辑性质一样以下性质可根据相等定义得到，与命题逻辑性质一样以下性质可根据相等定义得到，与命题逻辑性质一样幂等律幂等律A A=A，A A=A结合律结合律A B C=A(B C)=(A B)C A B C=A (B C)=(A B)C交换律交换律A B=B A A B=B A分配律分配律A(B C)=(A B)(A C)A(B C)=(A B)(A C)同一同一/零律零律 A=A A =排中排中/

4、矛盾律矛盾律AA=E A A=吸收律吸收律(大吃小大吃小)A(B A)=A,A(B A)=A德摩律德摩律 (A B)=AB (A B)=A B双重否定双重否定 A=A本讲稿第四页，共六十一页3.3、有穷集的计数有穷集的计数1、|A|=集合集合A的元素数的元素数2、例题：、例题：24人中人中(书上缺少此条件书上缺少此条件)，会英，会英=13、日、日=5、德、德=10、法、法=9，同时会英日有，同时会英日有2人，会德、法、英中任意二种有人，会德、法、英中任意二种有4人，会日语的不懂法德语，只会人，会日语的不懂法德语，只会1种和种和3种人？种人？令同时会三种语言为令同时会三种语言为x人，人，只会英为

5、只会英为y1,只会法为只会法为y2,只会德语只会德语y3 y1+2+4-x+x+4-x=13 y2+4-x+4-x+x=9 y3+2(4-x)+x=10 y1+y2+y3+3+2+3(4-x)+x=24法法德德英英日日xy1y2y324-x4-x4-x5-2x=1，y1=4，y2=2，y3=3本讲稿第五页，共六十一页3.3、包含排斥原理包含排斥原理|A1 A2|=|A1|+|A2|-|A1 A2|因为公共部分算了两次！因为公共部分算了两次！例例：A1=蓝球队蓝球队=10，A2=足球队足球队=13，双重身份，双重身份球员球员3人，请问这二个球队总共多少人？人，请问这二个球队总共多少人？解解：|A

6、1 A2|=|A1|+|A2|-|A1 A2|=10+13-3=20人人|A1 A2|=|Ai|-|Ai Aj|+|Ai Aj Ak|-|Ai Aj Ak AL|.+(-1)n-1|A1 A2 An|加奇数个集合相交加奇数个集合相交-偶数集合相交偶数集合相交A1A2本讲稿第六页，共六十一页3.3、集合计数集合计数|A1 A2|=|A1|+|A2|-|A1 A2|A1 A2|=|Ai|-|Ai Aj|+|Ai Aj Ak|-|Ai Aj Ak AL|.+(-1)n-1|A1 A2 An|加奇数个集合相交加奇数个集合相交-偶数集合相交偶数集合相交例题例题：设校足球队的球衣有：设校足球队的球衣有38

7、件，蓝球有件，蓝球有15件，排件，排球有球有20件，三队总数为件，三队总数为58人，人，3个同时参加个同时参加3队，请队，请问同时参加二队有多少？问同时参加二队有多少？解解|A1 A2 A3|=|Ai|-|Ai Aj|+|Ai Aj Ak|58=(38+15+20)-|Ai Aj|+3|Ai Aj|=18A1A2本讲稿第七页，共六十一页例题例题在在1,300整数中能被整数中能被3或或5或或7整除的整数的个数。整除的整数的个数。解解：A3示能被示能被3整除的数整除的数,A5能被能被5整除整除,A7能被能被7整除整除.能被能被3整除的个数：整除的个数：|A3|=300/3=100能被能被5整除的个

8、数：整除的个数：|A5|=300/5=60能被能被7整除的个数：整除的个数：|A7|=300/7=42能被能被3与与5同时整除的个数：同时整除的个数：|A3 A5|=300/15=20能被能被3与与7同时整除的个数：同时整除的个数：|A3 A7|=300/21=100/7=14能被能被5与与7同时整除的个数：同时整除的个数：|A5 A7|=300/35=60/7=8能被能被3、5、7同时整除的个数：同时整除的个数：|A3 A5 A7|=2能被能被3或被或被5或被或被7整除的个数：整除的个数：|A3 A5 A7|=|A3|+|A5|+|A7|-|A3 A5|-|A3 A7|-|A5 A7|+|A

9、3 A5 A7|=100+60+42-20-14-8+2=162本讲稿第八页，共六十一页3.4、序偶序偶 定定义义3.4.1 将将具具有有次次序序的的两两对对象象写写在在一一块块，称称为为序序偶偶即即有有秩秩序的二个对象，记为序的二个对象，记为或或。如如:,定义定义3.4.2 令令与与是二个序偶，如果是二个序偶，如果x=u、y=v，那，那么么=即即2个序偶相等个序偶相等。序偶序偶，a代表操作码，代表操作码，b代表地址码，显然来自两个不代表地址码，显然来自两个不同的集合。同的集合。定义定义3.4.3 如果如果是序偶，且是序偶，且,z也是一个序偶，也是一个序偶，则称则称为三元组。为三元组。如如，。

10、定义定义3.4.4 如果如果是是n-1 元组，而元组，而,xn是序偶，则称为是序偶，则称为为为n元组。元组。本讲稿第九页，共六十一页3.5 直积或笛卡尔积直积或笛卡尔积 定义定义3.5.1 令令A、B是两个集合，称集合是两个集合，称集合|x A,y B为为A与与B的的直积直积或或笛卡尔积笛卡尔积，记为记为A B。如如A=1,2,3,B=a,b,cA B=1,2,3 a,b,c=,B A=a,b,c 1,2,3=,由于由于，所以，所以A B B A 直积不满足交换律直积不满足交换律,序偶的前后序偶的前后2个元素来自于不同的集合，也可以个元素来自于不同的集合，也可以来自同一个集合。来自同一个集合。

11、本讲稿第十页，共六十一页3.5 直积或笛卡尔积直积或笛卡尔积又如又如 A=中中,巴巴,美美,古古 A A=中中,巴巴,美美,古古 中中,巴巴,美美,古古=,直积的结果实际是一个直积的结果实际是一个集合集合,具有以下性质具有以下性质1、A (B C)=AC)=A B B A A C C 2 2、A A (B(B C)=AC)=A B B A A C C3 3、(B(B C)A=B A=B A C A A 4 4、(B(B C)A=B A=B A A C A A 5 5、A A B BA A C B B C CC A A C C B B6 6、A A B,CB,C D D A A C C B D

12、D本讲稿第十一页，共六十一页3.6、关系、关系 将笛卡尔积中将笛卡尔积中前后两个元素前后两个元素之间存在之间存在某种关系某种关系的的序序偶偶检出来检出来,便得到一个便得到一个关系关系。A B=1,2,3 a,b,c=,R1=前后两个元素的前后两个元素的序号序号一样一样 =,A A=1,2,3 1,2,3=,R2=第一个元素第一个元素第第2个元素个元素 =,有时无法有时无法用文字描述两者用文字描述两者的关系，只好将相关的序的关系，只好将相关的序偶选出来。偶选出来。R3=,本讲稿第十二页，共六十一页3.6、关系、关系 将笛卡尔积中将笛卡尔积中前后两个元素前后两个元素之间存在之间存在某种关系某种关系

13、的的序偶序偶检出来检出来,便得到一个便得到一个关系关系。定义定义3.6.2 如果如果序偶序偶或或元组元组属于某个关系属于某个关系R，则，则称序偶或元组称序偶或元组具有关系具有关系R。若序偶若序偶 R，还可写成，还可写成xRy，将关系名称写在二个元素之间，将关系名称写在二个元素之间，其他数学也是这样表示，如其他数学也是这样表示，如24，2|4，2=2 如如 R，可可写成，可可写成2R4 如如 R2，可写成，可写成2R24 也有人认为，这种写法不直观，可能产生歧义，也有人认为，这种写法不直观，可能产生歧义，本课程尽量回避这种写法。本课程尽量回避这种写法。本讲稿第十三页，共六十一页3.6 关系的描述

14、关系的描述 A B=1,2,3 a,b,c=,R1=前后两个元素的序号一样前后两个元素的序号一样 =,除给出关系中所包含的序除给出关系中所包含的序偶外，还可用偶外，还可用关系矩阵关系矩阵、关系图关系图表示。表示。123abc本讲稿第十四页，共六十一页3.6 关系的描述关系的描述 A=1,2,3,4,5,6,7,8,R3=,关系矩阵关系矩阵本讲稿第十五页，共六十一页3.6 关系的描述关系的描述 关系图：令关系图：令R A B，则将，则将A、B的元素均画成一个点，的元素均画成一个点，如果序偶如果序偶 R，则从点，则从点x画一条画一条有向边有向边到点到点y。A=1,2,3,4,5,6,7,8，R=,

15、序偶前后元素均是序偶前后元素均是A，还可，还可简简化！化！本讲稿第十六页，共六十一页3.6 关系的描述关系的描述 关系图：令关系图：令R A B，则将，则将A、B的元素均画成一个点，的元素均画成一个点，如果序偶如果序偶 R，则从点，则从点x画一条画一条有向边有向边到点到点y。A=1,2,3,4,5，R=,，则其关系图如下则其关系图如下 本讲稿第十七页，共六十一页3.7、关系复合关系复合 A=1,2,3,F AxA,G AxA A上的关上的关系系 设设F,G为二元关系为二元关系,G对对F的右复合记为的右复合记为F G,定义定义F G=|t(F,G)如如F=,G=,F G=,M(F G)=M(F)

16、M(G)可用关系矩阵相乘可用关系矩阵相乘/关系图表示关系图表示123123本讲稿第十八页，共六十一页A=1,2,3,F AxA,G AxA A上的关系上的关系F=,G=,123123123123本讲稿第十九页，共六十一页3.7、关系复合关系复合 MF的第的第i行与行与MG的第的第j列相乘时，列相乘时，乘法是乘法是合取合取，加法是，加法是析取析取，如如MF1行与行与MG3列相乘列相乘(1 1)(1 0)(0 0)，结果为，结果为1。定义定义3.7.2 称称|F 为为F的逆，的逆，记为记为F-1 令令A=1,2,3，F=,。则则F-1=,性质性质：(1)结合律结合律 (P R)S=P(R S)(2

17、)复合的逆复合的逆(P R)-1=R-1 P-1本讲稿第二十页，共六十一页3.8、关系的性质与分类关系的性质与分类 自反关系自反关系:若关系若关系R前后二个元素来自同一个集前后二个元素来自同一个集合合A,若若 x A,都有都有 R,则则R是自反的是自反的.反自反关系反自反关系:若关系若关系R前后二个元素来自同一个前后二个元素来自同一个集合集合 A,若若 x A,都有都有 R,则则R是反自反的是反自反的.如如:A=1,2,3 R1=,因为因为 R1不是自反的不是自反的 因为因为 R1,R1,故不是反自反的故不是反自反的.R2=,自反的自反的!R3=反自反的反自反的!本讲稿第二十一页，共六十一页3

18、.8、关系的性质与分类关系的性质与分类 自反关系自反关系:若若 x A,有有 R,则自反的则自反的.主对全主对全1 反自反关系反自反关系:若若 x A,有有 R,则则R反自反反自反主对全主对全0 如如:A=1,2,3 R1=,自反的自反的!R2=反自反反自反!R3=,不是自反不是自反,不是反自反不是反自反.321321321自反自反自反自反反自反反自反反自反反自反本讲稿第二十二页，共六十一页3.8、关系的性质与分类关系的性质与分类 自反关系自反关系:若若 x A,有有 R,则自反的则自反的.主对全主对全1 反自反关系反自反关系:若若 x A,有有 R,则则R反自反反自反主对全主对全0 定义定义

19、3.8.3 若关系若关系R=A A，则称为全域关系，记为，则称为全域关系，记为EA.在全域关系中，由于直积的每个序偶都在关系在全域关系中，由于直积的每个序偶都在关系R中，中，所以其关系矩阵全是所以其关系矩阵全是1，主对角线肯定也为主对角线肯定也为1，故是自反关系。，故是自反关系。定义定义3.8.4 若所有形如若所有形如的序偶都在关系的序偶都在关系R中，中，R也也只有这种形式的序偶，则称只有这种形式的序偶，则称R为恒等关系，记为为恒等关系，记为IA。若若R是自反关系，则恒等关系是自反关系，则恒等关系IA R 如如A=1,2,3,则则IA=,本讲稿第二十三页，共六十一页3.8、关系的分类关系的分类

20、 自反关系自反关系:若若 x A,都有都有 R 反自反关系反自反关系:若若 x A有有 R 对称关系对称关系:若若 R有有 R 反对称关系反对称关系:若若 R,Rx=y也可：也可：若若 R且且x y R则反对称则反对称 如如:A=1,2,3 R1=,对称对称 R2=,反对称反对称 R3=,因因 R1不对称不对称,因因与与成对出现成对出现,而而不是不是反对称反对称本讲稿第二十四页，共六十一页3.8、关系的分类关系的分类 1-2班班 对称关系对称关系:若若 R有有 R 非对角成对非对角成对 反对称关系反对称关系:若若 R且且x y R 如如:A=1,2,3 R1=,对称对称 R2=,反对称反对称

21、R3=,321321321本讲稿第二十五页，共六十一页3.8、关系的分类关系的分类 对称关系对称关系:若若 R有有 R 非对角成对非对角成对 反对称关系反对称关系:若若 R,Rx=y 2个定义等价个定义等价 若若 R且且x y R(R x y)R(R x y)R条件式的等值式条件式的等值式 R x y R德摩律德摩律 R x=y R 的含义的含义(R R)x=y结合律结合律(R R)x=y德摩律德摩律(R R)x=y条件式的等值式条件式的等值式本讲稿第二十六页，共六十一页3.8、关系的性质与分类关系的性质与分类 传递关系传递关系:若若 R,R R 表示两个序偶的复合仍在表示两个序偶的复合仍在R

22、中中,即即R R R,M2 M A=a,b,c R=,R R=,=,R 学会看图学会看图abcdRRR R本讲稿第二十七页，共六十一页3.8、关系的性质与分类关系的性质与分类 传递关系传递关系:若若 R,R R 表示复合仍在表示复合仍在R中中,即即R R R,M2 M如如A=1,2,3 R1=,R1 R1=,=,R故可传递故可传递 复合边复合边已在图中，或已在图中，或传递可达传递可达的二点有边的二点有边直连直连.123本讲稿第二十八页，共六十一页3.8、关系的性质与分类关系的性质与分类 传递关系传递关系:若若 R,R R 表示复合仍在表示复合仍在R中中,即即R R R,M2 M 如如A=1,2

23、,3 R2=,传递的产生的传递的产生的 R故故不是不是复合边复合边已在图中，或已在图中，或传递可达传递可达的二点有边的二点有边直连直连.123本讲稿第二十九页，共六十一页3.8、关系的性质与分类关系的性质与分类 传递关系传递关系:若若 R,R R 表示两个序偶的复合仍在表示两个序偶的复合仍在R中中,即即R R R,M2 M如如A=1,2,3 R1=,可传递可传递的，的，OKR1 R1=R1 R1故为可传递！故为可传递！123本讲稿第三十页，共六十一页3.8、关系的性质与分类关系的性质与分类 自反关系自反关系:x A RIA R 反自反关系反自反关系:x A RIA R=对称关系对称关系:R R

24、 R=R-1反对称关系反对称关系:R,Rx=y R且且x y R R R-1 IA传递关系传递关系:R,R RR2 R自反自反:主对角线均为主对角线均为1 反自反反自反:主对角线均为主对角线均为0对称对称:M=MT。反对称反对称：M MT后只有主对角非后只有主对角非0传递传递:R2 R即即M2 M 本讲稿第三十一页，共六十一页3.9、关系的闭包：加点序偶使之成某种类型关系的闭包：加点序偶使之成某种类型1、R自反闭包自反闭包r(R)：加序偶使之成自反的。加序偶使之成自反的。R=,不是自反不是自反 r(R)=,r(R)=R IA321321本讲稿第三十二页，共六十一页3.9、关系的闭包：加点序偶使

25、之成某种类型关系的闭包：加点序偶使之成某种类型2、R对称闭包对称闭包s(R)：加序偶使之成对称的。加序偶使之成对称的。R=,反对称反对称 s(R)=,对称对称s(R)=R RT.321321本讲稿第三十三页，共六十一页3.9、关系的闭包关系的闭包 A=a,b,c,d，R=,，求其传递闭包求其传递闭包 解：先求解：先求R2，若，若R2 R则则R是传递关系，即是传递关系，即不添不添序偶就得传递关系，传递闭包就是序偶就得传递关系，传递闭包就是R。若若R2 R，表示复合产生的序偶不在，表示复合产生的序偶不在R中，为了中，为了可传递，故将复合出来的序偶投入到可传递，故将复合出来的序偶投入到R中即得到中即

26、得到R2 R。新序偶与旧序偶又复合出二代新序偶。新序偶与旧序偶又复合出二代新序偶。若二代新序偶已在若二代新序偶已在R2 R中，则中，则R2 R已是可传已是可传递关系，则它就是传递闭包，即递关系，则它就是传递闭包，即t(R)=R2 R。否则将二代新序偶放入否则将二代新序偶放入R中，得到中，得到R3 R2 R。重复以上过程，直到得到一个传递关系。重复以上过程，直到得到一个传递关系。本讲稿第三十四页，共六十一页例例A=a,b,c,d,R=,R2=,R3=,=,t(R)=,结点结点u u出发经过出发经过2 2条边到达条边到达条边到达条边到达v,v,若若u u与与与与v v有边相连则可传递有边相连则可传

27、递有边相连则可传递有边相连则可传递 当集合当集合当集合当集合A A有有n n结点时结点时,从从从从u u出发，若结点不重复，最多可经过其出发，若结点不重复，最多可经过其出发，若结点不重复，最多可经过其出发，若结点不重复，最多可经过其他他他他n-1n-1结点，最多可依次跨越结点，最多可依次跨越结点，最多可依次跨越结点，最多可依次跨越n-1n-1条不同的边，条不同的边，条不同的边，条不同的边，故以上重复过程，最多经过故以上重复过程，最多经过故以上重复过程，最多经过故以上重复过程，最多经过n-1n-1轮，最多求到轮，最多求到轮，最多求到轮，最多求到R Rn-1n-1。本讲稿第三十五页，共六十一页例例

28、A=a,b,c,d,R=,R2=,R3=,=,t(R)=,由关系的复合可知，由关系的复合可知，R,R R=R2,R3,Rn-1,可由可由关系矩阵的积来实现。关系矩阵的积来实现。R R2 R3 Rn-1,将剔除将剔除重复出现重复出现的序偶的序偶,因因此可由矩阵幂次方的析取此可由矩阵幂次方的析取MR(MR)2(MR)n-1实实现现,即即t(R)=MR(MR)2(MR)n-1。本讲稿第三十六页，共六十一页t(R)=R R2 R3.Rn-1.任何两点最多任何两点最多n-1步达步达 =M M2 M3 .Mn-1.例例A=a,b,c,d,R=,t(R)=,abcd本讲稿第三十七页，共六十一页t(R)=R

29、R2 R3.Rn-1.任何两点最多任何两点最多n-1步达步达 =M M2 M3 .Mn-1.效率比较低！效率比较低！Warshall算法算法for(j=1;jn;j+)/第第1列到最后列列到最后列 for(i=1;in;i+/第第j列从第列从第1行到最后行行到最后行 if(M(i,j)=1)第第i行行=第第i行行 第第j行行;本讲稿第三十八页，共六十一页3.10、等价关系、等价类、分类、等价关系、等价类、分类(划分划分)自反自反、对称对称、可传递可传递的关系称为等价关系。的关系称为等价关系。例例 A=1,2,3,4,5,6,7,8R=,=|x-y=3k判断判断:是否为是否为等价关系等价关系(1

30、)x A,因因x-x=0=3*0，故，故 R，故自反故自反(2)Rx-y=3k y-x=3(-k)R(3)R,Rx-y=3k,y-z=3m x-z=3(k+m)R本讲稿第四十页，共六十一页3.10、等价关系、等价类、分类、等价关系、等价类、分类(划分划分)例例 A=1,2,3,4,5,6,7,8R=,彼此有等价关系的元素的集合彼此有等价关系的元素的集合,称为称为等价类等价类.如：上述关系如：上述关系R的序偶分成的序偶分成3类类=,等价类有：等价类有：1,4,7，2,5,8，3,6 简记为简记为1=4=7 这显然对集合这显然对集合A的元素进行了划分！的元素进行了划分！本讲稿第四十一页，共六十一页

31、3.10、等价关系、等价类、分类、等价关系、等价类、分类(划分划分)设设R A A，R是是等价关系等价关系，A0,A1,Ak是基于是基于R得到的得到的等价类等价类，则称，则称集合集合A0,A1,Ak为为A关于关于R的的商集商集，记为，记为A/R。例例 A=1,2,3,4,5,6,7,8R=,=,A/R=A0,A1,A2=1,4,7,2,5,8,3,6 本讲稿第四十二页，共六十一页划分划分:若若A=A0 A1 Ak,且不相交且不相交,则称则称A的划分的划分例例 A=1,2,3,4,5,6,7,8R=,因为等价类因为等价类1,4,7,2,5,8,3,6彼此彼此不相交不相交，并集并集为为A，称为，称

32、为A的划分的划分,因此等价关系可划分集合因此等价关系可划分集合。定理定理 设设R A A，R是等价关系，是等价关系，A0,A1,Ak-1是利用是利用R得到的得到的k个不同的等价类，则个不同的等价类，则A0,A1,Ak为集合为集合A的划的划分分3.10、等价关系、等价类、分类（划分）、等价关系、等价类、分类（划分）本讲稿第四十三页，共六十一页 划分划分:若若A=A0 A1 Ak,且不相交且不相交,则称则称A的划分的划分 定理定理 设设R A A，R是等价关系，是等价关系，A0,A1,Ak-1是利用是利用R得到的得到的k个不同个不同的等价类，则的等价类，则A0,A1,Ak为集合为集合A的划分的划分

33、(1)当当i j 时假设时假设Ai Aj。则。则 x Ai Aj可知可知x Ai，x Aj，对对Ai中任意元中任意元y，由等价类定义知，由等价类定义知,R，对对Aj中任意元素中任意元素z，也有，也有,R。因因R是等价关系及是等价关系及,R可知可知 R,同理同理 R，所以所以,R，即二者的任意组合构成的序偶都在，即二者的任意组合构成的序偶都在R中，根据等价类的定义中，根据等价类的定义y与与z在同一个等价类中，即在同一个等价类中，即Ai=Aj，与前提矛盾，与前提矛盾，故假设错。只能故假设错。只能Ai Aj=。(2)x A，若，若x与其他所有元素都没有关系，则单个与其他所有元素都没有关系，则单个x构

34、成一个等价类。构成一个等价类。若若x与有其他元素有等价关系与有其他元素有等价关系R，则与他们处于一等价类，则与他们处于一等价类.总之总之x至少属于一个等价类至少属于一个等价类Ai，所以，所以x A0 A1 Ak-1，所以，所以A A0 A1 Ak-1。又由等价类的定义可知。又由等价类的定义可知Aj A，故故A0 A1 Ak-1 A，故，故A=A0 A1 Ak-1。3.10、等价关系、等价类、分类（划分）、等价关系、等价类、分类（划分）本讲稿第四十四页，共六十一页划分划分:若若A=A0 A1 Ak,且不相交且不相交,则称则称A的划分的划分例例 A=1,2,3,4,5,6,7,8R=,因为等价类因

35、为等价类1,4,7,2,5,8,3,6彼此彼此不相交不相交，并集并集为为A，称为，称为A的划分的划分,因此等价关系可划分集合因此等价关系可划分集合。(1)观察关系中的序偶可得到划分观察关系中的序偶可得到划分 (2)观察关系图也可得到划分观察关系图也可得到划分3.10、等价关系、等价类、分类（划分）、等价关系、等价类、分类（划分）本讲稿第四十五页，共六十一页3.10、等价关系、等价类、分类、等价关系、等价类、分类(划分划分)自反自反、对称对称、可传递可传递的关系称为等价关系。的关系称为等价关系。例例 A=1,2,3,4,5,6,7,8R=,=1,4,7x1,4,7 2,5,8x2,5,8 3,6

36、x3,6由由等价关系等价关系 找出找出 划分划分 1,4,7,2,5,8,3,6.反过来，由反过来，由划分划分 构造构造 等价关系等价关系吗？吗？本讲稿第四十六页，共六十一页3.10、等价关系、等价类、分类、等价关系、等价类、分类(划分划分)R=A1 A1 A2 A2 A3 A3 R=1,4,7x1,4,7 2,5,8x2,5,8 3,6x3,6 可验证可验证R是等价关系是等价关系!再如再如A的划分的划分:A1=1,2,3,A2=4,5,6,A3=7,8，则则R=A1 A1 A2 A2 A3 A3=,R是对称、自反、可传递的等价关系。是对称、自反、可传递的等价关系。本讲稿第四十七页，共六十一页

37、3.10、等价关系、等价类、分类、等价关系、等价类、分类(划分划分)定定理理3.10.2 设设A0,A1,Ak-1是是A的的划划分分，R=A0 A0 A1 A1 Ak-1 Ak-1，则，则R等价关系。等价关系。(1)x A，由由划划分分的的定定义义可可知知，x肯肯定定属属于于某某个个子子集集Ai，所所以以 Ai Ai，故，故 R,自反自反。(2)若若 R，则则至至少少属属于于某某个个子子集集Ai的的直直积积(如如果果不不属属于于任任何何Ai 的的直直积积则则不不属属于于R)，即即 Ai Ai，由由于于Ai的的直积是直积是对对称的，故称的，故 Ai Ai R,故故R对称对称。(3)若若 Ai A

38、i则则 Ai Ai。假设。假设 Aj Aj，其中其中i j。由。由 Ai Ai有有x Ai,y Ai，由，由 Aj Aj有有y Aj,z Aj，故，故y Ai又又y Aj这不可能，故假设错，只能这不可能，故假设错，只能 Ai Ai。因因Ai直积可传递，故直积可传递，故 Ai Ai R，故，故R可传递。可传递。本讲稿第四十八页，共六十一页3.11、偏序关系、偏序关系 1、自反、反对称、可传递、自反、反对称、可传递的关系。的关系。例题例题设设A=实数集，实数集，R是实数中小于等于关系，即是实数中小于等于关系，即R=|x,y是实数，是实数，且且x y，则，则R是偏序关系。是偏序关系。(1)x A(实

39、数实数)有有x x，故，故 R，即为，即为自反自反关系。关系。(2)若若 R,R，则，则x y且且y x,故故x=y,故故反对反对称称(3)若若 R,R，则，则x y且且y z，故，故x z,R可传递可传递 例题例题：A=1,2,3,4,5,6 R=:x|y(1)x|x，故，故 R即即自反自反(2)x|y,y|x即即y=kx,x=my，故，故x=m(kx),故故mk=1,故故k=m=1 故故x=y，故，故反对反对称称(3)x|y,y|z即即y=kx,z=my，故，故z=m(kx)=mkx即即x|z故故可传递可传递 偏序关系可偏序关系可理解理解为广义的为广义的“小于等于小于等于”关系，记为关系，

40、记为。本讲稿第四十九页，共六十一页3.11、偏序关系、偏序关系 1、自反、反对称、可传递、自反、反对称、可传递的关系。可的关系。可理解理解为广义的为广义的“小于等于小于等于”关系，记为关系，记为。2、当、当 时，写成时，写成x y，主要为了直观。，主要为了直观。3、当、当 但但x y时，记成时，记成xy即即严格小于严格小于。4、x,y A,x与与y可比可比是指是指或或，即，即x y或或y x。例题例题：A=1,2,3,4,5,6 R=:x|yR=,R，可记为，可记为1 2,也可也可12 R，可记为，可记为2 2,不可不可22 2与与4可比可比，因为，因为 R即即2 4 可比与不可比可比与不可比

41、 4与与2可比可比，因为，因为 R即即2 4 2与与5不可比不可比，因为，因为 R,R本讲稿第五十页，共六十一页3.11、偏序关系、偏序关系 1)自反、反对称、可传递自反、反对称、可传递的关系。广义的的关系。广义的“小于等于小于等于”关系，关系，记为记为。2)当当 时，写成时，写成x y，主要为了直观。，主要为了直观。3)当当 但但x y时，记成时，记成xy即即严格小于严格小于。4)x,y A x与与y可比可比是指是指或或。5)全序全序(线序线序):x,y A，x与与y都可比都可比。如如A=1,2,3,4,5,6 R=:x y 狭义狭义 关系图中所有点在一条线上！关系图中所有点在一条线上！B=

42、1,2,A=,1,2 R=:x y,x A,y A,即即x与与y是是B的子集。的子集。全序全序 B=1,2,A=,1,2,1,2 R=:x y,x A,y A,即即x与与y是是B的子集。的子集。偏序偏序a,b 本讲稿第五十一页，共六十一页3.11、偏序关系、偏序关系 1)自反、反对称、可传递自反、反对称、可传递的关系。的关系。2)当当 时，写成时，写成x y，主要为了直观。，主要为了直观。3)当当 但但x y时，记成时，记成xy即即严格小于严格小于。4)x,y A x与与y可比可比是指是指或或。5)全序全序(线序线序):x,y A，x与与y都可比都可比。6)偏序集偏序集：。A=1,2,3,4,

43、5,6 R=:x y B=1,2,A=,1,2,1,2 R1=:x y,x A,y A,B=1,2,A=,1,2 R2=:x y,x A,y A 本讲稿第五十二页，共六十一页3.11、偏序关系、偏序关系 7)哈斯图哈斯图 因箭头都朝上方，故箭头不画。因箭头都朝上方，故箭头不画。因每个结点因每个结点都有都有自旋箭头，故不画自旋。自旋箭头，故不画自旋。因可传递即因可传递即复合边均复合边均在其中，故将传递可达在其中，故将传递可达的二点间的的二点间的直达直达边去掉。边去掉。这样得到的图为这样得到的图为哈斯图哈斯图。1,2 121,2 121,2 12本讲稿第五十三页，共六十一页3.11、偏序关系、偏序

44、关系 因箭头都朝上方，故箭头不画。因箭头都朝上方，故箭头不画。因每个结点因每个结点都有都有自旋箭头，故不画自旋。自旋箭头，故不画自旋。因可传递即因可传递即复合边均复合边均在其中，故将传递可达在其中，故将传递可达的二点间的的二点间的直达直达边去掉。边去掉。这样得到的图为这样得到的图为哈斯图哈斯图。本讲稿第五十四页，共六十一页3.11、偏序关系、偏序关系 2)当当 时，写成时，写成x y，主要为了直观。，主要为了直观。4)x,y A x与与y可比可比是指是指或或。6)偏序集偏序集：。8)盖住盖住:x A,y A,xy,z A,使得使得xzy则称则称y盖住盖住x.在在x的上方最近者。的上方最近者。B

45、=1,2,A=,1,2,1,2 R1=:x y,x A,y A,1盖住盖住,2盖住盖住,但但1,2并不盖住并不盖住.1,2 12本讲稿第五十五页，共六十一页3.11、偏序关系、偏序关系-最大元最大元/最小元最小元 9)最大元最大元:设设是偏序集，是偏序集，B A,y0 B,若若 x B,均有均有 R，则，则y0是是B的最大元。的最大元。y0与与B每个每个元素元素x有关系有关系R即即可比可比，且，且比其大比其大。最小元类似定义最小元类似定义abcgdfeh123574869B=a,b,c,d,e,f,g,h 最大最小无最大最小无B=18 有最小有最小B=1,2,4,8 有最大与最小有最大与最小B

46、=b,c,d,e,f 最大有最大有本讲稿第五十六页，共六十一页3.11、偏序关系、偏序关系-极大元极大元/极小元极小元 9)最大元最大元:设设是偏序集，是偏序集，B A,y0 B,若若 x B,均有均有 R，则，则y0是是B的最大元。的最大元。y0与与B每个每个元素元素x有关系有关系R即即可比可比，且，且比其大比其大。10)极大元极大元:不存在不存在x使使 R.哈图无元居其哈图无元居其上上 极小元极小元:不存在不存在x使使 R.哈图无元居其哈图无元居其下下abcgdfeh123574869极大元极大元a,f,h极小极小 元元a,b,c,g极大元极大元8,6,9,7极小元极小元1本讲稿第五十七页

47、，共六十一页3.11、偏序关系、偏序关系-极大元极大元/极小元极小元 10)极大元极大元:不存在不存在x使使 R.哈图无元居其哈图无元居其上上 极小元极小元:不存在不存在x使使 R.哈图无元居其哈图无元居其下下11)上界上界:在偏序集在偏序集中，中，B A，y A，若任意，若任意x B都都有有 R，则称，则称y是是B的的上界上界。与与B中每个元素都可比，并且都中每个元素都可比，并且都B中的元素大中的元素大 abcgdfeh123574869b,c上界上界f,d,e1,2的上界的上界2,4,6,8本讲稿第五十八页，共六十一页3.11、偏序关系、偏序关系-极大元极大元/极小元极小元11)上界上界:

48、在偏序集在偏序集中，中，B A，y A，若任意，若任意x B都都有有 R，则称，则称y是是B的的上界上界。12)下界下界:在偏序集在偏序集中，中，B A，y A，若任意，若任意x B都都有有 R，则称，则称y是是B的下界。的下界。与与B中每个元素都可比，并且都中每个元素都可比，并且都B中的中的元素小元素小 abcgdfeh123574869f,d,e下界下界b,c8,4,6,2下界下界1,2本讲稿第五十九页，共六十一页3.11、偏序关系、偏序关系-极大元极大元/极小元极小元11)上界上界:在偏序集在偏序集中，中，B A，y A，若任意，若任意x B都有都有 R，则称，则称y是是B的的上界上界。

49、与与B中每个元素都可比，并且都中每个元素都可比，并且都B中的元素大中的元素大13)上确界上确界:在偏序集在偏序集中，中，B A，设，设C为为B的的所有上界所有上界元元的集合，若的集合，若C中有中有最小元最小元则该最小元称为则该最小元称为B的的上确界上确界 abcgdfeh123574869b,c上界上界f,d,e无无最小元最小元1,2的上界的上界2,4,6,8,最小元最小元2本讲稿第六十页，共六十一页3.11、偏序关系、偏序关系-极大元极大元/极小元极小元12)下界下界:在偏序集在偏序集中，中，B A，y A，若任意，若任意x B都都有有 R，则称，则称y是是B的下界。的下界。14)下确界下确界:在偏序集在偏序集中，中，B A，设，设C为为B的所有的所有下下界元界元的集合，若的集合，若C中有最大元则该最大元为中有最大元则该最大元为B的的下确界下确界 abcgdfeh123574869f,d,e下界下界b,c无无最大元最大元8,4,6,2下界下界1,2最大元最大元2本讲稿第六十一页，共六十一页