理工大學(xué)離散數(shù)學(xué)檢測題答案

1、-. z.*理工大學(xué)離散數(shù)學(xué)第一章檢測題答案一、填空題每空2分，共30分12 3， ， ， 。4，567二、單項選擇題每題2分，共20分 12345678910得分DBCBCDAACB三、簡答題每題6分，共12分1構(gòu)造命題公式的真值表 00011001110100001111100111011111001111112求命題公式的主析取*式和主合取*式。3判斷命題公式與 是否等價。解：等價四證明題共32分 10分用CP規(guī)則證明；1. P 6. T(4,5) I 2分2. P 7. T(3,4) I2分 3. T(1, 2) I 2分 8. T(6,7) I2分4. P(附加前提) 9. CP 2

2、分5. P 10分用歸謬法證明 證: 1 1分 2 3 2分 4 5 2分 6 7 2分 8 2分由8得出了矛盾，根據(jù)歸謬法說明原推理正確1分312分公安人員審理*珠寶商店的鉆石項鏈的失竊案，偵察結(jié)果如下：1營業(yè)員或盜竊了鉆石項鏈2假設(shè)作案，則作案時間不在營業(yè)時間3假設(shè)提供的證詞正確，則貨柜未上鎖4假設(shè)提供的證詞不正確，則作案發(fā)生在營業(yè)時間5貨柜上了鎖試問：作案者是誰？要求寫出推理過程。解：令表示“營業(yè)員盜竊了鉆石項鏈； 表示“營業(yè)員盜竊了鉆石項鏈；表示“作案時間在營業(yè)時間；表示“提供的證詞正確；表示“貨柜上了鎖。則偵察結(jié)果如下：， ，由此可推出作案者是4分推理過程如下：(1) (6) (2)

3、 (7) (5)，(6) 2分(3) (1)，(2) 2分 (8) (4) (9) (7)，(8) 2分(5) (3)，(4) 2分*理工大學(xué)離散數(shù)學(xué)第二章檢測題答案一、填空題每空3分，共30分1或23456； 78二、單項選擇題每題2分，共20分 12345678910得分AABDCACCBD簡答題每題6分，共12分1求謂詞公式的前束析取*式2證明：證：四證明題共38分 112分用謂詞演算的推理規(guī)則證明:，12 2分34I 2分56 2分7 I 2分8I 2分9I 2分2(10分) 指出下面推理證明過程中的錯誤，并給出正確的證明用謂詞演算的推理規(guī)則證明：證:：(1) P (6) T(4) I

4、 (2) US(1) (7) T(2),(5) I (3) P (8) T(6),(7) I(4) ES(3) (9) EG(8) (5) T(4) I該證明的錯誤在于: (1)、 (2) 與 (3)、 (4) 的順序顛倒了，應(yīng)該先指定存在后指定全稱。 2分正確的證明是：4分(1) P (6) T(2) I 1分(2) ES (1) 2分 (7) T(4),(5) I 1分(3) P (8) T(6),(7) I 1分(4) US (3) 2分(9) EG(8) 1分(5) T(2) I 316分符號化以下命題并推證其結(jié)論任何人如果他喜歡音樂,他就不喜歡體育每個人或者喜歡體育，或者喜歡美術(shù)有的

5、人不喜歡美術(shù)因而有的人不喜歡音樂設(shè)M(*)：*喜歡音樂，S(*)：*喜歡體育，(*)：喜歡美術(shù)該推理符號化為： 或前提：結(jié)論：4分證：1P 2 ES1 2分3 P 4 US3 2分5 T24I2分6 P7 US62分8 T7E 1分9 T58I2分10 EG9 1分*理工大學(xué)離散數(shù)學(xué)第三、四章檢測題答案一、填空題每空2分，共40分1 34反對稱，傳遞。 5；6，或單位矩陣7 4,6 ， 2,3 ， 無 ， 無 ， 12 ， 1 。8 , 。9單射，滿射；既是單射又是滿射； ； 二、單項選擇題每題2分，共20分 12345678910得分(1)(2)(1)(3)22(1)(3)(3)(1)三、簡

6、答題共30分16分設(shè)=1,2,3,5,6,10,15,30 ， “ 為集合上的整除關(guān)系。，是否為偏序集 假設(shè)是，畫出其哈斯圖；解：，是偏序集。其哈斯圖為：212分對以下圖所給的偏序集，求下表所列集合的上下界，上下確界，并將結(jié)果填入表中。子 集上 界下 界上 確 界下 確 界無無無無36分設(shè) =1,2,3,4,5,6，集合上的關(guān)系=1,3,1,5,2,5,4,4,4,5,5,4,6,3,6,6。1畫出的關(guān)系圖，并求它的關(guān)系矩陣；2求及 。解：1的關(guān)系圖為的關(guān)系矩陣為 2分2， 1分 1分 2分4設(shè)Z是整數(shù)集，是Z上的模3同余關(guān)系，即，試根據(jù)等價關(guān)系決定Z的一個劃分 。答案：由決定的Z的劃分為：，

7、 其中：四證明題共10分 設(shè) 定義為 ，證明：是雙射，并求出其逆映射。證：1先證明是入射2分 對任意的則有，從而有，故是入射。 2) 再證明是滿射2分對任意的從而是滿射。 綜合1、2知是雙射。為 ，對任意。1分*理工大學(xué)離散數(shù)學(xué)第五章檢測題答案一、填空題每空2分，共30分1. 23 4；1 5關(guān)于運(yùn)算不封閉6 2，7循環(huán)群，生成元 89關(guān)于封閉二、單項選擇題每題2分，共20分12345678910得分BCAABDDCBD三、簡答題共30分1設(shè)是實數(shù)集上的二元運(yùn)算，其定義如下： 1求23， 3(-5)和71/2。 2是半群嗎？可交換嗎？ 3求中關(guān)于的單位元。 4中哪些元素有逆元素，其逆元素是什么

8、？答案：117，-32，14.5。 2是半群，可交換。 30。 4當(dāng)時，有逆元素，。2設(shè)，是交換群，是的單位元。的運(yùn)算表如下：求，并說明道理。答案：。因為有限群的運(yùn)算表中的每行、每列都是群中元素的一個置換。3設(shè)集合，是定義在上的模11乘法即任意a,bG，有a*b=(ab)(mod11)，是普通乘法，問是循環(huán)群嗎？假設(shè)是，試找出它的生成元。答：的運(yùn)算表如下表所示。1 3 4 5 913459 1 3 4 5 93 9 1 4 54 1 5 9 35 4 9 3 19 5 3 1 4從運(yùn)算表可知，在上封閉、有幺元1，且，再由是可結(jié)合的得是循環(huán)群，3，4，5和9均為其生成元。四證明題共20分4分設(shè)是

9、獨(dú)異點(diǎn)，為其幺元，且對，有，證明是一個交換群。證明： 對，由于，則 ， 即中的每一個元素都有逆元素,故是一個群。又對，有，所以是一個Abel群。6分設(shè)是一個群，有試證明是一個自同構(gòu)證：首先證明是入射。3分其次證明是滿射。對 綜合以上兩點(diǎn)，知是雙射。3分*理工大學(xué)離散數(shù)學(xué)第六章檢測題答案一、填空題每空2分，共40分1. 上確界 和下確界， 2至少有一個補(bǔ)元素，不一定30，1；1，0 45； 6 ，二、單項選擇題每題2分，共20分12345678910得分D CB CADABDD三、簡答題共30分1下面哈斯圖表示的格中哪個元素?zé)o補(bǔ)元？對有補(bǔ)元的元素求出它們的補(bǔ)元解：c無補(bǔ)元1分，a的補(bǔ)元為e1分，

10、b的補(bǔ)元為d1分，d的補(bǔ)元為b、e1分，e的補(bǔ)元為a、d1分，0與1互為補(bǔ)元。1分2設(shè)是一個布爾代數(shù)且，求布爾表達(dá)式的析取*式和合取*式并計算的值。解：的析取*式為： 4分的合取*式為：4分2分3設(shè)=1,2,3,5,6,10,15,30 ， “ 為集合上的整除關(guān)系。(1)，是否為偏序集 假設(shè)是，畫出其哈斯圖；(2)，是否構(gòu)成格？為什么？(3)，是否構(gòu)成布爾代數(shù)？為什么？解：(1)，是偏序集。 其哈斯圖為：(2)，構(gòu)成格。因為其任意兩個元素都有上確界和下確界。(3)，構(gòu)成布爾代數(shù)。因為它是有界分配格，且其任意元素都有唯一補(bǔ)元素。四證明題共10分4分設(shè)是獨(dú)異點(diǎn)，為其幺元，且對，有，證明是一個交換群

11、。證明： 對，由于，則 ， 即中的每一個元素都有逆元素,故是一個群。又對，有，所以是一個Abel群。6分設(shè)是一個群，有試證明是一個自同構(gòu)證：首先證明是入射。3分其次證明是滿射。對 綜合以上兩點(diǎn)，知是雙射。3分離散數(shù)學(xué)第七章檢測題答案單項選擇題每題2分，共20分12345678910得分2424324213二、 填空題每空3分，共45分1 4 ， 3 。 2 _0_， _1_。 _0_， _0_。3( 4 2 E ， 偶數(shù) 。5_5_； _9_。6 3 ， 1 。77 。 簡答題每題5分，共25分1對有向圖求解以下問題： 1寫出鄰接矩陣； 2中長度為3的不同的路有幾條？其中不同的回路有幾條？ 解

12、：1鄰接矩陣為：，2則，中長度為3的不同的路有10條，其中有1條不同的回路。2設(shè)有盞燈，擬公用一個電源，求至少需要插頭的接線板的數(shù)目。解：設(shè)至少需要4插頭的接線板i個，則有 4-1i=28-1 3分故 i=9即至少需要9個4插頭的接線板。 2分3設(shè)有6個城市V1，V2，V6，它們之間有輸油管連通，其布置如以下圖,Si(數(shù)字)中Si為邊的編號，括號內(nèi)數(shù)字為邊的權(quán)，它是兩城市間的距離，為了保衛(wèi)油管不受破壞，在每段油管間派一連士兵看守，為保證每個城市石油的正常供給最少需多少連士兵看守輸油管道總長度越短，士兵越好防守。求他們看守的最短管道的長度。(要求寫出求解過程)解：為保證每個城市石油的正常供給最少

13、需5連士兵看守.求看守的最短管道相當(dāng)于求圖的最小生成樹問題，此圖的最小生成樹為：因此看守的最短管道的長度為：12224以給定權(quán)1, 4, 9, 16, 25, 36, 49, 64, 81, 100構(gòu)造一棵最優(yōu)二叉樹。5一次學(xué)術(shù)會議的理事會共有20個人參加，他們之間有的相互認(rèn)識，但有的相互不認(rèn)識。但對任意兩個人，他們各自認(rèn)識的人的數(shù)目之和不小于20，說明能否把這20個人排在圓桌旁，使得任意一個人認(rèn)識其旁邊的兩個人？根據(jù)是什么？解：可以把這20個人排在圓桌旁，使得任意一個人認(rèn)識其旁邊的兩個人。1分根據(jù)是：分別用20個結(jié)點(diǎn)代表這20個人，將相互認(rèn)識的人之間連一條線，便得到一個無向簡單圖，每個結(jié)點(diǎn)的度數(shù)是與認(rèn)識的人的數(shù)目，由題意知，有，于是中存在