離散數學 ( 第1次 )

1、第1次作業(yè)一、單項選擇題（本大題共30分，共 15 小題，每小題 2 分）1. 圖G所示平面圖deg(R3)為A. 4B. 5C. 6D. 32. 在完全m叉樹中，若樹葉數為t，分枝點數為i，則有（） 。A. (m-1)i<t-1  B. (m-1)i>t-1 C. (m-1)i=t-1D. (m-1)it-13. 命題a）：如果天下雨，我不去。寫出命題a）的逆換式      。A. 如果我不去，天下雨。B. 如果我去，天下雨。C. 如果天下雨，我去。D. 如果天不下雨，我去。4. 設無向圖中有6條邊，

2、3度與5度頂點各1個，其余頂點都是2度點，問該圖有多少個頂點（）A. 5B. 4C. 2D. 65. 假設A=a,b,c,d,考慮子集S=a,b,b,c,d，則下列選項正確的是（ ）。 A. S是A的覆蓋B. S是A的劃分C. S既不是劃分也不是覆蓋D. 以上選項都不正確6. 沒有不犯錯誤的人。M(x)：x為人。F（x）：x犯錯誤。則命題可表示為（ ）。A. (x)(M(x)F(x)B. (x)(M(x)F(x)C. （x）(M(x)F(x) D. (x)(M(x)F(x)7. 命題邏輯演繹的CP規(guī)則為（）A. 在推演過程中可隨便使用前提B. 在推演過程中可隨便使用前面演繹出的某些公

3、式的邏輯結果C. 如果要演繹出的公式為BC形式，那么將B作為前提，演繹出CD. 設(A)是含公式A的命題公式，B<=>A，則可以用B替換(A)中的A8. 設G是有6個結點的完全圖，從G中刪去（）條邊，則得到樹。A. 6B. 9C. 10D. 159. 設A、B兩個集合，當（ ）時A-B=B。 A. A=B B. ABC. BAD. A=B=10. 設U=1，2，3，4，5，A=2，4，B=4，3，5，C=2，5，3，確定集合(A-C)-B = （）。A. 1,4 B. 2,3,4,5 C. 4D. 11. 下圖的最小生成樹的權為（）。A. 40

4、0; B. 44C. 48D. 5212. 對偶式為PQ表達式是      。A. PQB. PQC. PQD. PQ13. 下列語句是命題，并且真值為0的是（）A. 雪式白的。B. 1+2>4。C. 天氣真好啊！D. 我正在說謊。14. 如果有限個數的乘積為零，那么至少有一個因子等于零。N(x)：x是有限個數的乘積。Z(y)：y為0。P（x）：x的乘積為0 。F（y）：y為乘積中的一個因子則命題可表示為（ ）。A. (x)(N(x)P(x)(y)(F(y)(Z(y)B. (x)(N(x)P(x)(y)(F(y)(Z(y)C.

5、(x)(N(x)P(x)(y)(F(y)(Z(y)D. (x)(N(x)P(x)(y)(F(y)(Z(y)15. 設A、B、C是任意集合，判斷下述論斷是否正確，并將正確的題號填入括號內（ ）。A. 若AB=AC，則 B=C  B. 若AB=AC ，則 B=CC. 若A-B=A-C，則 B=C D. 若A=B，則 A=B 二、多項選擇題（本大題共20分，共 5 小題，每小題 4 分）1. 兩個命題變元P和Q生成的4個小項為：      。A. PQB. PQC. PQD. PQ 2. 下圖是（）。A. 是強連通的 &

6、#160;B. 是弱連通的C. 是單側連通的 D. 是不連通的3.   下列說法正確的是（ ）A. 設<Z,+>是整數加法群，令f: n-n, nZ，則f是Z的一個自同構映射。B. 設G是一個Abel群，令 f: aa(-1) ( aG)，則f是G的一個自同構映射。C. 設<R ,>是實數乘法群，<R,+>是實數加法群，令f: x5x，則f是R的一個滿同態(tài)映射D. A、B、C都是正確的。4. 函數f：R×RR×R,f(<x，y>)=<x+y，x-y>是(   )函數。A. 入射B. 滿

7、射 C. 雙射 D. 以上答案都不對5. 設A=1,2,3，則集合A上的關系R=<1,1>,<1,3>,<2,1>,<2,3>是（    ）關系；A. 自反B. 反自反C. 不是自反D. 不是反自反三、判斷題（本大題共20分，共 10 小題，每小題 2 分）1. 判斷對錯：集合2,3,4，是無限集（ ）。2. 設G是一個聯(lián)結詞的集合，若任意一個命題公式都可用G中聯(lián)結詞構成的公式來表示，則稱G為最小聯(lián)結詞組。3. 公式xP(x)yQ(x,y)的前束范式是xy(P(x)Q(x,y)。4. 判斷對錯。一個謂詞公式

8、wff A,如果在一種賦值下為假，則稱該wff A為不可滿足的。5. 下圖中（c）和（d）是根樹6. 設fx,y1,3,5 定義為f(x)=1,f(y)=5，則這個函數是入射函數。7. 設集合A=216，243，357，648.定義A上的關系 R=x,y|x,yA，且x與y中至少有一個相同數字。 則R是A上的一個相容關系，R不是等價關系。 8. 自反（對稱、傳遞）閉包是包含R的最小自反（對稱、傳遞）關系。（ ）9. 設X=1,2,3,4,Y=1,2,3,4,5,Z=1,2,3, f:XY,f=, g:YZ,g=,，則g°f=,。 10. 設R是由A=1,2,3,4 到B=2,3,4

9、的關系，S是由B到C=3,5,6的關系，分別定義為： R=a+b=6=, S=b整除c=, 于是復合關系R°S=,。 四、計算題（本大題共20分，共 4 小題，每小題 5 分）1.     設f,g均為實函數，f(x)=2x+1 ,   g(x)=x2+1。求f°g  ,   g°f  ,   f°f  ,   g°g   。      2. 設集合A=1,2,3,4，A上的二元關系R=(x,y)|x,yA

10、,且xy,求R的關系圖與關系矩陣3.  試將公式P（PQ）化為析取范式和合取范式：4. 設全集合E=a，b，c，d，e，A=a，d，B=a，b，e，C=b，d，求下列集合：(1)AB；        （2）（AB）C；（3）A（BC）；（4）(A)(B)五、證明題（本大題共10分，共 2 小題，每小題 5 分）1. 符號化下列命題并推證其結論：科學家都是勤奮的。每個勤奮又身體健康的人在事業(yè)中都會獲得成功。存在著身體健康的科學家。所以存在著事業(yè)獲得成功的人或事業(yè)半途而廢的人。2. 設整數集Z上的二元關系R定義如下：R=<x,y>|x,

11、yZ,(x-y)/2是整數，證明R在Z上是自反的。答案：一、單項選擇題（30分，共 15 題，每小題 2 分）1. B 2. C 3. A 4. B 5. A 6. A 7. C 8. C 9. D 10. D 11. C 12. B 13. B 14. B 15. D 二、多項選擇題（20分，共 5 題，每小題 4 分）1. ABCD 2. BC 3. AB 4. ABC 5. CD 三、判斷題（20分，共 10 題，每小題 2 分）1. 2. × 3. × 4. × 5. 6. 7. 8. 9. 10. 四、計算題（20分，共 4 題，每小題 5 分）1. 參

12、考答案：f°g(x)=2(x2+1)=2x2+3     g°f(x)=(x2+1)2+1=4x2+4x+2     f°f(x)=2(2x+1)+1=4x+3     g°g(x)=(x2+1)2+1=x4+2x2+2所以f°g=<x,2x2+3>|xRg°f=<x,4x2+4x+2>|xRf°f=<x,4x+3>xRg°g=<x,x4+2x2+2>|xR解題方案：評分標準：2

13、. 參考答案：R=(x,y)x,yA,且xy=(1,1),(2,1),(3,1),(4,1),(2,2),(3,2),(4,2),(3,3),(4,3),(4,4)  R的關系圖如圖3-1所示。解題方案：評分標準：3. 參考答案： （PQ）（PQ）=(（PQ）（PQ）)(（PQ）（PQ）)(等值律)=(（PQ）（PQ）) (（PQ）（PQ）)  (蘊涵律) =（PQ）(PQ)           (分配律) 合取范式=(PP) (PQ)(QP)(QQ)   (分配律)析取范式解題方案：評分標準：4. 參考答案：（1）AB=a，dc，d=d.(2) （AB）C=aa,c,e=