離散數(shù)學B卷及答案

1、百度文庫-讓每個人平等地提升自我10武漢理工大學離散數(shù)學考試試題 （B卷）站點:姓名:專業(yè):層次、單項選擇題（本大題共15小題，每小題1分，共15分）在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。1 .令P:今天下雪了，Q:路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為（A. PQB. PV-QC.2.A.C.3.A.PAQD. PA1Q卜列命題公式為重言式的是（Qf ( PA Q)（PAQ） 一 PF列4個推理定律中，不正確的是（A (AAB)B.D.)B.Pf (PAQ)(PVQ) 一Qc.A. x(P(x) yR(y)(A

2、fB) A A BD.(AVB) A 1A(A-B)人怕I Ha4 .謂詞公式x(P(x) V yR(y) 一 Q(x)中量詞x的轄域是（B. P (x)C. (P(x)V yR(y)D. P(x), Q(x)5 .、設(shè)個體域A=a,b,公式 xP（x） A xS（x）在A中消去量詞后應(yīng)為（A. P(x) A S(x)B.P(a)A P(b)A (S(a)VS(b)C. P（a）AS（b）6.下列選項中錯誤的是（D.P(a)A P(b)AS(a)VS(b)A. ?B.C. ?D.?C?7.設(shè) A=a,b,c,d的劃分是（A.a,b, c,dC.a,b,c,d8.設(shè)R為實數(shù)集,A 上的等價關(guān)系

3、R=<a, b>, <b, a>, <c, d>, <d, c> U Ia,則對應(yīng)于B. a, b,c, dD. a, b, c,d函數(shù)f: R-R, f(x)=2x,則 f 是(A.滿射函數(shù)B.入射函數(shù)C.雙射函數(shù)/D.非入射非滿射9.設(shè)R為實數(shù)集，R+=x|x C RAx>0 , *是數(shù)的乘法運算<R+, *>是一個群，則下列集合 關(guān)于數(shù)的乘法運算構(gòu)成該群的子群的是（）A.R+中的有理數(shù)B.R+中的無理數(shù)C.R+中的自然數(shù)D.1, 2, 3'10.下列運算中關(guān)于整數(shù)集不.能構(gòu)成半群的是（）、A.a b=maxa, b

4、B.ab=bC.a b=2abD.ab=|a-b|11 .設(shè)Z是整數(shù)集，+,分別是普通加法和乘法，則（Z, +,）是（A.域B.整環(huán)和域C.整環(huán)D,含零因子環(huán)12 .設(shè)A=a, b, c ,R是A上的二元關(guān)系，R=<a, a>, <a, b>, <a, c>, <c, a>，那么 R是（ ）A .反自反的B.反對稱的C.可傳遞的D.不可傳遞的13 .設(shè) D=<V, E> 為有向圖，V=a, b, c, d, e, f, E=<a, b>, <b, c>, <a, d>, <d, e>,

5、<f, e> 是（ ）A.強連通圖B.單向連通圖C.弱連通圖D,不連通圖14 .在有n個結(jié)點的連通圖中，其邊數(shù)（）A.最多有n-1條B.至少有n-1條C.最多有n條D,至少有n條15 .連通圖G是一棵樹，當且僅當 G中（）/A.有些邊不是割邊B.每條邊都是割邊/C.無割邊集 D.每條邊都不是割邊/二、填空題（本大題共 10小題，每小題2分，共20分）/請在每小題的空格中填上正確答案。錯填、不填均無分。16 .任意兩個不同的小項的合取為 式，全體小項的析取式必為17 .公式 x（P（x） - Q（x,y） V zR（y, z） -S（x）中的自由變元為 ，約束變元為。18 .設(shè)集合

6、M=x|1 WxW12,x 被 2 整除，xCZ,N=x|1 <x< 12,x 被 3 整除，x C Z,則 M n N=, M U N=19 .設(shè) X=1 , 2, 3, f: X-X, g: X - X, f=<1,2>,<2,3>,<3,1>, g=<1,2>,<2,3>,<3,3>,則 f g=, g f=。20 .設(shè)A=a,b,c , R是A上的二元關(guān)系，且給定 R=<a,b>,<b,c>,<c,a>,則R的自反閉包 r(R尸，對稱閉包 s(R)=。21 .設(shè)Q為有

7、理數(shù)集，笛卡爾集S=QXQ, *是S上的二元運算，<a, b>,<x, y> C S,<a, b>*<x, y>=<ax, y+b>,貝U*運算的幺元是 。<a, b> C S,若 aw0,貝U <a, b>的逆元是 。22 .設(shè)*是集合S上的二元運算，若運算*滿足 且存在,則稱<S, *>為獨異點。23 .令A(yù)=a, b, c, <A, *>是循環(huán)群，a是單位元，則b2=, c的階是24 .如下無向圖割點是 ,割邊是 25 .無向圖G具有生成樹，當且僅當 4的所有生成樹中 的生成樹稱為

8、最小生成樹。三、計算題(本大題共5小題，第26、27小題各5分，第28、29小題各6分，第30小題8分，共30分)26 .集合 A=a, b, c, d, e上的二元關(guān)系 R為X/R=<a,a>, <a,b>, <a,c>, <a,d>, <a,e>, <b,b>, <b,c>, <b,e>,<c,c>, <c,d>,<c,e>, <d,d>,<d,e>, <e,e>/(1)寫出R的關(guān)系矩陣；/(2)判斷R是不是偏序關(guān)系，為什么

9、？/27 .利用真值表判斷公式(1PVQ) A (Q - R) 一/ (PAIR)是否為重言式。28 .給定圖G如下所示，（1）寫出G的可達矩陣；（2） G中長度為4的路有幾條?29 .求下列公式的主析取范式和主合取范式：（AQ） A （Q-R）30 .設(shè)A為54的因子構(gòu)成的集合，R AXA, x,y C A, xRy x整除y。畫出偏序集<A,R> 的哈斯圖，并求 A中的最大元，最小元，極大元，極小元。五、證明題（本大題共 3小題，第31、32小題各6分，第33小題8分，共20分）31 .設(shè)R是A上的一個自反關(guān)系，證明：R是一個等價關(guān)系，當且僅當若 <a,b>CR,

10、<a,c>e r,則 <b,c> e Ro32 .設(shè) <G, *> 是一個群，xCG,定義：a b=a*x*b , a,bC G。證明：<G, > 也是一個群。33 .設(shè)圖G是具有6個結(jié)點，12條邊的無向簡單圖，證明圖G是漢密爾頓圖。五、應(yīng)用題（本大題共 2小題，第34小題8分，第35小題7分，共15分）34 .構(gòu)造下面推理的證明。如果今天是星期六，我們就要到頤和園或圓明園去玩。如果頤和園游人太多，我們 就不去頤和園玩。今天是星期六，頤和園游人太多，所以我們?nèi)A明園玩。35 . n個城市用k條公路的網(wǎng)絡(luò)連結(jié)。 一條公路定義為兩個城市間的一條不穿過

11、任何中間城 市的道路。任意兩個城市之間至多修一條公路。證明如果k>1 （n-1）（n-2）,則人們總能通2過連結(jié)的公路，在任何兩個城市間旅行。武漢理工大學離散數(shù)學考試試題 （B卷）答案站點:姓名:專業(yè):層次（2海為 <瓦4 > q % < 7 > 美系事一.單項選擇題次大超共15小號,銀小即1分.扶1$分】L D2.CVA4, CS. B6. B 工口 8, 09 式 10 口11.GIX P13+ C14 R15. R二、埴空題（本大題髭L。小妹同小麗2分.指加分116矛底靂言I工工,* K,工IS 6,12） （2工4,65耳16 T J > , <

12、;2、Y3J > < 13 > ,20- 曰11?# wb.u ± , ec,r，怔包1呂 > /卜,卜、，<仁，"、!（<afb> > <b.Q , vhn,<匚產(chǎn)，1工1,14戶<, - b22靖臺很忠兀23一 c 324. d 口25, G連通帶叔昌小三.計算逾4本文題共5小題.第26.2了小窗香5分，第巡、29小翹各6分第g小摩S分,共第分）iijir0I01招解“1泮的關(guān)系矩降力:耨“三oD1I1 （2分）00011.0000L包n,伊ehd i咽宣，故亢不具岔傳遞性，不是偏序 （3分）.該式為重官

13、式口(1分)128.解的鄰接矩陣為00 0 0 10 10 00 0 0 10 10 0(1分),0 10 0故R* =00 .2252001200000012L0 (T 2 0 2 0. 5" 2 50.0110J0202010 20002020CT 0 0 0ro04.0000 040 00 044' 000.（4分）L1（2）G中投度為4的路有32條.29 .解:原式a（lPVQ）A（QVH）(1分)U(1PVQV(RA】H)A(1QVRV(PA】P)q(1FVQVR) A(lPVQVlR) A(PVIQVR) A(PV1QVR)oE4,5,2,6)0M2.35,6)G

14、 分)IP A IQ AIR) V(lPAlQAlQAR) V(lPAQAR) V (PAQAR)=£1,3,7),3 冬30 .解，54的因子集合為U ,2,3,6,9,18,”,54“分)4人*>的哈斯圖如下:A中最大元54,展小元1,極大元54,極小元U（4分）四、證明豌（本大題共3小期.第八、32小題各6分，第勢小減盤分，共20分）31.證明:必要性° R是等價關(guān)系，若4日，卜> 任上> g R+由R的對稱性知: e Rfg R,再由 R 的傳遞性知二 <> e Ho （3 分）充分性.首先R是A上的自反美系.其次若e日/ e R,由R

15、的自反性知* <&淮>電見再由已知條件知： < 3口 > s R.因而R是對稱的*再次若 <口上> wR, <h,ceR,由R的對稱性知；<bta> eRt <b,c> eR,由已知條 件知<3£> eR,因而R是傳遞的，所以R是一個等價關(guān)系。分）3Z證明：顯然，地G上的二元運算，要證G是群，需證明結(jié)合律成立，同時存在單位 元和每個元素都有逆元，1-陶敬數(shù)學試廖答案及評分參考第2頁（共4頁）VafbTceGfW（a4）（A*n4h）*x*c = aoii*（b«T«c） =4i4

16、b»c）可知運 算是可緒合的，（2分）其次逐展（心）的單醞事實上，¥*已有 u* J電="（2分）06丫2聿工7中在（G中的理元心事實上，（X唱”-，白丁"0鼻E"（2分）由以上證明可知,（G,）是群.3曳證明:已知一個圖是漢密爾頓圖的充分條件是:圖中任意不同兩點的度敬之和大于等于g Q分）假饞圖中存在潮個結(jié)點.年.其度放之和不大于等于6,即d（也） *d與）域5。叵|去這兩個點后，至重礴去圉G中的5條邊。（3分）由于由G是具 有6個結(jié)點42條邊的無向前單圈,翼去結(jié)點V,戶工后，得到的子圖為:具有4個結(jié) 點,至少7條邊的無向管單留，但這祥的無向

17、前單圖不存在，由此證明圖c中任意 兩個不同結(jié)點的度數(shù)之和大于等于6,第G地漢密爾頓圖。（3分）五、應(yīng)用逾（本大函共2小燃，第34小噌8分，翦35小題7分，共15分）"舞;令巴今天是星期六Q ：我打到頤和國壇氏舞/門到國明園玩品籟和園涉人太喜前提:PtQVR,J1Q,P5結(jié)聯(lián)R證明:JQS1QP-Q V R®P®QVR ®RP（前提引入）P（前提引人）P（前提引人） P（前提引人） T®®1 T®©I(2分)a分)35,證明:把城市作為結(jié)點，城市間的公略作為結(jié)點間的邊，由此構(gòu)成趙G” G有n個結(jié)點,k條邊.（分）用反證法證明"假設(shè)G中有兩結(jié)點1!門,從¥不熊經(jīng)過邊到達U.不妨設(shè)力為G中 能到達U的結(jié)點集1為0中不能到達U的結(jié)點集.則有u三/ 一eV" （2分） 設(shè)G=* % E G = % E 為G的子,圖，顯然有i vj 小 v, =* | E | * 1耳=匕設(shè)Ml 三小則 |E| |美加(m4。/2 jE/(n = ni)(n = 1 /2, 所以 k =恒| *I Ej m( m -1 )/2 + (n " m) (n *m - t )/2 =-( n1 n