離散數學試題(2008)_C(答案)

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

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

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互質的正整數：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. 設集合=a，b，c，d上的二元關系r=áa，bñ，áb，añ，áb，cñ，ác，dñ，利用集合運算求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個頂點的所有自補圖(2) 給出具有5個頂點的所有自補圖（1）cbdacbda（2） 5. 若r1，r2均是非空集合a上的等價關系，那么r1，r2的交r1r2、并r1r2和復合r1 r2

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

10、不一定滿足傳遞性，例如：設a=a，b，cr1=áa，bñ，r2=áb，cñ，則r1r2=áa，bñ，áb，cñ不是a上的傳遞關系四、 證明題（每小題10分，共20分）1. 在一階邏輯中構造下面推理的證明前提："x(f(x)® g(x)，Ø"x(f(x)®h(x) 結論：$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. 設h£g，"a，bÎg，定義áa，bñ&#

12、206;rÛab-1Îh，證明r是g上的等價關系，求出等價關系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