1、1离散数学Discrete Mathematics 1/87&学习内容学习内容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 偏序偏序偏序偏序2/87&偏序偏序一、偏序一、偏序 定义定义1：集合集合S上关系上关系R，假如它是自反、反对称，假如它是自反、反对称 和传递，就称为和传递，就称为偏序偏序。集合集合S与偏序与
2、偏序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】整除关系整除关系“|”是正整数集合
3、上偏序，因为由前是正整数集合上偏序，因为由前几节所述，它是自反、反对称和传递。我们看到几节所述，它是自反、反对称和传递。我们看到（Z+,|）是偏序集（）是偏序集（Z+表示正整数集合）。表示正整数集合）。5/87【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)，）是偏序集。）
4、是偏序集。6/87在任意一个偏序集中记号在任意一个偏序集中记号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,）元素时，不一定有）元素时，不一定有a b 或或b c。比如，在（比如，在（P(Z),P(Z),）
5、中）中,1,2,1,2与与1,31,3没相关系，反之亦然，因为没相关系，反之亦然，因为没有一个集合被另一个集合包含。类似地在没有一个集合被另一个集合包含。类似地在(Z,|)(Z,|)中，中，2 2与与3 3没关系，没关系，3 3与与2 2也没关系。由此得到定义也没关系。由此得到定义2.2.7/87定义定义2 2：偏序集：偏序集(S,)元素元素a和和b叫做叫做可比可比，假如，假如a b 或或 b a。当。当a和和b是是S元素而且既没有元素而且既没有a b，也没，也没 有有b a，则称，则称a与与b是是不可比不可比。【example 4】在偏序集在偏序集(Z+,)中，整数中，整数3和和9是可比吗？
6、是可比吗？5和和7是可比吗？是可比吗？整数整数3和和9是可比，因为是可比，因为3|9.整数整数5和和7是不可比，因为是不可比，因为5不能整除不能整除7，而且，而且7也不能整除也不能整除5.8/87用形容词用形容词“部分（偏）部分（偏）”描述偏序是因为一些对元素描述偏序是因为一些对元素可能是不可比。当集合中每对元素都可比时，这个关可能是不可比。当集合中每对元素都可比时，这个关系叫做系叫做全序全序。定义定义3：假如假如(S,)是偏序集，且是偏序集，且S每对元素都是可比，每对元素都是可比，则则S叫做叫做全序集全序集或或线序集线序集，且，且 叫做叫做全序全序或或线序线序。一。一个全序集也叫做个全序集也
7、叫做链链。9/87【example 5】偏序集偏序集(Z,)是全序集，因为只要是全序集，因为只要a和和b是整数是整数，就有，就有a b或或b a。【example 6】偏序集偏序集(Z+,|)不是全序集，因为它包含着不可不是全序集，因为它包含着不可比元素，比如比元素，比如5和和7.10/87定义定义4 4：对于偏序集对于偏序集(S,)，假如，假如 是全序，而且是全序，而且S每每 个非空子集都有一个最小元素，就称它为个非空子集都有一个最小元素，就称它为良序集良序集。For example，N是自然数集合，是自然数集合，I是整数集合，是整数集合，是小于等于关系，是小于等于关系，就是就是良序集。而良
8、序集。而不是良序集。不是良序集。11/87定理定理 全部全部良序集，一定是全序集。良序集，一定是全序集。Proof：设设为良序集为良序集,任取任取x,y A,则则x,y A,它有最小它有最小元素。该最小元素或是元素。该最小元素或是x,或是或是y。于是有于是有x y或或 y x，所以所以是全序集。是全序集。12/87定理定理 有限有限全序集，一定是良序集。全序集，一定是良序集。Proof：设设A=a1,a2,，an,是全序集。是全序集。假设它不是良序，必存在非空子集假设它不是良序，必存在非空子集B A，B中无最小元素，中无最小元素，因因B是有限集，必存在是有限集，必存在x,y B,使得使得x与与
9、y之间不满足之间不满足关系关系,与与是全序矛盾。是全序矛盾。是良序集。是良序集。13/87【example 7】正整数有序正确集合正整数有序正确集合Z+Z+与与 组成组成良序集，对于良序集，对于(a1,a2)和和(b1,b2),假如假如a1b1,或假如或假如a1=b1且且a2 b2（字典次序），则（字典次序），则(a1,a2)(b1,b2).14/87在前几章学习中我们现实了怎样使用良序归纳标准证实关于在前几章学习中我们现实了怎样使用良序归纳标准证实关于一个良序集结果。现在我们叙述并证实这个证实技术是有效。一个良序集结果。现在我们叙述并证实这个证实技术是有效。定理定理1 良序归纳原理良序归纳原
10、理 设设S是一个良序集，假如下述条件成立：是一个良序集，假如下述条件成立：基础步基础步：P(x0)对对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不等于不等于x0,因为从因为从基础步知道
11、基础步知道P(x0)为真。为真。依据依据a是选自是选自A最小元素，我们知道对全部最小元素，我们知道对全部x S(xaa)都都有有P(x)为真。由归纳步这就能够退出为真。由归纳步这就能够退出P(a)为真。为真。这个矛盾就证实了这个矛盾就证实了P(x)必须对全部必须对全部x S 为真。为真。16/87二、字典次序二、字典次序字典次序字典次序是以字母表中字母次序为基础。这是从一个集是以字母表中字母次序为基础。这是从一个集合上偏序结构一个集合上串序特殊情况。我们将说明这合上偏序结构一个集合上串序特殊情况。我们将说明这种结构在任一个偏序集上是怎么做。种结构在任一个偏序集上是怎么做。17/87首先，我们将
12、说明怎样在两个偏序集首先，我们将说明怎样在两个偏序集(A1,1)和和(A2,2)笛笛卡尔积上结构一个偏序。卡尔积上结构一个偏序。在在A1A2上字典次序定义以下：假如第一个正确第一个上字典次序定义以下：假如第一个正确第一个元素（在元素（在A1中）小于第二个正确第一个元素，或者第一个元中）小于第二个正确第一个元素，或者第一个元素相等，不过第一个正确第二个元素（在素相等，不过第一个正确第二个元素（在A2中）小于第二个中）小于第二个正确第二个元素，那么第一个对小于第二个对。换句话说，正确第二个元素，那么第一个对小于第二个对。换句话说，(a1,a2)小于小于(b1,b2),即即(a1,a2)(b1,b2
13、)或者或者a11b1,或者或者a1=b1且且a22b2.把相等加到把相等加到A1A2上序就得到偏序上序就得到偏序。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)
14、小有序正确集合。小有序正确集合。19/8720/87能够在能够在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元组元素小于第二个元组元素小于第二个n元组元素，那么第一个元组元素，那么第一个n元组小元组小于第二个于第二个n元组。元组。21/87【example
15、9】注意（注意（1，2，3，5）（1，2，4，3），因为这），因为这些些4元组前两位相同，不过第一个元组前两位相同，不过第一个4元组第三位元组第三位3小于第二个小于第二个4元组第三位元组第三位4（这里（这里4元组上字典次序是整数集合上通元组上字典次序是整数集合上通常常“小于或等于小于或等于”关系导出字典次序）。关系导出字典次序）。22/87我们现在能够定义串上字典次序。考虑偏序集我们现在能够定义串上字典次序。考虑偏序集S上串上串a1a2an和和b1b2bn,假定这些串不相等。设假定这些串不相等。设t是是m，n中较小数。中较小数。定义字典次序以下：定义字典次序以下：a1a2an小于小于b1b2b
16、n,当且仅当当且仅当（a1a2at）（b1b2bt）或者或者（a1a2at）=（b1b2bt）而且）而且mn 其中这个不等式中其中这个不等式中表示表示St中字典次序。换句话说，为确定两中字典次序。换句话说，为确定两个不一样串序，较长串被切到较短串长度个不一样串序，较长串被切到较短串长度t，即，即t=min(m,n)然然后使用后使用St上字典次序比较每个船前上字典次序比较每个船前t为组成为组成t元组，假如对应于元组，假如对应于第一个串第一个串t元组小于第二个串元组小于第二个串t元组，或者这两个元组，或者这两个t元组相等，不过元组相等，不过第二个串更长，那么第一个串小于第二个串。第二个串更长，那么
17、第一个串小于第二个串。23/87【example 10】考虑小写英语字母串组成集合。使用在字母表考虑小写英语字母串组成集合。使用在字母表中字母序，能够组成在串集合上字典次序。中字母序，能够组成在串集合上字典次序。假如两个串第一次出现不一样字母时，第一个串字母先于第假如两个串第一次出现不一样字母时，第一个串字母先于第二个字母，或者假如第一个串和第二个串在全部位都相同，不二个字母，或者假如第一个串和第二个串在全部位都相同，不过第二个串有更多字母，那么，第一个串小于第二个串。这种过第二个串有更多字母，那么，第一个串小于第二个串。这种排序和字典使用排序相同。比如排序和字典使用排序相同。比如 discr
18、eet discrete因为这两个串在第因为这两个串在第7位首次出现字母，而且位首次出现字母，而且 e t.discreet discreetness因为这两个串前因为这两个串前8个字母相同，不过第二个串更长。另外个字母相同，不过第二个串更长。另外 discrete discretion24/87在有穷偏序集有向图中有许多能够无须显示出来，因为他们在有穷偏序集有向图中有许多能够无须显示出来，因为他们是必须存在。是必须存在。比如，考虑在集合比如，考虑在集合11，2 2，3 3，44上偏序上偏序(a,b)|a(a,b)|a bb有向图，参见图有向图，参见图a a。因为这个关系是偏序，它是自反而且有
19、向图在全部顶点都有环，所以，我因为这个关系是偏序，它是自反而且有向图在全部顶点都有环，所以，我们无须显示这些环，因为它们是必须出现。在图们无须显示这些环，因为它们是必须出现。在图b b中没有显示这些环。因中没有显示这些环。因为一个偏序是传递，我们无须显示那些因为传递性而必须出现边。比如，为一个偏序是传递，我们无须显示那些因为传递性而必须出现边。比如，在图在图c c中没有显示边中没有显示边(1,3),(1,4)(1,3),(1,4)和和(2,4)(2,4)，因为它们是必须出现。假如假，因为它们是必须出现。假如假设全部边方向是向上，我们无须显示边方向；图设全部边方向是向上，我们无须显示边方向；图c
20、 c没有显示方向。没有显示方向。25/8726/87我们能够使用下面过程表示一个有穷集上偏序。我们能够使用下面过程表示一个有穷集上偏序。从这个关系有向图开始：从这个关系有向图开始：(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
21、)(b,c)对应边对应边,省略边省略边(a,c)(a,c)。27/87哈塞图（哈塞图（Hasse 图）图）定义：定义：设设 是上一个偏序关系，假如是上一个偏序关系，假如a a b b，则将画在，则将画在 下面，且不下面，且不，使，使a a c c，c c b b，则，间用直线连，则，间用直线连 接。并符合简化关系图绘制，称这么得到关系图为接。并符合简化关系图绘制，称这么得到关系图为 哈塞图（哈塞图（HasseHasse图）图）。28/87292024/9/29【example 11】画出表示画出表示1，2，3，4，6，8，12上偏序上偏序(a,b)|a 整除整除b哈塞图。哈塞图。Solutio
22、n：由这个偏序有向图开始，以下列图由这个偏序有向图开始，以下列图a所表示。移走全部环，所表示。移走全部环，以下列图以下列图b所表示，然后删去全部由传递性导出边。这些边是所表示，然后删去全部由传递性导出边。这些边是(1,4),(1,6),(1,8),(1,12),(2,8),(3,12).排列全部边使得方向向上排列全部边使得方向向上，而且删除全部箭头得到哈塞图。结果如图，而且删除全部箭头得到哈塞图。结果如图c所表示。所表示。29/8730/87【example 12】画出幂集画出幂集P(S)上偏序上偏序(A,B)|A B哈塞哈塞 图，其中图，其中S=a,b,c.Solution:关于这个偏序哈塞
23、图是由相关有向图得到，先删除所关于这个偏序哈塞图是由相关有向图得到，先删除所有环和全部由传递性产生边，即有环和全部由传递性产生边，即(,a,b),(,a,c),(,b,c),(,a,b,c),(a,a,b,c),(b,a,b,c)和和(c,a,b,c).最终，使全部边方向向上并删除箭头。得到哈塞图以下所最终，使全部边方向向上并删除箭头。得到哈塞图以下所示。示。31/8732/87【example】：，1（，）（，），2（，）（，）|，3(s1,s2)s1 s2，s1，s2 p(B)求求R1,R2,R3 所表示关系哈塞图。所表示关系哈塞图。33/871 2 3 4 5 6 7 8 9 12345
24、6789abca,ba,ca,ca,b,c34/87含有极值性质偏序集元素有许多主要应用。含有极值性质偏序集元素有许多主要应用。偏序集一个元素叫做极大，当它大于这个偏序集任何其它元偏序集一个元素叫做极大，当它大于这个偏序集任何其它元素。即素。即a在偏序集在偏序集（S，）中是）中是极大极大，当不存在，当不存在bS使得使得ab.类似地，偏序集一个元素叫做极小，假如它小于这个偏序集类似地，偏序集一个元素叫做极小，假如它小于这个偏序集任何其它元素。即任何其它元素。即a在偏序集（在偏序集（S，）中是）中是极小极小，假如不，假如不存在存在bS使得使得ba。使用哈塞图很轻易是识别极大元素和极小元素。它们是图
25、中使用哈塞图很轻易是识别极大元素和极小元素。它们是图中“顶顶”元素与元素与“底底”元素。元素。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/87【example】（N，|）是偏序集，是偏序集，A=2，3，4，5，6，7，8，9则则 中极大元素：，中极大元素：，极
26、小元素：，极小元素：，注：注：极极大大元元，极极小小元元并并不不要要求求唯唯一一，且且同同一一元元素素，能能够够既既是是极极大大元，又是极小元，如，。元，又是极小元，如，。极大元，极小元必须是子集中元素。极大元，极小元必须是子集中元素。2357648937/87【example 13】偏序集（偏序集（2，4，5，10，12，20，25，|）哪些元素时极大，哪些是极小？哪些元素时极大，哪些是极小？Solution：右图关于这个偏序集哈塞图右图关于这个偏序集哈塞图显示了极大元素是显示了极大元素是12，20和和25，极小元素时极小元素时2和和5。38/87在偏序集中存在一个元素大于每个其它元素，这么
27、元素叫做在偏序集中存在一个元素大于每个其它元素，这么元素叫做最大元素，即最大元素，即a a是偏序集（是偏序集（S S，）最大元素最大元素，当对全部，当对全部b bS S有有b b a a。当最大元素存在时它是唯一。当最大元素存在时它是唯一。类似地，一个元素叫做最小元素，当它小于偏序集全部其它类似地，一个元素叫做最小元素，当它小于偏序集全部其它元素。即元素。即a a是偏序集（是偏序集（S S，）最小元素最小元素，假如对全部，假如对全部b bS S有有a a b b。当最小元素存在时它也是唯一。当最小元素存在时它也是唯一。39/87402024/9/29 定定义最大元素与最小元素：最大元素与最小元
28、素：设（设（S，）是偏序集，若）是偏序集，若，(），则称为），则称为最大元素（最小元素）最大元素（最小元素）。【example】上例中其上例中其Hasse图以下列图所表示图以下列图所表示23576489结论：结论：子集中是不存在最大元（最小元）。子集中是不存在最大元（最小元）。40/87定理定理 是偏序集，是偏序集，B是是A非空子集，假如非空子集，假如B有最小元素有最小元素(最最大元素大元素)，则最小元素，则最小元素(最大元素最大元素)是唯一。是唯一。proof：假设假设B有两个最小元素有两个最小元素a、b,则则 因为因为a是是最小元素，最小元素，b B，依据依据最小元素定义，有最小元素定义，
29、有a b;类似地，因为类似地，因为b是是最小元素，最小元素，a B，依据，依据最小元素定义，有最小元素定义，有b a。因为。因为 有反对称性，所以有有反对称性，所以有a=b。同理可证同理可证最大元素唯一性。最大元素唯一性。41/87小结：小结：是偏序集，是偏序集，B是是A非空子集，则非空子集，则 B B极小极小(大大)元素总是存在，就是子集中处于最下元素总是存在，就是子集中处于最下(上上)层元素层元素是极小是极小(大大)元素。元素。B B最小元最小元(最大元最大元)素有时可能不存在，只要有唯一极小素有时可能不存在，只要有唯一极小(大大)元素，则这个极小元素，则这个极小(大大)元素就是最小元素就
30、是最小(大大)元素。不然就没有元素。不然就没有最小最小(大大)元素。元素。42/87【example 14】确定下列图每个哈塞图表示偏序集是否有最确定下列图每个哈塞图表示偏序集是否有最大元素和最小元素。大元素和最小元素。43/87Solution：哈塞图哈塞图(a)偏序集最小元素时偏序集最小元素时a。这个偏序集没有最大元。这个偏序集没有最大元素。素。哈塞图哈塞图(b)偏序集既没有最大元素也没有最小元素。偏序集既没有最大元素也没有最小元素。哈塞图哈塞图(c)偏序集没有最小元素，它最大元素时偏序集没有最小元素，它最大元素时d。哈塞图哈塞图(d)偏序集有最小元素偏序集有最小元素a和最大元素和最大元素
31、d。44/87【example15】设设S是集合。确定偏序集（是集合。确定偏序集（P(S),）中是否存）中是否存在最大元素与最小元素。在最大元素与最小元素。Solution：最小元素时空集。因为对于最小元素时空集。因为对于S任何子集任何子集T,有有 T，集合，集合S是是这个偏序集最大元素，因为只要这个偏序集最大元素，因为只要T是是S子集，就有子集，就有T S。45/87462024/9/29【example 16】在偏序集（在偏序集（Z+,|）中是否存在最大元素和）中是否存在最大元素和最小元素？最小元素？Solution：1是最小元素，因为只要是最小元素，因为只要n是正整数，就有是正整数，就有
32、1|n。因为没。因为没有被全部正整数整除整数，所以不存在最大元素。有被全部正整数整除整数，所以不存在最大元素。46/87472024/9/29有时能够找到一个元素大于偏序集（有时能够找到一个元素大于偏序集（S，）子集）子集A中全部元中全部元素。假如素。假如u是是S元素使得对全部元素元素使得对全部元素a A,有有a u，那么，那么u叫做叫做A一个上界一个上界。也可能存在一个元素小于也可能存在一个元素小于A中全部其它元素。假如中全部其它元素。假如l是是S一个元一个元素使得对全部元素素使得对全部元素a A,有有l a，那么，那么l叫做叫做A一个下界一个下界。47/87 定定义 上界与下界：上界与下界
33、：设（设（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),)是偏序集。是偏序集。设设，a,b,c,a,c,a,b,a,c其其HasseHasse图如右图所表示图如右图所表示:abca,ba,cb,c48/87注：注：（1）上例中，无最大元素，但存在上界）上例中，无最大元素，但存在上界 ，。，。（2）为最小元，也是下界。为最小元，也是下界。（3）最大（小）元素是一个上（下）界。）最大（小）元素是一个上（下）界。（4）上（下）界能
34、够不唯一，也能够不存在。）上（下）界能够不唯一，也能够不存在。49/87【example 17】找出下列图所表示哈塞图偏序集子集找出下列图所表示哈塞图偏序集子集a,b,c,j,h和和a，c，d，f下界和上界。下界和上界。50/87Solution：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其它上界。因为假如
35、这么元素存在，只存在一个，称其它上界。因为假如这么元素存在，只存在一个，称这个元素为最小上界（上确界）是有意义。即假如只要这个元素为最小上界（上确界）是有意义。即假如只要a A就有就有a x，而且只要，而且只要z是是A上界，就有上界，就有x z,x就是就是A最小上界最小上界（上确界）。（上确界）。类似地，假如类似地，假如y是是A下界，而且只要下界，而且只要z是是A下界，就有下界，就有z y，y就是就是A最大下界（下确界）最大下界（下确界）。A最大下界（下确界）假如存在最大下界（下确界）假如存在也是唯一。也是唯一。一个子集一个子集A最大下界（下确界），和最小上界（上确界），分最大下界（下确界），
36、和最小上界（上确界），分别记作别记作 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,31,2,36,12,24C 16,12,24,361241,2,3,61无无6,12,24,36上确界上确界下确界下确界6624无无
37、116154/87【example 18】在下列图所表示偏序集中假如在下列图所表示偏序集中假如b，d，g最大下最大下界和最小上界存在，求出这个最大下界和最大上界。界和最小上界存在，求出这个最大下界和最大上界。55/87【example 19】在偏序集（在偏序集（Z+,|）中，假如集合）中，假如集合3，9，12和和1，2，4，5，10最大下界和最小上界存在，求出这些最大最大下界和最小上界存在，求出这些最大下界和最小上界。下界和最小上界。Solution：求最大下界：求最大下界：假如假如3，9，12被一个整数整除，那么这个整数就是被一个整数整除，那么这个整数就是3，9，12下界。这么整数只有下界。
38、这么整数只有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整除，
39、含有这种性质整数就是被这些整数最整除，含有这种性质整数就是被这些整数最小公倍数小公倍数20整除整数。所以，整除整数。所以，20是集合是集合1，2，4，5，10最小上界。最小上界。57/87五、格五、格 在这里我们引入格概念。在这里我们引入格概念。1.定义：定义：设设 X,是偏序集，假如是偏序集，假如 x,y X，集合，集合 x,y 都有都有 最小上界和最大下界，则称最小上界和最大下界，则称 X,是格。是格。【example 20】确定以下列图所表示每个哈塞图表示偏序集是确定以下列图所表示每个哈塞图表示偏序集是否是格否是格 58/87Solution：图图a和和c中哈塞图表示偏序集是格。因为在每
40、个偏序集中中哈塞图表示偏序集是格。因为在每个偏序集中每对元素都有最小上界和最大下界。每对元素都有最小上界和最大下界。另首先，图另首先，图b所表示哈塞图偏序集不是格，因为元素所表示哈塞图偏序集不是格，因为元素b和和c没有最小上界。为此只要注意到没有最小上界。为此只要注意到d，e和和f中每一个都是上界，但中每一个都是上界，但这这3个元素任何一个关于这个偏序集中序都小于其它个元素任何一个关于这个偏序集中序都小于其它2个个.59/87【example】以下各集合对于整除关系都组成偏序集以下各集合对于整除关系都组成偏序集,判断哪些判断哪些偏序集是格偏序集是格?L=1,2,3,4,5；L=1,2,3,4,
41、6,9,12,18,36；L=1,2,22,2n；L=1,2,3,4,5,6,7,8,9,1060/87Solution：不是，因为不是，因为L中元素对中元素对2,3没有最小上界；没有最小上界；是，因为是，因为L=1,2,3,4,6,9,12,18,36任何一对元素任何一对元素a,b，都有，都有最小上界和最大下界；最小上界和最大下界；是，与是，与同理；同理；不是，因为不是，因为L中元素对中元素对6,7没有最小上界不存在最小上界没有最小上界不存在最小上界.61/87【example】下列图中给出了一些偏序集哈斯图，判断它们是否下列图中给出了一些偏序集哈斯图，判断它们是否组成格。组成格。62/87
42、Solution：它们都不是格。它们都不是格。在在(a)中，中，1,2没有下界，因而没有最大下界。没有下界，因而没有最大下界。在在(b)中，中，2,4虽有两个上界，但没有最小上界。虽有两个上界，但没有最小上界。在在(c)中，中，1,3没有下界，因而没有最大下界。没有下界，因而没有最大下界。在在(d)中，中，2,3虽有三个上界，但没有最小上界。虽有三个上界，但没有最小上界。63/87【example 21】偏序集（偏序集（Z+,|）是格吗？）是格吗？Solution：设设a和和b是两个正整数，这两个整数最小上界和最大下界分是两个正整数，这两个整数最小上界和最大下界分别是它们最小公倍数和最大条约数
43、，所以这个偏序集是格。别是它们最小公倍数和最大条约数，所以这个偏序集是格。64/87【example 22】确定偏序集（确定偏序集（1，2，3，4，5，|）和）和（1，2，4，8，16，|）是否为格？）是否为格？Solution：因为因为2和和3在（在（1，2，3，4，5，|）中没有上界，它们）中没有上界，它们当然没有最小上界。所以第一个偏序集不是格。当然没有最小上界。所以第一个偏序集不是格。第二个偏序集每两个元素都有最小上界和最大下界。在第二个偏序集每两个元素都有最小上界和最大下界。在这个偏序集中两个元素最小上界是他们中间较大元素，这个偏序集中两个元素最小上界是他们中间较大元素，而两个元素最
44、大下界是它们中间较小元素。所以第二个而两个元素最大下界是它们中间较小元素。所以第二个偏序集是格。偏序集是格。65/87【example 23】确定（确定（P(S),）是否为格，其中）是否为格，其中S是集合。是集合。Solution：设设A和和B是是S两个子集，两个子集，A和和B最小上界和最大下界分别是最小上界和最大下界分别是A B和和A B，所以（，所以（P(S),）是格。）是格。66/87【example 24】信息流格模式信息流格模式 在许多设置中，从一个人或在许多设置中，从一个人或计算机程序到另一个人或计算机程序信息流要受到限制，这可计算机程序到另一个人或计算机程序信息流要受到限制，这可
45、以经过安全权限来实现。我们能够使用格模型来表示不一样信以经过安全权限来实现。我们能够使用格模型来表示不一样信息流策略。息流策略。比如，一个通用信息流策略适合用于政府或军事系统中比如，一个通用信息流策略适合用于政府或军事系统中多多级安全策略级安全策略。为，诶组信息分配一个安全级别，而且每个安全级。为，诶组信息分配一个安全级别，而且每个安全级别用一个对（别用一个对（A,C）表示，其中）表示，其中A是权限级别，是权限级别，C是种类。然后是种类。然后允许人和计算机程序从一个被尤其限制安全类集合中访问信允许人和计算机程序从一个被尤其限制安全类集合中访问信息。息。67/87 在美国政府中，使用经典权限级别
46、是不保密（在美国政府中，使用经典权限级别是不保密（0）、秘密）、秘密（1）、机密（）、机密（2）和绝密（）和绝密（3）。在安全级别中使用种类是一）。在安全级别中使用种类是一个集合子集，这个集合含有与一个特定行业领域相关全部个集合子集，这个集合含有与一个特定行业领域相关全部分部，每个分部表示一个指定对象域。分部，每个分部表示一个指定对象域。比如，假如分部集合是比如，假如分部集合是间谍，鼹鼠。双重间谍间谍，鼹鼠。双重间谍，那么存，那么存在在8个不一样种类，分部集合有个不一样种类，分部集合有8个子集，对于每个子集有一类个子集，对于每个子集有一类，比如，比如间谍，鼹鼠间谍，鼹鼠。68/87 我们能够对
47、安全类排序，要求（我们能够对安全类排序，要求（A1,C1）（A2,C2）当且仅当）当且仅当A1 A2和和C1 C2.信息允许从安全类（信息允许从安全类（A1,C1）流向安全类）流向安全类（A2,C2）当且仅当（）当且仅当（A1,C1）（A2,C2）。比如，信息允许从安全类（机密，比如，信息允许从安全类（机密，间谍，鼹鼠间谍，鼹鼠）流向安全）流向安全类（绝密，类（绝密，间谍，鼹鼠，双重间谍间谍，鼹鼠，双重间谍），反之，信息不允许从安），反之，信息不允许从安全类（绝密，全类（绝密，间谍，鼹鼠间谍，鼹鼠）流向安全类（机密，）流向安全类（机密，间谍，鼹鼠间谍，鼹鼠，双重间谍，双重间谍）或（绝密，）或（
48、绝密，间谍间谍）。）。69/87六、拓扑排序六、拓扑排序假设一个项目由假设一个项目由2020个任务组成。一些任务只能在其它任务结个任务组成。一些任务只能在其它任务结束之后完成，怎样找到关于这些任务次序？束之后完成，怎样找到关于这些任务次序？为了对这个问题结构模型，我们建立一个任务集合上偏序，为了对这个问题结构模型，我们建立一个任务集合上偏序，使得使得ab,ab,当且仅当当且仅当a a和和b b是任务且直到是任务且直到a a结束后结束后b b才能开始。为安才能开始。为安排好这个项目，需要得出与这个偏序相容全部排好这个项目，需要得出与这个偏序相容全部2020个任务顺个任务顺序。我们将说明怎样做到这
49、一点。序。我们将说明怎样做到这一点。70/87从定义开始，假如只要从定义开始，假如只要aRb就有就有a b,则称一个全序则称一个全序 与偏序与偏序R 是是相容相容。从一个偏序结构一个相容全序叫做。从一个偏序结构一个相容全序叫做拓扑排序拓扑排序。需要使。需要使用引理用引理1.引理引理1：每个有穷非空偏序集（每个有穷非空偏序集（S,）都有极小元素。）都有极小元素。71/87Proof：选择选择S一个元素一个元素a0.假如假如a0不是绩效元素，那么存在元素不是绩效元素，那么存在元素a1,满足满足a1 a0.假如假如a1不是极小元素，那么存在元素不是极小元素，那么存在元素a2,满足满足a2 a1.继续
50、这一过程，使得假如继续这一过程，使得假如an不是极小元素，那么存在元素不是极小元素，那么存在元素an+1满满足足an+1an.因为在这个偏序集只有有穷个元素，这个过程一定结因为在这个偏序集只有有穷个元素，这个过程一定结束而且含有极小元素束而且含有极小元素an.72/87我们将要描述拓扑排序算法对任何有穷非空偏序集都有效我们将要描述拓扑排序算法对任何有穷非空偏序集都有效 为在偏序集（为在偏序集（A,）上定义一个全序，首先选择一个极小元）上定义一个全序，首先选择一个极小元素素a1；由引理；由引理1这么元素存在。接着，这么元素存在。接着，A-a1，也是一个也是一个偏序集。假如它是非空，选择这个偏序集
