離散數(shù)學(xué)試卷及答案

1、一、單項(xiàng)選擇題(本大題共15小題，每小題1分，共15分)在每小題列出的四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的，請(qǐng)將正確選項(xiàng)前的字母填在題后的括號(hào)內(nèi)。1.一個(gè)連通的無向圖G，如果它的所有結(jié)點(diǎn)的度數(shù)都是偶數(shù)，那么它具有一條( )A.漢密爾頓回路 B.歐拉回路C.漢密爾頓通路 D.初級(jí)回路2.設(shè)G是連通簡(jiǎn)單平面圖，G中有11個(gè)頂點(diǎn)5個(gè)面，則G中的邊是( )A.10 B.12 C.16 D.143.在布爾代數(shù)L中，表達(dá)式(ab)(abc)(bc)的等價(jià)式是( )A.b(ac)B.(ab)(ab)C.(ab)(abc)(bc)D.(bc)(ac)4.設(shè)i是虛數(shù)，是復(fù)數(shù)乘法運(yùn)算，則G=是群，下列是G的子群

2、是( )A. B.-1, C.i, D.-i,5.設(shè)Z為整數(shù)集，A為集合，A的冪集為P(A),+、-、/為數(shù)的加、減、除運(yùn)算，為集合的交運(yùn)算，下列系統(tǒng)中是代數(shù)系統(tǒng)的有( )A.Z，+，/ B.Z，/C.Z，-，/ D.P(A)，6.下列各代數(shù)系統(tǒng)中不含有零元素的是( )A.Q，*Q是全體有理數(shù)集，*是數(shù)的乘法運(yùn)算B.Mn(R),*,Mn(R)是全體n階實(shí)矩陣集合，*是矩陣乘法運(yùn)算C.Z，Z是整數(shù)集，定義為xxy=xy,x,yZD.Z，+，Z是整數(shù)集，+是數(shù)的加法運(yùn)算7.設(shè)A=1,2,3，A上二元關(guān)系R的關(guān)系圖如下：R具有的性質(zhì)是A.自反性B.對(duì)稱性C.傳遞性D.反自反性8.設(shè)A=a,b,c，A

3、上二元關(guān)系R=a,a，b,b,a,c，則關(guān)系R的對(duì)稱閉包S(R)是( )A.RIA B.R C.Rc,a D.RIA9.設(shè)X=a,b,c,Ix是X上恒等關(guān)系，要使Ixa,b，b,c，c,a，b,aR為X上的等價(jià)關(guān)系，R應(yīng)取( )A.c,a，a,c B.c,b，b,aC.c,a，b,a D.a,c，c,b10.下列式子正確的是( )A. B. C. D.11.設(shè)解釋R如下：論域D為實(shí)數(shù)集，a=0,f(x,y)=x-y,A(x,y):xy.下列公式在R下為真的是( )A.( x)( y)( z)(A(x,y)A(f(x,z),f(y,z)B.( x)A(f(a,x),a)C.(x)(y)（A(f(

4、x,y),x)D.(x)(y)(A(x,y)A(f(x,a),a)12.設(shè)B是不含變?cè)獂的公式，謂詞公式(x)(A(x)B)等價(jià)于( )A.(x)A(x)B B.(x)A(x)BC.A(x)B D.(x)A(x)(x)B13.謂詞公式(x)(P(x,y)(z)Q(x,z)(y)R(x,y)中變?cè)獂( )A.是自由變?cè)皇羌s束變?cè)狟.既不是自由變?cè)植皇羌s束變?cè)狢.既是自由變?cè)质羌s束變?cè)狣.是約束變?cè)皇亲杂勺冊(cè)?4.若P：他聰明；Q：他用功；則“他雖聰明，但不用功”，可符號(hào)化為( )A.PQ B.PQ C.PQ D.PQ15.以下命題公式中，為永假式的是( )A.p(pqr) B.(pp

5、)pC.(qq)p D.(qp)(pp)二、填空題(每空1分，共20分)16.在一棵根樹中，僅有一個(gè)結(jié)點(diǎn)的入度為_，稱為樹根，其余結(jié)點(diǎn)的入度均為_。17.A=1,2,3,4上二元關(guān)系R=2，4，3，3，4，2，R的關(guān)系矩陣MR中m24=_,m34=_。18.設(shè)s,*是群，則那么s中除_外，不可能有別的冪等元；若s,*有零元，則|s|=_。19.設(shè)A為集合，P(A)為A的冪集，則P(A)，是格，若x,yP(A),則x,y最大下界是_，最小上界是_。20.設(shè)函數(shù)f:XY,如果對(duì)X中的任意兩個(gè)不同的x1和x2，它們的象y1和y2也不同，我們說f是_函數(shù)，如果ranf=Y，則稱f是_函數(shù)。21.設(shè)R為

6、非空集合A上的等價(jià)關(guān)系，其等價(jià)類記為xR。x,yA，若x,yR，則xR與yR的關(guān)系是_，而若x,yR，則xRyR=_。22.使公式(x)( y)(A(x)B(y)(x)A(x)(y)B(y)成立的條件是_不含有y，_不含有x。23.設(shè)M(x):x是人，D(s):x是要死的，則命題“所有的人都是要死的”可符號(hào)化為(x)_,其中量詞(x)的轄域是_。24.若H1H2Hn是_，則稱H1,H2,Hn是相容的，若H1H2Hn是_，則稱H1,H2,Hn是不相容的。25.判斷一個(gè)語句是否為命題，首先要看它是否為 ，然后再看它是否具有唯一的 。三、計(jì)算題 (共30分)26.(4分)設(shè)有向圖G=(V,E)如下圖

7、所示，試用鄰接矩陣方法求長度為2的路的總數(shù)和回路總數(shù)。27.(5)設(shè)A=a,b,P(A)是A的冪集，是對(duì)稱差運(yùn)算，可以驗(yàn)證是群。設(shè)n是正整數(shù)，求(a-1ba)na-nbnan28.(6分)設(shè)A=1,2,3,4,5,A上偏序關(guān)系 R=1，2，3，2，4，1，4，2，4，3，3，5，4，5IA;(1)作出偏序關(guān)系R的哈斯圖(2)令B=1,2,3,5，求B的最大，最小元，極大、極小元，上界，下確界，下界，下確界。29.(6分)求(PQ)(PQ)的主合取范式并給出所有使命題為真的賦值。30.(5分)設(shè)帶權(quán)無向圖G如下，求G的最小生成樹T及T的權(quán)總和，要求寫出解的過程。31.(4分)求公式(x)F(x,

8、y)(y)G(x,y)(x)H(x)的前束范式。四、證明題 (共20分)32.(6分)設(shè)T是非平凡的無向樹，T中度數(shù)最大的頂點(diǎn)有2個(gè)，它們的度數(shù)為k(k2),證明T中至少有2k-2片樹葉。33.(8分)設(shè)A是非空集合，F(xiàn)是所有從A到A的雙射函數(shù)的集合，是函數(shù)復(fù)合運(yùn)算。 證明：F, 是群。34.(6分)在個(gè)體域D=a1,a2,，an中證明等價(jià)式： (x)(A(x)B(x)(x)A(x)(x)B(x)五、應(yīng)用題(共15分)35.(9分)如果他是計(jì)算機(jī)系本科生或者是計(jì)算機(jī)系研究生，那么他一定學(xué)過DELPHI語言而且學(xué)過C+語言。只要他學(xué)過DELPHI語言或者C+語言，那么他就會(huì)編程序。因此如果他是計(jì)

9、算機(jī)系本科生，那么他就會(huì)編程序。請(qǐng)用命題邏輯推理方法，證明該推理的有效結(jié)論。36.(6分)一次學(xué)術(shù)會(huì)議的理事會(huì)共有20個(gè)人參加，他們之間有的相互認(rèn)識(shí)但有的相互不認(rèn)識(shí)。但對(duì)任意兩個(gè)人，他們各自認(rèn)識(shí)的人的數(shù)目之和不小于20。問能否把這20個(gè)人排在圓桌旁，使得任意一個(gè)人認(rèn)識(shí)其旁邊的兩個(gè)人?根據(jù)是什么?參考答案一、單項(xiàng)選擇題(本大題共15小題，每小題1分，共15分) 1.B 2.D 3.A 4.A 5.D 6.D 7.D 8.C 9.D 10.B 11.A 12.A 13.C 14.B 15.C二、填空題16.0 117.1 018.單位元 119.xy xy20.入射 滿射21.xR=yR 22.A

10、(x) B(y)23.(M(x)D(x) M(x)D(x)24.可滿足式 永假式(或矛盾式)25.陳述句 真值三、計(jì)算題26. M= M2= G中長度為2的路總數(shù)為18，長度為2的回路總數(shù)為6。27.當(dāng)n是偶數(shù)時(shí)，xP(A),xn= 當(dāng)n是奇數(shù)時(shí)，xP(A),xn=x 于是：當(dāng)n是偶數(shù)，(a-1ba)na-nbnan =(a-1)nbnan= 當(dāng)n是奇數(shù)時(shí)， (a-1ba)na-nbnan =a-1ba(a-1)nbnan =a-1baa-1ba=28.(1)偏序關(guān)系R的哈斯圖為 (2)B的最大元：無，最小元：無； 極大元：2，5，極小元：1，3 下界：4， 下確界4； 上界：無，上確界：無2

11、9.原式(PQ)(PQ)(PQ)(PQ) (PQ)(PQ)(PQ)(PQ) (PQPQ)(PQ)(PQ) (PQ)(PQ) (PQ)(PQ) P(QQ) P(QQ) (PQ)(PQ) 命題為真的賦值是P=1,Q=0和P=1,Q=130.令e1=(v1,v3), e2=(v4,v6) e3=(v2,v5), e4=(v3,v6) e5=(v2,v3), e6=(v1,v2) e7=(v1,v4), e8=(v4,v3) e9=(v3,v5), e10=(v5,v6) 令ai為ei上的權(quán)，則 a1a2a3a4a5=a6=a7=a8a9=a10 取a1的e1T,a2的e2T,a3的e3T,a4的e4

12、T,a5的e5T,即， T的總權(quán)和=1+2+3+4+5=1531.原式(x1F(x1,y)y1G(x,y1)x2H(x2) (換名) x1y1(F(x1,y)G(x,y1)x2H(x2) x1y1(F(x1,y1)G(x,y1)x2H(x2) x1y1x2(F(x1,y1)G(x,y1)H(x2) 四、證明題32.設(shè)T中有x片樹葉，y個(gè)分支點(diǎn)。于是T中有x+y個(gè)頂點(diǎn)，有x+y-1 條邊，由握手定理知T中所有頂點(diǎn)的度數(shù)之的 =2(x+y-1)。 又樹葉的度為1，任一分支點(diǎn)的度大于等于2 且度最大的頂點(diǎn)必是分支點(diǎn)，于是 x1+2(y-2)+k+k=x+2y+2K-4 從而2(x+y-1)x+2y+

13、2k-4 x2k-233.從定義出發(fā)證明：由于集合A是非空的，故顯然從A到A的雙射函數(shù)總是存在的，如A上恒等函數(shù)，因此F非空 (1)f,gF,因?yàn)閒和g都是A到A的雙射函數(shù)，故fg也是A到A的雙射函數(shù)，從而集合F關(guān)于運(yùn)算是封閉的。 (2)f,g,hF,由函數(shù)復(fù)合運(yùn)算的結(jié)合律有f(gh)=(fg)h故運(yùn)算是可結(jié)合的。 (3)A上的恒等函數(shù)IA也是A到A的雙射函數(shù)即IAF,且fF有IAf=fIA=f,故IA是F，中的幺元 (4)fF,因?yàn)閒是雙射函數(shù)，故其逆函數(shù)是存在的，也是A到A的雙射函數(shù)，且有ff-1=f-1f=IA,因此f-1是f的逆元 由此上知F，是群34.證明(x)(A(x)B(x) x

14、(A(x)B(x) (A(a1)B(a1)(A(a2)B(a2)(A(an)B(an) (A(a1)A(a2)A(an)(B(a1)B(a2)(B(an) (A(a1)A(a2)A(an)(B(a1)B(a2)(B(an) (x)A(x)(x)B(x) (x)A(x)(x)B(x)五、應(yīng)用題35.令p：他是計(jì)算機(jī)系本科生 q：他是計(jì)算機(jī)系研究生 r：他學(xué)過DELPHI語言 s:他學(xué)過C+語言 t:他會(huì)編程序 前提：(pq)(rs),(rs)t 結(jié)論：pt 證p P(附加前提) pq TI (pq)(rs) P(前提引入) rs TI r TI rs TI (rs)t P(前提引入) t TI3

15、6.可以把這20個(gè)人排在圓桌旁，使得任一人認(rèn)識(shí)其旁邊的兩個(gè)人。 根據(jù)：構(gòu)造無向簡(jiǎn)單圖G=,其中V=v1,v2,，V20是以20個(gè)人為頂點(diǎn)的集合，E中的邊是若任兩個(gè)人vi和vj相互認(rèn)識(shí)則在vi與vj之間連一條邊。 ViV,d(vi)是與vi相互認(rèn)識(shí)的人的數(shù)目，由題意知vi,vjV有d(vi)+d(vj)20,于是G中存在漢密爾頓回路。 設(shè)C=Vi1Vi2Vi20Vi1是G中一條漢密爾頓回路，按這條回路的順序按其排座位即符合要求。一、單項(xiàng)選擇題（本大題共15小題，每小題1分，共15分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1下列是

16、兩個(gè)命題變?cè)猵，q的小項(xiàng)是（ ）AppqBpqCpqDppq2令p：今天下雪了，q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號(hào)化為（ ）ApqBpqCpqDpq3下列語句中是命題的只有（ ）A1+1=10Bx+y=10Csinx+siny0Dx mod 3=24下列等值式不正確的是（ ）A(x)A(x)AB(x)(BA(x)B(x)A(x)C(x)(A(x)B(x)(x)A(x)(x)B(x)D(x)(y)(A(x)B(y)(x)A(x)(y)B(y)5謂詞公式(x)P(x,y)(x)(Q(x,z)(x)(y)R(x,y,z)中量詞x的轄域是（ ）A(x)Q(x,z)(x)(y)R(x,

17、y,z)BQ(x,z)(y)R(x,y,z)CQ(x,z)(x)(y)R(x,y,z)DQ(x,z)6設(shè)R為實(shí)數(shù)集，函數(shù)f：RR，f(x)=2x，則f是（ ）A滿射函數(shù)B入射函數(shù)C雙射函數(shù)D非入射非滿射7設(shè)A=a,b,c,d，A上的等價(jià)關(guān)系R=,IA，則對(duì)應(yīng)于R的A的劃分是（ ）Aa,b,c,dBa,b,c,dCa,b,c,dDa,b,c,d8設(shè)A=，B=P(P(A)，以下正確的式子是（ ）A,BB,BC,BD,B9設(shè)X，Y，Z是集合，一是集合相對(duì)補(bǔ)運(yùn)算，下列等式不正確的是（ ）A(X-Y)-Z=X-(YZ)B(X-Y)-Z=(X-Z)-YC(X-Y)-Z=(X-Z)-(Y-Z)D(X-Y)-

18、Z=X-(YZ)10設(shè)*是集合A上的二元運(yùn)算，稱Z是A上關(guān)于運(yùn)算*的零元，若（ ）A有x*Z=Z*x=ZBZA，且有x*Z=Z*x=ZCZA，且有x*Z=Z*x=xDZA，且有x*Z=Z*x=Z11在自然數(shù)集N上，下列定義的運(yùn)算中不可結(jié)合的只有（ ）Aa*b=min(a,b)Ba*b=a+bCa*b=GCD(a,b)(a,b的最大公約數(shù))Da*b=a(mod b)12設(shè)R為實(shí)數(shù)集，R+=x|xRx0，*是數(shù)的乘法運(yùn)算，是一個(gè)群，則下列集合關(guān)于數(shù)的乘法運(yùn)算構(gòu)成該群的子群的是（ ）AR+中的有理數(shù)BR+中的無理數(shù)CR+中的自然數(shù)D1，2，313設(shè)是環(huán)，則下列正確的是（ ）A是交換群B是加法群C對(duì)*

19、是可分配的D*對(duì)是可分配的14下列各圖不是歐拉圖的是（ ）15設(shè)G是連通平面圖，G中有6個(gè)頂點(diǎn)8條邊，則G的面的數(shù)目是（ ）A2個(gè)面B3個(gè)面C4個(gè)面D5個(gè)面第二部分 非選擇題（共85分）二、填空題（本大題共10小題，每空1分，共20分）請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。16一公式為 之充分必要條件是其析取范式之每一析取項(xiàng)中均必同時(shí)包含一命題變?cè)捌浞穸ǎ灰还綖?之充分必要條件是其合取范式之每一合取項(xiàng)中均必同時(shí)包含一命題變?cè)捌浞穸ā?7前束范式具有形式(Q1V1)(Q2V2)(QnVn)A，其中Qi(1in)為 ，A為 的謂詞公式。18設(shè)論域是a,b,c，則(x)S(x)等價(jià)于命題公式 ；()S(x)等價(jià)于命題公式 。19設(shè)R為A上的關(guān)系，則R的自反閉包r(R)= ，對(duì)稱閉包s(R)= 。20某集合A上的二元關(guān)系R具有對(duì)稱性，反對(duì)稱性，自反性和傳遞性，此關(guān)系R是 ，其關(guān)系矩陣是 。21設(shè)是一個(gè)偏序集，如果S中的任意兩個(gè)元素都有 和 ，則稱S關(guān)于構(gòu)成一個(gè)格。22設(shè)Z是整數(shù)集，在Z上定義二元運(yùn)算*為a*b=a+b+ab，其中+和是數(shù)的加法和乘法，則代數(shù)系統(tǒng)的幺元是 ，零元是 。23如下平面圖有2個(gè)面R1和R2，其中deg(R1)= ，deg(R2)=