北京科技大学远程教育学院《离散数学》模拟试卷 3学号： 学习中心名称： 专业： 层次： 姓名： 题号一 二 三 四 五 六 七 八 九 十总分得分一、判断题（每题 2 分，共 10 分。用 F 表示错，T 表示对）1、“2015 年 1 月 1 日是晴天。”是复合命题。 （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、Mx：x 是人。Hx：x 活到百岁。则“有的人活到百岁。” 可符号化为  x  M  x  H  x  。3、非负整数集 与普通加法 构成的代数系统中，有逆元的元素是 0 。 4、整数集 Z 与普通乘法 × 构成的代数系统是 独异点 。5、完全图 Kn ，当 n  2 的奇数 时是欧拉图。三、（每题 6 分，共 18 分）1、设 X={1，2，3}，对关系图1写出相应的关系矩阵，并说出它具有的性质。解： 只有自反性 图22、指出图2是不是哈密尔顿图，说明理由。 解：是哈密尔顿图，回路 abcfeda。3、设无向树 T 中有 4 度顶点有 2 个，3 度顶点有 3 个，其余是树叶， 问 T 中有几个树叶?解：设有 x 个树叶 2[2+3+x1]=2×4+3×3+x 2x+ 8=17+x x = 9四、（每题 8 分，共 32 分）1、解释 I 如下：D ， ； 谓词 L ， 为：L2，3=L3，2=0，L2，2= L3，3=1； 求公式 L ， 的真值解： L ，  Lx，2∨Lx，3L2，2∨L2，3∧L3，2∨L3，31∨0∧0∨112、判别命题公式 pqqp。解：pqqpp∨q∨q∨p 可满足式3、用避圈法求图1的最小生成树，并计算权数。解： 权=1＋1＋1＋3=64、 求带权 1，2，4，6、7 的最优二元树，并计算权数。解： 或 权=3＋7＋13＋20=43五、（10 分） ={ ， ， }，定义 上的二元运算*如下：* 运算 * 是否具有可交换性、单位元、零元，每个元素是否有逆？解：有可交换性、单位元 a、无零元、a ，c 是自己的逆。六、（10 分）A = {1，2，3，…，9，10}，R 是 A 上的整除关系。画出哈斯图，并指出最大元、最小元；极大元、极小元。解：最大元：无 ，最小元、极小元： 1， 极大元：6，7，8，9，10七、（10 分）写出下面推理的证明，要求写出前提、结论，并注明推理规则。 如果小王是理科学生，则小王必学高等数学。如果小王不是文科学生， 他一定是理科学生。小王没学高等数学。所以小王是文科学生。 p：小王是理科学生。q：小王是文科学生。r：小王学高等数学。 前提：pr，pq，r结论：q证明：① pr 前提引入 ④ pq 前提引入② r 前提引入 ⑤ q ③④ 假言推理③ p ①② 拒取式 正确推理