离散数学必备知识点总结.doc

课程资料：离散数学科目，本科课程，计算机专业，软件专业，数学专业，离散数学期末考试复习资料，离散数学知识点总结，离散数学练习题模拟题，试题及答案，本科大学，必背知识点，必背考点，课后练习，期末考试试卷及答案。 ### 离散数学必备知识点总结 #### 一、命题逻辑 **1. 基本逻辑连接词：** - **蕴含（→）**: 当前件为真而后件为假时，整个蕴含式为假；其余情况下均为真。 - **等价（↔）**: 当两个命题具有相同的真值时为真；当两个命题真值不同时为假。 **2. 主析取范式与主合取范式：** - **主析取范式**: 所有极小项的析取（即“或”操作）。极小项是使得公式为真的最简单组合。 - **主合取范式**: 所有极大项的合取（即“与”操作）。极大项是使得公式为假的最简单组合。 - **求极小项**: 将命题变元中的真值用1表示，假值用0表示。 - **求极大项**: 与求极小项相反，真值用0表示，假值用1表示。 - **注意事项**: 每个变元及其否定在表达式中恰好出现一次，保持变元的顺序一致有助于避免错误。 **3. 求范式技巧：** - 使用真值表辅助计算，其中真值为1的行对应极小项，真值为0的行对应极大项。 - 对于n个变元，共有\(2^n\)个极小项和极大项。 **4. 特殊情况：** - 永真式没有主合取范式，因为不存在使其为假的情况。 - 永假式没有主析取范式，因为不存在使其为真的情况。 **5. 推理方法：** - **真值表法**: 直接通过真值表判断公式是否为永真式或永假式。 - **分析法**: 假设前件为真推出后件也为真，或假设前件为假推出后件也为假。 - **推理演算方法**: 包括P规则、T规则等，用于逻辑公式的推导。 #### 二、谓词逻辑 **1. 谓词类型：** - **一元谓词**: 描述单一对象的性质。 - **多元谓词**: 描述多个对象间的关系。 **2. 量词应用：** - **全称量词**: 通常与蕴含（→）一起使用。 - **存在量词**: 通常与合取（∧）一起使用。 - **量词顺序**: 当同时包含存在量词和全称量词时，一般先处理存在量词。 #### 三、集合 **1. 基础概念：** - **自然数集N**: 包含正整数{1, 2, 3, ...}，不包含0。 - **基**: 表示集合中不同元素的数量，记作|A|。 - **幂集P(A)**: 由集合A的所有子集构成的新集合。 **2. 集合运算：** - 若集合A有n个元素，则其幂集P(A)中有\(2^n\)个元素。 - **集合的分划**: - 由集合A的若干互不相交的子集组成，这些子集的并等于集合A本身。 - 分划与覆盖的区别在于分划要求每个元素只出现在一个子集中，而覆盖不要求这一点。 #### 四、关系 **1. 基础概念：** - **笛卡尔积A×B**的基数为\(mn\)，其中m和n分别是集合A和B的基数。 - **关系**: 从集合A到集合B的所有可能配对中选取一部分。 - **特殊关系**: - **全关系**具备自反性、对称性和传递性。 - **空关系**具备反自反性、反对称性和传递性。 - **全封闭环**具备自反性、对称性和反对称性。 **2. 闭包操作：** - **自反闭包**: \(r(R) = R \cup I\), 其中I为集合A上的恒等关系。 - **对称闭包**: \(s(R) = R \cup R^{-1}\)，其中\(R^{-1}\)为R的逆关系。 - **传递闭包**: \(t(R) = R \cup R^2 \cup R^3 \cup \ldots\) **3. 关系特性：** - **等价关系**: 需满足自反性、对称性和传递性。 - **偏序关系**: 需满足自反性、反对称性和传递性。 **4. 上界与下界：** - **上界**: 集合A中比集合B中所有元素都要大的元素。 - **下界**: 集合A中比集合B中所有元素都要小的元素。 - **上确界与下确界**: 分别是最小的上界和最大的下界，若存在则是唯一的。 #### 五、函数 **1. 函数定义：** - 从集合X到集合Y的不同关系数为\(m^n\)，不同函数数为\(m^n\)。 - 在含有n个元素的集合上，不同关系数为\(2^{2^n}\)，不同函数数为\(n^n\)。 **2. 特殊函数：** - **单射**: 若对任意两个不同元素\(x_1, x_2 \in X\)，有\(f(x_1) \neq f(x_2)\)。 - **满射**: 若对集合Y中的每一个元素\(y\)，至少存在一个\(x \in X\)使得\(f(x) = y\)。 - **双射**: 同时满足单射和满射条件。 **3. 函数合成：** - **复合函数**: \(f \circ g = g(f(x))\)，其中\(f\)和\(g\)是两个函数。 **4. 单射、满射与双射的复合：** - 如果\(f\)和\(g\)都是单射，则\(f \circ g\)也是单射。 - 如果\(f\)和\(g\)都是满射，则\(f \circ g\)也是满射。 - 如果\(f\)和\(g\)都是双射，则\(f \circ g\)也是双射。 #### 六、代数系统 **1. 二元运算：** - 二元运算是指将集合A的两个元素作为输入，并输出集合A中的一个元素的操作。 **2. 定义与性质：** - **封闭性**: 集合A关于某种运算\(∗\)封闭，意味着对于所有\(a, b \in A\)，都有\(a ∗ b \in A\)。 - **结合律**: 对于所有\(a, b, c \in A\)，有\((a ∗ b) ∗ c = a ∗ (b ∗ c)\)。 - **交换律**: 对于所有\(a, b \in A\)，有\(a ∗ b = b ∗ a\)。 - **单位元**: 存在元素e使得对于所有\(a \in A\)，有\(e ∗ a = a ∗ e = a\)。 - **逆元**: 对于每个\(a \in A\)，存在\(b \in A\)使得\(a ∗ b = b ∗ a = e\)。 通过以上总结，我们可以清晰地了解到离散数学中各个章节的核心知识点，这些内容不仅涵盖了基础概念，还深入探讨了各种重要性质和操作方法，对于学习离散数学的学生来说是非常有价值的参考资料。