离散数学是研究离散量的结构及其相互关系的数学学科，广泛应用于计算机科学、密码学、人工智能等领域。本文档系统整理了离散数学中的核心公式与定理，涵盖集合论、逻辑、图论、组合数学等关键模块，旨在为学习者提供高效的参考工具。
公式笔记考点总结
目录集合论基础命题逻辑与谓词逻辑图论基本公式组合数学公式数论基础公式代数结构公式正文1. 集合论基础1.1 集合运算公式并集：A∪B={x∣x∈A∨x∈B}A \cup B = \{x \mid x \in A \lor x \in B\}A∪B={x∣x∈A∨x∈B}交集：A∩B={x∣x∈A∧x∈B}A \cap B = \{x \mid x \in A \land x \in B\}A∩B={x∣x∈A∧x∈B}补集：A‾={x∣x∉A}\overline{A} = \{x \mid x \notin A\}A={x∣x∈/A}差集：A−B={x∣x∈A∧x∉B}A - B = \{x \mid x \in A \land x \notin B\}A−B={x∣x∈A∧x∈/B}对称差：A⊕B=(A−B)∪(B−A)A \oplus B = (A - B) \cup (B - A)A⊕B=(A−B)∪(B−A)1.2 集合运算律交换律：A∪B=B∪AA \cup B = B \cup AA∪B=B∪A，A∩B=B∩AA \cap B = B \cap AA∩B=B∩A结合律：(A∪B)∪C=A∪(B∪C)(A \cup B) \cup C = A \cup (B \cup C)(A∪B)∪C=A∪(B∪C)，(A∩B)∩C=A∩(B∩C)(A \cap B) \cap C = A \cap (B \cap C)(A∩B)∩C=A∩(B∩C)分配律：A∪(B∩C)=(A∪B)∩(A∪C)A \cup (B \cap C) = (A \cup B) \cap (A \cup C)A∪(B∩C)=(A∪B)∩(A∪C)，A∩(B∪C)=(A∩B)∪(A∩C)A \cap (B \cup C) = (A \cap B) \cup (A \cap C)A∩(B∪C)=(A∩B)∪(A∩C)德摩根定律：A∪B‾=A‾∩B‾\overline{A \cup B} = \overline{A} \cap \overline{B}A∪B=A∩B，A∩B‾=A‾∪B‾\overline{A \cap B} = \overline{A} \cup \overline{B}A∩B=A∪B2. 命题逻辑与谓词逻辑2.1 命题逻辑公式蕴含式：p→q≡¬p∨qp \rightarrow q \equiv \neg p \lor qp→q≡¬p∨q等价式：p↔q≡(p→q)∧(q→p)p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)p↔q≡(p→q)∧(q→p)逆否命题：p→q≡¬q→¬pp \rightarrow q \equiv \neg q \rightarrow \neg pp→q≡¬q→¬p常用逻辑等价式： 双重否定律：¬¬p≡p\neg \neg p \equiv p¬¬p≡p幂等律：p∨p≡pp \lor p \equiv pp∨p≡p，p∧p≡pp \land p \equiv pp∧p≡p吸收律：p∨(p∧q)≡pp \lor (p \land q) \equiv pp∨(p∧q)≡p，p∧(p∨q)≡pp \land (p \lor q) \equiv pp∧(p∨q)≡p2.2 谓词逻辑公式全称量词：∀xP(x)\forall x P(x)∀xP(x) 表示“所有x满足P(x)”存在量词：∃xP(x)\exists x P(x)∃xP(x) 表示“存在x满足P(x)”量词否定：¬∀xP(x)≡∃x¬P(x)\neg \forall x P(x) \equiv \exists x \neg P(x)¬∀xP(x)≡∃x¬P(x)，¬∃xP(x)≡∀x¬P(x)\neg \exists x P(x) \equiv \forall x \neg P(x)¬∃xP(x)≡∀x¬P(x)3. 图论基本公式3.1 图的基本性质顶点度数：∑v∈Vdeg(v)=2∣E∣\sum_{v \in V} \deg(v) = 2|E|∑v∈Vdeg(v)=2∣E∣（握手定理）完全图边数：KnK_nKn 的边数为 n(n−1)2\frac{n(n-1)}{2}2n(n−1)二分图判定：图G是二分图当且仅当G中不含奇数长度的环3.2 特殊图公式欧拉公式：连通平面图满足 v−e+f=2v - e + f = 2v−e+f=2（v为顶点数，e为边数，f为面数）树的性质：n个顶点的树有 n−1n-1n−1 条边，且任意两点间有唯一路径4. 组合数学公式4.1 排列组合排列数：P(n,k)=n!(n−k)!P(n, k) = \frac{n!}{(n-k)!}P(n,k)=(n−k)!n!组合数：C(n,k)=(nk)=n!k!(n−k)!C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}C(n,k)=(kn)=k!(n−k)!n!二项式定理：(a+b)n=∑k=0n(nk)an−kbk(a + b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k} b^k(a+b)n=∑k=0n(kn)an−kbk4.2 容斥原理两集合：∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A \cup B| = |A| + |B| - |A \cap B|∣A∪B∣=∣A∣+∣B∣−∣A∩B∣三集合：∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣5. 数论基础公式5.1 模运算加法：(a+b)mod m=[(amod m)+(bmod m)]mod m(a + b) \mod m = [(a \mod m) + (b \mod m)] \mod m(a+b)modm=[(amodm)+(bmodm)]modm乘法：(a×b)mod m=[(amod m)×(bmod m)]mod m(a \times b) \mod m = [(a \mod m) \times (b \mod m)] \mod m(a×b)modm=[(amodm)×(bmodm)]modm逆元：若 aaa 与 mmm 互质，则存在 xxx 使得 ax≡1mod ma x \equiv 1 \mod max≡1modm5.2 欧拉定理若 aaa 与 mmm 互质，则 aϕ(m)≡1mod ma^{\phi(m)} \equiv 1 \mod maϕ(m)≡1modm，其中 ϕ(m)\phi(m)ϕ(m) 是欧拉函数6. 代数结构公式6.1 群论群公理：封闭性、结合律、单位元、逆元阿贝尔群：满足交换律的群6.2 环与域环：加法交换群 + 乘法结合律 + 分配律域：交换环且非零元素构成乘法群结论离散数学的公式体系是计算机科学与工程的重要理论基石。本文档通过结构化整理，系统呈现了集合论、逻辑、图论等核心模块的关键公式。学习者可结合具体问题灵活运用这些公式，深入理解离散结构的本质及其在算法设计、密码学等领域的应用。