離散數(shù)學(xué)教案

1、學(xué)習(xí)目標(biāo)：1深刻理解序偶、笛卡爾積、關(guān)系、集合的劃分與覆蓋、等價(jià)關(guān)系、等價(jià)類、商集、相容關(guān)系、（最大）相容類、偏序關(guān)系、極大元、極小元、上（下）界、上（下）確界、最大（?。┰?、全序關(guān)系、良序關(guān)系等概念；2掌握集合的交、并、差、補(bǔ)、對稱差的運(yùn)算及其運(yùn)算規(guī)律；3掌握關(guān)系的交、并、逆、復(fù)合運(yùn)算、閉包運(yùn)算及其性質(zhì)；4掌握關(guān)系的矩陣表示和關(guān)系圖；5深刻理解關(guān)系的自反性、反自反性、對稱性、反對稱性和傳遞性，掌握其判別方法；6掌握集合的覆蓋與劃分的聯(lián)系與區(qū)別；7掌握偏序關(guān)系的判別及其哈斯圖的畫法；會求偏序集中給定集合的極大元、極小元、上（下）界、上（下）確界、最大（?。┰?。主要內(nèi)容：1集合的基本概念及其運(yùn)算

2、2序偶與笛卡爾積3關(guān)系及其表示4關(guān)系的性質(zhì)及其判定方法5復(fù)合關(guān)系和逆關(guān)系6關(guān)系的閉包運(yùn)算7等價(jià)關(guān)系與相容關(guān)系8偏序關(guān)系 重點(diǎn)： 1關(guān)系的性質(zhì)及其判別；2關(guān)系的復(fù)合運(yùn)算及其性質(zhì)；3等價(jià)關(guān)系與等價(jià)類、等價(jià)關(guān)系與集合的劃分的聯(lián)系；4偏序關(guān)系判別及其哈斯圖的畫法、偏序集中特異位置元素的理解。 難點(diǎn)：1關(guān)系的傳遞性及其判別；2等價(jià)關(guān)系的特性；3偏序關(guān)系的哈斯圖的畫法；偏序集中特異位置元素的求法。 教學(xué)手段： 通過多個(gè)實(shí)例的精講幫助同學(xué)理解重點(diǎn)和難點(diǎn)的內(nèi)容，并通過大量的練習(xí)使同學(xué)們鞏固和掌握關(guān)系的性質(zhì)及其判別、關(guān)系的復(fù)合運(yùn)算及其性質(zhì)、等價(jià)關(guān)系的特性、偏序關(guān)系的哈斯圖的畫法及偏序集中特異位置元素的求法。習(xí)題

3、： 習(xí)題3.1：4，6；習(xí)題3.2：3（8），4（12），6（m）；習(xí)題3.4：1 （2）、(4)，3；習(xí)題3.5：1，4；習(xí)題3.6：2，5，6；習(xí)題3.7：2，5，6；習(xí)題3.8：1（1）-（6）；習(xí)題3.9：3（2）、（4），4（3）；習(xí)題3.10：1 ，4，5。3.1 集合的基本概念集合(set)（或稱為集）是數(shù)學(xué)中的一個(gè)最基本的概念。所謂集合，就是指具有共同性質(zhì)的或適合一定條件的事物的全體，組成集合的這些“事物”稱為集合的元素。集合常用大寫字母表示，集合的元素常用小寫字母表示。若是集合，是的元素，則稱屬于，記作；若不是的元素，則稱不屬于，記作。若組成集合的元素個(gè)數(shù)是有限的，則稱該集合

4、為有限集(Finite Set)，否則稱為無限集(Infinite Set)。常見集合專用字符的約定： 自然數(shù)集合(非負(fù)整數(shù)集) (或)整數(shù)集合(，)有理數(shù)集合(，)實(shí)數(shù)集合(，)分?jǐn)?shù)集合(，)腳標(biāo)+和-是對正、負(fù)的區(qū)分復(fù)數(shù)集合素?cái)?shù)集合奇數(shù)集合偶數(shù)集合冪集定義3.1.1 對于每一個(gè)集合，由的所有子集組成的集合，稱為集合的冪集(Power Set)，記為 或即。例如：, 。定理3.1.1 如果有限集有個(gè)元素，則其冪集有個(gè)元素。證明 的所有由個(gè)元素組成的子集數(shù)為從個(gè)元素中取個(gè)的組合數(shù)。另外，因，故的元素個(gè)數(shù)可表示為 又因 令 得 故的元素個(gè)數(shù)是。人們常常給有限集的子集編碼，用以表示的冪集的各個(gè)元素

5、。具體方法是：設(shè)，則子集按照含記、不含記的規(guī)定依次寫成一個(gè)位二進(jìn)制數(shù)，便得子集的編碼。例如，若，則的編碼是，當(dāng)然還可將它化成十進(jìn)制數(shù)。如果，那么這個(gè)十進(jìn)制數(shù)為，此時(shí)特別記為。 3.2 集合的對稱差運(yùn)算定義3.2.1 設(shè)、是兩個(gè)集合，要么屬于，要么屬于，但不能同時(shí)屬于和的所有元素組成的集合，稱為和的對稱差集，記為。即例如，若，則。對稱差的定義如圖3-1所示。圖3-1由對稱差的定義容易推得如下性質(zhì)：（1）（2）（3）（4）（5）證明 （5）但 =故 又 因?yàn)?故 因此 對稱差運(yùn)算的結(jié)合性亦可用圖3-2說明。 圖3-2 對稱差運(yùn)算的結(jié)合性從文氏圖3-3亦可以看出以下關(guān)系式成立。 圖3-3 3.4 序

6、偶與笛卡爾積 序偶 在日常生活中，有許多事物是成對出現(xiàn)的，而且這種成對出現(xiàn)的事物，具有一定的順序。例如，上，下；男生9名而女生6；中國地處亞洲；平面上點(diǎn)的坐標(biāo)等。一般的說，兩個(gè)具有固定次序的客體組成一個(gè)序偶(Ordered Pair)，記作。上述各例可分別表示為上，下；中國，亞洲；等。 序偶可以看作是具有兩個(gè)元素的集合，但它與一般集合不同的是序偶具有確定的次序。在集合中，但對序偶，當(dāng)時(shí)，。定義 兩個(gè)序偶相等，當(dāng)且僅當(dāng)。這里指出：序偶中兩個(gè)元素不一定來自同一個(gè)集合，它們可以代表不同類型的事物。例如，代表操作碼，代表地址碼，則序偶就代表一條單地址指令；當(dāng)然亦可將代表地址碼，代表操作碼，仍代表一條單

7、地址指令。但上述這種約定，一經(jīng)確定，序偶的次序就不能再予以變化了。在序偶中，稱第一元素，稱第二元素。序偶的概念可以推廣到有序三元組的情況。有序三元組是一個(gè)序偶，其第一元素本身也是一個(gè)序偶，可形式化表示為。由序偶相等的定義，可以知道當(dāng)且僅當(dāng)，即，我們約定有序三元組可記作。注意：，因?yàn)椴皇怯行蛉M。同理，有序四元組被定義為一個(gè)序偶，其第一元素為有序三元組，故有序四元組有形式為，可記作，且這樣，有序元組(Ordered n-tuple)定義為，記作，且 一般地，有序元組中的稱作有序元組的第個(gè)坐標(biāo)。 笛卡爾積 定義 設(shè)和是任意兩個(gè)集合，若序偶的第一個(gè)成員是的元素，第二個(gè)成員是的元素，所有這樣的序偶集

8、合，稱為集合和的笛卡爾乘積或直積(Cartesian Product)，記作。即例 若, 求以及解 顯然，我們有：（1）；（2）如果，則。我們約定：若或，則。由笛卡爾積定義可知： 由于不是三元組，所以定理 設(shè)、和為任意三個(gè)集合，則有（1）（2）（3）（4）證明 （1）設(shè) 因此， 。（4）設(shè) 因此， 。定理 設(shè)、和為三個(gè)非空集合，則有 證明 設(shè)，對任意的，因此， 。反之，若，取，則對，有因此，。定理的第二部分，證明類似。定理 設(shè)、和為四個(gè)非空集合，則的充要條件為且。證明 若，對任意的，有 即 。反之，若且，設(shè)任意，有 因此， 。對于有限個(gè)集合可以進(jìn)行多次笛卡爾積運(yùn)算。為了與有序元組一致，我們約定

9、：一般地，故是有序元組構(gòu)成的集合。特別地，同一集合的次直積，記為, 這里。例如， 此處，。一般地，若 。3.5 關(guān)系及其表示 關(guān)系的定義 在日常生活中我們都熟悉關(guān)系這詞的含義，例如，父子關(guān)系、上下級關(guān)系、朋友關(guān)系等。我們知道，序偶可以表達(dá)兩個(gè)客體、三個(gè)客體或個(gè)客體之間的聯(lián)系，因此可以用序偶表達(dá)關(guān)系這個(gè)概念。例如，機(jī)票與艙位之間有對號關(guān)系。設(shè)表示機(jī)票的集合，表示艙位的集合，則對于任意的和，必有與有對號關(guān)系和與沒有對號關(guān)系兩種情況的一種。令表示“對號”關(guān)系，則上述問題可以表達(dá)為或，亦可記為或，因此，我們看到對號關(guān)系是序偶的集合。定義 設(shè)、是任意兩個(gè)集合，則稱直積的任一子集為從到的一個(gè)二元關(guān)系(Bi

10、nary Relation )。二元關(guān)系亦簡稱關(guān)系，記為，。到的二元關(guān)系，如圖3-4所示。圖3-4集合到的二元關(guān)系是第一坐標(biāo)取自、第二坐標(biāo)取自的序偶集合。如果序偶，也說與有關(guān)系，記為；如果序偶，則說與沒有關(guān)系，記為。當(dāng)時(shí)，關(guān)系是的子集，這時(shí)稱為集合上的二元關(guān)系。例 （1）設(shè)，則，令因?yàn)?，所以，和均是由到的關(guān)系。（2）>=是實(shí)數(shù)且是實(shí)數(shù)集上的大于關(guān)系。定義 設(shè)為到的二元關(guān)系，由的所有組成的集合稱為的定義域或前域(Domain)，記作dom或，即 dom使的所有組成的集合稱為的值域(Range)，記作ran，即ran。的定義域和值域一起稱作的域(Field)，記作FLD，即FLD domra

11、n顯然，dom，ran，F(xiàn)LDdomran例3.5.2 設(shè)，求dom，ran 和FLD。解 dom，ran ，F(xiàn)LD。 例3.5.3 設(shè)，求集合上的關(guān)系“”、dom及ran。 解 domran3.5.2 幾種特殊的關(guān)系1空關(guān)系對任意集合，所以是由到的關(guān)系，也是上的關(guān)系，稱為空關(guān)系(Empty Relation)。2全域關(guān)系因?yàn)?，所以是一個(gè)由到的關(guān)系，稱為由到的全域關(guān)系(Universal Relation)。是上的一個(gè)關(guān)系，稱為上的全域關(guān)系，通常記作，即。例3.5.4 若表示家庭中父、母、子、女四個(gè)人的集合，確定上的全域關(guān)系和空關(guān)系，另外再確定上的一個(gè)關(guān)系，并指出該關(guān)系的前域和值域。解 設(shè)上同

12、一家庭的成員的關(guān)系為， 設(shè)上的互不相識的關(guān)系為，則為全域關(guān)系，為空關(guān)系。設(shè)上的長幼關(guān)系為，domran3恒等關(guān)系定義 設(shè)是上的二元關(guān)系且滿足，則稱是上的恒等關(guān)系(Identical Relation)。例如，則。因?yàn)殛P(guān)系是序偶的集合，因此，可以進(jìn)行集合的所有運(yùn)算。定理 若和是從集合到集合的兩個(gè)關(guān)系，則、的并、交、補(bǔ)、差仍是到的關(guān)系。證明 因?yàn)?故 例3.5.5 若，求 ，和。解 ， 3.5.3 關(guān)系的表示 1集合表示法因?yàn)殛P(guān)系是序偶的集合，因此可用表示集合的列舉法或描述法來表示關(guān)系。例如，例的（1）中的關(guān)系，和及例3.5.2中的關(guān)系，均是用列舉法表示的關(guān)系；而例的（2）中的關(guān)系和例3.5.5中

13、的關(guān)系，都是用描述法表示的關(guān)系。有限集合間的二元關(guān)系除了可以用序偶集合的形式表達(dá)以外，還可用矩陣和圖形表示，以便引入線性代數(shù)和圖論的知識來討論。2矩陣表示法 設(shè)給定兩個(gè)有限集合，則對應(yīng)于從到的二元關(guān)系有一個(gè)關(guān)系矩陣，其中 。 如果是有限集合上的二元關(guān)系或和含有相同數(shù)量的有限個(gè)元素，則是方陣。例3.5.6 若，寫出關(guān)系矩陣。解 例3.5.7 設(shè)，寫出集合上的大于關(guān)系>的關(guān)系矩陣。 解 > 3關(guān)系圖表示法有限集合的二元關(guān)系也可用圖形來表示。設(shè)集合到上的一個(gè)二元關(guān)系為，首先我們在平面上做出個(gè)結(jié)點(diǎn)分別記作，另外做個(gè)結(jié)點(diǎn)分別記作。如果，則從結(jié)點(diǎn)至結(jié)點(diǎn)做一有向弧，其箭頭指向，如果，則之間沒有線

14、段連接。用這種方法連接起來的圖稱為的關(guān)系圖。例3.5.8 畫出例3.5.6的關(guān)系圖。解 本題的關(guān)系圖如圖3-11所示： 圖3-11 例3.5.8的關(guān)系圖例3.5.9 設(shè)，畫出的關(guān)系圖。 解 因?yàn)槭巧系年P(guān)系，故只需畫出中的每個(gè)元素即可。如果，就畫一條由到的有向弧。若，則畫出的是一條自回路。本題的關(guān)系圖如圖3-12所示。 3 2 1 45 圖3-12 例3.5.9的關(guān)系圖關(guān)系圖主要表達(dá)結(jié)點(diǎn)與結(jié)點(diǎn)之間的鄰接關(guān)系，故關(guān)系圖與結(jié)點(diǎn)位置和線段的長短無關(guān)。從到的關(guān)系是的子集，即，而，所以，。令，則。因此，我們今后通常限于討論同一集合上的關(guān)系。3.6 關(guān)系的性質(zhì)及其判定方法3.6.1 關(guān)系的性質(zhì)定義設(shè)是定義在

15、集合上的二元關(guān)系，如果（1）對于每一個(gè)，都有，則稱是自反的(Reflexive)。即在上自反（2）對于每一個(gè)，都有，則稱是反自反的(Antireflexive)。即在上反自反（3）對于任意，若，就有，則稱是對稱的(Symmetric)。即在上對稱（4）對于任意，若，必有，則稱在上是反對稱的(Antisymmetric)。即在上反對稱（5）對于任意，若，就有，則稱在上是傳遞的(Transitive)。即在上傳遞例 設(shè)，則集合上的關(guān)系是自反而不是反自反的關(guān)系；是反自反而不是自反的關(guān)系；是既不是自反也不是反自反的關(guān)系；是對稱的而不是反對稱的關(guān)系；是反對稱的而不是對稱的關(guān)系；是既對稱也反對稱的關(guān)系；是

16、既不對稱也不反對稱關(guān)系。，是可傳遞的關(guān)系；是不可傳遞的關(guān)系，因?yàn)?，但。由定義及例3.6.1可知：（1）對任意一個(gè)關(guān)系，若自反則它一定不反自反，若反自反則它也一定不自反；但不自反，它未必反自反，若不反自反，也未必自反。（2）存在著既對稱也反對稱的關(guān)系。圖3-5表明了自反與反自反、對稱與反對稱性之間的關(guān)系。圖3-5例 (1) 集合之間的關(guān)系是自反的、反對稱的和可傳遞的。因?yàn)椋?） 對于任意集合，均有成立，所以是自反的；2） 對于任意集合，若且，則，所以是反對稱的；3） 對于任意集合，若且，則，所以是可傳遞的。（2）平面上三角形集合中的相似關(guān)系是自反的、對稱的和可傳遞的。因?yàn)椋喝我庖粋€(gè)三角形都與自身

17、相似；若三角形相似于三角形，則三角形必相似于三角形；若三角形相似于三角形，且三角形相似于三角形，則三角形必相似于三角形。（3）人類的祖先關(guān)系是反自反、反對稱和可傳遞的。（4）實(shí)數(shù)集上的“>”關(guān)系是反自反、反對稱和可傳遞的。（5）實(shí)數(shù)集上的“”關(guān)系是自反、反對稱和可傳遞的。（6）實(shí)數(shù)集上的“=”關(guān)系是自反、對稱、反對稱和可傳遞的。（7）人群中的父子關(guān)系是反自反和反對稱的。（8）正整數(shù)集上的整除關(guān)系是自反、反對稱和可傳遞的。（9）是反自反、對稱、反對稱和可傳遞的。（10）任意非空集合上的全關(guān)系是自反的、對稱的和可傳遞的。例3.6.3 設(shè)整數(shù)集上的二元關(guān)系定義如下：是整數(shù)，驗(yàn)證在上是自反和對稱

18、的。證明 ，即，故是自反的。又設(shè)，如果，即是整數(shù)，則也必是整數(shù)，即，因此是對稱的。3.6.2 由關(guān)系圖、關(guān)系矩陣判別關(guān)系的性質(zhì)例 集合，上的關(guān)系的關(guān)系矩陣為：，的關(guān)系圖如圖3-6所示。討論的性質(zhì)。圖3-6解 從的關(guān)系矩陣和關(guān)系圖容易看出，是自反的、對稱的。一般地，我們有：（1）若關(guān)系是自反的，當(dāng)且僅當(dāng)其關(guān)系矩陣的主對角線上的所有元素都是1；其關(guān)系圖上每個(gè)結(jié)點(diǎn)都有自環(huán)。（2）若關(guān)系是對稱的，當(dāng)且僅當(dāng)其關(guān)系矩陣是對稱矩陣；其關(guān)系圖上任意兩個(gè)結(jié)點(diǎn)間若有定向弧，必是成對出現(xiàn)的。（3）若關(guān)系是反自反的，當(dāng)且僅當(dāng)其關(guān)系矩陣的主對角線上的元素皆為0；關(guān)系圖上每個(gè)結(jié)點(diǎn)都沒有自環(huán)。（4）若關(guān)系是反對稱的，當(dāng)且僅

19、當(dāng)其關(guān)系矩陣中關(guān)于主對角線對稱的元素不能同時(shí)為1；其關(guān)系圖上任意兩個(gè)不同結(jié)點(diǎn)間至多出現(xiàn)一條定向弧。（5）若關(guān)系是可傳遞的，當(dāng)且僅當(dāng)其關(guān)系矩陣滿足：對，若且，則；其關(guān)系圖滿足：對，若有弧由指向，且又有弧由指向，則必有一條弧由指向。 例 圖3-7是由關(guān)系圖所表示的上的5個(gè)二元關(guān)系。 （1） （2）（3） （4） （5）圖3-7請判斷它們的性質(zhì)。解 (1) 是反對稱、傳遞但不是對稱的關(guān)系，而且是既不自反也不反自反的關(guān)系；(2) 是自反、傳遞、反對稱的關(guān)系，但不是對稱也不是反自反的關(guān)系；(3) 是反自反但不是對稱、不是反對稱、不是自反也不是傳遞的關(guān)系；(4) 是不自反、不反自反但是傳遞的關(guān)系，而且既是

20、對稱也是反對稱的關(guān)系； (5) 是自反、反對稱但不是傳遞、不是對稱也不是反自反的關(guān)系。 3.7 復(fù)合關(guān)系和逆關(guān)系 復(fù)合關(guān)系 1. 復(fù)合關(guān)系的定義定義 設(shè)是從到的關(guān)系，是從到的關(guān)系，則稱為和的復(fù)合關(guān)系(Compositive Relation)，表示為從和求，稱為關(guān)系的復(fù)合運(yùn)算。復(fù)合運(yùn)算是關(guān)系的二元運(yùn)算，它能夠由兩個(gè)關(guān)系生成一個(gè)新的關(guān)系，以此類推。例如，是從到的關(guān)系，是從到的關(guān)系，是從到的關(guān)系，則是從到的關(guān)系。例設(shè)是由到的關(guān)系，是由到 的關(guān)系，分別定義為：于是復(fù)合關(guān)系。例3.7.2 設(shè)是所有人的集合。，那么；而。例3.7.3 設(shè)和是集合上的關(guān)系，或，求、和。解 2. 關(guān)系的復(fù)合運(yùn)算的性質(zhì)定理 設(shè)

21、是由集合到的關(guān)系，則。定理3.7.2 設(shè)是從到的關(guān)系，是從到的關(guān)系，則有（1）（2）（3）若，則。證 （1）和（2）是顯然的，下面我們證明（3）。用反證法。反設(shè)，則必存在，使，從而，使，故且 ，所以，這就與矛盾，因此，。定理3.7.3 （1）設(shè)、和分別是從到、到和到的關(guān)系，則即關(guān)系的復(fù)合運(yùn)算滿足結(jié)合律。（2）設(shè)和都是從到的關(guān)系，是從到的關(guān)系，則1）2）（3）設(shè)是從到的關(guān)系，和都是從到的關(guān)系，則1） 2）證 我們只證明（2），其它證明類似。 1） 所以 2） 所以 。注意：一般來說，（1）；（2）關(guān)系的復(fù)合運(yùn)算不滿足交換律。 例3.7.4 （1）設(shè)，和都是從到的關(guān)系，是從到的關(guān)系，則，可見，但。

22、（2）設(shè)，和都是集合上的關(guān)系，則，而，所以。由于關(guān)系的復(fù)合運(yùn)算滿足結(jié)合律，所以可以寫成。一般地，若是一由到的關(guān)系，是由到的關(guān)系，是一由到的關(guān)系，則不加括號的表達(dá)式唯一地表示一由到的關(guān)系，在計(jì)算這一關(guān)系時(shí)，可以運(yùn)用結(jié)合律將其中任意兩個(gè)相鄰的關(guān)系先結(jié)合。特別地，當(dāng) ，即是集合上的關(guān)系時(shí)，復(fù)合關(guān)系 簡記作，它也是集上的一個(gè)關(guān)系。 復(fù)合關(guān)系的矩陣表示及圖形表示 因?yàn)殛P(guān)系可用矩陣表示，所以復(fù)合關(guān)系也可用矩陣表示。已知從集合到集合上的關(guān)系為，關(guān)系矩陣，從集合到集合的關(guān)系，關(guān)系矩陣，表示復(fù)合關(guān)系的矩陣可構(gòu)造如下：若，使得且，則。在集合中能夠滿足這樣條件的元素可能不止一個(gè)，例如另有也滿足且。在所有這樣的情況下

23、，都是成立的。這樣，當(dāng)我們掃描的第行和的第列時(shí)，若發(fā)現(xiàn)至少有一個(gè)這樣的，使得第行的第個(gè)位置上的記入值和第列的第個(gè)位置上的記入值都是1時(shí)，則的第行和第列上的記入值為1；否則為0。因此可以用類似于矩陣乘法的方法得到：其中 式中代表邏輯加，滿足，；代表邏輯乘，滿足，。例3.7.5 給定集合，在集合上定義兩種關(guān)系：，求和的矩陣。解因?yàn)殛P(guān)系可用圖形表示，所以復(fù)合關(guān)系也可用圖形表示。例3.7.6 例3.7.1中的兩個(gè)關(guān)系與的復(fù)合很容易通過下面的關(guān)系圖（見圖3-8）得到。圖3-8 示意圖由該圖立即可得。 逆關(guān)系關(guān)系是序偶的集合，由于序偶的有序性，關(guān)系還有一些特殊的運(yùn)算。定義 設(shè)是從到的二元關(guān)系，若將中每一序

24、偶的元素順序互換，得到的集合稱為的逆關(guān)系(Inverse Relation)，記為。即例如，在實(shí)數(shù)集上，關(guān)系“<”的逆關(guān)系是“>”。從逆關(guān)系的定義，我們?nèi)菀卓闯?。定理3.7.4 設(shè)、和都是從到的二元關(guān)系，則下列各式成立。（1）（2）(3) (4) 這里 -(5) 證明 （1） （4） （5）因?yàn)椋视?其它自證。定理3.7.5 設(shè)為從到的關(guān)系，是從到的關(guān)系，則（1）（2）證明 （1） 所以 （2）自證。定理3.7.6 設(shè)是上的二元關(guān)系，則（1）是對稱的，當(dāng)且僅當(dāng)；（2）是反對稱的，當(dāng)且僅當(dāng)；（3）是傳遞的，當(dāng)且僅當(dāng)；（4）是自反的，當(dāng)且僅當(dāng)；（5）是反自反的，當(dāng)且僅當(dāng)證明 （1）

25、若是對稱的，則對， 所以，；若 ，則對，所以，是對稱的。（3）若，則對，所以，是傳遞的；若是傳遞的， 所以，。其它證明留為作業(yè)。關(guān)系的圖形，是關(guān)系圖形中將其弧的箭頭方向反置。的關(guān)系矩陣是的轉(zhuǎn)置矩陣。例3.7.7 設(shè)是到的二元關(guān)系，是到的二元關(guān)系，且，求和。解 或從 ， 得 故取到同樣的序元素；而 故取到同樣的序元素。例3.7.8 給定集合，是上的二元關(guān)系，的關(guān)系矩陣求和的關(guān)系矩陣解 3.8 關(guān)系的閉包運(yùn)算關(guān)系作為集合, 在其上已經(jīng)定義了并、交、差、補(bǔ)、復(fù)合及逆運(yùn)算。現(xiàn)在再來考慮一種新的關(guān)系運(yùn)算關(guān)系的閉包運(yùn)算，它是由已知關(guān)系，通過增加最少的序偶生成滿足某種指定性質(zhì)的關(guān)系的運(yùn)算。 例如, 設(shè)，上的

26、二元關(guān)系，則上含且最小的自反關(guān)系是：；上含且最小的對稱關(guān)系是： ；上含且最小的傳遞關(guān)系是： 。定義 設(shè)是上的二元關(guān)系，如果有另一個(gè)上的關(guān)系滿足：（1）是自反的（對稱的，傳遞的）；（2）；（3）對于任何上的自反的（對稱的，傳遞的）關(guān)系，若，就有。則稱關(guān)系為的自反（對稱，傳遞） 閉包(Reflexive (Symmetric，Transitive) Closure)，記作。顯然，自反（對稱，傳遞）閉包是包含的最小自反（對稱，傳遞）關(guān)系。定理 設(shè)是上的二元關(guān)系，那么（1）是自反的，當(dāng)且僅當(dāng)（2）是對稱的，當(dāng)且僅當(dāng)（3）是傳遞的，當(dāng)且僅當(dāng)證明 （1）若是自反的，對任何包含的自反關(guān)系，有，故；若，根據(jù)閉

27、包定義，必是自反的。（2）、（3）的證明完全類似。 下面討論由給定關(guān)系，求取的方法。定理 設(shè)是集合上的二元關(guān)系，則（1）；（2）（3），通常也記作。證明 （1）令，因?yàn)?，故，于是在上是自反的。又即。若有自反關(guān)系且，顯然有，于是 ，所以 。 （2）令，因?yàn)?所以是對稱的。若是對稱的且，則。當(dāng)時(shí)，；當(dāng)時(shí)，。因此 ，故 。（3）令，先證是傳遞的。 ，則存在自然數(shù)，有 ，因此 ，所以，是傳遞的。顯然，。若有傳遞關(guān)系且，則存在自然數(shù)，有 ，則 ，使得 ，因此，由于是傳遞關(guān)系，則，所以。故。例 設(shè)，是上的二元關(guān)系，求。解 為了求得，先寫出即繼續(xù)這個(gè)運(yùn)算有： 從以上例題中看到，若有限，譬如含有個(gè)元素，那么求

28、取上二元關(guān)系的傳遞閉包不必計(jì)算到對的無限大次復(fù)合，而最多不超過次復(fù)合。定理3.8.3 設(shè)是含有個(gè)元素的集合，是上的二元關(guān)系，則存在一個(gè)正整數(shù)，使得證明 設(shè)，記。若，則存在整數(shù)，使得成立，既存在序列，有。設(shè)滿足上述條件的最小大于，不妨，則序列中必有，使得或。不妨，此時(shí)序列就成為，這表明存在，其中，這與是最小的假設(shè)矛盾，所以，不成立，即。所以 （）一般地，取，式中的給出了復(fù)合次數(shù)的上限。 例 設(shè)，給定上的關(guān)系，求。解 所以 即 為計(jì)算元素較多的有限集合上二元關(guān)系的傳遞閉包， Warshall在1962年提出了一個(gè)有效的算法（假定集合含有個(gè)元素）：（） 置新矩陣：；（） 置：；（） 對，若（），則置

29、：，；（） ：；（） 如果，則轉(zhuǎn)到步驟（3），否則停止。例3.8.3 已知，求。 解 按照Warshall算法，從出發(fā)，只要遵循“置行查列遍尋真，見真行上析當(dāng)今，行推列移下右再，行窮列盡閉包成”便可直接求得。 對集合上關(guān)系，首先將其關(guān)系矩陣賦予：而后的每后一次循環(huán)重復(fù)操作， 均在前一次操作結(jié)果的矩陣上進(jìn)行。置當(dāng)今行為第1行，查看第1列中1，對有1的行進(jìn)行改寫，改寫方法是：將當(dāng)今行的元素與列中有1的行的元素分別做析取。對本例，時(shí)，第1列中只有，將第一行與第一行各對應(yīng)元素進(jìn)行邏輯加，仍記于第一行：；置當(dāng)今行為第2行， 查看第2列中1， 對有1的行進(jìn)行改寫。對本例，時(shí)，第二列中，將第二行與第一行各對

30、應(yīng)元素進(jìn)行邏輯加，仍記于第一行：；置當(dāng)今行為第3行，重復(fù)上述操作并結(jié)束。對本例，時(shí)，第三列中，將第三行分別與第一行、第二行、第三行各對應(yīng)元素進(jìn)行邏輯加，仍分別記于第一行、第二行、第三行：得 。結(jié)果與例3.8.2一致。傳遞閉包在語法分析中有很多應(yīng)用，先以下列說明/例3.8.4 設(shè)有一字母表并給定下面六條規(guī)則：為定義在上的二元關(guān)系且，即是從出發(fā)用一條規(guī)則推出一串字符，使其第一個(gè)字符恰為。說明每個(gè)字母連續(xù)應(yīng)用上述規(guī)則可能推出的頭字符。解 則表示從出發(fā)，經(jīng)過多次連續(xù)推導(dǎo)而得的字符串，其第一個(gè)字符恰為的關(guān)系，此關(guān)系即是。按照Warshall算法計(jì)算的過程中，時(shí)，由于第五行的元素都等于零，的賦值不變。時(shí)，

31、由于第3、6、7列各元素均為零，的賦值不變。經(jīng)計(jì)算得 因此。 這說明應(yīng)用給定的六條規(guī)則，從出發(fā)推導(dǎo)的頭字符有三種可能，而從出發(fā)推導(dǎo)的頭字符有兩種可能，而從推出的頭字符有兩種可能，從出發(fā)推導(dǎo)的頭字符只可能為。從一種性質(zhì)的閉包關(guān)系出發(fā)，求取另一種性質(zhì)的閉包關(guān)系，具有以下運(yùn)算律： 定理3.8.4 設(shè)是集合上的二元關(guān)系，則（1）（2）（3）證明 （1） 這里，。（2）這里，（）。（3）留作練習(xí)請讀者自證。3.9 等價(jià)關(guān)系與相容關(guān)系 本節(jié)討論兩類特殊關(guān)系等價(jià)關(guān)系與相容關(guān)系。在討論之前，我們先引進(jìn)兩個(gè)概念集合的劃分與覆蓋。 集合的劃分和覆蓋 設(shè)是某一所綜合性大學(xué)本科學(xué)生全體組成的集合，是對的某種分類的集合

32、（）。若按文理科分類，則有，其中表示理科學(xué)生全體的集合、表示文科學(xué)生全體的集合；若按年級分類，則有，其中表示該大學(xué)年級學(xué)生全體的集合；若按系分類，則有，這說明這所大學(xué)有六個(gè)系。分類法盡管給出了三種，但是它們有個(gè)共同的特點(diǎn)：(1) 的元素都是的非空子集；(2) 的元素求交是空集、求并就是。 此時(shí)，我們就說是集合的一個(gè)劃分。 定義 設(shè)是非空集合，的子集的集合，如果滿足： （1）都是非空集合； （2）則稱集合是集合的覆蓋(Cover)，稱是覆蓋的分塊。如果除以上條件外，另有（），則稱是的劃分（或分劃）(Partition)。顯然，若是劃分則必是覆蓋，其逆不真。若，則有兩個(gè)簡單的劃分：一是，稱為的最大

33、劃分(分塊最多)；二是，稱為的最小劃分(分塊最少)。 例如，考慮下列子集：，則是的覆蓋；是的劃分，其中是最小劃分，是最大劃分；既不是劃分也不是覆蓋。 定義 若與是同一集合的兩種劃分，則其中所有組成的集合，稱為和的交叉劃分，即 注意：和的交叉劃分一般不是，而是以與元素之間的所有非空交集作元素的集合。 例如，所有生物的集合，可分割成，其中表示所有植物的集合，表示所有動(dòng)物的集合；又也可分割成，其中表示史前生物，表示史后生物。則其交叉劃分為，其中表示史前植物，表示史后植物，表示史前動(dòng)物，表示史后動(dòng)物。 定理 設(shè)與是同一集合的兩種劃分，則其交叉劃分也是原集合的一種劃分。 證明 和的交叉劃分是： 在交叉劃

34、分中，任取兩元素和，（），因?yàn)?，所以 ；其次，交叉劃分中所有元素的并為 所以，和的交叉劃分也是的一種劃分。定義 給定的任意兩個(gè)劃分與，若對于每一個(gè)均有，使（），則稱為的加細(xì)。若還有，則稱為的真加細(xì)。定理 任何兩種劃分的交叉劃分，都是原來各劃分的一種加細(xì)。證明 設(shè)與的交叉劃分為，對中任意元素必有和，則分別是和的加細(xì)。 等價(jià)關(guān)系與等價(jià)類1. 等價(jià)關(guān)系 定義 設(shè)為定義在集合上的一個(gè)關(guān)系，若是自反的、對稱的和傳遞的，則稱為等價(jià)關(guān)系(Equivalence Relation)。例 3 . 9. 1 （1） 平面上三角形集合中，三角形的相似關(guān)系是等價(jià)關(guān)系。（） 數(shù)的相等關(guān)系是任何數(shù)集上的等價(jià)關(guān)系。（3）

35、一群人的集合中姓氏相同的關(guān)系也是等價(jià)關(guān)系。（4）設(shè)是任意非空集合，則上的恒等關(guān)系和全域關(guān)系均是上的等價(jià)關(guān)系。例3.9.2 設(shè)集合， 驗(yàn)證是上的等價(jià)關(guān)系。證明 的關(guān)系矩陣：關(guān)系圖如圖3-9所示。圖3-9關(guān)系矩陣中，對角線上的所有元素都是1，關(guān)系圖上每個(gè)結(jié)點(diǎn)都有自環(huán)，說明是自反的。關(guān)系矩陣是對稱的，關(guān)系圖上任意兩結(jié)點(diǎn)間或沒有弧線連接，或有成對弧出現(xiàn)，故是對稱的。從的序偶表示式中，可以看出是傳遞的。故是上的等價(jià)關(guān)系。例3.9.3 設(shè)為整數(shù)集，其中當(dāng)且僅當(dāng)，使得，證明是等價(jià)關(guān)系。證明 設(shè)任意（1），所以，是自反的；（2）若，(為整數(shù))，則 ，所以，是對稱的；（3）若，則， (為整數(shù))，所以，是傳遞的。

36、因此，是等價(jià)關(guān)系。我們稱之為整數(shù)集上的模同余關(guān)系(Congruence Modulo )。2等價(jià)類定義 設(shè)是集合上的等價(jià)關(guān)系，對任何，若，則稱與等價(jià)。對任何，集合中等價(jià)于的所有元素組成的集合稱為以為代表元的（關(guān)于等價(jià)關(guān)系的）等價(jià)類(Equivalence Class)，記作。即由等價(jià)類的定義可知是非空的，因?yàn)?，。因此，任給集合及其上的等價(jià)關(guān)系，必可寫出上各個(gè)元素的等價(jià)類。例如，在例3.9.2中，的各個(gè)元素的等價(jià)類為：；可見，上的等價(jià)關(guān)系的不同的等價(jià)類有兩個(gè)。例3.9.4 設(shè)是整數(shù)集合，是模同余關(guān)系，即，確定由的元素所產(chǎn)生的等價(jià)類。解 例3.9.3已證明整數(shù)集合上的模同余的關(guān)系是等價(jià)關(guān)系，故本例

37、中由的元素所產(chǎn)生的等價(jià)類是從本例可以看到，在集合上模3同余等價(jià)關(guān)系所構(gòu)成的等價(jià)類有：定理 設(shè)給定集合上的等價(jià)關(guān)系，對于有當(dāng)且僅當(dāng)。證明 若 ，因?yàn)?，故，即 ，則。若 ，則，即 ；，即 。所以，。定義 集合上的等價(jià)關(guān)系，其所有等價(jià)類的集合稱作關(guān)于的商集(Quotient Set )，記作，即例如，例3.9.2中，商集： 例3.9.4中商集： 。我們注意到商集中，且任意兩個(gè)等價(jià)類的交為，于是我們有下述重要定理。定理 集合上的等價(jià)關(guān)系，決定了的一個(gè)劃分，該劃分就是商集。為證定理，我們需要證明非空集合在其上的等價(jià)關(guān)系下形成的等價(jià)類的全體的集合商集滿足：(1) 每一等價(jià)類都是的子集， 中任一元素均屬于

38、某一等價(jià)類， 即等價(jià)類全體的并集是；(2) 不同的等價(jià)類之間交是空集。 證明 ，因?yàn)?，所以，從而；因?yàn)樽苑矗?，所以，則 ；故 。(1) 得證。為證明（2），用反證法：設(shè)，且 則 ，使成立，由對稱性得 ，再由傳遞性得 ，據(jù)定理，必有 ，這與題設(shè)矛盾，（2）得證。所以，是的對應(yīng)于的一個(gè)劃分。定理設(shè)是集合的一個(gè)劃分，則存在上的一個(gè)等價(jià)關(guān)系，使得是關(guān)于的商集。證明 在集合上定義關(guān)系，對任意，當(dāng)且僅當(dāng)在同一分塊中?？梢宰C明這樣定義的關(guān)系是一個(gè)等價(jià)關(guān)系。因?yàn)椋海?）與在同一分塊中，故必有，即是自反的。（2）若與在同一分塊中，與也必在同一分塊中，即 ，故是對稱的。（3）若與在同一分塊中，與在同一分塊中，

39、因?yàn)?，即屬于且僅屬于一個(gè)分塊，故與必在同一分塊中，即 ，故是傳遞的。所以，是等價(jià)關(guān)系。由的定義可知： 。由定理可知：由集合的劃分所確定的上的等價(jià)關(guān)系為：定理和定理說明：非空集合上的等價(jià)關(guān)系與的劃分一一對應(yīng)。例3.9.5 設(shè)的劃分，試由劃分確定上的一個(gè)等價(jià)關(guān)系。解 顯然，。定理 設(shè)和為非空集合上的等價(jià)關(guān)系，則。證明 ，。若 ，故 ，即；若，即，則對，必有，使得，故 所以， ；類似地有 ，因此，。 相容關(guān)系定義3.9.4 給定集合上的關(guān)系，若是自反的、對稱的，則稱是上的相容關(guān)系Cconsistent Relation)。相容關(guān)系只要求滿足自反性與對稱性，因此，等價(jià)關(guān)系必定是相容關(guān)系但反之不真。

40、例3.9.6 設(shè)是由下列英文單詞組成的集合，定義關(guān)系：，且和有相同的字母顯然，是一個(gè)相容關(guān)系。令的關(guān)系圖如圖3-10所示。 圖3-10的關(guān)系矩陣為。由于相容關(guān)系是自反和對稱的，因此，其關(guān)系矩陣的對角線元素都是，且矩陣是對稱的。為此我們可將矩陣用梯形表示。同理，在相容關(guān)系的關(guān)系圖中，每個(gè)結(jié)點(diǎn)處都有自環(huán)且每兩個(gè)相關(guān)聯(lián)的結(jié)點(diǎn)間的弧線都是成對出現(xiàn)的，為了簡化圖形，我們今后對相容關(guān)系圖，不畫自環(huán)，并用單線代替雙向弧線，因此，上例的關(guān)系矩陣和關(guān)系圖可簡化為表3-1和圖3-11。表3-1 例的簡化關(guān)系矩陣 圖3-11定義3.9.5 設(shè)是集合上的相容關(guān)系， ，如果對于中任意兩個(gè)元素 有，就稱是由相容關(guān)系產(chǎn)生的

41、相容類(Consistent Class)。例如，上例中相容關(guān)系可產(chǎn)生相容類等等。對于前三個(gè)相容類，都能加進(jìn)新的元素組成新的相容類，而后兩個(gè)相容類，加入任一新元素，就不再組成相容類，稱它們?yōu)樽畲笙嗳蓊?Maximal Consistent Class)。定義3.9.6 設(shè)是集合上的相容關(guān)系，不能真包含在任何其它相容類中的相容類，稱作最大相容類，記作。若為最大相容類，顯然它是的子集，對于任意，必與中的所有元素有相容關(guān)系。而在中沒有任何元素與所有元素有相容關(guān)系。根據(jù)最大相容類的定義，它可以從相容關(guān)系的簡化關(guān)系圖求得，具體方法是：（1）在相容關(guān)系的簡化關(guān)系圖中，每一個(gè)最大完全多邊形的頂點(diǎn)集合，就是一

42、個(gè)最大相容類。所謂完全多邊形(Complete Polygon)，就是其每個(gè)頂點(diǎn)都與其它頂點(diǎn)連接的多邊形。例如一個(gè)三角形是完全多邊形，一個(gè)四邊形加上兩條對角線就是完全多邊形。（2）在的簡化關(guān)系圖中，每一個(gè)孤立結(jié)點(diǎn)的單點(diǎn)集合，是一個(gè)最大相容類。（3）在的簡化關(guān)系圖中，不在完全多邊形中的邊的兩個(gè)端點(diǎn)的集合，是一個(gè)最大相容類。例3.9.7 由例3.9.6中相容關(guān)系的簡化關(guān)系圖3-11可得其全部最大相容類為：定理3.9.7 設(shè)是集合上的相容關(guān)系，是一個(gè)相容類，那么必存在一個(gè)最大相容類，使得。證明 設(shè)，構(gòu)造相容類序列，其中，且，其中是滿足而 與中各元素都有相容關(guān)系的最小下標(biāo)。由于的元素個(gè)數(shù)， 所以至多經(jīng)

43、過步，就使這個(gè)過程終止，而此序列的最后一個(gè)相容類，就是所要找的最大相容類。從定理3.9.7中可以看到，的任一元素，它可以組成相容類，因此必包含在一個(gè)最大相容類中，因此，如由所有最大相容類作出一個(gè)集合，則中每一個(gè)元素至少屬于該集合的一個(gè)成員之中，所以最大相容類集合必覆蓋集合。定義3.9.6 在集合上給定相容關(guān)系，其最大相容類的集合稱作集合的完全覆蓋(Complete Cover)，記作。例3.9.8 設(shè)集合，上二元關(guān)系求的完全覆蓋。 解 是上的相容關(guān)系(自反，對稱)。 的簡化關(guān)系圖如圖3-12所示：圖3-12的最大相容類是確定的，即。因此，集合是的完全覆蓋。定理3.9.8 給定集合的覆蓋，由它確

44、定的關(guān)系是上的相容關(guān)系。證明 因?yàn)?，對于任意，必存在某個(gè)， 使得 ，所以， ，即 ， 因此，是自反的。其次，若有任意，且，則必存在某個(gè)，使 ，故必有 ，即，所以是對稱的。因此，是上的相容關(guān)系。從上述定理可以看到，給定集合上的任意一個(gè)覆蓋，必可在上構(gòu)造對應(yīng)于此覆蓋的一個(gè)相容關(guān)系，但是不同的覆蓋卻能構(gòu)造相同的相容關(guān)系。例如，設(shè)，集合和都是的覆蓋，但它們可以產(chǎn)生相同的相容關(guān)系：因此，相容關(guān)系與覆蓋之間不是一一對應(yīng)的。但是我們有：定理3.9.9 集合上相容關(guān)系與完全覆蓋一一對應(yīng)。習(xí)題3.91設(shè)是集合的劃分，試證明是集合的劃分。其中。2把個(gè)元素的集合劃分成兩個(gè)分塊，共有多少種不同的方法？3已知及其關(guān)系

45、如下，試說明是等價(jià)關(guān)系，并指出其等價(jià)類。（1）：自然數(shù)集， 能表示成形式，為任意整數(shù)；（2）：正整數(shù)的序偶，； （3）：實(shí)數(shù)部分非零的復(fù)數(shù)全體，；（4）：實(shí)數(shù)集，其中表示小于或等于的最大整數(shù)。4設(shè)，試根據(jù)以下的劃分求上相應(yīng)的等價(jià)關(guān)系，并畫出關(guān)系圖。（1）； （2）；（3）； （4）.5證明：（1）設(shè)是上的關(guān)系。對于而言，如且蘊(yùn)含，則關(guān)系稱為循環(huán)的。證明是自反的和循環(huán)的，當(dāng)且僅當(dāng)它是一等價(jià)關(guān)系。（2）設(shè)和是上的等價(jià)關(guān)系，分別是相應(yīng)于的劃分。證明：當(dāng)且僅當(dāng)中每一個(gè)等價(jià)類包含于的一些等價(jià)類中。（3）設(shè)和是上的等價(jià)關(guān)系，其對應(yīng)等價(jià)類的數(shù)目（稱為等價(jià)關(guān)系的秩）分別為。試證是秩至多為的上的等價(jià)關(guān)系，但不一

46、定是上的等價(jià)關(guān)系。6（1）試敘述根據(jù)上的相容關(guān)系來定義一個(gè)覆蓋的方法，此方法所定義的覆蓋是否唯一？（2）給定集合的覆蓋，能否確定此覆蓋對應(yīng)的相容關(guān)系？（3）若和是上的相容關(guān)系，問，是不是相容關(guān)系？3.10 偏序關(guān)系偏序關(guān)系的定義在一個(gè)集合上，我們常常要考慮元素的次序關(guān)系，其中很重要的一類關(guān)系稱作偏序關(guān)系。定義 設(shè)是一個(gè)集合，如果上的一個(gè)關(guān)系，滿足自反性、反對稱性和傳遞性，則稱是上的一個(gè)偏序關(guān)系(Partially Ordered Relation)，并把它記為“”。序偶稱作偏序集(Partially Ordered Set Or Poset)。例 在實(shí)數(shù)集上，小于等于關(guān)系“”是偏序關(guān)系。因?yàn)椋?/p>

47、（1）對于任何實(shí)數(shù)，有成立，故是自反的；（2）對任何實(shí)數(shù)，如果且，則必有，故是反對稱的；（3）對任何實(shí)數(shù)，如果，那么必有，故是傳遞的。例 設(shè)為任意非空集合，上的包含關(guān)系是偏序關(guān)系。因?yàn)椋海?）對于任意，有，所以“”是自反的； （2）對任意，若且，則所以“”是反對稱的； （3）對任意，若且，則，所以“”是可傳遞的。 例3.10.3 正整數(shù)集上的整除關(guān)系是偏序關(guān)系。因?yàn)椋?（1）對于任何正整數(shù)，有成立，故“”是自反的；（2）對任何正整數(shù)，如果且，則必有，故“”是反對稱的；（3）對任何正整數(shù)，如果且，那么必有，故“”是傳遞的。例3.10.4 （1）實(shí)數(shù)集上的小于關(guān)系“<”不是偏序關(guān)系。（2）任

48、意非空集合的冪集上的真包含關(guān)系“”不是偏序關(guān)系。 偏序關(guān)系的哈斯圖為了更清楚地描述偏序集合中元素間的層次關(guān)系，我們先介紹“蓋住”的概念。定義 在偏序集合中，如果，且沒有其它元素滿足，則稱元素蓋住元素。并且記COV蓋住。稱為偏序集中的蓋住關(guān)系。顯然。例3.10.5 設(shè)，并設(shè)“”為整除關(guān)系，求COV。解 “”COV對于給定偏序集，它的蓋住關(guān)系是唯一的，所以哈斯(Hasse)根據(jù)蓋住的概念給出了偏序關(guān)系圖的一種畫法，這種畫法畫出的圖稱為哈斯圖(Hasse Diagram)，其作圖規(guī)則如下： （1） 用小圓圈代表元素。（2） 如果且，則將代表的小圓圈畫在代表的小圓圈之上。（3） 如果COV，則在與之間

49、用直線連接。根據(jù)這個(gè)作圖規(guī)則，例3.10.5中偏序集的一般關(guān)系圖和哈斯圖如圖3-13所示。 圖3-13例3.10.6 設(shè)，則“”關(guān)系是上的偏序關(guān)系，它們的哈斯圖分別如圖3-14的所示。 圖3-14 例3.10.7 設(shè)，上的整除關(guān)系“”是一偏序關(guān)系，其哈斯圖如圖3-15所示。圖3-15 偏序集中特殊位置的元素從偏序集的哈斯圖可以看到偏序集中各個(gè)元素之間具有分明的層次關(guān)系，則其中必有一些處于特殊位置的元素。下面討論偏序集中具有特殊位置的元素。定義3.10.3 設(shè)是一個(gè)偏序集合，且是的子集，若有某個(gè)元素，使得（1）不存在，滿足且，則稱為的極大元(Maximal Element)；（2）不存在，滿足且，則稱為的極小元(Minimal Element)；（3）對每一個(gè)有，