《離散數(shù)學(xué)》題庫大全及答案

1課程內(nèi)容涉及1．集合論部分：集合及其運算、支配集、覆蓋集、獨立集與匹配、帶權(quán)圖及其應(yīng)用3．代數(shù)結(jié)構(gòu)部分：代數(shù)系統(tǒng)的基本概念、半群與獨異點、群、環(huán)與域、格與布爾代數(shù)4．組合數(shù)學(xué)部分：組合存在性定理、基本的計數(shù)公式、組合計數(shù)方法、組合計數(shù)定理離散數(shù)學(xué)被分成三門課程進行教學(xué)，即集合論與圖論、代數(shù)結(jié)構(gòu)與組合數(shù)學(xué)、數(shù)理邏輯。教學(xué)方式以課堂講授為主,課后有書面作業(yè)、通過學(xué)校網(wǎng)絡(luò)教學(xué)平臺發(fā)布課件并進行師生交編輯本段相關(guān)文獻耿素云.離散數(shù)學(xué)習(xí)題集--數(shù)理邏輯與集合論分冊.北大出版社，離散數(shù)學(xué)習(xí)題輔導(dǎo)軟件命題邏輯教學(xué)軟件為離散數(shù)學(xué)領(lǐng)域的經(jīng)典教材,全世界幾乎所有知名的院校都曾經(jīng)使用本書作為教材.以我個人觀點看來,這本書可以稱之為離散數(shù)學(xué)百科.書中不但介紹了離散數(shù)學(xué)的理論和方法,還有豐富的歷史資料和相關(guān)學(xué)習(xí)網(wǎng)站資源.更為令人激動的便是這本書少有的將離散數(shù)學(xué)理論與應(yīng)用結(jié)合得如此的好.你可以看到離散數(shù)學(xué)理論在邏輯電路,程序設(shè)計,商業(yè)和互聯(lián)網(wǎng)等諸多領(lǐng)域的應(yīng)用實例.本書的英文版(第六版)當(dāng)中更增添了相當(dāng)多的數(shù)學(xué)和計算機科學(xué)家的傳記,是計算機科學(xué)歷史不可多得的參考資料.作為教材這本書配有相當(dāng)數(shù)量的練習(xí).每一章后面還有一組課題,把學(xué)生已經(jīng)學(xué)到的計算和離散數(shù)學(xué)的內(nèi)容結(jié)合在一起進行訓(xùn)練.這本書也是我個人在學(xué)習(xí)離散數(shù)學(xué)時讀的唯一的英文教材,實為一本值得推薦的好書。2《離散數(shù)學(xué)》題庫答案3、設(shè)有下列公式，請問哪幾個是永真蘊涵式?()答23456）6、命題“存在一些人是大學(xué)生”的否定是(是要死的”的否定是()。38、設(shè)個體域為整數(shù)集，則下列公式的意義是()。在哪個個體域中為真?()12、永真式的否定是()419、設(shè)P={x|(x+1)2<4且xeR},Q={x|5<x2+16且xeR},則下列命題哪個正確()20、下列各集合中，哪幾個分別相等()。22、判斷下列命題哪個為真?()527、A,B,C是三個集合，則下列哪幾個推理正確：-1。6-1。-1。<A,*>中，單位元是()，零元是()。7<A,*>中，單位元是()，零元是()；39、設(shè)〈G,*〉是一個群，則43、群<G,*>的等冪元是()，有()個。44、素數(shù)階群一定是()群,它的生成元是()。46、<H,,*>是<G,,*>的子群的充分必要條件是()。答：<H,,*>是群或a，bG，a*bH，a-1H或a,bG，a*b-1H47、群＜A,*＞的等冪元有()個，是()，零元有()個。849、在自然數(shù)集N上，下列哪種運算是可結(jié)合的？()52、下列哪個偏序集構(gòu)成有界格()54、設(shè)G是一個哈密爾頓圖，則G一定是()。956、一個圖的哈密爾頓路是一條通過圖中()的路。59、n階無向完全圖K的邊數(shù)是()n263、下面給出的集合中，哪一個不是前綴碼()。64、n個結(jié)點的有向完全圖邊數(shù)是()，每個結(jié)點的度數(shù)是()。65、一個無向圖有生成樹的充分必要條件是()。74、任一有向圖中，度數(shù)為奇數(shù)的結(jié)點有(）（）（）（9、P→Q（P視R）喻Q（P喻Q）喻RB提(8)RSCP18）（3）R（12）QS（12）W（710）（13）X（811）（14）W^X（1213）（5）U（34）（5）R（24）（7）Q→S（56）（8）S（27）（9）Q→SCP28）（10）P→(Q→S)CP19）（5）P（34）提提16、PQ，QR，RSP（3）Q（12）17、用真值表法證明PQ(PQ)(QP)PPQPQFFTTFTFFTFFFTTTT（6）B（35）PP喻QQ四、設(shè)A,B,C是三個集合，證明：12、(A-B)(A-C)=ABCx(A-B)-C，有xA-B且xC，即xA，xB且xC。從而xA，xB-C，故xA-(B-C)。從而(A-B)-CA-(B-C)15、P(A)P(B)P(AB)（P(S)表示S的冪集）SP(A)P(B)，有SP(A)或SP(B)，所以SA或SB。16、P(A)P(B)=P(AB)（P(S)表示S的冪集）SP(A)P(B)，有SP(A)且SP(B)，所以SA且SB。從而SP(A)且SP(B)，故SP(A)P(B)。即P(AB)P(A)P(B)。(1)xy（xy=1）;(2)xy(xy=1);(4)xy（xy=0）;(6)xy（xy=x）;(7)xyz(x-y=z)（1）A={0,1,2}，B={0,2,4}，R={<x,（2）A={1,2,3,4,5}，B={1,2}，R={<x,y>|2x+y4且xA且yB};（3）A={1,2,3}，B={-3,-2,-1,0,1}，R={<x,y>||x|=|y|且xA且yB};4、對任意集合A,B，證明：若AA=BB，則B=B。222={<a,c,a,c>,<a,c,b,c>,<b,c,a,c>,<b,c,b,c>};,<A,a>,<A,b>}。（3）若AeB，且BeC，則AeC；（4）若AB，且BC，則AC；但AC。BC，但AC。(4)成立。因為AB,且BC，所以AC。AAxAIR，<x,x>R。即xRx，故R是自反的。Ax，yA，若<x,y>R，即<y,x>R-1。：R=R-1，<y,x>R。即yRx，故（1）<x，z>R。(ST)，則由合成關(guān)系的定義知yB，使得<x，y>R且R|R|A<10,3>,<10,5>,<5,10>,<4,6>,<6,4>,<4,8>,<8,4>,AR誘導(dǎo)的劃分為{{1,5},{2,4},{3,6}}。aaebcdf5,a9},{a2,a6,a10},{a3,a7,a11}。3526子群外，還有{e,a4},{e,a2,a4,a6}。-13352)=b·a4。454vb，ceSkl=ak+lvxeG，因為a是〈G，*〉的生成元，所以存在整數(shù)k，使得x=ak。2。a,bSa·b）2=(a·b)·(a·b)=((a·b)·a)·ba,bS，因為（a·b）2=a2·b2，所（1）aA,記b=a*a。因為*是可結(jié)合的，故有b*a=(a*a)*a=a*(a*a)=a*b。（2）a,bA,因為由（1a*(a*b*a)=(a*a)*(b*a)=a*(b*a),（3）a,b,cA,（a*b*c）*（a*c）=a*b*c）*a）*c=(a*(b*c)*a)*c且(a*c)*(a*b*c)=a*(c*(a*b*c))=a*(c*(a*b)*c))。故（a*b*c）*（a*c）=(a*(b*c)*a)*c=a*c且(a*c)*(a*b*c)=a*(c*(a*b)*c))=a*c，即（a*b*c）*（a*c）=(a*c)*(a*b*c)。-1)-1=(f(b)-1=(f(b·a))-1=((b·a)-1)--1-1=a-1-142、若群<G,＊>的子群<H,＊>滿足|G|＝2|H|，則<H,＊>一定是群<G,＊>-1-1對aG，hC(G)，記b=a·h·a-1。下證bC(G)。因為hC(G)，所以-1-1=h·(a·a-1)=hC(G)。-1?>是<S,?>e?e=e，eT，即T是S的非空子集。va,beT,<S，.>是可交換獨異點,：(a.b).(a.b)=((a.b).a).b=(a.(b.a)).b=（a.(a.b)）.b=((a.a).b).b=(a.a).(b.b)=a.b,即a.beT。由于p和m都是正整數(shù)，所以p=m。即｜ak|=──。vaeG，由封閉性及|G|=n可知a,a2,…,an,an+1中必有相同的元素，不妨設(shè)為m)；r=ak-mq=ak.a-mq=b.(am)-q。meH,且H<G，所以areH。d1nnm則1（4）若h為單一同態(tài)，則vaeG1，|h(a)|=|a|。(1)因為h(e).h(e)=h(e.e)=h(e)=e.h(e),所以h(e)=e。(2)va∈G，h(a).h(a-1)=h(a.a-1)=h(e)=e,h(a-1).h(a)=h(a-1.a)=h(e)=e,故h(a-1)=h(a)-1。(3)vc,d∈h(H),二a,b∈H，使得c=h(a),d=h(b)。故c.d=h(a).h(b)設(shè)|G|=n，vaeG，則|a|=m。令H={e,a,a2,…,am-1}。a.b=c。同理可得a.c=c.a=b,c.b=b.c=a,b.a=c。是k。-1故a,beG，從而a*beG。有設(shè)S關(guān)于*的單位元為(a,b)。根據(jù)*和單位元的定義，對(x,y)eS,有即ax=x,ay+b=y,xb+y=y對x,yeQ都成立。解得a=1,b=0。即ac=1,ad+b=0,cb+d=0。解得c=-,d=-（4）a∈G，h∈G，a?h?a-1H。1H?aH。(3)(4)類似于（2）(3)的證明。-1?a)=(a?h?a-1)?a。由于a?h?a-1∈H，所以b∈H?a。即a?HH?a。-1)即H?aa?H。63、在半群<G,*>中，若對a,bG，方程a*x=b和y*a=b都有惟一Rb*e=(y*a)*e=y*(a*e)=y*a=b。Le*b=e*(a*x)=(e*a)*x=a*x=b。從而在半群<G,*>中,關(guān)于運算*存在單位元，記為e。:d=e。:-1=b-1-1-1eH,b-1eK，即ceKH。從而HK堅KH。vceKH，則存在aeH,beK,使得c=b·a。因為c=（a-1·b-1）-1。-1-1=(a-1=b-1-1對vaeHK，有heH，keK，使得a=h·k。因為a=h·k=(h·k·h-1)·h，且K=(c*b)2*a*bn2=(c*b)2*(a*b)*bn3=(c*b)2*(c*b*a)*bn3=(c*b)3*a*bn3=…=(c*b)n*a,…=b*(a*c)m,69、設(shè)(L,≤)是格，若a,b,ceL，a≤b≤c，則70、在布爾代數(shù)中，證明恒等式a①(a,*且僅當(dāng)a=a=…=a。72、在布爾代數(shù)中，證明恒等式(a*c)①(a,*b)①(b*c)=(a*c)①(a,*b)((a*c)①(a,*b))*(b*c)=((a*c)*(b*c))①((a,*b)*(b*c))=(a*b*c)①(a,*b*c)=(a①a,)*b*c=1*b*c=b*c,故b*c<(a*c)①(a,*b)，從而(a*c)①(a,*b)①(b*c)=(a*c)①(a,*b)。73、在布爾代數(shù)中，證明恒等式(a*b)①(a,*c)①(b,*c)=(a*b)①ca*c<b*d(a*c)*(b*d)=((a*c)*b)*d=(b*(a*c))*d=((b*a)*c)*d=a*(c*d)=a*c，所以a*c<b*d。n10..5.2.1.45.9..9.35..35.(a①b,)*(b①c,)*(c①a,)=(a,①b)*(b,①c)*(c,①a)=(a*b*c)①(a*b*a,)①(a*c,*a,)①(a*c,*c)①(b,*b*c)①(b,*c,*c)①(b,*c,*a,)①(b,*b*a,)=(a*b*c)①(b,*c,*a,)，=(a,*b,*c,)①(a,*b,*a)①(a,*c*c,)①(a,*c*a)①(b*b,*c,)①(b*b,*a)①(b*c*c,)①(<I[a,b]，≤>是<L，≤>的子格。dcba.db.a..c81、格<L,,>是模格a,b,cL，有83、證明：在有補分配格中，每個元素的補元一定惟一。84、設(shè)<L,,>是格，則L是分配格當(dāng)且僅當(dāng)a,b,cL，有(ab)ca(bc)設(shè)L是分配格。對a,b,cL，有85、設(shè)<S,,⊙,′,0,1>是一布爾代數(shù)，則<S,＋>是一個交換群，其中+，：設(shè)T=<V,E>是任一棵樹，則|V|=n，且|E|=n-1。veV由歐拉握手定理可得Σdeg(v)=2|E|=2n-2。veVveV解kkkk設(shè)|V|=n，則|E|=n-1。由歐拉握手定理可得Σdeg(v)=2|E|=2n-2。veVΣdeg(v)>2n>2n-2。veV由歐拉握手定理可得Σdeg(v)=2|E|=2n-2。veVΣdeg(v)>2(n-1)+1>2n-2,veV則m<k(n-2)／(k-2)。由已知對任一feF,deg(f)>k。feFk所以m<k(n-2)／(k-2)。由公式Σdeg(f)=2|E|可得fF2記|V|=n,|E|=m,|F|=k。由歐拉握手定理得Σdeg(v)=2|E|得5n<2m。所以對每個面f,deg(f)3。fF-6。:feF3:|E|<3|V|－6。feF,d(f)=3。所以對任一feF，deg(f)之3。再由公式Σdeg(f)=2|E|，Σdeg(f)=24。feFfeF101、設(shè)G=<V,E>是n個頂點的無向圖(n>2)，若對任意u,veV，有而G中的任一頂點至多只和G中的頂點鄰接。任取ueV(G),veV(G),這20人圍成一圓桌入席。有沒有可能使任意相鄰而坐的兩個人都是朋1A3=||，A4=||1..v4.v2.v.v31.....bd.e.f在這個無向圖中d(a)=3,d(b)=6,d(c)=4,d(d)=3,d(e)=0,d(f)=0。befefa?bd?e?f106、求下列無向圖的子圖、生成子圖、由邊集誘導(dǎo)的子圖和由頂點cbdaabdbbc由邊集{(a,b),(a,c),(a,d),(b,ddafbf●??d?a471c?b??f?3164324v5Sl(v2)l(v3)l(v4)l(v5)l(v6)tl(t){v1}34v23v34v56v47v69ddaebc則0|0|00000002004|||||||||0430001ΣiiΣdeg(v)=2|E|vEV可得2|E|=k+4+3+12=k+19。再由于它是一棵樹，故1