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

類、商集、相容關(guān)系、(最大)相容類、偏序關(guān)系、極大界、上(下)確界、最大(小)元、全序關(guān)系、良序關(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é)理解重點和難點的內(nèi)容，并通過大量的練習(xí)使同學(xué)們鞏固和掌握關(guān)系的性質(zhì)及其判別、關(guān)系的復(fù)合運算及其性質(zhì)、等價關(guān)系的特性、偏序關(guān)系的哈斯圖的畫法及偏序集中特異位置元素的求法。3.1集合的基本概念禁煙教案N-自然數(shù)集合(非負整數(shù)集)1(或Z)-整數(shù)集合(1,1)冪集人們常常給有限集A的子集編碼，用以表示A的冪集的各個元素。具體方法是：設(shè)A={a,a,…,a},則A子集B按照含a記1、不含a記0(i=1,2,…,n)的規(guī)定12n例如，若,則B的編碼是100…01,當然還可將它化成十進制數(shù)。如果n=4,那么這個十進制數(shù)為9,此時特別記定義3.2.1設(shè)A、B是兩個集合，要么屬于A,要么屬于B,但不能同時屬于A和B的所有元素組成的集合，稱為A和B的對稱差集，記為A田B。即圖3-1證明(5)(A田B)田C=(A∩B∩C)U(A∩B∩C)U{[(AUBAUB=[AN(B∩C)U(B∩C)]U{A∩[(B∩C)U禁煙教案A田B從文氏圖3-3亦可以看出以下關(guān)系式成立。3.4序偶與笛卡爾積禁煙教案元素。有序三元組是一個序偶，其第一元素本身也是一個序偶，可形式化表示為3.4.2笛卡爾積禁煙教案B×B={(a,a}.(a,b},(a,c),(b,a),(b,b},(b,c},(c,a},(c,bB×A={(a,1},(a,2>,(b,1),(b,2>,(c,1}AGC且BcD是有序n元組構(gòu)成的集合。圖3-4禁煙教案當X=Y時，關(guān)系R是X×X的子集，這時稱R為集合X上的二元關(guān)系。例3.5.1(1)設(shè)A={a,b},B={2,5,8},則A×B={(a,2},(a,5>,(a,8>,(b,2},(b,5>,(b,8》,令因為R≤A×B,R≤A×B,R≤A×B,所以R,R,和R均是由A到B的關(guān)3R的定義域和值域一起稱作R的域(Field),記作FLDR,即例3.5.2設(shè)A={1,3,7},B={1,2,6},H={(1,2>,(1,6>,(7,2》),例3.5.3設(shè)X={2,3,4,5},求集合X上的關(guān)系“<”、dom<及ran<。3.5.2幾種特殊的關(guān)系1.空關(guān)系對任意集合X,Y,φSX×Y,φCX×X,所以φ是由X到Y(jié)的關(guān)系，也是X2.全域關(guān)系因為X×YsX×Y,X×X5X×X,所以X×Y是一個由X到Y(jié)的關(guān)系，稱為域關(guān)系，通常記作,即例3.5.4若H={f,m,s,d}表示家庭中父、母、子、女四個人的集合，確定H上的全域關(guān)系和空關(guān)系，另外再確定H上的一個關(guān)系，并指出該關(guān)系的前域和值域。解設(shè)H上同一家庭的成員的關(guān)系為H,33證明因為Q=X×Y,S≤X×Y,R·R3.5.3關(guān)系的表示因為關(guān)系是序偶的集合，因此可用表示集合的列舉法或描述法來表示關(guān)系。例如，例3.5.1的(1)中的關(guān)系R,R、和R、及例3.5.2中的關(guān)系H,均是用列舉法表示的關(guān)系；而例3.5.1的(2)中的關(guān)系>和例3.5.5中的關(guān)系R,R都是用描述法表示的關(guān)系。有限集合間的二元關(guān)系R除了可以用序偶集合的形式表達以外，還可用矩陣和圖形表示，以便引入線性代數(shù)和圖論的知識來討論。2.矩陣表示法設(shè)給定兩個有限集合,Y={y,y,,…,y},則對應(yīng)于從X到Y(jié)的二元關(guān)系R有一個關(guān)系矩陣,其中如果R是有限集合X上的二元關(guān)系或X和Y含有相同數(shù)量的有限個元素，則M是方陣。例3.5.6若R={(a,b>·(a,b>·(a?b?>·(a,b>(a,b>(a,b>(a,b,))解例3.5.7設(shè)X={1,2,3,4},寫出集合X上的大于關(guān)系>的關(guān)系矩陣。3.關(guān)系圖表示法上的一個二元關(guān)系為R,首先我們在平面上做出m個結(jié)點分別記作例3.5.8畫出例3.5.6的關(guān)系圖。解本題的關(guān)系圖如圖3-11所示：圖3-11例3.5.8的關(guān)系圖解因為R是A上的關(guān)系，故只需畫出A中的每個元素即可。如果aRa,就畫一條由a到a的有向弧。若a=a,則畫出的是一條自回路。本題的關(guān)系圖如圖3-12所示。35(4)對于任意x,y∈X,若xRy,yRx,必有x=y,則稱R在X上是反對稱的(5)對于任意x,y,z∈X,若xRy,yRz,就有xRz,則稱R在X上是傳遞的例3.6.1設(shè)A={1,2,3},則集合A上的關(guān)系圖3-5表明了自反與反自反、對稱與反對稱性之間的關(guān)系。EE例3.6.2(1)集合之間的三關(guān)系是自反的、反對稱的和可傳遞的。因為：1)對于任意集合A,均有ASA成立，所以三是自反的；2)對于任意集合A,B,若A<B且BCA,則A=B,所以C是反對稱的；3)對于任意集合A,B,C,若A≤B且B=C,則AcC,所以C是可傳遞(2)平面上三角形集合中的相似關(guān)系是自反的、對稱的和可傳遞的。因為：任意一個三角形都與自身相似；若三角形A相似于三角形B,則三角形B必相似于三角形A;若三角形A相似于三角形B,且三角形B相似于三角形C,則三角形A必相似于三角形C.C(3)人類的祖先關(guān)系是反自反、反對稱和可傳遞的。(4)實數(shù)集上的">"關(guān)系是反自反、反對稱和可傳遞的。(5)實數(shù)集上的“≤”關(guān)系是自反、反對稱和可傳遞的。(6)實數(shù)集上的“=”關(guān)系是自反、對稱、反對稱和可傳遞的。(7)人群中的父子關(guān)系是反自反和反對稱的。(8)正整數(shù)集上的整除關(guān)系是自反、反對稱和可傳遞的。(9)φ是反自反、對稱、反對稱和可傳遞的。禁煙教案(10)任意非空集合上的全關(guān)系是自反的、對稱的和可傳遞的。例3.6.3設(shè)整數(shù)集Z上的二元關(guān)系R定義如下：yRx,因此R是對稱的。3.6.2由關(guān)系圖、關(guān)系矩陣判別關(guān)系的性質(zhì)例3.6.4集合A={1,2,3,4},A上的關(guān)系R的關(guān)系矩陣為：R的關(guān)系圖如圖3-6所示。討論R的性質(zhì)。圖3-6(1)若關(guān)系R是自反的，當且僅當其關(guān)系矩陣的主對角線上的所有元素都是1;其關(guān)(2)若關(guān)系R是對稱的，當且僅當其關(guān)系矩陣是對稱矩陣；其關(guān)系圖上任意兩個結(jié)(3)若關(guān)系R是反自反的，當且僅當其關(guān)系矩陣的主對角線上的元素皆為0;關(guān)系圖且,則;其關(guān)系圖滿足：對Vi,j,k,i≠j,j≠k,若有弧由a指向a,且又J例3.6.5圖3-7是由關(guān)系圖所表示的A={a,b,c}上的5個二元關(guān)系。圖3-73.7復(fù)合關(guān)系和逆關(guān)系例3.7.2設(shè)A是所有人的集合。那么而定理3.7.1設(shè)R是由集合X到Y(jié)的關(guān)系，則IoR=RoI=R。(3)若ranR∩domS=φ,則RoS=φ。證(1)和(2)是顯然的，下面我們證明(3)。用反證法。1)So(RUR)=(SoR)U(SoR)所以(2)關(guān)系的復(fù)合運算不滿足交換律。例3.7.4(1)設(shè)A={a,b,c},B={x,y,z},R和R,都是從A到B的關(guān)系，S 系，在計算這一關(guān)系時，可以運用結(jié)合律將其中任意兩個相鄰的關(guān)系先結(jié)合。特別地，當A=A=…=A=A,,即R是集合A上的關(guān)系時，復(fù)合關(guān)系簡記作Rn,它也是集A上的一個關(guān)系。3.7.2復(fù)合關(guān)系的矩陣表示及圖形表示因為關(guān)系可用矩陣表示，所以復(fù)合關(guān)系也可用矩陣表示。A代表邏輯乘，滿足0?0=0,0?1=0,1?0=0,1?1=1。解3.7.3逆關(guān)系禁煙教案22例如，在實數(shù)集上，關(guān)系"<"的逆關(guān)系是">"。其它自證。(2)自證。(4)R是自反的，當且僅當ISR;X(3)若R2≤R,則對Vx,y,z∈X,解3.8關(guān)系的閉包運算關(guān)系作為集合，在其上已經(jīng)定義了并、交、差、補、復(fù)合及逆運算?，F(xiàn)在再來考慮一種新的關(guān)系運算一關(guān)系的閉包運算，它是由已知關(guān)系，通過增加最少的序偶生成滿足某種A上含R且最小的對稱關(guān)系是：定義3.8.1設(shè)R是X上的二元關(guān)系，如果有另一個X上的關(guān)系R滿足：(1)R是自反的(對稱的，傳遞的);R"2R'。則稱關(guān)系R為R的自反(對稱，傳遞)閉包(Reflexive(Symmetric,顯然，自反(對稱，傳遞)閉包是包含R的最小自反(對稱，傳遞)關(guān)系。定理3.8.1設(shè)R是X上的二元關(guān)系，那么(2)、(3)的證明完全類似。下面討論由給定關(guān)系R,求取R的方法。定理3.8.2設(shè)R是集合X上的二元關(guān)系，則(2)令R=RUR-1,即R2=繼續(xù)這個運算有：若,則存在整數(shù)p>0,使得xRpx成立，既存在序列a,a,…aJ12p-1’設(shè)滿足上述條件的最小p大于n,不妨x=a,x=a,則序列中必有0解所以為計算元素較多的有限集合X上二元關(guān)系R的傳遞閉包，Warshall在1962年提出了一個有效的算法(假定集合X含有n個元素):(5)如果i≤n,則轉(zhuǎn)到步驟(3),否則停止。例3.8.3解按照Warshall算法，從M出發(fā)，只要遵循“置行查列遍尋真(1),見真行上析R當今(i),行推列移下右再，行窮列盡閉包成(便可直接求得M。禁煙教案而后的每后一次循環(huán)重復(fù)操作，均在前一次操作結(jié)果的矩陣M上進行。置當今行為第1行，查看第1列中1,對有1的行進行改寫，改寫方法是：將當今行第一行與第一行各對應(yīng)元素進行邏輯加，仍記于第一行：;第二列中r.=1,將第二行與第一行各對應(yīng)元素進行邏輯加，仍記于第一行：置當今行為第3行，重復(fù)上述操作并結(jié)束。對本例，i=3時，第三列中r=1,r=1,r=1,將第三行分別與第一行、第二行、第三行各對應(yīng)元素進行邏輯加仍分別記于第一行、第二行、第三行：得R+={(a,a}),(a,b},(a,c},(b,c>,結(jié)果與例3.8.2一致。禁煙教案A→B,B→De,D→Bf個字符恰為x,。說明每個字母連續(xù)應(yīng)用上述規(guī)則可j解J從一種性質(zhì)的閉包關(guān)系出發(fā)，求取另一種性質(zhì)的閉包關(guān)系，具有以下定理3.8.4設(shè)R是集合X上的二元關(guān)系，則XX(3)留作練習(xí)請讀者自證。3.9等價關(guān)系與相容關(guān)系本節(jié)討論兩類特殊關(guān)系-等價關(guān)系與相容關(guān)系。在討論之前，我們先引進兩個概念-集S是對A的某種分類的集合S是對A的某種分類的集合合、S、表示文科學(xué)生全體的集合；若按年級分類，則有,其中S(j=1,2,3,4)表示該大學(xué)j年級學(xué)生全體的集合；若按系分類，則有2j定義3.9.1設(shè)A是非空集合，A的子集的集合S={A,A,…,A},都是非空集合； S={{a,b},{b,c},hxrwida},Q={D={{a,d},{b,c}},G={{a,bE={{a},,{c},xrwuryv},F={{a,是劃22交定理3.9.1設(shè)S={A,A,…,A}與S={B,B,…,B}是同一集合X的兩種劃22定義3.9.3給定X的任意兩個劃分S={A,A,…,A}若對于每一個A均有B,使A≤B(i=1,2,…r;k=1,2,…t),k與S={B,B,…,B},22若還有S≠S,2定理3.9.2證明設(shè)S2任何兩種劃分的交叉劃分，都是原來各劃分的一種加細。={A,A,…,A}與S,={B,B,…,B}的交叉劃分為T,對T中任意元j1Ij23.9.2等價關(guān)系與等價類1.等價關(guān)系定義3.9.4設(shè)R為定義在集合A上的一個關(guān)系，若R是自反的、對稱的和傳遞的，例3.9.1(1)平面上三角形集合中，三角形的相似關(guān)系是等價關(guān)系。(3)一群人的集合中姓氏相同的關(guān)系也是等價關(guān)系。(4)設(shè)A是任意非空集合，則A上的恒等關(guān)系1和全域關(guān)系E均是A上的等價關(guān)驗證R是A上的等價關(guān)系。關(guān)系圖如圖3-9所示。圖3-9關(guān)系矩陣中，對角線上的所有元素都是1,關(guān)系圖上每個結(jié)點都有自環(huán)，說明R是自反的。關(guān)系矩陣是對稱的，關(guān)系圖上任意兩結(jié)點間或沒有弧線連接，或有成對弧出現(xiàn)，故R是對稱的。從R的序偶表示式中，可以看出R是傳遞的。故R是A上的等價關(guān)系。(2)若a=b(modk),a-b=kt(t為整數(shù)),則b-a=-kt,所以，(3)若a=b(modk),b=c(modk),則a-b=kt,b-c=ks(t,sa-c=a-b+b-c=k(t+s),所以，a=c(modk),R是傳遞的。2.等價類定義3.9.5設(shè)R是集合A上的等價關(guān)系，對任何a,b∈A,若aRb,則稱a與b等價。對任何a∈A,集合A中等價于a的所有元素組成的集合稱為以a為代表元的(A關(guān)于等價關(guān)系R的)等價類(EquivalenceClass),記作[a]。即由等價類的定義可知是非空的，因為aRa,。因此，任給集合A及其上的等價關(guān)系R,必可寫出A上各個元素的等價類。例如，在例3.9.2中，A的各個元素的例3.9.4設(shè)I是整數(shù)集合，R是模3同余關(guān)系，即解例3.9.3已證明整數(shù)集合上的模k同余的關(guān)系是等價關(guān)系，故本例中由I的元素從本例可以看到，在集合I上模3同余等價關(guān)系R所構(gòu)成的等價類有：禁煙教案定理3.9.3設(shè)給定集合ARR上的等價關(guān)系R,對于a,b∈A有aRb當且僅當,即定義3.9.6集合A上的等價關(guān)系R,其所有等價類的集合稱作A關(guān)于R的商集例如，例3.9.2中，商集：我們注意到商集,且任意兩個等價類的交為φ,于是定理3.9.4集合A上的等價關(guān)系R,決定了A的一個劃分，該劃分就是商集%。為證定理，我們需要證明非空集合A在其上的等價關(guān)系R下形成的等價類的全體的集禁煙教案(1)每一等價類都是A的子集，A中任一元素均屬于某一等價類，即等價類全體的并集是A;(2)不同的等價類之間交是空集。證明Va∈A,因為,所以，,從而(1)得證。為證明(2),用反證法：由對稱性得cRb,再由傳遞性得aRb,據(jù)定理3.9.3,必有,這與題設(shè)矛盾，(2)得證。所以，是A的對應(yīng)于R的一個劃分。定理3.9.5是集合A的一個劃分，則存在A上的一個等價關(guān)系R,使得S是A關(guān)于R的商集。..。由定理3.9.5可知：由集合A的劃分S={S,S,…,S}所確定的A上的等價關(guān)系R定理3.9.4和定理3.9.5說明：非空集合A上的等價關(guān)系與A的劃分一一對應(yīng)。例3.9.5設(shè)A={a,b,c,d,e}的劃分S={{a,b},{c},{d,e}},試由劃分S確定A上的一個等價關(guān)系R口定理3.9.6設(shè)R和R.為非空集合A上的等價關(guān)系，則222即,則對,使得,故3.9.3相容關(guān)系定義3.9.4給定集合A上的關(guān)系R,若R是自反的、對稱的，則稱R是A上的相A={cat,teachercolddeskknifebycatteachercolddeskknifeR的關(guān)系圖如圖3-10所示。圖3-10R的關(guān)系矩陣由于相容關(guān)系是自反和對稱的，因此，其關(guān)系矩陣的對角線元素都是1,且矩陣是對同理，在相容關(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-11定義3.9.5設(shè)R是集合A上的相容關(guān)系，C≤A,如果對于C中任意兩個元素a,a有aRa,就稱C是由相ConsistentClass對于前三個相容類，都能加進新的元素組成新的相容類，而后兩個相容類，加入任一新元素，就不再組成MaximalConsistentClass定義3.9.6設(shè)R是集合A上的相容關(guān)系，不能真包含在任何其它相容類中的相容類，RRR若C.為最大相容類，顯然它是ARRR有相容關(guān)系。而在A-C。中沒有任何元素與C。所有元素有相容關(guān)系。RR根據(jù)最大相容類的定義，它可以從相容關(guān)系R的簡化關(guān)系圖求得，具體方法是(1)在相容關(guān)系R的簡化關(guān)系圖中，每一個最大完全多邊形的頂點集合，就是一個最大相容類。所謂完全多邊形(CompletePolygon),就是其每個頂點都與其它頂點連接例3.9.7由例3.9.6中相容關(guān)系R的簡化關(guān)系圖3-11可得其全部最大相容類為：定理3.9.7設(shè)R是集合A上的相容關(guān)系，C是一個相容類，那么必存在一個最大相R圖3-12R=A×AUA×AU…UA×AJR=((1,1}.(12>,(1.3},(2,1,(2,2>,(2,3>,(3,1},(3,2},(3,3>,(3,4>,(4,3),(4,4習(xí)題3.92.把n個元素的集合劃分成兩個分塊，共有多少種不同的方法?3.已知X及其關(guān)系R如下，試說明R是等價關(guān)系，并指出其等價類。5.證明：(1)設(shè)R是X上的關(guān)系。對于x,x,x∈X而言，如xRx且xRx蘊含jkiik3.10.1偏序關(guān)系的定義