中国石油大学（北京）2008—2009学年第二学期。
离散数学》期末考试试卷a
班级： 姓名： 学号： 分数：
一、 判断题（只写“是”或“不是”、“对”或“错”、“或“”即可，不用写过程及依据。每小题1分，共10分）
请问下列命题是否正确？
1． 命题联结词集是联结词完备集。
2． 当r和s都是集合a上的反自反关系时，则rs也是反自反关系。
3． 设为无限循环群，则g中有且仅有一个生成元。
4． 单位元为群中惟一幂等元。
5． 设r是集合a上的反对称关系，则t(r)一定是反对称关系。
6． 若存在从|a|到|b|的单射，则|a|≤|b|。
7． 完全图kn（n≥3）是哈密顿图。
8． 通过图的邻接矩阵可以判断图是否是欧拉图。
9． 图g中任意两结点间都有路可达，则g必是一棵树。
10． 连通无向图g的任何边，是g的某棵生成树的弦。
二、 选择填空题（从供选择的答案中选出一个应填入【 】中的正确答案或在横线上填写正确答案。每空2分，共20分）
1．给定下列序列，可构成无向简单图的结点度数序列的是【 】
a：(1,1,2,2,3) b： (1,1,2,2,2) c：(0,1,3,3,3) d： (1,3,4,4,5)
2．下列集合哪个不是偏序集【 】
a: 〈i，≤〉其中≤是整数集合上的小于等于关系。
b: 〈其中|是整除关系。
c: 〈i，|〉其中|是整数集合上的整除关系
d: 〈p()，其中是的幂集合上的包含关系。
3．设集合a=，下面定义的哪种运算关于集合a是不封闭的？【
a：x*y=max(x,yb: x*y=gcd(x,y) ,即x ,y的最大公约数。
c: x*y=min(x,yd: x*y=lcm(x,y) ,即x ,y的最小公倍数。
4．瑞士数学家列昂哈德欧拉发表图论“哥尼斯堡七桥”问题于【 】年。
a：1637 b：1736c：1836 d：1863
5．前提 sr，p q，q r的有效结论是【 】
a： p b：qc：p q d：s
6．函数的复合满足【 】
a：结合律 b：交换律 c：幂等律 d：分配律。
7．设a(x) :x是人，b(x) :x犯错误，命题“没有不犯错误的人”符号化为【 】
a: x (a(x) b(xb: x (a(x) b(x))
c: x (a(x) b(xd: x (a(x) b(x))
8．整数集上的小于关系“＜”是具有和性质的关系。
三、 简答题（共40分）
1． 求p ((pq) (qp))的主析取范式和主合取范式。
2． 求(x)p(x)(y)q(x,y)的前束范式。
3． 设*是正整数集合z+的二元运算，且x*y= lcm(x,y) ,即x ,y的最小公倍数。问运算是可交换的可结合的吗？运算满足幂等律吗？
并说明原因。单位元是否存在？若存在请求出。
4． 给定集合s=，r是s上的整除关系，写出r的集合表示形式，并画哈斯图。子集b=，求b的上界和下界，最小上界和最大下界。
5． 设t为二叉树，除叶子结点外还含有3个3度结点、1个2度结点。问t中有几个1度结点？并画出两个满足上述要求的互不同构的二叉树。
四、 证明题（任选3题即可，多做不加分）（共30分）
1． 设g为群，如果ag 都有 a2 = e, 证明 g 为 abel群。
2． r是集合a上的反自反的、对称的关系，证明r不是传递的。
3． g为n个结点m条边，每个面的次数至少为4的连通平面图，证明：m≤2n-4。
4． 设是群，ag ,定义函数 f :gg，,f(x)=a*x*a -1，xg，证明：f是g的自同构。
离散数学试题A卷
2010 至 2011 学年第 2 学期 课程名称 离散数学b考试时间 110 分钟 课程 7304159试卷总分 100 分。考试形式 闭卷学生自带普通计算器 否 一 填空题 每空2分，共30分 1 设e a b c 则 a b c p a p cab a c2 设m x x是人，d x x是长寿...
离散数学试题A卷
2010 至 2011 学年第 2 学期 课程名称 离散数学b考试时间 110 分钟 课程 7304159试卷总分 100 分。考试形式 闭卷学生自带普通计算器 否 一 填空题 每空2分，共30分 1 设e a b c 则 a b c p a p cab a c2 设m x x是人，d x x是长寿...
离散数学试题A卷
一 单项选择题 本大题共10小题，每小题2分，共20分 1 下列命题公式中不是重言式的是 a p q r b p q p c p p p d p q r q p r 2 设个体域是整数集，则下列命题的真值为真的是 a yx x y 1 b xy x y 0 c xy x y y2 d yx x y ...