離散數(shù)學(xué)自學(xué)考試真題附答案打印版

1、離散數(shù)學(xué)試題課程代碼：02324一、單項選擇題(本大題共15小題，每 小題1分，共15分)在每題列出 的四個選項中只有一個選項是符合 題目要求的，請將正確選項前的字 母填在題后的括號內(nèi)。1. 一個連通的無向圖 G如果它的所有結(jié)點的度數(shù)都是偶數(shù)，那么它具有一條()A.漢密爾頓回路B.歐拉回路C.漢密爾頓通路D.初級回路2.設(shè)G是連通簡單平面圖，G中有11個頂點 5個面，那么G中的邊是()3. 在布爾代數(shù)L中，表達式(a A b) V (aA b A c) V (b A c)的等價式是()A (a V c)B. (a A b) V (a ' A b)C. (a V b) A (a V b

2、V c) A (b V c)D. (b V c) A (a V c)4. 設(shè)i是虛數(shù)，是復(fù)數(shù)乘法運算，那么G=<1,-1,i,-i,>是群，以下是 G的子群是()A. <1,>B. -1,C. i,D.-i,5. 設(shè)Z為整數(shù)集，A為集合，A的幕集為P(A),+、-、/為數(shù)的加、減、除 運算，門為集合的交運算，以下系 統(tǒng)中是代數(shù)系統(tǒng)的有()A. Z,+,/B.Z, / >C.Z,-,/D.P(A)，門6. 以下各代數(shù)系統(tǒng)中不含有零元素的是()A. Q, *Q是全體有理數(shù)集，*是數(shù) 的乘法運算B. Mn(R),*，Mn(R)是全體n階實矩 陣集合，*是矩陣乘法運算C.

3、 <Z,>, Z是整數(shù)集，：定義為x :xy=xy,- x,y ZD. < Z / +>, Z是整數(shù)集，+是數(shù)的加法 運算7. 設(shè)A=1,2,3 / A上二元關(guān)系 R的關(guān) 系圖如下：R具有的性質(zhì)是A. 自反性B. 對稱性C. 傳遞性D. 反自反性8.設(shè) A=a,b,c，A 上二元關(guān)系R= a,a >， < b,b,a,c，那么關(guān)系R的對稱閉包S(R)是()U I AU < c,aA I A9.設(shè)X=a,b,c,lx 是X上恒等關(guān)系， 要使 Ix U a,b > / < b,c > / c,a > /b,a U R為X上的等價關(guān)系

4、，R應(yīng)取()A. c,a >，a,c > B. c,b >， b,ac.c,a >，< b,a D. a,c >， c,b10.以下式子正確的選項是()A.一 .一B.0匸0c.一 '= D. ._ 11.設(shè)解釋R如下：論域D為實數(shù)集，a=0,f(x,y)=x-y,A(x,y):x<y.以下公式在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(x,y),x)D. ( -x)( - y)(A(x,y)A(f(x,a),a)

5、12. 設(shè)B是不含變元x的公式，謂詞公 式(- x)(A(x) t B)等價于()A. ( x)A(x) t BB. ( - x)A(x) t B(x) t BD. ( -x)A(x) t ( - x)B13. 謂詞公式(- x)(P(x,y) t (-I z)Q(x,z) A (一 y)R(x,y)中變元 x()A. 是自由變元但不是約束變元B. 既不是自由變元又不是約束變元C. 既是自由變元又是約束變元D. 是約束變元但不是自由變元14. 假設(shè)P:他聰明；Q:他用功；那么“他 雖聰明，但不用功，可符號化為()V QAn QTqQVq Q15. 以下命題公式中，為永假式的是()t (p V

6、q V r)B. (P 7 P) Tq Pc.q (q Tq) A pD.q (q Vq p) t(p Aq p)二、填空題(每空1分，共20分)16. 在一棵根樹中，僅有一個結(jié)點的入度為，稱為樹根，其余結(jié)點的入度均為。=1,2,3,4 上二元關(guān)系 R=2,4， 3, 3， 4, 2 / R的關(guān)系矩陣M中 mi4=,m34=。18. 設(shè)s,*是群，那么那么s中除夕卜，不可能有別的幕等元；假設(shè)S,*有零元，那么|s|= 。19. 設(shè)A為集合，P(A)為A的幕集，那么P(A)亠是格，假設(shè) x,y P(A), 那么x,y最大下界是 ，最小上界是。20. 設(shè)函數(shù)f:X t Y,如果對X中的任意兩個不同

7、的X1和X2,它們的象y1和 y也不同，我們說f是函數(shù)，如果ranf=Y /那么稱f是函數(shù)。21. 設(shè)R為非空集合 A上的等價關(guān)系， 其等價類記為xR。- x,y A, 假設(shè)x,y > R,貝Ux占yr的關(guān)系是，而假設(shè)x,yR,那么xrA yr=。22. 使公式(x)(y)(A(x) AB(y) = ( x)A(x) A ( y)B(y)成立的條件是 不含有y,不含有x。23. 設(shè)M(x):x 是人，D(s):x 是要死的， 貝愉題“所有的人都是要死的可符號化為(寸x),其中量詞(-x)的轄域是。24. 假設(shè) H1A H2A-A H 是，那么稱H1,H2,Hn是相容的，假設(shè)HA H2AA

8、 H是，那么稱H ,H2,Hi是不相容的。25. 判斷一個語句是否為命題，首先要看它是否為 ，然后再看它是否具有唯一的。三、計算題(共30分)26. (4分)設(shè)有向圖G=(V,E)如以下圖所示，試用鄰接矩陣方法求長度為2的路的總數(shù)和回路總數(shù)。27. (5)設(shè) A=a,b,P(A) 是 A 的幕集，二 是對稱差運算，可以驗證<P(A)，二> 是群。設(shè)n是正整數(shù)，求 (a -1 ba)"二a -nb na n28. (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

9、, 5> U I a;(1)作出偏序關(guān)系R的哈斯圖令B=1,2,3,5，求B的最大，最 小元，極大、極小元，上界，下確 界，下界，下確界。29. (6 分)求n (Pt Q)u(PQ)的主 合取范式并給出所有使命題為真的 賦值。30. (5分)設(shè)帶權(quán)無向圖 G如下，求 G 的最小生成樹 T及T的權(quán)總和，要 求寫出解的過程。31. (4 分)求公式( - x)F(x,y) t(-iy)G(x,y) V ( x)H(x)的前束范 式。四、證明題(共20分)32. (6分)設(shè)T是非平凡的無向樹，T中 度數(shù)最大的頂點有 2個，它們的度 數(shù)為k(k > 2),證明T中至少有2k-2 片樹葉。

10、33. (8分)設(shè)A是非空集合，F(xiàn)是所有從 A到A的雙射函數(shù)的集合，：是函數(shù) 復(fù)合運算。證明：F,：>是群。34. (6 分)在個體域 D=a1,a2,an中 證明等價式：(x)(A(x) t B(x)二(- x)A(x) x)B(x)五、應(yīng)用題(共15分)35. (9分)如果他是計算機系本科生或者是計算機系研究生，那么他一定 學(xué)過DELPHI語言而且學(xué)過C+語言。只要他學(xué)過 DELPHI語言或者 C+語言，那么他就會編程序。因此 如果他是計算機系本科生，那么他 就會編程序。請用命題邏輯推理方 法，證明該推理的有效結(jié)論。36. (6分)一次學(xué)術(shù)會議的理事會共有20個人參加，他們之間有的相

11、互認(rèn) 識但有的相互不認(rèn)識。但對任意兩 個人，他們各自認(rèn)識的人的數(shù)目之 和不小于20。問能否把這20個人排 在圓桌旁，使得任意一個人認(rèn)識其 旁邊的兩個人根據(jù)是什么答案：一、單項選擇題(本大題共15小題，每 小題1分，共15分)二、填空題1018. 單位元 1n yxU y20.入射 滿射21. :x r= : y r(x)B(y)23.(M(x)t D(x)M(x)tD(x)24.可滿足式永假式(或矛盾式)25.陳述句真值三、計算題1 1001 01026. M=1 0110 0112 110"22 111M =卜2 1211 011J444E E m2= 18,遲 m2=6i丄1日7

12、G中長度為2的路總數(shù)為18,長度為 2的回路總數(shù)為6。27.當(dāng) n 是偶數(shù)時，- x P(A),x n= 當(dāng)n是奇數(shù)時，- x P(A),x n=x于是：當(dāng)蘭n是偶數(shù)，(a -1b a )n二a-n b na n=一 二(a -1)nb na n=_=0當(dāng)n是-奇數(shù)時,(a-1 ba)"二-nab nna=a-1 b a二(a -1)nb nna=a-1 b a二a-1 b a =.28.(1)偏序關(guān)系R的哈斯圖為(2)B 的最大元：無，最小元：無；極大元：2, 5,極小元：1, 3下界：4,下確界4; 上界：無，上確界：無大于等于2且度最大的頂點必是分支點，于F是前提：(p V q

13、) (rtA s),(r V s)29.原式(n (P t Q)t (P>n Q) Ax y結(jié)論：p t(P-n Q)-n (P - Q)' d(Vi)證(P t Q)V (P -nQ) A ( ni =1pP(附加前提)(P -n Q)Vn (P -Q)x 1+2(y-2)+k+k=x+2y+2K-4pV qT1(n PV QVn PVnQ)A ( n從而 2(x+y-1)> x+2y+2k-4(p V q) (rA s) P(前提引入)(nPVn Q)V (P An Q)x> 2k-2r A sT1(n (P An Q) V (P An Q)33.從定義出發(fā)證明:

14、由于集合A是非rT1(P A Q)V (P An Q)空的，故顯然從A到A的雙射函數(shù)r V sT1PA (QVn Q)總是存在的，如A上恒等函數(shù)，因(r V s) tP(前提引入)PV (QAn Q)此F非空tT1(P V Q)A (P Vn命題為真的賦值是P=1,Q=1Q)P=1,Q=0 和30.令 e1=(v 1,V3),e2=(V 4,V 6)是封閉的。任一人認(rèn)識其旁邊的兩個人。e3=(v 2,v 5),e4=(V 3,V 6)(2)- f,g,h F,由函數(shù)復(fù)合運算的根據(jù)：構(gòu)造無向簡單圖 G=<V,E>,其e 5=(v 2,v 3),e6=(V 1,V 2)結(jié)合律有f ：(

15、g ：h)=(f ：g) :h故運中V=V1,V2,V20是以20個人為e7=(v 1,v 4),e8=(v 4,V 3)算：是可結(jié)合的。頂點的集合，E中的邊是假設(shè)任兩個人e9=(v 3,v 5),e10=(v 5,v 6)(3)A上的恒等函數(shù)I a也是A到A的Vi和Vj相互認(rèn)識那么在 Vi與Vj之間連令ai為ei上的權(quán)，那么雙射函數(shù)即I a F,且- f F有一條邊。36.可以把這20個人排在圓桌旁，使得a1<a2<a3<a4<a5=a6=a7=a 8<a9=a 10取 a1 的 e1 T,a 2的 a T,a3 的 e3T,a4 的 e4 T,a 5的 e5

16、T,即，T 的總權(quán)和31.原式二-|y1G(x,y °)G(x,y 1)=1+2+3+4+5=15n (- X1F(X1,y)宀V Tx2H(X2)(換名)-I X1 -I y1(F(x 1,y) 宀nV X2H(X2)- X1 - y1 n (F(x 1,y 1) tV X2H(X2)冇G(x,y 1)= _ xi _yi X2( n (F(x i,y 1)G(x,y i) V H(x»四、證明題32. 設(shè)T中有x片樹葉，y個分支點。(1)-f,g F,因為f和g都是A到A的雙射函數(shù)，故f為也是A至U A 的雙射函數(shù)，從而集合F關(guān)于運算二I A :f=f J A=f,故

17、I A 是F,:- > 中的 幺元(4)-f F,因為f是雙射函數(shù)，故其逆函數(shù)是存在的，也是A到A的雙射函數(shù)，且有f f'f-1： f=I A,因此f-1是f的逆元 由此上知F,:是群34. 證明(x)(A(x) t B(x) 二x( n A(x) V B(x)(n A(aJ V B(a") V (n A) V B(a2) V V (n A(an) V B(an) =(n A(aJ V A(a2)V Vn A(an) V (B(a 1) V B(a2) V V (B(a n) =n (A(a 1) A A(a2)A A A(an) V (n B(aJ V B) V V

18、(B(a n)n (一 x)A(x) V ( x)B(x)-V V,d(v i)是與Vi相互認(rèn)識的人的數(shù)目，由題意知- Vi,Vj V有d(v i)+d(v j) _20,于是G中存在漢密 爾頓回路。設(shè)C=V V2V20V1是G中一條漢 密爾頓回路，按這條回路的順序按 其排座位即符合要求。全國2004年4月高等教育自學(xué)考試離散數(shù)學(xué)試題課程代碼：02324局部選擇題(共15分)第一、單項選擇題(本大題共 每題1分，共15分)p, q的小項是于是T中有x+y個頂點，有x+y-1條(-x)A(x) ( x)B(x)1.以下是兩個命題變兀邊，由握手定理知 T中所有頂點的五、應(yīng)用題()度數(shù)之的35.令p

19、：他是計算機系本科生A.pAn p A qx yq :他是計算機系研究生B.n p V q' d(Vi) =2(x+y-1)。r :他學(xué)過DELPHI語言C.n pA qi ds:他學(xué)過C+語言D.n p V pV q又樹葉的度為 1，任一分支點的度t:他會編程序2.令p:今天下雪了，q：路滑，那么命15小題,題“雖然今天下雪了，但是路不滑可符號化為()A. pr qB. pVn qC. pA qD. pAn q3 .以下語句中是命題的只有()A. 1+1=10B. x+y=10C. sinx+siny<0D. x mod 3=24 .以下等值式不正確的選項是()A. n (-

20、x)A ：= ( -lx) n AB. ( -x)(B tA(x) = B( - x)A(x)C. ( x)(A(x) A B(x) = ( x)A(x) A(x)B(x)D .(-x)(-y)(A(x)tB(y)二(x)A(x)t( -y)B(y)5 .謂詞公式(x)P(x,y) A(-x)(Q(x,z) t (x)( - y)R(x,y,z)中量詞-x的轄域是()A .(- x)Q(x,z) t(x)( - y)R(x,y,z)B. Q(x,z) t ( -y)R(x,y,z)C. Q(x,z) t ( -1x)( - y)R(x,y,z)D. Q(x,z)6.設(shè)R為實數(shù)集，函數(shù)f : R

21、t R, f(x)=2 x, 那么f是( )A. 滿射函數(shù)B. 入射函數(shù)C. 雙射函數(shù)D. 非入射非滿射7 .設(shè)A=a,b,c,d, A上的等價關(guān)系R=<a,b>,<b,a>,<c,d>,<d,c> UIa,那么對應(yīng)于R的A的劃分是()A. a,b,c,dB. a,b,c,dC. a,b,c,dD. a,b,c,d8 .設(shè) A=? , B=P(P(A)，以下正確的式子是()A. ?,? BB. ?,? BC. ? , ? BD.? , ? B9.設(shè)X, Y, Z是集合，一是集合相對補運算,以下等式不正確的選項是 (A.(X-Y)- Z=X- (Y

22、 n Z)B.(X-Y)- Z=(X- Z)- YC.(X-Y)- Z=(X- Z)- (Y- Z)D.(X-Y)- Z=X- (Y U Z)10. 設(shè)*是集合A上的二元運算，稱 Z是A上關(guān)于運算*的零元，假設(shè)()A. -x wA,有 x*Z=Z*x=ZB. Z . A,且-x A 有 x*Z=Z*x=ZC. Zw A,且-x 三 A 有 x*Z=Z*x=xD. Z 三 A,且 % 二 A 有 x*Z=Z*x=Z11. 在自然數(shù)集N上，以下定義的運算中不可結(jié)合的只有()A. a*b=min(a,b)B. a*b=a+bC. a*b=GCD(a,b)(a,b 的最大公約數(shù))D. a*b=a(mo

23、d b)12. 設(shè) R 為實數(shù)集，R+=x|x RA x0,*是數(shù)的乘法運算，R, *是一個 群，那么以下集合關(guān)于數(shù)的乘法運算 構(gòu)成該群的子群的是(A. R+中的有理數(shù)B. R+中的無理數(shù)C. R+中的自然數(shù)D 1 , 2, 313. 設(shè)A,*,：是環(huán)，那么以下正確的選項是( )A. A,是交換群B. A,*是加法群C. :對*是可分配的D. *對：是可分配的14. 以下各圖不是歐拉圖的是()15. 設(shè)G是連通平面圖，G中有6個頂 點8條邊，那么G的面的數(shù)目是()A. 2個面B. 3個面C. 4個面D. 5個面第二局部非選擇題(共85分) 二、填空題(本大題共 10小題，每空 1分，共20分)

24、16. 一公式為 之充分必要條件是其析取范式之每一析取項中均必 同時包含一命題變元及其否認(rèn)；-公式為之充分必要條件是其合取范式之每一合取項中均必 同時包含一命題變元及其否認(rèn)。17 .前束范式具有形式(QM)(Q 2V2)(QnW)A ,其中 Q(1 i w n)為,A為的謂詞公式。18 .設(shè)論域是a,b,c，那么(- x)S(x)等價于命題公式; ( x )S(x)等價于命題公式。19. 設(shè)R為A上的關(guān)系，那么R的自反閉包r(R)= ,對稱閉包s(R)=。20. 某集合A上的二元關(guān)系R具有對稱性，反對稱性，自反性和傳遞性，此關(guān)系R是，其關(guān)系矩陣21. 設(shè)S, w 是一個偏序集，如果S中 的任意

25、兩個元素都有和,那么稱S關(guān)于w構(gòu)成一個格。22 .設(shè)Z是整數(shù)集，在Z上定義二元運 算*為a*b=a+b+a - b,其中+和是 數(shù)的加法和乘法，那么代數(shù)系統(tǒng) Z,*的幺元是,零元23 .如下平面圖有 2個面R和艮，其中deg(R"=, deg(R2)=24. 無向圖G具有一條歐拉回路， 當(dāng)且僅當(dāng)G是,并且所有結(jié)點的度數(shù)都是。25. 在以下圖中，結(jié)點V2的度數(shù)是 ,結(jié)點V5的度數(shù)是。三、計算題(本大題共6小題，第2627小題每題 4分，第28、30 小題每題5分，第29、31小題 每題6分，共30分)26. (4 分)求出從 A=1,2到 B=x,y 的所有函數(shù)，并指出哪些是雙射函 數(shù)

26、，哪些是滿射函數(shù)。27. 4分如果論域是集合a,b,c, 試消去給定公式中的量詞：yxx y =0。28. 5 分設(shè) A=a,b,c ，P A是A的幕集，三是集合對稱差運算。PA,二是群。在群 PA,二中，找出其幺元。 找出任一元素的逆元。求元素x使?jié)M足a二 x=b。29. 6分用等值演算法求公式pt q二Pq的主合取范式30. 5分畫出5個具有5個結(jié)點5條邊的非同構(gòu)的無向連通簡單圖。31. 6分在偏序集Z, 中，其中Z=1,2,3,4,6,8,12,14, 是 Z中的整除關(guān)系，求集合D=2,3,4,6的極大元，極小元，最大元，最小 元，最小上界和最大下界。四、證明題本大題共3小題，第3233

27、 小題每題6分，第34小題8分，共 20分32. 6分用等值演算法證明q A s t r A s t p v r s A p t q t r33. 6分設(shè)n階無向樹 G=V E中 有m條邊，證明m=r 1。34.8 分 設(shè)P=? ,1,1,2,1,2,3,是集合P上的包含關(guān)系。1 證明：P,是偏序集。2在1的根底上證明P,二 是全序集五、應(yīng)用題本大題共 2小題，第35 小題9分，第36小題6分，共15分35. 9分在謂詞邏輯中構(gòu)造下面推 理的證明：每個在學(xué)校讀書的人都 獲得知識。所以如果沒有人獲得知 識就沒有人在學(xué)校讀書。個體域： 所有人的集合36. 6 分設(shè)有 a,b,c,d,e,f,g 等

28、七 個人，a會講英語；b會講英 語、漢語；c會講英、俄語；d會 講日、漢語；e會講德語、俄語；f會講法語、日語；g會講法語、 德語。試用圖論方法安排園桌座 位，使每人都能與其身邊的人交 談。全國2005年4月高等教育自學(xué)考試離散數(shù)學(xué)試題課程代碼：02324一、單項選擇題本大題共15小題，每 小題1分，共15分在每題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫 在題后的括號內(nèi)。 錯選、多項選擇或未選均 無分。1. 以下各圖是平面圖的是 2. 設(shè)G是n個頂點的無向簡單圖，貝忡列說法不正確的選項是A. 假設(shè)G是樹，那么其邊數(shù)等于n-1B. 假設(shè)G是歐拉圖，那么G中必有割邊C. 假設(shè)G中

29、有歐拉路，那么G是連通圖，且 有零個或兩個奇度數(shù)頂點D. 假設(shè)G中任意一對頂點的度數(shù)之和大 于等于n-1，貝U G中有漢密爾頓路3. 格L是分配格的充要條件是L不含與下面哪一個選項同構(gòu)的子格A. 鏈B. 鉆石格C. 五角格D. 五角格與鉆石格4. 設(shè)G,*是有限循環(huán)群，那么以下說法不正確的選項是A. G,*的生成元是唯一的B. 有限循環(huán)群中的運算*適合交換律 中存在一元素a，使G中任一元素都由 a的幕組成D. 設(shè)a是G,*的生成元，那么對任一正 整數(shù)i，存在正整數(shù)j使a-' =aJ5. 在實數(shù)集合R上，以下定義的運算中 是可結(jié)合的只有*b=a+2b*b=a+b-2ab*b=a-b+2a

30、b*b=a-b-2ab6. 設(shè)群G=A,*中,A的元素個數(shù)大于1，假設(shè)元素a A的逆元素為b A,那么a*b的運算結(jié)果是中零元素中幺元7. 非空集合A上的二元關(guān)系R假設(shè)是自反 和對稱的，那么R是A. 偏序關(guān)系b.等價關(guān)系c.相容關(guān)系D. 擬序關(guān)系8. 下面的圖是A= 1,2,3 上關(guān)系R的 關(guān)系圖G(R),從G(R)可判斷R所具有的 性質(zhì)是()1。2。3。A. 自反，對稱，傳遞B. 反自反，非對稱C. 反自反，對稱，非傳遞D. 反自反，對稱，反對稱，傳遞9. 設(shè) A= 1, 2, 3, B= a,b ,以下二元關(guān)系R為A至U B的函數(shù)的是()=<1,a>,<2,a>,&

31、lt;3,a>=<1,a>,<2,b> =<1,a>,<1,b>,<2,a>,<3,a>=<1,b>,<2,a>,<3,b>,<1,a>10. 設(shè)0為空集，P(x)是集合x的幕集, 以下論斷不正確的選項是()A.B. C.C. 0 P( 0 ),0 J P( 0 )0 P ( 0 ), 0 P ( 0 )0 P (P ( 0 ), 0 P (P ( 0 )0 P( P( 0 ) , 0 GP( P( 0 )11. 利用謂詞的約束變元改名規(guī)那么和自 由變元代入規(guī)那么，可將

32、如下公式：(-x)(p(x,y) > ( z)Q(x,z)(-y)R(x,y)改寫成()A.(z)(p(z, y)；( y)Q(z,y)(_s)R(z,s)B.(z)(p(z, y) ( s)Q(x,s)(y)R(z,y)C.(_x)(p(x,m) > ( y)Q(x,y)(_m)R(m,m)D.(一x)(p(y,y)； ( y)Q(x,y)(一s)R(y,s)(-x)( y)(x y =1)(y)(-x)(x y =x) (x)(y)( z)(x y =z)12. 設(shè)論域為整數(shù)集，以下謂詞公式中 真值為假的是()A. (-x)( y)(x y =0)B.C.D.13. 在命題演算

33、中，語句為真為假的一 種性質(zhì)稱為()A. 真值B. 陳述句C. 命題D. 謂詞14. 設(shè)P:明天天晴；q：我去爬山；那 么“除非明天天晴，否那么我不去爬山。 可符號化為(A. p qB. _p-qC.p I, qD. _p-15.(以下命題公式是永真式的是)A. (p一p) q2個結(jié)3，3個那么該樹B. (p；q) qC. (p q) qD. (p p) (p、一p)二、填空題(本大題共10小題，每空1 分，共20分)請在每題的空格中填上正確答案。錯填、不填均無分。16. 棵有6個葉結(jié)點的完全二叉樹，有個內(nèi)點；而假設(shè)一棵樹有點度數(shù)為2, 一個結(jié)點度數(shù)為 結(jié)點度數(shù)為4，其余是葉結(jié)點， 有個葉結(jié)點

34、。17. 在一棵根樹中，有且只有一個結(jié)點的入度為 ，其余所有結(jié)點的入度均為。18. 設(shè)<S, w >是格，其中一個命題 P是(a A c)。a< (a V b) A (a V c),貝U P的對偶命題 是 a(a A b)19. 設(shè)Z是整數(shù)集，+是整數(shù)加法運算，那么<Z,+>是群，其幺元是 ,對任一整數(shù)i,其逆元是。20. 當(dāng)f:X t Y是函數(shù)時，f有逆函數(shù)，且f -1。f=21. 設(shè)E=1,2,3,4,5,6,A=1,4,B=1,2,3,C=2,4,那么(AQ B) A C=,幕集 P(AA B) A C)=22. 設(shè) 論域(-lx)P(x)：-23.,(1o

35、D=a,b, 那么 -x)( y)Q(x,y式-x)A(不公(- x)( - y)(A(x)- B(y)(x) V (- y)B(y)成立的條件是.含有y, 不含有x。24. 由命題變元及其否認(rèn)所組成的有限個析取式的合取式稱為 ，由命題變元及其否認(rèn)所組成的有限個合取式 的析取式稱為。25. 不包含的命題叫做原子命題，包含的命題稱為復(fù)合命題。三、計算題(本大題共7小題，第26、 28小題每題5分，第27、31小 題每題7分，第29、30小題每 小題8分，第32小題9分，共49 分)26. 用等值演算法，求 PV (QA R)的主 析取范式，并按P, Q R順序，寫成編 碼形式。27. 設(shè)A=1,

36、2,3，給定 A上二元關(guān)系 R=<1,1>,<1,2>,<2,3>,求 r(R),s(R) 和 t(R)。28. 求公式(x)(f (x)(y)G(x,y,z) ( z)H(x,y,z)的前束范式。29. 對如下有向圖 D,求D中長度為4 的路有多少條其中回路有多少條30. 設(shè) A=a,abc,bc,bcd,bd ，定義 A上二元關(guān)系R=<x,y>|x,y A且字符串x包含于字符串 y中，即R=IaU <a,abc>,<bc,abc>,<bc,bcd> ，可以 驗證R是A上偏序關(guān)系。 作出R的哈斯圖 向R中最少

37、添加幾個序偶可使之成 為等價關(guān)系求出該等價關(guān)系所確定的 集合A的劃分。31. 某科研所要從3個工程A B、C中 選擇12個工程上馬，由于某種原因，立項時要滿足以下條件：(1)假設(shè)A上，那么C也要上；假設(shè)B上，貝U C不能上；假設(shè)C不上，那么A或B可以上。請找出所有的立項方案32. 設(shè)有6個城市Vi, V2,，V6,它們之間有輸油管連通，其布置如以下圖,S i(數(shù)字)中S為邊的編號，括號內(nèi)數(shù)字為邊的權(quán)，它 是兩城市間的矩離，為了保衛(wèi)油管不受 破壞，在每段油管間派一連士兵看守， 為保證每個城市石油的正常供給最少 需多少連士兵看守輸油管道總長度越 短，士兵越好防守。求他們看守管道的最短的總長度。(要

38、求寫出求解過程)四、證明題(本大題共2小題，每題8分，共16分)33. 證明(- x) (P(x) t Q(x)卜 (-x)P(x) - x)Q(x)34. 證明當(dāng)每個結(jié)點的度數(shù)大于等于3時，不存在有 7條邊的連通簡單平面 圖。D (pTnA0x) aB(x)= (X/x)A(x) x/(XZx)B(A) RoS全國2006年4月高等教育自學(xué)考試離散數(shù)學(xué)試題課程代碼：02324一、單項選擇題(本大題共15小題，每題1分，共15分) 在每題列出的四個備選項中只有 一個是符合題目要求的，請將其代 碼填寫在題后的括號內(nèi)。錯選、多 選或未選均無分。1 .以下命題公式為重言式的是( )A. pT (p

39、V q)C. qAn q2.以下語句中不是命題的只有( )A. 這個語句是假的。(x)(y)(P(x,y)Q(z) > ( y)P(y,z)C. 飛碟來自地球外的星球。3. 設(shè)p:我很累，q：我去學(xué)習(xí)，命題:“除非我很累，否那么我就去學(xué)習(xí) 的符號化正確的選項是()A. n p A qB. n pt qC. n p r qD. p Tn q4. 以下等價式正確的選項是()A. n ( x)A：= ( x)n AB. (-x)( -y)A：= ( x)( -y)AC. n (x)A：= ( x) n AD B- (p Vn p) tq.5. 在公式中變元 y是()A. B自由變元B. 約束變

40、元C. D既是石頭都可練成是約束變元D. 既不是自由變元，又不是約束變元6.設(shè) A=1,2,3 ,A上二元關(guān)系 S=<1, 1>, <1, 2>, <3, 2>, <3, 3>, 那么S是()A. 自反關(guān)系C. 對稱關(guān)系7 .設(shè)集合X為人的全體，在 X上定義 關(guān)系 R S為 R=<a, b|a , b XA a 是 b 的父親, S=<a, b>|a , b XA a是b的母親，那么關(guān)系 <a , b>|a , b xA a 是 b 的祖母 的表達式為()C. S . R&設(shè)A是正整數(shù)集，R=(x , y)|

41、x , y AA x+3y=12，貝U RA (2 , 3,4, 6 X 2 , 3, 4 , 6)=()A.OB.<3 , 3>C.<3 , 3>, <6, 2>D.<3 , 3>, <6, 2>, <9,1>9.以下式子不正確的選項是()A.(A-B)-C=(A-C)-BC.(A-B)-C=(A-C)-(B-C)10.卜列命題止確的是()A.1 , 2 1 , 2 , 1 ,2 , 3,1B.1,2工1,1,2 ,1,2 ,3,2C.1 , 2 1 , 2 , 1,2D.1 , 2 1 , 2 , 2 , 1,2 ,3

42、11 .在以下代數(shù)系統(tǒng)中，不是環(huán)的只有( )A. Z, +, *)，其中Z為整數(shù)集，+, *分別為整數(shù)加法和乘法。B. (Q, +, *)，其中Q為有理數(shù)集，+,*分別為有理數(shù)加法和乘法。C. R, +, *，其中R為實數(shù)集，+為實數(shù)加法，a*b=a+2b。D. M (R) , +, *，其中 M(R)為實數(shù)集nxn階矩陣結(jié)合，+, *是矩陣 加法和乘法。12.以下整數(shù)集對于整除關(guān)系都構(gòu)成偏 序集，而能構(gòu)成格的是()A.1 ,2 ,3 ,4 , 5B.1 ,2 ,3 ,6 , 12C.2,3 ,7D.1 ,2 ,3 ,713.結(jié)點數(shù)為奇，數(shù)且所有結(jié)點的度數(shù)也為奇數(shù)的連通圖必定是()A. 歐拉圖

43、B. 漢密爾頓圖C. 非平面圖D. 不存在的14.無向圖G是歐拉圖當(dāng)且僅當(dāng) G是連通的且()A. G中各頂點的度數(shù)均相等B. G中各頂點的度數(shù)之和為偶數(shù)C. G中各頂點的度數(shù)均為偶數(shù)D. G中各頂點的度數(shù)均為奇數(shù)15. 平面圖(如下)的三個面的次數(shù)分別是()B. (A-B)-C=A-(B U C)D. A-(B U C)=(A-B) U CA. 11, 3, 4 B . 11, 3, 5C. 12, 3, 6 D . 10, 4, 3二、填空題(本大題共 10小題，每小題2分，共20分)16. 求一個公式的主析取或主合取范式的方法，有法和法。17. 給定謂詞合式公式 A,其中一局部公式形式為(

44、-x )B(x)或(x)B(x)，那么量詞-， 后面所跟的x稱為，而稱B為相應(yīng)量詞的。18. 設(shè)X, U, V, Y都是實數(shù)集，f1： X tU,且 f l(x) tex; f 2： URV,且 f2(u) = u (1+u); f 3: VtY，且f3(V)= C0SV。那么 f 3 ：f 2 ：f 1 的定義 域是,而復(fù)合函數(shù)(f 3 of 2 of 1 )(x)= 。19.集合 X=a ,b ,c , d上二兀關(guān)系R=<a , b> ,<a ,c> , <a, d>, <b ,c>, <b, d> ,<e,d,那么R的自反

45、閉包r(R)=,對稱閉包 s(R)=。20. G=<l ,-1 ,i , -i , >(其中i= . -1 ,是數(shù)的乘法)是群，那么-l的階是;i的階是。21. 對代數(shù)系統(tǒng)S, *，其中*是S上 的二元運算，假設(shè) a, b S,且對任 意的 x S,都有 a*x=x*a=x , b*x=x*b=b ,那么稱a為運算“ * 的，稱b為運算“ * 的22 .設(shè)S, *是群，那么S, *滿足結(jié)合律和;假設(shè)丨S| l , S中不可能有。23. 寫出如右有向圖的一條初級回路：，其長度是。24. 一個且的無向圖稱為樹。25. 在簡單無向圖 G=V E中,如果V中的每個結(jié)點都與其余的所有結(jié)點鄰接

46、，那么該圖稱為,如果V有n個結(jié)點，那么它還是 度正那么圖。三、計算題(本大題共5小題，第26、27題各5分，第28、29題各6分，第30題8分，共30分)26. 假設(shè)集合 A=a, b , c的幕集為 P(A)，集合 B= Q , O 的幕集為 P(B),求 P(A) n P(B)。27. 構(gòu)造命題公式(p t (q A r) tp 的真值表。28. 求圖G= V, E的可達矩陣，其中 V= V1,v 2,v 3,v 4E = (v 1,v 2), (v 2,v 3), (v 2,v 4), (v 3,V 2), (v 3,v 4), (v 3,v1), (v 4,v 1) 29. 求以下公式

47、的主析取范式和主合取 范式：(PA Q V(n PA R)30. 設(shè) A= 2, 3, 4, 6, 8, 12, 24,R為A上整除關(guān)系，試畫A,只勺 哈斯圖，并求A中的最大元，最小 元，極大元，極小元。四、證明題(本大題共 3小題，第31、 32小題各6分，第33題8分，共20分)31 設(shè)M是偶數(shù)集，+和是數(shù)的加、乘運算，證明<M+, >是一個環(huán)。32 設(shè)R是集合X上的二元關(guān)系，證明R是X上傳遞關(guān)系當(dāng)且僅當(dāng) R 迅二 R。33 .設(shè)G是簡單平面圖，G有n個頂點m條邊，且m<3Q證明G中存在一 項點 v,d (v) < 4。五、應(yīng)用題(本大題共 2小題，第34 題6分，

48、第35題9分，共15分)34. 判斷下面推理是否正確，并證明你 的結(jié)論。如果小王今天家里有事，那么他不會 來開會。如果小張今天看到小王， 那么小王今天來開會了。 小張今天看 到小王。所以小王今天家里沒事。35. 有6個村莊V , i=l , 2,，6欲修建道路使村村可通?，F(xiàn)已有修建 方案如下帶權(quán)無向圖所示， 其中邊 表示道路，邊上的數(shù)字表示修建該 道路所需費用，問應(yīng)選擇修建哪些 道路可使得任二個村莊之間是可 通的且總的修建費用最低要求寫 出求解過程，畫出符合要求的最低 費用的道路網(wǎng)絡(luò)圖并計算其費用。C.全國2007年4月高等教育自 學(xué)考試 離散數(shù)學(xué)試題課程代碼：02324一、單項選擇題(本大題

49、共15小題,每題1分，共15分)在每題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1 .以下命題公式中不.是重言式的是( )A. Pf (q t r) B . 廠(q p)C. pf (p f P)D. (p f (q f r)(q f (p f r)2 .以下語句中為命題的是()A. 這朵花是誰的B. 這朵花真美麗??！C. 這朵花是你的嗎D. 這朵花是他的。3 .設(shè)個體域是整數(shù)集，那么以下命題的真值為真的是()A. yx(x y=1)B. xy (x yz 0)D.4.xy (x y=y2) yx(x y=x2)關(guān)于謂詞公式(x)Q(y,z) A (x)p(x,y), 中錯誤的選項是(y)(P(x,y) a下面的描述)A. (x)的轄域是(y) (P( x,y ) A Q(y,z)B.C.D.5.A.B.C.D.6.A.C.