离散数学(3.12序关系)

1离散数学(DiscreteMathematics)张捷第三章集合与关系（SetsandRelations)

3.6关系的闭包运算(ClosureOperations)3.7集合的划分与覆盖(Partition&CoverofSets)3.8等价关系(EquivalentRelations)3.9相容关系(Compatibility

Relations)3.10序关系(OrderedRelations)3.1集合及其运算(Sets&Operationswithsets)

3.2序偶与笛卡尔积(OrderedPairs&CartesianProduct)3.3关系

(Relations)3.4关系的性质(ThePropetiesofRelations)3.5复合关系与逆关系(CompoundRelations&InverseRelations)3.10序关系(OrderedRelations)3.10.1偏序关系的定义(PartiallyOrdered

Relations)3.10.2偏序关系的哈斯图(TheHasseDiagramofPosets)3.10.3偏序集中特殊位置的元素3.10.4几种特殊的偏序集第三章集合与关系(Sets&Relations)3.10偏序关系

3.10.1偏序关系的定义(PartiallyOrderedRelations)定义3.10.1集合A上的关系ρ,如果它是自反的,反对称的且可传递的,则称ρ是A上的偏序关系.记作“≤”,序偶称为偏序集(partiallyorderedsetorposetforshort).例1

实数集R上的“≤”关系显然是一个偏序关系。

证明

对于任意，有，所以“

”是自反的。

对任意，若且，则所以“

”是反对称的。例2

全集合U的幂集2U上的“

”关系也是一个偏序关系。

对任意，若，，则所以“

”是可传递的。

例3

设A={1,2,3,4,6,8,12}，定义A上的整除关系如下：则ρ是A上的偏序关系。例4自然数集上的整除关系是偏序关系。实数集R上的“＜”关系不是偏序关系。2U上的真包含关系“

”也不是偏序关系。3.10.2偏序关系的哈斯图(TheHasseDiagramofPosets)a≤c,c≤b，则称元素b盖住元素a，并且记称为偏序集中的盖住关系。显然。

定义3.10.2

在偏序集中，若元素，a≠b，a≤b，且在集A中不存在任何其它元素c，使得3.10.2偏序关系的哈斯图(TheHasseDiagramofPosets)用小圆圈代表元素;若元素a≠b且a≤b时，则结点a画在结点b的下方。

(3)若b盖住a，则在a与b之间用直线连接.由于所有边的箭头向上,故省去箭头。例3中的关系的哈斯图如右图.哈斯(Hasse)根据盖住的概念给出了偏序关系图的一种画法,这种画法画出的图称为哈斯图,作图规则如下：

例5

设U={a,b,c}，则“

”关系是2U上的偏序关系，偏序关系“

”的哈斯图如下：

例6

设A={2,3,6,12,24,36}，A上的整除关系是一偏序关系，其哈斯图如下：3.10.3偏序集中特殊位置的元素

既然偏序集的元素之间具有分明的层次关系，则其中必有一些处于特殊位置的元素。定义3-10.3（极大元，极小元，最大元，最小元）设是一个偏序集，且BA，如果存在元素b∈B使得（1）不存在xB满足xb且bx，则称b为B的极大元；B满足xb且x（2）不存在xb，则称b为B的极小元；（3）对B中任意元素x，均有xb，则称b为B的最大元；（4）对B中任意元素x，均有bx，则称b为B的最小元。

集合极大元极小元最大元最小元

｛a,b,c｝｛a,b,c｝{a}例7.设A＝｛a,b,c｝，对于偏序集，{{a},{b},{c}}{a},{b},{c}{a},{b},{c}

无无{{a},{a,b}}{a,b}{a,b}{a}

集合极大元极小元最大元最小元例8

在例6中取B={6，12}，C={2，3，6}，则ABC24，361262，362，3无126无6无

最大（小）元和极大（小）元的性质：（1）最大（小）元必是极大（小）元，反之不然。（2）最大（小）元不一定存在，若存在，则是唯一的。（3）极大（小）元不唯一，当B＝A时，偏序集的极大元即是其哈斯图中最顶层元素，其极小元是哈斯图中最底层元素，不同的极大（小）元之间不可比，它们处在哈斯图中的同一个层次。证：定义3.10.4（上界，下界，上确界，下确界)

A，如果存在元素a设为一偏序集，且BA，B中任意元素x，都满足（1）xa，则称a为B的上界；X，则称a为B的下界；（2）a（3）若a是B的上界，且对B的任意上界，均有

a则称a为B的最小上界（上确界），记作LUB(B)；（4）若a是B的下界，且对B的任意下界，均有a,则称a为B的最大下界（下确界），记作GLB(B)。

集合上界下界上确界下确界

｛a,b,c｝｛a,b,c｝{a},例9.设A＝｛a,b,c｝，对于偏序集，{{a},{b},{c}}{a,b,c}{a,b,c}{{a},{a,b}}{a,b},{a,b,c}{a,b}{a}

集合上界下界上确界下确界例10

在例6中取B={12,24,36}，C={2，3，6}，则ABC无无6,12,24,36

无12,6,3,2无无无6无12无A={2,3,6,12,24,36}

通过以上例子可以看出界有以下性质：（1）一个集合可能没有上界或下界，若有，则不一定唯一，并且它们可能在B中，也可能在B外；（2）一个集合若有上下确界，必定是唯一的，并且若是B的最大（小）元素，则它必是B的上（下）确界。

3.10.4两种特殊的偏序集1.全序设“≤”是集合A上的一个偏序关系，对于任意a,b∈A，当a≠b时，a≤b和b≤a至多一个成立，这意味着允许a≤b和b≤a可以都不成立。例如

在例3的整除关系中，3≤4，4≤3均不成立。

在例4的包含关系中定义3.10.5设≤是集合A上的一个偏序，若对于任意元素a,b∈A，必有a≤b或b≤a，则称它为A上的一个全序。

例如实数集R上的数之间的小于或等于关系“≤”就是R上的一个全序，

正整数集N上的小于或等于关系“≤”也是N上的一个全序。N上的整除关系就仅是一个偏序而不是全序。

例11

设A={1,2,8,24,48}，则A上的整除关系是A上的偏序，并且也是一个全序.

3.10.4两种特殊的偏序集

2.良序定义3.10.6设“≤”是集合A上的一个偏序关系，若A的任意子集B均有最小元素,则称≤为A上的一个良序。称为良序集。例如(1)正整数集N上的小于等于关系“≤”是良序关系。

(2)In={1,2,…,n}上的小于等于关系“≤”是良序关系。(3)整数集Z和实数集R上的小于等于关系“≤”不是良序关系(因为Z或R本身无最小元)。定理3.10.1每一个良序集一定是全序集.注意:定理3.10.1的逆不成立

。

例如:整数集Z和实数集R上的小于等于关系“≤”是全序关系,但不是良序关系。证:设为良序集,则对任意的a,b∈A,{a,b}构成A的子集,因此它必有最小元素,最小元素非a则b,故一定有a≤b或b≤a.所以是一个全序集.但是,对于有限的全序集,定理3.10.1的逆也成立.即有定理3.10.2每一个有限的全序集一定是良序集.综合练习

1.对下述论断判断正确与否，在相应括号中键入“Y”或“N”。（1）设A={2,3,6,12,24,36}，A上的整除关系是一偏序关系，用“≤”表示。

(b)“≤”={〈2,2〉,〈2,6〉,〈3,3〉,〈3,6〉,〈6,6〉,〈6,12〉,〈12,12〉,〈12,24〉,〈24,24〉,〈36,36〉}

（）NY（2）集合A={3,9,27,54}上的整除关系是A上的全序（）Y（a）该偏序关系的哈斯图是（）

解

满足上述条件的最小基数的关系

ρ2={〈2,3〉，〈2,4〉，〈4,3〉｝一般说，给定ρ1和ρ1·ρ2，不能唯一的确定ρ2。例如ρ2=｛〈2,3〉，〈2,4〉，〈4,3〉，〈0,0〉，〈3,3〉｝也可以.2．给定ρ1=｛〈0,1〉,〈1,2〉,〈3,4〉},ρ1·ρ2=｛〈1,3〉，〈1,4〉，〈3,3〉｝,求满足上述条件的一个基数最小的关系ρ2.一般地说,若给定ρ1和ρ1·ρ2

，ρ2

能被唯一地确定吗?基数最小的ρ2能被唯一确定吗？给定ρ1和ρ1·ρ2，也不能唯一的确定出最小基数的ρ2。

则ρ2=｛〈2,3〉，〈2,4〉，〈4,3〉｝或

ρ2=｛〈2,3〉，〈2,4〉，〈3,3〉｝都可以。例如ρ1=｛〈0,1〉，〈1,2〉，〈3,3〉，〈3,4〉｝，ρ1·ρ2=｛〈1,3〉，〈1,4〉，〈3,3〉｝，433．下列关系哪一个是自反的、对称的、反对称的或可传递的？

〈1〉当且仅当n1n2<8(n1,n2∈N)时,有n1ρn2

〈2〉当且仅当r1≤|

r2|(r1,r2∈R)时,有r1ρr2

解〈1〉ρ不是自反的，如4∈N，但4·4=16>8。

ρ是对称的，因为对于任意的n1,n2∈N，若有n1n2<8，则n2n1=n1n2<8。ρ不是可传递的，例如，3·2<8，2·3<8，但3·3=9>8。

ρ不是反对称的，例，2·3<8，3·2<8，但3≠2.〈2〉ρ是自反的，因为对任意的r∈R，有r≤|r|。

ρ不是对称的，如-1≤|3|，但3>|-1|。ρ不是可传递的，100≤|-101|，-101≤|2|，但100>|2|ρ不是反对称的，如-3≤|2|，2≤|-3|，但-3≠2。4.设ρ1和ρ2是集合A上的任意两个关系,判断下列命题是否正确,并说明理由.〈1〉若ρ1和ρ2是自反的，则ρ1·ρ2也是自反的；

〈2〉若ρ1和ρ2是非自反的，则ρ1·ρ2也是非自反的；

证明〈1〉正确。〈2〉否。所以对任意的a∈A,有a〈ρ1·ρ2〉a，因此ρ1·ρ2也是自反的。又对任意的a∈A,有aρ2a.因为对任意的a∈A,有aρ1a,例如，设集合A=｛a,b｝.ρ1={〈a,b〉,〈b,a〉},ρ2={〈a,b〉,〈b,a〉}显然ρ1和ρ2都是非自反的，但ρ1·ρ2自反。

〈3〉若ρ1和ρ2是对称的，则ρ1·ρ2也是对称的；

〈4〉若ρ1和ρ2是反对称的，则ρ1·ρ2也是反对称的；

〈5〉若ρ1和ρ2是可传递的，则ρ1·ρ2也是可传递的；例如，设集合A=｛1,2,3｝，

ρ1=｛〈1,2〉，〈2,1〉｝,ρ2=｛〈1,3〉，〈3,1〉｝，显然ρ1和ρ2都是对称的，例如设A=｛1,2,3｝,ρ1={〈1,2〉,〈3，3〉｝,ρ2={〈2,3〉,〈3，1〉｝显然ρ1和ρ2都是反对称的，例如设A=｛1,2,3},ρ1={〈1,2〉,〈2,3〉,〈1,3〉},ρ2=｛〈2，3〉，〈3，1〉，〈2，1〉｝，显然ρ1和ρ2都可传递的.但ρ1·ρ2=｛〈2,3〉｝不是对称的。但ρ1·ρ2={〈1,3〉,〈2,1〉,〈1,1〉}不是可传递的。但ρ1·ρ2=｛〈1,3〉，〈3,1〉｝不是反对称的。证明〈3〉否.

〈4〉否.〈5〉否.5.有人说，集合A上的关系，如果是对称的且可传递，则它也是自反的。其理由是，从对称性传递性例设A＝｛1,2，3｝ρ＝｛〈1,2〉,〈2,1〉,〈1,1〉,〈2,2〉}

6．设ρ1是集合A上的一个关系，ρ2=｛〈a,b〉|存在c，使〈a,c〉∈ρ1且〈c,b〉∈ρ1｝，试证明：若ρ1是一个等价关系，则ρ2也是一个等价关系。证明

因为ρ1是自反的，所以对于任意的a∈A

,有〈a,a〉∈ρ1

，由〈a,a〉∈ρ1,〈a,a〉∈ρ1由ρ1