离散数学里有一章叫“基本离散结构”标题列了五个东西集合、函数、序列、和式还有矩阵。当年学这章时我第一反应是“这几个概念拆开都认识合在一起不知道在讲什么”。直到后来写代码、刷算法题、做数据分析才慢慢意识到这五样东西其实就是计算机里“数据组织方式”的数学骨架。这篇笔记我想把这五块串起来讲一遍重点说清楚它们各自的定义、背后的逻辑、常见的应用场景以及我踩过的那些坑。不管你是正在准备离散数学考试还是被集合去重、函数设计、子序列动态规划、矩阵维度不匹配折磨过的程序员读下去多少会有些帮助。1. 先建立整体框架为什么这些结构都是“离散”的1.1 连续与离散的分水岭数学世界里连续的东西就像一条没有缝隙的线而离散的东西是一堆可数、可编号的点。计算机内存再大存储单元也是有限的所以计算机天然只能处理离散量。离散数学之所以被叫作“离散”就是因为它研究的是这种可数的、可以逐步推导的结构。集合、函数、序列、和式、矩阵五者有一个共同点它们都由有限或可数的元素组成并且可以通过穷举、递推、枚举等有限步骤来处理。我见过不少同学觉得“离散数学和编程没关系”这个想法其实很亏。你写循环就是在遍历一个序列写条件分支就是在做集合划分用哈希表点查本质上是在构造一个函数。理解这些数学结构会帮助你更清楚地知道代码为什么这样写边界条件为什么这样定。1.2 五个结构之间的互相支撑这五个结构并不是彼此孤立的考试题它们之间有一条认知链条集合是最底层的语言用来描述“有哪些对象”。函数是集合之间的映射用来描述“从一个集合到另一个集合的规则”。序列是带顺序的集合是“排队”后的元素列表。和式是对序列的累积操作用来算“总量”。矩阵则是一个二维表可以看成函数的表格化表达也能看成多个序列拼在一起。举个例子一张图的邻接矩阵本质上是把“顶点集合之间的边关系”用一个函数映射到0/1表格里。很多图算法比如最短路径、连通性判断最后都能化成一个矩阵运算问题。也就是说散开的五个概念在实际问题里经常组合使用。1.3 学习路径建议我给想入门的人一个学习顺序建议先把集合和集合运算搞熟尤其是幂集、文氏图和德摩根律第二步学函数重点理解单射、满射、双射以及反函数存在的条件第三步进入序列和和式训练“把重复过程写成下标和通项”的感觉最后学矩阵把它当作二维数据的承载工具。别跳着学。后来你会发现动态规划的状态转移表就是一张二维矩阵而状态转移方程里经常藏着求和的影子。这些都是同一套数学直觉。2. 集合最底层的语言2.1 集合的定义与表示方法集合是对象元素的无序聚合。它有三个基本属性确定性、互异性、无序性。确定性指的是任何一个元素要么属于集合要么不属于互异性指的是集合里不能有重复元素无序性指的是集合中元素之间没有先后顺序。集合的表示方法有两种常见写法一种是穷举法比如 {1, 2, 3}另一种是描述法比如 {x | x 是自然数且 x 5}。常用数集符号要记熟N表示自然数集Z表示整数集Q表示有理数集R表示实数集。做题的时候先看题目问的是哪个数集再决定元素范围。这里要特别提醒一个容易混淆的地方数学里的集合不允许重复元素{1, 2, 1}和{1, 2}是同一个集合。但编程语言里的数组、列表通常允许重复。所以做算法题时一旦题目里说“去重”你就应该立刻想到用集合结构。2.2 集合运算与运算律集合的基本运算包括并集、交集、差集、补集和对称差。并集就是把两个集合的元素合并交集是取公共部分差集是从一个集合中移除另一个集合的元素对称差是“只属于其中一个集合但不同时属于两个集合”的元素。这些运算满足交换律、结合律、分配律以及德摩根律。比如德摩根律(A ∪ B)^c A^c ∩ B^c(A ∩ B)^c A^c ∪ B^c。这个定律在逻辑电路设计里特别有用它告诉我们“与”和“或”之间的互换关系。幂集也是一个重要概念。集合A的幂集P(A)是A的所有子集组成的集合|P(A)| 2^|A|。为什么是2的n次方因为每个元素都有“选”和“不选”两种状态n个元素就是2的n次方种组合。这个结论在计算状态空间时非常常见比如一个开关系统的所有可能状态数。顺带说一句热词里有人搜“3个元素的集合有多少拓扑”。这问题比幂集复杂得多一个3元素集合上可以定义29种不同的拓扑结构。它涉及到开集、闭包等概念离散数学基础课一般不深入如果你只是好奇知道答案是29就行。2.3 集合的计算机实现与工程教训编程语言里常见集合实现Python 的set底层类似哈希表支持并、交、差、对称差运算。Java 的HashSet底层是 HashMap。SQL 的UNION、INTERSECT、EXCEPT分别对应并、交、差。用 Python 做集合运算很直观A {1, 2, 3} B {2, 3, 4} print(A | B) # 并集 {1, 2, 3, 4} print(A B) # 交集 {2, 3} print(A - B) # 差集 {1} print(A ^ B) # 对称差 {1, 4}但这里有一个经典坑空集合必须用set()创建不能写成{}因为{}在 Python 里是空字典。很多新手在这里翻车查半天才发现类型不对。另一个容易踩的坑是集合的元素必须可哈希。Python 里的 list 是可变的不能放进 set而 tuple 可以。所以在对列表去重时如果列表里套着 list你需要先把内层 list 转成 tuple再转成 set。我在处理 JSON 数据去重时经常遇到这个问题提前把元素结构统一能省不少时间。3. 函数关系的特殊形态3.1 从关系到函数在离散数学里函数被定义为一种特殊的关系从定义域到陪域每个输入恰好对应一个输出。这意味着每个 x 只能有一个 y不允许“一对多”。这个定义和编程中的纯函数高度一致同样的输入永远返回同样的输出没有副作用。用一句话记就是函数是“一行一个定义域元素”的关系表。判断一个关系是不是函数只需要看每个定义域元素是否都有唯一的值域元素与之对应。如果某个 x 没有对应值那就是偏函数如果每个 x 都有对应值就是全函数。算法题里经常用到的“查找表”本质上就是一个从输入到输出的函数。3.2 单射、满射、双射函数的三大性质是单射、满射、双射单射不同的输入对应不同的输出也就是一对一。满射值域等于陪域也就是每一个可能的输出都能被某个输入取到。双射既是单射又是满射也就是一一对应。为什么要区分这三个性质因为双射是反函数存在的充要条件。一个函数如果有反函数那么原函数必须是双射。这个结论在密码学、编码理论里尤其重要因为只有可逆的函数才能做无损编解码。举个例子f(x) 2x定义在整数集到整数集上它是单射但不是满射因为奇数是整数集里的元素却没有任何整数 x 能映射到它。而f(x) x 1定义在整数集到整数集上就是一个双射因为每个整数都有唯一原像。判断技巧单射用反证法假设f(x1) f(x2)推出x1 x2满射则要检查值域是否覆盖整个陪域。做题时一定要先明确定义域和陪域很多错误都出在把陪域搞混了。3.3 复合函数与反函数复合函数写作f∘g(x) f(g(x))先算内层再算外层。复合函数满足结合律但不满足交换律f∘g和g∘f通常不一样。这个知识点在函数式编程里特别有存在感比如 JavaScript 里的pipe函数就是从左到右组合多个函数const pipe (...fns) (x) fns.reduce((v, f) f(v), x);这和数学上的f∘g方向相反因为工程习惯是从左往右读但背后的原理一模一样。理解复合函数的本质你再看函数组合、中间件、Webpack loader 这类概念会感觉格外亲切。反函数则要求原函数是双射。求反函数的步骤是把 y f(x) 解出 x 关于 y 的表达式然后交换 x 和 y。比如f(x) 2x 1反函数是f^{-1}(x) (x - 1) / 2。工程里的“逆操作”比如解压、解密、反序列化都对应反函数思想。3.4 离散结构中的特殊函数除了基本函数离散数学里还有几个高频出现的函数需要额外留意。第一个是取整函数向下取整⌊x⌋和向上取整⌈x⌉。算法题里经常用它们处理分页、二分查找边界比如计算数组长度的一半时⌈n/2⌉和⌊n/2⌋的差异会导致死循环。第二个是模运算函数mod它在哈希、密码学里有大量应用。这里要注意数学里的模运算和编程语言的%在负数处理上有差异使用时必须确认语言规范。第三个是双曲函数比如 sinh、cosh。热词里提到“双曲函数的双曲角与双曲扇形面积的关系”这其实是三角函数在双曲线下的类比。虽然离散数学基础课很少深讲但它在信号处理、神经网络激活函数里经常出现作为扩展了解一下是值得的。4. 序列把集合排成队4.1 序列的定义序列在离散数学里被定义成“定义域为自然数或整数子集的函数”通常写作 a1, a2, a3, ... 或 a0, a1, a2, ...。和集合最大的区别是序列有顺序元素可以重复。所以序列在计算机里对应数组、列表、字符串这些“有序容器”。这里必须强调一个下标问题数学里的序列通常从1开始而几乎所有编程语言的下标从0开始。这不是哪个更正确而是约定不同。但当你用代码实现数学公式时经常要把下标减1。比如数学里的第 n 项在数组里就是 arr[n-1]。我在做动态规划题目时至少因为这个问题错了两三次后来养成了先用纸笔把下标范围写清楚再动手写代码的习惯。常见的序列有等差数列、等比数列、斐波那契数列以及一些更抽象的有序对序列。比如有限状态机里用 (状态, 事件) 的序列来描述系统行为这就是一个典型的离散序列应用。4.2 子序列和“不同的子序列”问题子序列和子串是两种不同的概念子串必须连续子序列不需要连续。比如字符串 abc它的子串有 ab、bc、abc但 ac 是子序列而不是子串。算法题里大量出现“最大子序列和”“最长上升子序列”“不同子序列”等全部建立在子序列这个数学概念上。热词“不同的子序列”对应一类动态规划问题。给你字符串 s 和 t问 s 中有多少个不同的子序列等于 t。经典解法是二维 DPdp[i][j] 表示 s 前 i 个字符组成的子序列中等于 t 前 j 个字符的匹配数。 如果 s[i-1] t[j-1]dp[i][j] dp[i-1][j-1] dp[i-1][j] 否则 dp[i][j] dp[i-1][j]第一项意思是“选择当前字符作为匹配”第二项意思是“跳过当前字符”。这个状态转移其实就是“选或不选”的决策模型和子集计数是同一个思想。另一个很常见的是“最长上升子序列”LIS。朴素动态规划是 O(n^2)优化后可以做到 O(n log n)核心思想是维护每个长度下的最小末尾元素。你一旦理解了序列的有序性和递推关系这些题目就不再是“背模板”而是真的在利用离散结构推导问题。4.3 序列操作与序列化工程里有一个词叫“序列化”和数学里的序列概念直接相关。序列化就是把内存中的对象转换成字节流或 JSON 字符串的过程本质上是把复杂结构拍平成有序序列以便存储和传输。热词里有人搜“PHP序列化与反序列化”在 PHP 里就是serialize()和unserialize()两个函数。虽然是语言层面的工具但背后的思维和离散数学里的“序列”一脉相承。Python 里的序列类型包括 list、tuple、string都支持索引、切片、拼接。C17 里的std::span是一个更贴近“序列视图”的工具它不拥有数据只是对一段连续内存的引用视图。用它可以避免不必要的拷贝也能有效防止越界访问。我在写 C 数据处理程序时常把 span 当作一个“轻量级序列”来用。一个实用的区间约定是切片arr[start:end]采用左闭右开即包含 start不包含 end。这样设计的优点是切片长度正好等于end - start并且相邻切片可以无缝拼接。理解这个约定就理解了为什么 Python 很多 API 的边界设计成那样。5. 和式序列的累加艺术5.1 求和符号与基本性质和式用大写希腊字母 Σ 表示阅读顺序是先看通项再看下标。写法Σ_{k1}^{n} a_k表示把 a1 加到 an。很多人看到一堆符号就晕其实求和就是一个 for 循环的数学表达。和式有两个基本性质必须掌握线性性Σ(a_k b_k) Σa_k Σb_k常数可提取Σc·a_k c·Σa_k这两个性质在化简算法复杂度公式时几乎天天用。比如你想计算三重循环的总迭代次数可以先写出内层通项再逐层求和最后利用线性性和求和公式化简。不要怕繁琐多列几步很快就能看出规律。5.2 常用求和公式有几个公式必须背下来因为它们经常出现在算法复杂度和概率统计里等差数列Σ_{k1}^{n} k n(n1)/2平方和Σ_{k1}^{n} k^2 n(n1)(2n1)/6等比数列Σ_{k0}^{n-1} ar^k a(1-r^n)/(1-r)r ≠ 1无穷等比级数Σ_{k0}^{∞} ar^k a/(1-r)条件是|r| 1为什么无穷等比级数有收敛条件因为如果公比绝对值不小于1项不会趋于0累加结果就会发散。这个条件在后面学概率论、信号系统时还会反复出现。我记得自己做双层循环复杂度分析时经常需要计算Σ_{i1}^{n} (n - i 1) n (n-1) ... 1 n(n1)/2如果没记住公式可能每次都要推到一半卡住。把公式背熟分析时间复杂度的效率会明显提升。5.3 和式在算法分析中的应用算法复杂度本质上就是和式的渐近估计。比如冒泡排序中内层比较次数是Σ_{i1}^{n-1} (n-i)化简后是n(n-1)/2也就是 O(n^2)。插入排序同理。归并排序的递推式T(n) 2T(n/2) n通过逐层展开可以变成T(n) n 2(n/2) 4(n/4) ... n log n这里的展开过程其实就是一个和式求和。要学会“变量替换”。当求和下标长得别扭时换个变量往往能立刻看清结构。比如Σ_{k0}^{n-1} k令j k1就变成Σ_{j1}^{n} (j-1) n(n-1)/2。换元之后的式子更接近模板公式。另一个容易出错的点是求和边界的开闭。如果外层从0到n-1内层从1到i那么总项数一定比从1到n要少。画一个三角形区域更直观这个技巧在双重和式交换顺序时尤其重要先对行求和再对列求和和先对列再对行结果必须相等但边界表达会变。多列几项验证总没错。6. 矩阵离散结构的二维表达6.1 矩阵的定义与基本运算矩阵是一个 m 行 n 列的数字矩形阵列写作A [a_{ij}]。它本质上是一个二维结构可以看作是把多个序列按行排列的结果。矩阵加法要求两个矩阵同型也就是行数和列数都相同标量乘法就是把每个元素都乘以一个常数。转置A^T是把行列互换(A^T)_{ij} A_{ji}。如果转置后矩阵等于原矩阵即A^T A就叫对称矩阵。对角矩阵是除主对角线外全为0的方阵单位矩阵则是对角线上全为1的特殊对角矩阵它在矩阵乘法里扮演“1”的角色。矩阵运算是很多高级算法的基础比如图像变换、社交网络分析、推荐系统。我在刚接触 numpy 的时候最喜欢用np.reshape和np.transpose来观察数据视角的变化这种“把数据换个形式看”的能力就是矩阵思维的核心。6.2 特殊矩阵和线性方程组矩阵在解线性方程组时非常有力。把系数和常数项放到一起就叫增广矩阵。用高斯消元法对增广矩阵做行变换可以逐步得到方程组的解。整个过程可以写成程序也可以手算。热词里有一条“绕任意轴旋转后坐标形式(七矩阵连乘)”这是3D图形学里的经典场景把一个点绕任意轴旋转可以拆成“平移、旋转、再平移”等多次基本变换的矩阵连乘最后组合成一个矩阵。因为矩阵乘法不满足交换律所以连乘顺序必须严格对应变换顺序。写图形学代码时如果这里搞反了物体就会跑到错误的位置。矩阵乘法本身有一个严格规则左矩阵的列数必须等于右矩阵的行数。结果矩阵的第 i 行第 j 列元素等于左矩阵第 i 行和右矩阵第 j 列的点积。实现时千万不要把维度搞错建议每次写代码前先print(A.shape)确认一下。6.3 特征值与特征分解对于一个方阵 A如果存在非零向量 v 和标量 λ使得A v λ v那么 v 是 A 的特征向量λ 是对应特征值。特征值分解就是把方阵分解成特征向量矩阵和特征值对角矩阵的组合。特征值分解在机器学习、信号处理、物理建模中无处不在。热词“解耦标定矩阵 w c v w0”也体现了矩阵的实际工程地位c 是解耦标定矩阵v 是桥路输出w0 是零漂通过矩阵运算可以把多路传感器信号解耦成各自独立的物理量。这种标定过程不复杂但对矩阵乘法和向量加法的理解要求很扎实。另外对称矩阵有非常好的性质它可以正交对角化特征值一定是实数。所以在 numpy 里处理对称矩阵时应该用np.linalg.eigh而不是通用的np.linalg.eig前者更快也更稳定。6.4 用 Python快速实现矩阵运算推荐用 numpy 做矩阵实验代码量小不容易出错。import numpy as np A np.array([[1, 2], [3, 4]]) B np.array([[0, 1], [1, 0]]) print(A.dot(B)) # 矩阵乘法 print(A B) # 等价写法 print(np.transpose(A)) print(np.linalg.eig(A)) # 特征值、特征向量注意*在 numpy 里是逐元素相乘不是矩阵乘法。矩阵乘法要用或.dot()。这个区别几乎每个 numpy 新手都会踩坑尤其是 MATLAB 习惯转过来的人更容易混淆。如果矩阵不可对角化eig可能返回复数特征值这并不一定是 bug而是矩阵本身的性质。在数据分析场景里通常更喜欢用对称矩阵或协方差矩阵作为输入这样特征值就是实数后续解释也更方便。7. 组合应用从数学结构到工程影响单独看每个概念都很基础但把它们组合起来几乎能覆盖计算机科学一大半的核心内容。首先是关系型数据库。SQL 查询里最常见的操作就是集合运算SELECT语句查出来的结果集可以做UNION、INTERSECT、EXCEPT这就是集合论在工程里的直接映射。理解集合的互异性和幂集含义可以帮你理解为什么DISTINCT关键字那么费性能——因为要额外做去重处理。其次是函数式编程。函数是一等公民map、filter、reduce这些高阶函数本质就是把函数作为参数传递到其他函数里和数学里的复合函数、映射关系同构。函数式程序员追求的“纯函数”和离散数学里“每个输入唯一对应输出”的定义完全一致。然后是算法设计。序列和和式是动态规划、复杂度分析的语言。你会看到dp[i][j]这样的二维表格它是一张矩阵状态转移方程里经常出现求和的影子。最长上升子序列、最大子序列和、编辑距离这些经典问题都是离散结构之上的优化。最后是图论与矩阵的集合应用。图的邻接矩阵、可达矩阵、拉普拉斯矩阵把图结构变成数值结构之后PageRank、社群发现、推荐算法全都可以用矩阵运算来实现。你从“离散结构”入门最后走到“机器学习”和“大规模计算”这条路线上的数学基石就是本章的五件套。8. 常见问题与排查技巧实录8.1 集合去重时报 TypeErrorPython 里最典型的报错是TypeError: unhashable type: list。原因就是集合要求元素可哈希list 是可变的所以不行。解决办法是把内层 list 转成 tuple 再放进 set。比如你要对一组坐标去重可以写set(tuple(coord) for coord in coords)。理解互异性和可哈希的联系比死记语法更有用。8.2 判断函数单射/满射时忽略了陪域很多人在判断题里说“f(x)x^2 是单射还是满射”结论完全取决于定义域和陪域的选取。如果定义在自然数到自然数x^2 是单射但不是满射如果定义在整数到自然数它是满射但不是单射如果定义在非负实数到非负实数它才是双射。做题前先把集合范围写清楚否则答案会变。8.3 序列下标差一问题数学公式里下标从1开始程序里下标从0开始。实现递推式时最常见的错误是arr[n]越界或者用n-1算错了长度。我的建议是在纸上把前几项写出来然后对着程序跑一遍。尤其是在处理dp状态转移的时候先用小规模数据验证边界能省下大量调试时间。8.4 交换和式求和顺序遇到双重求和需要交换顺序时先画出一个网格或三角形区域把当前求和覆盖的索引范围标出来再写出交换后的边界。比如Σ_{i1}^n Σ_{j1}^i等价于Σ_{j1}^n Σ_{ij}^n。如果直接靠记忆很容易把上界下界写错。多列几项验证是最后的保障。8.5 矩阵乘法维度不匹配numpy 中A.dot(B)维度不匹配时会抛ValueError。但手写矩阵乘法时你得自己负责检查。建议统一用(m, n) (n, p) - (m, p)来验算。另一个问题是乘法顺序A B和B A通常不同。在实现图形学变换时变换矩阵的连乘顺序必须和操作顺序对应否则结果完全不对。我在实际使用中发现把这些离散结构当成“数据容器”来学是最快的路径。集合是去重容器函数是变换管道序列是有序容器和式是聚合计算矩阵是二维容器。每学一个结构去查一下它在编程语言里对应的实现跑一遍再看数学定理理解深度完全不一样。比如你用 Python 实现一次集合并交差比背十遍文氏图有用用 numpy 算一次特征值比只背定义直观得多。希望这篇笔记能在你复习离散数学或写工程代码时帮你少踩几个坑。
离散结构五件套：集合、函数、序列、和式与矩阵的工程实践
离散数学里有一章叫“基本离散结构”标题列了五个东西集合、函数、序列、和式还有矩阵。当年学这章时我第一反应是“这几个概念拆开都认识合在一起不知道在讲什么”。直到后来写代码、刷算法题、做数据分析才慢慢意识到这五样东西其实就是计算机里“数据组织方式”的数学骨架。这篇笔记我想把这五块串起来讲一遍重点说清楚它们各自的定义、背后的逻辑、常见的应用场景以及我踩过的那些坑。不管你是正在准备离散数学考试还是被集合去重、函数设计、子序列动态规划、矩阵维度不匹配折磨过的程序员读下去多少会有些帮助。1. 先建立整体框架为什么这些结构都是“离散”的1.1 连续与离散的分水岭数学世界里连续的东西就像一条没有缝隙的线而离散的东西是一堆可数、可编号的点。计算机内存再大存储单元也是有限的所以计算机天然只能处理离散量。离散数学之所以被叫作“离散”就是因为它研究的是这种可数的、可以逐步推导的结构。集合、函数、序列、和式、矩阵五者有一个共同点它们都由有限或可数的元素组成并且可以通过穷举、递推、枚举等有限步骤来处理。我见过不少同学觉得“离散数学和编程没关系”这个想法其实很亏。你写循环就是在遍历一个序列写条件分支就是在做集合划分用哈希表点查本质上是在构造一个函数。理解这些数学结构会帮助你更清楚地知道代码为什么这样写边界条件为什么这样定。1.2 五个结构之间的互相支撑这五个结构并不是彼此孤立的考试题它们之间有一条认知链条集合是最底层的语言用来描述“有哪些对象”。函数是集合之间的映射用来描述“从一个集合到另一个集合的规则”。序列是带顺序的集合是“排队”后的元素列表。和式是对序列的累积操作用来算“总量”。矩阵则是一个二维表可以看成函数的表格化表达也能看成多个序列拼在一起。举个例子一张图的邻接矩阵本质上是把“顶点集合之间的边关系”用一个函数映射到0/1表格里。很多图算法比如最短路径、连通性判断最后都能化成一个矩阵运算问题。也就是说散开的五个概念在实际问题里经常组合使用。1.3 学习路径建议我给想入门的人一个学习顺序建议先把集合和集合运算搞熟尤其是幂集、文氏图和德摩根律第二步学函数重点理解单射、满射、双射以及反函数存在的条件第三步进入序列和和式训练“把重复过程写成下标和通项”的感觉最后学矩阵把它当作二维数据的承载工具。别跳着学。后来你会发现动态规划的状态转移表就是一张二维矩阵而状态转移方程里经常藏着求和的影子。这些都是同一套数学直觉。2. 集合最底层的语言2.1 集合的定义与表示方法集合是对象元素的无序聚合。它有三个基本属性确定性、互异性、无序性。确定性指的是任何一个元素要么属于集合要么不属于互异性指的是集合里不能有重复元素无序性指的是集合中元素之间没有先后顺序。集合的表示方法有两种常见写法一种是穷举法比如 {1, 2, 3}另一种是描述法比如 {x | x 是自然数且 x 5}。常用数集符号要记熟N表示自然数集Z表示整数集Q表示有理数集R表示实数集。做题的时候先看题目问的是哪个数集再决定元素范围。这里要特别提醒一个容易混淆的地方数学里的集合不允许重复元素{1, 2, 1}和{1, 2}是同一个集合。但编程语言里的数组、列表通常允许重复。所以做算法题时一旦题目里说“去重”你就应该立刻想到用集合结构。2.2 集合运算与运算律集合的基本运算包括并集、交集、差集、补集和对称差。并集就是把两个集合的元素合并交集是取公共部分差集是从一个集合中移除另一个集合的元素对称差是“只属于其中一个集合但不同时属于两个集合”的元素。这些运算满足交换律、结合律、分配律以及德摩根律。比如德摩根律(A ∪ B)^c A^c ∩ B^c(A ∩ B)^c A^c ∪ B^c。这个定律在逻辑电路设计里特别有用它告诉我们“与”和“或”之间的互换关系。幂集也是一个重要概念。集合A的幂集P(A)是A的所有子集组成的集合|P(A)| 2^|A|。为什么是2的n次方因为每个元素都有“选”和“不选”两种状态n个元素就是2的n次方种组合。这个结论在计算状态空间时非常常见比如一个开关系统的所有可能状态数。顺带说一句热词里有人搜“3个元素的集合有多少拓扑”。这问题比幂集复杂得多一个3元素集合上可以定义29种不同的拓扑结构。它涉及到开集、闭包等概念离散数学基础课一般不深入如果你只是好奇知道答案是29就行。2.3 集合的计算机实现与工程教训编程语言里常见集合实现Python 的set底层类似哈希表支持并、交、差、对称差运算。Java 的HashSet底层是 HashMap。SQL 的UNION、INTERSECT、EXCEPT分别对应并、交、差。用 Python 做集合运算很直观A {1, 2, 3} B {2, 3, 4} print(A | B) # 并集 {1, 2, 3, 4} print(A B) # 交集 {2, 3} print(A - B) # 差集 {1} print(A ^ B) # 对称差 {1, 4}但这里有一个经典坑空集合必须用set()创建不能写成{}因为{}在 Python 里是空字典。很多新手在这里翻车查半天才发现类型不对。另一个容易踩的坑是集合的元素必须可哈希。Python 里的 list 是可变的不能放进 set而 tuple 可以。所以在对列表去重时如果列表里套着 list你需要先把内层 list 转成 tuple再转成 set。我在处理 JSON 数据去重时经常遇到这个问题提前把元素结构统一能省不少时间。3. 函数关系的特殊形态3.1 从关系到函数在离散数学里函数被定义为一种特殊的关系从定义域到陪域每个输入恰好对应一个输出。这意味着每个 x 只能有一个 y不允许“一对多”。这个定义和编程中的纯函数高度一致同样的输入永远返回同样的输出没有副作用。用一句话记就是函数是“一行一个定义域元素”的关系表。判断一个关系是不是函数只需要看每个定义域元素是否都有唯一的值域元素与之对应。如果某个 x 没有对应值那就是偏函数如果每个 x 都有对应值就是全函数。算法题里经常用到的“查找表”本质上就是一个从输入到输出的函数。3.2 单射、满射、双射函数的三大性质是单射、满射、双射单射不同的输入对应不同的输出也就是一对一。满射值域等于陪域也就是每一个可能的输出都能被某个输入取到。双射既是单射又是满射也就是一一对应。为什么要区分这三个性质因为双射是反函数存在的充要条件。一个函数如果有反函数那么原函数必须是双射。这个结论在密码学、编码理论里尤其重要因为只有可逆的函数才能做无损编解码。举个例子f(x) 2x定义在整数集到整数集上它是单射但不是满射因为奇数是整数集里的元素却没有任何整数 x 能映射到它。而f(x) x 1定义在整数集到整数集上就是一个双射因为每个整数都有唯一原像。判断技巧单射用反证法假设f(x1) f(x2)推出x1 x2满射则要检查值域是否覆盖整个陪域。做题时一定要先明确定义域和陪域很多错误都出在把陪域搞混了。3.3 复合函数与反函数复合函数写作f∘g(x) f(g(x))先算内层再算外层。复合函数满足结合律但不满足交换律f∘g和g∘f通常不一样。这个知识点在函数式编程里特别有存在感比如 JavaScript 里的pipe函数就是从左到右组合多个函数const pipe (...fns) (x) fns.reduce((v, f) f(v), x);这和数学上的f∘g方向相反因为工程习惯是从左往右读但背后的原理一模一样。理解复合函数的本质你再看函数组合、中间件、Webpack loader 这类概念会感觉格外亲切。反函数则要求原函数是双射。求反函数的步骤是把 y f(x) 解出 x 关于 y 的表达式然后交换 x 和 y。比如f(x) 2x 1反函数是f^{-1}(x) (x - 1) / 2。工程里的“逆操作”比如解压、解密、反序列化都对应反函数思想。3.4 离散结构中的特殊函数除了基本函数离散数学里还有几个高频出现的函数需要额外留意。第一个是取整函数向下取整⌊x⌋和向上取整⌈x⌉。算法题里经常用它们处理分页、二分查找边界比如计算数组长度的一半时⌈n/2⌉和⌊n/2⌋的差异会导致死循环。第二个是模运算函数mod它在哈希、密码学里有大量应用。这里要注意数学里的模运算和编程语言的%在负数处理上有差异使用时必须确认语言规范。第三个是双曲函数比如 sinh、cosh。热词里提到“双曲函数的双曲角与双曲扇形面积的关系”这其实是三角函数在双曲线下的类比。虽然离散数学基础课很少深讲但它在信号处理、神经网络激活函数里经常出现作为扩展了解一下是值得的。4. 序列把集合排成队4.1 序列的定义序列在离散数学里被定义成“定义域为自然数或整数子集的函数”通常写作 a1, a2, a3, ... 或 a0, a1, a2, ...。和集合最大的区别是序列有顺序元素可以重复。所以序列在计算机里对应数组、列表、字符串这些“有序容器”。这里必须强调一个下标问题数学里的序列通常从1开始而几乎所有编程语言的下标从0开始。这不是哪个更正确而是约定不同。但当你用代码实现数学公式时经常要把下标减1。比如数学里的第 n 项在数组里就是 arr[n-1]。我在做动态规划题目时至少因为这个问题错了两三次后来养成了先用纸笔把下标范围写清楚再动手写代码的习惯。常见的序列有等差数列、等比数列、斐波那契数列以及一些更抽象的有序对序列。比如有限状态机里用 (状态, 事件) 的序列来描述系统行为这就是一个典型的离散序列应用。4.2 子序列和“不同的子序列”问题子序列和子串是两种不同的概念子串必须连续子序列不需要连续。比如字符串 abc它的子串有 ab、bc、abc但 ac 是子序列而不是子串。算法题里大量出现“最大子序列和”“最长上升子序列”“不同子序列”等全部建立在子序列这个数学概念上。热词“不同的子序列”对应一类动态规划问题。给你字符串 s 和 t问 s 中有多少个不同的子序列等于 t。经典解法是二维 DPdp[i][j] 表示 s 前 i 个字符组成的子序列中等于 t 前 j 个字符的匹配数。 如果 s[i-1] t[j-1]dp[i][j] dp[i-1][j-1] dp[i-1][j] 否则 dp[i][j] dp[i-1][j]第一项意思是“选择当前字符作为匹配”第二项意思是“跳过当前字符”。这个状态转移其实就是“选或不选”的决策模型和子集计数是同一个思想。另一个很常见的是“最长上升子序列”LIS。朴素动态规划是 O(n^2)优化后可以做到 O(n log n)核心思想是维护每个长度下的最小末尾元素。你一旦理解了序列的有序性和递推关系这些题目就不再是“背模板”而是真的在利用离散结构推导问题。4.3 序列操作与序列化工程里有一个词叫“序列化”和数学里的序列概念直接相关。序列化就是把内存中的对象转换成字节流或 JSON 字符串的过程本质上是把复杂结构拍平成有序序列以便存储和传输。热词里有人搜“PHP序列化与反序列化”在 PHP 里就是serialize()和unserialize()两个函数。虽然是语言层面的工具但背后的思维和离散数学里的“序列”一脉相承。Python 里的序列类型包括 list、tuple、string都支持索引、切片、拼接。C17 里的std::span是一个更贴近“序列视图”的工具它不拥有数据只是对一段连续内存的引用视图。用它可以避免不必要的拷贝也能有效防止越界访问。我在写 C 数据处理程序时常把 span 当作一个“轻量级序列”来用。一个实用的区间约定是切片arr[start:end]采用左闭右开即包含 start不包含 end。这样设计的优点是切片长度正好等于end - start并且相邻切片可以无缝拼接。理解这个约定就理解了为什么 Python 很多 API 的边界设计成那样。5. 和式序列的累加艺术5.1 求和符号与基本性质和式用大写希腊字母 Σ 表示阅读顺序是先看通项再看下标。写法Σ_{k1}^{n} a_k表示把 a1 加到 an。很多人看到一堆符号就晕其实求和就是一个 for 循环的数学表达。和式有两个基本性质必须掌握线性性Σ(a_k b_k) Σa_k Σb_k常数可提取Σc·a_k c·Σa_k这两个性质在化简算法复杂度公式时几乎天天用。比如你想计算三重循环的总迭代次数可以先写出内层通项再逐层求和最后利用线性性和求和公式化简。不要怕繁琐多列几步很快就能看出规律。5.2 常用求和公式有几个公式必须背下来因为它们经常出现在算法复杂度和概率统计里等差数列Σ_{k1}^{n} k n(n1)/2平方和Σ_{k1}^{n} k^2 n(n1)(2n1)/6等比数列Σ_{k0}^{n-1} ar^k a(1-r^n)/(1-r)r ≠ 1无穷等比级数Σ_{k0}^{∞} ar^k a/(1-r)条件是|r| 1为什么无穷等比级数有收敛条件因为如果公比绝对值不小于1项不会趋于0累加结果就会发散。这个条件在后面学概率论、信号系统时还会反复出现。我记得自己做双层循环复杂度分析时经常需要计算Σ_{i1}^{n} (n - i 1) n (n-1) ... 1 n(n1)/2如果没记住公式可能每次都要推到一半卡住。把公式背熟分析时间复杂度的效率会明显提升。5.3 和式在算法分析中的应用算法复杂度本质上就是和式的渐近估计。比如冒泡排序中内层比较次数是Σ_{i1}^{n-1} (n-i)化简后是n(n-1)/2也就是 O(n^2)。插入排序同理。归并排序的递推式T(n) 2T(n/2) n通过逐层展开可以变成T(n) n 2(n/2) 4(n/4) ... n log n这里的展开过程其实就是一个和式求和。要学会“变量替换”。当求和下标长得别扭时换个变量往往能立刻看清结构。比如Σ_{k0}^{n-1} k令j k1就变成Σ_{j1}^{n} (j-1) n(n-1)/2。换元之后的式子更接近模板公式。另一个容易出错的点是求和边界的开闭。如果外层从0到n-1内层从1到i那么总项数一定比从1到n要少。画一个三角形区域更直观这个技巧在双重和式交换顺序时尤其重要先对行求和再对列求和和先对列再对行结果必须相等但边界表达会变。多列几项验证总没错。6. 矩阵离散结构的二维表达6.1 矩阵的定义与基本运算矩阵是一个 m 行 n 列的数字矩形阵列写作A [a_{ij}]。它本质上是一个二维结构可以看作是把多个序列按行排列的结果。矩阵加法要求两个矩阵同型也就是行数和列数都相同标量乘法就是把每个元素都乘以一个常数。转置A^T是把行列互换(A^T)_{ij} A_{ji}。如果转置后矩阵等于原矩阵即A^T A就叫对称矩阵。对角矩阵是除主对角线外全为0的方阵单位矩阵则是对角线上全为1的特殊对角矩阵它在矩阵乘法里扮演“1”的角色。矩阵运算是很多高级算法的基础比如图像变换、社交网络分析、推荐系统。我在刚接触 numpy 的时候最喜欢用np.reshape和np.transpose来观察数据视角的变化这种“把数据换个形式看”的能力就是矩阵思维的核心。6.2 特殊矩阵和线性方程组矩阵在解线性方程组时非常有力。把系数和常数项放到一起就叫增广矩阵。用高斯消元法对增广矩阵做行变换可以逐步得到方程组的解。整个过程可以写成程序也可以手算。热词里有一条“绕任意轴旋转后坐标形式(七矩阵连乘)”这是3D图形学里的经典场景把一个点绕任意轴旋转可以拆成“平移、旋转、再平移”等多次基本变换的矩阵连乘最后组合成一个矩阵。因为矩阵乘法不满足交换律所以连乘顺序必须严格对应变换顺序。写图形学代码时如果这里搞反了物体就会跑到错误的位置。矩阵乘法本身有一个严格规则左矩阵的列数必须等于右矩阵的行数。结果矩阵的第 i 行第 j 列元素等于左矩阵第 i 行和右矩阵第 j 列的点积。实现时千万不要把维度搞错建议每次写代码前先print(A.shape)确认一下。6.3 特征值与特征分解对于一个方阵 A如果存在非零向量 v 和标量 λ使得A v λ v那么 v 是 A 的特征向量λ 是对应特征值。特征值分解就是把方阵分解成特征向量矩阵和特征值对角矩阵的组合。特征值分解在机器学习、信号处理、物理建模中无处不在。热词“解耦标定矩阵 w c v w0”也体现了矩阵的实际工程地位c 是解耦标定矩阵v 是桥路输出w0 是零漂通过矩阵运算可以把多路传感器信号解耦成各自独立的物理量。这种标定过程不复杂但对矩阵乘法和向量加法的理解要求很扎实。另外对称矩阵有非常好的性质它可以正交对角化特征值一定是实数。所以在 numpy 里处理对称矩阵时应该用np.linalg.eigh而不是通用的np.linalg.eig前者更快也更稳定。6.4 用 Python快速实现矩阵运算推荐用 numpy 做矩阵实验代码量小不容易出错。import numpy as np A np.array([[1, 2], [3, 4]]) B np.array([[0, 1], [1, 0]]) print(A.dot(B)) # 矩阵乘法 print(A B) # 等价写法 print(np.transpose(A)) print(np.linalg.eig(A)) # 特征值、特征向量注意*在 numpy 里是逐元素相乘不是矩阵乘法。矩阵乘法要用或.dot()。这个区别几乎每个 numpy 新手都会踩坑尤其是 MATLAB 习惯转过来的人更容易混淆。如果矩阵不可对角化eig可能返回复数特征值这并不一定是 bug而是矩阵本身的性质。在数据分析场景里通常更喜欢用对称矩阵或协方差矩阵作为输入这样特征值就是实数后续解释也更方便。7. 组合应用从数学结构到工程影响单独看每个概念都很基础但把它们组合起来几乎能覆盖计算机科学一大半的核心内容。首先是关系型数据库。SQL 查询里最常见的操作就是集合运算SELECT语句查出来的结果集可以做UNION、INTERSECT、EXCEPT这就是集合论在工程里的直接映射。理解集合的互异性和幂集含义可以帮你理解为什么DISTINCT关键字那么费性能——因为要额外做去重处理。其次是函数式编程。函数是一等公民map、filter、reduce这些高阶函数本质就是把函数作为参数传递到其他函数里和数学里的复合函数、映射关系同构。函数式程序员追求的“纯函数”和离散数学里“每个输入唯一对应输出”的定义完全一致。然后是算法设计。序列和和式是动态规划、复杂度分析的语言。你会看到dp[i][j]这样的二维表格它是一张矩阵状态转移方程里经常出现求和的影子。最长上升子序列、最大子序列和、编辑距离这些经典问题都是离散结构之上的优化。最后是图论与矩阵的集合应用。图的邻接矩阵、可达矩阵、拉普拉斯矩阵把图结构变成数值结构之后PageRank、社群发现、推荐算法全都可以用矩阵运算来实现。你从“离散结构”入门最后走到“机器学习”和“大规模计算”这条路线上的数学基石就是本章的五件套。8. 常见问题与排查技巧实录8.1 集合去重时报 TypeErrorPython 里最典型的报错是TypeError: unhashable type: list。原因就是集合要求元素可哈希list 是可变的所以不行。解决办法是把内层 list 转成 tuple 再放进 set。比如你要对一组坐标去重可以写set(tuple(coord) for coord in coords)。理解互异性和可哈希的联系比死记语法更有用。8.2 判断函数单射/满射时忽略了陪域很多人在判断题里说“f(x)x^2 是单射还是满射”结论完全取决于定义域和陪域的选取。如果定义在自然数到自然数x^2 是单射但不是满射如果定义在整数到自然数它是满射但不是单射如果定义在非负实数到非负实数它才是双射。做题前先把集合范围写清楚否则答案会变。8.3 序列下标差一问题数学公式里下标从1开始程序里下标从0开始。实现递推式时最常见的错误是arr[n]越界或者用n-1算错了长度。我的建议是在纸上把前几项写出来然后对着程序跑一遍。尤其是在处理dp状态转移的时候先用小规模数据验证边界能省下大量调试时间。8.4 交换和式求和顺序遇到双重求和需要交换顺序时先画出一个网格或三角形区域把当前求和覆盖的索引范围标出来再写出交换后的边界。比如Σ_{i1}^n Σ_{j1}^i等价于Σ_{j1}^n Σ_{ij}^n。如果直接靠记忆很容易把上界下界写错。多列几项验证是最后的保障。8.5 矩阵乘法维度不匹配numpy 中A.dot(B)维度不匹配时会抛ValueError。但手写矩阵乘法时你得自己负责检查。建议统一用(m, n) (n, p) - (m, p)来验算。另一个问题是乘法顺序A B和B A通常不同。在实现图形学变换时变换矩阵的连乘顺序必须和操作顺序对应否则结果完全不对。我在实际使用中发现把这些离散结构当成“数据容器”来学是最快的路径。集合是去重容器函数是变换管道序列是有序容器和式是聚合计算矩阵是二维容器。每学一个结构去查一下它在编程语言里对应的实现跑一遍再看数学定理理解深度完全不一样。比如你用 Python 实现一次集合并交差比背十遍文氏图有用用 numpy 算一次特征值比只背定义直观得多。希望这篇笔记能在你复习离散数学或写工程代码时帮你少踩几个坑。
