离散数学课件-第4章.ppt

《离散数学课件-第4章.ppt》由会员分享，可在线阅读，更多相关《离散数学课件-第4章.ppt（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1离散数学Discrete Mathematics&学习内容学习内容4.14.1集合的基本知识集合的基本知识集合的基本知识集合的基本知识4.2 序偶与笛卡尔积序偶与笛卡尔积4.3 4.3 关系及其性质关系及其性质关系及其性质关系及其性质4.4 n4.4 n元关系及其应用元关系及其应用元关系及其应用元关系及其应用4.5 4.5 关系的闭包关系的闭包关系的闭包关系的闭包4.6 4.6 等价关系等价关系4.7 4.7 偏序偏序偏序偏序&偏序偏序一、偏序一、偏序 定义定义1：集合集合S上的关系上的关系R，如果它是自反的、反对称的，如果它是自反的、反对称的 和传递的，就称为和传递的，就称为偏序偏序。集合

2、集合S与偏序与偏序R一起叫做一起叫做偏序集偏序集，记作（，记作（S,R）.例如数值的例如数值的、关系和集合的关系和集合的 都是偏序关系。都是偏序关系。【example 1】证明证明“大于或等于大于或等于”关系（关系（）是整数集合上）是整数集合上的偏序。的偏序。solution：因为对所有整数因为对所有整数a，有，有a a，是自反的。是自反的。如果如果a b且且b a，那么，那么a=b，因此，因此是反对称的。是反对称的。最后，因为最后，因为a b和和b c，所以，所以是传递的。是传递的。从而从而是整数集合上的偏序且（是整数集合上的偏序且（Z,）是偏序集。）是偏序集。【example 2】整除关系

3、整除关系“|”是正整数集合上的偏序，因为由是正整数集合上的偏序，因为由前前几节所述，它是自反的、反对称的和传递的。我们看到几节所述，它是自反的、反对称的和传递的。我们看到（Z+,|）是偏序集（）是偏序集（Z+表示正整数集合）。表示正整数集合）。【example 3】证明包含关系证明包含关系 是集合是集合S S的幂集上的偏序。的幂集上的偏序。Solution：因为只要因为只要A是是S的子集，就有的子集，就有A A,是自反的。是自反的。因为因为A B和和B A推出推出A=B，因此它是反对称的。，因此它是反对称的。最后，因为最后，因为A B和和B C推出推出A B,是传递的。是传递的。因此，因此，是

4、是P(S)上的偏序，且（上的偏序，且（P(S)，）是偏序集。）是偏序集。在任意一个偏序集中记号在任意一个偏序集中记号a a b b表示表示(a(a，b)b)R.R.使用这个记号使用这个记号 是由于是由于“小于或等于小于或等于”关系是偏序关系的范例。关系是偏序关系的范例。注意：注意：符号符号 表示任意偏序关系，并不仅仅是表示任意偏序关系，并不仅仅是“小于或等于小于或等于”关系。关系。记号记号abab表示表示a a b b但但ab.ab.如果如果ab,ab,我们说我们说“a a小于小于b”b”或或“b b大于大于a”a”。当当a与与b是偏序集（是偏序集（S,）的元素时，不一定有）的元素时，不一定有

5、a b 或或b c。例如，在（例如，在（P(Z),P(Z),）中）中,1,2,1,2与与1,31,3没有关系，反之亦然，因为没有关系，反之亦然，因为没有一个集合被另一个集合包含。类似地在没有一个集合被另一个集合包含。类似地在(Z,|)(Z,|)中，中，2 2与与3 3没关系，没关系，3 3与与2 2也没关系。由此得到定义也没关系。由此得到定义2.2.定义定义2 2：偏序集：偏序集(S,)的元素的元素a和和b叫做叫做可比的可比的，如果，如果a b 或或 b a。当。当a和和b是是S的元素并且既没有的元素并且既没有a b，也没，也没 有有b a，则称，则称a与与b是是不可比不可比的。的。【exam

6、ple 4】在偏序集在偏序集(Z+,)中，整数中，整数3和和9是可比的吗？是可比的吗？5和和7是可比的吗？是可比的吗？整数整数3和和9是可比的，因为是可比的，因为3|9.整数整数5和和7是不可比的，因为是不可比的，因为5不能整除不能整除7，并且，并且7也不能整除也不能整除5.用形容词用形容词“部分的（偏的）部分的（偏的）”描述偏序是由于一些对描述偏序是由于一些对元素可能是不可比的。当集合中的每对元素都可比时，元素可能是不可比的。当集合中的每对元素都可比时，这个关系叫做这个关系叫做全序全序。定义定义3：如果如果(S,)是偏序集，且是偏序集，且S的每对元素都是可的每对元素都是可比的，则比的，则S叫

7、做叫做全序集全序集或或线序集线序集，且，且 叫做叫做全序全序或或线线序序。一个全序集也叫做。一个全序集也叫做链链。【example 5】偏序集偏序集(Z,)是全序集，因为只要是全序集，因为只要a和和b是整数是整数，就有，就有a b或或b a。【example 6】偏序集偏序集(Z+,|)不是全序集，因为它包含着不可不是全序集，因为它包含着不可比的元素，例如比的元素，例如5和和7.定义定义4 4：对于偏序集对于偏序集(S,)，如果，如果 是全序，并且是全序，并且S的每的每 个非空子集都有一个最小元素，就称它为个非空子集都有一个最小元素，就称它为良序集良序集。For example，N是自然数集合

8、，是自然数集合，I是整数集合，是整数集合，是小于等于关系，是小于等于关系，就是就是良序集。而良序集。而不是良序集。不是良序集。定理定理 所有所有良序集，一定是全序集。良序集，一定是全序集。Proof：设设为良序集为良序集,任取任取x,y A,则则x,y A,它有最小它有最小元素。该最小元素或是元素。该最小元素或是x,或是或是y。于是有于是有x y或或 y x，所以所以是全序集。是全序集。定理定理 有限的有限的全序集，一定是良序集。全序集，一定是良序集。Proof：设设A=a1,a2,，an,是全序集。是全序集。假设它不是良序，必存在非空子集假设它不是良序，必存在非空子集B A，B中无最小元素，

9、中无最小元素，因因B是有限集，必存在是有限集，必存在x,y B,使得使得x与与y之间不满足之间不满足关系关系,与与是全序矛盾。是全序矛盾。是良序集。是良序集。【example 7】正整数的有序对的集合正整数的有序对的集合Z+Z+与与 构成构成良序集，对于良序集，对于(a1,a2)和和(b1,b2),如果如果a1b1,或如果或如果a1=b1且且a2 b2（字典顺序），则（字典顺序），则(a1,a2)(b1,b2).在前几章的学习中我们现实了怎样使用良序归纳原则证明关在前几章的学习中我们现实了怎样使用良序归纳原则证明关于一个良序集的结果。现在我们叙述并证明这个证明技术是于一个良序集的结果。现在我们

10、叙述并证明这个证明技术是有效的。有效的。定理定理1 良序归纳原理良序归纳原理 设设S是一个良序集，如果下述条件成立：是一个良序集，如果下述条件成立：基础步基础步：P(x0)对对S的最小元素为真，且的最小元素为真，且 归纳步归纳步:对一切对一切y S,如果如果P(x)对所有的对所有的x y为真，则为真，则P(y)为为 真。那么真。那么P(x)对所有的对所有的x S为真。为真。proof：假若假若P(x)不对所有的不对所有的x S为真。那么存在一个元素为真。那么存在一个元素y S使使得得P(y)为假。于是集合为假。于是集合A=x S|P(x)为假为假是非空的。是非空的。因为因为S是良序的，集合是良

11、序的，集合A有最小元素有最小元素a.易知易知a不等于不等于x0,因为从因为从基础步知道基础步知道P(x0)为真。为真。根据根据a是选自是选自A的最小元素，我们知道对所有的的最小元素，我们知道对所有的x S(xaa)都都有有P(x)为真。由归纳步这就可以退出为真。由归纳步这就可以退出P(a)为真。为真。这个矛盾就证明了这个矛盾就证明了P(x)必须对所有必须对所有x S 为真。为真。二、字典顺序二、字典顺序字典顺序字典顺序是以字母表中的字母顺序为基础的。这是从一是以字母表中的字母顺序为基础的。这是从一个集合上的偏序构造一个集合上的串的序的特殊情况。个集合上的偏序构造一个集合上的串的序的特殊情况。我

12、们将说明这种构造在任一个偏序集上是怎么做的。我们将说明这种构造在任一个偏序集上是怎么做的。首先，我们将说明怎样在两个偏序集首先，我们将说明怎样在两个偏序集(A1,1)和和(A2,2)的笛的笛卡尔积上构造一个偏序。卡尔积上构造一个偏序。在在A1A2上的字典顺序定义如下：如果第一个对的第一个上的字典顺序定义如下：如果第一个对的第一个元素（在元素（在A1中）小于第二个对的第一个元素，或者第一个元中）小于第二个对的第一个元素，或者第一个元素相等，但是第一个对的第二个元素（在素相等，但是第一个对的第二个元素（在A2中）小于第二个中）小于第二个对的第二个元素，那么第一个对小于第二个对。换句话说，对的第二个

13、元素，那么第一个对小于第二个对。换句话说，(a1,a2)小于小于(b1,b2),即即(a1,a2)(b1,b2)或者或者a11b1,或者或者a1=b1且且a22b2.把相等加到把相等加到A1A2上的序就得到偏序上的序就得到偏序。【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)的第一元素相同，但的第

14、一元素相同，但911,我们有我们有(4,9)(4,11)。下图明显地显示了下图明显地显示了Z+Z+中比中比(3,4)小的有序对的集合。小的有序对的集合。可以在可以在n个偏序集个偏序集(A1,1),(A2,2),(An,n)的笛卡尔的笛卡尔积上定义字典顺序。积上定义字典顺序。如下定义如下定义A1A2An上的偏序上的偏序 ：如果：如果a10 是的是的a1=b1,ai=bi,且且ai+1i+1 bi+1,那么那么(a1,a2,an)(b1,b2,bn)换句话说，如果在两个换句话说，如果在两个n元组不同元素出现的第一位置上等元组不同元素出现的第一位置上等一个一个n元组的元素小于第二个元组的元素小于第二

15、个n元组的元素，那么第一个元组的元素，那么第一个n元组小元组小于第二个于第二个n元组。元组。【example 9】注意（注意（1，2，3，5）（1，2，4，3），因为这），因为这些些4元组的前两位相同，但是第一个元组的前两位相同，但是第一个4元组的第三位元组的第三位3小于第二个小于第二个4元组的第三位元组的第三位4（这里的（这里的4元组上的字典顺序是整数集合上的通元组上的字典顺序是整数集合上的通常的常的“小于或等于小于或等于”关系导出的字典顺序）。关系导出的字典顺序）。我们现在可以定义串上的字典顺序。考虑偏序集我们现在可以定义串上的字典顺序。考虑偏序集S上的串上的串a1a2an和和b1b2bn

16、,假定这些串不相等。设假定这些串不相等。设t是是m，n中较小的数。中较小的数。定义字典顺序如下：定义字典顺序如下：a1a2an小于小于b1b2bn,当且仅当当且仅当（a1a2at）（b1b2bt）或者或者（a1a2at）=（b1b2bt）并且）并且mn 其中这个不等式中的其中这个不等式中的表示表示St中的字典顺序。换句话说，为确定两中的字典顺序。换句话说，为确定两个不同串的序，较长的串被切到较短的串的长度个不同串的序，较长的串被切到较短的串的长度t，即，即t=min(m,n)然然后使用后使用St上的字典顺序比较每个船的前上的字典顺序比较每个船的前t为组成的为组成的t元组，如果对应于元组，如果对

17、应于第一个串的第一个串的t元组小于第二个串的元组小于第二个串的t元组，或者这两个元组，或者这两个t元组相等，但是元组相等，但是第二个串更长，那么第一个串小于第二个串。第二个串更长，那么第一个串小于第二个串。【example 10】考虑小写英语字母串构成的集合。使用在字母考虑小写英语字母串构成的集合。使用在字母表中的字母序，可以构成在串的集合上的字典顺序。表中的字母序，可以构成在串的集合上的字典顺序。如果两个串第一次出现不同字母时，第一个串的字母先于第如果两个串第一次出现不同字母时，第一个串的字母先于第二个字母，或者如果第一个串和第二个串在所有的位都相同，二个字母，或者如果第一个串和第二个串在所

18、有的位都相同，但是第二个串有更多的字母，那么，第一个串小于第二个串。但是第二个串有更多的字母，那么，第一个串小于第二个串。这种排序和字典使用的排序相同。例如这种排序和字典使用的排序相同。例如 discreet discrete因为这两个串在第因为这两个串在第7位首次出现字母，并且位首次出现字母，并且 e t.discreet discreetness因为这两个串前因为这两个串前8个字母相同，但是第二个串更长。此外个字母相同，但是第二个串更长。此外 discrete discretion在有穷偏序集的有向图中有许多可以不必显示出来，因为他在有穷偏序集的有向图中有许多可以不必显示出来，因为他们是必

19、须存在的。们是必须存在的。例如，考虑在集合例如，考虑在集合11，2 2，3 3，44上的偏序上的偏序(a,b)|a(a,b)|a bb的有向图，参的有向图，参见图见图a a。因为这个关系是偏序，它是自反的并且有向图在所有的顶点都有。因为这个关系是偏序，它是自反的并且有向图在所有的顶点都有环，因此，我们不必显示这些环，因为它们是必须出现的。在图环，因此，我们不必显示这些环，因为它们是必须出现的。在图b b中没有中没有显示这些环。由于一个偏序是传递的，我们不必显示那些由于传递性而必显示这些环。由于一个偏序是传递的，我们不必显示那些由于传递性而必须出现的边。例如，在图须出现的边。例如，在图c c中没

20、有显示边中没有显示边(1,3),(1,4)(1,3),(1,4)和和(2,4)(2,4)，因为它们，因为它们是必须出现的。如果假设所有的边的方向是向上的，我们不必显示边的方是必须出现的。如果假设所有的边的方向是向上的，我们不必显示边的方向；图向；图c c没有显示方向。没有显示方向。我们可以使用下面的过程表示一个有穷集上的偏序。我们可以使用下面的过程表示一个有穷集上的偏序。从这个关系的有向图开始：从这个关系的有向图开始：(1)(1)自反性：每个顶点都有自回路，省去。自反性：每个顶点都有自回路，省去。(2)(2)反反对对称称性性：两两个个顶顶点点间间只只可可能能有有一一个个箭箭头头从从左左 右右，

21、或从下或从下上的方向从小到大安置顶点，可省略箭头。上的方向从小到大安置顶点，可省略箭头。(3)(3)传递性：由于有传递性：由于有(a,b)(a,b)，(b,c)R(b,c)R 则则(a,c)R(a,c)R故只画故只画(a,b)(a,b)，(b,c)(b,c)对应的边对应的边,省略边省略边(a,c)(a,c)。哈塞图（哈塞图（HasseHasse 图）图）定义：定义：设设 是上的一个偏序关系，如果是上的一个偏序关系，如果a a b b，则将画在，则将画在 下面，且不下面，且不，使，使a a c c，c c b b，则，间用直线连，则，间用直线连 接。并符合简化的关系图的绘制，称这样得到关系图为接

22、。并符合简化的关系图的绘制，称这样得到关系图为 哈塞图（哈塞图（HasseHasse图）图）。292023/2/20【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).排列所有的边使得方向向上排列所有的边使得方向向上，并且删

23、除所有的箭头得到哈塞图。结果如图，并且删除所有的箭头得到哈塞图。结果如图c所示。所示。【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).最后，使所有的边方向向上并删除箭头。得到哈塞图如下所最后，使所有的边方向向

24、上并删除箭头。得到哈塞图如下所示。示。【example】：，1（，）（，），2（，）（，）|，3(s1,s2)s1 s2，s1，s2 p(B)求求R1,R2,R3 所表示关系的哈塞图。所表示关系的哈塞图。1 2 3 4 5 6 7 8 9 123456789abca,ba,ca,ca,b,c具有极值性质的偏序集元素有许多重要应用。具有极值性质的偏序集元素有许多重要应用。偏序集的一个元素叫做极大的，当它不小于这个偏序集的任偏序集的一个元素叫做极大的，当它不小于这个偏序集的任何其他元素。即何其他元素。即a在偏序集在偏序集（S，）中是）中是极大的极大的，当不存，当不存在在bS使得使得ab.类似地，偏

25、序集的一个元素叫做极小的，如果它不大于这个类似地，偏序集的一个元素叫做极小的，如果它不大于这个偏序集的任何其他元素。即偏序集的任何其他元素。即a在偏序集（在偏序集（S，）中是）中是极小极小的的，如果不存在，如果不存在bS使得使得ba。使用哈塞图很容易是识别极大元素和极小元素。它们是图中使用哈塞图很容易是识别极大元素和极小元素。它们是图中的的“顶顶”元素与元素与“底底”元素。元素。定义定义 极大元与极小元：极大元与极小元：设（设（S，）是偏序集，若）是偏序集，若S，且在，且在S中找不到一个中找不到一个元素元素b（ba），使），使a b（b a），则称），则称a为为A中的中的极大元素极大元素（极小

26、元素）。（极小元素）。y是是B的的极小元素极小元素 y(y B x(x B x y x y)y是是B的的极大元素极大元素 y(y B x(x B x y y x)【example】（N，|）是偏序集，是偏序集，A=2，3，4，5，6，7，8，9则则 中极大元素：，中极大元素：，极小元素：，极小元素：，注：注：极极大大元元，极极小小元元并并不不要要求求唯唯一一，且且同同一一元元素素，可可以以既既是是极极大大元，又是极小元，如，。元，又是极小元，如，。极大元，极小元必须是子集中的元素。极大元，极小元必须是子集中的元素。23576489【example 13】偏序集（偏序集（2，4，5，10，12，

27、20，25，|）的）的哪些元素时极大的，哪些是极小的？哪些元素时极大的，哪些是极小的？Solution：右图关于这个偏序集的哈塞图右图关于这个偏序集的哈塞图显示了极大元素是显示了极大元素是12，20和和25，极小元素时极小元素时2和和5。在偏序集中存在一个元素大于每个其他的元素，这样的元素在偏序集中存在一个元素大于每个其他的元素，这样的元素叫做最大元素，即叫做最大元素，即a a是偏序集（是偏序集（S S，）的）的最大元素最大元素，当对所，当对所有的有的b bS S有有b b a a。当最大元素存在时它是唯一的。当最大元素存在时它是唯一的。类似地，一个元素叫做最小元素，当它小于偏序集的所有其类似

28、地，一个元素叫做最小元素，当它小于偏序集的所有其他元素。即他元素。即a a是偏序集（是偏序集（S S，）的）的最小元素最小元素，如果对所有的，如果对所有的b bS S有有a a b b。当最小元素存在时它也是唯一的。当最小元素存在时它也是唯一的。402023/2/20 定义定义 最大元素与最小元素：最大元素与最小元素：设（设（S，）是偏序集，若）是偏序集，若，(），则称为的），则称为的最大元素（最小元素）最大元素（最小元素）。【example】上例中其上例中其Hasse图如下图所示图如下图所示23576489结论：结论：子集中是不存在最大元（最小元）的。子集中是不存在最大元（最小元）的。定理定

29、理 是偏序集，是偏序集，B是是A的非空子集，如果的非空子集，如果B有最小元素有最小元素(最大元素最大元素)，则最小元素，则最小元素(最大元素最大元素)是唯一的。是唯一的。proof：假设假设B有两个最小元素有两个最小元素a、b,则则 因为因为a是是最小元素，最小元素，b B，根据根据最小元素定义，有最小元素定义，有a b;类似地，因为类似地，因为b是是最小元素，最小元素，a B，根据，根据最小元素定义，有最小元素定义，有b a。因为。因为 有反对称性，所以有有反对称性，所以有a=b。同理可证同理可证最大元素的唯一性。最大元素的唯一性。小结：小结：是偏序集，是偏序集，B是是A的非空子集，则的非空

30、子集，则 B B的的极小极小(大大)元素总是存在的，就是子集中处在最下元素总是存在的，就是子集中处在最下(上上)层的层的元素是极小元素是极小(大大)元素。元素。B B的的最小元最小元(最大元最大元)素有时可能不存在，只要有唯一的极小素有时可能不存在，只要有唯一的极小(大大)元素，则这个极小元素，则这个极小(大大)元素就是最小元素就是最小(大大)元素。否则就没元素。否则就没有最小有最小(大大)元素。元素。【example 14】确定下图的每个哈塞图表示的偏序集是否有最确定下图的每个哈塞图表示的偏序集是否有最大元素和最小元素。大元素和最小元素。Solution：哈塞图哈塞图(a)的偏序集的最小元素

31、时的偏序集的最小元素时a。这个偏序集没有最大元。这个偏序集没有最大元素。素。哈塞图哈塞图(b)的偏序集既没有最大元素也没有最小元素。的偏序集既没有最大元素也没有最小元素。哈塞图哈塞图(c)的偏序集没有最小元素，它的最大元素时的偏序集没有最小元素，它的最大元素时d。哈塞图哈塞图(d)的偏序集有最小元素的偏序集有最小元素a和最大元素和最大元素d。【example15】设设S是集合。确定偏序集（是集合。确定偏序集（P(S),）中是否存）中是否存在最大元素与最小元素。在最大元素与最小元素。Solution：最小元素时空集。因为对于最小元素时空集。因为对于S的任何子集的任何子集T,有有 T，集合，集合S

32、是是这个偏序集的最大元素，因为只要这个偏序集的最大元素，因为只要T是是S的子集，就有的子集，就有T S。462023/2/20【example 16】在偏序集（在偏序集（Z+,|）中是否存在最大元素和）中是否存在最大元素和最小元素？最小元素？Solution：1是最小元素，因为只要是最小元素，因为只要n是正整数，就有是正整数，就有1|n。因为没。因为没有被所有正整数整除的整数，所以不存在最大元素。有被所有正整数整除的整数，所以不存在最大元素。472023/2/20有时可以找到一个元素大于偏序集（有时可以找到一个元素大于偏序集（S，）的子集）的子集A中所有中所有的元素。如果的元素。如果u是是S的

33、元素使得对所有的元素的元素使得对所有的元素a A,有有a u，那，那么么u叫做叫做A的的一个上界一个上界。也可能存在一个元素小于也可能存在一个元素小于A中的所有的其他元素。如果中的所有的其他元素。如果l是是S的的一个元素使得对所有的元素一个元素使得对所有的元素a A,有有l a，那么，那么l叫做叫做A的的一个一个下界下界。定义定义 上界与下界：上界与下界：设（设（P,）是半序集，）是半序集，A P，若，若a P，对，对 b A,b a（a b）称）称a为为A的的上界（下界）上界（下界）。【example】：B=a,b,c,R3=(s1,s2)|s1 s2，s1P(B),(P(B),)是偏序集。

34、是偏序集。设设，a,b,c,a,c,a,b,a,c其其HasseHasse图如右图所示图如右图所示:abca,ba,cb,c注：注：（1）上例中，无最大元素，但存在的上界）上例中，无最大元素，但存在的上界 ，。，。（2）为的最小元，也是的下界。为的最小元，也是的下界。（3）最大（小）元素是的一个上（下）界。）最大（小）元素是的一个上（下）界。（4）上（下）界可以不唯一，也可以不存在。）上（下）界可以不唯一，也可以不存在。【example 17】找出下图所示哈塞图的偏序集的子集找出下图所示哈塞图的偏序集的子集a,b,c,j,h和和a，c，d，f的下界和上界。的下界和上界。Solution：a，b

35、，c的上界是的上界是e,f,j 和和h，它的唯一的下界是，它的唯一的下界是a。j，h没有上界，它的下界是没有上界，它的下界是a，b，c，d，e和和f.a,c,d,f 的上界是的上界是f，h和和j，它的下界是，它的下界是a。元素元素x叫做子集叫做子集A的的最小上界（上确界）最小上界（上确界），如果，如果x是一个上界并是一个上界并且它小于且它小于A的其他上界。因为如果这样的元素存在，只存在一的其他上界。因为如果这样的元素存在，只存在一个，称这个元素为最小上界（上确界）是有意义的。即如果个，称这个元素为最小上界（上确界）是有意义的。即如果只要只要a A就有就有a x，并且只要，并且只要z是是A的上界

36、，就有的上界，就有x z,x就是就是A的最小上界（上确界）。的最小上界（上确界）。类似地，如果类似地，如果y是是A的下界，并且只要的下界，并且只要z是是A的下界，就有的下界，就有z y，y就是就是A的的最大下界（下确界）最大下界（下确界）。A的最大下界（下确界）的最大下界（下确界）如果存在也是唯一的。如果存在也是唯一的。一个子集一个子集A的最大下界（下确界），和最小上界（上确界），的最大下界（下确界），和最小上界（上确界），分别记作分别记作 glb(A)和和 lub(A).定义定义 上确界与下确界：上确界与下确界：设（设（S，）是偏序集，）是偏序集，A S，若，若a是是A的一个上界的一个上界（

37、下界），而（下界），而 A的上界（下界）的上界（下界）z，都有，都有a b（b a），则称，则称a是是A的的上确界（下确界）上确界（下确界）。【example】给定（给定（A,）的哈塞）的哈塞图如图所示：图如图所示：12 36 24 子集子集B上界上界下界下界2,31,2,36,12,24C 16,12,24,361241,2,3,61无无6,12,24,36上确界上确界下确界下确界6624无无1161【example 18】在下图所示偏序集中如果在下图所示偏序集中如果b，d，g的最大下界的最大下界和最小上界存在，求出这个最大下界和最大上界。和最小上界存在，求出这个最大下界和最大上界。【exa

38、mple 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的最大下界。的最大下界。求最小上

39、界：求最小上界：一个整数是一个整数是 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，5，10的的最小上界。最小

40、上界。五、格五、格 在这里我们引入格的概念。在这里我们引入格的概念。1.定义：定义：设设 X,是偏序集，如果是偏序集，如果 x,y X，集合，集合 x,y 都有都有2.最小上界和最大下界，则称最小上界和最大下界，则称 X,是格。是格。3.【example 20】确定如下图所示的每个哈塞图表示的偏序集确定如下图所示的每个哈塞图表示的偏序集是否是格是否是格 Solution：图图a和和c中的哈塞图表示的偏序集是格。因为在每个偏序集中中的哈塞图表示的偏序集是格。因为在每个偏序集中每对元素都有最小上界和最大下界。每对元素都有最小上界和最大下界。另一方面，图另一方面，图b所示的哈塞图的偏序集不是格，因为

41、元素所示的哈塞图的偏序集不是格，因为元素b和和c没有最小上界。为此只要注意到没有最小上界。为此只要注意到d，e和和f中每一个都是上界，但中每一个都是上界，但这这3个元素的任何一个关于这个偏序集中的序都不大于其他个元素的任何一个关于这个偏序集中的序都不大于其他2个个.【example】下列各集合对于整除关系都构成偏序集下列各集合对于整除关系都构成偏序集,判断哪些判断哪些偏序集是格偏序集是格?L=1,2,3,4,5；L=1,2,3,4,6,9,12,18,36；L=1,2,22,2n；L=1,2,3,4,5,6,7,8,9,10Solution：不是，因为不是，因为L中的元素对中的元素对2,3没有

42、最小上界；没有最小上界；是，因为是，因为L=1,2,3,4,6,9,12,18,36任何一对元素任何一对元素a,b，都有，都有最小上界和最大下界；最小上界和最大下界；是，与是，与同理；同理；不是，因为不是，因为L中的元素对中的元素对6,7没有最小上界不存在最小上界没有最小上界不存在最小上界.【example】下图中给出了一些偏序集的哈斯图，判断它们是否下图中给出了一些偏序集的哈斯图，判断它们是否构成格。构成格。Solution：它们都不是格。它们都不是格。在在(a)中，中，1,2没有下界，因而没有最大下界。没有下界，因而没有最大下界。在在(b)中，中，2,4虽有两个上界，但没有最小上界。虽有两

43、个上界，但没有最小上界。在在(c)中，中，1,3没有下界，因而没有最大下界。没有下界，因而没有最大下界。在在(d)中，中，2,3虽有三个上界，但没有最小上界。虽有三个上界，但没有最小上界。【example 21】偏序集（偏序集（Z+,|）是格吗？）是格吗？Solution：设设a和和b是两个正整数，这两个整数的最小上界和最大下界分是两个正整数，这两个整数的最小上界和最大下界分别是它们的最小公倍数和最大公约数，因此这个偏序集是格。别是它们的最小公倍数和最大公约数，因此这个偏序集是格。【example 22】确定偏序集（确定偏序集（1，2，3，4，5，|）和）和（1，2，4，8，16，|）是否为格

44、？）是否为格？Solution：因为因为2和和3在（在（1，2，3，4，5，|）中没有上界，它们）中没有上界，它们当然没有最小上界。因此第一个偏序集不是格。当然没有最小上界。因此第一个偏序集不是格。第二个偏序集的每两个元素都有最小上界和最大下界。在第二个偏序集的每两个元素都有最小上界和最大下界。在这个偏序集中两个元素的最小上界是他们中间较大的元素，这个偏序集中两个元素的最小上界是他们中间较大的元素，而两个元素的最大下界是它们中间较小的元素。因此第二个而两个元素的最大下界是它们中间较小的元素。因此第二个偏序集是格。偏序集是格。【example 23】确定（确定（P(S),）是否为格，其中）是否为

45、格，其中S是集合。是集合。Solution：设设A和和B是是S的两个子集，的两个子集，A和和B的最小上界和最大下界分别是的最小上界和最大下界分别是A B和和A B，因此（，因此（P(S),）是格。）是格。【example 24】信息流的格模式信息流的格模式 在许多设置中，从一个人或在许多设置中，从一个人或计算机程序到另一个人或计算机程序的信息流要受到限制，这可计算机程序到另一个人或计算机程序的信息流要受到限制，这可以通过安全权限来实现。我们可以使用格的模型来表示不同的信以通过安全权限来实现。我们可以使用格的模型来表示不同的信息流策略。息流策略。例如，一个通用的信息流策略适用于政府或军事系统中的

46、例如，一个通用的信息流策略适用于政府或军事系统中的多多级安全策略级安全策略。为，诶组信息分配一个安全级别，并且每个安全级。为，诶组信息分配一个安全级别，并且每个安全级别用一个对（别用一个对（A,C）表示，其中）表示，其中A是权限级别，是权限级别，C是种类。然后是种类。然后允许人和计算机程序从一个被特别限制的安全类的集合中访问信允许人和计算机程序从一个被特别限制的安全类的集合中访问信息。息。在美国政府中，使用的典型的权限级别是不保密（在美国政府中，使用的典型的权限级别是不保密（0）、秘密）、秘密（1）、机密（）、机密（2）和绝密（）和绝密（3）。在安全级别中使用的种类是一）。在安全级别中使用的种

47、类是一个集合的子集，这个集合含有与一个特定行业领域相关的所有的个集合的子集，这个集合含有与一个特定行业领域相关的所有的分部，每个分部表示一个指定的对象域。分部，每个分部表示一个指定的对象域。例如，如果分部的集合是例如，如果分部的集合是间谍，鼹鼠。双重间谍间谍，鼹鼠。双重间谍，那么存，那么存在在8个不同的种类，分部集合有个不同的种类，分部集合有8个子集，对于每个子集有一类个子集，对于每个子集有一类，例如，例如间谍，鼹鼠间谍，鼹鼠。我们可以对安全类排序，规定（我们可以对安全类排序，规定（A1,C1）（A2,C2）当且仅当）当且仅当A1 A2和和C1 C2.信息允许从安全类（信息允许从安全类（A1,

48、C1）流向安全类）流向安全类（A2,C2）当且仅当（）当且仅当（A1,C1）（A2,C2）。例如，信息允许从安全类（机密，例如，信息允许从安全类（机密，间谍，鼹鼠间谍，鼹鼠）流向安全）流向安全类（绝密，类（绝密，间谍，鼹鼠，双重间谍间谍，鼹鼠，双重间谍），反之，信息不允许从安），反之，信息不允许从安全类（绝密，全类（绝密，间谍，鼹鼠间谍，鼹鼠）流向安全类（机密，）流向安全类（机密，间谍，鼹鼠间谍，鼹鼠，双重间谍，双重间谍）或（绝密，）或（绝密，间谍间谍）。）。六、拓扑排序六、拓扑排序假设一个项目由假设一个项目由2020个任务构成。某些任务只能在其他任务结个任务构成。某些任务只能在其他任务结束之

49、后完成，如何找到关于这些任务的顺序？束之后完成，如何找到关于这些任务的顺序？为了对这个问题构造模型，我们建立一个任务集合上的偏序，为了对这个问题构造模型，我们建立一个任务集合上的偏序，使得使得ab,ab,当且仅当当且仅当a a和和b b是任务且直到是任务且直到a a结束后结束后b b才能开始。为安才能开始。为安排好这个项目，需要得出与这个偏序相容的所有排好这个项目，需要得出与这个偏序相容的所有2020个任务的顺个任务的顺序。我们将说明怎样做到这一点。序。我们将说明怎样做到这一点。从定义开始，如果只要从定义开始，如果只要aRb就有就有a b,则称一个全序则称一个全序 与偏序与偏序R 是是相容的相

50、容的。从一个偏序构造一个相容的全序叫做。从一个偏序构造一个相容的全序叫做拓扑排序拓扑排序。需。需要使用引理要使用引理1.引理引理1：每个有穷非空偏序集（每个有穷非空偏序集（S,）都有极小元素。）都有极小元素。Proof：选择选择S的一个元素的一个元素a0.如果如果a0不是绩效元素，那么存在元素不是绩效元素，那么存在元素a1,满足满足a1 a0.如果如果a1不是极小元素，那么存在元素不是极小元素，那么存在元素a2,满足满足a2 a1.继续这一过程，使得如果继续这一过程，使得如果an不是极小元素，那么存在元素不是极小元素，那么存在元素an+1满满足足an+1an.因为在这个偏序集只有有穷个元素，这