离散数学学习体会.doc

1、 我的离散数学学习心得 (1) - 一类抽象代数题的解题思路学习离散数学已经有一段时间了，书读了不少，题也做了一些。最近又常在群里和研友们讨论离散数学中的问题。所以对离散数学也有了一些心得和体会。在今后的一段时间里，我会不定期的写一些小的经验总结，以供后来人参考。：）因为是“心得体会”，所以多半是想到什么写什么，组织和条理方面可能会比较差。还望各位看官多多包涵。；）这次我们来讨论一类代数问题的解题思路。问题：设 R 为含幺环，求证：对任意 a,bR，若 1-ab 可逆，则 1-ba 也可逆。分析：我们知道，证明问题的方法大致可以分为两类：构造性证明和存在性证明。前者要求给出一个切实的方法，找出

2、符合命题要求的元素（在这道题中，就是找到 1-ba 的逆元）。后者则只证明这样的元素必然存在，但并不给出切实的寻找方法。反证法是存在性证明的基本方法。无论打算采用是哪种证明方法，确认一下我们可以使用的前提条件总是必要的。就这道题而言，我们可以使用这些前提：1、R 是含幺环。这就意味着 R 对加法构成 Abel 群（从而我们可以自由地使用加法交换律、加法消去律、加法逆元等），R 对乘法构成独异点（从而可以使用乘法单位元 1），当然还有乘法对加法的分配律。2、1-ab 是可逆的，这就是说，存在 cR，使得 c(1-ab)=(1-ab)c=1。移项后得到：cab=abc=c-1。需要注意的是：1、在

3、题设中没有假设 R 的可换性（事实上，如果 R 可换的话，整个问题就没有任何难度了），也没有假设 a、b 是可逆的。所以，在解题时，不能使用乘法交换律，也不能随便使用 a、b 的逆元（除非已经证明了它们的存在性）。2、如果没有 1-ab 可逆这个条件，肯定是推不出 1-ba 可逆的（我们在环中可以找到太多的反例）。所以，cab=abc=c-1 将是解题的关键。观察这个式子，我们注意到，它提供了在 c 的参与下，移动和消去ab 的方法。我们的目的是，证明存在这样的一个元素 dR，满足(1-ba)d=d(1-ba)=1。初看到这道题，我们并不知道使用构造性证明容易还是使用反证法容易。不过推理一下我

4、们可以发现，如果要使用反证法的话，我们需要反设 1-ba 不存在乘法逆元，然后由此推出 1-ab 也不可能有逆元（或者推出 R 不是含幺环）。但反设 1-ba 不存在乘法逆元后，我们到底能推出哪些结论来呢？似乎很少。我们甚至连“对任意 xR，必有 x(1-ba)1”这样简单的情况都难以证明（因为我们只假设了 1-ba 没有“乘法逆元”，并不能由此推出 1-ba 没有“乘法左逆元”）。另一方面，利用等式 cab=abc=c-1 直接构造出一个 1-ba 的逆元应该一个比较有希望的方法。这时，我们可以“取巧”了。注意到：1、如果我们相信题目给的命题没有错的话，我们只要找到 1-ba 的左逆元（或者

5、右逆元）就基本完成任务了（虽然最终书写证明时，我们需要证明我们找到的元素既是左逆元又是右逆元）。因为如果一个元素的左右逆元都存在的话，它的左右逆元是唯一且相等的（所以，1-ba 确实可逆，而我们又找到了它的一个左逆元 x，那么这个 x 自然也是 1-ba 的右逆元）。2、不要指望证明 c 本身也是 1-ba 的逆元。因为假如是这样的话，(1-ab)和(1-bc)就都是 c 的逆元，由逆元的唯一性可知，1-ab=1-ba，利用消去律，我们可以得到 ab=ba。这就说，在这个环里，只要 1-ab有逆元，a 和 b 就是可换的。这个符合“含幺环 R”的一般情况吗？显然不符合。比如，由所有实矩阵对矩阵

6、加法和矩阵乘法组成的环，它是含幺环。但只要|a|b|1，1-ab 就可逆，但这样的矩阵都可换吗？显然不是的。这就说明，即使 1-ab 的逆元 c 存在，1-ba 的逆元（如果存在的话）也未必是 c。3、我们前面看到，在这道题中，c 的存在性是 1-ba 可逆的一个不可缺少的条件，但 c 本身并不一定就是 1-ba 的逆元（仅当 ab=ba 时，c 是 1-ba 的逆元）。那么，1-ba 的逆元应该是一个与 c 有某种关系的元素。根据这些线索，我们来寻找 1-ba 的乘法逆元（不妨先寻找左逆元）。前面已经提到，cab=abc=c-1 应该是解题的一个关键。那么，如果要使用它，就得用一个式子（不妨

7、记为 X）与(1-ba)相乘，使得它们的乘积中出现包含 cab 或者 abc 的项。因为 X(1-ba) = X - Xba。我们很容易看出，如果 X 中有以 ca 结尾的项（不妨记作 Yca），那么就可以得到 Ycaba 这样的项，而这个项可以换成 Yabca 或 Y(c-1)a。这些式子也许有助于我们消掉那些不需要的项。这样，我们不妨设 X = (Yca + Z)，其中 Y 和 Z 分别是两个式子（注意到，这样的假设是具有一般性的，任何含有以 ca 结尾的项的式子都能写成 Yca+Z 的样子）。看看这样乘出来的式子是什么样的：X(1-ba) = (Yca + Z)(1 - ba)= Yca

8、 + Z - Ycaba - Zba= Yca + Z - Y(c-1)a - Zba= Yca + Z - Yca + Ya - Zba= Z - Zba + Ya好了，现在我们得到一个当 X = (Yca + Z) 时，乘积的一般形式，如果能给 Y 和 Z 适当的值，使得Z - Zba + Ya = 1，那么相应的 X 就是我们要找的逆元了。我们发现，要想把 Zba 消掉，Ya 就应该也以 ba 结尾。看到这里，结果已经很明显了，令 Y=b，Z=1，则 Z - Zba + Ya = 1 - ba + ba = 1。这就是说，我们已经发现，当 X = (bca + 1) 时，X(1-ba)=

9、1。这样的 X 就是 1-ba 的左逆元了。证明 X 是右逆元的工作是简单的，和前面这段推导一样，只需利用等式 abc = c-1 就可以了。写在答题纸上的证明只不过是后面那小小的一段：(bca+1)(1-ba) = bca+1-bcaba-ba= bca+1-b(c-1)a-ba= bca+1-bca+ba-ba= 1(1-ba)(bca+1) = bca-babca+1-ba= bca-b(c-1)a+1-ba= bca-bca+ba+1-ba= 1而寻找 bca+1 的过程才是解题的关键。总结一下我们的思路：1、我们得到一些已知条件，需要找到一个未知的、满足某种特定条件的元素 d。2、整

10、理出我们可以使用的条件和不可以使用的条件（在抽象代数里要特别注意“不可以使用的条件”。因为抽象代数里常常使用以往算术运算中的符号，使人容易不自觉地使用一些在实数域上成立，但在其它代数系统上未必成立的性质和原理）。3、找到一些重要的等式，把它们变形为容易利用的形式（通常一边是一个单项，这样才方便在等式中代换）。4、写出待求元素的一般形式，考虑如何在其中利用我们在第 3 步找出的等式。5、根据推导的结果，确定待求元素的具体形式。6、证明结果的正确性。抽象代数中许多构造性证明都可以按这一思路进行。从这里也可以看出，虽然抽象代数中绝大多数题都是证明题，但在大多数情况下，观察、分析和试探仍然是解决问题的

11、关键所在。学习了一学期的离散数学，要说颇有成就、深有体会之类的话嘛，那还谈不上；要说是一点体会都没有，那也不可能。只是在这一年的离散数学的学习过程中，有一些个人体会想与大家分享。离散数学是一门计算机专业的基础课程，也是比较难学的一门课程。这门课程里有太多的概念需要记忆。那是不是要把所有的概念的定义都要完完整整地背下来呢？我认为大可不必。要想在一学期中的那么一点有限的时间里，背完所有的概念的定义是不太现实的，况且也没有那个必要！学理工科最重要的就是理解。只有真正理解了概念的内在涵义，才能真正掌握这个概念。理解了概念的内在涵义，就为学好这门课程打好了坚实的基础。在理解概念的基础上，再形成适合于离散

12、数学本身的思维模式。学习物理，要用物理思维模式；学习高等数学，要用高数的思维模式；学习线性代数，也要用线性代数式思维模式。所以学习任何一门课程，都要有适合于该课程的思维模式。当然离散数学也不例外，它也有自己独特的思考问题的方式。只有找到了，并理解了这种思维方式，才能为后继学习作好铺垫。最后最重要的就是要找到解决问题的方法。学习任何一门课程，都是为了解决实际问题。离散数学也是如此。有了对概念的理解，有了正确的思考问题的方式，在解决问题的时候就不会走弯路了，也就是说基本的解决问题的方法也就自然而然地掌握了。学习这门课的目的，我认为并不是说要学得如何的精通，因为这是不可能的，课时有限嘛。其真正的目的

13、就是要让你打好基础，为以后向更深、更广的方向发展垫定基础。有了以上三个方面的掌握，学习目的就可以达到了。以上这些仅是我个人的看法，仅供参考。如果有什么说的不确切的地方，还请指正！离 散 数 学 (Discrete mathematics)是 研 究 离 散 量 的 结 构 及 其 相 互 关 系 的 数 学 学 科 ， 是现 代 数 学 的 一 个 重 要 分 支 。 它 在 各 学 科 领 域 ， 特 别 在 计 算 机 科 学 与 技 术 领 域 有 着 广泛 的 应 用 ， 同 时 离 散 数 学 也 是 计 算 机 专 业 的 许 多 专 业 课 程 ， 如 程 序 设 计 语 言 、

14、 数 据结 构 、 操 作 系 统 、 编 译 技 术 、 人 工 智 能 、 数 据 库 、 算 法 设 计 与 分 析 、 理 论 计 算 机 科 学 基础 等 必 不 可 少 的 先 行 课 程 。 通 过 离 散 数 学 的 学 习 ， 不 但 可 以 掌 握 处 理 离 散 结 构 的 描述 工 具 和 方 法 ， 为 后 续 课 程 的 学 习 创 造 条 件 ， 而 且 可 以 提 高 抽 象 思 维 和 严 格 的 逻 辑 推 理能 力 ， 为 将 来 参 与 创 新 性 的 研 究 和 开 发 工 作 打 下 坚 实 的 基 础 。随 着 信 息 时 代 的 到 来 ， 工

15、业 革 命 时 代 以 微 积 分 为 代 表 的 连 续 数 学 占 主 流 的 地 位 已经 发 生 了 变 化 ， 离 散 数 学 的 重 要 性 逐 渐 被 人 们 认 识 。 离 散 数 学 课 程 所 传 授 的 思 想 和 方 法， 广 泛 地 体 现 在 计 算 机 科 学 技 术 及 相 关 专 业 的 诸 领 域 ， 从 科 学 计 算 到 信 息 处 理 ， 从 理 论计 算 机 科 学 到 计 算 机 应 用 技 术 ， 从 计 算 机 软 件 到 计 算 机 硬 件 ， 从 人 工 智 能 到 认 知 系 统 ，无 不 与 离 散 数 学 密 切 相 关 。由 于 数

16、 字 电 子 计 算 机 是 一 个 离 散 结 构 ， 它 只 能 处 理 离 散 的 或 离 散 化 了 的 数 量 关 系 ， 因 此 ， 无 论 计 算 机 科 学 本 身 ， 还 是 与 计 算 机 科 学 及 其 应 用 密 切 相 关 的 现 代 科 学 研 究 领 域， 都 面 临 着 如 何 对 离 散 结 构 建 立 相 应 的 数 学 模 型 ； 又 如 何 将 已 用 连 续 数 量 关 系 建 立 起 来的 数 学 模 型 离 散 化 ， 从 而 可 由 计 算 机 加 以 处 理 。离 散 数 学 是 传 统 的 逻 辑 学 ， 集 合 论 （ 包 括 函 数 ）

17、， 数 论 基 础 ， 算 法 设 计 ， 组 合 分 析 ，离 散 概 率 ， 关 系 理 论 ， 图 论 与 树 ， 抽 象 代 数 （ 包 括 代 数 系 统 ， 群 、 环 、 域 等 ） ， 布尔 代 数 ， 计 算 模 型 （ 语 言 与 自 动 机 ） 等 汇 集 起 来 的 一 门 综 合 学 科 。 离 散 数 学 的 应 用 遍及 现 代 科 学 技 术 的 诸 多 领 域 。离 散 数 学 课 程 主 要 介 绍 离 散 数 学 的 各 个 分 支 的 基 本 概 念 、 基 本 理 论 和 基 本 方 法 。 这些 概 念 、 理 论 以 及 方 法 大 量 地 应 用

18、 在 数 字 电 路 、 编 译 原 理 、 数 据 结 构 、 操 作 系 统 、数 据 库 系 统 、 算 法 的 分 析 与 设 计 、 人 工 智 能 、 计 算 机 网 络 等 专 业 课 程 中 ； 同 时 ， 该 课程 所 提 供 的 训 练 十 分 有 益 于 学 生 概 括 抽 象 能 力 、 逻 辑 思 维 能 力 、 归 纳 构 造 能 力 的 提 高 ，十 分 有 益 于 学 生 严 谨 、 完 整 、 规 范 的 科 学 态 度 的 培 养 。离 散 数 学 课 程 的 教 学 目 的 ， 不 但 作 为 计 算 机 科 学 与 技 术 及 相 关 专 业 的 理 论

19、 基 础 及 核心 主 干 课 ， 对 后 续 课 程 提 供 必 需 的 理 论 支 持 。 更 重 要 的 是 旨 在 “通 过 加 强 数 学 推 理 ，组 合 分 析 ， 离 散 结 构 ， 算 法 构 思 与 设 计 ， 构 建 模 型 等 方 面 专 门 与 反 复 的 研 究 、 训 练 及 应用 ， 培 养 提 高 学 生 的 数 学 思 维 能 力 和 对 实 际 问 题 的 求 解 能 力 。 ”离 散 数 学 通 常 研 究 的 领 域 包 括 ： 数 理 逻 辑 、 集 合 论 、 代 数 结 构 、 关 系 论 、 函 数 论、 图 论 、 组 合 学 、 数 论 等

20、 。 它 是 高 校 计 算 机 及 相 关 专 业 的 重 要 基 础 课 程 之 一 。课 程 内 容 涉 及 ：1 集 合 论 部 分 ： 集 合 及 其 运 算 、 二 元 关 系 与 函 数 、 自 然 数 及 自 然 数 集 、 集 合 的 基数2 图 论 部 分 ： 图 的 基 本 概 念 、 欧 拉 图 与 哈 密 顿 图 、 树 、 图 的 矩 阵 表 示 、 平 面 图、 图 着 色 、 支 配 集 、 覆 盖 集 、 独 立 集 与 匹 配 、 带 权 图 及 其 应 用3 代 数 结 构 部 分 ： 代 数 系 统 的 基 本 概 念 、 半 群 与 独 异 点 、 群

21、 、 环 与 域 、 格 与 布尔 代 数4 组 合 数 学 部 分 ： 组 合 存 在 性 定 理 、 基 本 的 计 数 公 式 、 组 合 计 数 方 法 、 组 合 计数 定 理5 数 理 逻 辑 部 分 ： 命 题 逻 辑 、 一 阶 谓 词 演 算 、 消 解 原 理离 散 数 学 被 分 成 三 门 课 程 进 行 教 学 ， 即 集 合 论 与 图 论 、 代 数 结 构 与 组 合 数 学 、 数 理逻 辑 。 编 辑 本 段 Discrete Mathematics and Its Applications 此 书 的 价 值 已 经 被 全 世 界 几 百 所 大学 所

22、证 实 ,作 为 离 散 数 学 领 域 的 经 典 教 材 ,全 世 界 几 乎 所 有 知 名 的 院 校 都 曾 经 使 用 本 书作 为 教 材 .以 我 个 人 观 点 看 来 ,这 本 书 可 以 称 之 为 离 散 数 学 百 科 .书 中 不 但 介 绍 了 离 散 数学 的 理 论 和 方 法 ,还 有 丰 富 的 历 史 资 料 和 相 关 学 习 网 站 资 源 .更 为 令 人 激 动 的 便 是 这 本书 少 有 的 将 离 散 数 学 理 论 与 应 用 结 合 得 如 此 的 好 .你 可 以 看 到 离 散 数 学 理 论 在 逻 辑 电 路 ,程序 设 计 ,

23、商 业 和 互 联 网 等 诸 多 领 域 的 应 用 实 例 .本 书 的 英 文 版 (第 六 版 )当 中 更 增 添 了 相当 多 的 数 学 和 计 算 机 科 学 家 的 传 记 ,是 计 算 机 科 学 历 史 不 可 多 得 的 参 考 资 料 .作 为 教 材这 本 书 配 有 相 当 数 量 的 练 习 .每 一 章 后 面 还 有 一 组 课 题 ,把 学 生 已 经 学 到 的 计 算 和 离 散数 学 的 内 容 结 合 在 一 起 进 行 训 练 .这 本 书 也 是 我 个 人 在 学 习 离 散 数 学 时 读 的 唯 一 的 英 文教 材 ,实 为 一 本 值

24、 得 推 荐 的 好 书 。 编 辑 本 段 内 容 简 介离 散 数 学 和 微 积 分 不 同 ， 离 散 数 学 是 以 离 散 对 象 为 研 究 对 象 的 ， 是 计 算 机 专 业 和 其他 一 些 工 程 专 业 的 数 学 基 础 。 本 书 包 含 了 数 理 逻 辑 、 集 合 论 、 数 函 数 和 递 推 关 系 、 图 论、 代 数 系 统 及 布 尔 代 数 等 主 要 内 容 。 本 书 注 重 理 论 的 系 统 性 和 准 确 性 ， 特 别 重 视 对 理 论难 点 的 诠 释 ， 叙 述 通 俗 易 读 。本 书 适 合 作 为 高 等 学 校 计 算

25、机 专 业 或 其 他 工 程 类 专 业 教 材 使 用 ， 也 可 以 供 对 离 散 数学 有 兴 趣 的 读 者 自 学 。内 容 简 介 离 散 数 学 作 为 一 个 单 独 的 分 枝 ， 在 世 界 上 出 现 的 时 间 并 不 久 ， 不 过 几 十 年 ，但 它 的 各 部 分 内 容 中 有 相 当 一 部 分 却 早 已 出 现 在 数 学 中 。 为 什 么 将 各 个 数 学 分 支 中 的 一些 内 容 集 中 起 来 加 以 研 究 ， 并 且 冠 上 一 个 新 的 名 称 离 散 数 学 呢 ？ 这 主 要 是 因 为 计算 机 科 学 的 产 生 和 发

26、 展 。 正 如 恩 格 斯 所 说 ： “科 学 的 状 况 还 更 多 的 从 属 于 技 术 的 状况 和 需 要 。 倘 若 社 会 上 有 了 一 种 技 术 上 的 需 要 ， 那 就 比 十 个 大 学 还 更 能 推 动 科 学 前 进 。” 计 算 机 的 出 现 ， 在 很 大 程 度 上 影 响 到 了 人 们 的 思 想 和 生 活 ， 对 社 会 生 产 起 了 重 大 作用 。 为 了 研 究 计 算 机 科 学 的 理 论 基 础 ， 离 散 数 学 也 就 应 运 而 生 。 因 此 ， 如 果 我 们 不 从 纯数 学 的 角 度 ， 而 从 应 用 数 学

27、的 角 度 来 考 虑 ， 也 许 给 离 散 数 学 换 一 个 名 称 一 一 计 算 机 科学 的 数 学 基 础 更 能 说 明 问 题 。正 是 因 为 这 个 原 因 ， 在 计 算 机 科 学 系 。 信 息 管 理 系 都 将 离 散 数 学 作 为 必 须 学 习 的 基础 课 程 。 而 实 践 证 明 这 种 做 法 是 正 确 的 。 编 辑 本 段 如何学好离散数学离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。离散数学以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数个元素，因此他充分描述了计算机科学离散性的特点。由于离散

28、数学在计算机科学中的重要性，因此，许多大学都把它作为研究生入学考试的专业课程中的一门，或者是一门中的一部分。作为计算机系的一门课程，离散数学有与其它课程相通相似的部分，当然也有它自身的特点，现在我们就它作为考试内容时具有的特点作一个简要的分析。1、定义和定理多。离散数学是建立在大量定义上面的逻辑推理学科。因而对概念的理解是我们学习这门学科的核心。在这些概念的基础上，特别要注意概念之间的联系，而描述这些联系的实体则是大量的定理和性质。在考试中的一部分内容就是考察大家对定义和定理的识记、理解和运用。如 2002 年上海交通大学的试题，问什么是相容关系。如果知道的话，很容易得分；如果不清楚，那么无论

29、如何也得不到分数的。这类型题目往往因其难度低而在复习中被忽视。实际上这是一种相当错误的认识，在研究生入学考试的专业课试题中，经常出现直接考查对某知识点的识记的题目。对于这种题目，考生应该能够准确、全面、完整地再现此知识点。任何的模糊和遗漏，都会造成极为可惜的失分。我们建议读者，在复习的时候，对重要知识的记忆，务必以上面提到的“准确、全面、完整 ”为标准来要求自己，不能达到，就说明还不过关，还要下工夫。关于这一点，在后续章节中我们仍然会强调，使之贯穿于整个离散数学的复习过程中。离散数学的定义主要分布在集合论的关系和函数部分，还有代数系统的群、环、域、格和布尔代数中。一定要很好地识记和理解。2、方

30、法性强。离散数学的证明题中，方法性是非常强的，如果知道一道题用怎样的方法证明，很轻易就可以证出来，反之则事倍功半。所以在平常复习中，要善于总结，那么遇到比较陌生的题也可以游刃有余了。在本书中，我们为读者总结了不少解题方法。读者首先应该熟悉并且会用这些方法。同时我们还鼓励读者勤于思考，对于一道题，尽可能地多探讨几种解法。3、有穷性。由于离散数学较为“呆板”，出新题比较困难，不管什么考试，许多题目是陈题，或者稍作变化的来的。“熟读唐诗三百首，不会做诗也会吟。 ”如果拿到一本习题集，从头到尾做过，甚至背会的话。那么，在考场上就会发现绝大多数题见过或似曾相识。这时，要取得较好的成绩也就不是太难的事情了

31、。本书是专门针对研究生入学考试而编写的，适合于读者对研究生入学考试的复习。如果还有时间的话，我们可以推荐两本习题集。一本是左孝凌老师等编写的离散数学理论、分析、题解，另一套有三本，是耿素云老师等编写的离散数学习题集。这两套书大多数题都是相同的，只是由于某些符号和定义的不同，使得题目的设定和解法有些不同而已。现在我们就分析一下研究生入学考试有哪些题型，以及我们应如何应付。1、基础题基础题就是考察对定义的识记，以及简单的证明和推理。题目主要集中在数理逻辑部分和集合论部分。这些题目不需要思考，很容易上手。这一部分的题目主要问题是要防止粗心大意和对定义记忆似是而非而丢的分数。不重视这一点的人将会在考试

32、中吃大亏。如在主合取范式中，极大项编码对应的指派与真值表对应的指派相反，这一点在许多的参考书里也会犯错误；还有是要防止没有按照一定的方法而引起的错误，如我们在数理逻辑或者集合论里作等价推演，可以省略若干不重要的步骤，只要老师和考生都清楚就可以了，而在推理理论里则不能省略任何步骤，否则被认为是逻辑错误。我们在学习中，还要注意融会贯通，例如，数理逻辑和集合论是相通的，因此记忆或者总结方法的时候可以综合起来，这样便于比较和理解。2、定理应用题本部分是最“死”的一部分，它主要体现了离散数学的方法性强的特点。并且这一部分占了考试内容的大部分，我们必须在这一部分下功夫，记住了各种方法，也就拿到了离散数学的

33、大部分分数。下面我们就列出常用的几种应用：证明等价关系：即要证明关系有自反、对称、传递的性质。证明偏序关系：即要证明关系有自反、反对称、传递的性质。（特殊关系的证明就列出来两种，要证明剩下的几种只需要结合定义来进行）。X，使得 f(x)=y。Y，都有 xY，即要证明对于任意的 y证明满射：函数 f：XX，且 x1x2，则 f(x1) f(x2)；或者对于任意的 f(x1)=f(x2)，则有 x1=x2。 Y，即要证明对于任意的 x1、x2 证明入射：函数 f：X证明集合等势：即证明两个集合中存在双射。有三种情况：第一、证明两个具体的集合等势，用构造法，或者直接构造一个双射，或者构造两个集合相互

34、间的入射；第二、已知某个集合的基数，如果为，就设它和 R 之间存在双射 f，然后通过 f 的性质推出另外的双射，因此等势；如果为0 ，则设和 N 之间存在双射；第三、已知两个集合等势，然后再证明另外的两个集合等势，这时，先设已知的两个集合存在双射，然后根据剩下题设条件证明要证的两个集合存在双射。证明群：即要证明代数系统封闭、可结合、有幺元和逆元。（同样，这一部分能够作为证明题的概念更多，要结合定义把它们全部搞透彻）。证明子群：虽然子群的证明定理有两个，但如果考证明子群的话，通常是第二个定理，即设S,则 是群，S 是 G 的非空子集，如果对于 S 中的任意元素 a 和 b 有 a*b-1是的子群

35、。对于有限子群，则可考虑第一个定理。证明正规子群：若H。这是最常见的题目中所使用的方法。H，有 a-1 *h*aG，有 aH=Ha，或者对于任意的 h是一个子群，H 是 G 的一个子集，即要证明对于任意的 a证明格和子格：子格没有条件，因此和证明格一样，证明集合中任意两个元素的最大元和最小元都在集合中。图论虽然方法性没有前几部分的强，但是也有一定的方法，如最长路径法、构造法等等。3、难题难题就是考试中比较难以下手，大多考生作不出来，用来拉开分数档次的题。那么，遇到难题我们怎么下手分析呢？难题主要有以下四种，我们来逐一进行分析：综合题综合题就是内容涵盖若干章的问题，这样的题大多数是在群论里面的陪

36、集、拉格朗日定理、正规子群、商群这一部分中。这一部分结合的内容很多，而且既复杂又难理解，是整个离散数学中的难点。首先拉格朗日定理把群和等价关系、划分结合在一起，又与群的阶数相挂钩（在子群中有一部分阶方面的题是比较难的题，它的解法依据就在此处）；然后商群将两个群结合在一起，因为两个群的元素是不同的，因此必须时刻概念清楚才不至于混乱；接着同余关系把群和关系相结合，定义了一种新的关系；自然同态把正规子群和商群相联系，也成为某些证明题的着眼处；核的定义和群同态定理给出了正规子群的另一种证明方法，因为核就是正规子群当然，综合题不仅此一处，离散数学是一个融会贯通的学科，像集合论，图论等都可能成为综合题的命

37、题点。对于综合题，我们可以从两方面下手，首先不管题设如何，看所要证明的问题，按照定理应用的题型着眼，设出所需要的格式，然后进行进一步推演；其次可以先看题设，应用已知条件的性质定理向前推几步，看看哪一个性质更能够接近所问，题目也就迎刃而解了。例外题例外题有两个含义，首先是对于定理应用题而言的，对于一个概念的判定定理和性质定理不是唯一的，而定理应用题是给出的是最常出题的定理，因此有的考题可能考出一个不常用的定理。其次例外题还有一种题型是与我们平常思维相悖的问题，如：有一些题目给出一个结论，说如果它正确的话请指出来，错误的话则请证明，凭做题经验通常是要选择证明的那条思路。其实也不妨用一些时间看看能不

38、能指出来，从而不用证明。请看下面的例子： 偏题常常有的参考书会说某某章是非重点，不会考到之类的话，这是非常错误和有害的。其结果是令这些章成为读者复习中的盲点，成为难题的又一种。这些章通常概念少，定理不多，因此题目本身不难。但由于没有好好复习或者根本没有复习，考试中又出了题目，故此拿不到分数则是非常令人懊丧的。所以我们建议读者进行全面复习，除非是所报考院校明确说明不考的部分，其余内容一律要认真复习。即使是复习时间比较少，也必须做到至少是了解了基本概念和定义。对于离散数学而言，函数一章中的基数部分和格和布尔代数一章是人们容易忽略的问题。我们平时复习的时候，不管是什么课程，一定不能留死角，而这些地方

39、出的题目由于它的本身内容的局限性，又往往是非常简单的。丢了十分可惜。 错题专业课的题目是由较少老师出的，并不像基础课那样经过多方面的论证，因此出错题也不奇怪（虽然非常非常之少），如果我们遇到了一道题目，经过我们判断和推演得到相悖的答案，不要过分迷信题目的权威性，因为它可能是错题。下面讲一下离散证明题的证明方法：1、直接证明法直接证明法是最常见的一种证明的方法，它通常用作证明某一类东西具有相同的性质，或者符合某一些性质必定是某一类东西。直接证明法有两种思路，第一种是从已知的条件来推出结论，即看到条件的时候，并不知道它怎么可以推出结论，则可以先从已知条件按照定理推出一些中间的条件（这一步可能是没有

40、目的的，要看看从已知的条件中能够推出些什么），接着，选择可以推出结论的那个条件继续往下推演；另外一种是从结论反推回条件，即看到结论的时候，首先要反推一下，看看从哪些条件可以得出这个结论（这一步也可能是没有目的的，因为并不知道要用到哪个条件），以此类推一直到已知的条件。通常这两种思路是同时进行的。2、反证法反证法是证明那些“存在某一个例子或性质 ”，“不具有某一种的性质”，“ 仅存在唯一”等的题目。它的方法是首先假设出所求命题的否命题，接着根据这个否命题和已知条件进行推演，直至推出与已知条件或定理相矛盾，则认为假设是不成立的，因此，命题得证。3、构造法证明“存在某一个例子或性质” 的题目，我们可

41、以用反证法，假设不存在这样的例子和性质，然后推出矛盾，也可以直接构造出这么一个例子就可以了。这就是构造法，通常这样的题目在图论中多见。值得注意的是，有一些题目其实也是本类型的题目，只不过比较隐蔽罢了，像证明两个集合等势，实际上就是证明“两个集合中存在一个双射” ，我们即可以假设不存在，用反证法，也可以直接构造出这个双射。4、数学归纳法数学归纳法是证明与自然数有关的题目，而且这一类型的题目可以递推。作这一类型题目的时候，要注意一点就是所要归纳内容的选择。经过了一年的离散数学学习，自己对离散数学这门学科或多或少也有了一些感受，今天便和大家一起分享一下。离散数学是计算机专业必修的一门课程，在学习这门

42、课程之前，只能感到这是一门很不一般的学科。现在细细想来，其实里面充满了无限的奥秘 数理逻辑作为离散数学的第一部分，充满着对逻辑思维的挑战，同时锻炼了我们思考问题的严密性，当然最重要的是学会如何用数学方法去分析逻辑问题。集合论是一个离散数学中第一个抽象难关，在老师的生动讲解下，深入浅出，使得集合论成了相当有趣的知识。只是对于以后的应用还不是很了解，感觉学好它很重要。代数结构可以说是集合论知识的延续和发展，其中概念的知识很多，还好都是循序渐进的，只要完成了老师的作业，基本上可以理解其意思。图论是作为我们计算机专业的一门很有用处的知识，也是新兴的一个数学分支，在计算机迅速发展的同时，图论也迅速发展。因此，图论给我们以一种神奇的感觉，在学习图论中，老师总是把图论分析得很透彻，学起来很有趣，同时也很简单。图论在数据结构方面的应用极其广泛，对我们学计算机专业的人来说，是一门必须要学好的知识。总的来说，一个学期下来，自认为较好地掌握了离散数学的知识，并在平时的编程及其他方面得到了很好的应用。