南京航空航天大学2017离散数学试卷及答案

第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