1、摇 离散数学试题答案及评分参考第 员 摇 摇 摇 摇 页渊共 缘 页冤绝密绎启用前圆园圆猿 年 员园 月高等教育自学考试全国统一命题考试渊课程代码摇 园圆猿圆源冤一尧 单项选择题院 本大题共 员缘 小题袁 每小题 员 分袁 共 员缘 分遥员郾 阅圆郾 月猿郾 阅源郾 月缘郾 阅远郾 月苑郾 粤愿郾 悦怨郾 粤员园郾 阅员员郾 月员圆郾 悦员猿郾 粤员源郾 悦员缘郾 粤二尧 填空题院 本大题共 员园 小题袁 每小题 圆 分袁 共 圆园 分遥员远郾 喳 约 葬袁凿 跃 袁 约 葬袁糟 跃 札袁喳 约 糟袁凿 跃 札员苑郾 圆袁双员愿郾 喳园袁圆袁源袁远袁愿袁员园札袁喳 约 缘袁园 跃 袁 约 源袁
2、圆 跃 袁 约 猿袁源 跃 袁 约 圆袁远 跃 袁 约 员袁愿 跃 袁 约 园袁员园 跃 札员怨郾 缘圆园郾 栽袁云圆员郾 灶渊灶 原 员冤 辕圆圆圆郾 猿圆猿郾 园袁远 原 曾圆源郾 圆渊灶 原 员冤圆缘郾 员园袁远源三尧计算题院本大题共 缘 小题袁每小题 远 分袁共 猿园 分遥摇 摇 圆远郾 解院分别列出两个命题公式的真值表如下孕 匝 砸匝 寅 砸孕 寅 匝 渊孕 寅 匝冤 夷 渊匝 寅 砸冤孕 寅 砸渊渊孕 寅 匝冤 夷 渊匝 寅砸冤冤 寅 渊孕 寅 砸冤园园园员员员员员园园员员员员员员园员园园员园员员园员员员员员员员员园园员园园园员员园员员园园员员员员园园员园园员员员员员员员员员从真值
3、表最后一列全为 员袁可见袁渊渊孕 寅 匝冤 夷 渊匝 寅 砸冤冤 寅 渊孕 寅 砸冤 为重言式遥渊真值表 缘 分袁最后结论 员 分冤摇 摇 圆苑郾 解院渊劭 孕 遗 砸冤 夷 渊孕 遗 匝冤 夷 渊劭 匝 遗 劭 砸冤圳渊渊劭 孕 夷 孕冤 遗 渊劭 孕 夷 匝冤 遗 渊孕 夷 砸冤 遗 渊匝 夷 砸冤冤 夷 渊劭 匝 遗 劭 砸冤 渊员 分冤圳渊劭 孕 夷 匝 夷 劭 砸冤 遗 渊孕 夷 劭 匝 夷 砸冤渊猿 分冤圳皂圆遗 皂缘此即所求命题公式渊劭 孕 遗 砸冤 夷 渊孕 遗 匝冤 夷 渊劭 匝 遗 劭 砸冤 的主析取范式遥渊圆 分冤摇 离散数学试题答案及评分参考第 圆 摇 摇 摇 摇 页渊
4、共 缘 页冤摇 摇 圆愿郾 解院根据所列关系性质袁填表如下摇 摇 摇 摇运算性质 摇 摇 摇皂葬曾渊曾袁赠冤皂蚤灶渊曾袁赠冤渣 曾 原 赠 渣可结合性是是否可交换性是是是渊每空 员 分冤摇 摇 圆怨郾 解院根据整除关系及哈斯图规范袁画出哈斯图如答 圆怨 图所示院答 圆怨 图渊源 分冤由答 圆怨 图所示的哈斯图可见袁该整除关系偏序集有下界袁无上界袁因而不能构成格遥渊圆 分冤摇 摇 猿园郾 解院渊员冤 由题 猿园 图所示有向图 阅袁可得其邻接矩阵为渊圆 分冤渊圆冤 由上述 酝阅袁利用矩阵乘法可得由此可知袁阅 中长度为员 的通路有怨 条袁长度为圆 的通路有员缘 条袁长度为猿 的通路有圆缘 条袁长度为
5、源 的通路有源园 条曰阅中长度为员 的回路有员 条袁长度为圆 的回路有猿 条袁长度为 猿 的回路有 苑 条袁长度为 源 的回路有 猿 条遥渊源 分冤四尧证明题院本大题共 猿 小题袁每小题 苑 分袁共 圆员 分遥摇 摇 猿员郾 证明院渊员冤 自反性院坌 约 曾袁赠 跃 沂 粤 由于 曾赠 越 赠曾袁故 约 约 曾袁赠 跃 袁 约 曾袁赠 跃 跃 沂 砸即 砸 是自反的遥渊圆 分冤摇 离散数学试题答案及评分参考第 猿 摇 摇 摇 摇 页渊共 缘 页冤渊圆冤 对称性院如果 约 约 曾袁赠 跃 袁 约 怎袁增 跃 跃 沂 砸袁则 曾增 越 赠怎于是 约 约 怎袁增 跃 袁 约 曾袁赠 跃 跃 沂 砸因
6、此 砸 是对称的遥渊圆 分冤渊猿冤 传递性如果 约 约 曾袁赠 跃 袁 约 怎袁增 跃 跃 沂 砸袁则 曾增 越 赠怎且若 约 约 怎袁增 跃 袁 约 皂袁灶 跃 跃 沂 砸袁则 怎灶 越 增皂于是 曾灶 越 皂赠袁从而得约 约 曾袁赠 跃 袁 约 皂袁灶 跃 跃 沂 砸即 砸 是传递的遥渊圆 分冤综合上述渊员冤渊圆冤渊猿冤袁可知 砸 是 粤 上的等价关系遥渊员 分冤摇 摇 猿圆郾 证明院对谓词公式进行等值推演袁并注意参数替换得到坌曾渊孕渊曾冤 遗 匝渊曾冤冤 寅 坌曾孕渊曾冤 遗 埚曾 匝渊曾冤圳劭 渊坌曾渊孕渊曾冤 遗 匝渊曾冤冤冤 遗 坌赠孕渊赠冤 遗 埚扎 匝渊扎冤渊圆 分冤圳埚曾坌赠
7、埚扎渊渊孕渊曾冤 遗 匝渊曾冤冤 寅 孕渊赠冤 遗 匝渊扎冤冤渊猿 分冤显然这是一个永真式遥渊圆 分冤证明 圆院坌曾渊孕渊曾冤 遗 匝渊曾冤冤 寅 坌曾孕渊曾冤 遗 埚曾 匝渊曾冤圳劭 坌曾渊孕渊曾冤 遗 匝渊曾冤冤 遗 坌曾孕渊曾冤 遗 埚曾 匝渊曾冤渊圆 分冤圳埚曾劭 渊孕渊曾冤 遗 匝渊曾冤冤 遗 埚曾孕渊曾冤 遗 坌曾 匝渊曾冤圳埚曾渊劭 孕渊曾冤 夷 劭 匝渊曾冤冤 遗 匝渊曾冤冤 遗 坌曾 孕渊曾冤渊员 分冤圳埚曾渊劭 孕渊曾冤 遗 匝渊曾冤冤 遗 坌曾 孕渊曾冤渊员 分冤圳埚曾劭 孕渊曾冤 遗 埚曾匝渊曾冤 遗 坌曾 孕渊曾冤圳劭 坌曾 孕渊曾冤 遗 坌曾 孕渊曾冤 遗 埚曾匝渊
8、曾冤渊员 分冤圳员渊员 分冤所以 坌曾渊孕渊曾冤 遗 匝渊曾冤冤 寅 坌曾孕渊曾冤 遗 埚曾匝渊曾冤 是永真式渊员 分冤摇 摇 猿猿郾 证明院设图 郧 中度数为 噪 垣 员 的结点有 曾 个袁则曾 垣 灶噪越 灶 渊员冤渊圆 分冤由握手定理可得渊噪 垣 员冤曾 垣 噪灶噪越 圆皂 渊圆冤渊圆 分冤联立方程渊员冤 和渊圆冤袁即可得灶噪越 渊噪 垣 员冤灶 原 圆皂渊猿 分冤摇 离散数学试题答案及评分参考第 源 摇 摇 摇 摇 页渊共 缘 页冤五尧综合应用题院本大题共 圆 小题袁每小题 苑 分袁共 员源 分遥摇 摇 猿源郾 解院渊员冤 砸 越 喳 约 员袁员 跃 袁 约 员袁猿 跃 袁 约 猿袁员
9、 跃 袁 约 猿袁猿 跃 袁 约 员袁缘 跃 袁 约 缘袁员 跃 袁约 猿袁缘 跃 袁 约 缘袁猿 跃 袁 约 缘袁缘 跃 袁 约 圆袁圆 跃 袁 约 圆袁远 跃 袁 约 远袁圆 跃 袁 约 远袁远 跃 袁约 源袁源 跃 札渊猿 分冤渊圆冤 关系 砸 的关系图如下院答 猿源 图渊源 分冤摇 摇 猿缘郾 解院渊员冤 先画出 缘 个工厂的相互距离情况如答 猿缘 图 粤 所示答 猿缘 图 粤渊圆 分冤摇 离散数学试题答案及评分参考第 缘 摇 摇 摇 摇 页渊共 缘 页冤渊圆冤 根据 运则怎泽噪葬造 算法袁可得答 猿源 图 粤 的最小生成树 栽 如答 猿缘 图 月 所示答 猿缘 图 月此即最短的供电线路铺设方案遥渊源 分冤渊猿冤 可以算出答 猿缘 图 月 所示的线路长度为宰渊栽冤 越 源 垣 缘 垣 苑 垣 远 越 圆圆渊千米冤渊员 分冤