离散数学速查表

本速查表汇总离散数学的核心概念、公式和定理，便于快速查阅和复习。

数理逻辑

命题逻辑联结词

联结词	符号	读法	真值条件
否定	$\neg p$	非 p	真值取反
合取	$p \land q$	p 且 q	两者都真
析取	$p \lor q$	p 或 q	至少一真
蕴含	$p \rightarrow q$	p 蕴含 q	只有 p 真 q 假时为假
双条件	$p \leftrightarrow q$	p 当且仅当 q	真值相同

逻辑等价公式

德摩根律： $\neg(p \land q) \equiv \neg p \lor \neg q$ $\neg(p \lor q) \equiv \neg p \land \neg q$

蕴含等价： $p \rightarrow q \equiv \neg p \lor q$ $p \rightarrow q \equiv \neg q \rightarrow \neg p$ （逆否命题）

分配律： $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$

吸收律： $p \lor (p \land q) \equiv p$ $p \land (p \lor q) \equiv p$

其他重要等价： $p \rightarrow (q \rightarrow r) \equiv (p \land q) \rightarrow r$ $(p \rightarrow q) \land (p \rightarrow r) \equiv p \rightarrow (q \land r)$ $(p \rightarrow r) \land (q \rightarrow r) \equiv (p \lor q) \rightarrow r$

推理规则

规则名称	形式
假言推理	$p \rightarrow q, p \vdash q$
拒取式	$p \rightarrow q, \neg q \vdash \neg p$
假言三段论	$p \rightarrow q, q \rightarrow r \vdash p \rightarrow r$
析取三段论	$p \lor q, \neg p \vdash q$

谓词逻辑量词

量词	符号	含义
全称量词	$\forall$	对所有...
存在量词	$\exists$	存在...

量词否定： $\neg(\forall x, P(x)) \equiv \exists x, \neg P(x)$ $\neg(\exists x, P(x)) \equiv \forall x, \neg P(x)$

集合论

集合运算

运算	符号	定义
并集	$A \cup B$	$\{x \mid x \in A \lor x \in B\}$
交集	$A \cap B$	$\{x \mid x \in A \land x \in B\}$
差集	$A \setminus B$	$\{x \mid x \in A \land x \notin B\}$
补集	$\overline{A}$	$U \setminus A$
对称差	$A \triangle B$	$(A \setminus B) \cup (B \setminus A)$

集合恒等式

德摩根律： $\overline{A \cup B} = \overline{A} \cap \overline{B}$ $\overline{A \cap B} = \overline{A} \cup \overline{B}$

分配律： $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

幂集公式： $|\mathcal{P}(A)| = 2^{|A|}$

笛卡尔积： $|A \times B| = |A| \times |B|$

容斥原理

两集合： $|A \cup B| = |A| + |B| - |A \cap B|$

三集合： $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

关系与函数

关系的性质

性质	定义
自反性	$\forall a \in A, (a, a) \in R$
反自反性	$\forall a \in A, (a, a) \notin R$
对称性	$(a, b) \in R \Rightarrow (b, a) \in R$
反对称性	$(a, b) \in R \land (b, a) \in R \Rightarrow a = b$
传递性	$(a, b) \in R \land (b, c) \in R \Rightarrow (a, c) \in R$

特殊关系

等价关系：自反、对称、传递

偏序关系：自反、反对称、传递

等价类： $[a] = \{x \in A \mid (a, x) \in R\}$

函数性质

性质	定义
单射（一对一）	$f(a) = f(b) \Rightarrow a = b$
满射（映上）	$\forall y \in B, \exists x \in A, f(x) = y$
双射（一一对应）	既是单射又是满射

函数计数

从 $m$ 元集到 $n$ 元集的函数个数：$n^m$

从 $m$ 元集到 $n$ 元集的单射个数：$P(n, m) = \frac{n!}{(n-m)!}$

组合计数

基本计数原理

加法原理：做一件事有 $n$ 类方法，第 $i$ 类有 $m_i$ 种方法，则共有 $m_1 + m_2 + \ldots + m_n$ 种方法。

乘法原理：做一件事有 $n$ 个步骤，第 $i$ 步有 $m_i$ 种方法，则共有 $m_1 \times m_2 \times \ldots \times m_n$ 种方法。

排列与组合

排列数： $P(n, r) = \frac{n!}{(n-r)!}$

组合数： $C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$

组合恒等式： $\binom{n}{r} = \binom{n}{n-r}$ $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$ $\sum_{r=0}^{n} \binom{n}{r} = 2^n$ $\sum_{r=0}^{n} (-1)^r \binom{n}{r} = 0$

二项式定理

$(x + y)^n = \sum_{r=0}^{n} \binom{n}{r} x^{n-r} y^r$

可重复组合

从 $n$ 个不同元素中可重复地选取 $r$ 个：

$H(n, r) = \binom{n+r-1}{r}$

图论

基本概念

术语	定义
阶（Order）	图的顶点数 $
边数	图的边数 $
度（Degree）	顶点关联的边数
路径	顶点和边交替的序列
回路	起点等于终点的路径
连通图	任意两点间有路径

握手定理

$\sum_{v \in V} \deg(v) = 2|E|$

推论：任何图中度数为奇数的顶点个数是偶数。

图的类型

类型	条件
简单图	无自环和重边
完全图 $K_n$	任意两点都有边
二分图	顶点可分为两个独立集
树	连通无回路图

完全图的边数

$|E(K_n)| = \binom{n}{2} = \frac{n(n-1)}{2}$

树的性质

• $n$ 个顶点的树有 $n-1$ 条边
• 树中任意两点间有唯一路径
• 连通图的生成树存在
• $n$ 个标号顶点的生成树个数：$n^{n-2}$（Cayley 公式）

图的着色

色数 $\chi(G)$：给图的顶点着色，使相邻顶点颜色不同，所需的最少颜色数。

布鲁克斯定理：若连通图 $G$ 不是完全图或奇环，则 $\chi(G) \leq \Delta(G)$。

数论基础

整除与同余

整除：$a \mid b$ 表示存在整数 $k$ 使得 $b = ak$

同余：$a \equiv b \pmod{n}$ 表示 $n \mid (a - b)$

最大公约数与最小公倍数

$\gcd(a, b) \cdot \text{lcm}(a, b) = a \cdot b$

欧几里得算法： $\gcd(a, b) = \gcd(b, a \mod b)$

欧拉函数

$\phi(n)$：小于 $n$ 且与 $n$ 互质的正整数个数。

公式：若 $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$，则： $\phi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right)$

费马小定理

若 $p$ 是素数且 $\gcd(a, p) = 1$，则： $a^{p-1} \equiv 1 \pmod{p}$

代数结构

群的定义

集合 $G$ 和运算 $\cdot$ 构成群，满足：

1. 封闭性：$\forall a, b \in G, a \cdot b \in G$
2. 结合律：$(a \cdot b) \cdot c = a \cdot (b \cdot c)$
3. 单位元：$\exists e \in G, \forall a \in G, e \cdot a = a \cdot e = a$
4. 逆元：$\forall a \in G, \exists a^{-1}, a \cdot a^{-1} = e$

常见代数结构

结构	条件
半群	封闭、结合律
幺半群	半群 + 单位元
群	幺半群 + 逆元
阿贝尔群（交换群）	群 + 交换律
环	两个运算，都是阿贝尔群，满足分配律
域	环 + 非零元素有乘法逆元

递推关系

求解方法

特征方程法（用于线性齐次递推）：

对于 $a_n = c_1 a_{n-1} + c_2 a_{n-2}$，解特征方程： $r^2 - c_1 r - c_2 = 0$

若有两个不同根 $r_1, r_2$： $a_n = A \cdot r_1^n + B \cdot r_2^n$

常见递推关系

斐波那契数列：$F_n = F_{n-1} + F_{n-2}$ 通项公式： $F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]$

汉诺塔：$T_n = 2T_{n-1} + 1$ 解：$T_n = 2^n - 1$

常用数学符号

数集符号

符号	含义
$\mathbb{N}$	自然数集
$\mathbb{Z}$	整数集
$\mathbb{Q}$	有理数集
$\mathbb{R}$	实数集
$\mathbb{C}$	复数集

其他符号

符号	含义
$\forall$	对所有
$\exists$	存在
$\in$	属于
$\subseteq$	子集
$\Rightarrow$	蕴含
$\Leftrightarrow$	当且仅当
$\therefore$	因此
$\blacksquare$	证明完毕