离散数学基础

这一课你将能做到

1. 用集合语言描述并集、交集、差集、幂集，并对应到 Java 的 Set 操作与 SQL 的 JOIN
2. 区分命题逻辑中的与、或、非、蕴含，能把业务条件写成真值表并化简
3. 说清图论中度数、路径、连通分量、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 由时间戳、机器号、序列号按位拼接。理解到「模运算是带折回的数轴、素数是整数的原子」就够用。

讲清楚要点

1. 集合的三个基本运算（并、交、差）加一个补集概念，可以表达一切数据筛选；集合中元素无序、不重复——这正是 Set 与 List 的契约差异，也是为什么 DISTINCT 和 GROUP BY 能去重。
2. 布尔代数与集合代数同构：并对应或、交对应与、补对应非，所以德摩根定律在两边都成立；P⇒Q 只在 P 真 Q 假时为假，是理解权限规则和 SQL 条件的关键。
3. 图的两种遍历与两个经典问题：BFS/DFS（第 3 课）解决「怎么走遍」；拓扑排序解决「先做谁」，最短路、最小生成树解决「怎么走最省」，工程中大多直接调用现成库，但要能认出问题属于哪类。
4. 模运算的核心性质：(a+b) mod n = ((a mod n)+(b mod n)) mod n，加减乘都可先取模再运算，防止大数溢出；但除法不能直接取模，需要模逆元（加密算法中出现）。
5. 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 的溢出）

卡点急救

1. 分库分表后数据倾斜：检查分片键与桶数是否有公共因子（用 GCD 判断），更换分片键或取素数桶数；先用集合统计各桶分布再决定。
2. 任务/工作流跑不动或互相死等：把依赖画成有向图跑拓扑排序，处理不完节点即定位到环上的具体任务，打破循环依赖。
3. 复杂权限规则总出漏洞：把条件整理成真值表逐行核对，补全测试用例；长期方案是规则引擎或权限框架的声明式策略，而不是继续加 if。

面试常问

• 集合的交并差在数据库和缓存里分别对应什么？ SQL：INNER JOIN 近似交集、FULL/LEFT JOIN 处理并集与保侧、EXCEPT/MINUS 是差集、UNION 合并去重；Redis：SINTER、SUNION、SDIFF；Java：retainAll、addAll、removeAll（注意会修改原集合）。

• 什么是拓扑排序？什么场景用？结果不完整说明什么？ 对 DAG 排出「所有边都从前指向后」的线性顺序，Kahn 算法基于入度归零，或 DFS 后序逆序。用于编译顺序、任务调度、课程解锁。结果少于节点数说明存在有向环，即循环依赖。

• 讲一下模运算的性质和至少两个工程应用。 加减乘可先取模再运算且结果不变；应用：哈希表定位桶、环形数组下标、分库分表路由、校验和（如 ISBN/Luhn）。除法需模逆元，是非对称加密与签名算法的数学基础之一。

自测三问

1. 给两个 Set，不看代码默写出交集与差集的实现思路，并说出对应 SQL 关键字。
2. 为什么「下雨就带伞」这句话在没下雨时无论带没带伞都算真话？写出它的等价析取式。
3. GCD 为什么能在 O(log n) 内算出？举出两个「模运算 + 素数」在系统里的真实落点。

小结一句话

离散数学不研究曲线而研究「对象、真假、连接、余数」——软件世界恰好由它们构成，集合、逻辑、图、数论的直觉是看懂高级数据结构与系统设计的通用底座。

延伸

• MIT 6.042J Mathematics for Computer Science（公开课程）——离散数学的权威入门课，含全部讲义与习题
• 《具体数学》主页（Grahm/Knuth/Patashnik）——算法分析背后数学思维的经典
• Rosen《离散数学及其应用》配套资源
• 下一课：操作系统概念——数学给了抽象，下一课回到机器：操作系统如何让成百上千个进程线程「同时」使用一套 CPU 和内存。