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

1、學(xué)習(xí)目標(biāo)：1深刻理解序偶、笛卡爾積、關(guān)系、集合的劃分與覆蓋、等價(jià)關(guān)系、等價(jià)類(lèi)、商集、相容關(guān)系、（最大）相容類(lèi)、偏序關(guān)系、極大元、極小元、上（下）界、上（下）確界、最大（小）元、全序關(guān)系、良序關(guān)系等概念；2掌握集合的交、并、差、補(bǔ)、對(duì)稱(chēng)差的運(yùn)算及其運(yùn)算規(guī)律；3掌握關(guān)系的交、并、逆、復(fù)合運(yùn)算、閉包運(yùn)算及其性質(zhì)；4掌握關(guān)系的矩陣表示和關(guān)系圖；5深刻理解關(guān)系的自反性、反自反性、對(duì)稱(chēng)性、反對(duì)稱(chēng)性和傳遞性，掌握其判別方法；6掌握集合的覆蓋與劃分的聯(lián)系與區(qū)別；7掌握偏序關(guān)系的判別及其哈斯圖的畫(huà)法；會(huì)求偏序集中給定集合的極大元、極小元、上（下）界、上（下）確界、最大（?。┰?。主要內(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à)類(lèi)、等價(jià)關(guān)系與集合的劃分的聯(lián)系；4偏序關(guān)系判別及其哈斯圖的畫(huà)法、偏序集中特異位置元素的理解。 難點(diǎn)：1關(guān)系的傳遞性及其判別；2等價(jià)關(guān)系的特性；3偏序關(guān)系的哈斯圖的畫(huà)法；偏序集中特異位置元素的求法。 教學(xué)手段： 通過(guò)多個(gè)實(shí)例的精講幫助同學(xué)理解重點(diǎn)和難點(diǎn)的內(nèi)容，并通過(guò)大量的練習(xí)使同學(xué)們鞏固和掌握關(guān)系的性質(zhì)及其判別、關(guān)系的復(fù)合運(yùn)算及其性質(zhì)、等價(jià)關(guān)系的特性、偏序關(guān)系的哈斯圖的畫(huà)法及偏序集中特異位置元素的求法。習(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)（或稱(chēng)為集）是數(shù)學(xué)中的一個(gè)最基本的概念。所謂集合，就是指具有共同性質(zhì)的或適合一定條件的事物的全體，組成集合的這些“事物”稱(chēng)為集合的元素。集合常用大寫(xiě)字母表示，集合的元素常用小寫(xiě)字母表示。若是集合，是的元素，則稱(chēng)屬于，記作；若不是的元素，則稱(chēng)不屬于，記作。若組成集合的元素個(gè)數(shù)是有限的，則稱(chēng)該集合

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

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

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

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

8、素，第二個(gè)成員是的元素，所有這樣的序偶集合，稱(chēng)為集合和的笛卡爾乘積或直積(Cartesian Product)，記作。即例3.4.1 若, 求以及解 顯然，我們有：（1）；（2）如果，則。我們約定：若或，則。由笛卡爾積定義可知： 由于不是三元組，所以定理3.4.1 設(shè)、和為任意三個(gè)集合，則有（1）（2）（3）（4）證明 （1）設(shè) 因此， 。（4）設(shè) 因此， 。定理3.4.2 設(shè)、和為三個(gè)非空集合，則有 證明 設(shè)，對(duì)任意的，因此， 。反之，若，取，則對(duì)，有因此，。定理的第二部分，證明類(lèi)似。定理3.4.3 設(shè)、和為四個(gè)非空集合，則的充要條件為且。證明 若，對(duì)任意的，有 即 。反之，若且，設(shè)任意，有

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

10、號(hào)關(guān)系是序偶的集合。定義3.5.1 設(shè)、是任意兩個(gè)集合，則稱(chēng)直積的任一子集為從到的一個(gè)二元關(guān)系(Binary Relation )。二元關(guān)系亦簡(jiǎn)稱(chēng)關(guān)系，記為，。到的二元關(guān)系，如圖3-4所示。圖3-4集合到的二元關(guān)系是第一坐標(biāo)取自、第二坐標(biāo)取自的序偶集合。如果序偶，也說(shuō)與有關(guān)系，記為；如果序偶，則說(shuō)與沒(méi)有關(guān)系，記為。當(dāng)時(shí)，關(guān)系是的子集，這時(shí)稱(chēng)為集合上的二元關(guān)系。例3.5.1 （1）設(shè)，則，令因?yàn)?，所以，和均是由到的關(guān)系。（2）>=是實(shí)數(shù)且是實(shí)數(shù)集上的大于關(guān)系。定義3.5.2 設(shè)為到的二元關(guān)系，由的所有組成的集合稱(chēng)為的定義域或前域(Domain)，記作dom或，即 dom使的所有組成的集合稱(chēng)

11、為的值域(Range)，記作ran，即ran。的定義域和值域一起稱(chēng)作的域(Field)，記作FLD，即FLD domran顯然，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)系對(duì)任意集合，所以是由到的關(guān)系，也是上的關(guān)系，稱(chēng)為空關(guān)系(Empty Relation)。2全域關(guān)系因?yàn)?，所以是一個(gè)由到的關(guān)系，稱(chēng)為由到的全域關(guān)系(Universal Relation)。是上的一個(gè)關(guān)系，稱(chēng)為上的全域關(guān)系，通常記作，即。例3.5.4 若表示

12、家庭中父、母、子、女四個(gè)人的集合，確定上的全域關(guān)系和空關(guān)系，另外再確定上的一個(gè)關(guān)系，并指出該關(guān)系的前域和值域。解 設(shè)上同一家庭的成員的關(guān)系為， 設(shè)上的互不相識(shí)的關(guān)系為，則為全域關(guān)系，為空關(guān)系。設(shè)上的長(zhǎng)幼關(guān)系為，domran3恒等關(guān)系定義3.5.3 設(shè)是上的二元關(guān)系且滿(mǎn)足，則稱(chēng)是上的恒等關(guān)系(Identical Relation)。例如，則。因?yàn)殛P(guān)系是序偶的集合，因此，可以進(jìn)行集合的所有運(yùn)算。定理3.5.1 若和是從集合到集合的兩個(gè)關(guān)系，則、的并、交、補(bǔ)、差仍是到的關(guān)系。證明 因?yàn)?故 例3.5.5 若，求 ，和。解 ， 3.5.3 關(guān)系的表示 1集合表示法因?yàn)殛P(guān)系是序偶的集合，因此可用表示集合

13、的列舉法或描述法來(lái)表示關(guān)系。例如，例3.5.1的（1）中的關(guān)系，和及例3.5.2中的關(guān)系，均是用列舉法表示的關(guān)系；而例3.5.1的（2）中的關(guān)系和例3.5.5中的關(guān)系，都是用描述法表示的關(guān)系。有限集合間的二元關(guān)系除了可以用序偶集合的形式表達(dá)以外，還可用矩陣和圖形表示，以便引入線性代數(shù)和圖論的知識(shí)來(lái)討論。2矩陣表示法 設(shè)給定兩個(gè)有限集合，則對(duì)應(yīng)于從到的二元關(guān)系有一個(gè)關(guān)系矩陣，其中 。 如果是有限集合上的二元關(guān)系或和含有相同數(shù)量的有限個(gè)元素，則是方陣。例3.5.6 若，寫(xiě)出關(guān)系矩陣。解 例3.5.7 設(shè)，寫(xiě)出集合上的大于關(guān)系>的關(guān)系矩陣。 解 > 3關(guān)系圖表示法有限集合的二元關(guān)系也可用

14、圖形來(lái)表示。設(shè)集合到上的一個(gè)二元關(guān)系為，首先我們?cè)谄矫嫔献龀鰝€(gè)結(jié)點(diǎn)分別記作，另外做個(gè)結(jié)點(diǎn)分別記作。如果，則從結(jié)點(diǎn)至結(jié)點(diǎn)做一有向弧，其箭頭指向，如果，則之間沒(méi)有線段連接。用這種方法連接起來(lái)的圖稱(chēng)為的關(guān)系圖。例3.5.8 畫(huà)出例3.5.6的關(guān)系圖。解 本題的關(guān)系圖如圖3-11所示： 圖3-11 例3.5.8的關(guān)系圖例3.5.9 設(shè)，畫(huà)出的關(guān)系圖。 解 因?yàn)槭巧系年P(guān)系，故只需畫(huà)出中的每個(gè)元素即可。如果，就畫(huà)一條由到的有向弧。若，則畫(huà)出的是一條自回路。本題的關(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)位置和線段的長(zhǎng)短

15、無(wú)關(guān)。從到的關(guān)系是的子集，即，而，所以，。令，則。因此，我們今后通常限于討論同一集合上的關(guān)系。3.6 關(guān)系的性質(zhì)及其判定方法3.6.1 關(guān)系的性質(zhì)定義3.6.1設(shè)是定義在集合上的二元關(guān)系，如果（1）對(duì)于每一個(gè)，都有，則稱(chēng)是自反的(Reflexive)。即在上自反（2）對(duì)于每一個(gè)，都有，則稱(chēng)是反自反的(Antireflexive)。即在上反自反（3）對(duì)于任意，若，就有，則稱(chēng)是對(duì)稱(chēng)的(Symmetric)。即在上對(duì)稱(chēng)（4）對(duì)于任意，若，必有，則稱(chēng)在上是反對(duì)稱(chēng)的(Antisymmetric)。即在上反對(duì)稱(chēng)（5）對(duì)于任意，若，就有，則稱(chēng)在上是傳遞的(Transitive)。即在上傳遞例3.6.1 設(shè)，

16、則集合上的關(guān)系是自反而不是反自反的關(guān)系；是反自反而不是自反的關(guān)系；是既不是自反也不是反自反的關(guān)系；是對(duì)稱(chēng)的而不是反對(duì)稱(chēng)的關(guān)系；是反對(duì)稱(chēng)的而不是對(duì)稱(chēng)的關(guān)系；是既對(duì)稱(chēng)也反對(duì)稱(chēng)的關(guān)系；是既不對(duì)稱(chēng)也不反對(duì)稱(chēng)關(guān)系。，是可傳遞的關(guān)系；是不可傳遞的關(guān)系，因?yàn)椋?。由定義3.6.1及例3.6.1可知：（1）對(duì)任意一個(gè)關(guān)系，若自反則它一定不反自反，若反自反則它也一定不自反；但不自反，它未必反自反，若不反自反，也未必自反。（2）存在著既對(duì)稱(chēng)也反對(duì)稱(chēng)的關(guān)系。圖3-5表明了自反與反自反、對(duì)稱(chēng)與反對(duì)稱(chēng)性之間的關(guān)系。圖3-5例3.6.2 (1) 集合之間的關(guān)系是自反的、反對(duì)稱(chēng)的和可傳遞的。因?yàn)椋?） 對(duì)于任意集合，均有成

17、立，所以是自反的；2） 對(duì)于任意集合，若且，則，所以是反對(duì)稱(chēng)的；3） 對(duì)于任意集合，若且，則，所以是可傳遞的。（2）平面上三角形集合中的相似關(guān)系是自反的、對(duì)稱(chēng)的和可傳遞的。因?yàn)椋喝我庖粋€(gè)三角形都與自身相似；若三角形相似于三角形，則三角形必相似于三角形；若三角形相似于三角形，且三角形相似于三角形，則三角形必相似于三角形。（3）人類(lèi)的祖先關(guān)系是反自反、反對(duì)稱(chēng)和可傳遞的。（4）實(shí)數(shù)集上的“>”關(guān)系是反自反、反對(duì)稱(chēng)和可傳遞的。（5）實(shí)數(shù)集上的“”關(guān)系是自反、反對(duì)稱(chēng)和可傳遞的。（6）實(shí)數(shù)集上的“=”關(guān)系是自反、對(duì)稱(chēng)、反對(duì)稱(chēng)和可傳遞的。（7）人群中的父子關(guān)系是反自反和反對(duì)稱(chēng)的。（8）正整數(shù)集上的整除

18、關(guān)系是自反、反對(duì)稱(chēng)和可傳遞的。（9）是反自反、對(duì)稱(chēng)、反對(duì)稱(chēng)和可傳遞的。（10）任意非空集合上的全關(guān)系是自反的、對(duì)稱(chēng)的和可傳遞的。例3.6.3 設(shè)整數(shù)集上的二元關(guān)系定義如下：是整數(shù)，驗(yàn)證在上是自反和對(duì)稱(chēng)的。證明 ，即，故是自反的。又設(shè)，如果，即是整數(shù)，則也必是整數(shù)，即，因此是對(duì)稱(chēng)的。3.6.2 由關(guān)系圖、關(guān)系矩陣判別關(guān)系的性質(zhì)例3.6.4 集合，上的關(guān)系的關(guān)系矩陣為：，的關(guān)系圖如圖3-6所示。討論的性質(zhì)。圖3-6解 從的關(guān)系矩陣和關(guān)系圖容易看出，是自反的、對(duì)稱(chēng)的。一般地，我們有：（1）若關(guān)系是自反的，當(dāng)且僅當(dāng)其關(guān)系矩陣的主對(duì)角線上的所有元素都是1；其關(guān)系圖上每個(gè)結(jié)點(diǎn)都有自環(huán)。（2）若關(guān)系是對(duì)稱(chēng)的

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

20、關(guān)系，而且是既不自反也不反自反的關(guān)系；(2) 是自反、傳遞、反對(duì)稱(chēng)的關(guān)系，但不是對(duì)稱(chēng)也不是反自反的關(guān)系；(3) 是反自反但不是對(duì)稱(chēng)、不是反對(duì)稱(chēng)、不是自反也不是傳遞的關(guān)系；(4) 是不自反、不反自反但是傳遞的關(guān)系，而且既是對(duì)稱(chēng)也是反對(duì)稱(chēng)的關(guān)系； (5) 是自反、反對(duì)稱(chēng)但不是傳遞、不是對(duì)稱(chēng)也不是反自反的關(guān)系。 3.7 復(fù)合關(guān)系和逆關(guān)系3.7.1 復(fù)合關(guān)系 1. 復(fù)合關(guān)系的定義定義3.7.1 設(shè)是從到的關(guān)系，是從到的關(guān)系，則稱(chēng)為和的復(fù)合關(guān)系(Compositive Relation)，表示為從和求，稱(chēng)為關(guān)系的復(fù)合運(yùn)算。復(fù)合運(yùn)算是關(guān)系的二元運(yùn)算，它能夠由兩個(gè)關(guān)系生成一個(gè)新的關(guān)系，以此類(lèi)推。例如，是從到

21、的關(guān)系，是從到的關(guān)系，是從到的關(guān)系，則是從到的關(guān)系。例3.7.1設(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ì)定理3.7.1 設(shè)是由集合到的關(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)算滿(mǎn)足結(jié)合律。（2）設(shè)和都是從到的關(guān)系，是從到的關(guān)

22、系，則1）2）（3）設(shè)是從到的關(guān)系，和都是從到的關(guān)系，則1） 2）證 我們只證明（2），其它證明類(lèi)似。 1） 所以 2） 所以 。注意：一般來(lái)說(shuō)，（1）；（2）關(guān)系的復(fù)合運(yùn)算不滿(mǎn)足交換律。 例3.7.4 （1）設(shè)，和都是從到的關(guān)系，是從到的關(guān)系，則，可見(jiàn)，但。（2）設(shè)，和都是集合上的關(guān)系，則，而，所以。由于關(guān)系的復(fù)合運(yùn)算滿(mǎn)足結(jié)合律，所以可以寫(xiě)成。一般地，若是一由到的關(guān)系，是由到的關(guān)系，是一由到的關(guān)系，則不加括號(hào)的表達(dá)式唯一地表示一由到的關(guān)系，在計(jì)算這一關(guān)系時(shí)，可以運(yùn)用結(jié)合律將其中任意兩個(gè)相鄰的關(guān)系先結(jié)合。特別地，當(dāng) ，即是集合上的關(guān)系時(shí)，復(fù)合關(guān)系 簡(jiǎn)記作，它也是集上的一個(gè)關(guān)系。3.7.2 復(fù)合

23、關(guān)系的矩陣表示及圖形表示 因?yàn)殛P(guān)系可用矩陣表示，所以復(fù)合關(guān)系也可用矩陣表示。已知從集合到集合上的關(guān)系為，關(guān)系矩陣，從集合到集合的關(guān)系，關(guān)系矩陣，表示復(fù)合關(guān)系的矩陣可構(gòu)造如下：若，使得且，則。在集合中能夠滿(mǎn)足這樣條件的元素可能不止一個(gè)，例如另有也滿(mǎn)足且。在所有這樣的情況下，都是成立的。這樣，當(dāng)我們掃描的第行和的第列時(shí)，若發(fā)現(xiàn)至少有一個(gè)這樣的，使得第行的第個(gè)位置上的記入值和第列的第個(gè)位置上的記入值都是1時(shí)，則的第行和第列上的記入值為1；否則為0。因此可以用類(lèi)似于矩陣乘法的方法得到：其中 式中代表邏輯加，滿(mǎn)足，；代表邏輯乘，滿(mǎn)足，。例3.7.5 給定集合，在集合上定義兩種關(guān)系：，求和的矩陣。解因?yàn)殛P(guān)

24、系可用圖形表示，所以復(fù)合關(guān)系也可用圖形表示。例3.7.6 例3.7.1中的兩個(gè)關(guān)系與的復(fù)合很容易通過(guò)下面的關(guān)系圖（見(jiàn)圖3-8）得到。圖3-8 示意圖由該圖立即可得。3.7.3 逆關(guān)系關(guān)系是序偶的集合，由于序偶的有序性，關(guān)系還有一些特殊的運(yùn)算。定義3.7.2 設(shè)是從到的二元關(guān)系，若將中每一序偶的元素順序互換，得到的集合稱(chēng)為的逆關(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)?/p>

25、，故有 其它自證。定理3.7.5 設(shè)為從到的關(guān)系，是從到的關(guān)系，則（1）（2）證明 （1） 所以 （2）自證。定理3.7.6 設(shè)是上的二元關(guān)系，則（1）是對(duì)稱(chēng)的，當(dāng)且僅當(dāng)；（2）是反對(duì)稱(chēng)的，當(dāng)且僅當(dāng)；（3）是傳遞的，當(dāng)且僅當(dāng)；（4）是自反的，當(dāng)且僅當(dāng)；（5）是反自反的，當(dāng)且僅當(dāng)證明 （1）若是對(duì)稱(chēng)的，則對(duì)， 所以，；若 ，則對(duì)，所以，是對(duì)稱(chēng)的。（3）若，則對(duì)，所以，是傳遞的；若是傳遞的， 所以，。其它證明留為作業(yè)。關(guān)系的圖形，是關(guān)系圖形中將其弧的箭頭方向反置。的關(guān)系矩陣是的轉(zhuǎn)置矩陣。例3.7.7 設(shè)是到的二元關(guān)系，是到的二元關(guān)系，且，求和。解 或從 ， 得 故取到同樣的序元素；而 故取到同樣的

26、序元素。例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)在再來(lái)考慮一種新的關(guān)系運(yùn)算關(guān)系的閉包運(yùn)算，它是由已知關(guān)系，通過(guò)增加最少的序偶生成滿(mǎn)足某種指定性質(zhì)的關(guān)系的運(yùn)算。 例如, 設(shè)，上的二元關(guān)系，則上含且最小的自反關(guān)系是：；上含且最小的對(duì)稱(chēng)關(guān)系是： ；上含且最小的傳遞關(guān)系是： 。定義3.8.1 設(shè)是上的二元關(guān)系，如果有另一個(gè)上的關(guān)系滿(mǎn)足：（1）是自反的（對(duì)稱(chēng)的，傳遞的）；（2）；（3）對(duì)于任何上的自反的（對(duì)稱(chēng)的，傳遞的）關(guān)系，若，就有。則稱(chēng)關(guān)系為的自反（對(duì)稱(chēng)，傳遞） 閉包(Reflexive

27、 (Symmetric，Transitive) Closure)，記作。顯然，自反（對(duì)稱(chēng)，傳遞）閉包是包含的最小自反（對(duì)稱(chēng)，傳遞）關(guān)系。定理3.8.1 設(shè)是上的二元關(guān)系，那么（1）是自反的，當(dāng)且僅當(dāng)（2）是對(duì)稱(chēng)的，當(dāng)且僅當(dāng)（3）是傳遞的，當(dāng)且僅當(dāng)證明 （1）若是自反的，對(duì)任何包含的自反關(guān)系，有，故；若，根據(jù)閉包定義，必是自反的。（2）、（3）的證明完全類(lèi)似。 下面討論由給定關(guān)系，求取的方法。定理3.8.2 設(shè)是集合上的二元關(guān)系，則（1）；（2）（3），通常也記作。證明 （1）令，因?yàn)椋?，于是在上是自反的。又即。若有自反關(guān)系且，顯然有，于是 ，所以 。 （2）令，因?yàn)?所以是對(duì)稱(chēng)的。若是對(duì)稱(chēng)的

28、且，則。當(dāng)時(shí)，；當(dāng)時(shí)，。因此 ，故 。（3）令，先證是傳遞的。 ，則存在自然數(shù)，有 ，因此 ，所以，是傳遞的。顯然，。若有傳遞關(guān)系且，則存在自然數(shù)，有 ，則 ，使得 ，因此，由于是傳遞關(guān)系，則，所以。故。例3.8.1 設(shè)，是上的二元關(guān)系，求。解 為了求得，先寫(xiě)出即繼續(xù)這個(gè)運(yùn)算有： 從以上例題中看到，若有限，譬如含有個(gè)元素，那么求取上二元關(guān)系的傳遞閉包不必計(jì)算到對(duì)的無(wú)限大次復(fù)合，而最多不超過(guò)次復(fù)合。定理3.8.3 設(shè)是含有個(gè)元素的集合，是上的二元關(guān)系，則存在一個(gè)正整數(shù)，使得證明 設(shè)，記。若，則存在整數(shù)，使得成立，既存在序列，有。設(shè)滿(mǎn)足上述條件的最小大于，不妨，則序列中必有，使得或。不妨，此時(shí)序列

29、就成為，這表明存在，其中，這與是最小的假設(shè)矛盾，所以，不成立，即。所以 （）一般地，取，式中的給出了復(fù)合次數(shù)的上限。 例3.8.2 設(shè)，給定上的關(guān)系，求。解 所以 即 為計(jì)算元素較多的有限集合上二元關(guān)系的傳遞閉包， Warshall在1962年提出了一個(gè)有效的算法（假定集合含有個(gè)元素）：（） 置新矩陣：；（） 置：；（） 對(duì)，若（），則置：，；（） ：；（） 如果，則轉(zhuǎn)到步驟（3），否則停止。例3.8.3 已知，求。 解 按照Warshall算法，從出發(fā)，只要遵循“置行查列遍尋真，見(jiàn)真行上析當(dāng)今，行推列移下右再，行窮列盡閉包成”便可直接求得。 對(duì)集合上關(guān)系，首先將其關(guān)系矩陣賦予：而后的每后一次

30、循環(huán)重復(fù)操作， 均在前一次操作結(jié)果的矩陣上進(jìn)行。置當(dāng)今行為第1行，查看第1列中1，對(duì)有1的行進(jìn)行改寫(xiě)，改寫(xiě)方法是：將當(dāng)今行的元素與列中有1的行的元素分別做析取。對(duì)本例，時(shí)，第1列中只有，將第一行與第一行各對(duì)應(yīng)元素進(jìn)行邏輯加，仍記于第一行：；置當(dāng)今行為第2行， 查看第2列中1， 對(duì)有1的行進(jìn)行改寫(xiě)。對(duì)本例，時(shí)，第二列中，將第二行與第一行各對(duì)應(yīng)元素進(jìn)行邏輯加，仍記于第一行：；置當(dāng)今行為第3行，重復(fù)上述操作并結(jié)束。對(duì)本例，時(shí)，第三列中，將第三行分別與第一行、第二行、第三行各對(duì)應(yīng)元素進(jìn)行邏輯加，仍分別記于第一行、第二行、第三行：得 。結(jié)果與例3.8.2一致。傳遞閉包在語(yǔ)法分析中有很多應(yīng)用，先以下列說(shuō)明

31、/例3.8.4 設(shè)有一字母表并給定下面六條規(guī)則：為定義在上的二元關(guān)系且，即是從出發(fā)用一條規(guī)則推出一串字符，使其第一個(gè)字符恰為。說(shuō)明每個(gè)字母連續(xù)應(yīng)用上述規(guī)則可能推出的頭字符。解 則表示從出發(fā)，經(jīng)過(guò)多次連續(xù)推導(dǎo)而得的字符串，其第一個(gè)字符恰為的關(guān)系，此關(guān)系即是。按照Warshall算法計(jì)算的過(guò)程中，時(shí)，由于第五行的元素都等于零，的賦值不變。時(shí)，由于第3、6、7列各元素均為零，的賦值不變。經(jīng)計(jì)算得 因此。 這說(shuō)明應(yīng)用給定的六條規(guī)則，從出發(fā)推導(dǎo)的頭字符有三種可能，而從出發(fā)推導(dǎo)的頭字符有兩種可能，而從推出的頭字符有兩種可能，從出發(fā)推導(dǎo)的頭字符只可能為。從一種性質(zhì)的閉包關(guān)系出發(fā)，求取另一種性質(zhì)的閉包關(guān)系，具

32、有以下運(yùn)算律： 定理3.8.4 設(shè)是集合上的二元關(guān)系，則（1）（2）（3）證明 （1） 這里，。（2）這里，（）。（3）留作練習(xí)請(qǐng)讀者自證。3.9 等價(jià)關(guān)系與相容關(guān)系 本節(jié)討論兩類(lèi)特殊關(guān)系等價(jià)關(guān)系與相容關(guān)系。在討論之前，我們先引進(jìn)兩個(gè)概念集合的劃分與覆蓋。3.9.1 集合的劃分和覆蓋 設(shè)是某一所綜合性大學(xué)本科學(xué)生全體組成的集合，是對(duì)的某種分類(lèi)的集合（）。若按文理科分類(lèi)，則有，其中表示理科學(xué)生全體的集合、表示文科學(xué)生全體的集合；若按年級(jí)分類(lèi)，則有，其中表示該大學(xué)年級(jí)學(xué)生全體的集合；若按系分類(lèi)，則有，這說(shuō)明這所大學(xué)有六個(gè)系。分類(lèi)法盡管給出了三種，但是它們有個(gè)共同的特點(diǎn)：(1) 的元素都是的非空子集

33、；(2) 的元素求交是空集、求并就是。 此時(shí)，我們就說(shuō)是集合的一個(gè)劃分。 定義3.9.1 設(shè)是非空集合，的子集的集合，如果滿(mǎn)足： （1）都是非空集合； （2）則稱(chēng)集合是集合的覆蓋(Cover)，稱(chēng)是覆蓋的分塊。如果除以上條件外，另有（），則稱(chēng)是的劃分（或分劃）(Partition)。顯然，若是劃分則必是覆蓋，其逆不真。若，則有兩個(gè)簡(jiǎn)單的劃分：一是，稱(chēng)為的最大劃分(分塊最多)；二是，稱(chēng)為的最小劃分(分塊最少)。 例如，考慮下列子集：，則是的覆蓋；是的劃分，其中是最小劃分，是最大劃分；既不是劃分也不是覆蓋。 定義3.9.2 若與是同一集合的兩種劃分，則其中所有組成的集合，稱(chēng)為和的交叉劃分，即 注意

34、：和的交叉劃分一般不是，而是以與元素之間的所有非空交集作元素的集合。 例如，所有生物的集合，可分割成，其中表示所有植物的集合，表示所有動(dòng)物的集合；又也可分割成，其中表示史前生物，表示史后生物。則其交叉劃分為，其中表示史前植物，表示史后植物，表示史前動(dòng)物，表示史后動(dòng)物。 定理3.9.1 設(shè)與是同一集合的兩種劃分，則其交叉劃分也是原集合的一種劃分。 證明 和的交叉劃分是： 在交叉劃分中，任取兩元素和，（），因?yàn)?，所以 ；其次，交叉劃分中所有元素的并為 所以，和的交叉劃分也是的一種劃分。定義3.9.3 給定的任意兩個(gè)劃分與，若對(duì)于每一個(gè)均有，使（），則稱(chēng)為的加細(xì)。若還有，則稱(chēng)為的真加細(xì)。定理3.9

35、.2 任何兩種劃分的交叉劃分，都是原來(lái)各劃分的一種加細(xì)。證明 設(shè)與的交叉劃分為，對(duì)中任意元素必有和，則分別是和的加細(xì)。3.9.2 等價(jià)關(guān)系與等價(jià)類(lèi)1. 等價(jià)關(guān)系 定義3.9.4 設(shè)為定義在集合上的一個(gè)關(guān)系，若是自反的、對(duì)稱(chēng)的和傳遞的，則稱(chēng)為等價(jià)關(guān)系(Equivalence Relation)。例 3 . 9. 1 （1） 平面上三角形集合中，三角形的相似關(guān)系是等價(jià)關(guān)系。（） 數(shù)的相等關(guān)系是任何數(shù)集上的等價(jià)關(guān)系。（3）一群人的集合中姓氏相同的關(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)系圖如圖

36、3-9所示。圖3-9關(guān)系矩陣中，對(duì)角線上的所有元素都是1，關(guān)系圖上每個(gè)結(jié)點(diǎn)都有自環(huán)，說(shuō)明是自反的。關(guān)系矩陣是對(duì)稱(chēng)的，關(guān)系圖上任意兩結(jié)點(diǎn)間或沒(méi)有弧線連接，或有成對(duì)弧出現(xiàn)，故是對(duì)稱(chēng)的。從的序偶表示式中，可以看出是傳遞的。故是上的等價(jià)關(guān)系。例3.9.3 設(shè)為整數(shù)集，其中當(dāng)且僅當(dāng)，使得，證明是等價(jià)關(guān)系。證明 設(shè)任意（1），所以，是自反的；（2）若，(為整數(shù))，則 ，所以，是對(duì)稱(chēng)的；（3）若，則， (為整數(shù))，所以，是傳遞的。因此，是等價(jià)關(guān)系。我們稱(chēng)之為整數(shù)集上的模同余關(guān)系(Congruence Modulo )。2等價(jià)類(lèi)定義3.9.5 設(shè)是集合上的等價(jià)關(guān)系，對(duì)任何，若，則稱(chēng)與等價(jià)。對(duì)任何，集合中等價(jià)于

37、的所有元素組成的集合稱(chēng)為以為代表元的（關(guān)于等價(jià)關(guān)系的）等價(jià)類(lèi)(Equivalence Class)，記作。即由等價(jià)類(lèi)的定義可知是非空的，因?yàn)?，。因此，任給集合及其上的等價(jià)關(guān)系，必可寫(xiě)出上各個(gè)元素的等價(jià)類(lèi)。例如，在例3.9.2中，的各個(gè)元素的等價(jià)類(lèi)為：；可見(jiàn)，上的等價(jià)關(guān)系的不同的等價(jià)類(lèi)有兩個(gè)。例3.9.4 設(shè)是整數(shù)集合，是模同余關(guān)系，即，確定由的元素所產(chǎn)生的等價(jià)類(lèi)。解 例3.9.3已證明整數(shù)集合上的模同余的關(guān)系是等價(jià)關(guān)系，故本例中由的元素所產(chǎn)生的等價(jià)類(lèi)是從本例可以看到，在集合上模3同余等價(jià)關(guān)系所構(gòu)成的等價(jià)類(lèi)有：定理3.9.3 設(shè)給定集合上的等價(jià)關(guān)系，對(duì)于有當(dāng)且僅當(dāng)。證明 若 ，因?yàn)?，故，即 ，

38、則。若 ，則，即 ；，即 。所以，。定義3.9.6 集合上的等價(jià)關(guān)系，其所有等價(jià)類(lèi)的集合稱(chēng)作關(guān)于的商集(Quotient Set )，記作，即例如，例3.9.2中，商集： 例3.9.4中商集： 。我們注意到商集中，且任意兩個(gè)等價(jià)類(lèi)的交為，于是我們有下述重要定理。定理3.9.4 集合上的等價(jià)關(guān)系，決定了的一個(gè)劃分，該劃分就是商集。為證定理，我們需要證明非空集合在其上的等價(jià)關(guān)系下形成的等價(jià)類(lèi)的全體的集合商集滿(mǎn)足：(1) 每一等價(jià)類(lèi)都是的子集， 中任一元素均屬于某一等價(jià)類(lèi)， 即等價(jià)類(lèi)全體的并集是；(2) 不同的等價(jià)類(lèi)之間交是空集。 證明 ，因?yàn)?，所以，從而；因?yàn)樽苑矗?，所以，則 ；故 。(1)

39、得證。為證明（2），用反證法：設(shè)，且 則 ，使成立，由對(duì)稱(chēng)性得 ，再由傳遞性得 ，據(jù)定理3.9.3，必有 ，這與題設(shè)矛盾，（2）得證。所以，是的對(duì)應(yīng)于的一個(gè)劃分。定理3.9.5設(shè)是集合的一個(gè)劃分，則存在上的一個(gè)等價(jià)關(guān)系，使得是關(guān)于的商集。證明 在集合上定義關(guān)系，對(duì)任意，當(dāng)且僅當(dāng)在同一分塊中?？梢宰C明這樣定義的關(guān)系是一個(gè)等價(jià)關(guān)系。因?yàn)椋海?）與在同一分塊中，故必有，即是自反的。（2）若與在同一分塊中，與也必在同一分塊中，即 ，故是對(duì)稱(chēng)的。（3）若與在同一分塊中，與在同一分塊中，因?yàn)?，即屬于且僅屬于一個(gè)分塊，故與必在同一分塊中，即 ，故是傳遞的。所以，是等價(jià)關(guān)系。由的定義可知： 。由定理3.9.

40、5可知：由集合的劃分所確定的上的等價(jià)關(guān)系為：定理3.9.4和定理3.9.5說(shuō)明：非空集合上的等價(jià)關(guān)系與的劃分一一對(duì)應(yīng)。例3.9.5 設(shè)的劃分，試由劃分確定上的一個(gè)等價(jià)關(guān)系。解 顯然，。定理3.9.6 設(shè)和為非空集合上的等價(jià)關(guān)系，則。證明 ，。若 ，故 ，即；若，即，則對(duì)，必有，使得，故 所以， ；類(lèi)似地有 ，因此，。3.9.3 相容關(guān)系定義3.9.4 給定集合上的關(guān)系，若是自反的、對(duì)稱(chēng)的，則稱(chēng)是上的相容關(guān)系Cconsistent Relation)。相容關(guān)系只要求滿(mǎn)足自反性與對(duì)稱(chēng)性，因此，等價(jià)關(guān)系必定是相容關(guān)系但反之不真。 例3.9.6 設(shè)是由下列英文單詞組成的集合，定義關(guān)系：，且和有相同的字

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

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

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

44、的最大相容類(lèi)。從定理3.9.7中可以看到，的任一元素，它可以組成相容類(lèi)，因此必包含在一個(gè)最大相容類(lèi)中，因此，如由所有最大相容類(lèi)作出一個(gè)集合，則中每一個(gè)元素至少屬于該集合的一個(gè)成員之中，所以最大相容類(lèi)集合必覆蓋集合。定義3.9.6 在集合上給定相容關(guān)系，其最大相容類(lèi)的集合稱(chēng)作集合的完全覆蓋(Complete Cover)，記作。例3.9.8 設(shè)集合，上二元關(guān)系求的完全覆蓋。 解 是上的相容關(guān)系(自反，對(duì)稱(chēng))。 的簡(jiǎn)化關(guān)系圖如圖3-12所示：圖3-12的最大相容類(lèi)是確定的，即。因此，集合是的完全覆蓋。定理3.9.8 給定集合的覆蓋，由它確定的關(guān)系是上的相容關(guān)系。證明 因?yàn)?，對(duì)于任意，必存在某個(gè)，

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

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

47、蓋的方法，此方法所定義的覆蓋是否唯一？（2）給定集合的覆蓋，能否確定此覆蓋對(duì)應(yīng)的相容關(guān)系？（3）若和是上的相容關(guān)系，問(wèn)，是不是相容關(guān)系？3.10 偏序關(guān)系3.10.1偏序關(guān)系的定義在一個(gè)集合上，我們常常要考慮元素的次序關(guān)系，其中很重要的一類(lèi)關(guān)系稱(chēng)作偏序關(guān)系。定義3.10.1 設(shè)是一個(gè)集合，如果上的一個(gè)關(guān)系，滿(mǎn)足自反性、反對(duì)稱(chēng)性和傳遞性，則稱(chēng)是上的一個(gè)偏序關(guān)系(Partially Ordered Relation)，并把它記為“”。序偶稱(chēng)作偏序集(Partially Ordered Set Or Poset)。例3.10.1 在實(shí)數(shù)集上，小于等于關(guān)系“”是偏序關(guān)系。因?yàn)椋海?）對(duì)于任何實(shí)數(shù)，有成

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

49、冪集上的真包含關(guān)系“”不是偏序關(guān)系。3.10.2 偏序關(guān)系的哈斯圖為了更清楚地描述偏序集合中元素間的層次關(guān)系，我們先介紹“蓋住”的概念。定義3.10.2 在偏序集合中，如果，且沒(méi)有其它元素滿(mǎn)足，則稱(chēng)元素蓋住元素。并且記COV蓋住。稱(chēng)為偏序集中的蓋住關(guān)系。顯然。例3.10.5 設(shè)，并設(shè)“”為整除關(guān)系，求COV。解 “”COV對(duì)于給定偏序集，它的蓋住關(guān)系是唯一的，所以哈斯(Hasse)根據(jù)蓋住的概念給出了偏序關(guān)系圖的一種畫(huà)法，這種畫(huà)法畫(huà)出的圖稱(chēng)為哈斯圖(Hasse Diagram)，其作圖規(guī)則如下： （1） 用小圓圈代表元素。（2） 如果且，則將代表的小圓圈畫(huà)在代表的小圓圈之上。（3） 如果COV，則在與之間用直線連接。根據(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-153.10.3 偏序集中特殊位置的元素從偏序集的哈斯圖可以看到偏序集中各個(gè)元素之間具有分明的層次關(guān)系，則其中必有一些處于特殊位置的元