离散数学公式

离散数学是计算机科学的基础，涵盖了集合论、逻辑、关系、图论、代数结构、组合数学等多个领域。掌握这些公式和概念，对于理解和解决计算机科学中的问题至关重要。希望本文能帮助你全面掌握离散数学的核心内容。

目录

1. 集合论
2. 逻辑与命题
3. 关系与函数
4. 图论
5. 代数结构
6. 组合数学
7. 递归与递推
8. 概率与统计

---

1. 集合论

1.1 基本概念

• 集合表示：

  • 列举法：$A = \{1, 2, 3\}$
  • 描述法：$A = \{x \mid x \text{ 是正整数且 } x \leq 3\}$

• 集合运算：

  • 并集：$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\}$
  • 补集：$\overline{A} = \{x \mid x \notin A\}$

• 幂集：

  • $P(A) = \{S \mid S \subseteq A\}$

1.2 集合恒等式

• 交换律：

  • $A \cup B = B \cup A$
  • $A \cap B = B \cap A$

• 结合律：

  • $A \cup (B \cup C) = (A \cup B) \cup C$
  • $A \cap (B \cap C) = (A \cap B) \cap C$

• 分配律：

  • $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
  • $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

• 德摩根律：

  • $\overline{A \cup B} = \overline{A} \cap \overline{B}$
  • $\overline{A \cap B} = \overline{A} \cup \overline{B}$

---

2. 逻辑与命题

2.1 命题逻辑

• 命题连接词：

  • 否定：$\neg P$
  • 合取：$P \land Q$
  • 析取：$P \lor Q$
  • 蕴含：$P \rightarrow Q$
  • 等价：$P \leftrightarrow Q$

• 逻辑等价：

  • $P \rightarrow Q \equiv \neg P \lor Q$
  • $P \leftrightarrow Q \equiv (P \rightarrow Q) \land (Q \rightarrow P)$

• 德摩根律：

  • $\neg (P \land Q) \equiv \neg P \lor \neg Q$
  • $\neg (P \lor Q) \equiv \neg P \land \neg Q$

2.2 谓词逻辑

• 全称量词：

  • $\forall x \, P(x)$

• 存在量词：

  • $\exists x \, P(x)$

• 量词否定：

  • $\neg \forall x \, P(x) \equiv \exists x \, \neg P(x)$
  • $\neg \exists x \, P(x) \equiv \forall x \, \neg P(x)$

---

3. 关系与函数

3.1 关系

• 关系表示：

  • 有序对：$(a, b) \in R$

• 关系性质：

  • 自反性：$\forall a \in A, (a, a) \in R$
  • 对称性：$\forall a, b \in A, (a, b) \in R \Rightarrow (b, a) \in R$
  • 传递性：$\forall a, b, c \in A, (a, b) \in R \land (b, c) \in R \Rightarrow (a, c) \in R$

• 闭包：

  • 自反闭包：$R \cup \{(a, a) \mid a \in A\}$
  • 对称闭包：$R \cup R^{-1}$
  • 传递闭包：$R^+ = \bigcup_{n=1}^{\infty} R^n$

3.2 函数

• 函数定义：

  • $f: A \rightarrow B$

• 函数性质：

  • 单射：$\forall a_1, a_2 \in A, f(a_1) = f(a_2) \Rightarrow a_1 = a_2$
  • 满射：$\forall b \in B, \exists a \in A, f(a) = b$
  • 双射：既是单射又是满射。

---

4. 图论

4.1 基本概念

• 图表示：

  • 无向图：$G = (V, E)$
  • 有向图：$G = (V, E)$

• 度：

  • 无向图：$\deg(v)$
  • 有向图：$\deg^+(v)$（出度），$\deg^-(v)$（入度）

4.2 图的连通性

• 连通图：

  • 无向图：任意两点间存在路径。
  • 有向图：强连通（任意两点间双向路径）。

• 欧拉回路：

  • 无向图：所有顶点的度数为偶数。
  • 有向图：所有顶点的入度等于出度。

• 哈密顿回路：

  • 存在一条经过每个顶点一次的回路。

---

5. 代数结构

5.1 群

• 群定义：
  • 封闭性：$\forall a, b \in G, a \cdot b \in G$
  • 结合律：$\forall a, b, c \in G, (a \cdot b) \cdot c = a \cdot (b \cdot c)$
  • 单位元：$\exists e \in G, \forall a \in G, a \cdot e = e \cdot a = a$
  • 逆元：$\forall a \in G, \exists a^{-1} \in G, a \cdot a^{-1} = a^{-1} \cdot a = e$

5.2 环与域

• 环：

  • 加法群，乘法半群，分配律成立。

• 域：

  • 加法群，乘法群（除去零元），分配律成立。

---

6. 组合数学

6.1 排列与组合

• 排列：

  • $P(n, k) = \frac{n!}{(n - k)!}$

• 组合：

  • $C(n, k) = \frac{n!}{k!(n - k)!}$

6.2 二项式定理

• $(a + b)^n = \sum_{k=0}^{n} C(n, k) a^{n-k} b^k$

---

7. 递归与递推

7.1 递归关系

• 斐波那契数列：

  • $F(n) = F(n-1) + F(n-2)$

• 汉诺塔：

  • $T(n) = 2T(n-1) + 1$

7.2 递推求解

• 主定理：
  • 对于递推式 $T(n) = aT(n/b) + f(n)$，主定理提供解的形式。

---

8. 概率与统计

8.1 基本概率

• 概率公式：

  • $P(A) = \frac{|A|}{|S|}$

• 条件概率：

  • $P(A \mid B) = \frac{P(A \cap B)}{P(B)}$

8.2 期望与方差

• 期望：

  • $E(X) = \sum x P(x)$

• 方差：

  • $\text{Var}(X) = E(X^2) - [E(X)]^2$

---

总结

离散数学是计算机科学的基础，涵盖了集合论、逻辑、关系、图论、代数结构、组合数学等多个领域。掌握这些公式和概念，对于理解和解决计算机科学中的问题至关重要。希望本文能帮助你全面掌握离散数学的核心内容。

---

参考文档：

• 《离散数学及其应用》 - Kenneth H. Rosen
• 《离散数学》 - Richard Johnsonbaugh