北京科技大学远程教育学院《离散数学》模拟试卷 1学号： 学习中心名称： 专业： 层次： 姓名： 题号一 二 三 四 五 六 七 八 九 十总分得分一、判断题（每题 2 分，共 10 分。用 表示错， 表示对）1、“明年 1 月 1 日是晴天。”是复合命题。 （ F ）2、对任意集合 、 、 。“如果 及 ，则 。”是真命题。（ T ）3、  ， 上的恒等关系 是 上的等价关系 。 （ T ）4、非负整数集 与普通加法 构成的代数系统中，没有单位元。 （ F ）5、 是 到 的满射，则 的逆关系是 到 的映射。 （ F ）二、填空题（每题 2 分，共 10 分）1、无向图 G 有 n 个顶点，m 条边，且 m n，则 G 中一定含有 回路 。2、 是有理数。 是整数。则“整数都是有理数。” 可符号化为  x  M  x  H  x  。 3、 、 都是非空集合 上的等价关系，则 － 不是 上的等价关系。4、整数集 Z 与普通加法 + 构成的代数系统是 群 。5、 = {a，{}}，则 的幂集为 {  { a } ， {{  }} ， { a ， {  }}} 。三、（每题 6 分，共 18 分）1、证明：证明：A－(B∩C) = A∩~(B∩C) = A∩~B∪~C = A∩~B∪A∩~C = (A–B)∪(A – C) 2、用避圈法求图（1）的最小生成树，并计算权数。 权= 1＋2＋4＋5=123、求 8 阶循环群 G = < a > = < e，a1，a2 ，…，a7 >的全部子群。解： 8 的正因子 1、2、4、8，< a8/1 > = < a8 > = {e} 1 阶子群< a8/2 > = < a4 > = {e，a4} 2 阶子群< a8/4 > = < a2 > = {e，a2，a4，a6} 4 阶子群 < a8/8 > = < a > = {e，a，a2，…，a7} 8 阶子群四、（每题 8 分，共 32 分） 1、求带权 1，1，3，6、7 的最优二元树，并计算权数。解：权=2＋5＋11＋18=36 2、判别命题公式的类型 ，并求主析取范式。解： 永真式 主析取范式 m0m1m2m3 3、A = {1，2，3，4，6，8，12，24}， 是 上的整除关系。 画出哈斯图，并指出 A 的最大元、最小元；极大元、极小元。解： 最小元、极小元：1，最大元、极大元：24 4、 、 求 ， ， ，解：A∪B={{1，2}，2，4，{3}，{4}，{2}} A∩B={{1，2}，4} A－B={2，{3}} AB={2，{3}，{4}，{2}} 五、（10 分） 是有理数集，对 ，定义 上的运算 －2  其中 、－、 分别为普通的加、减、乘法。 验证代数系统〈 ，〉是独异点，但不是群。解：(x*y)*z = (x+y–2xy)*z = (x+y–2xy) +z –2(x+y–2xy)z = x+y+z –2xy–2xz–2yz +4xyz=x*(y*z ) 满足结合律 0 是单位元， 1/2 是零元无逆元。〈 ，〉是独异点，但不是群。 六、（10 分） 有向图 的邻接矩阵 1、画出这个有向图； 2、求 ； 3、 中长度为 2 的回路有多少条？ 4、 中 到 长度小于等于 2 的通路有多少条？ 5、 中的元素 说明什么？解：1、2、3、A2中对角线上元素之和为 3，所以， 中长度为 2 的回路有 3 条4、A 和 A2中 1 行 2 列中元素都是 2，所以， 中 到 长度小于等于 2 的通路有 4 条5、 中的元素 说明 到 长度等于 2 的通路有 1 条 七、（10 分）写出下面推理的证明，要求写出前提、结论，并注明推理规则。如果今天是星期一，我们考英语或离散数学。如果英语老师开会，就不考英语。今天是星期一。英语老师开会。所以我们考离散数学。设 p：今天是星期一。q：我们考英语。 r：我们考离散数学。s：英语老师开会。前提：pq∨r， sØq， p ，s 结论：r证明：① p 前提引入 ② pq∨r 前提引入 r ③ q∨r ①② 假言推理④ s 前提引入⑤ sØq 前提引入⑥ Øq ④ ⑤ 假言推理⑦ r ③ ⑥ 析取三段论推理正确