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

1、-. z.*理工大學(xué)離散數(shù)學(xué)第一章檢測(cè)題答案一、填空題每空2分，共30分12 3， ， ， 。4，567二、單項(xiàng)選擇題每題2分，共20分 12345678910得分DBCBCDAACB三、簡(jiǎn)答題每題6分，共12分1構(gòu)造命題公式的真值表 00011001110100001111100111011111001111112求命題公式的主析取*式和主合取*式。3判斷命題公式與 是否等價(jià)。解：等價(jià)四證明題共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分公安人員審理*珠寶商店的鉆石項(xiàng)鏈的失竊案，偵察結(jié)果如下：1營(yíng)業(yè)員或盜竊了鉆石項(xiàng)鏈2假設(shè)作案，則作案時(shí)間不在營(yíng)業(yè)時(shí)間3假設(shè)提供的證詞正確，則貨柜未上鎖4假設(shè)提供的證詞不正確，則作案發(fā)生在營(yíng)業(yè)時(shí)間5貨柜上了鎖試問：作案者是誰？要求寫出推理過程。解：令表示“營(yíng)業(yè)員盜竊了鉆石項(xiàng)鏈； 表示“營(yíng)業(yè)員盜竊了鉆石項(xiàng)鏈；表示“作案時(shí)間在營(yíng)業(yè)時(shí)間；表示“提供的證詞正確；表示“貨柜上了鎖。則偵察結(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é)第二章檢測(cè)題答案一、填空題每空3分，共30分1或23456； 78二、單項(xiàng)選擇題每題2分，共20分 12345678910得分AABDCACCBD簡(jiǎn)答題每題6分，共12分1求謂詞公式的前束析取*式2證明：證：四證明題共38分 112分用謂詞演算的推理規(guī)則證明:，12 2分34I 2分56 2分7 I 2分8I 2分9I 2分2(10分) 指出下面推理證明過程中的錯(cuò)誤，并給出正確的證明用謂詞演算的推理規(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該證明的錯(cuò)誤在于: (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分符號(hào)化以下命題并推證其結(jié)論任何人如果他喜歡音樂,他就不喜歡體育每個(gè)人或者喜歡體育，或者喜歡美術(shù)有的

5、人不喜歡美術(shù)因而有的人不喜歡音樂設(shè)M(*)：*喜歡音樂，S(*)：*喜歡體育，(*)：喜歡美術(shù)該推理符號(hào)化為： 或前提：結(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é)第三、四章檢測(cè)題答案一、填空題每空2分，共40分1 34反對(duì)稱，傳遞。 5；6，或單位矩陣7 4,6 ， 2,3 ， 無 ， 無 ， 12 ， 1 。8 , 。9單射，滿射；既是單射又是滿射； ； 二、單項(xiàng)選擇題每題2分，共20分 12345678910得分(1)(2)(1)(3)22(1)(3)(3)(1)三、簡(jiǎn)

6、答題共30分16分設(shè)=1,2,3,5,6,10,15,30 ， “ 為集合上的整除關(guān)系。，是否為偏序集 假設(shè)是，畫出其哈斯圖；解：，是偏序集。其哈斯圖為：212分對(duì)以下圖所給的偏序集，求下表所列集合的上下界，上下確界，并將結(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ù)等價(jià)關(guān)系決定Z的一個(gè)劃分 。答案：由決定的Z的劃分為：，

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

8、？答案：117，-32，14.5。 2是半群，可交換。 30。 4當(dāng)時(shí)，有逆元素，。2設(shè)，是交換群，是的單位元。的運(yùn)算表如下：求，并說明道理。答案：。因?yàn)橛邢奕旱倪\(yùn)算表中的每行、每列都是群中元素的一個(gè)置換。3設(shè)集合，是定義在上的模11乘法即任意a,bG，有a*b=(ab)(mod11)，是普通乘法，問是循環(huán)群?jiǎn)幔考僭O(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)，為其幺元，且對(duì)，有，證明是一個(gè)交換群。證明： 對(duì)，由于，則 ， 即中的每一個(gè)元素都有逆元素,故是一個(gè)群。又對(duì)，有，所以是一個(gè)Abel群。6分設(shè)是一個(gè)群，有試證明是一個(gè)自同構(gòu)證：首先證明是入射。3分其次證明是滿射。對(duì) 綜合以上兩點(diǎn)，知是雙射。3分*理工大學(xué)離散數(shù)學(xué)第六章檢測(cè)題答案一、填空題每空2分，共40分1. 上確界 和下確界， 2至少有一個(gè)補(bǔ)元素，不一定30，1；1，0 45； 6 ，二、單項(xiàng)選擇題每題2分，共20分12345678910得分D CB CADABDD三、簡(jiǎn)答題共30分1下面哈斯圖表示的格中哪個(gè)元素?zé)o補(bǔ)元？對(duì)有補(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è)是一個(gè)布爾代數(shù)且，求布爾表達(dá)式的析取*式和合取*式并計(jì)算的值。解：的析取*式為： 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)成格。因?yàn)槠淙我鈨蓚€(gè)元素都有上確界和下確界。(3)，構(gòu)成布爾代數(shù)。因?yàn)樗怯薪绶峙涓瘢移淙我庠囟加形ㄒ谎a(bǔ)元素。四證明題共10分4分設(shè)是獨(dú)異點(diǎn)，為其幺元，且對(duì)，有，證明是一個(gè)交換群

11、。證明： 對(duì)，由于，則 ， 即中的每一個(gè)元素都有逆元素,故是一個(gè)群。又對(duì)，有，所以是一個(gè)Abel群。6分設(shè)是一個(gè)群，有試證明是一個(gè)自同構(gòu)證：首先證明是入射。3分其次證明是滿射。對(duì) 綜合以上兩點(diǎn)，知是雙射。3分離散數(shù)學(xué)第七章檢測(cè)題答案單項(xiàng)選擇題每題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 。 簡(jiǎn)答題每題5分，共25分1對(duì)有向圖求解以下問題： 1寫出鄰接矩陣； 2中長(zhǎng)度為3的不同的路有幾條？其中不同的回路有幾條？ 解

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

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