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

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