【計(jì)算機(jī)】南理工離散數(shù)學(xué)A卷附答案

南京理工大學(xué)課程考試試卷(學(xué)生考試用)課程名稱：離散數(shù)學(xué)A學(xué)分：45大綱編號(hào)試卷編號(hào)：考試方式：閉卷滿分分值：100考試時(shí)間：120分鐘組卷日期：20XX年1月2日組卷教師(簽字)朱保平審定人(簽字)金忠學(xué)生班級(jí)：計(jì)算機(jī)學(xué)院09級(jí)(6分)試把下列語(yǔ)句翻譯為謂詞演算公式(1)某些人喜歡所有明星；(2)并非“所有人均喜歡電腦游戲”。(6分)把下列數(shù)論語(yǔ)句化為特征函數(shù)%為平方數(shù)且％為偶數(shù)；%是y的倍數(shù)或%小于等于y。(6分)已知公理：(A)(PaQ)TP(PaQ)TQ(PT(QT(PaQ))(D)」「PTP及分離規(guī)則和代入規(guī)則。試用假設(shè)推理證明下面公式為本系統(tǒng)中的定理(PTQ)T((「「PaR)T(QaR))(8分)試把函數(shù)h(%1,%2,%3,%J=f(g1(%1,b),%5,g2(%2,%3),4)(其中b為自然數(shù))化為(m,n)標(biāo)準(zhǔn)迭置。(6分)已知知識(shí)的符號(hào)表示3%(P(%)aVy(D(y)TL(%,y)))V%(P(%)TVy(Q(y)T「L(%,y)))結(jié)論：V%(D(%)T「Q(%))試用霍恩子句邏輯程序證明之。(8分)已知：A={{①},{1}},B={{〃}}。試求2a；B義2a。（6分）已知A,B,C是三個(gè)非空集合，f為A到B的映射，g為B到C的映射。證明：如果gf是A到C的雙射，則f為A到B的單射，g為B到C的滿射。（6分）（G,?）是群，（”,?）是（G,?）的子群，?是G上的二元關(guān)系，對(duì)于任意的a,bgG,a?b0b-i-agH。試證明（1）?為G上的等價(jià)關(guān)系；（2）對(duì)于VagG，有[a]=a?H。1 ”,、（8分）已知Q*=Q-{0},Q是有理數(shù)集，Vm,ngZ,n*m=7nm，證明（Q*,*）是群。（6分）G=（V,E）是一個(gè)簡(jiǎn)單連通圖。且G是一個(gè)二部圖（偶圖），相應(yīng)地頂點(diǎn)分類為{匕,V2}，且I匕閨匕I。證明G不是哈密爾頓圖。（8分）（1）畫一個(gè)10個(gè)頂點(diǎn)歐拉圖但非哈密爾頓圖，它是簡(jiǎn)單無(wú)向圖，有奇數(shù)條邊；（2）畫一個(gè)10個(gè)頂點(diǎn)哈密爾頓圖但不是歐拉圖，它是簡(jiǎn)單無(wú)向圖，有偶數(shù)條邊。（6分）設(shè)G=（V,E）是連通圖，且egE。證明：e為G的割邊（即拿去此邊后，G變成不連通的兩部分）當(dāng)且僅當(dāng)e在G的每棵生成樹(shù)中。（6分）設(shè)（H,*）是群（G,*）的子群，如果A={xIxgG,x*H=H*x}，證明（A,*）是（G,*）的子群。（8分）T是一棵樹(shù)。試證明T為二部圖；…—n2（2）若G=（V,E）是二部圖，且IVI=n,IEI=m，試證明m<--o4（6分）G=（V,E）是一個(gè)簡(jiǎn)單無(wú)向圖。若IVI>11,則G或G是非平面圖。南京理工大學(xué)課程考試試卷答案及評(píng)分標(biāo)準(zhǔn)課程名稱： 離散數(shù)學(xué) 學(xué)分4.5分 教學(xué)大綱編號(hào)：06022104-試卷編號(hào)：考試方式： 閉卷 滿分分值：」W—考試時(shí)間：」20—分鐘.（共6分，每小題3分）TOC\o"1-5"\h\z解（1）3x（P（x）A（Vy（S（y）fL（x，y）））） 3分（2）「Vx（P（x）f（Vy（G（y）fL（x，y））））或「Vx（P（x）f（3y（G（y）aL（x，y）））） 3分注：本大題為基本題，考核自然語(yǔ)言的謂詞表示方法。.（共6分，每小題3分）（1）N2（N2（x&[%良]2）+N2rs（x,2）） 3分（2）N2rs（x,y）?（N2（x&y）=min（N2rs（x,y）,N2（x&y）） 3分注：本大題為基本題，考核特征函數(shù)的表示方法。.（共6分）證明：（1）PfQ 前提假設(shè)（2）「「PaR 前提假設(shè)（「?「?PaR）—f「1-1P 公理（A）（「「PaR）fR 公理（B）（5）「「P （2）（3）分離（6）R （2）（4）分離（7）「「PfP 公理（D）（8）P （5）（7）分離（9）Q （1）（8）分離（10）（Qf（Rf（QaR）） 公理（C）（11）Rf（QAR）） （9）（10）分離（12）QaR （6）（11）分離由假設(shè)推理證明過(guò)程的定義知PfQ,「「PAR|-QaR由推理定理知（PfQ）f（（「「PaR）f（QaR））注：本大題為基本題，考核命題演算的假設(shè)推理系統(tǒng)。4.（共8分）h（xjx2,x3,xJ=f（g1a41,SbOI41），144,g2（142,143）,S40141）（xjx2,x3,x5）——8分

.(6分)證明：P(a)L(a,y)-D(y)-P(x),Q(yj,L(x,y1)D(b) 3分{a/x}(1)(3)歸結(jié){b/y1}(5)(6)歸結(jié) 3分{a/x}(1)(3)歸結(jié){b/y1}(5)(6)歸結(jié){b/y}(2)⑺歸結(jié)(4)(8)歸結(jié) 3分-Q(y1),L(a,yJ-L(a,b)—D(b)0注：本大題為基本題，考核命題演算的歸結(jié)推理系統(tǒng).(共8分，每小題4分)解：(1)2a=曲，4{{1}},{仲}}}-------4分Bx2a={({a}g),({a},A),({a},{{1}}),({a},{{6}})}注：本大題為基本題，幕集和積集的定義.(6分)假設(shè)g。f是A到C的雙射。TOC\o"1-5"\h\z先證f是A到B的單射。采用反證法。如果f不是A到B的單射，則存在％Wx3,使得f(x)=f(x)，于是g(f(x))=g(f(x))，即g。f(x1)=g。f(x2),這與g。f是單1 2 1 2射矛盾，即證得f為A到B的單射。 3分再證g為B到C的滿射。由g。f的滿射性質(zhì)，對(duì)于任意的ceC，存在aeA，使得g。f(a)=c，即有f(f(a))=c。記b=f(a)，即有g(shù)(b)=c，即證得g為B到C的滿射。 3分注：本大題為基本題，考核單射和滿射的證明方法。.(共6分)證明：(1)對(duì)于任意的aeG，:a-1?a=eeH，丁a?a，故?是自反的。對(duì)于任意的a,beG,若a?b,則有b-1?aeH，.二(b-1?a)-1=a-1?beH，.二b?a，故?是對(duì)稱的。對(duì)于任意的a,b,ceG，若a?b,b?c,則有b-1?aeH且c-1?beH,/.(c-1?b)?(b-1?a)=c-1?aeH,「.a?c,即?是傳遞的。這樣，?是G上的一個(gè)等價(jià)關(guān)系。 3分(2)先證[a]=a?H。對(duì)于任意的xe[a],x?a,即有x-1?aeH,即存在

heH,x-i-a=h。/.x=a-h-1ga-H。故[a]ca?H。再證，a?Hc[a]。對(duì)于任意的yca?H，即有heH，使得y=a-h，于是，TOC\o"1-5"\h\za-1?y=h?H,/.a?y,ye[a]，故a?Hc[a]。綜上所述，[a]=a?H 3分注：本大題綜合題，考核等價(jià)關(guān)系，群、陪集的定義、集合相等的證明方法。.（8分）證明：（1）封閉性。對(duì)于Va,beQ*,a*b=iabeQ*。 2分7（2）結(jié)合律。對(duì)于Va,b,ceQ*,a*（b*c）=a⑤ibc=+abc=（a*b）*c 2分（3）幺元7。因?yàn)閂aeQ*,a⑤7=+a7=a=7⑤a 2分7（4）逆元。VaQ*，其逆元為49，因?yàn)閂aeQ*,a⑤好=+a的=7=?、輆 2分a a7a a注：本大題為基本題，考核群的定義。.（共6分）證明：不妨假設(shè)IV1I<IV2I，根據(jù)二部圖的定義知，從圖中去掉V1中的頂點(diǎn)后，得到IV2I個(gè)連通分支。因?yàn)樗玫降倪B通分支數(shù)目221大于所去掉的頂點(diǎn)數(shù)目211，即W（G-V1）=IV2I>IV1I,即哈密爾頓圖的必要條件得不到滿足，所以圖G不是哈密爾頓圖。注：本大題為綜合題，考核二部圖、哈密爾頓圖的必要條件等。（共8分，每小題4分）注：本大題為基本題，考察哈密爾頓圖和歐拉圖定義等。.（共6分）證：先證必要性。假定e為G的割邊。用反證法。如果e不是在G的每棵生成樹(shù)中，則存在G的一棵生成樹(shù)T，e不在T中。因?yàn)樯蓸?shù)T是連通的，而e不在T中表明拿去邊e后，圖G仍然連通，所以與e為G的割邊的假定矛盾。矛盾表明e在G的每棵生成樹(shù)中。 3分再證充分性。假定邊e是在G的每棵生成樹(shù)中。用反證法。如果e不是G的割邊，則從圖G中拿去此邊后所得到的子圖G1仍然連通。由子圖G1得到的生成樹(shù)也是圖G的生成樹(shù)，但該生成樹(shù)中不包含邊e，這與e是在G的每棵生成樹(shù)中的假定矛盾。矛盾表明e是G的割邊。注：本大題為綜合題，考核連通圖、生成樹(shù)、割邊等相關(guān)概念。13證：假設(shè)e是群G的幺元。顯然，有e*H=H*e=H,所以eeA,即A非空集。對(duì)于Va,beA，即有a*H=H*a,b*H=H*b。下面要證a*beA。先證(a*b)*HuH*(a*b)，對(duì)于Vxe(a*b)*H，存在heH，使得x=(a*b)*h。顯然x=(a*b)*h，因?yàn)閎*heb*H=H*b，所以存在heH，使得b*h=h*b。于是，x=a*(h*b)=(a*h)*b，所以存在i i i iheH，使得b*h=h*b。于是x=a*(h*b)=(a*h)*b，又因?yàn)閍*hea*H=H*a，所以存在heH，使得a*h=h*a，于是，x=(h*a)*b=h*(a*b)eH*(a*b)。 3分同理可證H*（a*b）u（a*b）*H。所以有H*（a*b）=（a*b）*H，即證得a*beA對(duì)于VaeA，即有a*H=H*a。下面要證a_1eA。先證a-1*HuH*a-1。對(duì)于xea-1*H，存在heH，使得x=a*%。顯然，x-1=h-1*a。因?yàn)閔-1eH，故x-1eH*a=a*H，所以存在々eH，使得x-1=a*々，于是x=h1T*a-1eH*a-1。同理可以證得H*a-1ua-1*H。所以有H*a-1=a-1*H，即證得a_】eA。 3分注：本大題為提高題，考察群、子群、陪集、集合的相等等原理。14.（共8分，每小題4分）（1）因?yàn)門是一棵樹(shù)，所以T中沒(méi)有回路，也可以說(shuō)T中回路長(zhǎng)度都為0（0為偶數(shù)），這樣根據(jù)二部圖的等價(jià)定義（即所有回路長(zhǎng)度均為偶數(shù)）知：T是二部圖。 ------4分TOC\o"1-5"\h\z（2）假設(shè)二部圖G的頂點(diǎn)分類為（V1V2）。不妨記n1=IV1l,n2=IV2l。顯然，n1+n2=n，而且n1<n1n2，于是m<n1n2<（"1+<）2=q 4分\o"CurrentDocument"4 4注：本大題為提高題，考核樹(shù)、二部圖等相關(guān)性質(zhì)。15（共6分）證明：用反證法。設(shè)G和G的