電大歷年離散數(shù)學(xué)試題匯總

1、計算機科學(xué)與技術(shù)專業(yè)級第二學(xué)期離散數(shù)學(xué)試題2012年1月、單項選擇題（每小題 3分，本題共15分）1. C 2. C 3. B4. A 5. D1 .若集合A的元素個數(shù)為10,則其哥集的元素個數(shù)為（）.A . 10B. 100C. 1024D. 12 .設(shè)a, b , 1,2 , R，R2, R3是 A到 B 的二元關(guān)系，且 R=, , R2=, , , R3=, ,則（）是從 A 到 B 的函數(shù).A . R1 和 R2B . R2C. R3D, R1 和 R33 .設(shè)1,2, 3, 4, 5, 6, 7, 8 , R是A上的整除關(guān)系，2, 4, 6,則集合B的最大元、最小元、上界、下 界依次

2、為（）.A. 8、2、8、2C. 6、2、6、2B.無、2、無、2D. 8、1、6、1）時，圖G中存在歐拉回路.D. m為偶數(shù)4.若完全圖G中有n個結(jié)點（n2）, m條邊，則當(dāng)（A. n為奇數(shù)B. n為偶數(shù)C. m為奇數(shù)5.已知圖G的鄰接矩陣為0011則G有（）.A. 6點，8邊C. 5點，8邊二、填空題（每小題o o 1 r00010011010111108. 6點，6邊D. 5點，6邊3分，本題共15分）6 .設(shè)集合A=a,那么集合 A的募集是 ,a7,若Ri和&是A上的對稱關(guān)系，則R1UR2,R1AR2,R12,R21中對稱關(guān)系有 4 個.8 .設(shè)圖G是有5個結(jié)點的連通圖，結(jié)點度數(shù)總和為

3、10,則可從G中刪去 1條邊后使之變成樹.9 .設(shè)連通平面圖 G的結(jié)點數(shù)為5,邊數(shù)為6,則面數(shù)為 310 .設(shè)個體域D = a, b,則謂詞公式（Vx）（A（x） AB （ x ）消去量詞后的等值式為 （A （a）加（b）/A （a） AB （b）三、邏輯公式翻譯（每小題6分，本題共12分）11 .將語句“今天有聯(lián)歡活動，明天有文藝晚會.”翻譯成命題公式.設(shè)P：今天有聯(lián)歡活動， Q:明天有文藝晚會，（2分）P/Q.（6分）12.將語句“如果小王來，則小李去.”翻譯成命題公式.設(shè)P:小王來，Q:小李去(2分)P 一 Q.(6分)四、判斷說明題(每小題7分，本題共14分) 判斷下列各題正誤，并說明

4、理由.13.若偏序集的哈斯圖如圖一所示，則集合A的最大元為a,極小元不存在.錯誤.對于集合A的任意元素x,均有wR (或)，所以a是集合A中的最大元.(5分)但按照極小元的定義，在集合 A中均是極小元.(7分)14. n PA (P-n Q) V P 為永假式.錯誤.(3分)n PA (P-n Q) V P是由PA ( P-n Q)與P組成的析取式，如果P的值為真，則1PA ( P-n Q) V P為真，(5分)如果P的值為假，則IP與P-n Q為真，即PA ( P-n Q)為真，也即1PA ( P-n Q) V P為真，所以PA (P - n Q) VP是永真式.(7分)另種說明：n PA

5、(P-n Q) V P是由PA ( P-n Q)與P組成的析取式，只要其中一項為真，則整個公式為真.(5分)可以看到，不論P的值為真或為假，1 PA ( P- Q)與P總有一個為真，所以PA (P - n Q) VP是永真式.(7分)或用等價演算PA (P-n Q) VPuT五.計算題(每小題12分，本題共36分)15.設(shè)集合1 , 2, 3, 4 , , y三A; -1 或 x-0,試(1)寫出R的有序?qū)Ρ硎荆?2)畫出R的關(guān)系圖；(3)說明R滿足自反性，不滿足傳遞性.15. (1) ,(2)關(guān)系圖如圖二：(3分)(6分)(3)因為,均屬于R,即A的每個元素構(gòu)成的有序?qū)赗中，故R在A上是

6、自反的.(9分)因有2,3與3,4屬于R,但2,4不屬于R,所以R在A上不是傳遞的.(12 分)16.設(shè)圖 , vi, v2, v3, v4,v5), (V1, V2), (V1,V3), (V2,V4), (V3, V5), (V4, V5) ,試(1)畫出G的圖形表示；(2)寫出其鄰接矩陣；(3)求出每個結(jié)點的度數(shù)；(4)畫出圖G的補圖的圖形.16. (1)關(guān)系圖如圖三：(3分)(2)鄰接矩陣ro110L0(3) (vi)=2(V2)=2(V3)=2(V4)=2(V5)=2(4)補圖如圖四110 010 0 100 0 0 110 0 10 110(6分)(9分)(12 分)17 .求PT

7、Q A R的合取范式與主析取范式.P- ( RA Q)Ur PV (RA Q)(4 分)U (n PVQ) A (n PVR)(合取范式)(6 分)Pf ( RA Q)，PV (RA Q)PA (n QVQ) V (RAQ)(7 分)” PAn Q) V(n PAQ)V(RAQ)(8 分)(h PAn Q)A (n RVR) V(n PAQ)V(RA Q)(9 分)U 6 PAn QAn R)V (n PAn QA R) V (n PA Q) V (RA Q)(10 分)U 6 PAn QAn R)V (n PAn QA R) V (n PA Q)A(n RVR)V(RAQ)U (n PAn

8、QAn R)V (n PAn QA R) V (n PA QAn R) V (n PA QA R)V (RA Q)U 6 PAn Q R)V 6 PAn QA R) V (n PA QAn R) V6 P A Q A R) V (n P V P)A (RA Q)U 6 PAn QAn R)V 6 PAn QA R) V (n PA QAn R) V6 PAQA R)V (PA RA Q)(主析取范式)(12 分)說明：此題解法步驟多樣，若能按正確步驟求得結(jié)果，均可給分.六、證明題(本題共8分)18 .設(shè)連通無向圖 G有14條邊，3個4度頂點，4個3度頂點，其它頂點的度數(shù)均小于3,試說明G中可能

9、有的頂點數(shù).證明：可利用數(shù)列可圖化及握手定理解答頂點度數(shù)和為2x14=28,(2分)28- (3M4+4M3) =4,則知其他頂點度數(shù)和為 4,(4分)對于有限圖，若無零度頂點，則除4度及3度頂點外，可能的頂點情況有：2個2度點；1個2度點和2個1度點；4個1度點，(6分)即對應(yīng)圖的頂點數(shù)分別至少為9、10、11.(8分)2011年7月、單項選擇題(每小題 3分，本題共15分)1. A2. C 3. C4. D 5. BA.無向圖 B.無向圖 C.無向圖 D.無向圖B. 1 , 1D. 。，1A. n (3x)( A(x) - n B(x)C. n (三x)( A(x)AB(x)二、填空題(每

10、小題3分，本題共6.命題公式P vP的真值是 B. n ( x)( A(x) An B(x)D. (Vx)( A(x) A B(x)15分)真(或T,或1)1.若集合1 , 1 , 2 , 1 , 2,則下列表述正確的是().A . 2三 AB, 1 , 2匚 A1 . 1 乏AD. 2 U A2 .設(shè)G為無向圖，則下列結(jié)論成立的是 ().G的結(jié)點的度數(shù)等于邊數(shù)的兩倍.G的結(jié)點的度數(shù)等于邊數(shù).G的結(jié)點的度數(shù)之和等于邊數(shù)的兩倍.G的結(jié)點的度數(shù)之和等于邊數(shù).3 .圖G如圖一所示，以下說法正確的是A. (a, b)是邊割集B. a, c是點割集C. d是點割集D. (c, d)是邊割集4 .設(shè)集合1

11、,則A的哥集為().A. 1C. 0, 15.設(shè)A(x): x是人，B(x): x犯錯誤，則命題“沒有不犯錯誤的人”可符號化為().7 .若無向圖T是連通的，則 T的結(jié)點數(shù)v與邊數(shù)e滿足關(guān)系1 時,T是樹.8 .無向圖G是歐拉圖的充分必要條件是G是連通的且結(jié)點度數(shù)都是偶數(shù)9 .設(shè)集合1 , 2上的關(guān)系R=,則在R中僅需加入一個元素,就可使新得到的關(guān)系為自反的.10 . （X?X）（P（x）-R（y） VS（z）中的約束變元有 x.三、邏輯公式翻譯（每小題6分，本題共12分）11 .將語句“雪是黑色的.”翻譯成命題公式.設(shè)P:雪是黑色的，（2分）則命題公式為：P.（6分）12 .將語句“如果明天

12、下雨，則我們就在室內(nèi)上體育課.”翻譯成命題公式.設(shè)P:如果明天下雨， Q:我們在室內(nèi)上體育課，（2分）(6分)四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由.13 .設(shè)集合1 , 2, 3 , 4,從A到B的關(guān)系為 , 錯誤.,則f是A到B的函數(shù).因為A中元素1有B中兩個不同的元素與之對應(yīng)，故14 .設(shè) G 正確.因G是一是一個連通平面圖，有 5個結(jié)點9條邊，則個連通平面圖，滿足歐拉定理，有 2f不是A到B的函數(shù).G有6個面.（3分）（7分）(3分)所以 2- （） =2- （5-9） =6五.計算題（每小題 12分，本題共36分）15.試求出P一（RAQ）的合取范式.

13、(7分)P- (RAQ) 仁仁P V R) A16.設(shè)1, 1,2(1) (AHB)(1) (AH B)P V (RAQ)(1 PVQ)(合取范式),1, 1,2, 2,試計算(2) (AUB)=1(3) (AAB) 4(6分)(12 分)(2) (AUB) =1,2, 1, 2, 1,2(3) (APB) A =0（4分）（8分）（12 分）則命題公式為：PtQ.17 .試畫一棵帶權(quán)為 2, 3, 3, 4, 5,的最優(yōu)二叉樹，并計算該最優(yōu)二叉樹的權(quán). 最優(yōu)二叉樹如圖二所示.1710(10 分)權(quán)為2父3+3父3+3父2+4父2+5父2=39（12分）六、證明題（本題共 8分）18 .試證明

14、：若 R與S是集合A上的對稱關(guān)系，則 RAS也是集合A上的對稱關(guān)系.證明：設(shè) 甲,y三A,因為R對稱，所以若wR,貝U 三R. 因為S對稱，所以若WS,貝US.于是若 三RA S 貝UwR且wS即 ER且 三S也即 RAS,故RAS是對稱的.（2分）（4分）（6分）（8分）中央廣播電視大學(xué)2010 2011學(xué)年度第一學(xué)期“開放本科”期末考試離散數(shù)學(xué)（本）試題、單項選擇題（每小題 3分，本題共15分）1. A 2. D 3. B 4. D5. C2011年1月1 .若集合A= a, 1,則下列表述正確的是（）.A. 1三AB. 11AC. a三AD. 0WA2.設(shè)圖G = , vWV,則下列結(jié)論

15、成立的是().A. (v)=2 |E IB. (v)= |e|C.工 deg(v) = E v V3.如圖一所示，以下說法正確的是（A .C.（e, c）是割邊（b, a）是割邊B.D.D. z deg(v) = 2Ev ：:V).(d, e)是割邊(b, c)是割邊4.命題公式（A . PC. （PVP）5.下列等價公式成立的為（a . P,quP*Q).B. (PA Q)D. (PVQ).B. QQ-PPP-QQC. FPbQcQD. PwPuQ二、填空題（每小題 3分，本題共15分）6 .設(shè)集合0,1,2 , 1,2, 3, 4, , R是A到B的二元關(guān)系,R=x,y）|xW A且yW

16、B且x,yw A B則 R 的有序?qū)蠟?, , , .7 .設(shè)G是連通平面圖，v, e, r分別表示 G的結(jié)點數(shù)，邊數(shù)和面數(shù)，則 v, e和r滿足的關(guān)系式 28 .設(shè)G=是有20個結(jié)點，25條邊的連通圖，則從 G中刪去 6 條邊,可以確定圖 G的一棵生成樹.9.無向圖G存在歐拉回路，當(dāng)且僅當(dāng) G所有結(jié)點的度數(shù)全為偶數(shù)且連通10.設(shè)個體域D = 1,2,則謂詞公式 VxA（x）消去量詞后的等值式為A A(2)三、邏輯公式翻譯（每小題6分，本題共12分）11.將語句“如果小李學(xué)習(xí)努力，那么他就會取得好成績.”翻譯成命題公式.12.將語句“小張學(xué)習(xí)努力,小王取得好成績.”翻譯成命題公式.11 .

17、設(shè)P:小李學(xué)習(xí)努力, PtQ.12 .設(shè)P:小張學(xué)習(xí)努力,Q:小李會取得好成績,Q：小王取得好成績,(2分)(6分)(2分)(6分)四、判斷說明題（每小題7分，本題共14分） 判斷下列各題正誤，并說明理由13 .如果R1和R2是A上的自反關(guān)系，則 Re2是自反的.14 .如圖二所示的圖中存在一條歐拉回路.圖(3分)（7分）（3分）（7分）五.計算題（每小題12分，本題共36分)15.設(shè)2,1,2 , 1,1,2，試計算(1) (A-B);(AAB);16.設(shè), V1, V2（1）給出G的圖形表示；（3）求出每個結(jié)點的度數(shù);V4, V5(2)(3) AX B., ( V13), (V23), (

18、V24), (V34) , (V35),試 寫出其鄰接矩陣；（4）畫出其補圖的圖形.13 .正確.R1 和 R2是自反的， VxWA, R Ri, WR2,則 R1 - R2,所以Rcr2是自反的.14 .正確.因為圖G為連通的，且其中每個頂點的度數(shù)為偶數(shù).17.設(shè)謂詞公式 t(A(x, y) AVzB(x, y,z) AVyC(y,z),試(1)寫出量詞的轄域；15. (1) A-B =2,2(2) AAB =1(3) AX（2）指出該公式的自由變元和約束變元.，, ,（4分）（8分）(12 分), 16 . (1) G的圖形表示如圖三:V1V2V5（3分）(2)鄰接矩陣:0 00 01 1

19、0 10 0（3） V1, V2, V3, V4,100110011100100_V5結(jié)點的度數(shù)依次為1, 2, 4, 2, 1(4)補圖如圖四:（6分）（9分）（12 分）（2分）（4分）（6分）17 . （1）力量詞的轄域為（A（x, y）八 UzB（x, y, z）,Vz量詞的轄域為B(x,y,z),W量詞的轄域為C(y,z).（2）自由變元為（A（x, y） a VzB（x, y, z）中的y,以及C（y, z）中的z （9分）約束變元為(A(x,y) a VzB(x, y, z)中的x與B(x, y,z)中的z ,以及C(y, z)中的y.(12 分)六、證明題(本題共8分)18 .

20、試證明集合等式 2 (-C)=(A2B) c (A=C).19 .證明：設(shè) AJ (BC), (A=B) c (AjC),若 xC S,則 xC A 或 xC BC, (1 分)即 xC A 或 xC B 且 xC A 或 xCC.（2 分）也即 xCAB 且 xeC ,（3 分）即xC T,所以ST.（4分）反之，若 xC T,貝U xC AoB 且 xCA=C,（ 5 分）即 xCA 或 xCB 且 xCA 或 xCC,（6 分）也即xC A或xC BC,即xC S,所以TS.（7分）(8分)因此.2011年1月、單項選擇題（每小題 3分，本題共15分）1. D 2. B 3. C 4.

21、A 5. B1 .若集合a, b, a, a, b ，則（）.A. A-BB. A BC. A 二BD. A B2 .集合為小于10的自然數(shù),集合A上的關(guān)系10且x, y W A,則R的性質(zhì)為（）.A.自反的B.對稱的C.傳遞且對稱的D.反自反且傳遞的3 .設(shè)有向圖（a）、（b）、（c）與（d）如圖一所示，則下列結(jié)論成立的是（）.圖一A. （a）僅為弱連通的C. （c）僅為弱連通的4 .設(shè)圖G的鄰接矩陣為）110 010 0 111 0 0 0 00 10 0 10 10 10則G的邊數(shù)為（）.8. （b）僅為弱連通的D. （d）僅為弱連通的A. 5B. 6C. 7D. 85 .下列公式（）為

22、永真式.A . -P -Qf P QC. (Q，(P Q) fQ (P Q)B. (P，(-Q-； P)L (-P-； (P-； Q)D. (P (P Q)-Q、填空題（每小題 3分，本題共15分）6 .設(shè)集合 A=1, 2, 3,那么集合 A 的哥集是Q,1,2 ,3 ,1,2,1,3,2,3,1,2,37 .設(shè)a, b, 1 , 2,作f: A-B,則不同的函數(shù)個數(shù)為4.8,若1,2 , EA, y三A, 4,貝U R 的自反閉包為 ,.9 .無向連通圖在結(jié)點數(shù) v與邊數(shù)e滿足1關(guān)系時是樹.10 . (Vx)(A(xH B(x)VC(x, y)中的自由變元為C(x： y )中的 x 與 y

23、三、邏輯公式翻譯（每小題6分，本題共12分）11 .將語句“他們?nèi)ヂ糜?，僅當(dāng)明天天晴.”翻譯成命題公式.12 .將語句“今天沒有下雪.”翻譯成命題公式.11 .設(shè)P:他們?nèi)ヂ糜?，Q:明天天晴，（2分）P-Q.（6 分）12 .設(shè)P:今天下雪，（2分）P.（6 分）四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由 13.漢密爾頓圖一定是歐拉圖.錯誤.存在漢密爾頓圖不是歐拉圖.反例見圖二.（3分）（5分）（7分）14.下面的推理是否正確，試予以說明.（1）（羽（F （x） -G （y）（2） F （y） 一G （y）1、錯誤.前提引入（1）.（3分）（2）應(yīng)為F （a） 一G

24、 （y）,換名時，約束變元與自由變元不能混淆.（7分）五.計算題（每小題12分，本題共36分）15.設(shè)0, 1, 2, 3, 4, 5, 6, WA, y三 A 且 1, WA, yWA 且 3,試求 R, S, 1, 1, r（R）.R*S,（2 分）,（4 分）R *,（6 分）1=（8 分）1,=S（10分）r（R）.（12 分）16.畫一棵帶權(quán)為1,2, 2, 3, 6的最優(yōu)二叉樹，計算它們的權(quán).（10 分）（12 分）圖四權(quán)為：1 3+2 3+2 3+3 3+6 1=30 注：其他正確的最優(yōu)二叉樹參照給分.17.求（PVQ） 一（ RV Q）的析取范式，合取范式.(PVQ) 一( R

25、V Q)(PVQ) V ( RVQ)二 (-PA-Q)V (RVQ) UPV RVQ)A (-Q VRVQ) u(-PVRVQ)析取、合取范式注：其他正確答案參照給分.(4分)(12 分)六、證明題（本題共8分）18.試證明集合等式 AO （2C）=（ACB） 2 （AC）.證明：設(shè)A (BUC), (AAB)U(AnC),若 xCS,貝 U xCA 且 xCBUC,即 xC A 且 xC B 或 xCA 且 xCC,也即xC An B或xC An C ,即xC T,所以匹T. 反之，若 xC T,則 xC AA B 或 xCAAC,即xCA且xCB或xCA且xCC(4分)(8分)也即xC A

26、且xC BUC, 因此.即xCS,所以T三S.2010年7月、單項選擇題（每小題3分，本題共15分）1. B2. D3. B4. C 5. B若集合1 , 2 , 12 二A2,則下列表述正確的是（B.)C.2.().A .3.1 A已知一棵無向樹 T中有8個頂點,6設(shè)無向圖8. 4G的鄰接矩陣為0111J100111000011001則G的邊數(shù)為（)D.4度、C.1 A2三A3度、2度的分支點各一個,T的樹葉數(shù)為D. 5A .4.A .C.B. 7設(shè)集合 a,則A的哥集為5. a。，a下列公式中-A -B （）為永真式.-A -BC.-A -B 二、填空題（每小題 3分，本題共6. 命題公式

27、P aP的真值是 一11010)C. 6D. 14B. a, aD. 0, aB.AaF H n(AvB)D. ALB 7AaB)15分)假（或F,或0）7 .若無向樹 T有5個結(jié)點，則 T的邊數(shù)為 4.8 .設(shè)正則m叉樹的樹葉數(shù)為t,分支數(shù)為i,則(1)1.9 .設(shè)集合1 , 2上的關(guān)系R= ,則在R中僅需加一個元素,就可使新得到的關(guān)系為對稱的.10 . (X?X)(A(x)-B(x, z)V C(y)中的自由變元有 y.三、邏輯公式翻譯(每小題6分，本題共12分)11 .將語句“今天上課.”翻譯成命題公式.設(shè)P:今天上課，(2分)則命題公式為：P.(6分)12 .將語句“他去操場鍛煉，僅當(dāng)

28、他有時間.”翻譯成命題公式.設(shè)P:他去操場鍛煉，Q:他有時間，(2分)則命題公式為：PtQ.(6分)四、判斷說明題(每小題 7分，本題共14分) 判斷下列各題正誤，并說明理由.13 .設(shè)集合1 , 2, 3 , 4,從A到B的關(guān)系為,則f是A到B的函數(shù).14 .設(shè)G是一個有4個結(jié)點10條邊的連通圖，則 G為平面圖.13 .錯誤.(3分)因為A中元素2沒有B中元素與之對應(yīng)，故 f不是A到B的函數(shù).(7分)14 .錯誤.(3分)不滿足“設(shè)G是一個有v個結(jié)點e條邊的連通簡單平面圖，若v3,則eW36.”（7分）五.計算題（每小題12分，本題共36分）15 .試求出（PVQ） 一（ RV Q）的析取范

29、式.16 VQ） 一（ RV Q） u（PVQ）V （RV Q）（4 分）二（n PAn Q）V （ RV Q）（8分）u 6 PAn Q）VRV Q （析取范式）（12 分）17 .設(shè)1, 1,2 , 1, 2,試計算（1） APB（2） AUB（3） A （APB）.（2） AH1（4 分）（3） AU1,2, 1, 2（8 分）（4） A （APB） =1, 2（12 分）1、2、17.圖 ,其中 a, b, c, d , (a, b), (a, c), (a, d), (b, c), (b, d), (c, d),對應(yīng)邊的權(quán)值依次為 3、1、4 及 5,試(1)畫出G的圖形；(2)寫出

30、G的鄰接矩陣；(3)求出G權(quán)最小的生成樹及其權(quán)值.(1) G的圖形表示 如圖一所示：（3分）（2）鄰接矩陣：0 111（6分）（10 分）（12 分）10 11110 11110-（3）最小的生成樹如圖二中的粗線所示：權(quán)為：1+1+3=5 六、證明題（本題共 8分）18.試證明：若R與S是集合A上的自反關(guān)系，則 RAS也是集合A上的自反關(guān)系. 證明：設(shè)7x三A,因為R自反，所以x R x,即WR;又因為S自反，所以x R x,即WS.（4分）即WRA S（6 分）故RA S自反.（8分）2010年1月一、單項選擇題（每小題3分，本題共15分）1. A 2. C 3. B 4. B 5.1 .若

31、集合A= a, a,則下列表述正確的是（）.A. a三AB. a三AC. a, a eAD. 0WA2.命題公式（PVQ）的合取范式是 （）A . （PAQ）B. （PAQ） V （PVQ）C. （PVQ）D.（PAP）3 .無向樹T有8個結(jié)點，則T的邊數(shù)為（）.A. 6B. 7C. 8D. 94 .圖G如圖一所示，以下說法正確的是（）.A. a是割點B. b, c是點割集C. b, d是點割集D. c是點割集圖一5.下列公式成立的為（）.A , PA -Q U PVQB. PTQuPTQC. QtPn PD.PA(PVQ);Q二、填空題（每小題 3分，本題共15分）6 .設(shè)集合2, 3, 4

32、, 1,2, 3, 4, R是A到B的二元關(guān)系,R = xa AJL y w B且 x y則R的有序?qū)蠟?, , , , , 7 .如果R是非空集合A上的等價關(guān)系，a WA, bWA,則可推知 R中至少包含, 條邊，可以確定8 .設(shè)G=是有4個結(jié)點，8條邊的無向連通圖，則從 G中刪去 圖G的一棵生成樹.9.設(shè)G是具有n個結(jié)點m條邊k個面的連通平面圖，則 m等于210.設(shè)個體域D = 1,2,A（x）為“x大于1”，則謂詞公式（三x）A（x）的真值為真（或或1）三、邏輯公式翻譯（每小題6分，本題共12分）(2分)(6分)11 .將語句“今天考試，明天放假.”翻譯成命題公式.設(shè)P:今天考試，Q

33、:明天放假.則命題公式為：PAQ.12.將語句“我去旅游，僅當(dāng)我有時間.”翻譯成命題公式.設(shè)P:我去旅游，Q:我有時間,(2分)則命題公式為：P Q.(6分)四、判斷說明題（每小題 7分，本題共14分）判斷下列各題正誤，并說明理由.13 .如果圖G是無向圖，且其結(jié)點度數(shù)均為偶數(shù)，則圖錯誤.當(dāng)圖G不連通時圖G不為歐拉圖.14 .若偏序集G是歐拉圖.A的最大兀為a,（3分）（7分） 最小元是f.錯誤.集合A的最大兀與最小兀不存在，a是極大元，f是極小元，.五.計算題（每小題 12分，本題共36分）(3分)(7分)15.設(shè)謂詞公式(3x)(A(x,y)T (Vz)B(y,x, z),試（1）寫出量詞

34、的轄域;（2）指出該公式的自由變元和約束變元.(1)水量詞的轄域為(A(x, y)T Wz)B(y,x,z),(3分)加量詞的轄域為B( y, x, z),(6分)(2)自由變元為(A(x,y)T (Vz)B(y,x,z)中的 y,(9分)約束變元為x與z.16.設(shè)集合1,1,2, 1,1,2,試計算(12 分)(1)(1)(A-B) ;(2) (AAB);A 書=1，2(2) AAB =1(3) AXB.(3)A , 17.設(shè) , V1, V2, V3(1)給出G的圖形表示；(3)求出每個結(jié)點的度數(shù)；(1) G的圖形表示為(如圖三, , , V4 , (V13),(V23),(V24),(V

35、34)，試(2)寫出其鄰接矩陣；(4分)(8分)(12 分)(4)畫出其補圖的圖形.)：(3分)(2)鄰接矩陣：-00(6分)(3) V1, V2, V3,V4結(jié)點的度數(shù)依次為1, 2, 3, 2(9分)(4)補圖如圖四所示:(12 分)AXMB,則.(1分)(3分)圖四六、證明題(本題共 8分)18.設(shè)A, B是任意集合，試證明：若 證明：設(shè)x三A,貝U AMA,因為 AXMB,故BB,貝U有 xeB,(5分)（6分）（7分）（8分）設(shè) xWB,貝U WBxB,因為AxxB,故WAxA,則有x三A,所以B=A.故得.2009年10月一、單項選擇題（每小題 3分，本題共15分）1. D 2.

36、C 3. B 4. C 5, A1 .若G是一個漢密爾頓圖，則 G 一定是（）.A.平面圖B.對偶圖C.歐拉圖D.連通圖2 .集合1,2, 3, 4上的關(guān)系且x, W ,則R的性質(zhì)為（）.A.不是自反的B.不是對稱的C.傳遞的D.反自反3 .設(shè)集合1, 2, 3, 4, 5,偏序關(guān)系M是A上的整除關(guān)系，則偏序集 A,令上的元素5是集合A的 （ ）.B .極大元C.最小元4 .圖G如圖一所示，以下說法正確的是（）.A. (a, d)是割邊C. (a, d) ,(b, d)是邊割集B. (a, d)是邊割集D. (b, d)是邊割集圖一5.設(shè)A (x): x是人，B (x): x是工人，則命題“有

37、人是工人”可符號化為().A .(三x)(A(x)A B(x)B. (Vx)(A(x)A B(x)C. n (Vx)(A(x) -B(x)D. n (3x)(A(x)An B(x)二、填空題（每小題 3分，本題共15分）6 .若集合1 , 3, 5, 7, 2, 4, 6, 8,則 AA 空集（或 0）.7 .設(shè)集合1, 2, 3上的函數(shù)分別為：, , ,則復(fù)合函數(shù) gf = , , ,8 .設(shè)G是一個圖，結(jié)點集合為V,邊集合為E,則G的結(jié)點度數(shù)之和 為2（或“功數(shù)的兩倍）.9 .無向連通圖G的結(jié)點數(shù)為v,邊數(shù)為e,則G當(dāng)v與e滿足1關(guān)系時是樹.10 .設(shè)個體域D=1,2, 3 , P（x）為

38、“x小于2”，則謂詞公式（Vx）P（x）的真值為 假（或F.或0）.三、邏輯公式翻譯（每小題6分，本題共12分）11 .將語句“他是學(xué)生.”翻譯成命題公式.設(shè)P:他是學(xué)生，（2分）則命題公式為：P.（ 6分）12.將語句“如果明天不下雨，我們就去郊游.翻譯成命題公式.設(shè)P:明天下雨，Q:我們就去郊游，(2分)則命題公式為：一PtQ.四、判斷說明題(每小題 7分，本題共14分)判斷下列各題正誤，并說明理由.13 .下面的推理是否正確，試予以說明.(1) (Vx) F (x) 一G (x)前提引入(2) F (y) -G (y)(1).錯誤.(3分)(2)應(yīng)為F (y) 一G (x),換名時，約束

39、變元與自由變元不能混淆.(7分)14 .如圖二所示的圖 G存在一條歐拉回路.錯誤.因為圖G為中包含度數(shù)為奇數(shù)的結(jié)點.圖(3分)(7分)五.計算題(每小題 12分，本題共36分)15 .求(PVQ) 一 R的析取范式與合取范式. (PVQ) 一 Ru(PVQ) V R（4分）U （-PA Q）V R（析取范式）（8分）二（一PV R）A （Q VR）（合取范式）（12 分）16 .設(shè)0 , 1, 2, 3 , WA, yA 且 0, A, y三 A 且攵，試求 R, S, R*S, S1, r（R）.0, ,（3 分）R0,（6分）S-1= S,（9 分）r（R）, .（ 12 分）17 .畫一

40、棵帶權(quán)為1,2, 2, 3, 4的最優(yōu)二叉樹，計算它們的權(quán). 最優(yōu)二叉樹如圖三所示圖三（10 分）權(quán)為 1 3+2 3+2 2+3 2+4 2=27（12 分）六、證明題(本題共8分)18.試證明集合等式 2 (-C)=(A=B) c (A=C).證明：設(shè) A7 (BcC), (AB) c (A=C),若 xCS,則 xCA 或 xCB-C,即xCA 或 xCB 且 xC A 或 xe c.也即 反之，若也即因此.xCAjB 且 xCAC ,即 xCT,所以 ST.xC T,貝U xC A=B 且 xC A=C,即 xC A 或 xC B 且 xC A 或 xC CxC A 或 xC BF,2

41、009年7月一、單項選擇題(每小題1 .A .C.若集合a, b , aAB,且 AWB AE,但 AB3分，本題共15分)b, a, b ，則(B. AWB,1. A 2, B 3. B).但A二BD. AZB,且 AB2.集合1,2, 3, 4, 5, 6, 7, 8上的關(guān)系10 且 x, ,則R的性質(zhì)為(4分)4.D 5. C).A .自反的C.傳遞且對稱的B.對稱的D.反自反且傳遞的3.A .4.A .C.如果Ri和R2是A上的自反關(guān)系，則R1UR2, Ri n R2,B. 2如圖一所示，以下說法正確的是(a, e)是割邊( a, e) ,(b, c)是邊割集C. 1).B. (a,

42、e)是邊割集D. (d, e)是邊割集R12中自反關(guān)系有D. 3)個.圖一5.設(shè)A (x): x是人，B (x): x是學(xué)生，則命題“不是所有人都是學(xué)生”可符號化為().A . ( Vx)(A(x)A B(x)B. n (3x)(A(x)A B(x)C. n (Vx)(A(x) -B(x)D. n (3x)(A(x)An B(x)二、填空題(每小題 3分，本題共15分)6 .若集合A的元素個數(shù)為10,則其募集的元素個數(shù)為 1024.7 .設(shè)a, b, c, 1, 2,作f： A-B,則不同的函數(shù)個數(shù)為 8.8,若1,2 , , yEA, 10,則 R 的自反閉包為 ,.9 .結(jié)點數(shù)v與邊數(shù)e滿

43、足1關(guān)系的無向連通圖就是樹.10 .設(shè)個體域D = a, b, c,則謂詞公式(Vx)A(x)消去量詞后的等值式為A (a) M (b)M (c)三、邏輯公式翻譯(每小題6分，本題共12分)11 .將語句“盡管他接受了這個任務(wù)，但他沒有完成好.”翻譯成命題公式.設(shè)P:他接受了這個任務(wù)，Q:他完成好了這個任務(wù)，(2分)PaQ.(6 分)（#分）12 .將語句“今天沒有下雨.”翻譯成命題公式.設(shè)P:今天下雨,-P.（6分）四、判斷說明題（每小題7分，本題共14分）判斷下列各題正誤，并說明理由13 .下面的推理是否正確，試予以說明（1） （Vx） F （x） 一G （x）（2） F （y） 一G （

44、y）前提引入（1）.錯誤.（2）應(yīng)為F （y） 一G （x）,換名時，約束變元與自由變元不能混淆.14 .若偏序集A, R的哈斯圖如圖二所示，則集合 A的最大元為（3分）（7分） a,最小元不存在.圖錯誤.集合A的最大元不存在，a是極大元.（3分）（7分）五.計算題（每小題12分，本題共36分）15.求（PVQ） 一（ RV Q）的合取范式.（PVQ） 一（ RV Q）（PVQ） V （ RVQ）U（-PA P）V （RVQ）UPV RVQ）A （_Q VRVQ）U（-PVRVQ） A R 合取范式16.設(shè)0, 1, 2, 3, 4, EA, y三 A 且 0 , A r（R）. -,R0,（

45、4分）（12 分）y三A且M3,試求 R, S, R-S, 1, 1,= .=Sr（R）.（2分）（4分）（6分）（8分）（10 分）（12 分）17.畫一棵帶權(quán)為1,2, 2, 3, 4的最優(yōu)二叉樹，計算它們的權(quán).（12 分）權(quán)為 1 3+2 3+2 2+3 2+4 2=27六、證明題（本題共8分）18.設(shè)G是一個n階無向簡單圖，n是大于等于2的奇數(shù).證明G與G中的奇數(shù)度頂點個數(shù)相等 （G 是G的補圖）.證明：因為n是奇數(shù)，所以n階完全圖每個頂點度數(shù)為偶數(shù)，（3分）因此，若G中頂點v的度數(shù)為奇數(shù)，則在 G中v的度數(shù)一定也是奇數(shù)，（6分）所以G與G中的奇數(shù)度頂點個數(shù)相等.（8分）2008年7月4. C 5. D一、單項選擇題（每小題 3分，本題共15分）1. B 2. B 3. A1.設(shè)a, b , 1,2 , R1,2, , R3=, b,R2, R3是A到B的二元關(guān)系，且 Ri=, , R2=, ,則（R2）不是從A到B的函數(shù).C. R32.設(shè)1,2, 3, 4, 5, 6, 7, 8,R是A上的整除關(guān)系，2, 4, 6D. R 和 R3,則集合B的最大元、最小元、上界、下）.8、26、2B.無、2、無、D. 8、1、6、1界依次為（A. 8、2、C. 6、2、3.若集合A. 1024A的元素個數(shù)為B. 1010,則其哥集的元素個數(shù)為（4.設(shè)完