南京航空航天大學(xué)2017離散數(shù)學(xué)試卷及答案

第5頁（共10頁）南京航空航天大學(xué)第1頁（共12頁）二○一七～二○一八學(xué)年第一學(xué)期《離散數(shù)學(xué)》考試試題考試日期：2018年6月日試卷類型：A卷試卷代號(hào)：班號(hào)學(xué)號(hào)姓名題號(hào)一二三四五六七八九十總分得分本題分?jǐn)?shù)36本題分?jǐn)?shù)36得分一、填空：（每空2分，共36分）(1)設(shè)表示不超過k的正整數(shù)集,在全集為時(shí),的補(bǔ)集為,的補(bǔ)集為.(2)設(shè)為A為n元集,則集合的計(jì)數(shù)為.(3)兩集合與(填”是“或”不是”)等勢,自然數(shù)集N與實(shí)數(shù)集R(填”是”或”不是”)等勢.(4)設(shè)集合,為A上的一個(gè)關(guān)系,則R的關(guān)系矩陣是,的逆關(guān)系為,,的自反閉包是,對(duì)稱閉包是.(5)在同構(gòu)的意義下,4元布爾格的哈斯圖是.(6)若為以為生成元的8階循環(huán)群,則除了之外,還有個(gè)生成元,它們分別是.(7)設(shè)P：它占據(jù)空間，Q：它沒有質(zhì)量，R：它不斷運(yùn)動(dòng)，S：它叫做物質(zhì)。命題“占據(jù)空間的，有質(zhì)量的而且不斷運(yùn)動(dòng)的叫做物質(zhì)”的符號(hào)化為。(8)一個(gè)圖是歐拉圖的充要條件是,一個(gè)圖是偶圖的充要條件是,樹(填“是”或“不是”或“不一定是”)歐拉圖,(填“是”或“不是”或“不一定是”)偶圖.本題分?jǐn)?shù)10本題分?jǐn)?shù)10得分(1)若R是對(duì)稱關(guān)系,則對(duì)任意整數(shù)k,也是對(duì)稱關(guān)系,舉例說明兩個(gè)對(duì)稱關(guān)系的復(fù)合未必是對(duì)稱關(guān)系;(2)若R是等價(jià)關(guān)系,則對(duì)任意非零整數(shù)k,有.本題分?jǐn)?shù)本題分?jǐn)?shù)16得分三.設(shè)集合,定義M上的二元關(guān)系,證明:是M上的一個(gè)部分序關(guān)系;畫出部分序集對(duì)應(yīng)的哈斯圖,并指出其中的最大元和最小元;證明部分序集是一個(gè)布爾格,并指出其中的所有原子;設(shè),問是否為的子格,為什么?本題分?jǐn)?shù)本題分?jǐn)?shù)12得分四.設(shè)是整數(shù)模n剩余類集合,另一集合為,在和上定義運(yùn)算“*”如下:對(duì)和中任意元素,有:,(1)證明是半群,但不是群;(2)證明是群(3)求中元素的階數(shù).本題分?jǐn)?shù)本題分?jǐn)?shù)8得分五.若N為群G的子群,則有:N為G的正規(guī)子群,當(dāng)且僅當(dāng)對(duì)任意,.本題分?jǐn)?shù)10得分六、(1)用等值演算法證明下式為永真式(2)構(gòu)造下列推理的證明：若n是偶數(shù),并且n大于5,則m是奇數(shù).只有n是偶數(shù),m才大于6.n是大于5.所以,若m大于6,則m是奇數(shù).本題分?jǐn)?shù)6得分七.設(shè)F是k個(gè)連通分支的m條邊的n階森林,則有:.參考答案一、填空（每空2分，共36分）1、；2、3、是；不是4、；；；；5、6、3；7、8、此圖沒有奇點(diǎn)；此圖沒有奇圈；不是；是二、(1)、當(dāng)對(duì)稱時(shí),顯然也對(duì)稱,只須證明的情形即可1分當(dāng)然是對(duì)稱的,時(shí),是對(duì)稱的,假設(shè)是對(duì)稱的,下證也是對(duì)稱的,,即存在,使,從而,,所以,,即是對(duì)稱的由歸納原理,結(jié)論成立6分(2)為正整數(shù)時(shí),因?yàn)槭亲苑吹?所以,,即,因?yàn)槭莻鬟f的,所以,從而,,可得；為負(fù)整數(shù)時(shí),因?yàn)槭菍?duì)稱的,所以,,即,即結(jié)論成立.10分三、（1）對(duì)中任意矩陣,有:；若，則有；若，則有；所以，是上的一個(gè)部分序關(guān)系3分（2）哈斯圖如下，最大元為，最小元為6分（3）對(duì)中任意矩陣，定義，對(duì)任意有8分，對(duì)中任意矩陣,有:9分對(duì)中任意矩陣令，有所以，是的補(bǔ)元，即是布爾格，11分其中所有的原子為.13分（4）對(duì)中矩陣,有:而都不在中,所以,不是子格.16分四、(1)因?yàn)?是代數(shù)系統(tǒng),易驗(yàn)證結(jié)合律成立,且是單位元,故是單元半群2分元素沒有逆元,所以不是群3分(2)因?yàn)?,所以,,從而,有:,即,是代數(shù)系統(tǒng),易驗(yàn)證結(jié)合律成立,且是單位元,故是單元半群6分對(duì)任意,由,得,8分,即,所以,,即是群10分(3)因?yàn)?而,所以,12分五、若N為G的正規(guī)子群,則有:對(duì)任意,,所以,有:,從而,對(duì)任意,.3分若對(duì)任意,,則對(duì),其中,令,此時(shí),有:,且,所以,,即,同理可證,所以,,即N為G的正規(guī)子群.8分六、(1)5分(2)設(shè)P:n是偶數(shù),Q:n大于5,R:m是奇數(shù),S:m大于6.前提:,,,結(jié)論:7分①S引入附加前提⑤②P