離散數(shù)學(xué)(3.12序關(guān)系)

1離散數(shù)學(xué)(DiscreteMathematics)張捷第三章集合與關(guān)系（SetsandRelations)

3.6關(guān)系的閉包運(yùn)算(ClosureOperations)3.7集合的劃分與覆蓋(Partition&CoverofSets)3.8等價(jià)關(guān)系(EquivalentRelations)3.9相容關(guān)系(Compatibility

Relations)3.10序關(guān)系(OrderedRelations)3.1集合及其運(yùn)算(Sets&Operationswithsets)

3.2序偶與笛卡爾積(OrderedPairs&CartesianProduct)3.3關(guān)系

(Relations)3.4關(guān)系的性質(zhì)(ThePropetiesofRelations)3.5復(fù)合關(guān)系與逆關(guān)系(CompoundRelations&InverseRelations)3.10序關(guān)系(OrderedRelations)3.10.1偏序關(guān)系的定義(PartiallyOrdered

Relations)3.10.2偏序關(guān)系的哈斯圖(TheHasseDiagramofPosets)3.10.3偏序集中特殊位置的元素3.10.4幾種特殊的偏序集第三章集合與關(guān)系(Sets&Relations)3.10偏序關(guān)系

3.10.1偏序關(guān)系的定義(PartiallyOrderedRelations)定義3.10.1集合A上的關(guān)系ρ,如果它是自反的,反對稱的且可傳遞的,則稱ρ是A上的偏序關(guān)系.記作“≤”,序偶稱為偏序集(partiallyorderedsetorposetforshort).例1

實(shí)數(shù)集R上的“≤”關(guān)系顯然是一個(gè)偏序關(guān)系。

證明

對于任意，有，所以“

”是自反的。

對任意，若且，則所以“

”是反對稱的。例2

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

”關(guān)系也是一個(gè)偏序關(guān)系。

對任意，若，，則所以“

”是可傳遞的。

例3

設(shè)A={1,2,3,4,6,8,12}，定義A上的整除關(guān)系如下：則ρ是A上的偏序關(guān)系。例4自然數(shù)集上的整除關(guān)系是偏序關(guān)系。實(shí)數(shù)集R上的“＜”關(guān)系不是偏序關(guān)系。2U上的真包含關(guān)系“

”也不是偏序關(guān)系。3.10.2偏序關(guān)系的哈斯圖(TheHasseDiagramofPosets)a≤c,c≤b，則稱元素b蓋住元素a，并且記稱為偏序集中的蓋住關(guān)系。顯然。

定義3.10.2

在偏序集中，若元素，a≠b，a≤b，且在集A中不存在任何其它元素c，使得3.10.2偏序關(guān)系的哈斯圖(TheHasseDiagramofPosets)用小圓圈代表元素;若元素a≠b且a≤b時(shí)，則結(jié)點(diǎn)a畫在結(jié)點(diǎn)b的下方。

(3)若b蓋住a，則在a與b之間用直線連接.由于所有邊的箭頭向上,故省去箭頭。例3中的關(guān)系的哈斯圖如右圖.哈斯(Hasse)根據(jù)蓋住的概念給出了偏序關(guān)系圖的一種畫法,這種畫法畫出的圖稱為哈斯圖,作圖規(guī)則如下：

例5

設(shè)U={a,b,c}，則“

”關(guān)系是2U上的偏序關(guān)系，偏序關(guān)系“

”的哈斯圖如下：

例6

設(shè)A={2,3,6,12,24,36}，A上的整除關(guān)系是一偏序關(guān)系，其哈斯圖如下：3.10.3偏序集中特殊位置的元素

既然偏序集的元素之間具有分明的層次關(guān)系，則其中必有一些處于特殊位置的元素。定義3-10.3（極大元，極小元，最大元，最小元）設(shè)是一個(gè)偏序集，且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.設(shè)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大（?。┰男再|(zhì)：（1）最大（小）元必是極大（?。┰?，反之不然。（2）最大（小）元不一定存在，若存在，則是唯一的。（3）極大（?。┰晃ㄒ唬?dāng)B＝A時(shí)，偏序集的極大元即是其哈斯圖中最頂層元素，其極小元是哈斯圖中最底層元素，不同的極大（?。┰g不可比，它們處在哈斯圖中的同一個(gè)層次。證：定義3.10.4（上界，下界，上確界，下確界)

A，如果存在元素a設(shè)為一偏序集，且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.設(shè)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}

通過以上例子可以看出界有以下性質(zhì)：（1）一個(gè)集合可能沒有上界或下界，若有，則不一定唯一，并且它們可能在B中，也可能在B外；（2）一個(gè)集合若有上下確界，必定是唯一的，并且若是B的最大（?。┰?，則它必是B的上（下）確界。

3.10.4兩種特殊的偏序集1.全序設(shè)“≤”是集合A上的一個(gè)偏序關(guān)系，對于任意a,b∈A，當(dāng)a≠b時(shí)，a≤b和b≤a至多一個(gè)成立，這意味著允許a≤b和b≤a可以都不成立。例如

在例3的整除關(guān)系中，3≤4，4≤3均不成立。

在例4的包含關(guān)系中定義3.10.5設(shè)≤是集合A上的一個(gè)偏序，若對于任意元素a,b∈A，必有a≤b或b≤a，則稱它為A上的一個(gè)全序。

例如實(shí)數(shù)集R上的數(shù)之間的小于或等于關(guān)系“≤”就是R上的一個(gè)全序，

正整數(shù)集N上的小于或等于關(guān)系“≤”也是N上的一個(gè)全序。N上的整除關(guān)系就僅是一個(gè)偏序而不是全序。

例11

設(shè)A={1,2,8,24,48}，則A上的整除關(guān)系是A上的偏序，并且也是一個(gè)全序.

3.10.4兩種特殊的偏序集

2.良序定義3.10.6設(shè)“≤”是集合A上的一個(gè)偏序關(guān)系，若A的任意子集B均有最小元素,則稱≤為A上的一個(gè)良序。稱為良序集。例如(1)正整數(shù)集N上的小于等于關(guān)系“≤”是良序關(guān)系。

(2)In={1,2,…,n}上的小于等于關(guān)系“≤”是良序關(guān)系。(3)整數(shù)集Z和實(shí)數(shù)集R上的小于等于關(guān)系“≤”不是良序關(guān)系(因?yàn)閆或R本身無最小元)。定理3.10.1每一個(gè)良序集一定是全序集.注意:定理3.10.1的逆不成立

。

例如:整數(shù)集Z和實(shí)數(shù)集R上的小于等于關(guān)系“≤”是全序關(guān)系,但不是良序關(guān)系。證:設(shè)為良序集,則對任意的a,b∈A,{a,b}構(gòu)成A的子集,因此它必有最小元素,最小元素非a則b,故一定有a≤b或b≤a.所以是一個(gè)全序集.但是,對于有限的全序集,定理3.10.1的逆也成立.即有定理3.10.2每一個(gè)有限的全序集一定是良序集.綜合練習(xí)

1.對下述論斷判斷正確與否，在相應(yīng)括號中鍵入“Y”或“N”。（1）設(shè)A={2,3,6,12,24,36}，A上的整除關(guān)系是一偏序關(guān)系，用“≤”表示。

(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}上的整除關(guān)系是A上的全序（）Y（a）該偏序關(guān)系的哈斯圖是（）

解

滿足上述條件的最小基數(shù)的關(guān)系

ρ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〉｝,求滿足上述條件的一個(gè)基數(shù)最小的關(guān)系ρ2.一般地說,若給定ρ1和ρ1·ρ2

，ρ2

能被唯一地確定嗎?基數(shù)最小的ρ2能被唯一確定嗎？給定ρ1和ρ1·ρ2，也不能唯一的確定出最小基數(shù)的ρ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．下列關(guān)系哪一個(gè)是自反的、對稱的、反對稱的或可傳遞的？

〈1〉當(dāng)且僅當(dāng)n1n2<8(n1,n2∈N)時(shí),有n1ρn2

〈2〉當(dāng)且僅當(dāng)r1≤|

r2|(r1,r2∈R)時(shí),有r1ρr2

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

ρ是對稱的，因?yàn)閷τ谌我獾膎1,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〉ρ是自反的，因?yàn)閷θ我獾膔∈R，有r≤|r|。

ρ不是對稱的，如-1≤|3|，但3>|-1|。ρ不是可傳遞的，100≤|-101|，-101≤|2|，但100>|2|ρ不是反對稱的，如-3≤|2|，2≤|-3|，但-3≠2。4.設(shè)ρ1和ρ2是集合A上的任意兩個(gè)關(guān)系,判斷下列命題是否正確,并說明理由.〈1〉若ρ1和ρ2是自反的，則ρ1·ρ2也是自反的；

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

證明〈1〉正確?！?〉否。所以對任意的a∈A,有a〈ρ1·ρ2〉a，因此ρ1·ρ2也是自反的。又對任意的a∈A,有aρ2a.因?yàn)閷θ我獾腶∈A,有aρ1a,例如，設(shè)集合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也是可傳遞的；例如，設(shè)集合A=｛1,2,3｝，

ρ1=｛〈1,2〉，〈2,1〉｝,ρ2=｛〈1,3〉，〈3,1〉｝，顯然ρ1和ρ2都是對稱的，例如設(shè)A=｛1,2,3｝,ρ1={〈1,2〉,〈3，3〉｝,ρ2={〈2,3〉,〈3，1〉｝顯然ρ1和ρ2都是反對稱的，例如設(shè)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上的關(guān)系，如果是對稱的且可傳遞，則它也是自反的。其理由是，從對稱性傳遞性例設(shè)A＝｛1,2，3｝ρ＝｛〈1,2〉,〈2,1〉,〈1,1〉,〈2,2〉}

6．設(shè)ρ1是集合A上的一個(gè)關(guān)系，ρ2=｛〈a,b〉|存在c，使〈a,c〉∈ρ1且〈c,b〉∈ρ1｝，試證明：若ρ1是一個(gè)等價(jià)關(guān)系，則ρ2也是一個(gè)等價(jià)關(guān)系。證明

因?yàn)棣?是自反的，所以對于任意的a∈A

,有〈a,a〉∈ρ1

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