北京科技大学远程教育学院《离散数学》模拟试卷 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  。 2、 ， ， ， ， 、 都是 的函数。 ： ， ， ， ： ， ， ， （1） 、 中哪个有反函数？若有则求出反函数。 （2）求出 、 。解：1、 g 是双射，g –1 ： ac，ba，cd，db 2、 gog ： ad，bc，cb，da goh：ac，bc，ca，da3、判别命题公式的类型 ，并求主析取范式。解： 永真式主析取范式 m0m1m2m3m4m5m6m7 4、 ={ ， ， }，定义 上的二元运算*如下：* 运算 * 是否具有可交换性、单位元、零元，每个元素是否有逆？解：有可交换性；a 是单位元；无零元；a、c 有逆，b 无逆。 5、求图 1 所示平面图各面的次数，并验证欧拉公式.解： R1，R2，R0，的次数分别为 7，3，10n=9，m=10，r=3 9-10+3=2六、（10 分）设 7 个字母在通信中出现的频率如下： a: 35% b: 35% c: 35% d: 35% e: 35% f: 35% g: 35%(1) 以频率为权，求最优 2 元树.(2) 利用所求 2 元树找出每个字母的前缀码.解：(1)(2)11 传 a，01 传 b，101 传 c，100 传 e，0001 传 f，0000 传 g七、（10 分）写出下面推理的证明，要求写出前提、结论，并注明推理规则。 如果乙不参加篮球赛，那么甲就不参加篮球赛。若乙参加篮球赛，那么 甲和丙就参加篮球赛。因此，如果甲参加篮球赛，则丙就参加篮球赛。p：甲参加篮球赛。q：乙参加篮球赛。r：丙参加篮球赛。前提：qp，q(pr)结论：p r证明：① ① qp 前提引入 ② pq ① 置换 ③ p 附加前提引入 ④ q(pr) 前提引入 ⑤ pr ③④ 假言推理 ⑥ r ⑤ 化简 正确推理 3、 、 都是非空集合 上的等价关系，则 － 不是 上的等价关系。4、整数集 Z 与普通加法 + 构成的代数系统是 群 。5、 = {a，{}}，则 的幂集为 {  { a } ， {{  }} ， { a ， {  }}} 。三、（每题 5 分，共 20 分）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、求 20 阶循环群的全部子群。解：G = < a > = < e，a1，a2 ，…，a19 > < a20/1 > = < a20 > = {e} 1 阶子群< a20/2 > = < a10 > = {e，a10} 2 阶子群< a20/4 > = < a5 > = {e，a5，a10，a15} 4 阶子群 < a20/5 > = < a4 > = {e，a4，a8，a12，a16} 5 阶子群< a20/10 > = < a2 > = {e，a2，a4，…，a18} 10 阶子群G = < a > = < e，a1，a2 ，…，a19 > 20 阶子群4、解释 I 如下：个体域 D = N（N 为自然数）；D 中的特定元素 a = 2 ；D 上 的特定函数 ， = ；D 上的谓词 F ， ： 说明公式 F ， 在解释 I 下的含义，并讨论其真值。解：xF(g(x，a)，x) xF(x×a，x)  x( x×2 = x ) 含义：“对任意的自然数 x ，x 乘 2 等于 x 。” 真值为假四、（每题 6 分，共 30 分） 1、求带权 1，1，3，6、7 的最优二元树，并计算权数。解：权=2＋5＋13＋18=38 2、判别命题公式的类型 ，并求主析取范式。解： 主析取范式 m0m1m2m3 3、A = {1，2，3，4，6，8，12，24}， 是 上的整除关系。 画出哈斯图，并指出最大元、最小元；极大元、极小元。解：最小元、极小元：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}} 5、设 f： ，g： ， 是 是双映射。证明：f 是单射的。证明：∵ fog ：AC 是单射。若 f：AB 不是单射，则 x1≠x2  A ，使 f(x1) = f(x2) ，即有 g(f(x1)) = g(f(x2)) ， 由于 fog 是单射，又应有 g(f(x1)) ≠ g(f(x2)) ，矛盾。 所以 f：AB 是单射。五、（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、 中长度为 2 的回路有 3 条4、 中 到 长度小于等于 2 的通路有 4 条5、 中的元素 说明 到 长度等于 2 的通路有 1 条七、（10 分）写出下面推理的证明，要求写出前提、结论，并注明推理规则。大熊猫都产在中国。欢欢是大熊猫。所以欢欢产在中国。 F(x)：x 是大熊猫。G(x)：x 是产在中国。a：欢欢前提：xFxGx ， F(a) 结论：G(a)证明： ① xFxGx 前提引入 ② FaGa ① UI 规则 ③ F(a) 前提引入 ④ G(a) ② ③ 拒取式 正确推理北京科技大学远程教育学院《离散数学》模拟试卷 2 答案学号： 学习中心名称： 专业： 层次： 姓名： 题号一 二 三 四 五 六 七 八 九 十总分得分一、判断题（每题 2 分，共 10 分。用 表示错， 表示对）1、“2 是无理数。”不是命题。 （ F ）2、，，是真命题。 （ T ）3、二元关系 R=1，1，2，2，3，3有对称性 （ T ） 4、非负整数集 与普通加法 构成的代数系统中，所有元素都没有逆元。 （ F）5、 是 到 的满射，则 的逆关系是 到 的映射。 （ F ）二、填空题（每题 2 分，共 10 分）1、无向树 T 有 n 个顶点，则 T 中有 n － 1 条边。2、 是人。 爱唱歌。则“有的人爱唱歌。” 可符号化为  x  M  x  H  x  。3、非负整数集 与普通加法 构成的代数系统中，有逆元的元素是 0 。4、整数集 Z 与普通乘法 × 构成的代数系统是 独异点 。5、完全图 Kn ，当 n  3 时是哈密尔顿图。三、（每题 5 分，共 20 分）1、A ｛，，｛｝｝求 A 的幂集解：PA  ｛，｛｝，｛｝，｛｛｝｝，｛，｝，｛，｛ ｝｝，｛，｛｝｝，A｝2、设 X={1，2，3}，对关系图1写出相应的关系矩阵，并说出它具有的性质。 解：(1) ，有对称性3、解释 I 如下：D ， ； 谓词 L ， 为：L 2，3=L3，2=0，L2，2= L3，3=1； 求公式 L ， 的真值解： L ，   L2，2L2，3L3，2L3，314、设无向图 G 中有 12 条边，已知 G 中 3 度顶点有 6 个，其余顶点 的度数均小于 3，问 G 中至少有几个顶点?解：24－18 = 6，至少还需要三个顶点，G 中至少有 3＋6=9 个顶点。四、（每题 8 分，共 40 分） 1、指出下图是不是欧拉图，是不是哈密尔顿图，说明理由。解：是欧拉图，每个顶点的度数是偶数。是哈密尔顿图，abcdefsghijka 构成哈密尔顿回路。