離散數(shù)學樣卷十二套(含答案)

1、一、 證明下列各題1、 （10分）證明蘊涵式：2、（10分）證明：5、 3、（10分）給定代數(shù)結構和，其中是自然數(shù)集合，是數(shù)的乘法。設，定義為：試證。4、（10分）給定代數(shù)結構，其中是實數(shù)集合，對中任意元和，定義如下：試證明：是獨異點。二、 求下列各題的解：1、試求下列公式的主析取范式和主合取范式（15分）：2、（15分）（1）、（2）、，（3）、，（4）、，（5）、3、（15分給定無向圖，如圖，試求：F E D CA B （1） 從A到D的所有基本鏈；（2） 從A到D的所有簡單鏈；（3） 長度分別是最小和最大的簡單圈；（4） 長度分別是最小和最大的基本圈；（5） 從A到D的距離。4、（15分

2、）給定二部圖，如圖 試求到的最大匹配一、 證明下列各題1、 （10分）證明蘊涵式：2、（10分）證明：3、（10分）給定群，則為Abel群4、（10分）給定代數(shù)結構，其中S中元為實數(shù)有序對，定義為，試證是可交換獨異點。二、 求下列各題的解：1、試求下列公式的主析取范式和主合取范式（15分）：2、（15分）設試求和。v5 v4 v3v1 v23、（15分）給定有向圖，如圖，試求：（1）、各結點的出度、入度和度；（2）、從v1到v3的所有簡單路和基本路；（3）、所有簡單回路和基本回路。4、（15分）給定樹G，試求對應二叉樹一、 證明下列各題1、 （10分）證明蘊涵式：2、（10分）證明：3、（10

3、分）給定代數(shù)結構和，其中是自然數(shù)集合，是數(shù)的乘法。設，定義為：試證。4、（10分）給定代數(shù)結構，其中S中元為實數(shù)有序對，定義為，試證是可交換獨異點。二、 求下列各題的解：1、試求下列公式的主析取范式和主合取范式（15分）：2、（15分）（1）、（2）、，（3）、，（4）、，（5）、v5 v4 v3v1 v23、（15分）給定有向圖，如圖，試求：（1）、各結點的出度、入度和度；（2）、從v1到v3的所有簡單路和基本路；（3）、所有簡單回路和基本回路。4、（15分）給定樹G，試求對應二叉樹專業(yè):信息與計算科學課程名稱:離散數(shù)學學分:3試卷編號（D）課程編號:4114600考試方式:閉 卷考試時間:

4、120分鐘擬卷人(簽字):擬卷日期:審核人(簽字)：得分統(tǒng)計表題 號一二總 分得 分一、第一部分得 分閱卷人1（10分）寫出下列公式的真值表A = (pÚq) ®Ør2（10分）用等值演算法判斷下列公式的類型qÙØ(p®q)3（10分）求主析取范式(p®Øq)®r4（10分）判斷下面推理是否正確若今天是1號，則明天是5號. 今天是1號. 所以明天是5號.5（10分）用歸繆法證明前提：Ø(pÙq)Úr, r®s, Øs, p 結論：Øq二、第二部分

5、得 分閱卷人1（10分）在一階邏輯中將下面命題符號化正數(shù)都大于負數(shù)2（10分）設偏序集<A, >如下圖所示，求A的極小元、最小元、極大元、最大元. 設Bb,c,d, 求B的下界、上界、下確界、上確界. 3（10分）G=Z12是12階循環(huán)群,寫出 G的所有子群4（10分）考慮110的正因子集合S110關于gcd, lcm運算構成的布爾代數(shù). 寫出它所有的子布爾代數(shù)5（10分）對權構造一棵最優(yōu)二元樹，并求權和。 求下圖的最小生成樹，并求最小權和2413332223225522專業(yè):信息與計算科學課程名稱:離散數(shù)學學分:3試卷編號（E）課程編號:4114600考試方式:閉 卷考試時間:1

6、20分鐘擬卷人(簽字):擬卷日期:審核人(簽字)：得分統(tǒng)計表題 號一二總 分得 分一、第一部分得 分閱卷人1（10分）寫出下列公式的真值表B = (q®p) Ùq®p2（10分）用等值演算法判斷下列公式的類型(p®q)«(Øq®Øp)3（10分）求主合取范式(p®Øq)®r4（10分）判斷下面推理是否正確若今天是1號，則明天是5號. 明天是5號. 所以今天是1號5（10分）用附加前提證明法構造證明前提：pÚq, p®r, r®Øs結論：s

7、4;q二、第二部分得 分閱卷人1（10分）在一階邏輯中將下面命題符號化有的無理數(shù)大于有的有理數(shù)2（10分）已知偏序集<A,R>的哈斯圖如下圖所示, 試求出集合A和關系R的表達式.。 3（10分）設G=e, a, b, c是Klein四元群. 給出G的所有自同構.4（10分）寫出下圖中L1， L2， L3的原子。5（10分）寫出下圖所示樹產生的前綴碼 專業(yè):信息與計算科學課程名稱:離散數(shù)學學分:3試卷編號（F）課程編號:4114600考試方式:閉 卷考試時間:120分鐘擬卷人(簽字):擬卷日期:審核人(簽字)：得分統(tǒng)計表題 號一二總 分得 分一、第一部分得 分閱卷人1（10分）寫出下

8、列公式的真值表C = Ø(ØpÚq) Ùq2（10分）用等值演算法判斷下列公式的類型(pÙq)Ú(pÙØq)Ùr)3（10分）用主析取范式判兩個公式是否等值 p®(q®r) 與 (pÙq)®r p®(q®r) 與 (p®q)®r4（10分）證明¯為聯(lián)結詞完備集5（10分）直接證明法構造證明前提：(pÚq)®r, r®s, Øs結論：ØpÙØq二、第

9、二部分得 分閱卷人1（10分）在一階邏輯中將下面命題符號化（1）人都愛美（2）有人用左手寫字個體域分別為(a) D=“人類集合”=x | x是人(b) D為全總個體域2（10分）分別畫出下列各偏序集的哈斯圖，再求出最大元、最小元、極大元和極小元 A a,b,c,d,e <a,b>,<a,c>,<a,d>,<a,e>,<b,e>,<c,e>,<d,e>IA3（10分）設 f：RR, g：RR 求fog, gof. 如果f和g存在反函數(shù), 求出它們的反函數(shù).4（10分）下圖中的L1, L2, L3和L4是否是有補格

10、。 5（10分）用Huffman算法產生最佳前綴碼在通信中，八進制數(shù)字出現(xiàn)的頻率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5%求傳輸它們的最佳前綴碼，并求傳輸10000個按上述比例出現(xiàn)的八進制數(shù)字需要多少個二進制數(shù)字？若用等長的（長為3）的碼字傳輸需要多少個二進制數(shù)字？ 專業(yè):信息與計算科學課程名稱:離散數(shù)學學分:3試卷編號（G）課程編號:411461考試方式:閉 卷考試時間:100分鐘擬卷人(簽字): 擬卷日期:審核人(簽字)：得分統(tǒng)表:題 號一二三四總 分得 分得 分閱卷人一、將下列命題符號化：（本題共題,每題分,滿分分.）小明學習和體育

11、都好.只有努力才能成功.存在函數(shù)連續(xù)但不可導（論域為全總個體域）凡有理數(shù)均可表示成分數(shù)（論域為全總個體域）.得 分閱卷人二、計算題：（本題共小題,滿分分.）求公式的主析取范式和主合取范式（分）.設.求（分）.設問上共有多少個不同的等價關系（分）.得 分閱卷人三、應用題：（本題共小題,滿分分.）.畫出集合上整除關系的哈斯圖，指出最大元、最小元、極大元和極小元（分）. .設是半群，“”運算定義如下表（分）：abcdaabcdbbcdaccdabddabc .證明是一個循環(huán)含幺半群，并給出它的生成元； .把中的每個元素均表示成生成元的冪. .設是一個代數(shù)系統(tǒng)，均為有理數(shù)，其中為普通加法和普通乘法，問

12、是否為域？為什么？（分）得 分閱卷人四、證明題：（本題共小題,滿分分.）.給定代數(shù)系統(tǒng)設是從到的同態(tài)，是從到的同態(tài).證明:是從到的同態(tài).（分）：.構造下列推理的證明（分）：前提：結論：專業(yè):信息與計算科學課程名稱:離散數(shù)學學分:3試卷編號（H）課程編號:4114600考試方式:閉 卷考試時間:100分鐘擬卷人(簽字): 擬卷日期:審核人(簽字)：得分統(tǒng)表:題 號一二三四總 分得 分得 分閱卷人一、將下列命題符號化：（本題共題,每題分,滿分分.）小明學習好或體育好.除非努力才能成功.存在函數(shù)連續(xù)且可導（論域為全總個體域）有的有理數(shù)能被整除（論域為全總個體域）.得 分閱卷人二、計算題：（本題共小題

13、,滿分分.）化一階邏輯公式為前束范式（分）.設.求（分）.設問上共有多少個不同的等價關系（分）.得 分閱卷人三、應用題：（本題共小題,滿分分.）.畫出集合上整除關系的哈斯圖，指出極大元和極小元（分）. abcaabcbbcaccab.設是半群，“”運算定義如下表（分）： .證明是一個循環(huán)含幺半群，并給出它的生成元； .把中的每個元素均表示成生成元的冪. .設是一個代數(shù)系統(tǒng)，均為有理數(shù)，其中為普通加法和普通乘法，問是否為域？為什么？（分）得 分閱卷人四、證明題：（本題共小題,滿分分.）.設、分別是兩代數(shù)系統(tǒng)上的同態(tài)，其中可交換，令是從到的函數(shù)，對有：.證明:是從到的同態(tài).（分）：.構造下列推理的

14、證明（分）：前提：結論：專業(yè):信息與計算科學課程名稱:離散數(shù)學學分:3試卷編號（I）課程編號:4114600考試方式:閉 卷考試時間:100分鐘擬卷人(簽字): 擬卷日期:審核人(簽字)：得分統(tǒng)表:題 號一二三四總 分得 分得 分閱卷人一、將下列命題符號化：（本題共題,每題分,滿分分.）只要努力過就不會后悔.我在城在.所有孩子都崇拜某些偶像（論域為全總個體域）一切房子都不一樣大（論域為全總個體域）.得 分閱卷人二、計算題：（本題共小題,滿分分.）求公式的主析取范式和主合取范式（分）.設.求（分）.設問上共有多少個不同的等價關系（分）.得 分閱卷人三、應用題：（本題共小題,滿分分.）.畫出集合上

15、整除關系的哈斯圖，指出極大元和極小元（分）. .設，“”為上的二元運算，“”運算定義如下表（分）：eabceeabcaaecbbbceaccbae .是否能構成一個群？ .有何性質？ .設是一個代數(shù)系統(tǒng)，均為有理數(shù)，其中為普通加法和普通乘法，問是否為域？為什么？（分）得 分閱卷人四、證明題：（本題共小題,滿分分.）.設有證明:是上的自同構（分）：.構造下列推理的證明（分）：前提：結論：得 分閱卷人一、 證明下列各題1、 （10分）證明蘊涵式：2、（10分）證明：5、 3、（10分）給定代數(shù)結構和，其中是自然數(shù)集合，是數(shù)的乘法。設，定義為：試證。4、（10分）給定代數(shù)結構，其中是實數(shù)集合，對中任

16、意元和，定義如下：試證明：是獨異點。得分閱卷人二、 求下列各題的解：1、試求下列公式的主析取范式和主合取范式（15分）：2、（15分）（1）、（2）、，（3）、，（4）、，（5）、3、（15分給定無向圖，如圖，試求：F E D CA B （1） 從A到D的所有基本鏈；（2） 從A到D的所有簡單鏈；（3） 長度分別是最小和最大的簡單圈；（4） 長度分別是最小和最大的基本圈；（5） 從A到D的距離。4、（15分）給定二部圖，如圖 試求到的最大匹配。業(yè)：信息與計算科學課程名稱： 離散數(shù)學 學分： 3 試卷編號( K)課程編號： 4114600 考試方式： 閉卷 考試時間： 100 分鐘擬卷人(簽字)

17、： 擬卷日期： 審核人(簽字)： 得分統(tǒng)計表： 題號一二總 分得分得 分閱卷人一、 證明下列各題1、 （10分）證明蘊涵式：2、（10分）證明：3、（10分）給定群，則為Abel群4、（10分）給定代數(shù)結構，其中S中元為實數(shù)有序對，定義為，試證是可交換獨異點。得分閱卷人二、 求下列各題的解：1、試求下列公式的主析取范式和主合取范式（15分）：2、（15分）設試求和。v5 v4 v3v1 v23、（15分）給定有向圖，如圖，試求：（1）、各結點的出度、入度和度；（2）、從v1到v3的所有簡單路和基本路；（3）、所有簡單回路和基本回路。4、（15分）給定樹G，試求對應二叉樹得 分閱卷人一、 證明下

18、列各題1、 （10分）證明蘊涵式：2、（10分）證明：3、（10分）給定代數(shù)結構和，其中是自然數(shù)集合，是數(shù)的乘法。設，定義為：試證。4、（10分）給定代數(shù)結構，其中S中元為實數(shù)有序對，定義為，試證是可交換獨異點。得分閱卷人二、 求下列各題的解：1、試求下列公式的主析取范式和主合取范式（15分）：2、（15分）（1）、（2）、，（3）、，（4）、，（5）、v5 v4 v3v1 v23、（15分）給定有向圖，如圖，試求：（1）、各結點的出度、入度和度；（2）、從v1到v3的所有簡單路和基本路；（3）、所有簡單回路和基本回路。4、（15分）給定樹G，試求對應二叉樹答案：一、1、或用推理方法，或用真值

19、表方法（略）。2、5分 5分3、任給有三種情況：（1）存在使成立；1分（2）存在使成立而不存在使成立；或者反之；1分（3）不存在，使成立。1分對于（1），顯然有即；3分對于（2）（3），均有。2分因為或和或和。2分綜上所述，故。4、首先證明滿足結合律，任給，因為而故，因此，滿足結合律。5分其次證明有幺元0，任給，有：，故0是的幺元。5分 綜上所述，是獨異點。二、1、主析取范式為3分2、 3分3分3分3分3分3、（1）、從A到D的所有基本鏈共有10條，即：ABD，ABED，ABCD，ABCED，ABECD，AFED，AFECD，AFEBD，AFEBCD，AFECBD。3分（2）、從A到D的所有簡

20、單鏈共有14條，即除（1）的10條外，還有ABCEBD，ABECBD，AFEBCED，AFECBED。3分（3）、長度最小的簡單圈共4個，即BCDB，BCEB，BDEB，CDEC，長度最大的簡單圈共2個，即ABCEBDEFA，AFEBCEDBA。3分（4）、長度最小的基本圈共4個，即同（3）；長度最大的基本圈有2個，為ABDCEFA；ABCDEFA3分； （5）、。3分4、到的最大匹配有多個，如，得分情況根據(jù)具體解題過程考慮。一、1、2、3、充分性：因為是群，又對任意，有 可見，是可交換的，故為Abel.必要性：為Abel群，自然是群；又對任意，有4、首先證明是可結合的，任給，有：而故滿足結合

21、律，是半群。5分其次證明有幺元，任給，有因此，是幺元。2分最后，證明滿足交換律，任給，有，故滿足見換律。3分綜上可知，是可交換獨異點。二、1、2、5分5分5分3、（1）、5分（2）、到的所有簡單路共4條，它們是到的所有基本路共2條，它們是：5分（3）、所有基本回路共3條，它們是：。所有簡單回路除上3個基本回路外，還有1個，它是5分 4、根據(jù)解題過程分步給分。一、1、或用真值表方法（略）。 2、 3、任給有三種情況：（1）存在使成立；1分（2）存在使成立而不存在使成立；或者反之；1分（3）不存在，使成立。1分對于（1），顯然有即；3分對于（2）（3），均有。2分因為或和或和。2分綜上所述，故。

22、4、首先證明滿足結合律，任給，因為而故，因此，滿足結合律。5分，其次證明有幺元0，任給，有：，故0是的幺元。5分綜上所述，是獨異點。二、1、主合取范式，主析取范式為：。5分2、3分3分 3分3分 3分3、（1）、5分（2）、到的所有簡單路共4條，它們是到的所有基本路共2條，它們是：5分（3）、所有基本回路共3條，它們是：。所有簡單回路除上3個基本回路外，還有1個，它是5分4、根據(jù)解題過程分步給分。專業(yè)：信息與計算科學 課程名稱： 離散數(shù)學 學分： 3 試卷編號（D）一、第一部分1（10分）寫出下列公式的真值表A = (pÚq) ®Ørp q rpÚq&#

23、216;r(pÚq)®Ør0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1001111111010101011101010每錯一處扣1分，扣到10分為止2（10分）用等值演算法判斷下列公式的類型qÙØ(p®q) Û qÙØ(ØpÚq) （蘊涵等值式） Û qÙ(pÙØq) （德摩根律） Û pÙ(qÙØq) （交換律，結合律） Û pÙ0 （矛盾律） &#

24、219; 0 （零律） 由最后一步可知，為矛盾式.3（10分）求主析取范式(p®Øq)®rÛ (pÙq)Úr （析取范式） (pÙq) Û (pÙq)Ù(ØrÚr)Û (pÙqÙØr)Ú(pÙqÙr)Û m6Úm7 rÛ (ØpÚp)Ù(ØqÚq)Ùr Û (ØpÙØqÙ

25、;r)Ú(ØpÙqÙr)Ú(pÙØqÙr)Ú(pÙqÙr) Û m1Úm3Úm5Úm7 , 代入并排序，得(p®Øq)®r Û m1Úm3Úm5Ú m6Úm7 （主析取范式）4（10分）判斷下面推理是否正確若今天是1號，則明天是5號. 今天是1號. 所以明天是5號.解 設p：今天是1號，q：明天是5號. (p®q)Ùp®q（用等值演算法）

26、 (p®q)Ùp®qÛ Ø(ØpÚq)Ùp)Úq Û ØpÚØqÚq Û 1 推理正確5（10分）用歸繆法證明前提：Ø(pÙq)Úr, r®s, Øs, p結論：Øq證明（用歸繆法） q 結論否定引入 r®s 前提引入 Øs 前提引入 Ør 拒取式 Ø(pÙq)Úr 前提引入 Ø(pÙq) 析取三段論 

27、16;pÚØq 置換 Øp 析取三段論 p 前提引入 10 ØpÙp 合取 二、第二部分1（10分）在一階邏輯中將下面命題符號化正數(shù)都大于負數(shù)令F(x)：x為正數(shù)，G(y)：y為負數(shù) L(x,y)：x>y "x(F(x)®"y(G(y)®L(x,y) Û "x"y(F(x)ÙG(y)®L(x,y)2（10分）設偏序集<A, >如下圖所示，求A的極小元、最小元、極大元、最大元. 設Bb,c,d, 求B的下界、上界、下確界、上確界. 解 極小

28、元：a, b, c, g； 極大元：a, f, h； 沒有最小元與最大元. B的下界和最大下界都不存在, 上界有d和f,最小上界為d. 3 （10分）G=Z12是12階循環(huán)群寫出 G的所有子群解 1階子群<12>=<0>=0 2階子群<6>=0,6 3階子群 <4>=0,4,8 4階子群 <3>=0,3,6,9 6階子群<2>=0,2,4,6,8,10 12階子群<1>=Z12 4（10分）考慮110的正因子集合S110關于gcd, lcm運算構成的布爾代數(shù). 寫出它所有的子布爾代數(shù)：解 1, 110 1, 2

29、, 55, 110 1, 5, 22, 110 1, 10, 11, 110 1, 2, 5, 10, 11, 22, 55, 110 5（10分）對權構造一棵最優(yōu)二元樹，并求權和解：過程由下圖給出， 求下圖的最小生成樹，并求最小權和232221222每錯一處扣0.5分，扣到10分為止一、第一部分1（10分）寫出下列公式的真值表B = (q®p) Ùq®pp q q®p(q®p) Ùq(q®p) Ùq®p0 00 11 01 1101100011111每錯一處扣1分，扣到10分為止2（10分）用等值演算法

30、判斷下列公式的類型(p®q)«(Øq®Øp) Û (ØpÚq)«(qÚØp) （蘊涵等值式） Û (ØpÚq)«(ØpÚq) （交換律） Û 1 由最后一步可知，為重言式3. （10分）求主合取范式(p®Øq)®rÛ (pÚr)Ù(qÚr) （合取范式） pÚr Û pÚ(qÙØq)Úr

31、Û (pÚqÚr)Ù(pÚØqÚr) Û M0ÙM2 qÚr Û (pÙØp)ÚqÚr Û (pÚqÚr)Ù(ØpÚqÚr) Û M0ÙM4 , 代入并排序，得(p®Øq)®r Û M0ÙM2ÙM4 （主合取范式） 4（10分）判斷下面推理是否正確若今天是1號，則明天是5號. 明天是5號. 所以今天

32、是1號.解 設p：今天是1號，q：明天是5號. (p®q)Ùq®p（用主析取范式法） (p®q)Ùq®pÛ (ØpÚq)Ùq®pÛ Ø (ØpÚq)Ùq)ÚpÛ ØqÚp Û (ØpÙØq)Ú(pÙØq)Ú (pÙØq)Ú(pÙq) Û m0Úm2Ú

33、m3 結果不含m1, 故01時成假賦值，所以推理不正確5（10分）用附加前提證明法構造證明前提：pÚq, p®r, r®Øs 結論：s®q證明 s 附加前提引入 p®r 前提引入 r®Øs 前提引入 p®Øs 假言三段論 Øp 拒取式 pÚq 前提引入 q 析取三段論 二、第二部分1（10分）在一階邏輯中將下面命題符號化有的無理數(shù)大于有的有理數(shù)令F(x)：x是無理數(shù)，G(y)：y是有理數(shù)， L(x,y)：x>y $x(F(x)Ù$y(G(y)ÙL(x

34、,y) Û $x$y(F(x)ÙG(y)ÙL(x,y) 2（10分）已知偏序集<A,R>的哈斯圖如下圖所示, 試求出集合A和關系R的表達式。 解 A=a,b,c,d,e,f,g,h R=<b,d>,<b,e>,<b,f>,<c,d>,<c,e>,<c,f>,<d,f>,<e,f>,<g,h>IA 3（10分）設G=e, a, b, c是Klein四元群. 給出G的所有自同構. 解 設j是G的自同構, 則j(e)=e, 且j是雙射. 因此滿足這些條

35、件的映射只有以下六個：j1：ee, aa, bb, cc j2：ee, aa, bc, cb j3：ee, ab, bc, ca j4：ee, ab, ba, cc j5：ee, ac, bb, ca j6：ee, ac, ba, cb 經驗證，"x,yG都有 ji(xy) = ji(x) ji(y), i=1,2,6 上述j1, j2, j6是G上的全體自同構 4（10分）寫出下圖中L1， L2， L3的原子。解 L1的原子是a, L2的原子是a, b, c, L3的原子是a和b. 5（10分）寫出下圖所示樹產生的前綴碼解 所示樹產生的前綴碼為00, 10, 11, 011, 01

36、00, 0101每錯一處扣2分，扣到10分為止一、第一部分1（10分）寫出下列公式的真值表C = Ø(ØpÚq) Ùqp q ØpØpÚqØ (ØpÚq)Ø (ØpÚq) Ùq0 00 11 01 11100110100100000每錯一處扣1分，扣到10分為止2（10分）用等值演算法判斷下列公式的類型(pÙq)Ú(pÙØq)Ùr)(pÙq)Ú(pÙØq)Ù

37、r) Û (pÙ(qÚØq)Ùr （分配律） Û pÙ1Ùr （排中律） Û pÙr （同一律） 由最后一步可知，不是矛盾式，也不是重言式，它是可滿足式，其實101, 111是成真賦值，000, 010等是成假賦值. 3（10分）用主析取范式判兩個公式是否等值 p®(q®r) 與 (pÙq)®r p®(q®r) 與 (p®q)®r解 p®(q®r) = m0Úm1Úm2

38、8;m3Ú m4Úm5Ú m7 (pÙq)®r = m0Úm1Úm2Úm3Ú m4Úm5Ú m7 (p®q)®r = m1Úm3Ú m4Úm5Ú m7 顯見，中的兩公式等值，而的不等值. 4（10分）證明¯為聯(lián)結詞完備集Ø, Ù, Ú為完備集，而Øp Û ØpÙØp Û Ø(pÚp) Û p¯p pÙq Û Ø(ØpÚ&#