北京科技大学远程教育学院《离散数学》模拟试卷 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 时是哈密尔顿图。三、（每题 7 分，共 28 分）1、A ｛，，｛｝｝求 A 的幂集解：PA  ｛，｛｝，｛｝，｛｛｝｝，｛，｝，｛，｛｝｝，｛，｛｝｝，A｝2、设 X={1，2，3}，对关系图1写出相应的关系矩阵，并说出它具有的性质。解：(1) ，有自反性3、解释 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 。” 真值为假 4、设无向图 G 中有 12 条边，已知 G 中 3 度顶点有 6 个，其余顶点 的度数均小于 3，问 G 中至少有几个顶点?解：24－18 = 6，至少还需要三个顶点，G 中至少有 3＋6=9 个顶点。四、（每题 8 分，共 32 分） 1、指出下图是不是欧拉图，说明理由。解：是欧拉图，每个顶点的度数是偶数。 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、 是有理数集，对 ，定义 上的运算 －3 其中 、－分别为普通的加、减法。 验证代数系统〈 ，〉是群。解：(x*y)*z = (x+y–3)*z = (x+y–3) +z –3= x+y+z –6=x*(y*z ) 满足结合律 设 e 是单位元， x*e = x+e–3 =x 解得 e=3设 x1是 x 的逆元，x*x1= x+x1–3 =e=3 解得 x1=6x 〈 ，〉是群。 五、（10 分）求带权 1，3，4，5、7 的最优二元树，并计算权数。解：权=4＋8＋12＋20=44六、（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 ③ ⑥ 析取三段论推理正确