2015-2016 学年第一 学期本科试卷 课程名称:离散数学(A卷） ―――――――――――――装――――――――――――订――――――――――――线―――――――――――――― 题号 得分 一 二 三 总成绩 学 院: 专 业: 学号: 姓名: 请注意：单项选择题答案务必填写在下表中，否则无效。 01-05： 06-10： 11-15： 16-20： 得分 一、单项选择题（每小题2分，共40分） 1. 命题“我们今天去野餐，除非雾霾散去。”，令P：我们今天去野餐，Q：雾霾散去，下列翻译正确的是（ ）。 （A）P→Q （B）Q→P （C）P→Q （D）Q→P 2.令S（x）：x是大学生，L（y）：y是运动员，A（x，y）：x钦佩y，命题“有些大学生不钦佩运动员。”，下列翻译正确的是（ ）。 (A) (?x) (S (x) ? (?y)(L（y）? A（x，y））） (B) (?x) (S (x) ∨ (?y)(L（y）? (C) (?x) (S (x) ? (?y)(L（y）? A（x，y））） A（x，y））） (D) (?x) (S (x) ? (?y)(L（y） ? A（x，y））） 3. 已知集合A={?，{?}}，则A的幂集是（ ）。 (A) {?，{?}，{{?}}，{?，{?}}} (B) {?，{?}，{?，{?}}} (C) {?，{{?}}} (D) {?，{?}}
第 1 页 （共 8 页）
年级：14 专业：计算机相关（本科） 课程号：1002061010
4. 以下描述正确的是（ ）。
(A) 阿贝尔群不存在幺元。
(B) 若
5. 3个元素的集合上可以构成（ ）个等价关系。 (A) 3 (B) 5 (C) 7 (D) 9
6. 设X={1，2，3}，Y={a，b}，则有（ ）个从X到Y（即X?Y）的函数。 (A) 9 (B) 8 (C) 5 (D) 6
7．在一个格< A,? >中，对任意的a,b∈A，都有( )。 (A) a?b=a (B) a?b?b (C) a?b=a (D) a?b?a
8．设f和g为定义在集合S上的二元关系，且有fc。gc ={<1,2>, <3,2>,<3,3>}，则g。f为（ ）。
(A) {<1,2>, <3,2>,<3,3>} (B) {<1,1>, <2,2>,<3,3>} (C) {<2,1>, <2,3>,<3,3>} (D) {<3,2>, <2,2>,<3,3>}
9．集合X=?1,3,5?,Y=?1,9,10,25,?,f={
(A) 入射函数 (B) 满射函数 (C) 双射函数 (D) 非函数
10. 设有群
第 2 页 （共 8 页）
2015-2016 学年第一 学期本科试卷 课程名称:离散数学(A卷） ―― 11. 设(S,?)是偏序集，? 是整除关系，则当S=( )时，(S,?)是格。 ―― ― ― ― ― ― :名―姓― ― ― ― 线 ― ― ― ― ―:号―学― ― ― ― ― ― 订 ― ― ― ― ― :业―― 专― ― ― ― ― 装 ― ― ― ― ― :院― ―学――――― ―(A) {1,2,3,4} (B) {1,3,5,7} (C) {2,4,6,8} (D) {2,4,6,12} 12. 以下关于树的描述不正确的是（ ）。 (A) 一个连通且无回路的无向图称为树。 (B) 图中每一对结点之间有一条且仅有一条路。 (C) 图是连通的，删去一条边和一个结点后便不连通了。 (D) 图中无回路，但增加一条新边，得到一个且仅有一个回路。13. 存在割点的连通图G，其连通度为（ ）。 (A) 0 (B) 1 (C) 2 (D) δ(G) 14. 对于包含6个顶点的完全图K6，它的边数为( )。 (A) 21 (B) 12 (C) 30 (D) 15 15. 设A={a，b， c， 1， 2}， 下面哪个集合是A的划分（ (A) {{a，b，c}，{1，2}} (B) {{a，b，c}，{c，1，2}} (C) {{a，b，c}，{c}，{1}} (D) {{a，b，c}} 16. 公式（p∧Q）∨T的对偶式是为( )。 (A)（p∨Q）∧F (B) T (C) （p∨Q）∧F (D)（p∨Q）∧F 第 3 页 （共 8 页）
。 ） 年级：14 专业：计算机相关（本科） 课程号：1002061010
17. 以下集合关系式不成立的是( )。 (A) A∪B=(A∩~B) ∪ (~ A∩B) ∪(A∩B) (B) A○+B=(A∩~B) ∪ (~ A∩B) (C) A－B= ~ A∩B (D) ~（A∪B）= ~ A∩~B
18. 以下哪种情况可以将无向图G一笔画出( )。 (A) 无向图G具有一条欧拉回路。 (B) 无向图G没有偶数度数的结点。 (C) 无向图G删除一结点后是连通的。 (D) 无向图G所有结点度数和是边数的3倍。
19. 已知一个平面图G有v个结点，e条边，r个面，则其构成（v，e，r）不可能为（ ）。
(A) （3，3，2） (B) （2，3，2）
(C) （4，4，2） (D) （4，5，3）
20. 以下哪个代数系统是群（ ）。 (A) < R－{0}，－> (B) < I，＋>
(C)
第 4 页 （共 8 页）
―――― ― ― ― ― ― :名―姓― ― ― ― 线 ― ― ― ― ―:号―学― ― ― ― ― ― 订 ― ― ― ― ― :业―― 专― ― ― ― ― 装 ― ― ― ― ― :院― ―学――――― ―2015-2016 学年第一 学期本科试卷 课程名称:离散数学(A卷） 得分 二、解答题(每题10分，共40分) 1．求下式的主析取范式和主合取范式。 （P∨Q）∧R 2. 设集合A={1，2，3，4},给定A上的关系R={<1,2>,<2,1>,<2,3>,<3,4>}，求关系R的自反闭包r（R），对称闭包s（R）和传递闭包t（R）。 第 5 页 （共 8 页）