离散数学2006-2007B..doc

北京科技大学2006 — 2007 学年度第 1 学期 离散数学 试题（B卷）（时间120分钟） 学院 班级 学号 姓名 题号 一 二 三 四 五 六 七 八 卷面实际评 分 卷面分占总分 % 平时成绩占总分 % 成绩 总分 得分 判断正误（共36分，答错不扣分） 集合的∩、∪运算满足结合律，吸收率。 命题具有确定的真假值。量词的约束顺序对公式真假值无影响。 p?q和?p∨q命题等价。 ?$xθ(x)与$x?θ(x)等价。 任何质数阶群不可能有非平凡群。 质数阶群循环群。 自然数集是无限集中最小的集合。 有理数集是可数集。 若r(R)=R，则R一定是自反的。 有限半群必有幂等元。 群中有幺元，零元。 若f为函数，则(f-1)-1=。 若f，q为函数，则(f ? g)-1=f-1 ? g-1。 若f，g为入射，则f ? g也是入射。 无向连通图的所有结点度数之和等于边数的2倍。 中结点入度之和等于出度之和。 若无向图中有两对结点的度数为奇数，则存在欧拉路。 无向图中有哈密尔顿路的必要条件是任意两对结点度数之和大于n-1。 任何一个循环群必定是阿贝尔群。 设A，是一个代数系统，若∨、∧都是满足交换律，结合律和吸收率， 若A，为格，则有A，诱导的代数系统满足幂等律。 任意一棵树至少有两片树叶。 树是无环连通图。 n元集合上共有_____________个关系，____________个自反关系。 图中，极大元素是____________，极小元素为____________，{a,b,c}的最小上界____________，{f,g,h}的所有下界____________。在平面图中，若=6，e=，则r= ____________。 树中边数和结点的关系是____________。 任意一个正整数n，存在含有____________个元素的布尔代数。 设G，*为群，对任意的a,b,c∈G,若有a*b=a*c，则有____________。 前提 x(P(x)?A(x)∨B(x)) x(A(x) ?Q(x)) ?x(P(x) ?Q(x)) 结论 $x(P(x)∧B(x))?(P∨(?P∧Q))?? ?P∧?Q 设x={1,2,…,10}，定义x上一个关系R，a,b∈x，a，b∈R当且仅当a-b被3整除。（8分） 证明R为等价关系. 求由R确定的等价类。。。B卷 北京科技大学200 — 200 学年度第 学期 试题答案及评分标准 判断正误（共36分，答错不扣分） √ 2. √ 3. 4. √ 5. 6. √ 7. √ 8. √ 9. √ 10. √ 11. √ 12. 13. 14. 15. √ 16. √ 17. √ 18. 19. 20. √ 21. √ 22. √ 23. √ 24. √ 评分：每错一个扣1.5。 填空（每题2分，共20分） 1. 2nn ; 2nn 2. l, m; a, b, c; k; k, l, m 3. 6 4. 6 5. e=v-1 6. b=c 证明（12分） 证明：?x(P(x) ?Q(x)) $x(P(x)∧?Q(x)) ………………………得1分 P(a)∧Q(a) ………………………得1分 x(A(x) ?Q(x)) x(?A(x) ∨Q(x)) ?A(a) ∨Q(a) ………………………得1分 Q(a) ?A(a) x(P(x)?A(x)∨B(x)) x(?P(x) ∨A(x)∨B(x)) ?P(a) ∨A(a)∨B(a) ………………………得1分 P(a), ?A(a) ………………………得1分 B(a) P(a) ∧B(a) ………………………得1分 $x (P(x) ∧B(x)) 证明：?(P∨(?P∧Q))? ??P∧? (?P∧Q) ………………………得1分 ??P∧ (P∨?Q) ………………………得1分 ?(?P∧P)∨(?P∧?Q) ………………………得2分 ?0∨(?P∧?Q) ………………………得2分 ?P∧?Q (1)证明：1)R是自反的………………………得1分 2)R是对称的………………………得1分 3)R是传递的………………………得1分 所以，R为等价关系。………………………得1分 (2)[1]=[4]=[7]=[10]={1,4,7,10}………………………得2分 [2]=[5]=[8]={2,5,8}………………………得1分