《北京科技大学2006--2007学年离散数学-第1学期A卷试题》由会员分享，可在线阅读，更多相关《北京科技大学2006--2007学年离散数学-第1学期A卷试题（6页珍藏版）》请在金锄头文库上搜索。
1、北京科技大学2006 2007 学年度第 1 学期 离散数学 试题（A卷）（时间120分钟） 学院 班级 学号 姓名 题号一二三四五六七八卷面实际评 分卷面分占总分 %平时成绩占总分 %成绩总分得分一、 判断正误（共36分，答错不扣分）1. 命题具有确定的真假值。2. pq和pq命题等价。3. 量词的约束顺序对公式真假值无影响。4. $x(x)与$x(x)等价。5. 自然数集是无限集中最小的集合。6. 有理数集是可数集。7. 任何质数阶群不可能有非平凡群。8. 质数阶群必是循环群。9. 若r(R)=R，则R一定是自反的。10. 若f为函数，则(f-1)-1=f。11. 若f，q为函数，则(f
2、g)-1=f-1 g-1。12. 若f，g为入射，则f g也是入射。13. 有限半群必有幂等元。14. 群中有幺元，零元。15. 无向连通图的所有结点度数之和等于边数的2倍。16. 有向图中结点入度之和等于出度之和。17. 若无向图中有两对结点的度数为奇数，则存在欧拉路。18. 无向图中有哈密尔顿路的必要条件是任意两对结点度数之和 大于n-1。19. 任意一棵树至少有两片树叶。20. 树是无环连通图。21. 设是一个代数系统，若、都是满足交换律，结合 律和吸收率，则A上存在偏序关系 ，使是一个格。22. 若为格，则有诱导的代数系统满足幂等律。23. 任何一个循环群必定是阿贝尔群。24. 集合的
3、、运算满足结合律，吸收率。二、 填空（每题2分，共20分）1. n元集合上共有_个关系，_个自反关系。acbdefighjklm2. 左图中，极大元素是_，极小元素为 _，a,b,c的最小上界_，f,g,h的所有下界_。3. 任意一个正整数n，必存在含有_个元素的布尔代数。4. 在平面图中，若v=6，e=10，则r= _。5. 树中边数和结点的关系是_。6. 设为群，对任意的a,b,cG,若有a*b=a*c，则有_。三、 证明（12分）(1) 前提 x(P(x)A(x)B(x)x(A(x) Q(x)x(P(x) Q(x)结论 $x(P(x)B(x)(2) (P(PQ) PQ四、 设x=1,2,10，定义x上一个关系R，a,bx，R当且仅当a-b被3整除。（8分）(1) 证明R为等价关系.(2) 求由R确定的等价类。五、 设是一个格，那么对于任意的a，bA，有ab ab=b。（8分）六、 设G是一个有v个结点，e条边的连通简单平面图，若v3，则e3v-6。（6分）七、 设P1，P2 均为某集合的划分，如果在划分P1中的每个集合都是划分P2中每个集合的子集，则P1叫做P2的加细。证明：整数集上由模6同余类构成的划分是模3同余类构成划分的加细。（4分）八、 设f，g都是群到群的同态，证明是的一个子群。其中C=x|xG1，且f(x)=g(x)。（6分）
