华东师范大学离散数学作业答案.pdf

第一章 1 假定 A 是 ECNU二年级的学生集合 B 是 ECNU必须学离散数学的学生的集合 请用A 和 B 表示 ECNU不必学习离散数学的二年级的学生的集合 2 试求 1 P 2 P P 3 P P P 3 在 1 200 的正整数中 能被3 或 5 整除 但不能被15 整除的正整数共有多少个 能被 5 整除的有40 个 能被 15 整除的有13 个 能被 3 或 5 整除 但不能被15 整除的正整数共有 66 13 40 13 80个 第三章 1 下列语句是命题吗 1 2 是正数吗 2 x 2 x 1 0 3 我要上学 4 明年 2 月 1 日下雨 5 如果股票涨了 那么我就赚钱 2 请用自然语言表达命题 pr qr 其中 p q r 为如下命题 p 你得流感了 q 你错过了最后的考试 r 这门课你通过了 3 通过真值表求p p qp 的主析取范式和主合取范式 4 给出 p qs q prrs的形式证明 第四章 1 将x C x y C y F x y 翻译成汉语 其中C x 表示 x 有电脑 F x y 表示 x 和 y是同 班同学 个体域是学校全体学生的集合 解 学校的全体学生要么自己有电脑 要么其同班同学有电脑 2 构造x P x Q x x Q x R x xR x xP x 的形式证明 解 xR x 前提引入 R e US规则 x Q x R x 前提引入 Q e R e US规则 Q e 析取三段论 x P x Q x 前提引入 P e Q e US规则 P e 析取三段论 x P x EG规则 第五章 1 设 R S T 都是 X 上的关系 证明 R S T R S RT R S T R T ST 2 设 X 是所有人组成的集合 定义X 上的关系R1和 R2 aR1b 当且仅当a 比 b 高 aR2b 当且仅当a 和 b 有共同的祖父母 问关系R1和 R2是否是自反 反自反 对称 反对 称 传递的 3 设 R1和 R2是 X 上的关系 证明 t R1 R2 t R1 t R2 4 下列集合关于整除关系构成偏序集 请分别画出它们的哈斯图 判断它们是否是全 序集 给出它们的极大元 极小元 最大元 最小元 2 2 4 8 16 4 2 3 4 5 9 10 80 第六章 1 f XY 下列命题是否成立 1 f 是一对一的当且仅当对任意a bX 当 f a f b 时 必有a b 2 f 是一对一的当且仅当对任意a bX 当 f a f b 时 必有a b 2 下图展示了五个关系的关系图 问 这些关系中 哪些是函数 哪些是一对一的函数 哪些是到上的函数 哪些是一一对应 第七章 1 6 个学生 Alice Bob Carol Dean Santos和 tom 其中 Alice和 Carol不和 Dean 和 Carol不和 Santos Tom和 Alice 两两不和 请给出表示这种情形的图模型 2 设简单无向图G V E 若 G k k 1 则 G 有长度为k 的基本通路 解 证明 我们假设存在k 1 的基本通路 则存在k 个顶点 通路最后一个顶点与通路上顶点相连 的度数至多为k 1 因为 G k k 1 所以该顶点必定与其他顶点相连 那么存在长 度为 K 的基本通路 得证 3 一大学有 5 个专业委员会 物理 化学 数学 生物 计算机 6 位院士 B C D G S W 专业委员会由院士组成 物理委员会有院士 C S和 W 化学委员会有院 士 C D 和 W 数学委员会有院士 B C G 和 S 生物委员会有院士 B 和 G 计 算机委员会有院士 D 和 G 每个专业委员会每周开一小时例会 所有成员都不能缺席 如果某院士同时是两个专业委员会的成员 那么这两个专业委员会的例会就不能安排 在同一个时间 现要为这些例会安排时间 希望它们的时间尽可能集中 问最少需要 几个开会时间 请给出一种安排 第八章 1 说明下图不是哈密顿图 解 从图中删除所标记的6 个顶点 所得到的图由7 个孤立点组成 有7 个连通分量 所 以 该图不满足哈密顿图的必要条件 因而不是哈密顿图 2 证明连通图的割边一定是每棵生成树的边 证明 删除割边后的图一定不连通 其中不存在生成树 所以 每课生成树都包含割边 第九章 1 股评家推荐了12 个股票 一股民欲购买其中的3 个 问在下列各种条件下 分别有多 少种不同的投资方式 1 每个股票各投资3000 元 2 3 个股票分别投资5000 元 3000 元和1000 元 2 16 支互不同颜色的蜡笔平分给4 个孩子 有多少种不同的分法 解 C 16 4 C 12 4 C 8 4 C 4 4 3 某学校有2504 个计算机科学专业的学生 其中1876 人选修了C 语言 999 人选修了 Fortran 语言 345 人选修了JAVA 876 人选修了C 语言和 Fortran 语言 231 人选修 了 Fortran 和 JAVA 290 人选修了C 和 JAVA 189 个学生同时选了C Fortran 和 JAVA 问没有选这3 门程序设计语言课中的任何一门的学生有多少个 第十章 1 求初值问题的通项公式 an 10an 1 25an 2 a0 7 a1 15 解 特征方程 r2 10r 25 0 特征根 r2 r1 5 通解 an n 5 n 由a0 50 7和a1 7 51 15解得 7 10 初值问题的解 an 7 10n 2 n 2 计算广义二项式系数 3 5 和 1 2 3 的值 解 3 331351 21 5 5 1 2 1 2