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