2012年6月離散數(shù)學(xué)期末考試題及答案

1、-裝 訂 線-上 海 海 事 大 學(xué) 試 卷2011 2012 學(xué)年第二學(xué)期期末考試 離散數(shù)學(xué) （A卷）班級(jí) 學(xué)號(hào) 姓名 總分 題 目得 分閱卷人注：P=1,2,3,.1.(6)用題中所提供的變?cè)獙⑾旅嬉欢握撌鲛D(zhuǎn)化成命題公式，然后給出形式化證明。如果天氣干燥，那么我將去遠(yuǎn)足或游泳。我去游泳當(dāng)且僅當(dāng)天氣暖和。所以，如果我沒(méi)去遠(yuǎn)足，則天氣是潮濕的或暖和的。(d, h, s, w)2.(5)判斷下列兩個(gè)謂詞蘊(yùn)含式的邏輯值。如果邏輯值為F，須舉例予以說(shuō)明【或者通過(guò)定義一個(gè)恰當(dāng)?shù)闹^詞說(shuō)明，或者在一個(gè)小的論域上（如U=a,b）通過(guò)給變?cè)x真值驗(yàn)證】。(a)。(b) 。3.(6)設(shè)A=1, 2, 3，.(a

2、) 求。(b) 列出A的所有子集。(c) 中哪些是無(wú)窮集合？4.(6)從集合1,2,3,1000中隨機(jī)取一個(gè)整數(shù)，該整數(shù)至少能被4,5或6中的一個(gè)整除的概率是多少。5.(5)整數(shù)集合Z上的關(guān)系R定義如下：(m,n)R當(dāng)且僅當(dāng).判斷R是否滿足自反，反自反，對(duì)稱，反對(duì)稱和傳遞屬性。R是否為等價(jià)關(guān)系？6.(5) 設(shè)R1和R2是集合S到T上的關(guān)系，R3是集合T到U上的關(guān)系。證明：7.(8 ) 集合S=1,2,3,4,5上關(guān)系R的關(guān)系矩陣是：，寫(xiě)出下列閉包運(yùn)算的布爾矩陣：(a)r(R)；(b)s(R)；(c)rs(R)；(d)sr(R)；(e)tsr(R)；(f)列出tsr(R)的等價(jià)類(lèi)；(g)畫(huà)出與關(guān)

3、系R對(duì)應(yīng)的關(guān)系圖，并計(jì)算該關(guān)系圖的可達(dá)性矩陣。簡(jiǎn)要說(shuō)明有向圖可達(dá)性矩陣和對(duì)應(yīng)的傳遞閉包之間的關(guān)系。8.(7)下表給出格關(guān)于”運(yùn)算的部分結(jié)果，例如，bd=d.abcdefaeaeeabddebcdecdedeef(a) 將表中剩余部分填滿。(b) 找出L的最大元素和最小元素。(c) 證明。(d) 畫(huà)出L的哈斯圖。9.(6)設(shè)f和g是Z到Z的映射，其中，g是集合的特征函數(shù)。(a)計(jì)算(b)計(jì)算。(c)確定函數(shù).(d)證明：10.(5)(a)證明若S和T是可數(shù)的，則S×T也是可數(shù)的；(b)證明若f是S到T的滿射并且S是可數(shù)的，則T也是可數(shù)的；(c)用(a)和(b)的結(jié)論證明有理數(shù)集合Q是可

4、數(shù)的。11.(8) 設(shè)是布爾代數(shù)B1和B2之間的一一對(duì)應(yīng)，且已知保持或運(yùn)算。(a)證明也保持或運(yùn)算；即，如果x,yB2和a,bB1且滿足，則(b)證明保持序關(guān)系；即，如果在B1中cd,則在B2中有。(c)證明如果01和02分別是B1和B2的全下界，則。(c)證明如果11和12分別是B1和B2的全上界，則。12.(8)設(shè)兩個(gè)變?cè)牟紶柡瘮?shù)的集合用BOOL(2)表示，B=0,1.(a)用列表形式寫(xiě)出布爾代數(shù)BOOL(2)的全部原子。(b)將定義在上的函數(shù)用BOOL(2)中的原子”表示出來(lái)。(c)寫(xiě)出布爾表達(dá)式的析取范式，并用BOOL(2)中的原子”表示出來(lái)。13.(5) 設(shè)完全圖K6的頂點(diǎn)為v1,

5、v2,v6.(a) K6中有多少個(gè)與K4同構(gòu)子圖？(b)從v1到v2所有長(zhǎng)度小于等于3的跡有幾條？(c) K6中所有長(zhǎng)度小于等于3的跡總共有幾條？14.(5) (a)畫(huà)一個(gè)能構(gòu)造3階de Bruijn序列的有向圖。(b)根據(jù)你所畫(huà)出的有向圖，寫(xiě)出兩個(gè)3階de Bruijn序列。15.(5)(a)一棵樹(shù)有n2個(gè)節(jié)點(diǎn)度數(shù)是2，n3個(gè)節(jié)點(diǎn)的度數(shù)是3，nk個(gè)節(jié)點(diǎn)的度數(shù)是k，問(wèn)它有幾個(gè)度數(shù)為1的節(jié)點(diǎn)。16.(5) (a)找出下圖的最小生成樹(shù)。(b)最小生成樹(shù)的總權(quán)重是多少？(c)此圖中Hamilton回路的最小權(quán)重是多少？(e)判斷此圖中有沒(méi)有Euler回路或Euler路，如果有的話，計(jì)算相應(yīng)的權(quán)重；如

6、果沒(méi)有的話，說(shuō)明原因。4354421344222217(5)假設(shè)要用字母C, E, L, S, U, Y的二進(jìn)制碼字編寫(xiě)信息，它們的使用頻率分別為7, 31, 20, 24, 12, 6.(a) 畫(huà)一顆使這些字母編碼效率最高的樹(shù)。(b) 用(a)中確定的編碼方法對(duì)信息CLUE進(jìn)行編碼。參考答案注：P=1,2,3,.1.(6)設(shè)：d:=天氣干燥; h:=我去遠(yuǎn)足; s:=我去游泳; w:=天氣暖和。(d, h ,s, w)條件：dhs, sw.結(jié)論：hdw證明： h附加前提 dhsP dhsTE dsTI swP swTI swTE dwTI2.(5)(a)真值F。例如，假設(shè)U=a,b,令p(x

7、,y)表示命題“x=y”,則邏輯蘊(yùn)含不成立。(b)真值T。3.(6)(a) (b) (c) 。4.(6)0.4665.(5)滿足自反，對(duì)稱，傳遞。是等價(jià)關(guān)系。6.(5) ,同理可得，所以，反之，設(shè)，則。若，若，總之，故。證畢。7.(8) (a) ; (b) ; (c) ;(d) ; (e) ; (f)1=1,5; 2=2,3,4.（g）與關(guān)系R對(duì)應(yīng)的關(guān)系圖如下和該關(guān)系圖的可達(dá)性矩陣如下： 513452一個(gè)有向圖可達(dá)性矩陣就是其對(duì)應(yīng)關(guān)系的傳遞閉包。8.(7)(a)表中紅色部分為填入元素。abcdefaaeaeeabebddebcadcdecdedddedeeeeeeefabcdef(b)L的最大

8、元素和最小元素分別為：e,f(c)證明,同理可證，(d)畫(huà)出L的哈斯圖如下：dfcbae9.(6)(e) 1,0,-1,0(f) 9,10,1,0(c)是E的特征函數(shù)，(d)證明：同理可證：10.(5)(a)，每個(gè)S×t是可數(shù)的，所以S×T也是可數(shù)的。(b)對(duì)每個(gè)tT,設(shè)g(t)是S的元素且f(g(t)=t,則g是單射函數(shù)。所以T是S的子集，已知S是可數(shù)的，所以S的子集T也是可數(shù)的。(c)由(a)可知，Z×P是可數(shù)的。又因?yàn)閺腪×P到Q存在滿射函數(shù)f,根據(jù)(b)的結(jié)論，Q是可數(shù)的。11.(8)(a) ， (b)若cd，則d=cd,所以(c)因?yàn)槭荁2上的滿射，所以在B1中存在e，使得(e)=02.故(d) 與(c)類(lèi)似，設(shè)(e)=12.則12.(8)(a)xyabcd001000010100100010110001(b)根據(jù)(a)中的記號(hào)，g=cd(c)根據(jù)(a)中的記號(hào)，= abd13.(5) (a)(b) 1+4+4×3=17(c) 6×5+6×5×4+6×5×4×4=63014.(5)(a)d10010001101100011(b)兩個(gè)序列如下：111111110000000015.(5