集合论与关系.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 集合与关系,杨圣洪,3.1,、,集合的基本概念,不产生歧义的对象的汇集一块便构成集合,.,集合常用,枚举法,:,湖大教学楼,=,复临,中楼,东楼,北楼,前进楼,描述法,:,偶数集,=,除以,2,余为,0,的所有整数,子集,A,B:A,中的每个元素都是,B,的元素,幂集,P(A)=A,的所有子集的集合,=,2,A,.,如,A=1,2,3,A,000,=,A,001,=3,A,010,=2,A,011,=2,3,A,100,=1,A,101,=1,3,A,110,=1,2,A,111,=1,2,3,其有,2,3,个,即,2,|A|,个,3.2,、,集合的运算与性质,1,、,A,B,=,由同时属于,A,与,B,的元素组成,2,、,A,B,=,由属于,A,或属于,B,的元素组成,3,、,A-B,=,由属于,A,但不属于,B,的元素组成,4,、,A,=,全集,U,中不属于,A,的元素组成,=,U-A,A,B,A,B,A-B,A,A,B,3.2,、,集合的运算与性质,定义,3.1.1,如果集合,A,中任何元素都是,B,的元素，则称,A,是,B,的子集，记为,AB,，也称,B,包含,A,，记为,BA,。,定义,3.2.3,设,A,、,B,是两个集合，若,AB,、,BA,则,A=B,，即两个集合相等。,以下性质可根据相等定义得到，与命题逻辑性质一样,幂等律,AA=A,，,AA=A,结合律,ABC=A(BC)=(AB)C,ABC=A(B C)=(AB)C,交换律,AB=BA AB=BA,分配律,A(BC)=(AB)(AC),A(BC)=(AB)(AC),同一,/,零律,A=A A =,排中,/,矛盾律,AA=E A A=,吸收律,(,大吃小,)A(BA)=A,A(BA)=A,德摩律,(AB)=AB (AB)=A B,双重否定,A=A,3.3,、,有穷集的计数,1,、,|A|,=,集合,A,的元素数,2,、例题：,24,人中,(,书上缺少此条件,),，会英,=13,、日,=5,、德,=10,、法,=9,，同时会英日有,2,人，会德、法、英中任意二种有,4,人，会日语的不懂法德语，只会,1,种和,3,种人？,令同时会三种语言为,x,人，,只会英为,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,法,德,英,日,x,y1,y2,y3,2,4-x,4-x,4-x,5-2,x=1,，,y1=4,，,y2=2,，,y3=3,3.3,、,包含排斥原理,|A,1,A,2,|=|A,1,|+|A,2,|-|A,1,A,2,|,因为公共部分算了两次！,例,：,A1=,蓝球队,=10,，,A2=,足球队,=13,，双重身份球员,3,人，请问这二个球队总共多少人？,解,：,|A,1,A,2,|=|A,1,|+|A,2,|-|A,1,A,2,|=10+13-3=20,人,|A,1,A,2,|=,|A,i,|-,|,A,i,A,j,|,+,|,A,i,A,j,A,k,|-,|A,i,A,j,A,k,A,L,|,.,+(-1),n-1,|A,1,A,2,A,n,|,加奇数个集合相交,-,偶数集合相交,A,1,A,2,3.3,、,集合计数,|A,1,A,2,|=|A,1,|+|A,2,|-|A,1,A,2,|,|A,1,A,2,|=,|A,i,|-,|,A,i,A,j,|,+,|,A,i,A,j,A,k,|-,|A,i,A,j,A,k,A,L,|,.,+(-1),n-1,|A,1,A,2,A,n,|,加奇数个集合相交,-,偶数集合相交,例题,：设校足球队的球衣有,38,件，蓝球有,15,件，排球有,20,件，三队总数为,58,人，,3,个同时参加,3,队，请问同时参加二队有多少？,解,|A,1,A,2,A,3,|=,|A,i,|-,|,A,i,A,j,|+,|A,i,A,j,A,k,|,58=(38+15+20)-,|A,i,A,j,|+3,|,A,i,A,j,|=18,A,1,A,2,例题,在,1,300,整数中能被,3,或,5,或,7,整除的整数的个数。,解,：,A3,示能被,3,整除的数,A5,能被,5,整除,A7,能被,7,整除,.,能被,3,整除的个数：,|A3|=300/3=100,能被,5,整除的个数：,|A5|=300/5=60,能被,7,整除的个数：,|A7|=300/7=42,能被,3,与,5,同时整除的个数：,|A3A5|=300/15=20,能被,3,与,7,同时整除的个数：,|A3A7|=300/21=100/7=14,能被,5,与,7,同时整除的个数：,|A5A7|=300/35=60/7=8,能被,3,、,5,、,7,同时整除的个数：,|A3A5A7|=2,能被,3,或被,5,或被,7,整除的个数：,|A3A5A7|,=|A3|+|A5|+|A7|-|A3A5|-|A3A7|-|A5A7|+|A3A5A7|,=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,也是一个序偶，则称,为三元组。,如,，,，,，,。,定义,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,c,A,B,=1,2,3a,b,c=,B,A,=a,b,c,1,2,3=,由于,，所以,A,B,B,A,直积不满足交换律,序偶的前后,2,个元素来自于不同的集合，也可以来自同一个集合。,3.5 直积或笛卡尔积,又如,A,=,中,巴,美,古,A,A,=,中,巴,美,古,中,巴,美,古,=,直积的结果实际是一个,集合,具有以下性质,1,、,A,(B,C)=A,B,A,C,2,、,A,(B,C)=A,B,A,C,3,、,(B,C),A=B,A,C,A,4,、,(B,C),A=B,A,C,A,5,、,A,B,A,C,B,C,C,A,C,B,6,、,A,B,C,D,A,C,B,D,3.6,、关系,将笛卡尔积中,前后两个元素,之间存在,某种关系,的,序偶,检出来,便得到一个,关系,。,A,B,=1,2,3a,b,c=,R1=,前后两个元素的,序号,一样,=,A,A,=1,2,31,2,3=,R2=,第一个元素,第,2,个元素,=,有时无法,用文字描述两者,的关系，只好将相关的序偶选出来。,R3=,3.6,、关系,将笛卡尔积中,前后两个元素,之间存在,某种关系,的,序偶,检出来,便得到一个,关系,。,定义,3.6.2,如果,序偶,或,元组,属于某个关系,R,，则称序偶或元组,具有关系,R,。,若序偶,R,，还可写成,x,R,y,，,将关系名称写在二个元素之间，,其他数学也是这样表示，如,24,，,2|4,，,2=2,如,R,，可可写成,2R4,如,R,2,，可写成,2R,2,4,也有人认为，这种写法不直观，可能产生歧义，本课程尽量回避这种写法。,3.6,关系的描述,A,B,=1,2,3a,b,c=,R1=,前后两个元素的序号一样,=,除给出关系中所包含的序偶外，还可用,关系矩阵,、,关系图,表示。,1,2,3,a,b,c,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=,序偶前后元素均是,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,GAxA A,上的关系,设,F,G,为二元关系,G,对,F,的右复合记为,FG,定义,FG=|t(F,G),如,F=,G=,FG=,M(FG)=M(F)M(G),可用关系矩阵相乘,/,关系图表示,1,2,3,1,2,3,A=1,2,3,F,AxA,GAxA,A,上的关系,F,=,G,=,1,2,3,1,2,3,1,2,3,1,2,3,3.7,、,关系复合,M,F,的第,i,行与,M,G,的第,j,列相乘时，,乘法是,合取,，加法是,析取,，,如,M,F,1,行与,M,G,3,列相乘,(11)(10)(00),，结果为,1,。,定义,3.7.2,称,|F,为,F,的逆，记为,F,-1,令,A=1,2,3,，,F=,。,则,F,-1,=,性质,：,(1),结合律,(PR)S=P(RS),(2),复合的逆,(PR),-1,=R,-1,P,-1,3.8,、,关系的性质与分类,自反关系,:,若关系,R,前后二个元素来自同一个集合,A,若,xA,都有,R,则,R,是自反的,.,反自反关系,:,若关系,R,前后二个元素来自同一个集合,A,若,xA,都有,R,则,R,是反自反的,.,如,:A=1,2,3,R1=,因为,R1,不是自反的,因为,R1,R1,故不是反自反的,.,R2=,自反的,!,R3=,反自反的,!,3.8,、,关系的性质与分类,自反关系,:,若,xA,有,R,则自反的,.,主对全,1,反自反关系,:,若,xA,有,R,则,R,反自反,主对全,0,如,:A=1,2,3,R1=,自反的,!,R2=,反自反,!,R3=,不是自反,不是反自反,.,3,2,1,3,2,1,3,2,1,自反,自反,反自反,反自反,3.8,、,关系的性质与分类,自反关系,:,若,xA,有,R,则自反的,.,主对全,1,反自反关系,:,若,xA,有,R,则,R,反自反,主对全,0,定义,3.8.3,若关系,R=AA,，则称为全域关系，记为,E,A,.,在全域关系中，由于直积的每个序偶都在关系,R,中，所以其关系矩阵全是,1,，,主对角线肯定也为,1,，故是自反关系。,定义,3.8.4,若所有形如,的序偶都在关系,R,中，,R,也只有这种形式的序偶，则称,R,为恒等关系，记为,I,A,。,若,R,是自反关系，则恒等关系,I,A,R,如,A=1,2,3,则,I,A,=,3.8,、,关系的分类,自反关系,:,若,xA,都有,R,反自反关系,:,若,xA,有,R,对称关系,:,若,R,有,R,反对称关系,:,若,R,Rx,=y,也可：,若,R,且,xy,R,则反对称,如,:A=1,2,3,R1=,对称,R2=,反对称,R3=,因,R1,不对称,因,与,成对出现,而,不是,反对称,3.8,、,关系的分类,1-2,班,对称关系,:,若,R,有,R,非对角成对,反对称关系,:,若,R,且,xy,R,如,:A=1,2,3 R1=,对称,R2=,反对称,R3=,3,2,1,3,2,1,3,2,1,3.8,、,关系的分类,对称关系,:,若,R,有,R,非对角成对,反对称关系,:,若,R,Rx,=y,2,个定义等价,若,R,且,xy,R,(,Rxy,)R,(,Rxy,)R,条件式的等值式,R,xy,R,德摩律,R x=yR,的含义,(R,R)x,=y,结合律,(R,R)x,=y,德摩律,(RR)x=y,条件式的等值式,3.8,、,关系的性质与分类,传递关系,:,若,R,R,R,表示两个序偶的复合仍在,R,中,即,RRR,M,2,M,A=,a,b,c,R=,R,R=,=,R,学会看图,a,b,c,d,R,R,RR,3.8,、,关系的性质与分类,传递关系,:,若,R,R,R,表示复合仍在,R,中,即,RRR,M,2,M,如,A=1,2,3,R,1,=,R,1,R,1,=,=,R,故可传递,复合边,已在图中，或,传递可达,的二点有边,直连,.,1,2,3,3.8,、,关系的性质与分类,传递关系,:,若,R,R,R,表示复合仍在,R,中,即,RRR,M,2,M,如,A=1,2,3,R2=,传递的产生的,R,故,不是,复合边,已在图中，或,传递可达,的二点有边,直连,.,1,2,3,3.8,、,关系的性质与分类,传递关系,:,若,R,R,R,表示两个序偶的复合仍在,R,中,即,RRR,M,2,M,如,A=1,2,3,R,1,=,可传递,的，,OK,R,1,R1=R,1,R,1,故为可传递！,1,2,3,3.8,、,关系的性质与分类,自反关系,:,xA,R,I,A,R,反自反关系,:,xA,R,I,A,R=,对称关系,:,R R,R=R,-1,反对称关系,:,R,Rx,=y,R,且,xy,R,RR,-1,I,A,传递关系,:,R,R,R,R,2,R,自反,:,主对角线均为,1,反自反,:,主对角线均为,0,对称,:M=M,T,。,反对称,：,MM,T,后只有主对角非,0,传递,:R,2,R,即,M,2,M,3.9,、,关系的闭包：加点序偶使之成某种类型,1,、,R,自反闭包,r(R,),：,加序偶使之成自反的。,R=,不是自反,r(R,)=,r(R,)=RI,A,3,2,1,3,2,1,3.9,、,关系的闭包：加点序偶使之成某种类型,2,、,R,对称闭包,s(R,),：,加序偶使之成对称的。,R=,反对称,s(R,)=,对称,s(R,)=RR,T,.,3,2,1,3,2,1,3.9,、,关系的闭包,A=,a,b,c,d,，,R=,，,求其传递闭包,解：先求,R,2,，若,R,2,R,则,R,是传递关系，即,不添,序偶就得传递关系，传递闭包就是,R,。,若,R,2,R,，表示复合产生的序偶不在,R,中，为了可传递，故将复合出来的序偶投入到,R,中即得到,R,2,R,。新序偶与旧序偶又复合出二代新序偶。,若二代新序偶已在,R,2,R,中，则,R,2,R,已是可传递关系，则它就是传递闭包，即,t(R,)=R,2,R,。,否则将二代新序偶放入,R,中，得到,R,3,R,2,R,。,重复以上过程，直到得到一个传递关系。,例,A=,a,b,c,d,R=,R,2,=,R,3,=,=,t(R,)=,结点,u,出发经过,2,条边到达,v,若,u,与,v,有边相连则可传递,当集合,A,有,n,结点时,从,u,出发，若结点不重复，最多可经过其他,n-1,结点，最多可依次跨越,n-1,条不同的边，,故以上重复过程，最多经过,n-1,轮，最多求到,R,n-1,。,例,A=,a,b,c,d,R=,R,2,=,R,3,=,=,t(R,)=,由关系的复合可知，,R,R,R=R,2,R,3,R,n-1,可由关系矩阵的积来实现。,RR,2,R,3,R,n-1,将剔除,重复出现,的序偶,因此可由矩阵幂次方的析取,M,R,(M,R,),2,(M,R,),n-1,实现,即,t(R,)=M,R,(M,R,),2,(M,R,),n-1,。,t(R,)=,RR,2,R,3,.R,n-1,.,任何两点最多,n-1,步达,=,M M,2,M,3,.M,n-1,.,例,A=,a,b,c,d,R=,t(R,)=,a,b,c,d,t(R,)=,RR,2,R,3,.R,n-1,.,任何两点最多,n-1,步达,=,M M,2,M,3,.M,n-1,.,效率比较低！,Warshall,算法,for(j=1;j,n;j,+),/,第,1,列到最后列,for(i,=1;i,n;i,+,/,第,j,列从第,1,行到最后行,if(,M(i,j,)=1),第,i,行,=,第,i,行,第,j,行,;,3.9,、,关系的闭包：加点序偶使之成某种类型,1,、,R,自反闭包,r(R,),的定义：,(1)r(R),自反,;,(2)R,r(R),;,(3)RR,R,自反,r(R)R,最小性,恰好增加到变成自反为止。,2,、,R,对称闭包,s(R,),的定义：,(1)s(R),对称,;,(2)R,s(R),;,(3)RR,R,对称,s(R)R,最小性,3,、,R,传递闭包,t(R,),的定义：,(1)t(R),传递,;,(2)R,t(R),;,(3)RR,R,传递,t(R)R,最小性,利用求闭包方法也可判断关系性质,3.10,、等价关系、等价类、分类,(,划分,),自反,、,对称,、,可传递,的关系称为等价关系。,例,A=1,2,3,4,5,6,7,8,R,=,=,|,x-y,=3k,判断,:,是否为,等价关系,(1),xA,因,x-x,=0=3*0,，故,R,，,故自反,(2),R,x-y,=3k,y-x,=3(-k),R,(3)R,R,x-y,=3k,y-z=3m,x-z,=3(k+m),R,3.10,、等价关系、等价类、分类,(,划分,),例,A=1,2,3,4,5,6,7,8,R,=,彼此有等价关系的元素的集合,称为,等价类,.,如：上述关系,R,的序偶分成,3,类,=,等价类有：,1,4,7,，,2,5,8,，,3,6,简记为,1=4=7,这显然对集合,A,的元素进行了划分！,3.10,、等价关系、等价类、分类,(,划分,),设,RAA,，,R,是,等价关系,，,A,0,A,1,A,k,是基于,R,得到的,等价类,，则称,集合,A,0,A,1,A,k,为,A,关于,R,的,商集,，记为,A/R,。,例,A=1,2,3,4,5,6,7,8,R,=,=,A/R=A,0,A,1,A,2,=1,4,7,2,5,8,3,6,划分,:,若,A=A,0,A,1,A,k,且不相交,则称,A,的划分,例,A=1,2,3,4,5,6,7,8,R,=,因为等价类,1,4,7,2,5,8,3,6,彼此,不相交,，,并集,为,A,，称为,A,的划分,因此等价关系可划分集合,。,定理 设,RAA,，,R,是等价关系，,A,0,A,1,A,k-1,是利用,R,得到的,k,个不同的等价类，则,A,0,A,1,A,k,为集合,A,的划分,3.10,、等价关系、等价类、分类（划分）,划分,:,若,A=A,0,A,1,A,k,且不相交,则称,A,的划分,定理,设,RAA,，,R,是等价关系，,A,0,A,1,A,k-1,是利用,R,得到的,k,个不同的等价类，则,A,0,A,1,A,k,为集合,A,的划分,(1),当,ij,时假设,AiAj,。则,xAiAj,可知,xAi,，,xAj,，,对,Ai,中任意元,y,，由等价类定义知,R,，,对,Aj,中任意元素,z,，也有,R,。,因,R,是等价关系及,R,可知,R,同理,R,，,所以,R,，即二者的任意组合构成的序偶都在,R,中，根据等价类的定义,y,与,z,在同一个等价类中，即,Ai=Aj,，与前提矛盾，故假设错。只能,AiAj=,。,(2)xA,，若,x,与其他所有元素都没有关系，则单个,x,构成一个等价类。若,x,与有其他元素有等价关系,R,，则与他们处于一等价类,.,总之,x,至少属于一个等价类,Ai,，所以,xA,0,A,1,A,k-1,，所以,AA,0,A,1,A,k-1,。又由等价类的定义可知,AjA,，,故,A,0,A,1,A,k-1,A,，故,A=A,0,A,1,A,k-1,。,3.10,、等价关系、等价类、分类（划分）,划分,:,若,A=A,0,A,1,A,k,且不相交,则称,A,的划分,例,A=1,2,3,4,5,6,7,8,R,=,因为等价类,1,4,7,2,5,8,3,6,彼此,不相交,，,并集,为,A,，称为,A,的划分,因此等价关系可划分集合,。,(1),观察关系中的序偶可得到划分,(2,),观察关系图也可得到划分,3.10,、等价关系、等价类、分类（划分）,3.10,、等价关系、等价类、分类,(,划分,),自反,、,对称,、,可传递,的关系称为等价关系。,例,A=1,2,3,4,5,6,7,8,R=,=,1,4,7,x,1,4,7,2,5,8,x,2,5,8,3,6x3,6,由,等价关系,找出,划分,1,4,7,2,5,8,3,6,.,反过来，由,划分,构造,等价关系,吗？,3.10,、等价关系、等价类、分类,(,划分,),R,=A,1,A,1,A,2,A,2,A,3,A,3,R=,1,4,7,x,1,4,7,2,5,8,x,2,5,8,3,6x3,6,可验证,R,是等价关系,!,再如,A,的划分,:A,1,=1,2,3,A,2,=4,5,6,A,3,=7,8,，则,R=A,1,A,1,A,2,A,2,A,3,A,3,=,R,是对称、自反、可传递的等价关系。,3.10,、等价关系、等价类、分类,(,划分,),定理,3.10.2,设,A0,A,1,A,k-1,是,A,的划分，,R=A,0,A,0,A,1,A,1,A,k-1,A,k-1,，则,R,等价关系。,(1),xA,，由划分的定义可知，,x,肯定属于某个子集,Ai,，所以,AiAi,，故,R,自反,。,(2),若,R,，则,至少属于某个子集,Ai,的直积,(,如果,不属于任何,Ai,的直积则不属于,R),，即,AiAi,，由于,Ai,的直积是,对,称的，故,AiAiR,故,R,对称,。,(3),若,AiAi,则,AiAi,。假设,A,j,A,j,，其中,ij,。由,A,i,A,i,有,xA,i,yA,i,，由,A,j,A,j,有,yA,j,zA,j,，故,yAi,又,yAj,这不可能，故假设错，只能,AiAi,。,因,A,i,直积可传递，故,AiAiR,，故,R,可传递。,3.11,、偏序关系,1,、自反、反对称、可传递,的关系。,例题,设,A=,实数集，,R,是实数中小于等于关系，即,R=|x,y,是实数，,且,xy,，则,R,是偏序关系。,(1)xA(,实数,),有,xx,，故,R,，即为,自反,关系。,(2),若,R,R,，则,xy,且,yx,故,x=y,故,反对,称,(3),若,R,R,，则,xy,且,yz,，故,xz,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,故,可传递,偏序关系可,理解,为广义的“小于等于”关系，记为,。,3.11,、偏序关系,1,、自反、反对称、可传递,的关系。可,理解,为广义的“小于等于”关系，记为,。,2,、当,时，写成,x,y,，主要为了直观。,3,、当,但,xy,时，记成,xy,即,严格小于,。,4,、,x,yA,x,与,y,可比,是指,或,，即,xy,或,yx,。,例题,：,A=1,2,3,4,5,6 R=,:,x|y,R=,R,，可记为,12,也可,12,R,，可记为,22,不可,22,2,与,4,可比,，因为,R,即,24,可比与不可比,4,与,2,可比,，因为,R,即,24,2,与,5,不可比,，因为,R,R,3.11,、偏序关系,1),自反、反对称、可传递,的关系。广义的“小于等于”关系，记为,。,2,),当,时，写成,x,y,，主要为了直观。,3,),当,但,xy,时，记成,xy,即,严格小于,。,4,)x,yA,x,与,y,可比,是指,或,。,5,),全序,(,线序,):,x,yA,，,x,与,y,都可比,。,如,A,=1,2,3,4,5,6 R=,:,xy,狭义,关系图中所有点在一条线上！,B=1,2,A=,1,2,R=:,xy,xA,yA,即,x,与,y,是,B,的子集。,全序,B=1,2,A=,1,2,1,2,R=:,xy,xA,yA,即,x,与,y,是,B,的子集。,偏序,a,b,3.11,、偏序关系,1),自反、反对称、可传递,的关系。,2,),当,时，写成,x,y,，主要为了直观。,3,),当,但,xy,时，记成,xy,即,严格小于,。,4,)x,yA,x,与,y,可比,是指,或,。,5,),全序,(,线序,):,x,yA,，,x,与,y,都可比,。,6),偏序集,：,。,A=1,2,3,4,5,6 R=:,xy,B=1,2,A=,1,2,1,2,R,1,=:,xy,xA,yA,B=1,2,A=,1,2,R,2,=:,xy,xA,yA,3.11,、偏序关系,7),哈斯图,因箭头都朝上方，故箭头不画。,因每个结点,都有,自旋箭头，故不画自旋。,因可传递即,复合边均,在其中，故将传递可达的二点间的,直达,边去掉。,这样得到的图为,哈斯图,。,1,2,1,2,1,2,1,2,1,2,1,2,3.11,、偏序关系,因箭头都朝上方，故箭头不画。,因每个结点,都有,自旋箭头，故不画自旋。,因可传递即,复合边均,在其中，故将传递可达的二点间的,直达,边去掉。,这样得到的图为,哈斯图,。,3.11,、偏序关系,2,),当,时，写成,x,y,，主要为了直观。,4,)x,yA,x,与,y,可比,是指,或,。,6),偏序集,：,。,8),盖住,:,xA,yA,x,y,z,A,使得,xzy,则称,y,盖住,x.,在,x,的上方最近者。,B=1,2,A=,1,2,1,2,R,1,=:,xy,xA,y,A,1,盖住,2,盖住,但,1,2,并不盖住,.,1,2,1,2,3.11,、偏序关系,-,最大元,/,最小元,9),最大元,:,设,是偏序集，,BA,y,0,B,若,xB,均有,R,，则,y,0,是,B,的最大元。,y0,与,B,每个,元素,x,有关系,R,即,可比,，且,比其大,。,最小元类似定义,a,b,c,g,d,f,e,h,1,2,3,5,7,4,8,6,9,B=,a,b,c,d,e,f,g,h,最大最小无,B=18,有最小,B=1,2,4,8,有最大与最小,B=,b,c,d,e,f,最大有,3.11,、偏序关系,-,极大元,/,极小元,9),最大元,:,设,是偏序集，,BA,y,0,B,若,xB,均有,R,，则,y,0,是,B,的最大元。,y0,与,B,每个,元素,x,有关系,R,即,可比,，且,比其大,。,10),极大元,:,不存在,x,使,R.,哈图无元居其,上,极小元,:,不存在,x,使,R.,哈图无元居其,下,a,b,c,g,d,f,e,h,1,2,3,5,7,4,8,6,9,极大元,a,f,h,极小 元,a,b,c,g,极大元,8,6,9,7,极小元,1,3.11,、偏序关系,-,极大元,/,极小元,10),极大元,:,不存在,x,使,R.,哈图无元居其,上,极小元,:,不存在,x,使,R.,哈图无元居其,下,11,),上界,:,在偏序集,中，,BA,，,yA,，若任意,xB,都有,R,，则称,y,是,B,的,上界,。,与,B,中每个元素都可比，并且都,B,中的元素大,a,b,c,g,d,f,e,h,1,2,3,5,7,4,8,6,9,b,c,上界,f,d,e,1,2,的上界,2,4,6,8,3.11,、偏序关系,-,极大元,/,极小元,11,),上界,:,在偏序集,中，,BA,，,yA,，若任意,xB,都有,R,，则称,y,是,B,的,上界,。,12),下界,:,在偏序集,中，,BA,，,yA,，若任意,xB,都有,R,，则称,y,是,B,的下界。,与,B,中每个元素都可比，并且都,B,中的,元素小,a,b,c,g,d,f,e,h,1,2,3,5,7,4,8,6,9,f,d,e,下界,b,c,8,4,6,2,下界,1,2,3.11,、偏序关系,-,极大元,/,极小元,11,),上界,:,在偏序集,中，,BA,，,yA,，若任意,xB,都有,R,，则称,y,是,B,的,上界,。,与,B,中每个元素都可比，并且都,B,中的元素大,13),上确界,:,在偏序集,中，,BA,，设,C,为,B,的,所有上界,元的集合，若,C,中有,最小元,则该最小元称为,B,的,上确界,a,b,c,g,d,f,e,h,1,2,3,5,7,4,8,6,9,b,c,上界,f,d,e,无,最小元,1,2,的上界,2,4,6,8,最小元,2,3.11,、偏序关系,-,极大元,/,极小元,12),下界,:,在偏序集,中，,BA,，,yA,，若任意,xB,都有,R,，则称,y,是,B,的下界。,14),下确界,:,在偏序集,中，,BA,，设,C,为,B,的所有,下界元,的集合，若,C,中有最大元则该最大元为,B,的,下确界,a,b,c,g,d,f,e,h,1,2,3,5,7,4,8,6,9,f,d,e,下界,b,c,无,最大元,8,4,6,2,下界,1,2,最大元,2,