離散數(shù)學(xué)練習(xí)題(答案修改)

1、2016離散數(shù)學(xué)練習(xí)題-（答案修 改）2016注意事項(xiàng)：1、第一遍復(fù)習(xí)一定要認(rèn)真按考試大綱要求將本學(xué)期所學(xué)習(xí)內(nèi)容系統(tǒng)復(fù)習(xí)一遍。2、第二遍復(fù)習(xí)按照考試大綱的總結(jié)把重點(diǎn)內(nèi)容再做復(fù)習(xí)。另外，把大綱中指定 的例題及書后習(xí)題認(rèn)真做一做。檢驗(yàn)一下主要內(nèi)容的掌握情況。3、第三遍復(fù)習(xí)把隨后發(fā)去的練習(xí)題認(rèn)真做一做，檢驗(yàn)一下復(fù)習(xí)情況，要認(rèn)真理 解，注意做題思路與方法。離散數(shù)學(xué)綜合練習(xí)題一、選擇題L令P：今天下雪了,9：路滑，:他遲到了。則命題“下雪路滑，他遲到了”可符號(hào)化為(A )。A. p 八 q frC. p/q/rB. p/q f rD. p/q r2.設(shè)P(x)：x是整數(shù)，/(x)：x的絕對(duì)值，L(x,y

2、)：工大于等于y；命題“所有整 數(shù)的絕對(duì)值大于等于0”可符號(hào)化為(B ) oA. Vx(P(x)aL(/(x),O)C. VxP(x) a L(/(x), 0)3.設(shè)F(x) ： x是人，G(.v) ： x犯錯(cuò)誤,B. Tx(P(x)f L(/(x),0)D. VxP(x) -L(/(x),0)A. Vx(F(x)aG(x)B.i3x(F(x) - -nG(x)C. )3.v(F(x) a G(x)D »3x(F(x) a -iG(x)命題“沒有不犯錯(cuò)誤的人”符號(hào)化為(D)o*4.下列命題公式不是永真式的是(A )oA. (p f q) f pB. 一(“ 一 )C. f7(qfp)

3、D.5.設(shè)p：我們劃船，q：我們跳舞，命題“我們不能既劃船又跳舞”符號(hào)化正確的 是(B )«A.B. Tp /q)C. ai7D.p/q6.設(shè)Rx)：x為有理數(shù)；Q(x)：x為實(shí)數(shù)。命題“任何有理數(shù)都是實(shí)數(shù)”的符號(hào)化 為(A )A.(Vx)(H(x) - Q(x)B.(Vx)(/?(x) a Q(x)C.(3x)(R(x)a。)D.mx(R(x) - Q(x)7.設(shè)個(gè)體域。= “,與公式三小。)等價(jià)的命題公式是(C )A.A(a) a A(b)B.A(a) A(b)C. A(b)D.A(b) A(a)8.無向圖G有20條邊，4個(gè)6度頂點(diǎn)，2個(gè)5度頂點(diǎn)，其余均為2度頂點(diǎn)，則G一共有(C

4、 )個(gè)頂點(diǎn)。A. 7B.8C.9*9.設(shè)集合於c, &，下列命題是假命題的為(A. c e P(A) B. ceP(A) C. c c PA 10.設(shè)后0,。,40,則下列陳述正確的是(CD. 10C ) OD. cO)0h. aeXB. <7,0( c XC. a,0 = XD. 0eXIL有向圖是連通圖，當(dāng)且僅當(dāng)(D )oA.B.C.D.圖中至少有一條通路圖中有通過每個(gè)頂點(diǎn)至少一次的通路圖的連通分支數(shù)為一圖。中有通過每個(gè)頂點(diǎn)至少一次的回路12.設(shè)人=2力,。，則下列是集合A的劃分的是(B )A.也 c,。C. afb9a,c13 .下列謂詞公式中是前束范式的是(A. VxF(

5、x)a-<3x)(7(.¥)C Vx( P(x) -> 3yQ(x,y)B.DB.D.,依c /©)o14 .設(shè)簡(jiǎn)單圖6所有結(jié)點(diǎn)的度數(shù)之和為50,A. 50C. 10B.D.VxF(x) v UyG(y)Vx3y(P(x)Q(xty) 則G的邊數(shù)為(B 255)o15 .設(shè)集合 A = 1,2,3,4, A 上的等價(jià)關(guān)系 K = < 1,1 >, v 3,2 >,< 2,3 >,<4,4>17/則對(duì)應(yīng)于/?的劃分是(A )oA. 1,2,3,4B. 1,3,2,4C. 1,3,2,4D. 1,2,3,416 .設(shè)X =

6、l,2,3,y = a,b,c,dJ = <lM>,v2,b>9<3,c>,則/是A.B.c.D.C )o從X到Y(jié)的雙射從X到Y(jié)的滿射，但不是單射從X到Y(jié)的單射，但不是滿射從X到Y(jié)的二元關(guān)系，但不是從X到Y(jié)的映射17.下列圖是歐拉圖的是(D)o18.給定一個(gè)有n個(gè)結(jié)點(diǎn)的無向樹，下列陳述不正確的是(A )。A.所有結(jié)點(diǎn)的度數(shù)22B.無回路但若增加一條新邊就會(huì)變成回路C.連通且e =1,其中e是邊數(shù)，y是結(jié)點(diǎn)數(shù)D.無回路的連通圖19.若供選擇答案中的數(shù)值表示一個(gè)簡(jiǎn)單圖中各個(gè)頂點(diǎn)的度，能畫出圖的是 (C )»A. (1, 2, 2, 3, 4, 5)B. (1

7、, 2, 3, 4, 5, 5)C. (1,1,1,2,3)D. (2, 3, 3,4, 5, 6)20 .設(shè)4 = ",“,a,a則其塞集尸(A)的元素總個(gè)數(shù)為(CA. 3C. 8B. 4D. 1621 .設(shè)簡(jiǎn)單圖G所有結(jié)點(diǎn)的度數(shù)之和為48,則G的邊數(shù)為(BB. 24A. 48C. 16D.1222.F面既是哈密頓圖又是歐拉圖的圖形是(B )oB.不可以一筆畫的圖D.無奇數(shù)度結(jié)點(diǎn)的連通圖B.哈密頓圖23 .下列必為歐拉圖的是(D )A.有回路的連通圖C有1個(gè)奇數(shù)度結(jié)點(diǎn)的連通圖24 .二部圖%是(B )oA.歐拉圖C .平面圖D.完全圖25 .下列所示的哈斯圖所對(duì)應(yīng)的偏序集中能構(gòu)成格

8、的是（C ）。26 .設(shè)集合4 = 4也0,從上的關(guān)系尺=<4,4>,<4,(?>,<0,”>,則R是(B )A.自反的C傳遞的B.對(duì)稱的D.反對(duì)稱的27 .設(shè)與，&是集合A = a/cd上的兩個(gè)關(guān)系，其中為=<4,4<b9c>,<d,d > , R2 =<a,a >.< b,b >,< c,b >,< b,c >.< d ,d >),則& 是 & 的(B )閉包。A.自反C.傳遞B.對(duì)稱D.自反、對(duì)稱且傳遞閉包28 .下列公式是前束范式的是(A

9、 )oA. (Vx)(Vy)(F(z,x)vG(y) B. (T*"(x)v(Vy)G()，)aHC. (3x)F(x, y) t (Vy)G(y) D. (Vx)(/(x, y) T (Vy)G(x, y) 29.設(shè) R 為實(shí)數(shù)集，函數(shù)x) = ,d + 2x + 5,則/是(D )。A.單射而非滿射B.滿射而非單射C.雙射D.既不是單射，也不是滿射30.下列各圖中既是歐拉圖，又是漢密爾頓圖的是（C ）。A. MANC. M©N12 .設(shè)M=x"(x) = 0,N = x5(x) = 0,則方程力(幻/)=。的解為(B)oB. MUNC. M-N13 .設(shè)G=v

10、 A*是群，則下列陳述不正確的是（C ）oB.D.A.C. (ab 尸二、填空題1 .命題公式( AO)的成真指派為0001 11,成假指派為匚。2 .公式“x)(Vv)(P( y) T 0(X, z)八(玉/(X, V)約束變?cè)獮?XW ,自由變?cè)?為 xg 。3 .設(shè)4 = 也a/, B = a,bt 則8A= g, , A8= a,b04 .設(shè)A = a/,c, A上的關(guān)系A(chǔ) = va,>,v%MH7則對(duì)稱閉包 s(R)= va,b>,vb,a >), 傳 遞 閉 包f(R) = <a,b >,<£?,a >,< a,a >

11、、<b、b >。5 .一棵無向樹的頂點(diǎn)數(shù)與邊數(shù)?的關(guān)系是n-1。6階無向連通圖至多有 6棵不同構(gòu)的生成樹。6 .設(shè)/(x) = x-l, g(x) = X2 ,則復(fù)合函數(shù)(f og)(x) = (x-l)2, (go/)(x) =X2-1 O7 . <z.,o> 是一個(gè)群，其中2“=0,1,2廣.,一1, xy = (x+y)mod，則當(dāng) W 時(shí)，在<Z6.e>中，2的階為一3. 3的階為o8 .設(shè)小，W是格，其中A二1, 3,4, 6, 8, 12, 24, W為整除關(guān)系，貝心的補(bǔ) 元是_ _24 _ , 3的補(bǔ)元是9 .設(shè) A= <1, 3>

12、, <3, 5>, <4, 4>), B= <1, 3>, <4, 5>, <5, 5> ,那么 dom(A U B)=1,3,4,5ran (AQB) = 3 。10 .設(shè)#1,2,3,4,在的二元關(guān)系后<1,2>,<2,3>,<3,2>,故<1, 3>, <2, 3>, <4, 3»,貝?JS =vS,3>3,3> , (RoSy'= v3,l>,v3,3>。U.設(shè)復(fù)合函數(shù)go/是從A到C的函數(shù)，如果go/是滿射，那么必是滿

13、 射，如果是單射，那么工.必是單射。12 .給出A=1, 2上的一個(gè)等價(jià)關(guān)系<1,1>,<2,2>,并給出其對(duì)應(yīng)的劃分 1，2。13 .設(shè)4 =伍/工/, A上的二元關(guān)系/? = <*>,<“”>,<,>,則R的自 反閉包"K)=RU/a，傳遞閉包"R)= R14 .設(shè)個(gè)體域是實(shí)數(shù)集,命題Vx(x-3vx)的真值為1；命題*(/+ 1 = 0)的真值為0。15 .設(shè) f ： R->R,f(x)=x+3,g ： R->R5g(x)=2x+l,則復(fù)合函數(shù)(f og)(x)= 21+4,(gof)(x)= 2

14、。+7。16 .設(shè)Ze，,為模6加群，其中Z$= 0,123,4,5,則2-0 , 4三4 。17 . 一個(gè)結(jié)點(diǎn)為n的無向完全圖，其邊的數(shù)目為10k皿,，頂點(diǎn)的度為】/.18 .已知階無向簡(jiǎn)單圖G有?條邊，則G的補(bǔ)圖G中有n（nl）/2m條邊。19 .設(shè)K是個(gè)頂點(diǎn)的完全圖，則&有工條邊，每個(gè)頂點(diǎn)的度數(shù)為一£_。20 . 一個(gè)班有40個(gè)人，在第一次考試中有26人得優(yōu)秀，在第二次考試中有21 人得優(yōu)秀，如果兩次考試都得優(yōu)秀的有17人，兩次考試都沒有得優(yōu)秀的人數(shù) 為 10,至少有一次得優(yōu)秀的人數(shù)為30。三、計(jì)算題（僅給出部分題目的解題思路，未給出答案自己完成）1 .已知命題公式（1

15、）構(gòu)造真值表；（2）用等值演算法求公式的主析取范式。解：（1）真值表Pq rp7 rTpvr)(pvg)f TP")00000110100101001101101111001001100110110010111001111100(2)主析取范式(pvg)f Tvr)01( v 夕)v7 r)0(1 AIf/) V (-1P a >r)=(> a it/) a (>r v r) v (ip a (>q v q)八一>r)=()/) A It/ A if) V (1 A 1<7 A r) V (>p AA>r) V (1Air)=v ni

16、v m22 .求公式( (rv)A(g - p)的主合取范式及主析取范式。3 .設(shè)/:R>RJ(x) =一2 , g g(x) = x+4, /;:?> RJi(x) = - , 其中R表示實(shí)數(shù)集。(l)求函數(shù)/'og , g。f ；(2) 哪些函數(shù)有反函數(shù)？如果有，求出這些反函數(shù)。解：(1) g o /(A) = f(g(x) = /(x + 4) = (x + 4) A中的極大元為24, 54；極小元為1；最大元：無；最小元：1(3)求子集B= 3, 6, 9)的上確界為54,下確界為3。5.設(shè)有向圖。如圖所示，用鄰接矩陣計(jì)算匕到!長度小于或等于3的通路數(shù)。解：有向圖的

17、鄰接矩陣為 - 2 = x2 + 8x +14/。g(x) = g(/*) = g(-2) = a2 + 2(2) g和萬有反函數(shù)，g" R,gT(x) = x-4；/：Af KJ尸(x) = /x+l4.設(shè)A = 1,2,3,4,6,9,24,54,為整除關(guān)系°(1)畫出偏序集<A, 4 >的哈斯圖；(2)求A中的極大元；(3)求子集B=3, 6, 9)的上確界與下確界。解：(1)哈斯圖匕到內(nèi)長度小于或等于3的通路數(shù)為6.設(shè)Z6 =0,123,4.5,給出模6加運(yùn)算的運(yùn)算的運(yùn)算表。解：運(yùn)算的運(yùn)算表為0123450012345112345022345013345

18、01244501235501234參看教材P197-198例9. 4與9. 57 .設(shè)4=1, 2, 3, 4, 5, R是A上的二元關(guān)系，且R= (2, 1>, <2, 5), <2, 4>, <3, 4), <4, 4>, <5, 2>,求r(R)、s(R)和t(R)。解：r(R)=R U Ias(R)=R U R1t(R)= <2, 1>, <2, 5>, <2, 4>, <3, 4>, <4, 4>, <5, 2>, (2, 2>, <5, 5

19、87;8 . 一棵(無向)樹有2結(jié)點(diǎn)的度為2, 1個(gè)結(jié)點(diǎn)的度為3, 3個(gè)結(jié)點(diǎn)的度為4,其 余都是葉結(jié)點(diǎn)，問該樹有幾個(gè)葉結(jié)點(diǎn)？解：在一個(gè)有限圖中，各結(jié)點(diǎn)的度數(shù)總和是邊數(shù)的2倍；而樹中的邊數(shù)為結(jié)點(diǎn) 數(shù)減1。根據(jù)這兩點(diǎn)，可知樹中各結(jié)點(diǎn)的度數(shù)總和=2* (樹中點(diǎn)數(shù)T),設(shè)樹葉有x個(gè), 于是，2*2+3+3*4+x=2* (2+1+3+x-l)得 x=9o四、簡(jiǎn)答題1 .設(shè) R = vl,3>,(l,4>,v2,2>,v3,l>,v3,3),v4>是 A= 1,2,3,4上的二元關(guān) 系。(1)畫出R的關(guān)系圖；(2)寫出R的關(guān)系矩陣；(3)討論R的性質(zhì)。0o o 1 r0 1

20、0 010 0 010 0 0(4) R是否為函數(shù)(2) R的關(guān)系矩陣(3) R非自反、非反自傳、對(duì)稱、非反對(duì)稱、非傳遞的(4) R不是函數(shù)，不滿足函數(shù)單值性的要求。2.設(shè)集合4 = 1,2,3,4,5,6上的關(guān)系/? = (1>,<1,3>,<1,6>,<2,2>,<2,5>,<3,1>,<3,3>,<3,6>,<4,4>,<5,2>,<5,5>,<6,1 >,<6,3),<6,6>)(1)畫出R的關(guān)系圖，并寫出R的關(guān)系矩陣；(2) R是

21、否為等價(jià)關(guān)系？若是，寫出R的所有等價(jià)類。解：(1) R的關(guān)系圖為o010011010010100（2） R的關(guān)系矩陣0001001001由關(guān)系圖可以看出R是等價(jià)關(guān)系。等價(jià)類為:1 = P = 6 = 1,3,6,2 = 2,5,4 = 4或?qū)憺椋篈/R=1,3,6, 2,5, 4)3.判斷下圖是否為二部圖？若是，找出它的互補(bǔ)結(jié)點(diǎn)子集。它是否為哈密頓圖? 若是，找出一條哈密頓回路。四、證明題1 .設(shè)4 = <乂），>lx,y為正整數(shù),在A上定義二元關(guān)系R如下：<x,y>R<u,v> 當(dāng)且僅當(dāng)工一> =”。證明：R是一個(gè)等價(jià)關(guān)系。證明：任取v x, y&g

22、t;<x,y>A<=>x-y = xy <=x x, y > R v x, y >所以斤自反的。任取<x,y>R<u,v x=>x-y = u-v <>u-v = x-y <=x u.v> Rvx,y > 所以斤是對(duì)稱的。任取 vx,><x.y>R<u,v>/<u,v>R<s,t x=>x-y = u-v/u-v = s-t<=>x-y = 5-r <=Xx,y > R<s, > 所以斤是傳遞的。因此，斤是等價(jià)

23、關(guān)系。2 .設(shè)力=<,。>1,。為正整數(shù) >在A上定義二元關(guān)系R如下：va,b> Rc,d > 當(dāng)且僅當(dāng)。+b = c+d。證明：R是一個(gè)等價(jià)關(guān)系。證明：任取<,>< a,b >e Aa + b = a + b <=x a.b > R < a,b >所以斤自反的。任取<a,Z? >,<c,d >< x,y>R < u. v x=> a + b = c + d = c + d = a + b<x c.d > R< a,b > 所以斤是對(duì)稱的。任取

24、<,/?>,< c,d >y<eyf>< a.b > R<cyd > a < c.d > R<e,f x=> a + b = c + d /c + d = e + f= a + b = e + f <=>< a.b> R<e,f >所以斤是傳遞的。因此，斤是等價(jià)關(guān)系。3 .用一階邏輯的推理理論證明：X/x(F(x) T G(x) A Vx(G(x) T H(x) A 玉F(x)=> 玉H(x)4 .設(shè)代數(shù)系統(tǒng)V=<Z°,，Z6=0,l,2,3,4,5),為模6加法。證明：Zf關(guān)于 IS算構(gòu)成群。證明：集合4顯然非空。(1) 協(xié),。吐Z',從而集合&關(guān)于運(yùn)算是封閉的。(2) Va,b,ceZb9有(a®b)®c = a©(h&c),故運(yùn)算是可結(jié)合的。(3) VdeZ6,。0 =。，故。是<26