离散数学2006-2007A..doc

北京科技大学2006 — 2007 学年度第 1 学期 离散数学 试题（A卷）（时间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}的所有下界____________。任意一个正整数n，存在含有____________个元素的布尔代数。 在平面图中，若=6，e=，则r= ____________。 树中边数和结点的关系是____________。 设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确定的等价类。。 √ 2. √ 3 √ 4. √ 5. 6. 7. 8.√ 9.√ 10.√ 11. 12. 13. 14. 15.√ 16. 17. 18.√ 19.√ 20.√ 二、填空题（共30分，每个空格2分） {φ，{φ}，{1}，{2}，{φ，1}，{φ，2}，{1，2}，A} {a，a，a，c} M1 ＝{0}，M2 ＝{1，2，3}，M3 ＝{4，5} c，d P∧?Q∧R或m5 （F（a，a）∨F（a，b））∧（F（b，a）∨F（b，b））或 （F（a，a）∧F（b，a））∨（F（a，b）∧F（b，b）） 7 DBKHLEAFICGMJN {f1, f2}，{f1, f2}f3 = {f3, f5}, {f1, f2}f4 = {f4, f6}. 2个 {(1234), (13)(24), (1432), (1)} N，N×N×N 21人 三、证明（8分） 在自然推理系统F中构造下面推理的证明 前提：， 结论： 证明： (1) 附加前提引入 (2) (1) EI （1分） (3) (2)化简 (4) (2)化简 (5) 前提引入 (6) (3)EG （1分） (7) (5)(6)假言推理 （1分） (8) 前提引入 (9) (4)EG （1分） (10) (8) (9)假言推理 （1分） (11) (10)EI （1分） (12) (7)UI （1分） (13) (11) (12) 假言推理 （1分） (14)