離散數學(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)根據蓋住的概念給出了偏序關系圖的一種畫法,這種畫法畫出的圖稱為哈斯圖,作圖規(guī)則如下：

例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},,{c}}{a},,{c}{a},,{c}

無無{{a},{a,b}}{a,b}{a,b}{a}

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

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

最大（?。┰蜆O大（?。┰男再|：（1）最大（小）元必是極大（?。┰?，反之不然。（2）最大（?。┰灰欢ù嬖?，若存在，則是唯一的。（3）極大（?。┰晃ㄒ唬擝＝A時，偏序集的極大元即是其哈斯圖中最頂層元素，其極小元是哈斯圖中最底層元素，不同的極大（?。┰g不可比，它們處在哈斯圖中的同一個層次。證：定義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},,{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〉正確?！?〉否。所以對任意的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