南京航空航天大学2007《离散数学》试卷(及答案)

南京航空航天大学第1页（共10页）二○○七～二○○八学年第一学期《离散数学》考试试题考试日期：2008年6月日试卷类型：A卷试卷代号：班号学号姓名题号一二三四五六七八九十总分得分一、填空：（每空2分，共36分）(1)设kN表示不超过k的正整数集,在全集为10N时,3N的补集为3N,)(284NNN的补集为.(2)设为A为n元集,则集合)(APA的计数为|)(|APA.(3)两集合)2,0(与]2008,1((填”是“或”不是”)等势,自然数集N与实数集R(填”是”或”不是”)等势.(4)设集合}4,3,2,1{A,)}3,2(),1,1(),3,3(),2,1{(R为A上的一个关系,则R的关系矩阵是RM,R的逆关系为1R,2R,R的自反闭包是,对称闭包是.(5)在同构的意义下,4元布尔格的哈斯图是.(6)若)(aG为以a为生成元的8阶循环群,则除了a之外,还有个生成元,它们分别是.(7)设P：它占据空间，Q：它没有质量，R：它不断运动，S：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质”的符号化为。(8)一个图是欧拉图的充要条件是,一个图是偶图的充要条件是,树(填“是”或“不是”或“不一定是”)欧拉图,(填“是”或“不是”或“不一定是”)偶图.本题分数36得分第2页（共10页）二.设R是集合A上的一个关系,(1)若R是对称关系,则对任意整数k,kR也是对称关系,举例说明两个对称关系的复合未必是对称关系;(2)若R是等价关系,则对任意非零整数k,有RRk.本题分数10得分第3页（共10页）三.设集合}1,0|{22ijijaaM,定义M上的二元关系2,1,,:jibaBAijij,(1)证明:是M上的一个部分序关系;(2)画出部分序集),(M对应的哈斯图,并指出其中的最大元和最小元;(3)证明部分序集),(M是一个布尔格,并指出其中的所有原子;(4)设}0)det(,1,0|{2222)0(ijijijaaaM,问),()0(M是否为),(M的子格,为什么?本题分数16得分第4页（共10页）四.设]}1[,],1[],0{[nzn是整数模n剩余类集合,另一集合为}1),gcd(,][|]{[)0(nkZkkznn,在nz和)0(nz上定义运算“*”如下:对nz和)0(nz中任意元素][],[ji,有:][][][ijji,(1)证明),(nz是半群,但不是群;(2)证明),()0(nz是群(3)求),()0(nz中元素]1[n的阶数.本题分数12得分第5页（共10页）五.若N为群G的子群,则有:N为G的正规子群,当且仅当对任意NnGa,,Nana1.六、(1)用等值演算法证明下式为永真式)()(RQPRQP本题分数10得分本题分数8得分第6页（共10页）(2)构造下列推理的证明：若n是偶数,并且n大于5,则m是奇数.只有n是偶数,m才大于6.n是大于5.所以,若m大于6,则m是奇数.七.设F是k个连通分支的m条边的n阶森林,则有:knm.参考答案一、填空（每空2分，共36分）1、}10,,6,5,4{；}6,2,1{2、nn23、是；不是4、0000010001000011；)}2,3(),3,3(),1,1(),1,2{(；)}3,3(),3,2(),3,1(),2,1(),1,1{(；本题分数6得分第7页（共10页）AI)}3,2(),2,1{(；)}2,3(),3,2(),1,1(),3,3(),2,1(),1,2{(5、4C6、3；753,,aaa7、SRQP)(8、此图没有奇点；此图没有奇圈；不是；是二、(1)、当R对称时,显然1R也对称,只须证明Nk的情形即可-------1分AIR0当然是对称的,1k时,R是对称的,假设kR是对称的,下证1kR也是对称的,RRRyxkk1),(,即存在At,使RytRtxk),(,),(,从而,RtyRxtk),(,),(,所以,1),(kkRRRxy,即1kR是对称的由归纳原理,结论成立-------------6分(2)k为正整数时,因为R是自反的,所以,RIA,即2RR,因为R是传递的,所以RR2,从而,2RR,可得kRR；k为负整数时,因为R是对称的,所以,RR1,即RRRkk)(1,即结论成立.-------------10分三、（1）对M中任意矩阵CBA,,,有:AA；若,BA,AB，则有BA；若CBA，则有CA；所以，是M上的一个部分序关系--------3分（2）,00000M,00011M,00102M,01003M,10004M,00115M,01106M,01017M,11008M,10109M,100110M,011111M,111012M,110113M,101114M,111115M哈斯图如下，最大元为15M，最小元为0M--------------------------6分第8页（共10页）（3）对M中任意矩阵BA,，1511121314567891012340定义22)),(max(ijijbaBA，22)),(min(ijijbaBA对任意},1,0{,,cba有}},max{},,min{max{}},min{,max{cabacba-----------8分，对M中任意矩阵CBA,,,有:)()(CABACBA--------------9分对M中任意矩阵,A令22)1(ijaA，有,15MAA,0MAA所以，A是,A的补元，即),(M是布尔格，--------------11分其中所有的原子为4321,,,MMMM.--------------13分（4）对)0(M中矩阵106,MM,有:,15106MMM,0106MMM而106,MM都不在)0(M中,所以,),()0(M不是子格.--------------16分四、(1)因为)0(][][][nZijji,),(nz是代数系统,易验证结合律成立,且]1[是单位元,故),(nz是单元半群------------2分元素]0[没有逆元,所以),(nz不是群------------3分(2)因为)0(][nZa,)0(][nZb,所以,),gcd(1),gcd(nbna,从而,有:第9页（共10页）1),gcd(nab,即)0(][nZab,),()0(nz是代数系统,易验证结合律成立,且]1[是单位元,故),()0(nz是单元半群------------6分对任意)0(][nZa,由1),gcd(na,得1qnap,------------8分)(mod1nap,即]1[][][pa,所以,][][1pa,即),()0(nz是群---10分(3)因为]1[]1[n,而]1[]12[]1[22nnn,所以,2]1[n------------12分五、若N为G的正规子群,则有:对任意Ga,NaaN,所以,有:NaNaaNa11)(,从而,对任意NnGa,,Nana1.------------3分若对任意NnGa,,Nana1,则对aNan1,其中Nn1,令112aann,此时,有:Naann112,且12anan,所以,Naan1,即NaaN,同理可证aNNa,所以,aNNa,即N为G的正规子群.------------8分六、(1))()(RQPRQP))()(())()((RQPRQPRQPRQP))()(())(()))((RQPRQPRQPRQP))()(())()((RQPRQPRQPRQP)())((RQPRRQPQPtRQPqRQPP)()(ttt------------------5分(2)设P:n是偶数,Q:n大于5,R:m是奇数,S:m大于6.前提:RQP)(,PS,Q,结论:RS------------------7分①S引入附加前提⑤QP4,3T②PSP⑥RQP)(P③P2,1T⑦R6,5T④QP⑧RS7,1CP-----------------12分第10页（共10页）七、设k个连通分支(树)分别是kTTT,,21,其阶数分别是knnn,,21,边数分别是kmmm,,21,则有1iinm,------------------2分从而,有:knnmmkikiii)1(11------------------6分