离散数学试题

中南大学考试试卷2007--2008学年2学期期末考试试题时间110分钟离散数学课程64学时4学分考试形式：闭卷专业年级：信息科学0601-0604总分100分，占总评成绩70%注：此页不作答题纸，请将答案写在答题纸上.一、判断题(本大题共10小题，每小题1分，共10分)1、对每个集合A，都有{A}ρ(A)（）2、设（N，*）是代数系统，其中N为自然数集，*为二元运算，定义为：对任何的自然数a,b，有a*b=a，则*是可结合的（）3、(P(Q∧R))是一个命题演算的命题公式，其中P、Q、R是命题变元。（）4、ρ(A)ρ(B)=A是B的子集（）5、若R和S是反自反的，则R。S也是反自反的（）6、x(A(x)∧B(x))xA(x)∧xB(x)（）7、设R和S是集合A上的等价关系，则RS一定是等价的。（）8、若A-B，则（）9、(S,*)是独异点，a,bS，且a,b均有逆元，则(a*b)-1=a-1*b-1（）10、若R是集合A上的传递关系，则R2也是集合A上的传递关系。（）二、单项选择题(本大题共15小题，每小题2分，共30分)1、对自然数集N，下列哪种运算是可结合的？（）A、a*b=a-bB、a*b=max{a,b}C、a*b=a+2bD、a*b=ab2、设A-B=则有，（）A、B=B、BC、AD、B3、幂集P(P(P()))（）A、,{}B、{,{,{}},{}}C、{,{,{}},{{}},{}}D、,{,{}}4、设集合A={a,b,c}，R是A上的二元关系，R={a,a,a,b,a,c,c,a},那么R是（）A、反自反的B、反对称的C、可传递的D、不可传递的5、设A={a,{a}},下列选项错误的是（）A、{a}P(A)B、{a}P(A)C、{{a}}P(A)D、{{a}}P(A)6、Z是整数集合，函数f定义为：ZZ，f(x)=|x|-2x，则f是（）、单射B、满射C、双射D、非单射也非满射7、设集合A={a,b,c},R是A上的二元关系，R={a,a,a,b,a,c,c,a}，则R是（）A、反自反的B、反对称的C、可传递的D、不可传递的8、设R是集合A上的偏序关系，R-1是R的逆关系，则RR-1是（）A、偏序关系B、等价关系C、非自反关系D、非传递关系9、若f。g是满射，则（）A、f必是满射B、f必是单射C、g必是满射D、g必是单射10、设N是自然数集合，f和g是N到N的函数，且f(n)=2n+1,g(n)=n2，则复合函数f。g(n)=()A、n4B、4n+3C、2n2+1D、(2n+1)211、设集合A中有4个元素，则A上的不同的等价关系得个数为（）A、11个B、14个C、15个D、17个12、R为实数集，运算*定义为：a,bR,a*b=a|b|，则代数系统（R，*）是（）A、半群B、独异点C、群D、阿贝尔群13、设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（）A、PQB、PQC、()PQD、PQ14、群（R，+）与（R-{0}，）之间的关系是（）A、同态B、同构C、后者是前者的子群D、B，C均正确15、谓词公式x(P(x)yR(y))Q(x)中变元x是（）A、自由变量B、约束变量C、既不是自由变量也不是约束变量D、既是自由变量也是约束变量16、函数的复合满足（）A、交换律B、结合律C、幂等律D、分配率三、填空题（每小题3分、共15分)。请把答案填在题中的横线上。1.设A={a，b}，B={0,1,2},则从A到B有种不同的从A到B的单射函数。2.设A={x|100〈x〈200，x=7n+3，nZ，xZ}，则|A|=。3．设A={1，2，3，4}上关系R={〈1，2〉，〈2，4〉，〈3，3〉，〈1，3〉}，则r(R)=,s(R)=。4．命题公式()PQ。的主析取范式为。四、作图及计算题(共16分)1、（8分）设A={1，2，3}，做出A的所有划分；设A的所有划分构成的集合是H，画出（H，细分）的哈斯图。2、（8分）求命题公式F=(())(())PQQQPP的主析取范式和主合取范式。五、证明题（共24分）1、用命题逻辑推理规则证明下列推理的正确性：如果甲地发生了交通事故，则小张的交通会发生困难。如果小张按指定时间到达了，则他的通行没有发生困难。小张按指定时间到达了。所以甲地没有发生交通事故。