天津理工大學(xué)離散數(shù)學(xué)(魏雪麗版)檢測(cè)題答案.doc

天津理工大學(xué)《離散數(shù)學(xué)》第一章檢測(cè)題答案 一、填空題（每空2分，共30分） 1． 2． 3．→，，∧，， ，， ， 。 4．， 5． 6． 7． 二、單項(xiàng)選擇題（每小題2分，共20分） 1 2 3 4 5 6 7 8 9 10 得分 D B C B C D A A C B 三、簡(jiǎn)答題（每小題6分，共12分） 1．構(gòu)造命題公式的真值表． 0 0 0 1 1 0 0 1 1 1 0 1 0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 1 2．求命題公式的主析取范式和主合取范式。 3．判斷命題公式與 是否等價(jià)。 解： 等價(jià) 四．證明題（共32分） １．（10分）用CP規(guī)則證明； 1. P 6. T(4,5) I （2分） 2. P 7. T(3,4) I（2分） 3. T(1, 2) I （2分） 8. T(6,7) I（2分） 4. P(附加前提) 9. CP （2分） 5. P ２．（10分）用歸謬法證明 ． 證: 1 （1分） 2 3 （2分） 4 5 （2分） 6 7 （2分） 8 （2分） 由8得出了矛盾，根據(jù)歸謬法說(shuō)明原推理正確（1分） 3．（12分）公安人員審理某珠寶商店的鉆石項(xiàng)鏈的失竊案，已知偵察結(jié)果如下： （1）營(yíng)業(yè)員或盜竊了鉆石項(xiàng)鏈 （2）若作案，則作案時(shí)間不在營(yíng)業(yè)時(shí)間 （3）若提供的證詞正確，則貨柜未上鎖 （4）若提供的證詞不正確，則作案發(fā)生在營(yíng)業(yè)時(shí)間 （5）貨柜上了鎖 試問(wèn)：作案者是誰(shuí)？要求寫出推理過(guò)程。 解：令表示“營(yíng)業(yè)員盜竊了鉆石項(xiàng)鏈”； 表示“營(yíng)業(yè)員盜竊了鉆石項(xiàng)鏈”； 表示“作案時(shí)間在營(yíng)業(yè)時(shí)間”；表示“提供的證詞正確”；表示“貨柜上了鎖”。 則偵察結(jié)果如下： ， ，，，．由此可推出作案者是．（4分） 推理過(guò)程如下： (1) (6) (2) (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． 或 2． 3． 4． 5． 6．（；） 7． 8． 二、單項(xiàng)選擇題（每小題2分，共20分） 1 2 3 4 5 6 7 8 9 10 得分 A A B D C A C C B D 三、 簡(jiǎn)答題（每小題6分，共12分） 1．求謂詞公式的前束析取范式． 2．證明： 證： 四．證明題（共38分） 1．（12分）用謂詞演算的推理規(guī)則證明: ，， （1） （2） （2分） （3） （4） I （2分） （5） （6） （2分） （7） I （2分） （8） I （2分） （9） I （2分） 2．(10分) 指出下面推理證明過(guò)程中的錯(cuò)誤，并給出正確的證明． 用謂詞演算的推理規(guī)則證明： 證:：(1) P (6) T(4) I (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 3．（16分）符號(hào)化下列命題并推證其結(jié)論． 任何人如果他喜歡音樂(lè),他就不喜歡體育．每個(gè)人或者喜歡體育，或者喜歡美術(shù)．有的人不喜歡美術(shù)．因而有的人不喜歡音樂(lè)．（設(shè)M(x)：x喜歡音樂(lè)，S(x)：x喜歡體育，Ａ(x)：ｘ喜歡美術(shù)．） 該推理符號(hào)化為： 或 前提： 結(jié)論： （4分）證： （1） P （2） ES（1） （2分） （3） P （4） US（3） （2分）（5） T（2）（4）I（2分） （6） P （7） US（6）（2分） （8） T（7）E （1分） （9） T（5）（8）I（2分） （10） EG（9） （1分） 天津理工大學(xué)《離散數(shù)學(xué)》第三、四章檢測(cè)題答案 一、填空題（每空2分，共40分） 1． ２． 3． 4．反對(duì)稱，傳遞。 5．； 6． ，或單位矩陣 7． 4,6 ， 2,3 ， 無(wú) ， 無(wú) ， 12 ， 1 。 8． , 。 9．單射，滿射；既是單射又是滿射； ； 二、單項(xiàng)選擇題（每小題2分，共20分） 1 2 3 4 5 6 7 8 9 10 得分 (1) (2) (1) (3) （2） （2） (1) (3) (3) (1) 三、簡(jiǎn)答題（共30分） 1．（6分）設(shè)={1,2,3,5,6,10,15,30} ， “／” 為集合上的整除關(guān)系?！矗凳欠駷槠蚣? 若是，畫出其哈斯圖； 解：〈，／〉是偏序集。其哈斯圖為： 2．（12分）對(duì)下圖所給的偏序集，求下表所列集合的上（下）界，上（下）確界，并將結(jié)果填入表中。 子 集 上 界 下 界 上 確 界 下 確 界 無(wú) 無(wú) 無(wú) 無(wú) 3．（6分）設(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的劃分為：， 其中： 四．證明題（共10分） １．設(shè) 定義為 ，證明：是雙射，并求出其逆映射。 證：1）先證明是入射（2分） 對(duì)任意的則有，從而有，故是入射。 2) 再證明是滿射（2分） 對(duì)任意的從而是滿射。 綜合（1）、（2）知是雙射。 為 ，對(duì)任意。（1分） 天津理工大學(xué)《離散數(shù)學(xué)》第五章檢測(cè)題答案 一、填空題（每空2分，共30分） 1. 2． 3． 4．；1 5．關(guān)于運(yùn)算不封閉 6． 2， 7循環(huán)群，生成元 8． 9．關(guān)于封閉 二、單項(xiàng)選擇題（每小題2分，共20分） 1 2 3 4 5 6 7 8 9 10 得分 B C A A B D D C B D 三、簡(jiǎn)答題（共30分） 1．設(shè)是實(shí)數(shù)集上的二元運(yùn)算，其定義如下： （1）求23， 3(-5)和71/2 。 （2）是半群?jiǎn)幔靠山粨Q嗎？ （3）求中關(guān)于的單位元。 （4）中哪些元素有逆元素，其逆元素是什么？ 答案：（1）17，-32，14.5 。 2）是半群，可交換。 （3）0。 （4）當(dāng)時(shí)，有逆元素，。 2．設(shè)，是交換群，是的單位元。的運(yùn)算表如下： 求，并說(shuō)明道理。 答案：。因?yàn)橛邢奕旱倪\(yùn)算表中的每行、每列都是群中元素的一個(gè)置換。 3．設(shè)集合，是定義在上的模11乘法（即任意a,b∈G，有a*b=(a×b)(mod11)，×是普通乘法），問(wèn)是循環(huán)群?jiǎn)幔咳羰?，試找出它的生成元? 答： 的運(yùn)算表如下表所示。 1 3 4 5 9 1 3 4 5 9 1 3 4 5 9 3 9 1 4 5 4 1 5 9 3 5 4 9 3 1 9 5 3 1 4 從運(yùn)算表可知，在上封閉、有幺元1，且，再由是可結(jié)合的得是循環(huán)群，3，4，5和9均為其生成元。 四．證明題（共20分） １．（4分）設(shè)是獨(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ǔ)元素，不一定 3．0，1；1，0 4． 5．； 6． ， 二、單項(xiàng)選擇題（每小題2分，共20分） 1 2 3 4 5 6 7 8 9 10 得分 D C B C A D A B D D 三、簡(jiǎn)答題（共30分） 1．下面哈斯圖表示的格中哪個(gè)元素?zé)o補(bǔ)元？對(duì)有補(bǔ)元的元素求出它們的補(bǔ)元． 解：c無(wú)補(bǔ)元（1分），a的補(bǔ)元為e（1分），b的補(bǔ)元為d（1分），d的補(bǔ)元為b、e（1分），e的補(bǔ)元為a、d（1分），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)．〈，／〉是否為偏序集? 若是，畫出其哈斯圖； (2)．〈，／〉是否構(gòu)成格？為什么？ (3)．〈，／〉是否構(gòu)成布爾代數(shù)？為什么？ 解：(1)．〈，／〉是偏序集。 其哈斯圖為： (2)．〈，／〉構(gòu)成格。因?yàn)槠淙我鈨蓚€(gè)元素都有上確界和下確界。 (3)．〈，／〉構(gòu)成布爾代數(shù)。因?yàn)樗怯薪绶峙涓?，且其任? 元素都有唯一補(bǔ)元素。 四．證明題（共10分） １．（4分）設(shè)是獨(dú)異點(diǎn)，為其幺元，且對(duì)，有，證明 是一個(gè)交換群。 證明： 對(duì)，由于，則 ， 即中的每一個(gè)元素都有逆元素,故是一個(gè)群。 又對(duì)，有 ， 所以是一個(gè)Abel群。 ２．（6分）設(shè)是一個(gè)群，，，，有 試證明是一個(gè)自同構(gòu)． 證：首先證明是入射。（3分） 其次證明是滿射。 對(duì) 綜合以上兩點(diǎn)，知是雙射。（3分） 離散數(shù)學(xué)第七章檢測(cè)題答案 一、 單項(xiàng)選擇題（每小題2分，共20分） 1 2 3 4 5 6 7 8 9 10 得分 2 4 2 4 3 2 4 2 1 3 二、 填空題（每空3分，共45分） 1． 4 ， 3 。 2． __0___， _1__。 __0___， __0___。 3．( 4． 2 │E│ ， 偶數(shù) 。5．___5__； __9___。 6． 3 ， 1 　。7． 7 。 三、 簡(jiǎn)答題（每小題5分，共25分） 1．對(duì)有向圖求解下列問(wèn)題： （1）寫出鄰接矩陣； （2）中長(zhǎng)度為3的不同的路有幾條？其中不同的回路有幾條？ 解：（1）鄰接矩陣為： ， （2） 則，中長(zhǎng)度為3的不同的路有10條，其中有1條不同的回路。 2．設(shè)有２８盞燈，擬公用一個(gè)電源，求至少需要４插頭的接線板的數(shù)目。 解：設(shè)至少需要4插頭的接線板i個(gè)，則有 （4-1）i=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è)城市石油的正常供應(yīng)最少需多少連士兵看守?輸油管道總長(zhǎng)度越短，士兵越好防守。求他們看守的最短管道的長(zhǎng)度。(要求寫出求解過(guò)程) 解：為保證每個(gè)城市石油的正常供應(yīng)最少需 5連士兵看守.求看守的最短管道相當(dāng)于求圖 的最小生成樹問(wèn)題，此圖的最小生成樹為： 　　　　　　　　 因此看守的最短管道的長(zhǎng)度為： ?。祝ǎ裕剑保?＋2＋2＋2＝８． 4．以給定權(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，說(shuō)明能否把這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è) 無(wú)向簡(jiǎn)單圖，每個(gè)結(jié)點(diǎn)的度數(shù)是與認(rèn)識(shí)的人的數(shù)目，由題意知，有，于是中存在哈密爾頓回路，設(shè)是中的一條哈密爾頓回路，按此回路安排園桌座位即符合要求。（4分） 四．證明與應(yīng)用題（10分） 1． 某次聚會(huì)的成員到會(huì)后相互握手，試用圖論的知識(shí)說(shuō)明與奇數(shù)個(gè)人握手的人數(shù)一定是一個(gè)偶數(shù)。 證: 用結(jié)點(diǎn)代表成員, 握手的成員之間連一條線, 則所有聚會(huì)的成員之間的握手情況可以用一個(gè)圖來(lái)表示，其中每個(gè)結(jié)點(diǎn)的度數(shù)就是該結(jié)點(diǎn)所代表的成員握手的人數(shù),由于任一圖中奇數(shù)度結(jié)點(diǎn)的個(gè)數(shù)為偶數(shù),所以與奇數(shù)個(gè)人握手的人數(shù)一定是一個(gè)偶數(shù)。 - 15 -