北邮离散数学期末复习题.doc

离散数学是计算机科学中的基础学科，主要研究离散而非连续的数据结构和概念。北邮离散数学期末复习题涉及到的主要知识点包括集合论、关系、等价关系和传递性等。 1. **集合论** - 空集：空集是任何集合的子集，但不是它的真子集。如果一个集合没有任何元素，我们称它为空集，记作`∅`。 - 集合的元素：集合中的元素可以是任何对象，例如数字、字符、字符串等。例如，集合`{a, b, c}`包含三个元素a、b和c。 - 子集与真子集：如果所有集合A的元素都是集合B的元素，那么A是B的子集；如果A是B的子集但A不等于B，那么A是B的真子集。 2. **关系** - 复合关系：两个关系的复合表示先执行第一个关系，然后执行第二个关系，不满足交换律，即`R;S ≠ S;R`。 - 传递性：如果对于所有的`a, b, c ∈ A`，若`a R b`且`b R c`，则`a R c`，这样的关系称为传递关系。 - 反对称性：如果对于所有`a, b ∈ A`，`a R b`蕴含`b R a`且`a = b`，则关系`R`是对称的。而反对称性是指`a R b`蕴含`b R a`且`a ≠ b`。 3. **等价关系** - 等价关系是自反的（每个元素与自身相关）、对称的（如果`a R b`，则`b R a`）和传递的（如前所述）。例如，整数集合上的“相等”关系就是一个等价关系。 - 等价类：在等价关系下，集合A可以被划分为若干个互不相交的子集，每个子集内的元素都与集合内的其他元素等价，这些子集称为等价类。 4. **集合操作** - 并集：集合A与集合B的所有元素组成的集合是它们的并集，记作`A ∪ B`。 - 差集：如果`A ∪ B = A`，则`B`是`A`的子集；如果`A ∩ B = ∅`，则`B`是`A`的补集的一部分。 5. **单项选择题涉及知识点** - 实数集合的子集定义：如题中所示，选项A是空集，因为没有满足条件的x值。 - 集合的补集：如果`A \ B`，这意味着`B`中所有元素都不在`A`中。 - 集合的元素和子集的性质：集合元素的运算和集合的子集性质是判断题和选择题中的常见考点。 通过以上分析，我们可以看出离散数学的复习涵盖了集合的基本性质、关系的性质以及等价关系的定义和性质。在复习时，要特别注意理解和掌握这些基本概念及其相互之间的联系，这对于理解更复杂的离散结构如图论、逻辑和算法分析至关重要。