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

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，如果它是自反的、反对称的，如果它是自反的、反对称的 和传递的，就称为和传递的，就称为偏序偏序 集合集合S与偏序与偏序R一起叫做一起叫做偏序集偏序集，记作（，记作（S,R））. 例如数值的例如数值的≤≤、、≥≥关系和集合的关系和集合的 都是偏序关系都是偏序关系【【example 1】】证明证明“大于或等于大于或等于”关系（关系（ ≥ ）是整数集合上）是整数集合上的偏序 solution：： 因为对所有整数因为对所有整数a，有，有a ≥a，， ≥是自反的。

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

是偏序集³在任意一个偏序集中记号在任意一个偏序集中记号a a ≼ ≼ b b表示表示(a(a，，b)b) R.R.使用这个记号使用这个记号 是由于是由于““小于或等于小于或等于””关系是偏序关系的范例关系是偏序关系的范例注意：注意：符号符号 ≼ ≼ 表示任意偏序关系，并不仅仅是表示任意偏序关系，并不仅仅是““小于或等于小于或等于””关系 记号记号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.³用形容词用形容词“部分的（偏的）部分的（偏的）”描述偏序是由于一些对描述偏序是由于一些对元素可能是不可比的当集合中的每对元素都可比时，元素可能是不可比的当集合中的每对元素都可比时，这个关系叫做这个关系叫做全序全序定义定义3：：如果如果(S, ≼ ≼ ) 是偏序集，且是偏序集，且S的每对元素都是可的每对元素都是可比的，则比的，则S叫做叫做全序集全序集或或线序集线序集，且，且≼ ≼ 叫做叫做全序全序或或线线序序一个全序集也叫做一个全序集也叫做链链【【example 5】】偏序集偏序集(Z, ≤)是全序集，因为只要是全序集，因为只要a和和b是整数是整数，就有，就有a ≤b或或b ≤a。

example 6】】偏序集偏序集(Z+, | )不是全序集，因为它包含着不可不是全序集，因为它包含着不可比的元素，例如比的元素，例如5和和7.定义定义4 4：：对于偏序集对于偏序集(S, ≼ ≼ ) ，如果，如果≼ ≼是全序，并且是全序，并且S的每的每 个非空子集都有一个最小元素，就称它为个非空子集都有一个最小元素，就称它为良序集良序集For example，， N是自然数集合，是自然数集合，I是整数集合，是整数集合，≤是小于等于关系，是小于等于关系，就是就是良序集而良序集而不是良序集不是良序集定理定理 所有所有良序集，一定是全序集良序集，一定是全序集Proof：： 设设为良序集为良序集,任取任取x, y ∈ ∈ A, 则则{x, y}  A, 它有最小它有最小元素该最小元素或是元素该最小元素或是x,或是或是y 于是有于是有x ≤ y或或 y ≤ x，，所以所以是全序集是全序集定理定理 有限的有限的全序集，一定是良序集全序集，一定是良序集Proof：： 设设A={a1, a2, …，，an}, 是全序集。

是全序集 假设它不是良序，必存在非空子集假设它不是良序，必存在非空子集B A，，B中无最小元素，中无最小元素，因因B是有限集，必存在是有限集，必存在x, y ∈ ∈ B,使得使得x与与y之间不满足之间不满足≤关系关系,与与≤是全序矛盾是全序矛盾 ∴∴是良序集是良序集【【example 7】】正整数的有序对的集合正整数的有序对的集合Z+×Z+与与≼ ≼构成构成良序集，对于良序集，对于(a1, a2)和和(b1, b2),如果如果a1

那么真那么P(x)对所有的对所有的x∈ ∈ S为真 proof：： 假若假若P(x)不对所有的不对所有的x∈ ∈ S为真那么存在一个元素为真那么存在一个元素y ∈ ∈ S使使得得P(y)为假于是集合为假于是集合A={x ∈ ∈ S| P(x)为假为假}是非空的是非空的 因为因为S是良序的，集合是良序的，集合A有最小元素有最小元素a. 易知易知a不等于不等于x0,因为从因为从基础步知道基础步知道P(x0)为真 根据根据a是选自是选自A的最小元素，我们知道对所有的的最小元素，我们知道对所有的x∈ ∈ S (x

³首先，我们将说明怎样在两个偏序集首先，我们将说明怎样在两个偏序集(A1, ≼ ≼1)和和(A2, ≼ ≼2)的笛的笛卡尔积上构造一个偏序卡尔积上构造一个偏序³在在A1×A2上的字典顺序定义如下：如果第一个对的第一个上的字典顺序定义如下：如果第一个对的第一个元素（在元素（在A1中）小于第二个对的第一个元素，或者第一个元中）小于第二个对的第一个元素，或者第一个元素相等，但是第一个对的第二个元素（在素相等，但是第一个对的第二个元素（在A2中）小于第二个中）小于第二个对的第二个元素，那么第一个对小于第二个对换句话说，对的第二个元素，那么第一个对小于第二个对换句话说，(a1, a2)小于小于(b1,b2),即即(a1, a2) < (b1,b2)或者或者a1<1b1,或者或者a1=b1且且a2<2b2. 把相等加到把相等加到A1×A2上的序就得到偏序上的序就得到偏序≼ ≼【【example 8】】确定在偏序集（确定在偏序集（Z×Z，，≼ ≼ ）中是否有）中是否有(3, 5) < (4,8), (3,8)<(4,5) 和和(4,9) <(4,11) ?这里的这里的≼ ≼ 是从是从Z上通常的上通常的≤关系构造的字典顺序。

关系构造的字典顺序Solution：： 因为因为3<4,故而故而(3, 5) < (4,8), 且且(3,8)<(4,5) 因为(4,9)与与(4,11) 的第一元素相同，但的第一元素相同，但9<11,我们有我们有(4,9) <(4,11) 下图明显地显示了下图明显地显示了Z+×Z+ 中比中比(3,4)小的有序对的集合小的有序对的集合³可以在可以在n个偏序集个偏序集(A1, ≼ ≼1 ), (A2, ≼ ≼2 ), …, (An, ≼ ≼n ) 的笛卡尔的笛卡尔积上定义字典顺序积上定义字典顺序 如下定义如下定义A1×A2×…×An上的偏序上的偏序 ≼ ≼ ：如果：如果a10 是的是的a1=b1,…,ai=bi,且且ai+1

元组【【example 9】】注意（注意（1，，2，，3，，5））<（（1，，2，，4，，3），因为这），因为这些些4元组的前两位相同，但是第一个元组的前两位相同，但是第一个4元组的第三位元组的第三位3小于第二个小于第二个4元组的第三位元组的第三位4（这里的（这里的4元组上的字典顺序是整数集合上的通元组上的字典顺序是整数集合上的通常的常的“小于或等于小于或等于”关系导出的字典顺序）关系导出的字典顺序）³我们现在可以定义串上的字典顺序考虑偏序集我们现在可以定义串上的字典顺序考虑偏序集S上的串上的串a1a2…an和和b1b2…bn,假定这些串不相等设假定这些串不相等设t是是m，，n中较小的数中较小的数 定义字典顺序如下：定义字典顺序如下： a1a2…an小于小于b1b2…bn,当且仅当当且仅当（（a1a2…at））< （（b1b2…bt）） 或者或者（（a1a2…at）） = （（b1b2…bt）并且）并且m

第二个串更长，那么第一个串小于第二个串【【example 10】】 考虑小写英语字母串构成的集合使用在字母考虑小写英语字母串构成的集合使用在字母表中的字母序，可以构成在串的集合上的字典顺序表中的字母序，可以构成在串的集合上的字典顺序 如果两个串第一次出现不同字母时，第一个串的字母先于第如果两个串第一次出现不同字母时，第一个串的字母先于第二个字母，或者如果第一个串和第二个串在所有的位都相同，二个字母，或者如果第一个串和第二个串在所有的位都相同，但是第二个串有更多的字母，那么，第一个串小于第二个串但是第二个串有更多的字母，那么，第一个串小于第二个串这种排序和字典使用的排序相同例如这种排序和字典使用的排序相同例如 discreet < discrete因为这两个串在第因为这两个串在第7位首次出现字母，并且位首次出现字母，并且 e< t. discreet < discreetness因为这两个串前因为这两个串前8个字母相同，但是第二个串更长此外个字母相同，但是第二个串更长此外 discrete < discretion³在有穷偏序集的有向图中有许多可以不必显示出来，因为他在有穷偏序集的有向图中有许多可以不必显示出来，因为他们是必须存在的。

们是必须存在的 例如，考虑在集合例如，考虑在集合{1{1，，2 2，，3 3，，4}4}上的偏序上的偏序{(a, b)| a {(a, b)| a ≤≤b}b}的有向图，参的有向图，参见图见图a a因为这个关系是偏序，它是自反的并且有向图在所有的顶点都有因为这个关系是偏序，它是自反的并且有向图在所有的顶点都有环，因此，我们不必显示这些环，因为它们是必须出现的在图环，因此，我们不必显示这些环，因为它们是必须出现的在图b b中没有中没有显示这些环由于一个偏序是传递的，我们不必显示那些由于传递性而必显示这些环由于一个偏序是传递的，我们不必显示那些由于传递性而必须出现的边例如，在图须出现的边例如，在图c c中没有显示边中没有显示边(1,3),(1,4)(1,3),(1,4)和和(2,4)(2,4)，因为它们，因为它们是必须出现的如果假设所有的边的方向是向上的，我们不必显示边的方是必须出现的如果假设所有的边的方向是向上的，我们不必显示边的方向；图向；图c c没有显示方向没有显示方向•我们可以使用下面的过程表示一个有穷集上的偏序我们可以使用下面的过程表示一个有穷集上的偏序 从这个关系的有向图开始：从这个关系的有向图开始： (1)(1)自反性：每个顶点都有自回路，省去。

自反性：每个顶点都有自回路，省去 (2)(2)反反对对称称性性：：两两个个顶顶点点间间只只可可能能有有一一个个箭箭头头从从左左→ → 右右，，或从下或从下→→上的方向从小到大安置顶点，可省略箭头上的方向从小到大安置顶点，可省略箭头 (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，则ａ，ｂ间用直线连，则ａ，ｂ间用直线连 接并符合简化的关系图的绘制，称这样得到关系图为接并符合简化的关系图的绘制，称这样得到关系图为 哈塞图（哈塞图（HasseHasse图）图）。

292024/8/14【【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所示【【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}). 最后，使所有的边方向向上并删除箭头。

得到哈塞图如下所最后，使所有的边方向向上并删除箭头得到哈塞图如下所示【【example】】：： Ａ＝｛１，２，３，４，５，６，７，８，９｝Ａ＝｛１，２，３，４，５，６，７，８，９｝ Ｂ＝｛ａ，ｂ，ｃ｝Ｂ＝｛ａ，ｂ，ｃ｝ ＲＲ1＝｛（ａ，ｂ）｜＝｛（ａ，ｂ）｜ ａａ≤ｂ，ａ，ｂｂ，ａ，ｂ∈∈Ａ｝Ａ｝ ＲＲ2＝｛（ａ，ｂ）｜＝｛（ａ，ｂ）｜ ａａ|ｂ，ａ，ｂｂ，ａ，ｂ∈∈Ａ｝Ａ｝ ＲＲ3＝｛＝｛(s1,s2)｜｜s1 s2，，s1，，s2∈ ∈p(B)｝｝求求R1, R2, R3 所表示关系的哈塞图所表示关系的哈塞图1 2 3 4 5 6 7 8 9 123456789ΦΦ{a}{b}{c}{a,b}{a,c}{a,c}{a,b,c}³具有极值性质的偏序集元素有许多重要应用具有极值性质的偏序集元素有许多重要应用³偏序集的一个元素叫做极大的，当它不小于这个偏序集的任偏序集的一个元素叫做极大的，当它不小于这个偏序集的任何其他元素即何其他元素即a在偏序集在偏序集（（S，， ≼ ≼ ）中是）中是极大的极大的，当不存，当不存在在b∈∈S使得使得a

即偏序集的任何其他元素即a在偏序集（在偏序集（S，， ≼ ≼ ）中是）中是极小极小的的，如果不存在，如果不存在b∈∈S使得使得b

元，又是极小元，如５，７极大元，极小元必须是子集Ａ中的元素极大元，极小元必须是子集Ａ中的元素23576489【【example 13】】偏序集（偏序集（{2，，4，，5，，10，，12，，20，，25}，，| ）的）的哪些元素时极大的，哪些是极小的？哪些元素时极大的，哪些是极小的？Solution：： 右图关于这个偏序集的哈塞图右图关于这个偏序集的哈塞图显示了极大元素是显示了极大元素是12，，20和和25，，极小元素时极小元素时2和和5³在偏序集中存在一个元素大于每个其他的元素，这样的元素在偏序集中存在一个元素大于每个其他的元素，这样的元素叫做最大元素，即叫做最大元素，即a a是偏序集（是偏序集（S S，， ≼ ≼ ）的）的最大元素最大元素，当对所，当对所有的有的b b∈∈S S有有b b ≼ ≼ a a当最大元素存在时它是唯一的当最大元素存在时它是唯一的³类似地，一个元素叫做最小元素，当它小于偏序集的所有其类似地，一个元素叫做最小元素，当它小于偏序集的所有其他元素即他元素即a a是偏序集（是偏序集（S S，， ≼ ≼ ）的）的最小元素最小元素，如果对所有的，如果对所有的b b∈∈S S有有a a ≼ ≼ b b。

当最小元素存在时它也是唯一的当最小元素存在时它也是唯一的402024/8/14[ [定义定义] ] 最大元素与最小元素：最大元素与最小元素： 设（设（S，， ≼ ≼ ）是偏序集，，若ａ）是偏序集，，若ａ∈∈Ａ，Ａ， ｂｂ∈∈Ａ，ｂＡ，ｂ≼ ≼ａａ(ａａ≼ ≼ｂ），则称ａ为Ａ的ｂ），则称ａ为Ａ的最大元素（最小元素）最大元素（最小元素）example】】上例中其上例中其Hasse图如下图所示图如下图所示23576489结论：结论：子集Ａ中是不存在最大元（最小元）的子集Ａ中是不存在最大元（最小元）的[定理定理] 是偏序集，是偏序集，B是是A的非空子集，如果的非空子集，如果B有最小元素有最小元素(最大元素最大元素)，则最小元素，则最小元素(最大元素最大元素)是唯一的是唯一的proof：： 假设假设B有两个最小元素有两个最小元素a、、b,则则 因为因为a是是最小元素，最小元素，b∈ ∈B，，根据根据最小元素定义，有最小元素定义，有a≼ ≼b; 类似地，因为类似地，因为b是是最小元素，最小元素，a∈ ∈B，根据，根据最小元素定义，有最小元素定义，有b≼ ≼a。

因为因为≼ ≼有反对称性，所以有有反对称性，所以有a=b 同理可证同理可证最大元素的唯一性最大元素的唯一性小结：小结： 是偏序集，是偏序集，B是是A的非空子集，则的非空子集，则 ⑴ ⑴ B B的的极小极小( (大大) )元素总是存在的，就是子集中处在最下元素总是存在的，就是子集中处在最下( (上上) )层层的元素是极小的元素是极小( (大大) )元素 ⑵ ⑵ B B的的最小元最小元( (最大元最大元) )素有时可能不存在，只要有唯一的极素有时可能不存在，只要有唯一的极小小( (大大) )元素，则这个极小元素，则这个极小( (大大) )元素就是最小元素就是最小( (大大) )元素否则元素否则就没有最小就没有最小( (大大) )元素【【example 14】】确定下图的每个哈塞图表示的偏序集是否有最确定下图的每个哈塞图表示的偏序集是否有最大元素和最小元素大元素和最小元素Solution：： 哈塞图哈塞图(a)的偏序集的最小元素时的偏序集的最小元素时a这个偏序集没有最大元这个偏序集没有最大元素 哈塞图哈塞图(b)的偏序集既没有最大元素也没有最小元素。

的偏序集既没有最大元素也没有最小元素 哈塞图哈塞图(c)的偏序集没有最小元素，它的最大元素时的偏序集没有最小元素，它的最大元素时d 哈塞图哈塞图(d)的偏序集有最小元素的偏序集有最小元素a和最大元素和最大元素d【【example15】】设设S是集合确定偏序集（是集合确定偏序集（P(S),   ）中是否存）中是否存在最大元素与最小元素在最大元素与最小元素Solution：： 最小元素时空集因为对于最小元素时空集因为对于S的任何子集的任何子集T,有有Φ  T，集合，集合S是是这个偏序集的最大元素，因为只要这个偏序集的最大元素，因为只要T是是S的子集，就有的子集，就有T   S462024/8/14【【example 16】】在偏序集（在偏序集（Z+, | ）中是否存在最大元素和）中是否存在最大元素和最小元素？最小元素？Solution：： 1是最小元素，因为只要是最小元素，因为只要n是正整数，就有是正整数，就有1|n因为没有被所有正整数整除的整数，所以不存在最大元素有被所有正整数整除的整数，所以不存在最大元素472024/8/14³有时可以找到一个元素大于偏序集（有时可以找到一个元素大于偏序集（S，， ≼ ≼ ）的子集）的子集A中所有中所有的元素。

如果的元素如果u是是S的元素使得对所有的元素的元素使得对所有的元素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，，s1∈∈P(B) }, (P(B),  )是偏序集是偏序集设设Ａ＝Ａ＝{Ф，，{a},{b},{c},{a,c},{a,b},{a,c}}其其HasseHasse图如右图所示图如右图所示: :ΦΦ{a}{b}{c}{a,b}{a,c}{b,c}注：注： （（1）上例中，Ａ无最大元素，但存在Ａ的上界）上例中，Ａ无最大元素，但存在Ａ的上界 ｛ａ，ｂ，ｃ｝。

｛ａ，ｂ，ｃ｝ （（2））Ф为Ａ的最小元，也是Ａ的下界为Ａ的最小元，也是Ａ的下界 （（3）最大（小）元素是Ａ的一个上（下）界最大（小）元素是Ａ的一个上（下）界 （（4）上（下）界可以不唯一，也可以不存在上（下）界可以不唯一，也可以不存在【【example 17】】找出下图所示哈塞图的偏序集的子集找出下图所示哈塞图的偏序集的子集{a, b, c}, {j, h}和和{a，，c，，d，，f}的下界和上界的下界和上界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³元素元素x叫做子集叫做子集A的的最小上界（上确界）最小上界（上确界），如果，如果x是一个上界并是一个上界并且它小于且它小于A的其他上界因为如果这样的元素存在，只存在一的其他上界因为如果这样的元素存在，只存在一个，称这个元素为最小上界（上确界）是有意义的即如果个，称这个元素为最小上界（上确界）是有意义的。

即如果只要只要a∈ ∈A就有就有a ≼ ≼ x，并且只要，并且只要z是是A的上界，就有的上界，就有x ≼ ≼ z, x就是就是A的最小上界（上确界）的最小上界（上确界）³类似地，如果类似地，如果y是是A的下界，并且只要的下界，并且只要z是是A的下界，就有的下界，就有z ≼ ≼ y，，y就是就是A的的最大下界（下确界）最大下界（下确界）A的最大下界（下确界）的最大下界（下确界）如果存在也是唯一的如果存在也是唯一的³一个子集一个子集A的最大下界（下确界），和最小上界（上确界），的最大下界（下确界），和最小上界（上确界），分别记作分别记作 glb ( A )和和 lub ( A ).[ [定义定义] ]上确界与下确界：上确界与下确界： 设（设（S，，≤）是偏序集，）是偏序集，A S，若，若a是是A的一个上界的一个上界（下界），而（下界），而 A的上界（下界）的上界（下界）z，都有，都有a ≤ b（（b ≤ a）），则称，则称a是是A的的上确界（下确界）上确界（下确界）【【example】】给定（给定（A,≤）的哈塞）的哈塞图如图所示：图如图所示：６６ °１１ °３３ °12 ° ２２°36 ° 24 °子集子集B上界上界下界下界{2,3}{1,2,3}{6,12,24}C 16,12,24,361241,2,3,61无无6,12,24,36上确界上确界下确界下确界6624无无1161【【example 18】】在下图所示偏序集中如果在下图所示偏序集中如果{b，，d，，g}的最大下界的最大下界和最小上界存在，求出这个最大下界和最大上界。

和最小上界存在，求出这个最大下界和最大上界【【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}的最大下界的最大下界求最小上界：求最小上界： 一个整数是一个整数是 {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}的的最小上界最小上界五、格五、格 在这里我们引入格的概念在这里我们引入格的概念1.定义：定义：设设 X,≼ ≼ 是偏序集，如果是偏序集，如果 x, y   X，集合，集合{ x, y }都有都有 最小上界和最大下界，则称最小上界和最大下界，则称 X,≼ ≼ 是格example 20】】确定如下图所示的每个哈塞图表示的偏序集是确定如下图所示的每个哈塞图表示的偏序集是否是格否是格 Solution：： 图图a和和c中的哈塞图表示的偏序集是格因为在每个偏序集中中的哈塞图表示的偏序集是格因为在每个偏序集中每对元素都有最小上界和最大下界每对元素都有最小上界和最大下界。

另一方面，图另一方面，图b所示的哈塞图的偏序集不是格，因为元素所示的哈塞图的偏序集不是格，因为元素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,10｝｝Solution：： ⑴⑴不是，因为不是，因为L中的元素对中的元素对{2,3}没有最小上界；没有最小上界； ⑵⑵是，因为是，因为L=｛｛1,2,3,4,6,9,12,18,36｝任何一对元素｝任何一对元素a,b，都有，都有最小上界和最大下界；最小上界和最大下界； ⑶⑶是，与是，与⑵⑵同理；同理； ⑷⑷不是，因为不是，因为L中的元素对中的元素对{6,7}没有最小上界不存在最小上界没有最小上界不存在最小上界.【【example】】下图中给出了一些偏序集的哈斯图，判断它们是否下图中给出了一些偏序集的哈斯图，判断它们是否构成格。

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

因此第一个偏序集不是格当然没有最小上界因此第一个偏序集不是格 第二个偏序集的每两个元素都有最小上界和最大下界在第二个偏序集的每两个元素都有最小上界和最大下界在这个偏序集中两个元素的最小上界是他们中间较大的元素，这个偏序集中两个元素的最小上界是他们中间较大的元素，而两个元素的最大下界是它们中间较小的元素因此第二个而两个元素的最大下界是它们中间较小的元素因此第二个偏序集是格偏序集是格【【example 23】】确定（确定（P(S),   ）是否为格，其中）是否为格，其中S是集合Solution：： 设设A和和B是是S的两个子集，的两个子集，A和和B的最小上界和最大下界分别是的最小上界和最大下界分别是A∪ ∪B和和A ∩ B，因此（，因此（P(S),   ）是格【【example 24】】信息流的格模式信息流的格模式 在许多设置中，从一个人或在许多设置中，从一个人或计算机程序到另一个人或计算机程序的信息流要受到限制，这可计算机程序到另一个人或计算机程序的信息流要受到限制，这可以通过安全权限来实现我们可以使用格的模型来表示不同的信以通过安全权限来实现我们可以使用格的模型来表示不同的信息流策略。

息流策略 例如，一个通用的信息流策略适用于政府或军事系统中的例如，一个通用的信息流策略适用于政府或军事系统中的多多级安全策略级安全策略为，诶组信息分配一个安全级别，并且每个安全级为，诶组信息分配一个安全级别，并且每个安全级别用一个对（别用一个对（A, C）表示，其中）表示，其中A是权限级别，是权限级别，C是种类然后是种类然后允许人和计算机程序从一个被特别限制的安全类的集合中访问信允许人和计算机程序从一个被特别限制的安全类的集合中访问信息 在美国政府中，使用的典型的权限级别是不保密（在美国政府中，使用的典型的权限级别是不保密（0）、秘密）、秘密（（1）、机密（）、机密（2）和绝密（）和绝密（3）在安全级别中使用的种类是一）在安全级别中使用的种类是一个集合的子集，这个集合含有与一个特定行业领域相关的所有的个集合的子集，这个集合含有与一个特定行业领域相关的所有的分部，每个分部表示一个指定的对象域分部，每个分部表示一个指定的对象域 例如，如果分部的集合是例如，如果分部的集合是{间谍，鼹鼠双重间谍间谍，鼹鼠双重间谍}，那么存，那么存在在8个不同的种类，分部集合有个不同的种类，分部集合有8个子集，对于每个子集有一类个子集，对于每个子集有一类，例如，例如{间谍，鼹鼠间谍，鼹鼠}。

 我们可以对安全类排序，规定（我们可以对安全类排序，规定（A1,C1））≼ ≼ （（A2,C2）当且仅当）当且仅当A1 ≤ A2和和C1 ≤ C2.信息允许从安全类（信息允许从安全类（A1,C1））流向安全类流向安全类（（A2,C2）当且仅当（）当且仅当（A1,C1）） ≼ ≼ （（A2,C2）） 例如，信息允许从安全类（机密，例如，信息允许从安全类（机密，{间谍，鼹鼠间谍，鼹鼠}）流向安全）流向安全类（绝密，类（绝密，{间谍，鼹鼠，双重间谍间谍，鼹鼠，双重间谍}），反之，信息不允许从安），反之，信息不允许从安全类（绝密，全类（绝密，{间谍，鼹鼠间谍，鼹鼠}）流向安全类（机密，）流向安全类（机密，{间谍，鼹鼠间谍，鼹鼠，双重间谍，双重间谍}）或（绝密，）或（绝密，{间谍间谍}）六、拓扑排序六、拓扑排序³假设一个项目由假设一个项目由2020个任务构成某些任务只能在其他任务结个任务构成某些任务只能在其他任务结束之后完成，如何找到关于这些任务的顺序？束之后完成，如何找到关于这些任务的顺序？ 为了对这个问题构造模型，我们建立一个任务集合上的偏序，为了对这个问题构造模型，我们建立一个任务集合上的偏序，使得使得a

为安才能开始为安排好这个项目，需要得出与这个偏序相容的所有排好这个项目，需要得出与这个偏序相容的所有2020个任务的顺个任务的顺序我们将说明怎样做到这一点我们将说明怎样做到这一点³从定义开始，如果只要从定义开始，如果只要aRb就有就有a ≼ ≼b,则称一个全序则称一个全序≼ ≼与偏序与偏序R 是是相容的相容的从一个偏序构造一个相容的全序叫做从一个偏序构造一个相容的全序叫做拓扑排序拓扑排序需要使用引理要使用引理1.引理引理1：：每个有穷非空偏序集（每个有穷非空偏序集（S, ≼ ≼ ）都有极小元素都有极小元素Proof：： 选择选择S的一个元素的一个元素a0. 如果如果a0不是绩效元素，那么存在元素不是绩效元素，那么存在元素a1, 满足满足a1 < a0.如果如果a1不是极小元素，那么存在元素不是极小元素，那么存在元素a2,满足满足a2 < a1.继续这一过程，使得如果继续这一过程，使得如果an不是极小元素，那么存在元素不是极小元素，那么存在元素an+1满满足足an+1

接着，这样的元素存在接着，{A-{a1}，， ≼ ≼}也是一个也是一个偏序集如果它是非空的，选择这个偏序集的一个极小元素偏序集如果它是非空的，选择这个偏序集的一个极小元素a2.然后再取走然后再取走a2，如果还有其他的元素留下来，在，如果还有其他的元素留下来，在{ A - {a1, a2} }中中选择一个极小元素选择一个极小元素a3继续这个过程，只要还有元素留下来，就继续这个过程，只要还有元素留下来，就在在{ A - {a1, a2, …, ak } }中选择一个极小元素中选择一个极小元素ak+1. 因为因为A是有穷集，这个过程一定终止最终产生一个元素序是有穷集，这个过程一定终止最终产生一个元素序列列a1,a2,…, an.所需要的全序定义为所需要的全序定义为a1 ≼ ≼a2 ≼ ≼.. ≼ ≼an这个全序是与初始的偏序相容的为看出这一点，注意如果在这个全序是与初始的偏序相容的为看出这一点，注意如果在初始的偏序中初始的偏序中b

关于这个拓扑排序算法的伪代码在算法关于这个拓扑排序算法的伪代码在算法1中给出【【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作为最后的元素。

作为最后的元素 产生的全序是产生的全序是1<5<2<4<20<12这个排序算法所使用的步骤在下图中给出这个排序算法所使用的步骤在下图中给出³在项目的安排中常会用到拓扑排序在项目的安排中常会用到拓扑排序example 26】】一个计算机公司的来发项目需要完成一个计算机公司的来发项目需要完成7个任务其中某些任务只能在其他任务结束后才能开始考虑如下建立任其中某些任务只能在其他任务结束后才能开始考虑如下建立任务上的偏序，如果任务务上的偏序，如果任务Y在在X结束后才能开始，则任务结束后才能开始，则任务X<任务任务Y这7个任务关于这个偏序的哈塞图如下示求一个全序，使得个任务关于这个偏序的哈塞图如下示求一个全序，使得可以按照这个全序执行这些任务以完成这个项目可以按照这个全序执行这些任务以完成这个项目Solution：： 可以通过执行一个拓扑排序得到可以通过执行一个拓扑排序得到7个任务的排序排序的步骤个任务的排序排序的步骤显示在下图中显示在下图中 这个排序的结果，这个排序的结果，A

可以得到满足自反、反对称和传递性质的关系才是偏序关系可以得到 a) 是偏序集是偏序集 b) 不是偏序集因为它不满足上面三个性质中的任何一个不是偏序集因为它不满足上面三个性质中的任何一个 c) 是偏序集是偏序集 d) 不是偏序集因为它不是自反的不是偏序集因为它不是自反的Solution：2.2. 确定由线面的确定由线面的0-1矩阵表示的关系是否为偏序矩阵表示的关系是否为偏序3. 确定以下确定以下3个有向图所表示的关系是否为偏序？个有向图所表示的关系是否为偏序？4. 找出下面英语字母串的字典顺序找出下面英语字母串的字典顺序本节内容到此结束本节内容到此结束。