离散数学基础
这一课你将能做到
- 用集合语言描述并集、交集、差集、幂集，并对应到 Java 的
Set 操作与 SQL 的 JOIN
- 区分命题逻辑中的与、或、非、蕴含，能把业务条件写成真值表并化简
- 说清图论中度数、路径、连通分量、DAG 的直觉，以及数论中整除、模运算、素数、GCD 的工程用途
为什么要学
离散数学是「计算机自己的数学」。微积分处理连续变化，而软件面对的全是离散对象：一个用户集合、一组权限位、一张调用关系图、一个对数组长度取模得到的桶号。它不追求让你会做证明题，而是给你四把日常用得上的直觉尺子：
- 集合论：Redis 的 Set、Java 的 HashSet、SQL 的 JOIN 和去重，全是集合运算
- 逻辑：if 条件、权限判断、SQL WHERE、代码能不能被短路，背后是布尔代数
- 图论：社交关系、服务依赖、题目推荐、死锁检测，本质都是图上的问题
- 数论：哈希表取模、分库分表、雪花算法、RSA 加密，都建立在整除与模运算上
本课只建立直觉和工程对应，形式化的证明留给后续深入。
先建立图像
四大分支一张图
集合论：研究「一堆确定对象」
A={1,2,3} B={2,3,4}
并 A∪B={1,2,3,4} 交 A∩B={2,3} 差 A−B={1}
子集/幂集：A 的全部子集组成的集合有 2^|A| 个元素
逻辑：研究「命题的真假组合」
P∧Q 与(都真才真) P∨Q 或(一个真就真) ¬P 非
P⇒Q 蕴含：只有「P真Q假」时为假 ≡ ¬P∨Q
图论：研究「点与连接」
度=连边数 路径=边的序列 连通分量=互相可达的点集团
DAG=有向无环图：任务依赖、课程前置、编译顺序
数论：研究「整数的结构」
a mod b = 余数 a|b 表示 a 整除 b
GCD 最大公约数 素数=只有 1 和自身两个因子
记忆方式：集合管「属于谁」，逻辑管「是真是假」，图论管「怎么连、能不能到」，数论管「整数相除剩什么」。
跟着做
步骤 1：集合运算与 Java/SQL 对应
import java.util.Set;
public class SetMath {
public static void main(String[] args) {
Set<Integer> a = Set.of(1, 2, 3);
Set<Integer> b = Set.of(2, 3, 4);
Set<Integer> union = Set.copyOf(a);
union = java.util.stream.Stream.concat(a.stream(), b.stream())
.collect(java.util.stream.Collectors.toUnmodifiableSet());
System.out.println("并集: " + union); // {1,2,3,4}
Set<Integer> intersect = a.stream().filter(b::contains)
.collect(java.util.stream.Collectors.toSet());
System.out.println("交集: " + intersect); // {2,3}
Set<Integer> diff = a.stream().filter(x -> !b.contains(x))
.collect(java.util.stream.Collectors.toSet());
System.out.println("差集: " + diff); // {1}
System.out.println("3 元素集合的子集数 = 2^3 = " + (1 << 3)); // 8
}
}
工程对应：INNER JOIN 是交集，LEFT JOIN 保左集合，UNION 是并集，DISTINCT 是去重；Redis 的 SINTER/SUNION/SDIFF 直接以命令名对应交、并、差。判题平台用 Set 给「同时 AC 了题 A 和题 B 的用户」做人群圈选，底层就是交集运算。
步骤 2：布尔逻辑与条件化简
public class LogicDemo {
public static void main(String[] args) {
boolean isVip = true;
boolean hasCoupon = false;
// 蕴含直觉：「是 VIP 就免运费」= 不是 VIP，或者免运费条件成立
boolean freeShip = !isVip || true;
System.out.println(freeShip);
// 德摩根定律：¬(P∧Q) ≡ ¬P∨¬Q
// 「不能同时 已删除 且 已发布」的正向写法
boolean deleted = false;
boolean published = true;
boolean valid1 = !(deleted && published);
boolean valid2 = !deleted || !published;
System.out.println(valid1 == valid2); // true，两种写法等价
// 短路：&& 左边为假则右边不执行——判空之后再取属性正是靠它
String title = null;
if (title != null && title.length() > 5) {
System.out.println("不会 NPE，因为第二个条件没执行");
}
}
}
实用结论：复杂 if 嵌套用真值表枚举全部输入组合（n 个条件 2ⁿ 行），再用德摩根定律和分配律把条件化简；权限系统中「角色 ∧ 资源 ∧ 操作」的判断就是布尔表达式，位掩码（第 12 课）是它的压缩存储形式。
步骤 3：图论直觉——连通、DAG 与拓扑排序
import java.util.*;
public class GraphMath {
// 判题任务的前置依赖（DAG）：编译 → 执行 → 比对；拉取测试数据也必须先于执行
static Map<String, List<String>> buildGraph() {
Map<String, List<String>> g = new HashMap<>();
g.put("拉取数据", List.of("执行"));
g.put("编译", List.of("执行"));
g.put("执行", List.of("比对"));
g.put("比对", List.of());
return g;
}
// Kahn 拓扑排序：不断取出入度为 0 的节点
static List<String> topoSort(Map<String, List<String>> g) {
Map<String, Integer> indegree = new HashMap<>();
g.keySet().forEach(k -> indegree.put(k, 0));
g.values().forEach(edges -> edges.forEach(v -> indegree.merge(v, 1, Integer::sum)));
Deque<String> queue = new ArrayDeque<>();
indegree.forEach((k, d) -> { if (d == 0) queue.offer(k); });
List<String> order = new ArrayList<>();
while (!queue.isEmpty()) {
String node = queue.poll();
order.add(node);
g.get(node).forEach(next -> {
if (indegree.merge(next, -1, Integer::sum) == 0) queue.offer(next);
});
}
return order; // 若结果少于节点数，说明图里有环（依赖矛盾）
}
public static void main(String[] args) {
System.out.println(topoSort(buildGraph()));
}
}
图论要点直觉：度数决定一个点多忙（微服务里入度高的服务是关键依赖）；连通分量就是图里互不来往的集团（用并查集高效合并、查询）；DAG 上的拓扑排序给出合法的任务先后顺序，Maven 构建、课程解锁、工作流引擎都用它；如果拓扑排序处理不完所有节点，说明存在环——这就是循环依赖的检测方法，Spring 启动时的循环依赖报错同理。
步骤 4：数论——模运算、GCD 与素数
public class NumberTheory {
// 欧几里得算法：GCD(a,b) = GCD(b, a mod b)
public static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public static void main(String[] args) {
// 模运算就是「转圈取余」：哈希定位桶、环形缓冲区下标都靠它
int[] buckets = new int[8];
for (int key = 0; key < 20; key++) {
buckets[key % 8]++;
}
System.out.println(java.util.Arrays.toString(buckets));
// GCD：把两根周期分别为 12 和 18 的任务对齐，公共周期 = LCM = a*b/GCD
int g = gcd(12, 18);
System.out.println("GCD=" + g + ", LCM=" + 12 * 18 / g); // 6, 36
// 试除法判素数：只需检查到 √n（因子成对出现）
System.out.println(isPrime(97)); // true
}
static boolean isPrime(int n) {
if (n < 2) return false;
for (int i = 2; (long) i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
}
为什么数论在工程里高频：分库分表时 userId % 库数 决定数据落点（取模不均会数据倾斜，所以要选好分片键）；哈希函数的核心是模运算；RSA 等非对称加密建立在「大素数相乘容易、分解极难」的不对称性上（第 10 课展开）；雪花算法的 ID 由时间戳、机器号、序列号按位拼接。理解到「模运算是带折回的数轴、素数是整数的原子」就够用。
讲清楚要点
- 集合的三个基本运算（并、交、差）加一个补集概念，可以表达一切数据筛选；集合中元素无序、不重复——这正是 Set 与 List 的契约差异，也是为什么
DISTINCT 和 GROUP BY 能去重。
- 布尔代数与集合代数同构：并对应或、交对应与、补对应非，所以德摩根定律在两边都成立；
P⇒Q 只在 P 真 Q 假时为假，是理解权限规则和 SQL 条件的关键。
- 图的两种遍历与两个经典问题：BFS/DFS（第 3 课）解决「怎么走遍」；拓扑排序解决「先做谁」，最短路、最小生成树解决「怎么走最省」，工程中大多直接调用现成库，但要能认出问题属于哪类。
- 模运算的核心性质：
(a+b) mod n = ((a mod n)+(b mod n)) mod n，加减乘都可先取模再运算，防止大数溢出；但除法不能直接取模，需要模逆元（加密算法中出现）。
- GCD/LCM 与素数：GCD 用欧几里得算法 O(log min(a,b))；素数判定只需到 √n，因子成对是其直觉；这些小算法是理解更复杂密码学与散列设计的台阶。
你可能会懵的地方
-
集合的幂集是什么，为什么是 2ⁿ 个？
一个集合的全部子集（含空集和自身）构成幂集。每个元素对「某个子集」而言只有「选/不选」两种状态，n 个元素就是 2ⁿ 种组合。特征工程里的子集枚举、测试用例组合爆炸，根源都是这个数。
-
蕴含 P⇒Q 为什么「P 为假」时整个命题反而是真的？
把它读成承诺：「如果下雨（P），我就带伞（Q）」。只有下雨却没带伞时承诺才算被违背；没下雨时带不带伞都不算食言。所以真值表里 P 假则命题真，等价写法是 ¬P∨Q。
-
有向图、无向图、DAG 老分不清？
边有没有箭头（关系是否单向，如关注与好友）决定有向/无向；在有向图里再问「沿箭头会不会兜回原点」，不会的才是 DAG。任务依赖必须是 DAG，否则出现 A 等 B、B 等 A 的死局。
-
为什么哈希表桶数常取素数？
当 key 的分布呈现某种周期（比如 key 都是偶数）时，桶数为素数能让取模结果不与该周期共振，分布更均匀。Java HashMap 用 2 的幂是配合位运算（hash & (n−1)），但额外做了 hash 扰动补偿，两种思路各有前提。
-
离散数学要学到什么程度？
后端业务开发：本课的直觉 + 能手写 GCD/拓扑/简单集合运算即可。若要深入数据库内核、密码学、算法岗，则需要系统学习证明、关系代数、群论等，建议以《具体数学》或 Rosen《离散数学》进阶。
错法对照
| 错法 | 问题 | 正解 |
|---|
| 用 List 表达「无序不重复」概念 | 重复元素、O(n) 判重 | 用 Set，语义与性能都对 |
| 多重取模时先把两个大数相加 | 加法溢出后结果错误 | 先各自取模再加，必要时用 long/BigInteger |
| 拓扑排序不检查结果长度 | 有环时静默返回部分顺序 | 结果数 < 节点数即报「循环依赖」 |
| 权限条件用嵌套 if 堆到五层 | 无法穷举验证，易漏分支 | 列真值表，用布尔定律化简或改策略表 |
| 判素数循环写到 n-1 | 白做 √n 之后的全部检查 | 到 √n 为止（注意 i*i 的溢出） |
卡点急救
- 分库分表后数据倾斜：检查分片键与桶数是否有公共因子（用 GCD 判断），更换分片键或取素数桶数；先用集合统计各桶分布再决定。
- 任务/工作流跑不动或互相死等：把依赖画成有向图跑拓扑排序，处理不完节点即定位到环上的具体任务，打破循环依赖。
- 复杂权限规则总出漏洞：把条件整理成真值表逐行核对，补全测试用例；长期方案是规则引擎或权限框架的声明式策略，而不是继续加 if。
面试常问
-
集合的交并差在数据库和缓存里分别对应什么？
SQL：INNER JOIN 近似交集、FULL/LEFT JOIN 处理并集与保侧、EXCEPT/MINUS 是差集、UNION 合并去重；Redis：SINTER、SUNION、SDIFF；Java：retainAll、addAll、removeAll（注意会修改原集合）。
-
什么是拓扑排序？什么场景用？结果不完整说明什么？
对 DAG 排出「所有边都从前指向后」的线性顺序，Kahn 算法基于入度归零，或 DFS 后序逆序。用于编译顺序、任务调度、课程解锁。结果少于节点数说明存在有向环，即循环依赖。
-
讲一下模运算的性质和至少两个工程应用。
加减乘可先取模再运算且结果不变；应用：哈希表定位桶、环形数组下标、分库分表路由、校验和（如 ISBN/Luhn）。除法需模逆元，是非对称加密与签名算法的数学基础之一。
自测三问
- 给两个 Set，不看代码默写出交集与差集的实现思路，并说出对应 SQL 关键字。
- 为什么「下雨就带伞」这句话在没下雨时无论带没带伞都算真话？写出它的等价析取式。
- GCD 为什么能在 O(log n) 内算出？举出两个「模运算 + 素数」在系统里的真实落点。
小结一句话
离散数学不研究曲线而研究「对象、真假、连接、余数」——软件世界恰好由它们构成，集合、逻辑、图、数论的直觉是看懂高级数据结构与系统设计的通用底座。
延伸