離散數(shù)學(xué)試題()_A(答案)

1、哈爾濱工程大學(xué)試卷考試科目：離散數(shù)學(xué)(041121, 041131 -32) 考試時間： 2007.01.16 14:00-16:30題號-一一-二二-三四五總分分?jǐn)?shù)評卷人一、填空題(每題3分，共15分)1. 設(shè) F(x): x是蘋果，H(x，y): x與 y完全相同，L(x, y): x=y, 那么命題“沒有完全相同的蘋果的符號化(利用全稱量詞)為x y(F(x) F(y) L(x，y)H(x，y).2. 命題“設(shè)L是有補(bǔ)格，在L中求補(bǔ)元運(yùn)算"是L中的一元 運(yùn)算的真值是.3. 設(shè)G=e, a, b, c是Klein四元群，H= a是G的子群，那么商 群 G/H= a , b, c=

2、 e, a, b, c.4. 設(shè)群G= P(a, b, c),，其中 為集合的對稱差運(yùn)算，那么由集合a, b生成的子群a, b =, a, b.5. n階無向簡單圖G有m條邊，那么G的補(bǔ)圖有n(n-1)/2-m 條邊.二、選擇題(每題3分，共15分)1.命題“只要別人有困難(p),小王就會幫助他(q)，除非困難已經(jīng)解決了(r)的符號化為【B A. (P r) q.B. ( r p) q.C. r (p q).D. r (q p).2.設(shè)N為自然數(shù)集合，“為通常意義上的小于等于關(guān)系，那么偏序集N,是【C第1頁共6頁A .有界格.B.有補(bǔ)格.C .分配格.D.布爾代數(shù).3.設(shè)n (n 3)階無向圖

3、G= V, E是哈密爾頓圖，那么以下結(jié)論中不成立的是【DA. V1 V, p(G-VJ V1 .B .E n.C.無1度頂點(diǎn).D .(G) n/2 .4.設(shè)A=a, b, c，在A上可以定義個二元運(yùn)算，其中有個是可交換的，有個是幕等的.【A A . 39, 36, 36 .B .39, 36, 33 .C . 36, 36, 33 .D .39, 36, 39 .5.以下圖中是歐拉圖的有【CA . K4, 3 .B .K6 .C . K5 .D.K3, 3 .三、計(jì)算與簡答題(每題8分,共40分)1.利用等值演算方法求命題公式(p q)(q p)的主合取范式；利用該主合取范式求公式的主析取范式

4、， 賦值和成假賦值.并指出該公式的成真(p q) (q p)(p q) ( q p)(pq) (qp)(pq p)(qq p)q p p qM1此為公式的主合取范式.該公式的主析取范式是m。m2 m3 . 公式的成真賦值為00, 10, 11 . 公式的成假賦值為01 .第2頁共6頁2. 求群Z18 ,18的所有生成元和子群，畫出乙8, 18的子群格，指出該子群格的全下界、全上界和有補(bǔ)元，并求其補(bǔ)元.與 18互質(zhì)的數(shù)有 1, 5, 7, 11，13，17，因此，1, 5, 7, 11，13, 17是群Z18 ,18的生成元.18的因數(shù)有1, 2, 3, 6, 9, 18,因此，群 乙8, 18

5、的子群有1 = Z18 ,18 ,2 = 0, 2, 4, 6, 8, 10, 12, 14, 16,3 = 0 , 3, 6, 9, 12, 15,18 ,6 = 0 , 6, 12, 18 ,9 = 0 , 9 ,18 ,18 = 0 , 18 .Z18 ,18的子群格為 18 , 9 , 6 ,3 , 2 ,1 ,其哈斯圖為全下界為18 ,全上界為1 ,18 ' = , 1 ' =18 ,2 ' 9 , 9 '= , 3和6沒有補(bǔ)元.3. 假設(shè)R1 , R2均是非空集合A上的等價 關(guān)系，那么R1 , R2的交R1 n R2、并R1 U R2和復(fù)合R1CR2

6、也是A上的等價關(guān) 系嗎？假設(shè)是，證明你的結(jié)論.R1n R2是A上的等價關(guān)系.事實(shí)上，18 ,(1)因R1 ,R2是A上的自反關(guān)系，有IaR1 ,IaRz,因此，1aR1n R2 ,即&n R2是a上的自反關(guān)系.(2)因R1 , R2是A上的對稱關(guān)系，有R1 = R1-1 , R2= R2-1 ,而(R1 n R2)-1=R1-1n R2-1二rj R2 ,因此,R1 n R2是a上的對稱關(guān) 系. 因R1 , R2是A上的傳遞關(guān)系，有R12 R1 , R22 R2 ,而(Rd R2)2=(R1 n 劃(R1 n R2)=R12 n r,2 n R1 R2 n R2 R1 R12 n R2

7、2 R1 n R2,因此，R1n R2是a上的傳遞關(guān)系.4. 設(shè)無向連通圖G如以下圖，求其最小生成樹T及T的權(quán)W(T), 寫出G的對應(yīng)于T的根本回 路系統(tǒng)和根本割集系統(tǒng).G的最小生成樹T如圖(以實(shí) 線表示)，權(quán)W(T)=11.G的對應(yīng)于T的根本回路系統(tǒng) 為 Cbd , Ccd, Cde,其中Cbd=bdab , Ccd=cdabc ,Cde二dead.G的對應(yīng)于T的根本割集系統(tǒng)為Sab , Sad , We , Sbc,其中Sab=ab , bd , cd, Sad= ad , bd , cd , de,Sae=ae , de, Sbc二be, cd.5. 設(shè)B,，0 , 1是布爾代數(shù),式(a

8、 b) (a (b c)c.a , b , c B,化簡公(a b) (a (b c)') c=(a b) (a (b' c') c=(a b) (a (b' c') c)=(a b) (a c) (b' c' c)=(a b) (a c)=(a (a c) (b a c)=(a c) (a c b)=a c四、 證明題(共20分)1.在自然推理系統(tǒng)中，構(gòu)造推理證明:前提：x (F(x) G(x)結(jié)論： xF(x) xG(x)證明:(1)xF(x)附加前提引入(2)x F(x)(1)置換(3)F(c)(2)EI規(guī)那么(4)x (F(x)

9、G(x)前提引入(5)F(c) G(c)(4)UI規(guī)那么裝(6)G(c)(3)(5)析取三段論裝(7)xG(x)(6)EG規(guī)那么訂2.設(shè)代數(shù)系統(tǒng)A,是獨(dú)異點(diǎn)，e是其單位元.假設(shè)a A,有 a a=e,證明：A, 是Abel群.線證明：由于對 aA,有a a=e,因此，A中任意兀素a都有逆元，且 a=a-1 .又 A,是有單位元的獨(dú)異點(diǎn)，從而A, 是群.a, b A,有a bA,且a=a-1, b=b-1, (a b)-1二a b.又(a b)-1=b-1 a-1=b a,因此匕 a b=b a,即A, 是Abel群.3.證明：假設(shè)無向圖G為歐拉圖，那么G無橋.證明：(1)假設(shè)G中有橋，不妨設(shè)e

10、=(u，v)為其一座橋.這 樣，從中刪去邊e=(u, v)后，所得圖G'定不連通(G'至少含有 兩個連通分支).由于G為歐拉圖，因此它是連通圖，且有經(jīng)過每條邊一次且 僅一次的回路，這條回路必經(jīng)過 G的所有頂點(diǎn).從而存在頂點(diǎn)vi, V2,，Vs,使得UV1V2Vsvu是G的一條回路.從G中刪去邊e=(u, v)后，所得圖G'仍有從u到v的通路uviV2VsV,這樣G'仍是連通 圖.矛盾.因此，G中一定無橋.(2)由于G為歐拉圖，其每個頂點(diǎn)的度數(shù)均為偶數(shù).假設(shè) G 中有橋，不妨設(shè)e=(u, v)為其一座橋.這樣，從中刪去邊e=(u, v)后，所得圖G'至少有兩個連通分支.而且，頂點(diǎn) u, v的度數(shù)都 是奇數(shù)，這與每個連通分支為圖矛盾(與握手定理矛盾)，因此， G中一定無橋.五、 應(yīng)用題(10分)今有a, b, c, d, e, f和g七人，a會講英語；b會講英 語和漢語；c會講英語、意大利語和俄語；d會講漢語和日語；e會講德語和意大利語；f會講法語、日語和俄語；g會講法語和