简介：本资源是一份系统、详实的《离散数学》核心概念学习笔记，面向计算机专业本科生、考研学生及算法与理论基础薄弱的开发者，旨在帮助读者扎实掌握数理逻辑、集合论、图论、代数系统、关系论等关键模块，夯实计算机科学的数学根基。笔记以PDF格式单文件呈现（1个630KB文件），内容结构清晰、定义严谨、定理完整，覆盖命题逻辑（含范式转换、自然推理规则）、谓词逻辑、集合运算与函数、等价/偏序关系及其闭包、群与格等代数结构、欧拉/哈密顿图与树等图论核心，以及计数原理、概率基础与数论要点。预览可见其采用递归定义、运算律归纳、典型例证与算法（如Warshall传递闭包）并重的笔记风格，便于理解、记忆与复习。目前已有2880人下载学习，是兼顾理论深度与应试实用性的高价值入门与进阶参考材料。
1. 离散数学笔记.pdf：为什么一份手写风格的PDF，能让你在算法面试中少走三年弯路？
你有没有遇到过这种场景：写一个图的拓扑排序，逻辑通顺却总漏掉环检测；实现一个哈希表的键值映射，调试半天才发现等价关系没定义清楚；看懂了红黑树的旋转代码，却说不清“左旋保持偏序”背后的格论依据？——这些不是编码能力问题，而是离散结构的直觉尚未内化。这份《离散数学笔记.pdf》不是教科书的压缩包，它是一份用命题逻辑推演闭包构造、用集合势解释递归终止、用群同态重解状态机等价性的底层思维训练手册。它把“为什么DFS要标记访问状态”还原成“传递闭包的最小不动点迭代”，把“为什么哈希冲突要用链地址法”锚定在“等价类划分与陪集分解的同构性”上。这不是知识罗列，而是一套可执行的形式化直觉生成器：当你看到“Warshall算法更新矩阵第k行第k列”，你立刻意识到那是在对关系R进行R ∪ (R∘R) ∪ (R∘R∘R) … 的有限次幂逼近——因为笔记里用三行伪代码+一个n=3的矩阵演化图，把“传递闭包为何是R⁺ = R ∪ R² ∪ R³ ∪ …”这个抽象定义，焊死在你的工作记忆里。它解决的从来不是“怎么算”，而是“为什么必须这么算”。
2. 命题逻辑：为什么真值表穷举不是终点，而是自然推理的起点？
2.1 命题表达式的递归骨架：从语法树到语义求值栈
命题表达式（如(p → q) ∧ ¬r）不是字符串，而是一棵带类型标签的抽象语法树（AST）。笔记用递归定义明确其结构：
1) 命题变元 p, q, r 是命题表达式； 2) 若 A 是命题表达式，则 ¬A 是命题表达式； 3) 若 A, B 是命题表达式，则 (A ∧ B), (A ∨ B), (A → B), (A ↔ B) 是命题表达式； 4) 仅由有限次应用上述规则生成的符号串才是合法表达式。关键在于：每条规则对应一个语义求值操作。例如规则2）对应“取反操作符¬”，其语义函数⟦¬A⟧(σ) = 1 - ⟦A⟧(σ)（σ为指派），而规则3）中∧的语义是⟦A ∧ B⟧(σ) = min(⟦A⟧(σ), ⟦B⟧(σ))。笔记在“逻辑运算符优先级”旁手绘了一棵(p → q) ∧ ¬r的AST：根节点是∧，左子树是→（p,q为叶），右子树是¬（r为叶）。这棵树直接决定了求值顺序——必须先算p→q和¬r，再合取。没有这棵树，所谓“优先级”只是死记硬背；有了它，任何复杂表达式都能拆解为原子操作的组合。
提示：笔记在“成真指派”部分强调：对含n个变元的表达式，其真值表有2ⁿ行，但有效指派数可能远小于2ⁿ。例如
p ∧ ¬p只有0个成真指派，p ∨ ¬p则有2ⁿ个。这揭示了永真式/永假式的本质：它们的语义函数是常量函数（恒为1或0），与指派无关。
2.2 自然推理规则：如何把“显然成立”变成可验证的证明链？
自然推理不是公理系统，而是模拟人类推理直觉的形式化工具。笔记将8条核心规则分为三类：
| 规则名 | 推理式 | 机制说明 |
|---|---|---|
| 引入规则 | p, q ⇒ p ∧ q（合取引入） | 将两个独立真命题“打包”为合取式，对应编程中的结构体构造（{p:true, q:true}） |
| 消去规则 | p ∧ q ⇒ p（合取消去） | 从合取式中“解构”出单个分量，类似对象属性访问obj.p |
| 转换规则 | p → q, p ⇒ q（假言推理） | 模拟“如果P则Q，且P成立，故Q成立”的因果链，是所有条件分支的逻辑原型 |
特别值得注意的是消解律：p ∨ q, ¬p ∨ r ⇒ q ∨ r。笔记用电路图类比：p∨q是“p或q导通”，¬p∨r是“p断开则r导通”，二者并联后，无论p通断，q或r必有一个导通。这正是SAT求解器中CDCL（冲突驱动子句学习）算法的核心——当冲突发生时，通过消解生成新的“学习子句”来剪枝搜索空间。笔记没提CDCL，但它用消解律的三次手动推演（含一个含4个文字的子句），让你亲手感受到“新子句如何压缩搜索树”。
2.3 CNF/DNF：为什么布尔电路设计必须先转合取范式？
合取范式（CNF）是“与门连接多个或门”的电路结构，析取范式（DNF）是“或门连接多个与门”。笔记指出：CNF是硬件实现的友好形式，DNF是逻辑综合的友好形式。
CNF优势：每个子句
Cᵢ = l₁ ∨ l₂ ∨ … ∨ lₖ对应一个“只要有一个文字为真，该子句即满足”的约束。SAT求解器（如MiniSat）的冲突分析、变量决策都基于CNF结构。笔记给出(p → q) ∧ (r → s)转CNF的完整步骤：- 消除蕴含：
(¬p ∨ q) ∧ (¬r ∨ s) - 已是CNF（两个二元子句的合取）
- 消除蕴含：
DNF价值：主析取范式（所有最小项的析取）直接对应真值表中所有成真指派。笔记用
p ⊕ q（异或）为例：其真值表有2个成真指派（p=0,q=1 和 p=1,q=0），故主DNF为(¬p ∧ q) ∨ (p ∧ ¬q)—— 这正是数字电路中异或门的标准实现。
注意：笔记强调“任意公式可转CNF/DNF，但主范式唯一”。这意味着：不同推导路径得到的CNF可能文字数不同，但主CNF（所有最大项的合取）是唯一的。这解释了为何逻辑综合工具会追求“最简CNF”——它在保持逻辑等价的前提下，最小化硬件门数。
2.4 避坑：命题逻辑常见翻车现场与修复路径
现象：用
p → q表达“p发生导致q发生”，但在程序中写if p then q却出现q未执行的bug。
原因：p → q在p=false时恒为真（空真），而程序中的if语句只在p=true时执行q。二者语义不等价！p → q的编程等价物是if not p or q。
解决：在建模因果时，若需排除空真情况，改用p ∧ (p → q)（即p ∧ q），或引入时序逻辑。现象：将
¬(p ∧ q)直接等价于¬p ∧ ¬q，导致集合补集计算错误。
原因：混淆德摩根律。正确形式是¬(p ∧ q) ≡ ¬p ∨ ¬q。笔记用Venn图强调：p∧q是交集，其补集是“不在p中或不在q中”的并集。
解决：对任意逻辑等价式，强制用真值表验证（尤其当含3个以上变元时）。笔记附有快速验证法：只需检查等价式A ↔ B是否为永真式（全1列）。现象：证明
p → q时，误用“反证法”假设p → q为假，推出矛盾。
原因：p → q为假仅当p=true ∧ q=false，反证法应假设此情形成立，而非假设整个蕴含式为假。正确反证路径是：假设p=true ∧ q=false，导出矛盾。
解决：牢记“蕴含式为假”的唯一情形。笔记在“证明方法”页边空白处手写：“反证p→q，先撕开它：p ∧ ¬q”。现象：将谓词逻辑的
∀x P(x)与命题逻辑的p ∧ q ∧ r类比，认为∀x只是“无限合取”。
原因：无限合取在经典逻辑中无定义（涉及紧致性定理），且∀x具有变量绑定特性（∀x P(x)中x被约束，不可随意替换）。
解决：用全称例示规则∀x P(x) ⇒ P(c)理解∀x——它保证对任意具体个体c，P(c)成立，而非对某个固定集合的合取。
3. 集合论与关系论：为什么数据库索引和缓存淘汰策略，本质都是闭包运算？
3.1 集合势与可数性：如何用双射理解“无穷大也有大小”？
集合的势（基数）不是元素个数，而是存在双射的等价类。笔记用三个经典双射彻底破除“无穷=∞”的迷思：
|N| = |Z|：构造f: N → Z，f(0)=0, f(1)=1, f(2)=-1, f(3)=2, f(4)=-2, ...。这是“蛇形遍历”整数轴，证明可数无限集可被线性枚举。|N| = |Q|：用“对角线法”将正有理数排成网格，按分子分母和分组遍历（1/1, 1/2, 2/1, 1/3, 2/2, 3/1,...），剔除约分重复项。笔记手绘网格，标出前10个映射，强调“可数性取决于能否列出，而非是否稠密”。|N| < |R|：康托尔对角论证。笔记给出精简版：假设[0,1)区间可数，则可列r₁,r₂,...，将其小数展开为0.d₁₁d₁₂...,0.d₂₁d₂₂...，构造新数s=0.s₁s₂...其中sᵢ ≠ dᵢᵢ，则s不在列表中，矛盾。
关键洞见：数据库的“唯一索引”本质是维护一个可数集上的双射——每个键映射到唯一值，插入时需验证该键未被占用（即检查是否已存在双射）。而“布隆过滤器”的误判率，正源于它用有限位数组近似无限集R的特征函数，必然存在哈希碰撞（即sᵢ与dⱼᵢ的冲突）。
3.2 二元关系的矩阵表示：为什么邻接矩阵的幂等于路径计数？
设关系R ⊆ A×A，|A|=n，其关系矩阵M_R是n阶0-1矩阵，M_R[i][j]=1当且仅当(aᵢ,aⱼ)∈R。笔记指出：M_R^k[i][j]的值等于从aᵢ到aⱼ的长度为k的路径数。
证明基于矩阵乘法定义：M_R^2[i][j] = Σₗ M_R[i][l] × M_R[l][j]。由于是0-1矩阵，乘积为1当且仅当M_R[i][l]=1且M_R[l][j]=1，即存在aₗ使(aᵢ,aₗ)∈R且(aₗ,aⱼ)∈R，这正是长度为2的路径。归纳可得M_R^k[i][j]统计所有k步路径。
提示：笔记在“关系的幂”页用
A={1,2,3},R={(1,2),(2,3),(3,1)}为例，手算M_R,M_R²,M_R³，发现M_R³是单位矩阵——这对应关系R的3次复合回到自身，即图中存在长度为3的环。这正是检测循环依赖（如模块导入环）的数学基础。
3.3 传递闭包：Warshall算法为何是动态规划，而非暴力枚举？
传递闭包R⁺是包含R的最小传递关系。暴力法需检查所有(a,b),(b,c)∈R⁺是否蕴含(a,c)∈R⁺，时间复杂度O(|A|⁴)。Warshall算法将其优化至O(|A|³)，其核心是动态规划状态定义：
Wₖ[i][j] = 1表示存在从aᵢ到aⱼ的路径，且路径中所有中间顶点均属于{a₁,...,aₖ}。
初始W₀ = M_R（无中间顶点）。状态转移：Wₖ[i][j] = Wₖ₋₁[i][j] ∨ (Wₖ₋₁[i][k] ∧ Wₖ₋₁[k][j])
即：aᵢ→aⱼ的路径，要么不经过aₖ（继承Wₖ₋₁[i][j]），要么经过aₖ（需aᵢ→aₖ且aₖ→aⱼ）。笔记用k=2的迭代图示，清晰展示a₁→a₃如何因a₁→a₂且a₂→a₃而被置1。
为什么这是DP？因为Wₖ依赖于更小的子问题Wₖ₋₁，且最优子结构成立：aᵢ→aⱼ经aₖ的最短路径，必由aᵢ→aₖ和aₖ→aⱼ的最短路径构成。
3.4 等价关系与偏序关系：为什么Redis的分布式锁和Git的版本合并，都依赖同一套数学结构？
等价关系（自反、对称、传递）将集合划分为互不相交的等价类。笔记以“模m同余”为例：
Z被划分为m个类[0],[1],...,[m-1]，每个类内元素可互换（如哈希表中同余的键映射到同一桶）。Redis分布式锁的“租约续期”本质是维护一个等价类：所有持有相同锁标识的客户端，被视为同一逻辑实体，其操作需满足原子性。偏序关系（自反、反对称、传递）定义可比较性。笔记用“整除关系
|在N⁺上”为例：2|4但2∤3，故3与2不可比较。Git的提交DAG中，“祖先关系”是偏序：若提交A是B的祖先，则A ≤ B；但两个并行分支的提交互不祖先，故不可比较。git merge-base求最近公共祖先，正是在此偏序集上找最大下界（meet）。
注意：笔记强调“全序是偏序的特例”，要求任意两元素可比较。数据库的
ORDER BY排序必须基于全序（如时间戳），而Elasticsearch的_score排序基于偏序（分数可相同，需二次排序）。
3.5 避坑：集合与关系运算的隐性陷阱
现象：用
A - B = A ∩ ~B计算集合差，但在SQL中写SELECT * FROM A WHERE id NOT IN (SELECT id FROM B)却返回空结果。
原因：NOT IN子查询若含NULL，整个条件为UNKNOWN（三值逻辑），被WHERE过滤。而集合差A - B定义中，~B是相对于全集的补集，不含NULL语义。
解决：SQL中改用NOT EXISTS或在子查询加WHERE id IS NOT NULL。现象：认为关系
R的逆R⁻¹的矩阵是M_R的转置，故R⁻¹的传递闭包等于M_R^T的Warshall结果。
原因：R⁻¹的传递闭包是(R⁻¹)⁺，而(R⁻¹)⁺ = (R⁺)⁻¹（逆与闭包可交换），其矩阵确实是M_{R⁺}^T。但直接对M_R^T运行Warshall，得到的是(R⁻¹)⁺的矩阵，与R⁺的矩阵互为转置，而非相等。
解决：若需R⁺，先算R的闭包再转置；若需(R⁻¹)⁺，先转置再算闭包——二者结果矩阵互为转置。现象：将“偏序集的哈斯图”画成有向图，但删除所有传递边后，误删了覆盖关系边。
原因：哈斯图只保留覆盖关系（a < b且不存在c使a < c < b）。笔记强调：a覆盖b当且仅当a > b且a是b的极小上界。例如在整除偏序中，6覆盖2和3，但不覆盖1（因1<2<6）。
解决：画哈斯图时，对每对a>b，检查是否存在c满足a>c>b；若存在，则(a,b)边非覆盖边，应删除。现象：用笛卡尔积
A×B表示API请求参数组合，但实际调用量远超|A|×|B|。
原因：A×B是所有可能组合，但业务约束（如“选了套餐A则不能选附加服务B”）使其成为A×B的子集，即一个二元关系。笔记指出：API参数校验的本质，是定义一个关系R ⊆ A×B并验证(a,b)∈R。
解决：将参数约束建模为关系R，用关系数据库的外键或应用层的R.has(a,b)方法校验，而非枚举笛卡尔积。
4. 代数系统与图论：为什么密码学的RSA和前端路由的嵌套路由，共享同一个群论内核？
4.1 群的公理化：如何用四个方程理解“对称性”的本质？
群(G, *)是一个集合G配一个二元运算*，满足：
- 封闭性：
∀a,b∈G, a*b∈G - 结合律：
∀a,b,c∈G, (a*b)*c = a*(b*c) - 单位元：
∃e∈G, ∀a∈G, e*a = a*e = a - 逆元：
∀a∈G, ∃a⁻¹∈G, a*a⁻¹ = a⁻¹*a = e
笔记强调：这四条公理共同刻画了“可逆变换”的代数结构。以“平面刚体运动”为例：
G是所有平移、旋转、反射的集合*是变换复合（先做a再做b）e是恒等变换（不动）a⁻¹是a的逆变换（如旋转θ的逆是旋转-θ）
RSA加密的数学基础Zₙ*（模n乘法群）完美体现此结构：n=pq，Zₙ* = {x∈[1,n-1] | gcd(x,n)=1}，运算为模n乘法。其单位元是1，每个元素x有逆元y满足xy≡1 (mod n)（由裴蜀定理保证）。加密c = mᵉ mod n是群中元素的幂运算，解密m = cᵈ mod n是求逆元的幂，因为ed ≡ 1 (mod φ(n))，故cᵈ = (mᵉ)ᵈ = mᵉᵈ = m¹⁺ᵏφ⁽ⁿ⁾ = m·(mφ⁽ⁿ⁾)ᵏ ≡ m·1ᵏ = m (mod n)。
4.2 格与布尔代数：为什么React的虚拟DOM diff和数据库的查询优化，都在求“最小上界”？
格(L, ∧, ∨)是一个偏序集，其中任意两元素a,b都有最大下界（meet）a∧b和最小上界（join）a∨b。笔记指出：布尔代数是满足分配律、有界、有补的格。
- React虚拟DOM：新旧两棵DOM树的diff，本质是求两个树结构的“差异格”。
a∧b是最大公共子树（LCA），a∨b是最小包含两棵树的结构（即合并后的树）。diff(a,b) = (a∨b) - (a∧b)给出需更新的部分。 - 数据库查询优化：两个查询计划
P₁,P₂的代价可视为格中元素。P₁∧P₂是同时满足两者约束的最优计划（交集），P₁∨P₂是兼容两者的最宽松计划（并集）。优化器在格中搜索cost(P)的最小值。
笔记用布尔代数的“有限布尔代数表示定理”收束：任何含2ⁿ个元素的有限布尔代数，都同构于幂集代数P({1,2,...,n})。这意味着：前端状态管理（如Redux）中，n个布尔开关的所有可能状态（2ⁿ种），构成一个布尔代数，其运算∧（AND）、∨（OR）、¬（NOT）完全对应集合的交、并、补。状态归一化的本质，就是将状态映射到幂集代数的同构体上。
4.3 图论基础：为什么欧拉回路存在性判定，比哈密顿回路简单三个数量级？
欧拉回路（遍历所有边恰好一次）：存在当且仅当图连通且所有顶点度数为偶数。笔记给出充要性证明：
必要性：回路中每次进入顶点必离开，故度数为偶。
充分性：构造性证明——从任一点出发贪心行走，遇死路时必回到起点（因度数偶），再从已走路径中找仍有未用边的顶点继续，最终拼接成回路。算法复杂度 O(|E|)。哈密顿回路（遍历所有顶点恰好一次）：NP完全问题，无多项式判定算法。笔记对比：欧拉回路关注边的全局覆盖，其约束（度数）是局部可验证的；哈密顿回路关注顶点的全局排列，需验证所有
|V|!种排列，约束无法局部分解。
提示：笔记在“匹配问题”部分指出：霍尔婚姻定理
|N(S)| ≥ |S|（S的邻居数≥S的大小）是二分图存在完美匹配的充要条件。这与网络流中的“最大流最小割”定理同构——N(S)是S的割集，|S|是流量下界。Kubernetes的Pod调度器，正是用此定理验证节点资源（右部）能否满足Pod需求（左部）。
4.4 树与生成树：为什么Spanning Tree Protocol（STP）和微服务注册中心，都依赖“无环连通子图”？
树是无环连通图，n个顶点的树恰有n-1条边。生成树是包含图所有顶点的极小连通子图。笔记强调：生成树是图的“骨架”，它保留连通性，剔除所有冗余边（环）。
STP协议：交换机网络中，物理环路会导致广播风暴。STP通过选举根桥、计算到根的最短路径，将冗余链路置于阻塞态，最终形成一棵以根桥为根的生成树。笔记手绘拓扑图，标出“指定端口”（转发）和“根端口”（到根路径最优），指出：阻塞的端口，正是生成树算法中被剔除的环边。
微服务注册中心（如Eureka）：服务实例注册时，注册中心维护一个服务名到实例列表的映射。当某实例宕机，需通知所有依赖服务。若采用广播，消息数爆炸；若构建生成树，根节点（注册中心）向子节点分发，子节点再向其子节点分发，消息总数为
O(|V|)。笔记指出：服务发现的“健康检查传播”，本质是在服务实例图上维护一棵动态生成树。
4.5 避坑：代数与图论的典型误用
现象：在实现权限系统时，将角色继承关系建模为群，用
roleA * roleB表示权限合并。
原因：角色继承是偏序关系（Admin ≥ User），满足反对称性，而群运算要求每个元素有逆元——“撤销Admin权限”不等于获得一个新角色，而是降级为User。
解决：用格建模：roleA ∧ roleB是最小公共角色（交集权限），roleA ∨ roleB是最大角色（并集权限）。RBAC模型天然构成格。现象：用Dijkstra算法求无向图两点间最短路径，但图中存在负权边，结果错误。
原因：Dijkstra基于贪心，要求边权非负以保证“首次松弛即最短”。负权边破坏此性质（如A→B权-5，B→C权1，A→C权10，则A→B→C更短，但Dijkstra先确定A→C为10）。
解决：负权图用Bellman-Ford（检测负环）或SPFA。笔记强调：Dijkstra本质是优先队列实现的BFS，其正确性依赖于边权构成的“度量空间”。现象：认为完全图
Kₙ的生成树数是n^(n-2)（Cayley公式），故在n个微服务间随机选n-1条边就能构成生成树。
原因：Cayley公式给出的是标号完全图的生成树总数，但随机选边可能形成环或不连通。例如n=4，4²=16棵生成树，但随机选3条边的组合有C(6,3)=20种，其中4种含环（三角形+孤立点），故成功概率仅16/20=0.8。
解决：用Kruskal或Prim算法构造，或使用Wilson算法（基于循环消除的随机游走）生成均匀随机生成树。现象：将“图的连通分量”等同于“强连通分量”，在有向图中用并查集求解。
原因：并查集只能处理无向图的连通性（u-v边提供双向可达）。有向图的强连通分量（SCC）要求u→v且v→u，需Kosaraju或Tarjan算法。
解决：有向图连通性分三层：弱连通（忽略方向）、单向连通（u→v或v→u）、强连通（u↔v）。笔记建议：先用并查集求弱连通分量，再对每个分量运行Tarjan求SCC。
5. 数论与计数原理：为什么密码学的素数测试和推荐系统的多样性，都依赖“容斥原理”的变形？
5.1 素数理论：从算术基本定理到RSA的密钥生成
算术基本定理：每个大于1的整数，有唯一素因子分解（不计顺序）。笔记强调“唯一性”的威力：它使gcd(a,b)和lcm(a,b)可由素因子幂次的min/max直接计算。例如a=2³·3²·5,b=2²·3⁴·7，则gcd=2²·3²,lcm=2³·3⁴·5·7。
RSA密钥生成依赖此定理：
- 选大素数
p,q→n=pq - 计算
φ(n)=(p-1)(q-1)（因n的素因子只有p,q） - 选
e满足1<e<φ(n),gcd(e,φ(n))=1 - 求
d使ed≡1 (mod φ(n))（即e在Z_φ₍ₙ₎*中的逆元）
关键点：φ(n)的计算必须知道p,q，否则需分解n——这正是RSA安全性的基石。笔记在“费马小定理”旁批注：“aᵖ⁻¹≡1 (mod p)是Z_p*为p-1阶循环群的体现，而aᵈ ≡ a (mod p)当d≡1 (mod p-1)，这解释了为何mᵉᵈ ≡ m (mod p)”。
5.2 同余方程与中国剩余定理：为什么分布式ID生成器（如Snowflake）需要模运算？
线性同余方程ax≡b (mod m)有解当且仅当gcd(a,m)|b。解数为gcd(a,m)。中国剩余定理（CRT）解决方程组：
x ≡ a₁ (mod m₁) x ≡ a₂ (mod m₂) ... x ≡ aₖ (mod mₖ)当mᵢ两两互质时，存在唯一解mod M=m₁m₂...mₖ。
Snowflake ID生成：timestamp + datacenterId + machineId + sequence是64位整数。其中datacenterId和machineId可视为模2^5=32和2^5=32的余数。CRT保证：给定(dc, mc)，存在唯一x ∈ [0,1023]满足x≡dc (mod 32)且x≡mc (mod 32)？不，因模数不互质。但若设m₁=32, m₂=32，CRT不适用；实际中，datacenterId和machineId是独立字段，直接拼接，无需CRT。真正用CRT的是Shamir秘密共享：将密钥s分为k份，每份是(xᵢ, yᵢ)满足yᵢ ≡ s (mod pᵢ)，pᵢ为大素数，则k份可重构s mod Πpᵢ。
提示：笔记在“欧拉定理”部分指出：
a^φ⁽ⁿ⁾ ≡ 1 (mod n)要求gcd(a,n)=1。若a与n不互质（如a=p），则a^φ⁽ⁿ⁾ ≡ 0 (mod p)，但a^φ⁽ⁿ⁾ ≡ 1 (mod q)，故用CRT可得a^φ⁽ⁿ⁾ ≡ ? (mod n)。这正是RSA正确性证明中处理m与n不互质情形的关键。
5.3 容斥原理：为什么推荐系统要避免“信息茧房”，本质是集合交集的精确计数？
容斥原理计算并集大小：|A₁∪...∪Aₖ| = Σ|Aᵢ| - Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| - ...。笔记用“用户兴趣标签”举例：设A₁为喜欢科技的用户集，A₂为喜欢体育的用户集，A₃为喜欢娱乐的用户集。平台想推送“至少
本文还有配套的精品资源，点击获取
