2004～2005 第一学期考试卷 《离散数学》课程 闭卷 课程类别：必修 考试时间 序号 一 二 三 四 五 六 七 八 九 十 总 分 得分 评卷人 一、 单项选择题 (本大题共 10 小题，每小题 2 分，共 20 分) 1.下列不是命题的是[ ]。 A. 7 能被 3 整除. B. 5 是素数当且仅当太阳从西边升起. C. x 加 7 小于 0. D. 华东交通大学位于南昌北区. 2. 设 p:王平努力学习，q:王平取得好成绩，命题“除非王平努力学习，否则他 不能取得好成绩”的符号化形式为 [ ]。 A. p→q C. q→p B. p→q D. q→p 3. 下面 4 个推理定律中，不正确的为 [ ]。 A. A=>(A∨B) (附加律) B. (A∨B)∧A=>B (析取三段论) C. D. (A→B)∧A=>B (假言推理) (A→B)∧B=>A (拒取式) 4. 设解释 I 如下，个体域 D={1,2},F(1,1)=(2,2)=0,F(1,2)=F(2,1)=1，在解释 I 下， 下列公式中真值为 1 的是 [ ]。 A.x yF(x,y) B. xyF(x,y) C. xyF(x,y) D. xyF(x,y) 5. 下列四个命题中哪一个为真？ [ ]。 A. ∈ B.  ∈{a} 

C. ∈{{}} D.  6. 设 S={a,b,c,d}，R={,,}，则 R 的性质是 [ ]。 A.自反、对称、传递的 B. 对称、反对称、传递的 C.自反、对称、反对称的 D. 只有对称性 7. 设 A={a,b,c}，则下列是集合 A 的划分的是[ ]。 A.{{b,c},{c}} 8. 设集合 Q )2( B.{{a,b},{a,c}} C.{{a,b},c} { ba  ,2 Qba   }) D.{{a},{b,c}} 关于普通数的乘法，不正确的有[ ]。 A. 结合律成立 B. 有幺元 C. 任意元素有逆元 D. 交换律成立 9. 设 A 是非空集合，P(A)是 A 的幂集，∩是集合交运算，则代数系统〈P(A), ∩〉的幺元是[ ]。 A. P(A) B. φ C. A D. E 10. 下列四组数据中，不能成为任何 4 阶无向简单图的度数序列的为[ ]。 A. C. 2,2,2,2 1,1,2,3 B. 1,1,1,3 D. 1,2,2,3 二、填空题（本题共 10 小题，每小题 2 分，共 20 分） 1. 命题公式 p→q 的真值为假，当且仅当_________________。 2. 公 式 p→(q→r) 在 联 结 词 全 功 能 集 {  ，  ，  } 中 等 值 形 式 之 一 为 ____________________。 3. 谓词公式xF(x)yG(y)的前束范式为 。 4. 设集合 A = {1，4}，B = {2，4}，则 P (A) - P (B) = _____ ___________。 5. R 是非空集合上的偏序关系，当且仅当 R 具有___ ________。 6. 设函数 f(x)=x + 1,g(x)= 2x2, 则 f o g =____________________。 7. 设σ=(134)(256)，τ=(25)(1643)，则στ=____________________。 8. 命 题 “ 设 G 为 任 意 的 n 阶 简 单 的 哈 密 尔 图 ， 则 u ， v∈V(G) ， 均 有 d(u)+d(v)≥n”的真值为___________。 9. 无 向 连 通 图 G 是 欧 拉 图 ， 当 且 仅 当 G 中 每 一 个 顶 点 的 度 数 都 为 

____________。 10. 设树 T 有 m 个顶点，n 条边，则 T 中顶点与边的关系为_______________。 三、证明下式（6×2=12 分） 1、 判断下面推理是否正确。 如果你学习，那么你离散数学不会不及格。 如果你不热衷于玩游戏，那么你将学习。 但你离散数学不及格。因此你热衷于玩游戏。 2、在一阶谓词逻辑中构造下面推理的证明。 前提：xF(x), x(F(x)∨G(x)→H(x)) 结论：xH(x) 四、用等值演算法求公式((p∨q)∧(p→q))↔(q→p)的主合取范式与主 析取范式。（10 分） 五、设 R1 和 R2 是集合 X={ 0 , 1 , 2 , 3 , 4 }上的关系， R1={| y = 2x }，R2={| x= y + 1} 写出 R1、R2 ，写出 R2 的关系矩阵，并求出 R1R2。 （8 分） 六、设集合 A={2,3,4,6,8,12,24}，R 为 A 上的整除关系， (1)画出偏序集（A，R）的哈斯图； (2)出集合 A 中的最大元、最小元、极大元、极小元； （3）写出 A 的子集 B={2,3,6,12}的上界、下界、最小上界、最大 下界。 （8 分） 七、 设 Z 为整数集合，在 Z 上定义二元运算*， x,y∈Z 有 * yx 。证明：是一个群。（10 分） 2  x y 

八、平面图 G 有两个连通分支，其顶点数为 12，边数为 34，问 G 有 多少个面？（6 分） 九、对下图， （1）求其邻接矩阵；（2）长度小于 3 的通路和回路的总数。(6 分) V2 v3 v1 v4 v5