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

2、2序偶與笛卡爾積3關(guān)系及其表示4關(guān)系的性質(zhì)及其判定方法5復(fù)合關(guān)系和逆關(guān)系6關(guān)系的閉包運算7等價關(guān)系與相容關(guān)系8偏序關(guān)系 重點： 1關(guān)系的性質(zhì)及其判別；2關(guān)系的復(fù)合運算及其性質(zhì)；3等價關(guān)系與等價類、等價關(guān)系與集合的劃分的聯(lián)系；4偏序關(guān)系判別及其哈斯圖的畫法、偏序集中特異位置元素的理解。 難點：1關(guān)系的傳遞性及其判別；2等價關(guān)系的特性；3偏序關(guān)系的哈斯圖的畫法；偏序集中特異位置元素的求法。 教學(xué)手段： 通過多個實例的精講幫助同學(xué)理解重點和難點的內(nèi)容，并通過大量的練習(xí)使同學(xué)們鞏固和掌握關(guān)系的性質(zhì)及其判別、關(guān)系的復(fù)合運算及其性質(zhì)、等價關(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é)中的一個最基本的概念。所謂集合，就是指具有共同性質(zhì)的或適合一定條件的事物的全體，組成集合的這些“事物”稱為集合的元素。集合常用大寫字母表示，集合的元素常用小寫字母表示。若是集合，是的元素，則稱屬于，記作；若不是的元素，則稱不屬于，記作。若組成集合的元素個數(shù)是有限的，則稱該集合

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

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

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

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

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

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

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

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

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

13、的列舉法或描述法來表示關(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)系除了可以用序偶集合的形式表達以外，還可用矩陣和圖形表示，以便引入線性代數(shù)和圖論的知識來討論。2矩陣表示法 設(shè)給定兩個有限集合，則對應(yīng)于從到的二元關(guān)系有一個關(guān)系矩陣，其中 。 如果是有限集合上的二元關(guān)系或和含有相同數(shù)量的有限個元素，則是方陣。例3.5.6 若，寫出關(guān)系矩陣。解 例3.5.7 設(shè)，寫出集合上的大于關(guān)系>的關(guān)系矩陣。 解 > 3關(guān)系圖表示法有限集合的二元關(guān)系也可用

14、圖形來表示。設(shè)集合到上的一個二元關(guān)系為，首先我們在平面上做出個結(jié)點分別記作，另外做個結(jié)點分別記作。如果，則從結(jié)點至結(jié)點做一有向弧，其箭頭指向，如果，則之間沒有線段連接。用這種方法連接起來的圖稱為的關(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)系圖。 解 因為是上的關(guān)系，故只需畫出中的每個元素即可。如果，就畫一條由到的有向弧。若，則畫出的是一條自回路。本題的關(guān)系圖如圖3-12所示。 3 2 1 45 圖3-12 例3.5.9的關(guān)系圖關(guān)系圖主要表達結(jié)點與結(jié)點之間的鄰接關(guān)系，故關(guān)系圖與結(jié)點位置和線段的長短

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

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

17、立，所以是自反的；2） 對于任意集合，若且，則，所以是反對稱的；3） 對于任意集合，若且，則，所以是可傳遞的。（2）平面上三角形集合中的相似關(guān)系是自反的、對稱的和可傳遞的。因為：任意一個三角形都與自身相似；若三角形相似于三角形，則三角形必相似于三角形；若三角形相似于三角形，且三角形相似于三角形，則三角形必相似于三角形。（3）人類的祖先關(guān)系是反自反、反對稱和可傳遞的。（4）實數(shù)集上的“>”關(guān)系是反自反、反對稱和可傳遞的。（5）實數(shù)集上的“”關(guān)系是自反、反對稱和可傳遞的。（6）實數(shù)集上的“=”關(guān)系是自反、對稱、反對稱和可傳遞的。（7）人群中的父子關(guān)系是反自反和反對稱的。（8）正整數(shù)集上的整除

18、關(guān)系是自反、反對稱和可傳遞的。（9）是反自反、對稱、反對稱和可傳遞的。（10）任意非空集合上的全關(guān)系是自反的、對稱的和可傳遞的。例3.6.3 設(shè)整數(shù)集上的二元關(guān)系定義如下：是整數(shù)，驗證在上是自反和對稱的。證明 ，即，故是自反的。又設(shè)，如果，即是整數(shù)，則也必是整數(shù)，即，因此是對稱的。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)系圖容易看出，是自反的、對稱的。一般地，我們有：（1）若關(guān)系是自反的，當且僅當其關(guān)系矩陣的主對角線上的所有元素都是1；其關(guān)系圖上每個結(jié)點都有自環(huán)。（2）若關(guān)系是對稱的

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

20、關(guān)系，而且是既不自反也不反自反的關(guān)系；(2) 是自反、傳遞、反對稱的關(guān)系，但不是對稱也不是反自反的關(guān)系；(3) 是反自反但不是對稱、不是反對稱、不是自反也不是傳遞的關(guān)系；(4) 是不自反、不反自反但是傳遞的關(guān)系，而且既是對稱也是反對稱的關(guān)系； (5) 是自反、反對稱但不是傳遞、不是對稱也不是反自反的關(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)系，則稱為和的復(fù)合關(guān)系(Compositive Relation)，表示為從和求，稱為關(guān)系的復(fù)合運算。復(fù)合運算是關(guān)系的二元運算，它能夠由兩個關(guān)系生成一個新的關(guān)系，以此類推。例如，是從到

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ù)合運算的性質(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ù)合運算滿足結(jié)合律。（2）設(shè)和都是從到的關(guān)系，是從到的關(guān)

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

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

24、系可用圖形表示，所以復(fù)合關(guān)系也可用圖形表示。例3.7.6 例3.7.1中的兩個關(guān)系與的復(fù)合很容易通過下面的關(guān)系圖（見圖3-8）得到。圖3-8 示意圖由該圖立即可得。3.7.3 逆關(guān)系關(guān)系是序偶的集合，由于序偶的有序性，關(guān)系還有一些特殊的運算。定義3.7.2 設(shè)是從到的二元關(guān)系，若將中每一序偶的元素順序互換，得到的集合稱為的逆關(guān)系(Inverse Relation)，記為。即例如，在實數(shù)集上，關(guān)系“<”的逆關(guān)系是“>”。從逆關(guān)系的定義，我們?nèi)菀卓闯?。定理3.7.4 設(shè)、和都是從到的二元關(guān)系，則下列各式成立。（1）（2）(3) (4) 這里 -(5) 證明 （1） （4） （5）因為

25、，故有 其它自證。定理3.7.5 設(shè)為從到的關(guān)系，是從到的關(guān)系，則（1）（2）證明 （1） 所以 （2）自證。定理3.7.6 設(shè)是上的二元關(guān)系，則（1）是對稱的，當且僅當；（2）是反對稱的，當且僅當；（3）是傳遞的，當且僅當；（4）是自反的，當且僅當；（5）是反自反的，當且僅當證明 （1）若是對稱的，則對， 所以，；若 ，則對，所以，是對稱的。（3）若，則對，所以，是傳遞的；若是傳遞的， 所以，。其它證明留為作業(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)系的閉包運算關(guān)系作為集合, 在其上已經(jīng)定義了并、交、差、補、復(fù)合及逆運算?，F(xiàn)在再來考慮一種新的關(guān)系運算關(guān)系的閉包運算，它是由已知關(guān)系，通過增加最少的序偶生成滿足某種指定性質(zhì)的關(guān)系的運算。 例如, 設(shè)，上的二元關(guān)系，則上含且最小的自反關(guān)系是：；上含且最小的對稱關(guān)系是： ；上含且最小的傳遞關(guān)系是： 。定義3.8.1 設(shè)是上的二元關(guān)系，如果有另一個上的關(guān)系滿足：（1）是自反的（對稱的，傳遞的）；（2）；（3）對于任何上的自反的（對稱的，傳遞的）關(guān)系，若，就有。則稱關(guān)系為的自反（對稱，傳遞） 閉包(Reflexive

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

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

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

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

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

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

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

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

35、.2 任何兩種劃分的交叉劃分，都是原來各劃分的一種加細。證明 設(shè)與的交叉劃分為，對中任意元素必有和，則分別是和的加細。3.9.2 等價關(guān)系與等價類1. 等價關(guān)系 定義3.9.4 設(shè)為定義在集合上的一個關(guān)系，若是自反的、對稱的和傳遞的，則稱為等價關(guān)系(Equivalence Relation)。例 3 . 9. 1 （1） 平面上三角形集合中，三角形的相似關(guān)系是等價關(guān)系。（） 數(shù)的相等關(guān)系是任何數(shù)集上的等價關(guān)系。（3）一群人的集合中姓氏相同的關(guān)系也是等價關(guān)系。（4）設(shè)是任意非空集合，則上的恒等關(guān)系和全域關(guān)系均是上的等價關(guān)系。例3.9.2 設(shè)集合， 驗證是上的等價關(guān)系。證明 的關(guān)系矩陣：關(guān)系圖如圖

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

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

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

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

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

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

42、關(guān)系可產(chǎn)生相容類等等。對于前三個相容類，都能加進新的元素組成新的相容類，而后兩個相容類，加入任一新元素，就不再組成相容類，稱它們?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)系圖中，每一個最大完全多邊形的頂點集合，就是一個最大相容類。所謂完全多邊形(Complete Polygo

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

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

45、 使得 ，所以， ，即 ， 因此，是自反的。其次，若有任意，且，則必存在某個，使 ，故必有 ，即，所以是對稱的。因此，是上的相容關(guān)系。從上述定理可以看到，給定集合上的任意一個覆蓋，必可在上構(gòu)造對應(yīng)于此覆蓋的一個相容關(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把個元素的集合劃分成兩個分塊，共有多少種不同的方法？3已知及其關(guān)系如下，試說明是等價關(guān)系，并指出其等價類。（1）：自然數(shù)集，

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

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

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

49、冪集上的真包含關(guān)系“”不是偏序關(guān)系。3.10.2 偏序關(guān)系的哈斯圖為了更清楚地描述偏序集合中元素間的層次關(guān)系，我們先介紹“蓋住”的概念。定義3.10.2 在偏序集合中，如果，且沒有其它元素滿足，則稱元素蓋住元素。并且記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，則在與之間用直線連接。根據(jù)這個作圖規(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 偏序集中特殊位置的元素從偏序集的哈斯圖可以看到偏序集中各個元素之間具有分明的層次關(guān)系，則其中必有一些處于特殊位置的元