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

1、班級： 學(xué)號： 姓名： 裝 訂 線哈爾濱工程大學(xué)試卷考試科目：離散數(shù)學(xué)（061121，061131）題號一二三四五總分分?jǐn)?shù)評卷人一、 填空題（每小題3分，共15分）1. 謂詞公式"xf(x)®Ø$yg(x，y)的前束范式為 $x"y(f(x)®Øg(z，y) 2. 設(shè)有群áz12，Åñ和áz3，Åñ，令j ：z12® z3，j(x)=(x) mod3，則j是áz12，Åñ到áz3，Åñ 的 滿同態(tài)映射 3.

2、 已知n階無向簡單圖g有m條邊，則g的補(bǔ)圖有n(n-1)/2-m條邊4. 有理數(shù)集上定義二元運(yùn)算*為a*b=a+b-ab，則運(yùn)算*的單位元為 0 ，零元為 1 5. 設(shè)無向連通圖g有6個頂點(diǎn)10條邊，t為g的生成樹，對應(yīng)t的基本割集系統(tǒng)中的基本割集個數(shù)為 5 ，基本回路系統(tǒng)中的基本回路個數(shù)為 6 二、 選擇題（每小題3分，共15分）1. 命題公式¬(pÙq)(p®¬q)的類型是 【a】a重言式 b非重言式的可滿足式c矛盾式 d簡單析取式2. 無向樹t中有4度，3度，2度頂點(diǎn)各1個，其余頂點(diǎn)都是樹葉，則t中樹葉片數(shù)為 【d】a1 b8c7 d53. 素數(shù)階

3、群一定是 【b】a無限群 b循環(huán)群，也是abel群c非交換群 d循環(huán)群4. 下列圖中那一個是歐拉圖 【a】ak4，4 bk4ck3，4 dk3，35. 下列圖中是哈密爾頓圖的是 【b】ak3，4 bk5ck2 dk1，1三、 計算與簡答題（每小題10分，共50分）1. 利用等值演算方法求命題公式(pÚq)Ù(p®q)«(q®p)的主析取范式；并指出該公式的成真賦值和成假賦值(pÚq)Ù(p®q)«(q®p)Û(pÚq)Ù(ØpÚq)«(

4、ØqÚp)Ûq«(ØqÚp)Û(q®(ØqÚp)Ù(ØqÚp)®q)ÛØqÚ(ØqÚp)ÙØ(ØqÚp)ÚqÛ(ØqÚp)Ù(qÙØp)Úq)Û(ØqÚp)ÙqÛ(ØqÙq)Ú(pÙq)Ûp

5、ÙqÛm3原公式的主析取范式為m3；原公式的成真賦值為11；成假賦值為00，01，102. 求群áz20，Åñ的所有生成元和子群á2ñá1ñá5ñá0ñá10ñá4ñ群áz20，Åñ的所有生成元為與20互質(zhì)的正整數(shù)：1，3，7，9，11，13，17，1920的所有正因子為1，2，4，5，10，20，所以，z20=á1ñ有6個循環(huán)子群，分別為á120/1ñ=&

6、#225;120ñ=á0ñ=0，á120/2ñ=á110ñ=á10ñ=0，10，á120/4ñ=á15ñ=á5ñ=0，5，10，15，á120/5ñ=á14ñ=á4ñ=0，4，8，12，16á120/10ñ=á12ñ=á2ñ=0，2，4，6，8，10，12，14，16，18，á120/20ñ=á11

7、ñ=á1ñ=z203. 設(shè)集合=a，b，c，d上的二元關(guān)系r=áa，bñ，áb，añ，áb，cñ，ác，dñ，利用集合運(yùn)算求r的傳遞閉包t(r)r2=áa，añ，áa，cñ，áb，bñ，áb，dñ，r3=áa，bñ，áa，dñ，áb，añ，áb，cñ，r4=áa，añ，áa，cñ，

8、5;b，bñ，áb，dñ=r2，r5=r3，從而，t(r)=rr2r3r4=áa，añ，áa，bñ，áa，cñ，áa，dñ，áb，añ，áb，bñ，áb，cñ，áb，dñ，ác，dñ4. (1) 給出具有4個頂點(diǎn)的所有自補(bǔ)圖(2) 給出具有5個頂點(diǎn)的所有自補(bǔ)圖（1）cbdacbda（2） 5. 若r1，r2均是非空集合a上的等價關(guān)系，那么r1，r2的交r1r2、并r1r2和復(fù)合r1 r2

9、也是a上的等價關(guān)系嗎？簡要說明理由r1r2是a上的等價關(guān)系事實(shí)上，(1)因r1，r2是a上的自反關(guān)系，有iaÍr1，iaÍr2，因此，iaÍr1r2，即r1r2是a上的自反關(guān)系(2)因r1，r2是a上的對稱關(guān)系，有r1r1-1，r2r2-1，而(r1r2)-1=r1-1r2-1=r1r2，因此，r1r2是a上的對稱關(guān)系(3)因r1，r2是a上的傳遞關(guān)系，有r12Ír1，r22Ír2，而(r1r2)2=(r1r2)o(r1r2)=r12r22r1or2r2or1Ír12r22Ír1r2，因此，r1r2是a上的傳遞關(guān)系r1r2并

10、不一定滿足傳遞性，例如：設(shè)a=a，b，cr1=áa，bñ，r2=áb，cñ，則r1r2=áa，bñ，áb，cñ不是a上的傳遞關(guān)系四、 證明題（每小題10分，共20分）1. 在一階邏輯中構(gòu)造下面推理的證明前提："x(f(x)® g(x)，Ø"x(f(x)®h(x) 結(jié)論：$x(f(x) Ùg(x) ÙØh(x)(1) Ø"x(f(x)®h(x) 前提引入(2) $xØ(f(x)®h(x)

11、(1)置換(3) Ø(f(c)®h(c) (2)ei規(guī)則(4) f(c)ÙØh(c) (3)置換(5) f(c) (4)化簡(6) "x(f(x)® g(x) 前提引入(7) f(c)® g(c) (7)ui規(guī)則(8) g(c) (5)(8)假言推理(9) f(c)Ùg(c)ÙØh(c) (4)(8)合取(10) $x(f(x) Ùg(x) ÙØh(x) (9)eg規(guī)則2. 設(shè)h£g，"a，bÎg，定義áa，bñ&#

12、206;rÛab-1Îh，證明r是g上的等價關(guān)系，求出等價關(guān)系r的等價類自反性："aÎg, aa-1=eÎhÞáa, añÎr對稱性："a，bÎg，áa，bñÎrÞab-1ÎhÞ(ab-1)-1Îh=ba-1ÎhÞáb，añÎr傳遞性："a，b，cÎg，áa，bÎñr，áb，cÎñrÞab-1Îh， bc-1Îh=ab-1bc-1ÎhÞac-1Îh