離散數(shù)學(xué)復(fù)習(xí)題及參考解答

1、離散數(shù)學(xué)復(fù)習(xí)題及參考解答B(yǎng) .復(fù)習(xí)題2.45在1和1000之間(包括1和1000ft內(nèi))不能被4和5整除的數(shù)有設(shè)R是定義在集合A 1,2,3,4上的二元關(guān)系R ( 1,1 , 1,2 , 2,3 , 1,4 ,則R的對(duì)稱閉包s(R)中的零元是84與198的最大公約數(shù)是、單項(xiàng)選擇題(從下列各題四個(gè)備選答案中選出一個(gè)正確答案，并將其代號(hào)寫在答題G(x)x(F(x)2345678一、填空題(請(qǐng)將每空的正確答案寫在答題紙相應(yīng)位置處，答在試卷上不得分。每小題 2分，共16分。)1.謂詞公式x y(P(x, y) Q(y,z) xR(x, y)中x的轄域是數(shù)的有理數(shù)”可符號(hào)化為(A. x(F(x) G(x

2、)紙相應(yīng)1.示成分位置處。答案錯(cuò)選或未選者，該題不得分。每小題設(shè)F(x): x是有理數(shù)，G(x)： x能表示成分?jǐn)?shù)。)。B.命題公式(pq)的成真賦值為2分，共16分。)在一階邏輯中，命題“沒有不能A 1,2,3,4 , x y min x, y,則代數(shù)系統(tǒng)A,具有10個(gè)結(jié)點(diǎn)的無向完全圖的邊數(shù)=。一次同余方程3x 1(mod 5)的最小正整數(shù)解是A .C.D.6.對(duì)于下列度數(shù)序列，可畫成簡單無向圖的是 (A. (1 , 1, 1 , 2, 3) B . (1,2, 2, 3, 4, 5)C. (1 , 2, 3, 4, 5, 5) D . (2 , 3, 3, 4, 5, 6)x(F(x)D.

3、設(shè)個(gè)體域是整數(shù)集，則下列命題的真值為真的是B,10對(duì)自然數(shù)集合N ,下列定義的運(yùn)算中()是不可結(jié)合的。BDx y(x y y x(x yA.C.3.AC、傳遞的、對(duì)稱的、反自反的、傳遞的D 上的關(guān)系( 0) x2)y 1)2 y y )1,2,LC. x(F(x) G(x)R x,y |x y 10, x, y A,則 R 的性質(zhì)為y x(xx y(x集合a()。自反的對(duì)稱的G(x)。A. abaB.a b a 2bb 3a b min a,bb(mod 3)D.C. a b a卜列各圖中既是歐拉圖，又是漢密爾頓圖的是 ()7 .含有5個(gè)結(jié)點(diǎn)、3條邊的不同構(gòu)的簡單圖有（）個(gè)A. 2 B. 3C

4、. 4 D. 58 . 5的模6逆等于（）。A. 1 B . 3 【第 1 項(xiàng)4 D . 5三、計(jì)算題（第1、2、3、4小題各7分，第5、6小題各8分共44分。）1 .求命題公式（p q） （pr）的主析取范式和主合取范式。（1）畫 界。2 .設(shè) A, R為偏序集，其中A 1,2,3,4,6,9,24,54, R是A上的整除關(guān)系。出 A, R的哈斯圖；（2）求A中的極大元；（3）令B 4, 6,9,求B的上確界和下確3 .求下圖1中帶權(quán)無向圖的最小生成樹，并求出該最小生成樹的權(quán)值。4 .求解遞推方程：an 7an 1 12an 2 0, a0 4,4 6。vi 至 1 Vl5 .有向圖D如圖2

5、所示，求：（1） D中到V3長度為3的通路有幾條？ （ 2） D中 長度為3的回路有幾條？ （ 3） D是哪類連通圖？V4V2 O圖2【第1頁6 .在通訊中要傳輸字母a,b,c,d,e, f ,g ,它們出現(xiàn)的頻率為：a: 30%, b: 20%, c: 15%, d : 10%, e: 10%, f : 9%, g : 6% ,設(shè)計(jì)傳輸上述字母的最元前綴碼，畫出最優(yōu)樹，并求傳輸 100個(gè)按上述頻率出現(xiàn)的字母所需二進(jìn)制字個(gè)數(shù)。四、證明題（每小題8分，共16分。）1 .設(shè)R為自然數(shù)集N上的關(guān)系，定義N上的關(guān)系R如下：x, （1）證明R為等價(jià)關(guān)系；（2）求商集N/R。2 .設(shè)Z為整數(shù)集合，在Z上定

6、義二元運(yùn)算o如下：x, y Z, xoy 是群。五、符號(hào)化下列命題，并在自然推理系統(tǒng) P中論證結(jié)論的有效性y R x y是偶數(shù)x y 2，證明:（8 分。）Z,o若小張喜歡數(shù)學(xué)，則小李或小趙也喜歡數(shù)學(xué)。若小李喜歡數(shù)學(xué)，則他也喜歡物理。小張 確實(shí)喜歡數(shù)學(xué)，可小李不喜歡物理。所以，小趙喜歡數(shù)學(xué)。參考答案每小題一、填空題（請(qǐng)將每空的正確答案寫在答題紙相應(yīng)位置處，答在試卷上不得分。 2分，共16分。）1. P（x, y） Q（y,z） 2 . 10, 11, 00 3 . 600 1,1 , 1,2 , 2,3 , 1,4 , 2,1 , 3,2 , 4,1 5. 1八單項(xiàng)選擇題（從下列各題四個(gè)備選答

7、案中選出一個(gè)正確答案，并將其代號(hào)寫在答題紙相應(yīng)1位置處。答案錯(cuò)選或未選者，該題不得分。每小題 2分，共16分。）C 2.C 3. C 4. B 5.C 6 . A 7.C 8.D:、計(jì)算題（第1、2、3、4小題各7分，第5、6小題各8分共44分。）解：主合取范式為：(p q) (p (p q) ( p (p q) (r(5分)q q m5r)r) Mr)r) r)P qP q( r) r)P r)(q q)q r) ( P q r)q r)主析取范式為:（Pq)(2分)(P r)2.解:mo(Pmi(1) A,m2m3q r)(m7q r)q r) ( p q r) (p q(3分)r)R的哈

8、斯圖如下圖所示（2） A中的極大元是：24, 54;（ 2 分）（3） B的上確界：無；B的下確界：1。（ 2 分）3.解：所求該圖的最小生成樹如下圖所示。（5分）該最小生成樹的權(quán)值之和WW （t） =2+1+1+2+3+4=13（2分）分）4.解：其特征方程為：x2 7x 12通解為：an C13n0,其特征根是:Xi代入初值得到:Ci解得：G 10, C2nc24c2 4, 3cl63, X2 4（2分）（2分）所以，原方程的解為:an解：先求圖D的鄰接矩陣nn10 36 4A 及 A2、A3。4c26（2分）（1分）11 A01100011000110,（1 分）A22211110121

9、0121.（2 分）00A35412221133123202（2（1） D中4到V3長度為3的通路有3條。（1分）（2） D中4到長度為3的回路有5條。（1分）（3） D是強(qiáng)連通圖。（1分）6.解：按字母順序，令R為傳輸?shù)趇個(gè)字母的頻率，i1,2,L ,7 ,則傳輸100個(gè)字母，各字母出現(xiàn)的頻數(shù)為Wi 100R,得 w1 30, w2 20, w3 15, w4 按照從小到大順序排列，得（2分）以Wi為權(quán)求最優(yōu)2叉樹如下圖所示。10, w5 10, w6 9, w7 6。將它們6 9 10 10 15 20 30。00000001（4分）傳輸?shù)那熬Y碼分別為：a 01, b 11, c 001,

10、 d 100, e 101, f 0001, g 0000傳100個(gè)所需二進(jìn)制數(shù)字個(gè)數(shù)為：（2分）W（t）=15+30+60+100+40+20=265四、證明題(每小題8分，共16分。)1. (1)證明：x N,因?yàn)閤 x因此R在N上是自反的；x, y N,若 x, y 因此R在N上是對(duì)稱的；2x, 2x N且是偶數(shù)，于是R,則x y是偶數(shù),即yx,x R,(1分)x是偶數(shù)，于是y, x R,(1分)x, y,z N,若： 于是 x z (x y) (y 因此R在N上是傳遞的;x, y則 x y 2k1z) 2y 2(k1 k2 y),進(jìn)而 x,z綜上所述，R是N上的等價(jià)關(guān)系。(2) N關(guān)于

11、等價(jià)關(guān)系R的所有等價(jià)類為則 N/R 0 r, 1r o0r 0, 2,4,6,y Z 2k2,R,(2分)(1分)ki, k和1卜1,3,5,7, (3分)2.證明：顯然，Z關(guān)于o是封閉的。 對(duì)于任意x, y, z Z ,由于(xo y) oz (x y 2)oz (x y xo(yoz) xo(y z 2) x (y(1分)2) zz 2x y2) 2x y(xoy)oz xo(yoz),即o滿足結(jié)合律。x Z ,因?yàn)閤o2x Z ,由于4 xx關(guān)于o存在逆元4 所以，Z,o是群。x 2 2 x 2ox,因此2是Z關(guān)于o的單位元(2分)(2分)Z 且 xo(4 x) x (4 x) 2 2 x o (1分)(4 x) ox ,于是(2分)五、符號(hào)化下列命題，并在自然推理系統(tǒng) P中論證結(jié)論的有效性解：設(shè)簡單命題(8 分。)p：小