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