离散数学-第4章-7省名师优质课赛课获奖课件市赛课一等奖课件.ppt

DSPST,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,DSPST,research,宁波大学数字技术与软件应用研究所,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,DSPST,DSPST,research,宁波大学数字技术与软件应用研究所,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,1,离散数学,Discrete Mathematics,汪荣贵 教授,合肥工业大学软件学院专用课件,.03,1/87,学习内容,4.1,集合基本知识,4.2,序偶与笛卡尔积,4.3,关系及其性质,4.4 n,元关系及其应用,4.5,关系闭包,4.6,等价关系,4.7,偏序,2/87,偏序,一、偏序,定义1,：,集合,S,上关系,R,，假如它是自反、反对称,和传递，就称为,偏序,。,集合,S,与偏序,R,一起叫做,偏序集,，记作（,S,R,）,.,比如数值,、关系和集合,都是偏序关系。,3/87,【example 1】,证实“大于或等于”关系（,）是整数集合上,偏序。,solution,：,因为对全部整数,a,，有,a,a,，是自反。,假如,a,b,且,b,a,，那么,a=b,，所以是反对称。,最终，因为,a,b,和,b,c,，所以是传递。,从而是整数集合上偏序且（,Z,）是偏序集。,4/87,【example 2】,整除关系“,|”,是正整数集合上偏序，因为由前,几节所述，它是自反、反对称和传递。我们看到,（,Z,+,|,）是偏序集（,Z,+,表示正整数集合）。,5/87,【example 3】,证实包含关系,是集合,S,幂集上偏序。,Solution,：,因为只要,A,是,S,子集，就有,A,A,是自反。,因为,A,B,和,B,A,推出,A=B,，所以它是反对称。,最终，因为,A,B,和,B,C,推出,A,B,是传递。,所以，是,P(S),上偏序，且（,P(S),，）是偏序集。,6/87,在任意一个偏序集中记号,a,b,表示,(a,，,b),R.,使用这个记号,是因为“小于或等于”关系是偏序关系范例。,注意：,符号,表示任意偏序关系，并不但仅是“小于或等于”关系。,记号,ab表示,a,b,但,ab.,假如,ab,我们说“,a,小于,b”,或,“,b,大于,a”,。,当,a,与,b,是偏序集（,S,）元素时，不一定有,a,b,或,b,c,。,比如，在（,P(Z),）中,1,2,与,1,3,没相关系，反之亦然，因为,没有一个集合被另一个集合包含。类似地在,(Z,|),中，,2,与,3,没关系，,3,与,2,也没关系。由此得到定义,2.,7/87,定义,2,：偏序集,(S,),元素,a,和,b,叫做,可比,，假如,a,b,或,b,a,。当,a,和,b,是,S,元素而且既没有,a,b,，也没,有,b,a,，则称,a,与,b,是,不可比,。,【,example 4】,在偏序集,(Z,+,),中，整数,3,和,9,是可比吗？,5,和,7,是可比吗？,整数,3,和,9,是可比，因为,3|9.,整数,5,和,7,是不可比，因为,5,不能整除,7,，而且,7,也不能整除,5.,8/87,用形容词“部分（偏）”描述偏序是因为一些对元素可能是不可比。当集合中每对元素都可比时，这个关系叫做,全序,。,定义,3,：,假如,(S,),是偏序集，且,S,每对元素都是可比，则,S,叫做,全序集,或,线序集,，且 叫做,全序,或,线序,。一个全序集也叫做,链,。,9/87,【example 5】,偏序集,(Z,),是全序集，因为只要,a,和,b,是整数,，就有,a b,或,b a,。example 6】,偏序集,(Z,+,|),不是全序集，因为它包含着不可比元素，比如,5,和,7.,10/87,定义,4,：,对于偏序集,(S,),，假如是全序，而且,S,每,个非空子集都有一个最小元素，就称它为,良序集,。,For example,，,N,是自然数集合，,I,是整数集合，,是小于等于关系，,就是,良序集。而,不是良序集。,11/87,定理,全部,良序集，一定是全序集。,Proof,：,设,为良序集,任取,x,y,A,则,x,y A,它有最小,元素。该最小元素或是,x,或是,y,。,于是有,x y,或,y x,，,所以,是全序集。,12/87,定理,有限,全序集，一定是良序集。,Proof,：,设,A=a,1,a,2,，,a,n,是全序集。,假设它不是良序，必存在非空子集,BA,，,B,中无最小元素，,因,B,是有限集，必存在,x,y B,使得,x,与,y,之间不满足关系,与,是全序矛盾。,是良序集。,13/87,【example 7】,正整数有序正确集合,Z,+,Z,+,与组成,良序集，对于,(a,1,a,2,),和,(b,1,b,2,),假如,a,1,b,1,或假如,a,1,=b,1,且,a,2,b,2,（字典次序），则,(a,1,a,2,),(b,1,b,2,).,14/87,在前几章学习中我们现实了怎样使用良序归纳标准证实关于一个良序集结果。现在我们叙述并证实这个证实技术是有效。,定理,1,良序归纳原理,设,S,是一个良序集，假如下述条件成立：,基础步,：,P(x,0,),对,S,最小元素为真，且,归纳步,:,对一切,y S,假如,P(x),对全部,x,y,为真，则,P(y),为,真。那么,P(x),对全部,x S,为真。,15/87,proof,：,假若,P(x),不对全部,x S,为真。那么存在一个元素,y S,使,得,P(y),为假。于是集合,A=x S|P(x),为假,是非空。,因为,S,是良序，集合,A,有最小元素,a.,易知,a,不等于,x,0,因为从,基础步知道,P(x,0,),为真。,依据,a,是选自,A,最小元素，我们知道对全部,x S(x,a,),都,有,P(x),为真。由归纳步这就能够退出,P(a),为真。,这个矛盾就证实了,P(x),必须对全部,x S,为真。,16/87,二、字典次序,字典次序,是以字母表中字母次序为基础。这是从一个集合上偏序结构一个集合上串序特殊情况。我们将说明这种结构在任一个偏序集上是怎么做。,17/87,首先，我们将说明怎样在两个偏序集,(A,1,1,),和,(A,2,2,),笛,卡尔积上结构一个偏序。,在,A,1,A,2,上字典次序定义以下：假如第一个正确第一个,元素（在,A,1,中）小于第二个正确第一个元素，或者第一个元,素相等，不过第一个正确第二个元素（在,A,2,中）小于第二个,正确第二个元素，那么第一个对小于第二个对。换句话说，,(a,1,a,2,),小于,(b,1,b,2,),即,(a,1,a,2,),(b,1,b,2,),或者,a,1,1,b,1,或者,a,1,=b,1,且,a,2,2,b,2,.,把相等加到,A,1,A,2,上序就得到偏序,。,18/87,【example 8】,确定在偏序集（,ZZ,，）中是否有,(3,5),(4,8),(3,8)(4,5),和,(4,9)(4,11)?,这里,是从,Z,上通常,关系结构字典次序。,Solution,：,因为,34,故而,(3,5),(4,8),且,(3,8)(4,5),。因为,(4,9),与,(4,11),第一元素相同，但,911,我们有,(4,9)(4,11),。,下列图显著地显示了,Z,+,Z,+,中比,(3,4),小有序正确集合。,19/87,20/87,能够在,n,个偏序集,(A,1,1,),(A,2,2,),(A,n,n,),笛卡尔,积上定义字典次序。,以下定义,A,1,A,2,A,n,上偏序 ：假如,a,1,0,是,a,1,=b,1,a,i,=b,i,且,a,i+1,i+1,b,i+1,那么,(a,1,a,2,a,n,)(b,1,b,2,b,n,),换句话说，假如在两个,n,元组不一样元素出现第一位置上等,一个,n,元组元素小于第二个,n,元组元素，那么第一个,n,元组小,于第二个,n,元组。,21/87,【example 9】,注意（,1,，,2,，,3,，,5,）,（,1,，,2,，,4,，,3,），因为这,些,4,元组前两位相同，不过第一个,4,元组第三位,3,小于第二个,4,元组第三位,4,（这里,4,元组上字典次序是整数集合上通,常“小于或等于”关系导出字典次序）。,22/87,我们现在能够定义串上字典次序。考虑偏序集,S,上串,a,1,a,2,a,n,和,b,1,b,2,b,n,假定这些串不相等。设,t,是,m,，,n,中较小数。,定义字典次序以下：,a,1,a,2,a,n,小于,b,1,b,2,b,n,当且仅当,（,a,1,a,2,a,t,）,（,b,1b,2,b,t,）或者,（,a,1,a,2,a,t,）,=,（,b,1,b,2,b,t,）而且,mn,其中这个不等式中,表示,S,t,中字典次序。换句话说，为确定两,个不一样串序，较长串被切到较短串长度,t,，即,t=min(m,n),然,后使用,S,t,上字典次序比较每个船前,t,为组成,t,元组，假如对应于,第一个串,t,元组小于第二个串,t,元组，或者这两个,t,元组相等，不过,第二个串更长，那么第一个串小于第二个串。,23/87,【example 10】,考虑小写英语字母串组成集合。使用在字母表中字母序，能够组成在串集合上字典次序。,假如两个串第一次出现不一样字母时，第一个串字母先于第二个字母，或者假如第一个串和第二个串在全部位都相同，不过第二个串有更多字母，那么，第一个串小于第二个串。这种排序和字典使用排序相同。比如,discreet discrete,因为这两个串在第,7,位首次出现字母，而且,e t.,discreet discreetness,因为这两个串前,8,个字母相同，不过第二个串更长。另外,discrete discretion,24/87,在有穷偏序集有向图中有许多能够无须显示出来，因为他们是必须存在。,比如，考虑在集合,1,，,2,，,3,，,4,上偏序,(a,b)|a,b,有向图，参见图,a,。因为这个关系是偏序，它是自反而且有向图在全部顶点都有环，所以，我们无须显示这些环，因为它们是必须出现。在图,b,中没有显示这些环。因为一个偏序是传递，我们无须显示那些因为传递性而必须出现边。比如，在图,c,中没有显示边,(1,3),(1,4),和,(2,4),，因为它们是必须出现。假如假设全部边方向是向上，我们无须显示边方向；图,c,没有显示方向。,三、哈塞图（,Hasse,图）,25/87,26/87,我们能够使用下面过程表示一个有穷集上偏序。,从这个关系有向图开始：,(1),自反性：每个顶点都有自回路，省去。,(2),反对称性：两个顶点间只可能有一个箭头从左 右，或从下上方向从小到大安置顶点，可省略箭头。,(3),传递性：因为有,(a,b),，b,c)R,则,(a,c)R,故只画,(a,b),，,(b,c),对应边,省略边,(a,c),。,完成以上步骤就得到一个包含着足够表示偏序信息图，这个,图叫作,哈塞图,27/87,哈塞图（,Hasse,图）,定义：,设,是上一个偏序关系，假如,a,b,，则将画在,下面，且不,，使,a,c,，,c,b,，则，间用直线连,接。并符合简化关系图绘制，称这么得到关系图为,哈塞图（,Hasse,图）,。,28/87,29,2025/3/31 周一,【example 11】,画出表示,1,，,2,，,3,，,4,，,6,，,8,，,12,上偏序,(a,b)|a,整除,b,哈塞图。,Solution,：由这个偏序有向图开始，以下列图,a,所表示。移走全部环，,以下列图,b,所表示，然后删去全部由传递性导出边。这些边是,(1,4),(1,6),(1,8),(1,12),(2,8),(3,12).,排列全部边使得方向向上,，而且删除全部箭头得到哈塞图。结果如图,c,所表示。,29/87,30/87,【example 12】,画出幂集,P(S),上偏序,(A,B)|A,B,哈塞,图，其中,S=a,b,c.,Solution:,关于这个偏序哈塞图是由相关有向图得到，先删除所,有环和全部由传递性产生边，即,(,a,b,),(,a,c,),(,b,c,),(,a,b,c,),(,a,a,b,c,),(b,a,b,c),和,(c,a,b,c).,最终，使全部边方向向上并删除箭头。得到哈塞图以下所,示。,31/87,32/87,【example】,：,，,，,1,（，），,2,（，）,|,，,3,(s1,s2),s1,s2,，,s1,，,s2p(B),求,R,1,R,2,R,3,所表示关系哈塞图。,33/87,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,a,b,c,a,b,a,c,a,c,a,b,c,34/87,含有极值性质偏序集元素有许多主要应用。,偏序集一个元素叫做极大，当它大于这个偏序集任何其它元素。即,a,在偏序集,（,S,，,）中是,极大,，当不存在,b,S,使得,ab.,类似地，偏序集一个元素叫做极小，假如它小于这个偏序集任何其它元素。即,a,在偏序集（,S,，,）中是,极小,，假如不存在,b,S,使得,ba,。,使用哈塞图很轻易是识别极大元素和极小元素。它们是图中“顶”元素与“底”元素。,四、极大元素与极小元素,35/87,定义,极大元与极小元：,设（,S,，,）是偏序集，若,S,，且在,S,中找不到一个,元素,b,（,ba,），使,a,b,（,b,a,），则称,a,为,A,中,极大元素,（极小元素）。,y,是,B,极小元素,y(y B x(x B x y x y),y,是,B,极大元素,y(y B x(x B x y y x),36/87example】,（,N,，,|,）,是偏序集，,A=,2,，,3,，,4,，,5,，,6,，,7,，,8,，,9,则,中极大元素：，,极小元素：，,注：,极大元，极小元并不要求唯一，且同一元素，能够既是极大元，又是极小元，如，。,极大元，极小元必须是子集中元素。,2,3,5,7,6,4,8,9,37/87,【example 13】,偏序集（,2,，,4,，,5,，,10,，,12,，,20,，,25,，,|,）,哪些元素时极大，哪些是极小？,Solution,：,右图关于这个偏序集哈塞图,显示了极大元素是,12,，,20,和,25,，,极小元素时,2,和,5,。,经过这个例子能够看出，一个偏序集能够有多于一个极大元素和,多于一个极小元素。,38/87,在偏序集中存在一个元素大于每个其它元素，这么元素叫做最大元素，即,a,是偏序集（,S,，）,最大元素,，当对全部,b,S,有,b,a,。当最大元素存在时它是唯一。,类似地，一个元素叫做最小元素，当它小于偏序集全部其它元素。即,a,是偏序集（,S,，）,最小元素,，假如对全部,b,S,有,a,b,。当最小元素存在时它也是唯一。,39/87,40,2025/3/31 周一,定义,最大元素与最小元素：,设（,S,，,）是偏序集，若，,，,(,），则称为,最大元素（最小元素）,。,【example】,上例中其,Hasse,图以下列图所表示,2,3,5,7,6,4,8,9,结论：,子集中是不存在最大元（最小元）。,40/87,定理,是偏序集，,B,是,A,非空子集，假如,B,有最小元素,(,最大元素,),，则最小元素,(,最大元素,),是唯一。,proof,：,假设,B,有两个最小元素,a,、,b,则 因为,a,是,最小元素，,b,B,，,依据,最小元素定义，有,a,b;,类似地，因为,b,是,最小元素，,a,B,，依据,最小元素定义，有,b,a,。因为有反对称性，所以有,a=b,。,同理可证,最大元素唯一性。,41/87,小结：,是偏序集，,B,是,A,非空子集，则,B,极小,(,大,),元素总是存在，就是子集中处于最下,(上,),层元素是极小,(,大,),元素。,B,最小元,(,最大元,),素有时可能不存在，只要有唯一极小,(,大,),元素，则这个极小,(,大,),元素就是最小,(,大,),元素。不然就没有最小,(,大,),元素。,42/87,【example 14】,确定下列图每个哈塞图表示偏序集是否有最,大元素和最小元素。,43/87,Solution,：,哈塞图,(a),偏序集最小元素时,a,。这个偏序集没有最大元,素。,哈塞图,(b),偏序集既没有最大元素也没有最小元素。,哈塞图,(c),偏序集没有最小元素，它最大元素时,d,。,哈塞图,(d),偏序集有最小元素,a,和最大元素,d,。,44/87,【example15】,设,S,是集合。确定偏序集（,P(S),）中是否存在最大元素与最小元素。,Solution,：,最小元素时空集。因为对于,S,任何子集,T,有,T,，集合,S,是,这个偏序集最大元素，因为只要,T,是,S,子集，就有,T S,。,45/87,46,2025/3/31 周一,【example 16】,在偏序集（,Z,+,|,）中是否存在最大元素和,最小元素？,Solution,：,1,是最小元素，因为只要,n,是正整数，就有,1|n,。因为没,有被全部正整数整除整数，所以不存在最大元素。,46/87,47,2025/3/31 周一,有时能够找到一个元素大于偏序集（,S,，）子集,A,中全部元素。假如,u,是,S,元素使得对全部元素,a,A,有,a,u,，那么,u,叫做,A,一个上界,。,也可能存在一个元素小于,A,中全部其它元素。假如,l,是,S,一个元素使得对全部元素,a,A,有,l,a,，那么,l,叫做,A,一个下界,。,47/87,定义,上界与下界：,设（,P,）是半序集，,A,P,，若,aP,，对,bA,b,a,（,a,b,）称,a,为,A,上界（下界）,。,【example】,：,B=a,b,c,R,3,=(s,1,s,2,)|s,1,s,2,，,s,1,P(B),(P(B),),是偏序集。,设,，,a,b,c,a,c,a,b,a,c,其,Hasse,图如右图所表示,:,a,b,c,a,b,a,c,b,c,48/87,注：,（,1,）上例中，无最大元素，但存在上界,，。,（,2,）,为最小元，也是下界。,（,3,）最大（小）元素是一个上（下）界。,（,4,）上（下）界能够不唯一，也能够不存在。,49/87,【example 17】,找出下列图所表示哈塞图偏序集子集,a,b,c,j,h,和,a,，,c,，,d,，,f,下界和上界。,50/87,Solution,：,a,，,b,，,c,上界是,e,f,j,和,h,，它唯一下界是,a,。,j,，,h,没有上界，它下界是,a,，,b,，,c,，,d,，,e,和,f.,a,c,d,f,上界是,f,，h,和,j,，它下界是,a,。,51/87,元素,x,叫做子集,A,最小上界（上确界）,，假如,x,是一个上界而且它小于,A,其它上界。因为假如这么元素存在，只存在一个，称这个元素为最小上界（上确界）是有意义。即假如只要,aA,就有,a,x,，而且只要,z,是,A,上界，就有,x,z,x,就是,A,最小上界（上确界）。,类似地，假如,y,是,A,下界，而且只要,z,是,A,下界，就有,z,y,，,y,就是,A,最大下界（下确界）,。,A,最大下界（下确界）假如存在也是唯一。,一个子集,A,最大下界（下确界），和最小上界（上确界），分别记作,glb(A),和,lub(A).,52/87,定义,上确界与下确界：,设（,S,，）是偏序集，,A,S,，若,a,是,A,一个上界,（下界），而,A,上界（下界）,z,，都有,a b,（,b a,）,，则称,a,是,A,上确界（下确界）,。,53/87,【example】,给定（,A,）哈塞,图如图所表示：,12,36,24,子集,B,上界,下界,2,3,1,2,3,6,12,24,C,1,6,12,24,36,1,24,1,2,3,6,1,无,6,12,24,36,上确界,下确界,6,6,24,无,1,1,6,1,54/87,【example 18】,在下列图所表示偏序集中假如,b,，,d,，,g,最大下界和最小上界存在，求出这个最大下界和最大上界。,Solution,：,b,，,d,，,g,上界是,g,和,h,。因为,g h,g,是最小上界。,b,，,d,，,g,下界是,a,和,b,，因为有,a b,b,是,最大下界。,55/87,【example 19】,在偏序集（,Z+,|,）中，假如集合,3,，,9,，,12,和,1,，,2,，,4,，,5,，,10,最大下界和最小上界存在，求出这些最大,下界和最小上界。,Solution,：,求最大下界：,假如,3,，,9,，,12,被一个整数整除，那么这个整数就是,3,，,9,，,12,下界。这么整数只有,1,和,3.,因为,1|3,，,3,是,3,，,9,，,12,最大下界。,集合,1,，,2,，,4,，,5,，,10,关系到,|,下界只有,1,，所以,1,是,1,，,2,，,4,，,5,，,10,最大下界。,56/87,求最小上界：,一个整数是,3,，,9,，,12,上界，当且仅当它被,3,，,9,和,12,整除,。含有这种性质整数就是那些被,3,，,9,和,12,最小公倍数,36,整,除整数。所以，,36,是,3,，,9,，,12,最小上界。,一个正整数是集合,1,，,2,，,4,，,5,，,10,上界，当且仅当它被,1,，,2,，,4,，,5,，,10,整除，含有这种性质整数就是被这些整数最,小公倍数,20,整除整数。所以，,20,是集合,1,，,2,，,4,，,510,最小上界。,57/87,五、格,在这里我们引入格概念。,定义：,设,X,是偏序集，假如,x,y,X,，集合,x,y,都有,最小上界和最大下界，则称,X,是格。,【example 20】,确定以下列图所表示每个哈塞图表示偏序集是否是格,58/87,Solution,：,图,a,和,c,中哈塞图表示偏序集是格。因为在每个偏序集中,每对元素都有最小上界和最大下界。,另首先，图,b,所表示哈塞图偏序集不是格，因为元素,b,和,c,没有最小上界。为此只要注意到,d,，,e,和,f,中每一个都是上界，但,这,3,个元素任何一个关于这个偏序集中序都小于其它,2,个,.,59/87,【example】,以下各集合对于整除关系都组成偏序集,判断哪些偏序集是格,?,L=,1,2,3,4,5,；,L=,1,2,3,4,6,9,12,18,36,；,L=,1,2,2,2,2,n,；,L=,1,2,3,4,5,6,7,8,9,10,60/87,Solution,：,不是，因为,L,中元素对,2,3,没有最小上界；,是，因为,L=,1,2,3,4,6,9,12,18,36,任何一对元素,a,b,，都有最小上界和最大下界；,是，与同理；,不是，因为,L,中元素对,6,7,没有最小上界不存在最小上界,.,61/87,【example】,下列图中给出了一些偏序集哈斯图，判断它们是否,组成格。,62/87Solution,：,它们都不是格。,在,(a),中，,1,2,没有下界，因而没有最大下界。,在,(b),中，,2,4,虽有两个上界，但没有最小上界。,在,(c),中，,1,3,没有下界，因而没有最大下界。,在,(d),中，,2,3,虽有三个上界，但没有最小上界。,63/87,【example 21】,偏序集（,Z,+,|,）是格吗？,Solution,：,设,a,和,b,是两个正整数，这两个整数最小上界和最大下界分,别是它们最小公倍数和最大条约数，所以这个偏序集是格。,64/87,【example 22】,确定偏序集（,1,，,2,，,3,，,4,，,5,，,|,）和,（,1,，,2,，,4,，,8,，,16,，,|,）是否为格？,Solution,：,因为,2,和,3,在（,1,，,2,，,3,，,4,，,5,，,|,）中没有上界，它们,当然没有最小上界。所以第一个偏序集不是格。,第二个偏序集每两个元素都有最小上界和最大下界。在,这个偏序集中两个元素最小上界是他们中间较大元素，,而两个元素最大下界是它们中间较小元素。所以第二个,偏序集是格。,65/87,【example 23】,确定（,P(S),）是否为格，其中,S,是集合。,Solution,：,设,A,和,B,是,S,两个子集，,A,和,B,最小上界和最大下界分别是,AB,和,A B,，所以（,P(S),）是格。,66/87,【example 24】,信息流格模式,在许多设置中，从一个人或,计算机程序到另一个人或计算机程序信息流要受到限制，这可,以经过安全权限来实现。我们能够使用格模型来表示不一样信,息流策略。,比如，一个通用信息流策略适合用于政府或军事系统中,多,级安全策略,。为，诶组信息分配一个安全级别，而且每个安全级,别用一个对（,A,C,）表示，其中,A,是权限级别，,C,是种类。然后,允许人和计算机程序从一个被尤其限制安全类集合中访问信,息。,67/87,在美国政府中，使用经典权限级别是不保密（,0,）、秘密,（,1,）、机密（,2,）和绝密（,3,）。在安全级别中使用种类是一,个集合子集，这个集合含有与一个特定行业领域相关全部,分部，每个分部表示一个指定对象域。,比如，假如分部集合是,间谍，鼹鼠。双重间谍,，那么存,在,8,个不一样种类，分部集合有,8,个子集，对于每个子集有一类,，比如,间谍，鼹鼠,。,68/87,我们能够对安全类排序，要求（,A,1,C,1,）,（,A,2,C,2,）当且仅当,A,1,A,2,和,C,1,C,2,.,信息允许从安全类（,A,1,C,1,）流向安全类,（,A,2,C,2,）当且仅当（,A,1,C,1,）,（,A,2,C,2,）。,比如，信息允许从安全类（机密，,间谍，鼹鼠,）流向安全,类（绝密，,间谍，鼹鼠，双重间谍,），反之，信息不允许从安,全类（绝密，,间谍，鼹鼠,）流向安全类（机密，,间谍，鼹鼠,，双重间谍,）或（绝密，,间谍,）。,69/87,六、拓扑排序,假设一个项目由,20,个任务组成。一些任务只能在其它任务结,束之后完成，怎样找到关于这些任务次序？,为了对这个问题结构模型，我们建立一个任务集合上偏序，,使得,ab,当且仅当,a,和,b,是任务且直到,a,结束后,b,才能开始。为安,排好这个项目，需要得出与这个偏序相容全部,20,个任务顺,序。我们将说明怎样做到这一点。,70/87,从定义开始，假如只要,aRb,就有,a b,则称一个全序,与偏序,R,是,相容,。从一个偏序结构一个相容全序叫做,拓扑排序,。需要使用引理,1.,引理,1,：,每个有穷非空偏序集（,S,）都有极小元素。,71/87,Proof,：,选择,S,一个元素,a,0,.,假如,a,0,不是绩效元素，那么存在元素,a,1,满足,a,1,a,0,.,假如,a,1,不是极小元素，那么存在元素,a,2,满足,a,2,a,1,.,继续这一过程，使得假如,a,n,不是极小元素，那么存在元素,a,n+1,满,足,a,n+1,a,n,.,因为在这个偏序集只有有穷个元素，这个过程一定结,束而且含有极小元素,a,n,.,72/87,我们将要描述拓扑排序算法对任何有穷非空偏序集都有效,为在偏序集（,A,）上定义一个全序，首先选择一个极小元,素,a,1,；由引理,1,这么元素存在。接着，,A-a,1,，,也是一个,偏序集。假如它是非空，选择这个偏序集一个极小元素,a,2.,然后再取走,a,2,，假如还有其它元素留下来，在,A-a,1,a,2,中,选择一个极小元素,a,3,。继续这个过程，只要还有元素留下来，就,在,A-a,1,a,2,a,k,中选择一个极小元素,a,k+1,.,73/87,因为,A,是有穷集，这个过程一定终止。最终产生一个元素序,列,a,1,a,2,a,n,.,所需要全序定义为,a,1,a,2,.a,n,这个全序是与初始偏序相容。为看出这一点，注意假如在,初始偏序中,bc,c,在算法某个阶段被选择为极小元素，则这,时,b,已经被移出，不然,c就不会是极小元素。,关于这个拓扑排序算法伪代码在算法,1,中给出。,74/87,75/87,【example 25】,找出对于偏序集,(1,，,2,，,4,，,5,，,12,，,20,，,|),一个相容全序。,Solution,：,第一步是选择一个极小元素。这个元素一定是,1,，因为他是唯,一极小元素。,下一步选择（,2,，,4,，,5,，,12,，,20,，,|,）一个极小元素。在,这个偏序集中有两个极小元素，即,2,和,5.,我们选择,5.,剩下元素是,2,，,4,，,12,，,20,。在这一步，唯一极小元素,是,2.,下一步选择,4,，因为它是（,4,，,12,，,20,，,|,）唯一极小元,素。因为,12,和,20,都是（,12,，,20,，,|,）极小元素，下一步选哪,一个都能够，我们选,20,，只剩下,12,作为最终元素。,76/87,产生全序是,15242012,这个排序算法所使用步骤在下列图中给出。,77/87,在项目标安排中常会用到拓扑排序。,【example 26】,一个计算机企业来发项目需要完成,7,个任务。,其中一些任务只能在其它任务结束后才能开始。考虑以下建立任,务上偏序，假如任务,Y,在,X,结束后才能开始，则任务,X,任务,Y,。这,7,个任务关于这个偏序哈塞图以下示。求一个全序，使得,能够按照这个全序执行这些任务以完成这个项目。,78/87,Sol