06級(jí)離散數(shù)學(xué)期末試題B答案

1、06級(jí)離散數(shù)學(xué)期末試題 B答案一、計(jì)算題(共20分，每題5分)1、設(shè)A= a,b ，B= 0,1,2，求笛卡爾乘積 Ax B和A的冪集P(A)解 Ax B=va,0>,<a,1>,va,2>,vb,0>,vb,1>,vb,2.>P(A)=,a,b,a.b2、設(shè) A=1,2,3,4,A 上的關(guān)系 R=?1,1?,?1,2?,?2,4?,?3,1?,?4,3?,求 domR、ranR、R-1。解 domR=1,2,3,4,ranR=1,2,3,4, R -1 =?1,1?,?2,1?,?4,2?,?1,3?,?3,4?3、畫出集合2, 3, 4, 8, 9

2、, 10, 11上整除關(guān)系的哈斯圖，并求它的最大元、最小元、極大元、極小元 解 它的最大元、最小元都不存在；極大元為 8, 9, 10, 11;極小元為2, 3,11。114、設(shè) f: N N2N (N為自然數(shù)集合)，f ( x, y ) x2y，說明f是否為單射、滿射的？計(jì)算1f (0)。解f 丫0) =<0,0>不是單射，是滿射的.、判斷題(共10分，每題5分)1、設(shè)A= 1,2,3,4,5,8 ，R是A上的"模3同余關(guān)系。冋R是否為A上的等價(jià)關(guān)系？假設(shè)是，給出其等價(jià)類, 并畫出R的關(guān)系圖解 R 是 A 上的等價(jià)關(guān)系，等價(jià)類為1=4=1,42=5=8=2,5,83=3

3、R的關(guān)系圖如下：2、以下語句中哪些是命題？是命題的句子中哪些是復(fù)合命題？并將復(fù)合命題符號(hào)化。(1)小張與小劉住一個(gè)寢室。(2)只要天氣好，飛機(jī)就能正常降落。(3)請(qǐng)上樓！解 (1)是命題，不是復(fù)合命題；(2)是復(fù)合命題；設(shè) P:天氣好，q：飛機(jī)能正常降落，p q ;(3)不是命題；三、(共10分，每題5分)1、某電路中有1個(gè)燈泡和3個(gè)開關(guān)A、B、C。在下述任一情況下燈泡都會(huì)亮。將燈亮的情況用一個(gè) 命題公式表示出來(P: A翻開；q： B翻開；r: C翻開)。(1) C翻開，A和B關(guān)閉；(2) A翻開，B和C關(guān)閉；(3) B和C翻開，A關(guān)閉；(4) A和B翻開，C關(guān)閉。解 P: A 翻開；q：

4、B 翻開；r： C 翻開 (p A qA r)V( p A qA r)V( pA qA r)V( pA q A r)2、用等值演算法證明下面等值式p (q r) (p q) r。證 p (q r) p ( q r) ( p q) r (p q) (p q) r四、證明題(共20分，每題10分)1、構(gòu)造下述推理的證明：前提： x(F(x) G(x) A H(x), ( x) (F(x) A R (x)結(jié)論：(x) (F(x) A R (x) A G(x)證明：(1) ( x) (F(x) A R (x)P(2) F(c)A R(c)(1),EI(3) x(F(x) G(x) A H(x)P F(

5、c)G(c)A H(c)(3),UI(5) F(c)(2),化簡(jiǎn)(6) G(c)A H(c),(5),I假言推理(7)R(c)(2),化簡(jiǎn)(8)G(c)(6),化簡(jiǎn)(9) F(c)A R(c)A G(c)(5),(7),(8),合取(10)(x) (F(x)A R (x)A G(x) )(9)EG2、寫出對(duì)應(yīng)下面推理的證明：如果今天是星期一，那么要進(jìn)行英語或離散數(shù)學(xué)考試。如果英語老師有會(huì)，那么不考英語。今天是星期一,r:進(jìn)行離散數(shù)學(xué)英語老師有會(huì)。所以進(jìn)行離散數(shù)學(xué)考試。其中p：今天是星期一；q：進(jìn)行英語考試;考試；s：英語老師有會(huì)。前提：pT qV r , q, p, s結(jié)論：r證明：pq V

6、r前提引入p前提引入q V r假言推理sf q前提引入s前提引入q假言推理r析取三段論五、本大題共20分1、10分設(shè)圖中所示賦權(quán)圖表示某 7個(gè)城市及預(yù)先測(cè)算岀它們之間的一些直接通信線路的造價(jià)，試給岀一個(gè)設(shè)計(jì)方案，使得各城市間能夠通信，而又使總造價(jià)最小。要求畫岀其最小生成樹及最小生成樹 的補(bǔ)圖，并計(jì)算岀其最小總造價(jià)。該問題是求最小生成樹問題。圖的最小生成樹即為所求的通信線路圖設(shè)計(jì)方案。其權(quán)即是小總造價(jià)為1+3+4+8+9+23=48712、( 5分)設(shè)有向簡(jiǎn)單圖 D的度數(shù)序列為2、2、3、3,入度序列為0、0、2、3，試求D的出度序列和該解：出度序列為2、 2、 1、 0圖的邊數(shù)，并在圖4中畫出

7、該有向圖邊數(shù) m=( 2+2+3+3)12=53、( 5分)樹T有2個(gè)4度頂點(diǎn)，2個(gè)3度頂點(diǎn)，其余頂點(diǎn)全是樹葉。問T有幾片樹葉?解、設(shè)T有x片樹葉,n個(gè)頂點(diǎn)，m條邊n=2+2+x，m=n-1 = 4+x-1，由握手定理 2 (4+x-1)=2 4+2 3+xX 1 解得x=8，故T有8片樹葉.六、本大題共15分1、( 5分)設(shè)S=a,b，定義運(yùn)算*使a,b都是右零元，證明運(yùn)算*是可結(jié)合的。證明 因?yàn)?a*a=b*a=a a*b=b*b=bS上的運(yùn)算*是可結(jié)合的，因?yàn)閷?duì)任意x,y,z Sx*(y*z)=x*z=z=y*z=(x*y)*z因此運(yùn)算*是可結(jié)合的2、 (10分)設(shè)A,*是代數(shù)系統(tǒng)，其中 A=1,2,3,4。*定義如下表所示41 231234234134124123(1)運(yùn)算*是可交換的嗎？(2)求A中關(guān)于運(yùn)算*的單位元，并給岀每個(gè)元素的逆元。(3)A中有關(guān)于運(yùn)算*的零元嗎？解(1)運(yùn)算*是可交換的，因?yàn)檫\(yùn)算表是對(duì)稱的。(2) A中關(guān)于運(yùn)算*的單位元為1， 1的逆元是1，2的逆元是4，4的逆元是2，3的逆元是3(3) A中沒有關(guān)于運(yùn)算*的零元。七、(5分)設(shè)G為群，a G令f :G-G,f (x)=axa 1 2 3，x G,證明f是G的自同構(gòu)。證明 先證f為雙射假設(shè)f (x)= f (y)，那么axa 1= aya 1，由消