=================================== 离散数学 =================================== 0. 要点汇总 ==================== 本篇文章的要点整理如下 - 集合：明确可区分的对象的汇集，是现代数学的基石 - 子集：如果一个集合的所有元素都属于另一个集合，则称前者为后者的子集 - 幂集：给定集合的所有子集构成的集合 - 集合运算：并集、交集、差集、补集等基本操作 - 映射：两个集合之间元素的对应关系，包括单射、满射、双射 - 等价关系：满足自反性、对称性、传递性的二元关系 - 偏序关系：满足自反性、反对称性、传递性的二元关系 - 图：由顶点和边组成的数学结构，用于描述对象之间的关系 - 树：无环连通图，是数据结构的基础 - 欧拉图：经过所有边一次且仅一次的路径 - 哈密顿图：经过所有顶点一次且仅一次的路径 - 平面图：可以在平面上绘制且边不交叉的图 - 命题：能够判断真假的陈述句 - 联结词：否定(:math:`\neg`)、合取(:math:`\land`)、析取(:math:`\lor`)、蕴含(:math:`\to`)、等价(:math:`\leftrightarrow`) - 推理规则：假言推理、拒取式、假言三段论等 - 谓词：带有变量的命题，描述对象的性质或关系 - 量词：全称量词(:math:`\forall`)和存在量词(:math:`\exists`) - 排列：从n个不同元素中取出m个元素进行有序排列 - 组合：从n个不同元素中取出m个元素进行无序选择 - 二项式定理：:math:`(a+b)^n = \sum_{k=0}^{n} C(n,k)a^{n-k}b^k` - 鸽巢原理：如果n+1个物品放入n个盒子，则至少有一个盒子包含两个或更多物品 - 容斥原理：计算多个集合并集元素个数的基本方法 1. 集合论 =================================== 1.1 集合的基本概念 --------------------- **集合的定义** 集合是现代数学最基本的概念之一。直观地说，集合是一些确定的、不同的对象的整体，这些对象称为集合的元素。通常用大写字母（如A、B、C）表示集合，用小写字母（如a、b、c）表示元素。 **集合的表示方法** - **列举法**：将集合的所有元素一一列举出来，用花括号括起来。例如：A = {1, 2, 3, 4, 5} - **描述法**：通过描述元素所具有的共同性质来表示集合。例如：B = {x | x是偶数，x < 10} - **递归定义法**：通过递归的方式定义集合 **子集与幂集** 如果集合A的所有元素都属于集合B，则称A是B的子集，记作 :math:`A \subseteq B` 。如果 :math:`A \subseteq B` 且 :math:`A \neq B` ，则称A是B的真子集，记作 :math:`A \subset B` 。 幂集P(A)是指集合A的所有子集构成的集合。如果A有n个元素，那么P(A)有 :math:`2^n` 个元素。 例如： :math:`A = \{1, 2\}` ，则 :math:`P(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}` **集合的运算** - **并集**： :math:`A \cup B = \{x \mid x \in A \text{ 或 } x \in B\}` - **交集**： :math:`A \cap B = \{x \mid x \in A \text{ 且 } x \in B\}` - **差集**： :math:`A - B = \{x \mid x \in A \text{ 且 } x \notin B\}` - **补集**：A的补集记作 :math:`\bar A` ，或 :math:`A` ，指全集U中不属于A的所有元素构成的集合 1.2 关系与映射 --------------------- **关系的定义** 设A和B是两个集合，A与B的笛卡尔积 :math:`A \times B = \{(a,b) \mid a \in A, b \in B\}` 的任意子集称为从A到B的一个二元关系。 如果R是从A到B的关系，且 :math:`(a,b) \in R` ，则称a与b有关系R，记作aRb。 **关系的性质** - **自反性**：对于所有 :math:`a \in A` ，都有aRa - **对称性**：如果aRb，则bRa - **传递性**：如果aRb且bRc，则aRc - **反对称性**：如果aRb且bRa，则 :math:`a = b` **等价关系** 满足自反性、对称性和传递性的关系称为等价关系。等价关系可以将集合划分为若干个等价类。 例如：整数集上的模运算关系 a ≡ b (mod n) 是一个等价关系。 **偏序关系** 满足自反性、反对称性和传递性的关系称为偏序关系。带有偏序关系的集合称为偏序集。 例如：实数集上的"小于等于"关系( :math:`\leq` )是一个偏序关系。 **映射（函数）** 设A和B是两个集合，f是从A到B的关系。如果对于A中的每个元素a，都有唯一的 :math:`b \in B` 使得 :math:`(a,b) \in f` ，则称f是从A到B的映射，记作 :math:`f: A \to B` 。 - **单射（一对一）**：不同的元素映射到不同的元素 - **满射（映上）**：B中的每个元素都有原像 - **双射（一一对应）**：既是单射又是满射 2. 图论 =================================== 2.1 图的基本概念 --------------------- **图的定义** 图 :math:`G = (V, E)` 由顶点集V和边集E组成，其中E是V中元素对的多重集。如果边是有序的 :math:`(v_1, v_2)` ，则称图为有向图；如果边是无序的 :math:`\{v_1, v_2\}` ，则称图为无向图。 **图的分类** - **简单图**：没有自环和重边的图 - **多重图**：允许有重边但无自环的图 - **伪图**：允许有自环和重边的图 - **完全图**：每对顶点之间都有边的图 - **二部图**：顶点集可以分割成两个不相交的子集，所有边都连接这两个子集中的顶点 **度数** 对于无向图，顶点v的度数d(v)是与v关联的边的条数。对于有向图，顶点v的入度 :math:`d^-(v)` 是指向v的边的条数，出度 :math:`d^+(v)` 是从v出发的边的条数。 **握手定理** 在任何无向图中，所有顶点的度数之和等于边数的2倍： :math:`\sum_{v \in V} d(v) = 2|E|` 2.2 图的连通性 --------------------- **路径与回路** - **路径**：顶点序列 :math:`v_0, v_1, \ldots, v_k` ，其中相邻顶点之间有边 - **回路**：起点和终点相同的路径 - **简单路径**：顶点不重复的路径 - **简单回路**：除起点和终点外，顶点不重复的回路 **连通图** 如果无向图中任意两个顶点之间都存在路径，则称该图为连通图。有向图的连通性分为强连通和弱连通。 **连通分量** 图的极大连通子图称为连通分量。一个连通图只有一个连通分量。 2.3 特殊图 --------------------- **树** 连通且无回路的无向图称为树。树有以下重要性质： - n个顶点的树有n-1条边 - 树中任意两个顶点之间有且仅有一条路径 - 在树中任意添加一条边都会产生唯一的回路 **欧拉图** - **欧拉路径**：经过图中所有边一次且仅一次的路径 - **欧拉回路**：起点和终点相同的欧拉路径 - **欧拉图**：存在欧拉回路的图 欧拉图判定定理：连通无向图G是欧拉图当且仅当G中每个顶点的度数都是偶数。 **哈密顿图** - **哈密顿路径**：经过图中所有顶点一次且仅一次的路径 - **哈密顿回路**：起点和终点相同的哈密顿路径 - **哈密顿图**：存在哈密顿回路的图 哈密顿图没有简单的充要条件，但有一些充分条件和必要条件。 **平面图** 可以在平面上绘制且边不交叉的图称为平面图。 欧拉公式：对于连通平面图，V - E + F = 2，其中V是顶点数，E是边数，F是面数。 3. 数理逻辑 =================================== 3.1 命题逻辑 --------------------- **命题** 命题是能够判断真假的陈述句。命题的真值只有两种：真(True, T)和假(False, F)。 例如："2+2=4"是真命题，"今天下雨"是命题（其真值取决于实际情况），"x > 5"不是命题（因为无法确定其真假）。 **命题联结词** - **否定(¬)**：¬P为真当且仅当P为假 - **合取(∧)**：P ∧ Q为真当且仅当P和Q都为真 - **析取(∨)**：P ∨ Q为假当且仅当P和Q都为假 - **蕴含(→)**：P → Q为假当且仅当P为真而Q为假 - **等价(↔)**：P ↔ Q为真当且仅当P和Q的真值相同 **真值表** 真值表是列出命题公式在所有可能真值组合下结果的表格。 例如： :math:`P \to Q` 的真值表 .. math:: \begin{array}{c|c|c} P & Q & P \to Q \\ \hline T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \end{array} **等价公式** 两个命题公式A和B称为逻辑等价，记作 :math:`A \Leftrightarrow B` ，如果它们的真值表完全相同。 重要等价公式： - 双重否定律： :math:`\neg(\neg P) \Leftrightarrow P` - 德摩根律： :math:`\neg(P \land Q) \Leftrightarrow \neg P \lor \neg Q` ， :math:`\neg(P \lor Q) \Leftrightarrow \neg P \land \neg Q` - 分配律： :math:`P \land (Q \lor R) \Leftrightarrow (P \land Q) \lor (P \land R)` - 吸收律： :math:`P \lor (P \land Q) \Leftrightarrow P` ， :math:`P \land (P \lor Q) \Leftrightarrow P` **推理规则** - **假言推理**：从P和 :math:`P \to Q`，可以推出Q - **拒取式**：从 :math:`\neg Q`和 :math:`P \to Q`，可以推出 :math:`\neg P` - **假言三段论**：从 :math:`P \to Q`和 :math:`Q \to R`，可以推出 :math:`P \to R` - **析取三段论**：从 :math:`P \lor Q`和 :math:`\neg P`，可以推出Q **重言式与矛盾式** - **重言式（永真式）**：无论命题变元取何值，真值永远为真的命题公式 - **矛盾式（永假式）**：无论命题变元取何值，真值永远为假的命题公式 - **可满足式**：至少存在一种赋值使其为真的命题公式 例如： :math:`P \lor \neg P` 是重言式， :math:`P \land \neg P` 是矛盾式。 **范式** - **析取范式（DNF）**：由析取联结的合取式的形式 - **合取范式（CNF）**：由合取联结的析取式的形式 每个命题公式都可以转化为与之等价的范式。范式在逻辑推理和计算机科学中有重要应用。 **命题逻辑的应用** 命题逻辑在计算机科学中有广泛应用： - **电路设计**：逻辑门的工作原理基于命题联结词 - **程序验证**：程序正确性的形式化验证 - **人工智能**：知识表示和推理 - **数据库查询**：布尔查询的实现 3.2 谓词逻辑 --------------------- **谓词** 谓词是带有变量的命题，用来描述对象的性质或对象之间的关系。谓词通常用大写字母表示，变量用小写字母表示。 例如：P(x)表示"x是素数"，Q(x, y)表示"x < y" **量词** - **全称量词(∀)**："对于所有的"， :math:`\forall x P(x)` 表示 "对于所有x，P(x)成立" - **存在量词(∃ )**："存在"， :math:`\exists x P(x)` 表示 "存在x使得P(x)成立" **量词的否定** - :math:`\neg(\forall x P(x)) \Leftrightarrow \exists x \neg P(x)` - :math:`\neg(\exists x P(x)) \Leftrightarrow \forall x \neg P(x)` 这两个规则在逻辑推理中非常重要。 **谓词推理规则** 谓词逻辑的推理规则包括命题逻辑的所有规则，还包括： - **全称实例(UI)**：从 :math:`\forall x P(x)`，可以推出P(c)，其中c是任意个体 - **全称概括(UG)**：如果对于任意c都能推出P(c)，则可以推出 :math:`\forall x P(x)` - **存在实例(EI)**：从 :math:`\exists x P(x)`，可以推出P(c)，其中c是某个特定的个体 - **存在概括(EG)**：从 P(c)，可以推出 :math:`\exists x P(x)` **谓词逻辑的语义** 谓词逻辑的语义涉及以下概念： - **论域（域）**：谓词所讨论的对象的集合 - **解释**：对论域中每个常量的指定，对每个n元谓词的赋值 - **有效式**：在所有解释下都为真的谓词公式 - **可满足式**：存在至少一种解释使公式为真 **一阶谓词逻辑** 一阶谓词逻辑是比命题逻辑更强的逻辑系统，它允许使用量词和变量。一阶逻辑的表达能力更强，可以描述更复杂的数学性质。 例如："所有偶数都能被2整除"可以表示为： :math:`\forall x (E(x) \to D(x, 2))`，其中E(x)表示x是偶数，D(x, y)表示y能整除x。 **谓词逻辑的应用** 谓词逻辑在以下领域有重要应用： - **数据库理论**：关系数据模型和查询语言（如SQL）的理论基础 - **程序设计语言语义**：形式化描述编程语言的类型系统和语义 - **人工智能**：知识表示（如一阶逻辑推理） - **自动定理证明**：形式化证明系统的理论基础 4. 组合数学 =================================== 4.1 排列与组合 --------------------- **加法原理** 如果事件A有m种发生方式，事件B有n种发生方式，且A和B不能同时发生，那么"A或B"有m + n种发生方式。 **乘法原理** 如果事件A有m种发生方式，事件B有n种发生方式，那么"A和B"有 :math:`m \times n` 种发生方式。 **排列** 从n个不同元素中取出m个元素进行有序排列，排列数为： .. math:: P(n, m) = \frac{n!}{(n-m)!} 例如：从5个元素中取出3个进行排列，P(5,3) = 5!/(5-3)! = 60 **组合** 从n个不同元素中取出m个元素进行无序选择，组合数为： .. math:: C(n, m) = \frac{n!}{m!(n-m)!} 例如：从5个元素中取出3个，C(5,3) = 5!/(3!2!) = 10 4.2 二项式定理 --------------------- **二项式定理** 对于任意非负整数n： .. math:: (a + b)^n = \sum_{k=0}^{n} C(n, k)a^{n-k}b^k 展开式中第k+1项的系数为C(n, k)。 **杨辉三角** 杨辉三角（帕斯卡三角）展示了二项式系数的规律： :: C(0,0) C(1,0) C(1,1) C(2,0) C(2,1) C(2,2) C(3,0) C(3,1) C(3,2) C(3,3) ... 杨辉三角的每个数等于它上方两数之和：C(n, k) = C(n-1, k-1) + C(n-1, k) 4.3 容斥原理 --------------------- **容斥原理** 对于有限集合 :math:`A_1, A_2, \ldots, A_n`： .. math:: \left|\bigcup_{i=1}^{n} A_i\right| = \sum_{i=1}^{n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \cdots 以三个集合为例： .. math:: |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| **应用实例** 在1到100的正整数中，不能被2、3、5整除的数有多少个？ - 能被2整除的数： :math:`\lfloor 100/2 \rfloor = 50` - 能被3整除的数： :math:`\lfloor 100/3 \rfloor = 33` - 能被5整除的数： :math:`\lfloor 100/5 \rfloor = 20` - 能被6整除的数： :math:`\lfloor 100/6 \rfloor = 16` - 能被10整除的数： :math:`\lfloor 100/10 \rfloor = 10` - 能被15整除的数： :math:`\lfloor 100/15 \rfloor = 6` - 能被30整除的数： :math:`\lfloor 100/30 \rfloor = 3` 根据容斥原理： 能被2、3、5中至少一个整除的数 = 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74 因此，不能被2、3、5整除的数 = 100 - 74 = 26 4.4 鸽巢原理 --------------------- **鸽巢原理（抽屉原理）** 如果将n+1个物品放入n个盒子中，那么至少有一个盒子包含两个或更多物品。 **一般形式** 如果将 :math:`k \times n + 1` 个物品放入n个盒子中，那么至少有一个盒子包含 :math:`k + 1` 个或更多物品。 **应用实例** 在367个人中，至少有两个人生日相同（一年最多366天）。 在13个人中，至少有两个人出生在同一个月份。 **强鸽巢原理** 如果将物品分类，且每类中物品的平均数为μ，那么至少有一类包含至少 :math:`\lceil \mu \rceil` 个物品。 5. 离散数学在计算机科学中的应用 =================================== 5.1 数据结构 --------------------- **树的应用** 树结构在计算机科学中有广泛应用： - **二叉树**：每个节点最多有两个子节点的树，用于表达式求值、排序等 - **堆**：满足特定性质的完全二叉树，用于优先队列、堆排序 - **B树**：平衡的多路搜索树，用于数据库索引 **图的应用** 图结构用于表示复杂的关系： - **社交网络**：用户之间的关系可以用图表示 - **路由算法**：网络拓扑结构用图表示，Dijkstra算法寻找最短路径 - **网页链接**：万维网可以看作一个巨大的有向图 5.2 算法设计 --------------------- **递归与归纳** 数学归纳法是证明递归算法正确性的重要工具。 **动态规划** 组合数学的计数问题与动态规划密切相关。 **贪心算法** 图的某些性质（如最小生成树）可以用贪心算法解决。 5.3 编译原理 --------------------- **形式语言** 集合论和逻辑是形式语言理论的基础，用于描述编程语言的语法和语义。 **有限自动机** 有限自动机是处理字符串的重要工具，用于词法分析。 5.4 数据库理论 --------------------- **关系代数** 关系数据库的理论基础是集合论，关系代数操作包括选择、投影、连接等，都是集合运算的扩展。 **SQL查询** SQL查询语句可以看作是关系代数的表达式。 6. 总结与展望 =================================== 离散数学作为计算机科学的数学基础，为数据结构、算法设计、编译原理、数据库等核心课程提供了坚实的理论支撑。 **核心价值** - 提供了描述和处理离散结构的数学工具 - 培养了严密的逻辑思维能力 - 为算法分析和设计提供了理论基础 - 建立了形式化验证和证明的方法 **学习建议** - 注重理解概念的本质含义，而不仅仅是记忆公式 - 多做习题，特别是证明题和应用题 - 将理论与计算机科学实践相结合 - 使用可视化工具辅助理解抽象概念 **进阶方向** - 计算复杂性理论 - 形式化验证方法 - 组合优化理论 - 图算法高级应用 离散数学不仅是工具，更是一种思维方式，掌握它将为计算机科学的学习和研究打下坚实基础。