離散數(shù)學(xué)課本習(xí)題

c0的整倍數(shù)的集合。C={1，2，3}E={2x|x∈I}a)b)=c){}d)={}e){a,b}{a,b,c,{a,b,c}}f){a,b}={a,b,c,{a,b,c}}g){a,b}{a,b,{a,b}}h){a,b}={a,b,{a,b}}b){1，{2，3}}c){{1，{2，3}}}1/152/15d){}e){,{}}f){{1，2}，{2，1，1}，{2，1，1，2}}g){{，2}，{2}}a){a，}b){1，}c){x,y,z}d){，a,{a}}e)p({})10、設(shè)p(A)=p(B)。證明A=B。1.設(shè)U={1,2,3,4,5},A={1,4},B={1,2,5},C={2,4}。試求下列集合：a)A~B；b)(AB)~C；c)~(AB)；d)~A~B；e(A–B)–C；f)A–(B–C)；g)(AB)C；h)(AB)(BC)2.設(shè)A={n|n=I+且n<12},B={n|n=I+且n8},C={2n|n=I+},D={3n|n=I+}且E={2n-1|n=I+}試bc){10}；b)A(B-A)=;c)A(B-A)=AB;dA–(BC)=(A–B)(A–C)；e)A–(BC)=(A–B)(A–C)；f)A–(A–B)=AB；g)A-(B-C)=(A-B)(AC)。4.證明aAB僅當(dāng)AB=；b)AB=BA；c)(AB)C=A(BC)；d)A(BC)=(AB)(AC)；e)(BC)A=(BA)(CA)。3/156.給出下列各式成立的充分必要條件，并加以證明。a(A-B)同(A-C)=A;c)(A-B)后(A-C)=A;d(A-B)后(A-C)=A;e)(A-B)中(A-C)=A;h)A-B=B;i)A-B=B-A;j)A中B=A；k)p(A)同p(B)=p(A同B);a)p(A)同p(B)堅(jiān)p(A同B);b)p(A)后p(B)=p(A后B)。8.試求出同p和后p，其中p為：a){{氣}}；b){氣，{氣}}；c){{a},,{a,b}}。0ii+i0innnxxxwwiwwA=A，我們稱(chēng)A和A分別為集合序列A,A,A,i012 a)A為由一切屬于無(wú)限多個(gè)A的元素組成的集合；ib)A為由一切屬于“幾乎所有”的A的元素組成的集合。i4/154f)任意三個(gè)相鄰整數(shù)的立方和能被9整除；nF=00F=11n倒。規(guī)定每人每次可扳倒1至m根，且扳倒最后一根直立的大頭針者為獲勝者。試證明：mnn獲勝。數(shù)i≥i0及j≥j0，P(i,j)皆真。5/15c)(B×A)2用反例推翻下列命題：aA∪B)×(C∪D)=(A×C)∪(B×D)b)(A∩B)×(C∩D)=(A×C)∩(B×D)c)(A－B)×(C－D)=(A×C)－(B×D)dABCDAC(B×D)3、如果B∪CA，則(A×B)－(C×D)=(A－C)×(B－D)。這個(gè)命題對(duì)嗎？如果對(duì)，則給予證明；如果不對(duì)，則舉出反例。f)4、證明：若x=C且y=C，則<x,y>=p(p(C))。6、把三元偶<a,b,c>定義為{{a},{a,b},{a,b,c}}合適嗎？說(shuō)明理由。7、為了給出序偶的另一定義，選取兩個(gè)不同集合A和B(例如取A=，B={})，并定義<a,b>={{a,A},{b,B}}。證明這個(gè)定義的合理性。第二章二元關(guān)系3、設(shè)R和R都是從集合A到集合B的二元關(guān)系。證明a)既是自反的，又是反自反的；b)既不是自反的，又不是反自反的；c)既是對(duì)稱(chēng)的，又是反對(duì)稱(chēng)的；d)既不是對(duì)稱(chēng)的，又不是反對(duì)稱(chēng)的。6、試判斷下面的論斷正確與否。若正確，請(qǐng)加以證明；若不正確，請(qǐng)給出反例?；騻鬟f的)。y6/15R2.對(duì)圖給出的集合A={1,2,3}上的十二個(gè)二元關(guān)系的關(guān)系圖，寫(xiě)出相應(yīng)的關(guān)系矩陣，并指具有的性質(zhì)。LDLD關(guān)系圖，并寫(xiě)出它們的4.設(shè)R為任意的二元關(guān)系。證明7/15試求M，M，M，M及M。IAA上的恒等關(guān)系，R為A上的任意二元關(guān)系。證明a)R是自反的，當(dāng)且僅當(dāng)IAR；cRRR1；dR是反對(duì)稱(chēng)的，當(dāng)且僅當(dāng)RR-1=IA；e)R是傳遞的，當(dāng)且僅當(dāng)RoRIA。10、如果集合A上的二元關(guān)系R既是自反的，又是傳遞的，則R2=R。C8/157、設(shè)R為集合A上的二元關(guān)系，試證明：c)(R*)*=R*；RA1a){<i,j>|i,j=I且i·j>0}；b){<i,j>|i,j=I且i·j≥0且i與j不同時(shí)為0}；c){<i,j>|i,j=I且i≤0}；d){<i,j>|i,j==I且i·j≥0}；e){<i,j>|i,j=I且i|j}；f){<i,j>|i,j=I且有x=I使10x≤i≤j≤10(x+1)}；g){<i,j>|i,j=I且|i－j|≤10}；i){<i,j>|i,j=I且有x=I使10x<i<10(x+1)}；3、設(shè)集合A上的二元關(guān)系R是自反的。證明R為等價(jià)關(guān)系的充要條件是：若<a,b>,<a,c>=R,則<b,c>=R.試證明集合A上的二元關(guān)系R為A上的等價(jià)關(guān)系，當(dāng)且僅當(dāng)R是自反的和循環(huán)的。19/15是集合A∩B的劃分。11、設(shè)A為恰含n個(gè)元素的非空有限集，則有多少個(gè)不同的A上的等價(jià)關(guān)系？其中秩為22、畫(huà)出下列集合上的整除關(guān)系的哈斯圖。a){1,2,3,4,6,8,12,24}；b){i|iI且1≤i≤14}；c){i|iI且5≤i≤20}；ssss4、設(shè)R是集合A上的二元關(guān)系。證明：a)半序關(guān)系的逆關(guān)系仍然是半序關(guān)系；b)全序關(guān)系的逆關(guān)系仍然是全序關(guān)系；c)良序關(guān)系的逆關(guān)系未必是良序關(guān)系；7、舉出滿(mǎn)足下列條件的半序結(jié)構(gòu)<A,≤>的實(shí)例。a)<A,≤>為全序結(jié)構(gòu)，且A的某些非空子集無(wú)最小元。b)<A,≤>不是全序結(jié)構(gòu)，且A的某些非空子集無(wú)最大元。c)A的某些非空子集有下確界，但無(wú)最小元。d)A的某些非空子集有上界，但無(wú)上確定界。0/1512、I+在上定義二元關(guān)系R如下：8、設(shè)<A,≤>為半序結(jié)構(gòu)。證明A的每個(gè)非空有限子集都至少有一個(gè)極小元和極大元。9、設(shè)<A,≤>為全序結(jié)構(gòu)。證明A的每個(gè)非空有限子集都有一個(gè)最大元和最小元12、I+在上定義二元關(guān)系R如下：1212112212121212112212121212112212nRm當(dāng)且僅當(dāng)f(n)<f(m),或f(n)=f(m)且n≤m其中f(n)表示n的不同素因子的個(gè)數(shù)。證明<I+,R>為良序結(jié)構(gòu)。第三章cxyxyRyx2、下列集合能定義部分函數(shù)嗎？如果能，試求出它們的定義域和值域。a){<1,<2,3>>,<2,<3,4>>,<3,<1,4>>,<4,<1,4>>}；b){<1,<2,3>>,<2,<3,4>>,<3,<3,2>>}；c){<1,<2,3>>,<2,<3,4>>,<1,<2,4>>}；d){<1,<2,3>>,<2,<2,3>>,<3,<2,3>>}；1212123、設(shè)A為集合。若對(duì)任意s,s=p(A)皆令f(s,s)=s∩s，則f是從p(A)121212CfD寫(xiě)出f的全部序偶。c)有多少個(gè)和f具有相同的定義域和值域的函數(shù)g:A2→I?試證明a)f(99)=91；b)f(x)=91，其中0≤x≤100。0,h(x)=x。試求fof,hog,goh及它們的定義域和值域。3、對(duì)于下面的函數(shù)f，確定i)f是否為內(nèi)射、滿(mǎn)射和雙射；a)f:R→Rf(x)=2xs={1}b)f:N→N×Nf(n)=<n+n+1>s={<2,2>}c)f:N→Nf(n)=2n+1s={2,3}d)f:I→Nf(x)=|x|s={1,0}e)f:[0,1]→[0,1]f(x)=2/x+1/4s=[0,1/2]f)f:[0,∞]→Rf(x)=1/(1+x)s}f(x)=xah)f:(0,1)→(0,∞)2/15f(x)=1/x4、設(shè)n∈I+，f:A→A。證明：如果f是內(nèi)射(滿(mǎn)射，雙射)，則fn也是內(nèi)射(滿(mǎn)射，雙射)。a)fof=fb)fof=IAc)fofof=IAa)找出它們的一個(gè)共同的左逆。fABnAff逆。2、用特征函數(shù)求下列各式成立的充分必要條件。dA∩B=A∪B。aA=R,B=(0,∞)；c)A=[0,1),B=(1/4,1/2]；d)A=[0,1],B=(0,1)。4、證明在n+1個(gè)小于等于2n的不同正整數(shù)中必有兩數(shù)互素，其中n≥1。7天準(zhǔn)備考試，并決定復(fù)習(xí)60小時(shí)，每天至少用1小時(shí)，3/158、求下列集合的基數(shù)，并加以證明。002.寫(xiě)出圖抽象數(shù)學(xué)定義。3.證明在n階簡(jiǎn)單有向圖中，完全有向圖的邊數(shù)最多，其邊數(shù)為n(n-1)。5.在一次集會(huì)中，相互認(rèn)識(shí)的人會(huì)彼此握手。試證明與奇數(shù)個(gè)人握手的人數(shù)是偶數(shù)。6.證明圖的兩個(gè)圖同構(gòu)。7.證明：在任意六個(gè)人中，若沒(méi)有三個(gè)人彼此都認(rèn)識(shí)，則必有三個(gè)人彼此都不認(rèn)識(shí)。8.證明圖的兩個(gè)圖不同構(gòu)。10.證明任何階大于1的簡(jiǎn)單無(wú)向圖必有兩個(gè)結(jié)點(diǎn)的度相等。11.設(shè)n階無(wú)向圖G有m條邊，其中nk個(gè)結(jié)點(diǎn)的度為k，其余結(jié)點(diǎn)的度為k+1，證明1.畫(huà)出K4的所有不同構(gòu)的子圖，并說(shuō)明其中哪些是生成子圖，并找出互為補(bǔ)圖的生成子GVEVVGV3.畫(huà)出圖的兩個(gè)圖的交、并和環(huán)和。 5.我們稱(chēng)與其補(bǔ)圖同構(gòu)的簡(jiǎn)單無(wú)向圖為自補(bǔ)圖。證明每個(gè)自補(bǔ)圖的階能被4整除或被44/151.考慮圖.e)求出該圖的直徑。f)找出該圖的所有回路。2.證明圖中的基本路徑必為簡(jiǎn)單路徑。3.考慮圖b)找出所有強(qiáng)分支，單向分支，弱分支。4.設(shè)v1,v2,v3是任意無(wú)向圖(有向圖)G的三個(gè)任意節(jié)點(diǎn)，以下三公式是否成立？如果成立給出證明，如果不成立舉出反例。5.證明有向圖的每個(gè)節(jié)點(diǎn)和每條邊恰處于