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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、表方法（略）。2、5分 5分3、任給有三種情況：（1）存在使成立；1分（2）存在使成立而不存在使成立；或者反之；1分（3）不存在，使成立。1分對(duì)于（1），顯然有即；3分對(duì)于（2）（3），均有。2分因?yàn)榛蚝突蚝汀?分綜上所述，故。4、首先證明滿足結(jié)合律，任給，因?yàn)槎?，因此，滿足結(jié)合律。5分其次證明有幺元0，任給，有：，故0是的幺元。5分 綜上所述，是獨(dú)異點(diǎn)。二、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的所有簡(jiǎn)

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

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

22、4、首先證明滿足結(jié)合律，任給，因?yàn)槎?，因此，滿足結(jié)合律。5分，其次證明有幺元0，任給，有：，故0是的幺元。5分綜上所述，是獨(dú)異點(diǎn)。二、1、主合取范式，主析取范式為：。5分2、3分3分 3分3分 3分3、（1）、5分（2）、到的所有簡(jiǎn)單路共4條，它們是到的所有基本路共2條，它們是：5分（3）、所有基本回路共3條，它們是：。所有簡(jiǎn)單回路除上3個(gè)基本回路外，還有1個(gè)，它是5分4、根據(jù)解題過程分步給分。專業(yè)：信息與計(jì)算科學(xué) 課程名稱： 離散數(shù)學(xué) 學(xué)分： 3 試卷編號(hào)（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每錯(cuò)一處扣1分，扣到10分為止2（10分）用等值演算法判斷下列公式的類型qÙØ(p®q) Û qÙØ(ØpÚq) （蘊(yùn)涵等值式） Û qÙ(pÙØq) （德摩根律） Û pÙ(qÙØq) （交換律，結(jié)合律） Û 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號(hào)，則明天是5號(hào). 今天是1號(hào). 所以明天是5號(hào).解 設(shè)p：今天是1號(hào)，q：明天是5號(hào). (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結(jié)論：Øq證明（用歸繆法） q 結(jié)論否定引入 r®s 前提引入 Øs 前提引入 Ør 拒取式 Ø(pÙq)Úr 前提引入 Ø(pÙq) 析取三段論 

27、16;pÚØq 置換 Øp 析取三段論 p 前提引入 10 ØpÙp 合取 二、第二部分1（10分）在一階邏輯中將下面命題符號(hào)化正數(shù)都大于負(fù)數(shù)令F(x)：x為正數(shù)，G(y)：y為負(fù)數(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分）設(shè)偏序集<A, >如下圖所示，求A的極小元、最小元、極大元、最大元. 設(shè)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關(guān)于gcd, lcm運(yùn)算構(gòu)成的布爾代數(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分）對(duì)權(quán)構(gòu)造一棵最優(yōu)二元樹，并求權(quán)和解：過程由下圖給出， 求下圖的最小生成樹，并求最小權(quán)和232221222每錯(cuò)一處扣0.5分，扣到10分為止一、第一部分1（10分）寫出下列公式的真值表B = (q®p) Ùq®pp q q®p(q®p) Ùq(q®p) Ùq®p0 00 11 01 1101100011111每錯(cuò)一處扣1分，扣到10分為止2（10分）用等值演算法

30、判斷下列公式的類型(p®q)«(Øq®Øp) Û (ØpÚq)«(qÚØp) （蘊(yùn)涵等值式） Û (Ø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號(hào)，則明天是5號(hào). 明天是5號(hào). 所以今天

32、是1號(hào).解 設(shè)p：今天是1號(hào)，q：明天是5號(hào). (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 結(jié)果不含m1, 故01時(shí)成假賦值，所以推理不正確5（10分）用附加前提證明法構(gòu)造證明前提：pÚq, p®r, r®Øs 結(jié)論：s®q證明 s 附加前提引入 p®r 前提引入 r®Øs 前提引入 p®Øs 假言三段論 Øp 拒取式 pÚq 前提引入 q 析取三段論 二、第二部分1（10分）在一階邏輯中將下面命題符號(hào)化有的無理數(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和關(guān)系R的表達(dá)式。 解 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分）設(shè)G=e, a, b, c是Klein四元群. 給出G的所有自同構(gòu). 解 設(shè)j是G的自同構(gòu), 則j(e)=e, 且j是雙射. 因此滿足這些條

35、件的映射只有以下六個(gè)：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 經(jīng)驗(yàn)證，"x,yG都有 ji(xy) = ji(x) ji(y), i=1,2,6 上述j1, j2, j6是G上的全體自同構(gòu) 4（10分）寫出下圖中L1， L2， L3的原子。解 L1的原子是a, L2的原子是a, b, c, L3的原子是a和b. 5（10分）寫出下圖所示樹產(chǎn)生的前綴碼解 所示樹產(chǎn)生的前綴碼為00, 10, 11, 011, 01

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

37、r) Û (pÙ(qÚØq)Ùr （分配律） Û pÙ1Ùr （排中律） Û pÙr （同一律） 由最后一步可知，不是矛盾式，也不是重言式，它是可滿足式，其實(shí)101, 111是成真賦值，000, 010等是成假賦值. 3（10分）用主析取范式判兩個(gè)公式是否等值 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)結(jié)詞完備集Ø, Ù, Ú為完備集，而Øp Û ØpÙØp Û Ø(pÚp) Û p¯p pÙq Û Ø(ØpÚ&#