CPT107 离散数学 期末复习笔记配套例题

一边复习一边梳理的东西，挺细挺全，还有本人一些碎碎念无视就好w 可以搜笔记知识点对应的目录号来找例题，，， 说实话我以为自己复习的很无敌了但是，，，考试时间大家要安排好，适当做出取舍啥的，，，我就因为有些地方写太细了最后有一点没写完血亏了，，，大家一定要注意时间分配，，，一定，，， 以及还整理了配套的笔记，可以在主页看，，， 然后因为西浦万年不课改的习惯我觉得应该可以帮到后面学的人，希望这份笔记能够帮助到大家，，，以及机构啥的不要商用，，， 有啥想问的直接私信戳我w 离散数学是计算机科学中的基础课程，主要研究离散而非连续的对象。本复习笔记涵盖了三个主要部分：证明技巧、集合论和关系理论。 **一、证明技巧** 在离散数学中，证明是至关重要的，尤其是反证法。反证法是一种假设原命题的否定为真，然后推导出矛盾来证明原命题的正确性的方法。例如，证明根号2不是有理数，就是通过假设它是有理数，即存在两个整数x和y使得x/y=√2，进一步推导出矛盾，从而证明原命题。 **1. 反证法举例** - **Example 1**: 证明√2不是有理数。 - **Example 2**: 先假设一个命题的逆否命题为真，如果能证明其正确，则原命题成立；若不能，提供反例。 **二、集合论** 集合论是离散数学的基础，它涉及到集合的基本性质和运算。 **2. 集合论举例** - **Example 1**: 证明A∆B = (A ∪ B)∩ ∼ (A ∩ B)，这里A∆B表示差集，即属于A或B但不属于两者同时的元素集合。 - **Example 2**: 证明两个集合相等，这通常需要展示它们的元素完全相同。 **三、关系理论** 关系理论研究对象间的关联性，包括对称性、传递性和等价关系。 **3. 关系理论举例** - **Example 1,2**: 给出符合特定属性的关系实例，如对称关系或传递关系。 - **Example 3**: 证明关系是否对称，需要展示如果(x, y)属于关系，那么(y, x)也必须属于。 - **4.2.3 Transitive Closure**: 求关系的传递闭包，找到所有可以通过有限次传递步骤到达的元素对。 - **4.3 Equivalence Relations**: 等价关系需满足自反性、对称性和传递性，证明一个关系是等价关系，需要分别验证这三个属性。 - **4.4.2 Partial Order**: 偏序关系是反射性、反对称性和传递性的结合，证明一个关系是偏序关系也是基于这三个属性。 复习离散数学时，应注重理解每个概念，并通过大量的例题练习来巩固。在实际考试中，合理的时间分配至关重要，避免因过分详细而无法完成全部题目。此外，笔记的整理和分享可以促进知识的传承，帮助更多的学习者。记住，对于任何疑问，可以直接私信提问。