《離散數(shù)學(xué)》期末考試題22222

1、?離散數(shù)學(xué)?期末測(cè)試題(A)、填空題(每題3分,共15分)1.設(shè)A=a,b,cA-B=(),P(A)=(2.集合A=a,b,c,其上可定義(個(gè)封閉的3元運(yùn)算.B=a,b,c,c,那么A=B=().)個(gè)封I的1元運(yùn)算,()個(gè)封閉的2元運(yùn)算,()3 .命題公式(p八q)1的對(duì)偶式為().4 .所有6的因數(shù)組成的集合為().5 .不同的5階根樹(shù)有()棵.二、單項(xiàng)選擇題(每題3分,共15分)1 .設(shè)A,B是集合,假設(shè)AB=A,那么(A)B=._(B)A=._(C)A-B=._(D)A-B二A2 .謂詞公式Vx(P(x)T三yQ(y)AR(x)中量詞Vx的轄域?yàn)?A)-x(P(x)yQ(y)R(x)(B

2、)P(x)yQ(y)(C)(P(x)T3yQ(y)aR(x)(D)P(x)T三yQ(y)和R(x)3 .任意6階群的子群的階一定不為(A)4(B)6(C)2(D)34 .設(shè)n是正整數(shù),那么有限布爾代數(shù)的元素個(gè)數(shù)為n2(A)2n(B)4n(C)2(D)n5 .對(duì)于以下序列,可構(gòu)成簡(jiǎn)單無(wú)向圖的度數(shù)序列為(A)3,3,4,4,5(B)0,1,3,3,3(C)1,1,2,2,3(D)1,1,2,2,2三、判斷題(每題3分,共15分)：正確打“錯(cuò)誤打“X.1 .設(shè)f:NTNMN,f(x)=(x,x+1),那么f是滿射.()2 .5男5女圓桌交替就座的方式有2880種.()3 .設(shè)(L,與是格,對(duì)于x,y

3、,zWL,假設(shè)xy=XZ且x+y=x+zJUy=z.()4 .任何樹(shù)都至少2片樹(shù)葉.()5 .無(wú)向圖G有生成樹(shù)的充要條件是G為連通圖.()四、(10分)設(shè)A,B,C和D是集合,證實(shí)(AB)m(CD)=(AmC)(BmD),并舉例說(shuō)明上式中不能將J改為=.五、(15分)設(shè)N是自然數(shù)集合,定義N上的關(guān)系R如下：(x,y)wRux+y是偶數(shù),1 .證實(shí)R是N上的等價(jià)關(guān)系.2 .求出N關(guān)于等價(jià)關(guān)系R的所有等價(jià)類(lèi).3 .試求出一個(gè)N到N的函數(shù)f,使得R=(x,y)|x,yN,f(x)=f(y).六、(10分)在實(shí)數(shù)集合R中證實(shí)以下推理的有效性：由于R中存在自然數(shù),而所有自然數(shù)是整數(shù),所以R中存在整數(shù).七

4、、(10分)設(shè)R是實(shí)數(shù)集合,令G=(a,b)|a,bwR,a=0,定義G上的運(yùn)算如下：對(duì)于彳壬意(a,b),(c,d)WG,(a,b)(c,d)=(ac,ad+b),證實(shí)(G,)是非Abel群.八、(10分)假設(shè)簡(jiǎn)單平面圖G的節(jié)點(diǎn)數(shù)n=7且邊數(shù)m=15,那么G是連通圖,試證實(shí)之.?離散數(shù)學(xué)?期末測(cè)試題(A)參考答案一、1.A=B=a,a,b,b,c,c,AB=c,P(A)=a,b,c,a,b,c.39272.3,3,3.3. (pq)-0.4. -1,-2,-3,-6,1,2,3,6.5. 9.二、1(C);2(B);3(A);4(C);5(D).三、1(X);2(V);3(X);4(X);5

5、(V).四、證對(duì)于彳壬意(x,y)w(AB)m(CD),有xwAB且y亡CD,于是xwA,xB且ywC,y星D,進(jìn)而(x,y)亡A父C,(x,y嚴(yán)B父D,因此(x,y)三(AC)(B父D),所以(A-B)(C-D)(AC)-(BD).例如取A=B=a,b,C=c,D=d,這時(shí)A-B=0,進(jìn)而(A-B)m(CD)=0,而(AC)-(BD)=(a,c),(b,c)-(a,d),(b,d)=(a,c),(b,c),故(A-B)(C-D)=(AC)-(BD).五、證1.對(duì)于彳E意xwN,由于x+x=2x是偶數(shù),于是(x,x)wR,因此R是N上的自反關(guān)系.對(duì)于任意x,yWn,假設(shè)(x,y)wR,那么x+

6、y是偶數(shù),即y+x是偶數(shù),于是(y,x)wR,因此R是N上的對(duì)稱關(guān)系.對(duì)于任意x,y,zWN,假設(shè)(x,y)wR且(y,z)wR,那么x+y是偶數(shù)且y+z是偶數(shù),于是x+z=(x+y)+(y+z)2y是偶數(shù),進(jìn)而(x,z)wR,因此R是n上的傳遞關(guān)系.綜上所述,R是N上的等價(jià)關(guān)系.2.N關(guān)于等價(jià)關(guān)系R的所有等價(jià)類(lèi)為0r=0,2,4,6,.和1r=1,3,5,7,.3.令f:NTN,f(x)=0,x是偶數(shù)1,x是奇數(shù),顯然R=(x,y)|x,yN,f(x)=f(y).六、證令N(x):x是自然數(shù),Z(x):x是整數(shù),那么前提：xN(x),-x(N(x)Z(x)結(jié)論：xZ(x)構(gòu)造性證實(shí)如下：(1

7、)TxN(x)PN(c)ES(1)-x(N(x)Z(x)PN(c).Z(c)US(3)Z(c)T(2)(4)I(6) xZ(x)EG(5)七、證對(duì)于彳I意(a,b),(c,d)wG,有a,c#0,進(jìn)而ac#0,于是(ac,ad+b)wG,即“？是G上的代數(shù)(封閉)運(yùn)算.(2)結(jié)合律對(duì)于彳I意(a,b),(c,d),(e,f)wG,一方面有(a,b)(c,d)(e,f)=(ac,adb)(e,f)=(ace,acf+(ad+b)=(ace,acf+ad+b),另一方面有(a,b)(c,d)(e,f)=(a,b)(ce,cfd)=(ace,a(cfd)b)二(ace,acfadb),于是(a,b)

8、(c,d)(e,f)=(a,b)(c,d)(e,f).(3)單位元為(1,0)對(duì)于任意(a,b)wG,由于(1,0)(a,b)=(a,b+0)=(a,b)且(a,b)(1,0)=(a,a0+b)=(a,b),于是(1,0)是單位元.(4)每元素均存在逆元對(duì)于彳I意(a,b)wG,由于-bG且a,a(a,b)a.1,a.0+bL(1,0),:a：ba/JbU=(1,.),ka4所以,G中每元素均有逆元.(5)由于(1,2)(2,1)=(2,3)且(2,1)(1,2)=(2,5),即(1,2)(2,1)#(2,1)(1,2),因而,不可交換.綜上所述,(G,)是非Abel群.八、證(反證)設(shè)G是不

9、連通的,那么G有k(k之2)個(gè)連通分支G1,G2,Gk.對(duì)于彳I意i(lwiwk),令Gj是(n,mj圖.假設(shè)存在j(1WjMk)使得Aj=1,那么另外6個(gè)節(jié)點(diǎn)所生成的子圖恰15條邊.由于G是簡(jiǎn)單圖,K6的邊數(shù)為15,即G中含K6子圖.顯然,K6不是平面圖,這與G是平面圖矛盾.假設(shè)存在j(1Wj三女)使得門(mén)上=2,那么另外5個(gè)節(jié)點(diǎn)所生成的子圖恰14條邊,這不可能,由于K5的邊數(shù)恰為10.于是Aj之3,j=1,2,.,k,因此對(duì)于每個(gè)連通分支有mi3ni-6(1jk),進(jìn)而kkkm=miZ(3ni6)=3q6k=3n6k.因?yàn)閚=7,m=15,所以i4i1i11537-6k,由此得出kW1,與k

10、之2矛盾.故G是連通圖.?離散數(shù)學(xué)?期末測(cè)試題(B)一、填空題(每題3分,共15分)1 .設(shè)A=a,b,a,b,0,那么A0=(),A-0=(),P(A)中的元素個(gè)數(shù)|P(A)|=().2 .設(shè)集合A中有3個(gè)元素,那么A上的二元關(guān)系有()個(gè),其中有()個(gè)是A到A的函數(shù).3 .謂詞公式Vx(P(x)tQ(x)八三y(Q(y)八一P(y)中量詞Vx的轄域?yàn)?),量詞三y的轄域?yàn)?).4 .設(shè)D24=1,2,3,4,6,8,12,24,對(duì)于其上的整除關(guān)系“|,元素()不存在補(bǔ)元.5 .當(dāng)n()時(shí),n階完全無(wú)向圖Kn是平面圖,當(dāng)當(dāng)門(mén)為()時(shí),Kn是歐拉圖.二、單項(xiàng)選擇題(每題3分,共15分)1 .設(shè)R

11、是集合A上的偏序關(guān)系,R是R的逆關(guān)系,那么R=R,是A上的(A)偏序關(guān)系(B)等價(jià)關(guān)系(C)相容關(guān)系(D)以上結(jié)論都不成立2 .由2個(gè)命題變?cè)猵和q組成的不等值的命題公式的個(gè)數(shù)有(A)2(B)4(C)8(D)163 .設(shè)p是素?cái)?shù)且n是正整數(shù),那么任意有限域的元素個(gè)數(shù)為np(A)p-n(B)pn(C)p(D)n,4.設(shè)R是實(shí)數(shù)集合,E是其上的小于等于關(guān)系,那么(R,E)是(A)有界格(B)分配格(C)有補(bǔ)格(D)布爾格5.3階完全無(wú)向圖K3的不同構(gòu)的生成子圖有(A)2(B)3(C)4(D)5三、判斷題(每題3分,共15分)：正確打“錯(cuò)誤打“X.1 .假設(shè)一個(gè)元素a既存在左逆元al,又存在右逆元a

12、r,那么al=ar.()2 .命題聯(lián)結(jié)詞一不滿足結(jié)合律.()3 .在Z8=0,1,2,3,4,5,6,7中,2關(guān)于“8的逆元為4.()4 .整環(huán)不一定是域.()5 .任彳(n,m)平面圖的面數(shù)r=m-n+2.()四、(10分)設(shè)f：AtB且g:BTC,假設(shè)fg是單射,證實(shí)f是單射,并舉例說(shuō)明g不一定是單射.五、(15分)設(shè)A=a,b,c,d,A上的關(guān)系R=(a,a),(a,b),(a,c),(c,a),(c,b),(c,c),(d,a),(d,b),(d,c),1 .畫(huà)出R的關(guān)系圖Gr.2 .判斷R所具有的性質(zhì).3 .求出R的關(guān)系矩陣Mr.六、(10分)利用真值表求命題公式A=(pT(qtr)

13、(rt(qTp)的主析取范式和主合取范式.七、(10分)邊數(shù)mc30的簡(jiǎn)單平面圖G,必存在節(jié)點(diǎn)v使彳tdeg(v)Q(x),Q(y)-P(y).4. 2,4,6,12.5. 4,奇數(shù).二、1(B);2(D);3(C);4(B);5(C).三、1(X);2(M);3(X);4(X);5(X).四、證對(duì)于任意x,ywA,假設(shè)f(x)=f(y),那么g(f(x)=g(f(y),即(f-g)(x)=(f*g)(y).由于fgg是單射,因此x=y,于是f是單射.例如取A=a,b,B=(1,2,3,C=u,P,Y,令f=(a,1),(b,2),g=(1,a),(2,P),(3,P),這時(shí)fQg=(a,a)

14、,(b,P)是單射,而g不是單射.五、解1.R的關(guān)系圖GR如下:2 .(1)由于(b,b)更R,所以R不是自反的.(2)由于(a,a)wR,所以R不是反自反的.(3)由于(d,b)wR,而(b,d)更R,因此R不是對(duì)稱的.因(a,c),(c,a)wR,于是R不是反對(duì)稱的.(5)經(jīng)計(jì)算知R*R=(a,a),(a,b),(a,c),(c,a),(c,b),(c,c),(d,a),(d,c)R,進(jìn)而R是傳遞的.綜上所述,所給R是傳遞的.0000;1110003 .R的關(guān)系矩陣MR=1111111六、解命題公式A=(pT(qTr)(rt(qtp)的真值表如下p,q,rpT(qTr)L(qTp)A1,1

15、,11111,1,00101,0,11111,0,01110,1,11000,1,01110,0,11110,0,0111由表可知,A=(pT(qTr)修(rT(qtp)的主析取范式為A=(pqr)(p-qr)(pq-r)(-pq-r)(一p-qr)(-p-q-r).a的主合取范式為A=(一px/一1qvr)八(p一1qVr).七、證不妨設(shè)G的階數(shù)n23,否那么結(jié)論是顯然的.根據(jù)推論1知,m3n-6.假設(shè)G的任意節(jié)點(diǎn)v的度數(shù)均有deg(v)至5,由握手定理知2m=deg(v),5n.v22于是nem,進(jìn)而m3n-63m-6.因此m之30,與矛盾.所以必存在節(jié)點(diǎn)55使得deg(v)4.八、解設(shè)滿

16、足要求的r位數(shù)的個(gè)數(shù)有a種,r=0,1,2,那么排列計(jì)數(shù)生成函數(shù)_x2E(x)=1+x+2!Lx3!.=13x4x2193一x61941516一xx一x12212一一19.因而a4=-4!=38.12?離散數(shù)學(xué)?期末測(cè)試題(C)一、填空題(每題3分,共15分)1.假設(shè)|A|二m,|B|=n,那么1AMB|=(),A到B的2元關(guān)系共有()個(gè),a上的2元關(guān)系共有()個(gè).2.設(shè)A=1,2,3,f=(1,1),(2,1),(3,1),是單射,()是滿射,()是雙射.g=(1,1),(2,3),(3,2)和h=(1,3),(2,1),(3,1),那么(3.以下5個(gè)命題公式中,是永真式的有(p八(pTq)

17、Tq；(2)pT(pvq)；p-(pq)；)(選擇正確答案的番號(hào)).(4)p(pq)rq;(p,q),q.4.設(shè)D24是24的所有正因數(shù)組成的集合,|是其上的整除關(guān)系,那么3的補(bǔ)元(6的補(bǔ)元().5.設(shè)G是(7,15)簡(jiǎn)單平面圖,那么G一定是()圖,數(shù)為().二、單項(xiàng)選擇題(每題3分,共15分)1 .設(shè)A,B,C是集合,那么下述論斷正確的選項(xiàng)是().(A)假設(shè)A=B,BWC,那么AC.(B)假設(shè)AB,(假設(shè)慶乏8,B三C,那么AWC.(D)假設(shè)AWB,2 .設(shè)RAMA,S2AMA,那么下述結(jié)論正確的選項(xiàng)是(A)假設(shè)R和S是自反的,那么RS是自反的.(B)假設(shè)R和S是對(duì)稱的,那么R二S是對(duì)稱的.

18、(C)假設(shè)R和S是反對(duì)稱的,那么RS是反對(duì)稱的.(D)假設(shè)R和S是傳遞的,那么R,jS是傳遞的.3 .在謂詞邏輯中,以下各式中不正確的選項(xiàng)是().(A) -x(A(x)B(x)JxA(x)-xB(x)(B) -x(A(x)B(x)VxA(x)-xB(x)(C) x(A(x)B(x)=xA(x)xB(x)(D) _x_|yA(x,y)=y_xA(x,y)4.域與整環(huán)的關(guān)系為().(A)整環(huán)是域(B)域是整環(huán)(C)整環(huán)不是域且其每個(gè)面恰由(B那么A2C.BC,貝UA三C.).(D)域不是整環(huán)),4的補(bǔ)元(),)條邊圍成,G的面).5.設(shè)G是(n,m)圖,且G中每個(gè)節(jié)點(diǎn)的度數(shù)不是k就是k+1,那么G

19、中度數(shù)為k的節(jié)點(diǎn)個(gè)數(shù)為(A)-.(B)n(n+1).(C)nk.(D)n(k1)-2m.2三、判斷題(每題3分,共15分)：正確打“錯(cuò)誤打“X.1 .設(shè)f:ZTZ,f(x)=|x|-2x,那么f是單射.()2 .設(shè)中是群Gi到群G2的同態(tài)映射,假設(shè)Gi是Abel群,那么G2是Abel群.()3 .設(shè)(L,)是格,對(duì)于x,y,zwL,假設(shè)x,y=x,z且x+y=x+zJUy=z.()4 .元素個(gè)數(shù)相同的有限布爾代數(shù)都是同構(gòu)的.()5 .設(shè)G是n(n211)階簡(jiǎn)單圖,那么G或G是非平面圖.()四、(15分)設(shè)A和B是集合,使以下各式(1)AcB=A;(2)AB=BA;(3)(AB)=(B-A)=A

20、成立的充要條件是什么,并給出理由.五、(10分)設(shè)S是實(shí)數(shù)集合R上的關(guān)系,其定義如下xyS=(x,y)|x,ywr且是-y是整數(shù),證實(shí)：S是R上的等價(jià)關(guān)系.六、(10分)求謂詞公式3xA(x)(B(y)T(三yC(y)TVxD(x)的前束范式七、(10分)假設(shè)n個(gè)人,每個(gè)人恰有3個(gè)朋友,那么n必為偶數(shù),試證實(shí)之.八、(10分)利用生成函數(shù)求解遞歸關(guān)系a=an十2(n1)a1=2?離散數(shù)學(xué)?期末測(cè)試題(C)參考答案mnm2、1.mn,2,2.2.g,g,g.3.1,2,4.4.8,不存在,不存在.5.連通,3,10.、1(C);2(A);3(B);4(A);5(D).、1(V);2(X);3(X

21、);4(V);5(V).四、證(1)顯然,AcB=AuA=B.(2)可以證實(shí)：AB=BAuA=B.(U)當(dāng)A=B時(shí),AB=0且BA=0,于是AB=BA.(二)假定AB=BA,先證實(shí)A三B：對(duì)于任意xA,假設(shè)-更B,那么xAB,進(jìn)而xwBA,根據(jù)差運(yùn)算定義知xwB,與-正B矛盾.所以xwB,因此A=B.同理可證B=A.故A=B.容易證實(shí)：(AB)=(BA)=AuB=0.(U)顯然.(=)(反證)假設(shè)b#0,那么存在xB.分兩種情況討論：假設(shè)-正A,那么xBA,由于(AB)2(BA)=A,于是xWA,矛盾；假設(shè)xA,那么-正AB且-正B-A,進(jìn)而-正A,矛盾.證畢.x-x五、證1.對(duì)于任意xWR,由于-x=0是整數(shù),所以(x,x)WS,即S是R上的自反關(guān)系.3x-yy-xx-y.2 .對(duì)于任意x,yUR,假設(shè)(x,y)=S,那么是整數(shù),而=-也是整數(shù),于是(y,x)仁S3 33xVVZ3.對(duì)于任意x,y,zu