離散數(shù)學(xué)CH51特殊關(guān)系課件

1、離散數(shù)學(xué)第5章 特殊關(guān)系 Discrete Mathematics章節(jié)引入判定下列關(guān)系具有哪些性質(zhì)？在全體中國(guó)人所組成的集合上定義的“同姓”關(guān)系；對(duì)任何非空集合A，A上的全關(guān)系；三角形的“相似關(guān)系”、“全等關(guān)系”；直線的“平行關(guān)系”；“朋友”關(guān)系。發(fā)現(xiàn)：不同的關(guān)系卻具有多個(gè)相同的性質(zhì)。本章將研究具有不同性質(zhì)組合的幾種特殊關(guān)系相容關(guān)系、等價(jià)關(guān)系、擬序關(guān)系、偏序關(guān)系。自反性，對(duì)稱性和傳遞性 自反性，對(duì)稱性和傳遞性 自反性，對(duì)稱性和傳遞性 自反性，對(duì)稱性自反性，對(duì)稱性學(xué)習(xí)要求歷史人物相容關(guān)系等價(jià)關(guān)系 1內(nèi)容導(dǎo)航CONTENTS次序關(guān)系函數(shù) 5.1 5.4 5.3 5.4特殊關(guān)系的應(yīng)用 5.5作業(yè) 5

2、.61646-1716， 德國(guó)哲學(xué)家、數(shù)學(xué)家，微積分的發(fā)現(xiàn)者之一。 歷史人物1643-1727，英國(guó)數(shù)學(xué)家、科學(xué)家和哲學(xué)家。經(jīng)典力學(xué)理論開創(chuàng)者。學(xué)習(xí)要求歷史人物相容關(guān)系等價(jià)關(guān)系 1內(nèi)容導(dǎo)航CONTENTS次序關(guān)系函數(shù) 5.1 5.4 5.3 5.4特殊關(guān)系的應(yīng)用 5.5作業(yè) 5.6重點(diǎn)1 特殊關(guān)系的判定與證明2 等價(jià)類和商集的計(jì)算3 8個(gè)特殊元的判定4 復(fù)合函數(shù)的計(jì)算難點(diǎn)1 相容關(guān)系與覆蓋的聯(lián)系等價(jià)關(guān)系與集合劃分的聯(lián)系特殊關(guān)系的判定與證明4 8個(gè)特殊元的判定5 函數(shù)類型的證明 學(xué)習(xí)要求學(xué)習(xí)要求相容關(guān)系等價(jià)關(guān)系內(nèi)容導(dǎo)航CONTENTS次序關(guān)系函數(shù) 5.1 5.4 5.3 5.4特殊關(guān)系的應(yīng)用 5

3、.5作業(yè) 5.6歷史人物5.1.1 相容關(guān)系的定義定義5.1 設(shè)R是定義在非空集合A上的關(guān)系，如果R是自反的、對(duì)稱的，則稱R是A上的相容關(guān)系。例5.1設(shè)A是所有中國(guó)人組成的集合，試判斷下列關(guān)系是否為相容關(guān)系。(1) A上的“同性”關(guān)系。(2) A上的“朋友”關(guān)系。(3) A上的“父子”關(guān)系。解題小貼士相容關(guān)系的判斷方法 R是相容關(guān)系 R同時(shí)具有自反性和對(duì)稱性。是是否不具有對(duì)稱性，自反性例5.4 例5.4 假設(shè)A是由下列英文單詞組成的集合。Astudent, boy, work, table, to, girl，A上的關(guān)系R|x，yA且x和y有相同字母。（1）寫出關(guān)系R中的所有元素。（2）寫出R

4、的關(guān)系矩陣。（3）畫出R的關(guān)系圖。（4）試說明R是相容關(guān)系。例5.4 解解 (1) 令1=student, 2=boy, 3=work, 4=table, 5=to，6=girl，由R的定義可得R,。（4）由R的關(guān)系圖或者關(guān)系矩陣可看出，R具有自反性和對(duì)稱性，即R是相容關(guān)系。（2）R的關(guān)系矩陣如圖5.1（a）。（3）R的關(guān)系圖如圖5.1（b）。圖5.1例5.4 解（續(xù)）定義5.4 給定非空集合A，設(shè)有集合SA1,A2,Am。如果(1) Ai A且Ai ， i=1，2，m ； (2) 。則S被稱作集合A的一個(gè)覆蓋。例如：設(shè)A=1,2,3,4,5,6，則 1,2,4,5，2,3,5，6和1,2,4

5、,5，3,5,6都是的A一個(gè)覆蓋。5.1.2 集合的覆蓋顯然一個(gè)集合的覆蓋是不惟一的。定理5.1 定理5.1 給定集合A的一個(gè)覆蓋SA1,A2,An ，設(shè)：RA1A1A2A2AnAn （5.1）則R是A上的相容關(guān)系。 例5.3 例5.3 給定非空集合A=a,b,c和A上的兩個(gè)不同覆蓋S1a,b,c和S2=a,b，b,c，a,c，試給出S1和S2確定的相容關(guān)系。解 設(shè)覆蓋S1和S2確定的相容關(guān)系分別為R1和R2，則R1a,b,c a,b,c , ,；R2（a,ba,b）（b,cb,c）（a,ca,c） , ,。不同的覆蓋可以構(gòu)造出相同的相容關(guān)系。 學(xué)習(xí)要求相容關(guān)系等價(jià)關(guān)系內(nèi)容導(dǎo)航CONTENTS

6、次序關(guān)系函數(shù) 5.1 5.4 5.3 5.4特殊關(guān)系的應(yīng)用 5.5作業(yè) 5.6歷史人物問題引入顯然關(guān)系R具有自反性，對(duì)稱性和傳遞性 。等價(jià)關(guān)系假設(shè)集合A是由10個(gè)紅色、藍(lán)色或綠色球組成的集合，如圖5.4所示。定義A上的關(guān)系R為：如果x和y屬于關(guān)系R，則x和y有相同的顏色。關(guān)系R具有哪些性質(zhì)？圖5.45.4.1 等價(jià)關(guān)系的定義定義5.3 設(shè)R是定義在非空集合A上的關(guān)系，如果R是自反的、對(duì)稱的、傳遞的，則、 稱R為A上的等價(jià)關(guān)系。等價(jià)關(guān)系的判斷方法R是等價(jià)關(guān)系 R同時(shí)具有自反性、對(duì)稱性和傳遞性。注意：R是等價(jià)關(guān)系，則R一定是相容關(guān)系；反之不然。例5.4試判定例5.1中的關(guān)系是否為等價(jià)關(guān)系。(1)

7、A上的“同性”關(guān)系。(2) A上的“朋友”關(guān)系。(3) A上的“父子”關(guān)系。例5.4不具有傳遞性 是否否不具有對(duì)稱性，自反性例5.5 針對(duì)圖5.4中集合A上定義的關(guān)系R。 （1）寫出R中的所有元素。（2）畫出R的關(guān)系圖。（3）證明R是一個(gè)等價(jià)關(guān)系。例5.5解 （1）根據(jù)R的定義得：R,，,，,，,，,，,，,。（2）R的關(guān)系圖如圖5.3所示。例5.5 解 （續(xù)）例5.5 解 (續(xù))顯然，關(guān)系R將集合A分成了三個(gè)互不相交的子集，且它們的并集為A。例5.6例5.6 設(shè)n為正整數(shù)，考慮整數(shù)集合Z上的整除關(guān)系如下：R=|x,yZ(n|(x-y)證明 R是一個(gè)等價(jià)關(guān)系。 例5.6 證明以n為模的同余關(guān)系

8、整數(shù)集Z上的整除關(guān)系R又被稱為Z上以n為模的同余關(guān)系(Congruence Relation)，記xRy為x y(mod n) (5.4)通常稱(5.4）為同余式（Congruence）。如用resn(x)表示x除以n的余數(shù)，則x y(mod n) resn(x)resn(y)。以n為模的同余關(guān)系Z上的整除關(guān)系R將Z分成了下面n個(gè)互不相交的子集，且這些子集的并集為Z。S0 =, 2n,n,0,n,2n,；S1 =,2n1,n1,1,n1,2n1,；Sn-1 =,2n1,n1,1,n1,2n1, 。稱為集合Z的一個(gè)劃分5.4.2 集合的劃分定義5.3 給定非空集合A，設(shè)有集合S=A1,A2,Am

9、。如果滿足(1) AiA且Ai，i1,2,m；(2) AiAj，ij，i,j1,2,m； (3) 。則稱S為集合A的一個(gè)劃分(Partition)，而A1,A2,Am叫做這個(gè)劃分的塊(Block)或類(Class)。注意：集合的一個(gè)劃分一定是該集合的一個(gè)覆蓋，反之不然。例5.7試給出非空集合A上2個(gè)不同的劃分解（1）在A中設(shè)定一個(gè)非空真子集A1，令A(yù)2=A-A1，則根據(jù)集合劃分的定義，A1,A2就構(gòu)成了集合A的一個(gè)劃分，見圖(a)；（2）在A中設(shè)定兩個(gè)不相交非空真子集A1和A2，令A(yù)3=A-(A1A2)，則根據(jù)集合劃分的定義，A1,A2,A3就構(gòu)成了集合A的一個(gè)劃分，見圖(b)。(a)AA1(

10、b)AA1A2注意：對(duì)同一個(gè)集合，劃分的方法不同，得到的劃分也不同。問題引入1,4,8,10,2,7,9,3,5,6是集合A1,2,10的一個(gè)劃分； S0,S1 ,Sn-1是整數(shù)集Z的一個(gè)劃分。由等價(jià)關(guān)系產(chǎn)生的像這種由等價(jià)關(guān)系產(chǎn)生的劃分又被稱為集合A上關(guān)于R的商集，劃分中的每一塊被稱為等價(jià)類。5.4.3 等價(jià)類與商集解題小貼士等價(jià)類xR的計(jì)算方法對(duì)A中的任意x，找出以x為第一元素的所有序偶，將其第二元素構(gòu)成集合，這個(gè)集合就是xR。例5.8例5.8 設(shè)A1,2,3,4,5,6,7,8,9，R是A上以4為模的同余關(guān)系。（1）寫出R中的所有元素。（2）計(jì)算R的所有等價(jià)類。（3）畫出R的關(guān)系圖。解：（

11、1）根據(jù)R的定義得：R, ,。例5.8 解（續(xù)）解：（2）由例5.6知，A上的關(guān)系R是一個(gè)等價(jià)關(guān)系。于是有1R5R9R1,5,9； 2R6R2,6；3R7R3,7； 4R8R4,8。（3）R對(duì)應(yīng)的關(guān)系圖如圖5.5所示。定理5.4定理5.4 證明 b) yxR R 假設(shè)xRyR，則 xRyR zxRyR RR RR （R是對(duì)稱的） R （R是傳遞的） 顯然與 R矛盾。 從而xRyR成立。定理5.4 證明（續(xù)）定理5.4 證明（續(xù)）商 集定義5.5 設(shè)R是非空集合A上的等價(jià)關(guān)系，由R確定的一切等價(jià)類構(gòu)成的集合，稱為集合A上關(guān)于R的商集(Quotient Set)，記為A/R，即 A/RxR|(xA

12、) （5.4）例如，例5.8中A關(guān)于R的商集A/R=1R,2R,3R,4R1,5,9,2,6,3,7,4,8。例5.9例5.9 設(shè)A=1,2,3，在P(A)上規(guī)定二元關(guān)系如下：R=|s,tP(A)|s|=|t|試證明R是A上的等價(jià)關(guān)系，并計(jì)算商集P(A)/R。例5.9計(jì)算商集A/R的通用過程解題小貼士A是有限集或可數(shù)集，商集P(A)/R的計(jì)算步驟如下：（1）任選A中一個(gè)元素a，計(jì)算aR；（2）如果aRA，任選一個(gè)元素bAaR，計(jì)算bR；（3）如果aRbRA，任選一個(gè)元素cAaRbR，計(jì)算cR。以此類推，直到A中所有元素都包含在計(jì)算出的等價(jià)類中。5.4.4 等價(jià)關(guān)系與劃分5.4.4 等價(jià)關(guān)系與劃

13、分定理5.4 給定集合A的一個(gè)劃分=A1,A2,An， 則由該劃分確定的關(guān)系R=(A1A1)(A2A2)(AnAn)是A上的等價(jià)關(guān)系,稱此關(guān)系R為由劃分所導(dǎo)出的等價(jià)關(guān)系。5.4.4 等價(jià)關(guān)系與劃分5.4.4 等價(jià)關(guān)系與劃分注意：集合A上的等價(jià)關(guān)系與集合A的劃分是一一對(duì)應(yīng)的。例5.10例5.10 設(shè)A1,2,3,4,5,6，求出與下列劃分對(duì)應(yīng)的等價(jià)關(guān)系。（1）S11,2,3,5,4；（2）S21,3,2,4,5。解 （1）設(shè)與劃分S1對(duì)應(yīng)的等價(jià)關(guān)系為R1 ，則R1(1,21,2)(3,53,5)(44) , ,。例5.10 解(續(xù))（2）設(shè)與劃分S2對(duì)應(yīng)的等價(jià)關(guān)系為R2，則 R2 (1,31,3

14、)(2,3,52,3,5), ,。例5.11例5.11 設(shè)A=a,b,c，求A上所有的等價(jià)關(guān)系及其對(duì)應(yīng)的商集。解 只有1個(gè)劃分塊的劃分為S1，見圖(a)；具有2個(gè)劃分塊的劃分為S2、S3和S4，見圖(b)、(c)和(d)，具有3個(gè)劃分塊的劃分為S5，見圖(e)。bcabcabcabcabca (a) (b) (c) (d) (e)例5.11(續(xù)）假設(shè)由Si導(dǎo)出的對(duì)應(yīng)等價(jià)關(guān)系為Ri，i=1,2,3,4,5，則有 R1=S1S1=AA， A/R1=1,2,3； R2=1,21,233 =, A/R2=1,2,3； R3=1,31,322 =, A/R3=1,3,2；R4=2,32,311 =,，A

15、/R4=1,2,3；R5=112233 =,=IA，A/R5=1,2,3。 例5.11(續(xù)）學(xué)習(xí)要求相容關(guān)系等價(jià)關(guān)系內(nèi)容導(dǎo)航CONTENTS次序關(guān)系函數(shù) 5.1 5.4 5.3 5.4特殊關(guān)系的應(yīng)用 5.5作業(yè) 5.6歷史人物問題引入制作一道四川名菜四川麻婆豆腐，需執(zhí)行下面的任務(wù)：（1）把豆腐切塊；（2）牛肉剁成牛肉餡；（3）把蒜苗切成段，蒜和姜切成小粒；（4）鍋里倒清水燒熱，下豆腐塊，加鹽煮一下?lián)瞥觯唬?）油溫?zé)?成熱，下蒜、老姜、豆瓣醬翻炒，然后加 牛肉餡炒香；（6）加豆腐塊、辣椒粉、水煮開，加蒜苗炒香，裝盤上桌。圖5.7這些任務(wù)之間存在“先后”關(guān)系，這種“先后”關(guān)系被稱為次序關(guān)系。擬序

16、關(guān)系偏序關(guān)系次序關(guān)系5.3.1 擬序關(guān)系定義5.6 設(shè)R是非空集合A上的關(guān)系，如果R是反自反、反對(duì)稱和傳遞的，則稱R是A上的擬序關(guān)系(Quasi-Order Relation)，簡(jiǎn)稱擬序，記為“”，讀作“小于”，并將“”記為“ab”。序偶稱為擬序集(Quasi-Order Set)。解題小貼士擬序關(guān)系的判斷方法R是擬序關(guān)系 R同時(shí)具有反自反性、反對(duì)稱性和傳遞性。注意：“”的逆關(guān)系“-1”也是擬序，用“”表示，讀作“大于”。例5.12例5.12 判斷下列關(guān)系是否為擬序關(guān)系（1）集合A的冪集P(A)上定義的“”；（2）實(shí)數(shù)集Z上定義的“大于”關(guān)系()；不具有反自反性 否是例5.13例5.13 如果

17、關(guān)系R在非空集合A上是反自反和傳遞的，那么R一定是反對(duì)稱的嗎？解 R一定是反對(duì)稱的。用反證法。假設(shè)R不是反對(duì)稱的關(guān)系，則存在x0, y0A，且x0y0，滿足 R并且R。因?yàn)镽具有傳遞性，從而有R。這與R的反自反性矛盾，從而假設(shè)錯(cuò)誤，即R一定是反對(duì)稱的。定義5.7 設(shè)R是非空集合A上的關(guān)系，如果R是反自反和傳遞的，則稱R是A上的 擬序關(guān)系。問題引入假設(shè)集合A是制作四川麻婆豆腐的任務(wù)集，即A1,2,3,4,5,6，A上的關(guān)系R定義為：R 如果ij或者任務(wù)i必須在任務(wù)j之前完成。則關(guān)系R具有什么性質(zhì)？是擬序關(guān)系嗎？不具有反自反性 否具有自反性、反對(duì)稱性和傳遞性的。偏序關(guān)系5.3.2 偏序關(guān)系定義5.

18、8 設(shè)R是非空集合A上的關(guān)系，如果R是自反的、反對(duì)稱的和傳遞的，則稱R是A上的偏序關(guān)系(Partial Order Relation)，簡(jiǎn)稱偏序，記為“”，讀作“小于等于”，并將“”記為ab。 序偶稱為偏序集(PartialOrder Set)。 解題小貼士偏序關(guān)系的判斷方法R是偏序關(guān)系 R同時(shí)具有自反性、反對(duì)稱性和傳遞性。注意：（1）“”的逆關(guān)系是“”，“”記為“ab”， 讀作“a大于等于b”。（2）“”“IA”為A上的擬序關(guān)系，“”“IA”為A上的偏序關(guān)系。例5.13 試判斷下列關(guān)系是否為偏序關(guān)系（1）設(shè)A=1,2,3，A上的關(guān)系R=,。（2）設(shè)A=1,2,3，A上的關(guān)系S= ,。（3）整

19、數(shù)集Z上的模m同余關(guān)系T。例5.13不具有自反性 否是否不具有反對(duì)稱性 例5.14 證明整數(shù)集Z上的整除關(guān)系“|”是偏序關(guān)系。例5.14例5.15例5.15 試寫出制作四川麻婆豆腐的任務(wù)集A1,2,3,4,5,6上的關(guān)系R中的元素，并畫出它的關(guān)系圖。解 根據(jù)R的定義，有R, , ,其關(guān)系圖如圖5.8所示。哈斯圖如果已知R是偏序關(guān)系，那么它的關(guān)系圖一定具有如下特點(diǎn)：（1）每個(gè)結(jié)點(diǎn)都有自環(huán)（自反性）；（2）任意兩個(gè)結(jié)點(diǎn)要么有且僅有一條邊相連，要么沒有邊相連（反對(duì)稱性）；（3）如果元素a到元素b有邊相連，元素b到元素c有邊相連，則元素a到元素c必然有邊相連（傳遞性）。R是偏序關(guān)系 R同時(shí)具有自反性、

20、反對(duì)稱性和傳遞性。哈斯圖用小圓圈或點(diǎn)表示A中的元素，省掉關(guān)系圖中所有的環(huán)； （因自反性)對(duì)任意x,yA，若xy，則將x畫在y的下方，可省掉關(guān)系圖中所有邊的箭頭；（因反對(duì)稱性）3. 對(duì)任意x,yA，若xy，且不存在zA，使得xz, zy，則x與y之間用一條線相連，否則無(wú)線相連。 （因傳遞性）按照（1），（2）和（3）作成的圖被稱為R的哈斯圖（Hasse圖）。如果A上的關(guān)系R是偏序關(guān)系，那么可以按照下面的方式簡(jiǎn)化它的關(guān)系圖。例5.16例5.16 畫出例5.15中關(guān)系R的哈斯圖。解 例5.15中關(guān)系R的哈斯圖如圖5.9所示。例5.17例5.17 設(shè)A1,2,3,4,6,12，“”是A上的整除關(guān)系R，

21、先寫出R中元素，并判定能否畫出R的哈斯圖。如果能，請(qǐng)畫出其哈斯圖。解 由題意可得 R, , , ,。其哈斯圖如圖5.10所示。最大元最小元特殊元素 例5.18例5.18 設(shè)B12,4,6,12，B21,2,3是例5.17中集合A的子集，試求出B1，B2的最大元和最小元。解 子集B1，B2形成的哈斯圖分別如圖5.11（a） 和5.11（b）。 從圖5.11（a）可以看出，B1的最大元是12， 最小元是2。 從圖5.11（b）可以看出，圖的最上端存在 兩個(gè)元素2和3，它們之間不能比較，因此 B2無(wú)最大元，最小元是1。極大元特殊元素 例5.19 例5.19 設(shè)B31,2,3,4,6，B44,6,12

22、是例5.17中集合A的子集，試求出B3，B4的最大元、最小元、極大元和極小元。解 子集B3，B4形成的哈斯圖分別如圖5.12（a）和5.12（b）。B3，B4的最大元、最小元、極大元和極小元如下表所示。集合最大元極大元最小元極小元B3無(wú)4,611B41212無(wú)4,6定義5.11由定義5.3.5知解題小貼士例5.40例5.40 試求出例5.18和5.19中A的子集B1，B2，B3和B4的上界、下界、上確界和下確界。解 集合B1，B2，B3和B4的上界、下界、上確界和下確界如表5.4所示。 集合上界上確界下界下確界B1B2B3B412121,226,1261112121112121,22例5.41

23、例5.41 A=x1,x2,x3,x4，A上定義偏序集的哈斯圖如右圖所示。求B=x1,x2和C=x3,x4最大元、最小元、極大元、極小元、上界、下界、上確界和下確界。解 見下表。集合最大元極大元上界上確界最小元極小元下界下確界BC無(wú)x3,x4無(wú)無(wú)x1,x2無(wú)無(wú)無(wú)x1x3x2x4無(wú)無(wú)無(wú)無(wú)x1,x2x1,x2x3,x4x3,x4定理5.5定理5.5 設(shè)是一偏序集，B是A的子集。則：（1）b是B的最大元 b是B的極大元、上界、上確界；（2）b是B的最小元 b是B的極小元、下界、下確界；（3）a是B的上確界，且aB a是B的最大元；（4）a是B的下確界，且aB a是B的最小元。定理5.6定理5.6 設(shè)

24、是一偏序集，B是A的子集。則：（1）若B存在最大元，則B的最大元是惟一的；（2）若B存在最小元，則B的最小元是惟一的；（3） b是B的最大元 b是B的惟一極大元；（4） b是B的最小元 b是B的惟一極小元；（5）若B存在上確界，則B的上確界是惟一的；（6）若B存在下確界，則B的下確界是惟一的。問題引入在偏序關(guān)系中，為什么A的非空子集B通常存在多個(gè)極大元或極小元呢？因?yàn)檫@些極大元或者極小元之間不存在偏序關(guān)系！如果在給定偏序關(guān)系中增加“A中任意兩個(gè)元素均存在偏序關(guān)系”，那么這樣的偏序關(guān)系被稱為全序關(guān)系。5.3.3 全序關(guān)系例5.42例5.42 試判斷下列關(guān)系是否為全序關(guān)系，如果是，請(qǐng)畫出其哈斯圖。

25、（1）設(shè)集合A=a,b,c，其上的關(guān)系“”=, , （2）實(shí)數(shù)集R上的大于等于關(guān)系“”；（3）集合A的冪集P(A)上定義的包含關(guān)系“”。例5.42 解（1）是全序集，其哈斯圖見圖(a)；（2） 是全序集，其哈斯圖是數(shù)軸，見圖(b)，其中x,y,zR；不是全序關(guān)系；（3）當(dāng)|A|2時(shí)，P(A)上定義的“”是全序關(guān)系，是全序集，其哈斯圖見圖(c)；當(dāng)|A|2，則不是全序集。a(c)abc(a)xya(b)A的任何非空子集都有最小元，像這樣的全序關(guān)系被稱為良序關(guān)系5.3.4 良序關(guān)系定義5.13 設(shè)是一偏序集，若A的任何一個(gè)非空子集都有最小元素，則稱“”為良序關(guān)系（Well Order Rrelat

26、ion），簡(jiǎn)稱良序，此時(shí)稱為良序集（Well Order Set）。解題小貼士非空集合A上的關(guān)系R是良序關(guān)系的判斷方法（1）確定關(guān)系R是偏序關(guān)系；（2）A的任何一個(gè)非空子集都有最小元。例5.43例5.43 試判斷例5.42中的(1)和(2)是否為良序關(guān)系。（1）設(shè)集合A=a,b,c，其上的關(guān)系“”=, , （2）實(shí)數(shù)集R上的大于等于關(guān)系“”。是否存在非空子集(0,1)開區(qū)間沒有最小元5.3.6次序關(guān)系的應(yīng)用例5.3.15 計(jì)算機(jī)科學(xué)中常用的字典排序如下：設(shè)是一有限的字母表。上的字母組成的字母串叫上的字；*是包含空字“”的所有字組成的集合，建立*上的字典次序關(guān)系L：設(shè)x=x1x2xn，y=y1y

27、2ym，其中xi,yj(i=1,2,n；j=1,2,m)，則x,y*?？偨Y(jié)自反性反自反性對(duì)稱性反對(duì)稱性傳遞性相容關(guān)系等價(jià)關(guān)系擬序關(guān)系偏序關(guān)系學(xué)習(xí)要求相容關(guān)系等價(jià)關(guān)系內(nèi)容導(dǎo)航CONTENTS次序關(guān)系函數(shù) 5.1 5.4 5.3 5.4特殊關(guān)系的應(yīng)用 5.5作業(yè) 5.6歷史人物問題引入 函數(shù)也叫映射、變換或?qū)?yīng)。 函數(shù)本質(zhì)上是一種關(guān)系。 任何一個(gè)從A到B的關(guān)系都可以成為A到B的一個(gè)函數(shù)嗎？No，No滿足什么條件的從A到B的關(guān)系才是A到B的函數(shù)呢？5.4.1函數(shù)的基本概念函數(shù)的定義定義5.14 設(shè)f是集合A到B的關(guān)系，如果對(duì)每個(gè)xA，都存在惟一的yB，使得f，則稱關(guān)系f為A到B的函數(shù)(Functio

28、n)(或映射(Mapping)、變換(Transform)，記為f:AB。其中 A為函數(shù)f的定義域，記為domf=A； f(A)為函數(shù)f的值域，記為ranf=f(A)。 當(dāng)f時(shí)，通常記為y=f(x)， 這時(shí)稱x為函數(shù)f的自變量，y為x在f下的函數(shù)值(或象)， 也稱x為y在f下的原象 。 例5.24例5.24 設(shè)P是接受一個(gè)整數(shù)作為輸入并產(chǎn)生一個(gè)整數(shù)作為輸出的計(jì)算機(jī)程序。令A(yù)=B=Z，則由P確定的關(guān)系fp定義如下：如果fp當(dāng)且僅當(dāng)輸入m時(shí)，由程序P所產(chǎn)生的輸出是n。請(qǐng)判斷fp是否為函數(shù)。解 fp是一個(gè)函數(shù)。因?yàn)橛?jì)算結(jié)果是可重復(fù)的，即對(duì)相同的輸入，程序每次運(yùn)行都有相同的結(jié)果，所以根據(jù)程序P的規(guī)定，

29、對(duì)任意一個(gè)特殊的輸入，一定對(duì)應(yīng)惟一的輸出。事實(shí)上，計(jì)算機(jī)的輸入輸出關(guān)系都可以被看作函數(shù)。例5.25例5.25 設(shè)集合A1,2，Ba,b，試判斷下列關(guān)系哪些是函數(shù)。如果是函數(shù)，請(qǐng)寫出它的值域。（1）R1。（2）R2,。（3）R3,。（4）R4,。是否是否不滿足（1）不滿足（2）ranR3=aranR4=a,b例5.26例5.26 對(duì)例5.25中的集合A和B，請(qǐng)分別寫出所有A到B的不同關(guān)系和不同函數(shù)。解 因?yàn)锳B,，所以從A到B的不同的關(guān)系有2|AB|=24=16個(gè)。分別如下：R0=；R1=；R2=；R3=；R4=；R5=,；R6=,；R7=,；R8=,；R9=,；R10=,；R11=,；R12=

30、,；R13=,；R14=,；R15=,。從A到B的不同的函數(shù)通常，將從A到B的一切函數(shù)構(gòu)成的集合記為BA： BA f | f：AB。函數(shù)與關(guān)系的差別當(dāng)A和B都是有限集合時(shí)，函數(shù)和一般關(guān)系具有如下差別：（1）從A到B的不同的關(guān)系有2|A|B|個(gè)；但從A到B的不同的函數(shù)卻僅有|B|A|個(gè)。 (個(gè)數(shù)差別)（2）關(guān)系的第一個(gè)元素可以相同；函數(shù)的第一元素一定是互不相同的。 (集合元素的第一個(gè)元素存在差別)（3）每一個(gè)函數(shù)的基數(shù)都為|A|個(gè)(|f|=|A|)，但關(guān)系的基數(shù)卻為從零一直到|A|B|。 (集合基數(shù)的差別)2 函數(shù)的類型解題小貼士注意 若f是從有限集A到有限集B的函數(shù)，則有：（1） f是單射的必

31、要條件為|A|B|；（2） f是滿射的必要條件為|B|A|；（3） f是雙射的必要條件為|A|B|。例5.27例5.27 試分別構(gòu)造單射、滿射、雙射和變換。解 （1）構(gòu)造單射函數(shù)如下： 設(shè)A=1,2,3，B=a,b,c,d。f1 :AB定義為： , ； （2）構(gòu)造滿射函數(shù)如下：設(shè)A=1,2,3,4，B=a,b,c。f2:AB定義為： , ； （3）構(gòu)造雙射函數(shù)如下：設(shè)A1,2,3， B=a,b,c 。f3:AB定義為：, ； （4）構(gòu)造變換如下：設(shè)A1,2,3，B1,2,3，f4：AB定義為：,。定理5.7定理5.7 設(shè)A，B是有限集合，且|A|=|B|，f是A到B的函數(shù)，則f是單射當(dāng)且僅當(dāng)f

32、是滿射。證明 必要性()：設(shè)f是單射。顯然，f是A到f(A)的滿射，故f是A到f(A)的雙射，因此|A|=|f(A)|。由|f(A)|=|B|，且f(A)B，得f(A)=B，故f是A到B的滿射。定理5.7（續(xù)）充分性()：設(shè)f是滿射。任取x1,x2A，x1x2，假設(shè)f(x1)=f(x2)，由于f是A到B的滿射，所以f也是A-x1到B的滿射，故|A-x1|B|，即|A|-1|B|，這與|A|=|B|矛盾。因此f(x1)f(x2)，故f是A到B的單射。例5.28 設(shè)A1,2,3,n，f是A到A的滿射，并且具有性質(zhì)： f(xi)yi，i1,2,3,k，kn，xi,yiA。求f的個(gè)數(shù)。例5.28解：f

33、是有限集A到A的滿射，可知f是A到A的雙射。由于f已將A中的某k個(gè)元素與另外k個(gè)元素的對(duì)應(yīng)，所以只需考慮剩下n-k個(gè)元素的對(duì)應(yīng)，為此，令BA-xi|i1,2,3,k;CA-yi|i1,2,3,k則從B到C的滿射個(gè)數(shù)(即是雙射個(gè)數(shù))就是f的個(gè)數(shù)。根據(jù)推論2.3.1有，從A到A的滿足題目條件的不同滿射個(gè)數(shù)共有(n-k)!。例5.29例5.29 設(shè)X=0,1,2,，Y=1,1/2,1/3,，f:XY的定義如下： (1) f1=, （2）f2=, （3）f3=,。試判斷它們的類型。例5.29 解（1）由已知得，根據(jù)函數(shù)f1(n)的表達(dá)式和單射函數(shù)的定義知，f1是單射函數(shù)；但是，Y中元素1沒有原象，所以

34、f1不是滿射函數(shù)； (2) 由已知得，顯然f2是滿射函數(shù)。但是，X中元素0和1有相同的象1，所以f2不是單射函數(shù)；例5.29 解(續(xù)）（3） 由已知得， 顯然，f3是雙射函數(shù)。例5.30 設(shè)R是集合A上的一個(gè)等價(jià)關(guān)系，g：AA/R稱為A對(duì)商集A/R的典型(自然)映射，其中g(shù)(a)aR，aA.證明：典型映射是一個(gè)滿射。例5.30分析：由等價(jià)類的定義，對(duì)任意aRA/R，aaR，即任意A/R中的元 素都有原象，所以典型映射是滿射。證明過程留給讀者。例5.31 設(shè)是偏序集，對(duì)任意aA，令：f(a)x|(xA)(xa)證明：f是從A到P(A)的單射函數(shù)，并且f保持與的偏序關(guān)系，即：對(duì)任意a,bA，若ab

35、，則f(a)f(b)。例5. 31 證明：1) f是映射。任取aA，由于f(a)x|(xA)(xa)A，所以f(a)P(A)，即f是從A到P(A)的函數(shù)。2) f是單射。對(duì)任意a,bA，ab 若a,b存在偏序關(guān)系，不妨設(shè)ab a b ba bf(a)x|(xA)xa （“”是反對(duì)稱的）又因?yàn)?bb （“”是自反的）bb bf(b) x|(xA)xb 所以f(a)f(b) )，從而f是單射。 若a,b不存在偏序關(guān)系，則有：ab af(b)x|(xA)xb 又因?yàn)?aa （“”是自反的） aa af(a)，即f(a)f(b)，從而f是單射。因此對(duì) a，bA，當(dāng)ab，總有f(a)f(b)。從而f是從

36、A到P(A)的單射。例5.31 (續(xù))例5.31 (續(xù))3.一些重要的函數(shù)定義5.16 （續(xù)）（4）對(duì)有理數(shù)x，f(x)為大于等于x的最小的整數(shù)，則稱f(x)為上取整函數(shù)(Floor Functions)(強(qiáng)取整函數(shù))(，記為f(x)= ；（5）對(duì)有理數(shù)x，f(x)為小于等于x的最大的整數(shù)，則稱f(x)為下取整函數(shù)(弱取整函數(shù))，記為f(x)= ；（6）如果f(x)是集合A到集合B0,1上的函數(shù)，則稱f(x)為布爾函數(shù)（Boolean Function）。定義5.17定義5.17 設(shè)A和B是兩個(gè)集合。（1）如果A=R，B=(0,1)，則Sigmoid函數(shù)定義為： （2）如果A=R，B=(-1,

37、1)，則tanh函數(shù)定義為： （3）如果A=R，B=0,+），則ReLU函數(shù)定義為：ReLU(x)=max(0,x) 例5.32例5.32 設(shè)A=B=R(實(shí)數(shù)集)。試指出下列函數(shù)的類型。（1）f1=|xR；（2）f2=|xR,aR；（3）f3=|xR；（4）f4=|xR。解（1）f1是恒等函數(shù)，（2）f2是常值函數(shù)，（3）f3是上取整函數(shù)，（4）f4是下取整函數(shù)。 5.4.2 函數(shù)的運(yùn)算1. 函數(shù)的復(fù)合運(yùn)算定義5.18 設(shè)f：AB，g：BC是兩個(gè)函數(shù)，如果f與g的復(fù)合關(guān)系fg|xAzCy(fg)是從A到C的函數(shù)，則稱fog為f與g的復(fù)合函數(shù)（Composition Function)。例5.3

38、3例5.33 設(shè)A=1,2,3，B=a,b,c。函數(shù)f：AA，g：AB分別為：f,，g,求fog和gof。解 （1）fog, （2）gof不能計(jì)算，因?yàn)間的值域不是f的定義域的子集。例5.33例5.33 設(shè)f:RR，g:RR，h:RR，滿足f(x)=2x，g(x)x2，h(x)ex。計(jì)算：（1）(fg)h，f(gh)；（2）fh，hf。解（1）(fg)h)(x)h(fog)(x)h(g(f(x)h(g(2x)h(2x)2) 。 (f(gh)(x)(gh)(f(x)h(g(f(x) 。 （2）foh(x)h(f(x)h(2x)e2x，hof(x)f(h(x)f(ex)2ex。定理5.8 設(shè)f和g

39、分別是A到B和從B到C的函數(shù)，則：(1) 如f,g是滿射，則fg也是從A到C滿射；(2) 如f,g是單射，則fg也是從A到C單射；(3) 如f,g是雙射，則fg也是從A到C雙射。定理5.8 定理5.8 證明定理5.9定理5.9 設(shè)f和g分別是A到B和B到C的函數(shù)，則（1）如fog是A到C的滿射，則g是B到C 的滿射；（2）如fog是A到C的單射，則f是A到B的單射；（3）如fog是A到C的雙射，則f是A到B的單射，g是B到C的滿射。定理5.9 證明2. 函數(shù)的逆運(yùn)算問題引入：每個(gè)關(guān)系都有其逆關(guān)系，每個(gè)函數(shù)是否都有其逆函數(shù)呢？No，No例如 設(shè)A=1,2,3，R=,，S=,是A上的關(guān)系，則有 R

40、-1=, S-1=,不是是2. 函數(shù)的逆運(yùn)算定義5.19 設(shè)f:AB的函數(shù)。如果f-1|xAyBf是從B到A的函數(shù)，則稱f-1：BA的逆函數(shù)(Inverse Function)。解題小貼士f逆函數(shù)的計(jì)算方法（1）確定f是雙射。（2）對(duì)集合表示的函數(shù)，互換f中每個(gè)序偶兩個(gè)元素的位置即可；對(duì)表達(dá)式形式的函數(shù)如y=f(x)，首先反解f(x)，用y表示x，然后x與y的位置互換即可。例5.34例5.34 試判斷下列函數(shù)是否具有逆函數(shù)，如果有，試求出其逆函數(shù)。（1）f1,是A上的函數(shù)，其中A1,2,3。（2）f2,是A上的函數(shù)，其中A1,2,3。（3）f3(x)x2，xR。（4）f4(x)x+1，xR。無(wú)

41、f1不是A上的雙射函數(shù)f2-1,無(wú)f1不是A上的雙射函數(shù)f4-1(x)=x-1定理5.10 定理5.10 設(shè)f是A到B的雙射函數(shù)，則：f-1fIB|bB；ff-1IA|aA；IAffIBf。略。定理5.11 定理5.11 若f是A到B的雙射，則f的逆函數(shù)f1也是B到A的雙射。5.4.3 置換函數(shù)當(dāng)A是有限集合時(shí)，這種情況具有特殊重要性。有限集合上的雙射函數(shù)在數(shù)學(xué)、計(jì)算機(jī)科學(xué)和物理學(xué)中有著非常廣泛的應(yīng)用。5.4.1基本概念定義5.19 設(shè)A=a1,a2,an是有限集合。從A到A的雙射函數(shù)稱為A上的置換或排列(Permutation)，記為P:AA，n稱為置換的階(Order)。 n階置換P:AA

42、常表示為：例5.35例5.35 設(shè)A1,2,3，請(qǐng)寫出A上的所有置換P。解 A上的所有置換P如下：學(xué)習(xí)要求相容關(guān)系等價(jià)關(guān)系內(nèi)容導(dǎo)航CONTENTS次序關(guān)系函數(shù) 5.1 5.4 5.3 5.4特殊關(guān)系的應(yīng)用 5.5作業(yè) 5.6歷史人物5.5.1 等價(jià)關(guān)系的應(yīng)用例5.36 在下圖中，點(diǎn)i和j之間有路當(dāng)且僅當(dāng)從結(jié)點(diǎn)i通過圖中的邊能夠到達(dá)結(jié)點(diǎn)j。規(guī)定對(duì)任意結(jié)點(diǎn)i，i和i之間一定有路。定義R如下：Ri和j之間有路。試說明該關(guān)系R是否可以給定結(jié)點(diǎn)集A=1,2,3,4,5,6,7,8一個(gè)劃分？如果能，請(qǐng)給出具體的劃分。75683124解（1）由于規(guī)定任意結(jié)點(diǎn)i與他自身之間一定有路，因此R，即R具有自反性；（

43、2）若R，則兩個(gè)結(jié)點(diǎn)i和j之間存在路，當(dāng)然也存在j和i之間的路，所以R，即R具有對(duì)稱性；（3）若R，R，則結(jié)點(diǎn)i和j之間有路，j和k之間也有路，從而i到k之間存在經(jīng)過j的路，即有R，因此得到R具有傳遞性。由(1)、(2)和(3)知，R是等價(jià)關(guān)系。于是所有不同的等價(jià)類為：1R=1,2,3,4，5R=5,6,7，8R=8。根據(jù)定理5.3知，A/R=1R,5R,8R=1,2,3,4,5,6,7,8就是A的一個(gè)劃分。例5.37例5.37 信息檢索系統(tǒng)中的信息有離散數(shù)學(xué)，高等數(shù)學(xué)，計(jì)算機(jī)操作系統(tǒng)，計(jì)算機(jī)網(wǎng)絡(luò)，數(shù)據(jù)結(jié)構(gòu)，編譯原理，軟件工程，計(jì)算機(jī)組成原理。試給該信息檢索系統(tǒng)指定三種不同的劃分。解 設(shè)A=離

44、散數(shù)學(xué)，高等數(shù)學(xué)，計(jì)算機(jī)操作系統(tǒng)，計(jì)算機(jī)網(wǎng)絡(luò)，數(shù)據(jù)結(jié)構(gòu)，編譯原理，軟件工程，計(jì)算機(jī)組成原理，則劃分1：含關(guān)鍵詞離散數(shù)學(xué)，則A=離散數(shù)學(xué),高等數(shù)學(xué),計(jì)算機(jī)操作系統(tǒng),計(jì)算機(jī)網(wǎng)絡(luò),數(shù)據(jù)結(jié)構(gòu),編譯原理,軟件工程,計(jì)算機(jī)組成原理；劃分2：含關(guān)鍵詞數(shù)學(xué)，則A=離散數(shù)學(xué),高等數(shù)學(xué),計(jì)算機(jī)操作系統(tǒng),計(jì)算機(jī)網(wǎng)絡(luò),數(shù)據(jù)結(jié)構(gòu),編譯原理,軟件工程,計(jì)算機(jī)組成原理；劃分3：含關(guān)鍵詞計(jì)算機(jī)，則A=離散數(shù)學(xué)，數(shù)據(jù)結(jié)構(gòu),編譯原理,軟件工程,高等數(shù)學(xué),計(jì)算機(jī)操作系統(tǒng),計(jì)算機(jī)網(wǎng)絡(luò),計(jì)算機(jī)組成原理。5.5.2 次序關(guān)系的應(yīng)用例5.38 計(jì)算機(jī)科學(xué)中常用的字典排序如下：設(shè)是一有限的字母表。上的字母組成的字母串叫上的字；*是包含空字“

45、”的所有字組成的集合，建立*上的字典次序關(guān)系L：設(shè)x=x1x2xn，y=y1y2ym，其中xi,yj(i=1,2,n；j=1,2,m)，則x,y*。（1）當(dāng)x1y1時(shí)，若x1y1，則xLy；若y1x1，則yLx。（2）若存在最大的k且kmin(n,m),使xi=yi(i=1,2, k)，而xk+1yk+1，若xk+1yk+1，則xLy；若yk+1xk+1，則yLx。（3）若存在最大的k且k=min(n,m)，使xi=yi(i=1,2,3,k)，此時(shí)，若nm，則xLy；若mn，則yLx。證明 L是*上的一個(gè)偏序關(guān)系且是一個(gè)全序關(guān)系。例5.38 證明首先證明L是偏序關(guān)系。（1）L是自反的。對(duì)任意x

46、*，令x=x1x2xn，其中xi，顯然有xixi(i=1,2,n)，從而有xLx；（2）L是反對(duì)稱的。對(duì)任意x，y*，令x=x1x2xn, y=y1y2ym，其中xi,yj(i=1,2,n；j=1,2,m)。若xLy且yLx，根據(jù)L的定義有x=y；例5.38 證明（續(xù)）（3）L是傳遞的。對(duì)任意x,y,z*，令x=x1x2xn, y=y1y2ym，z=z1z2zp，其中xi,yj,zk(i=1,2,n；j=1,2,m；k=1,2,p)。若xLy且yLz，根據(jù)L的定義和“”的傳遞性，有xLz。綜上所述，L是*上的一個(gè)偏序關(guān)系。對(duì)任意x,y*，由x和y的表示形式知，xi和yi(i=1,2,n)總能進(jìn)

47、行比較，所以一定有xLy和yLx之一成立，從而L是*上的一個(gè)全序關(guān)系。例5.39例5.39 如果一個(gè)軟件項(xiàng)目需要完成的任務(wù)對(duì)應(yīng)的哈斯圖如圖5.17所示，求一個(gè)全序執(zhí)行這些任務(wù)以完成這個(gè)項(xiàng)目。例5.39解解 執(zhí)行這些任務(wù)的一種全序?yàn)椋?確定用戶需求寫出功能需求開發(fā)系統(tǒng)需求設(shè)置測(cè)試點(diǎn) 開發(fā)模塊A開發(fā)模塊B開發(fā)模塊寫文檔模塊集成 測(cè)試測(cè)試完成。 還可以寫出其它排序方法，此處不再敘述。5.5.3 函數(shù)的應(yīng)用解 （1）P(An)到Bn可以按照如下的方式建立關(guān)系：對(duì)任意SP(An)，令f(S)b1b2b3bn，其中：例5.40 設(shè)Ana1,a2,an是n個(gè)元素的有限集，Bnb1 b2bn|bi0,1，試建

48、立 P(An)到Bn的一個(gè)雙射。例如A3=a1,a2,a3，則有：000, a1110, a2010, a3001, a1,a2110, a1,a3101, a2,a3011, a1,a2,a3111。（2）證明f是雙射。 1) 證f是映射。因?yàn)閨P(An)|=|Bn|=2n，且對(duì) sP(An)，都有惟一的b1b2bnBn ，使得f(S) b1b2bn ，所以f是函數(shù)。 2) 證f是單射。任取S1,S2P(An)，S1S2，則存在元素ajAn(1jn)，使得ajS1，ajS2或ajS2，ajS1。從而f(S1)b1b2b3bn中必有bj1，f(S2)c1c2c3cn必有cj0或f(S1)b1b2b3bn中必有bj0，f(S2)c1c2c3cn必有cj1。所以f(S1)f(S2)，即f是單射。例