离散数学

2026年1月考题题型及部分题目回忆

• 填空（说是填空，但里面有几题也是选择，甚至是不定项选择，不定项考到一个关于大O估计概念的。有一道要算最小生成树和最短通路，记得这两个对应的算法就可以。）

• 计算（10道：有一道判断平面图的，情境是城市修管道不交又。一道单射满射概念问题，A集合里面五个元素，B集合里面三个元素，问A到B有多少个单射，B到A有多少个单射。有一道题关系矩阵，看矩阵判断是否有自反性，对称性，反对称性，传递性，并判断是不是偏序或者等价，然后再算复合系矩阵（矩阵相乘就好），算完之后画有向图或者哈塞图。熟练掌握费马小定理和欧拉定理，要算模的逆。）

• 证明（3道：有一个证明斐波那契数列前后两项互质的，可以用数学归纳法。还有一个是证明组合数的题目，考虑特定的情况，等式一边是普通的组合问题，等式右边分情况讨论即可。）

一些嘱咐

这门课只要上课认真听，考前把常用的定理都背下来其实很难拿低分，但相应的高分也不容易，高分需要比较强的理解能力，帮助你在最后的证明题中和大家拉开差距。

tip:这门书课本板砖一样厚没什么用，不如只看老师ppt，学完一学期觉得课本0用处。

一些核心知识点（复习时请以老师给的ppt为核心，每年考试范围应该会略有不同，以下内容是2025.09~2026.01所学）

离散数学核心知识点总结

一、课程基础信息

1. 课程范围

命题逻辑、图论、集合论、函数、关系、数论、计数问题等

2. 成绩评定

• 作业（20%）：会改的！尽量做正确挣取分高点，不过错几个也不会影响很多分啦，只是说不要随便写~
• 考试（80%）：期中（闭卷30%）+ 期末（闭卷50%） （期中那30也很重要！！撰稿人就是因为期中没考好最后总评没有期末卷面高！！）

二、命题逻辑

1. 核心概念

• 命题：或真或假的陈述语句，不能既真又假
• 命题变元：用p,q,r,s等表示，真值取“真（T）”或“假（F）”
• 复合命题：由命题通过逻辑运算符组合而成

2. 逻辑运算符（优先级：¬ > ∧ > ∨ > → > ↔）

运算符	名称	符号	真值规则
否定	非	¬	¬p与p真值相反
合取	并且	∧	仅p、q均为T时，p∧q为T
析取	或者（兼或）	∨	p、q至少一个为T时，p∨q为T
异或	要么要么	⊕	p、q真值不同时为T
条件	如果则	→	仅p为T且q为F时，p→q为F
双条件	当且仅当	↔	p、q真值相同时为T

3. 关键定理

• 德·摩根定律：
  1. ¬(p∧q) ↔ ¬p∨¬q
  2. ¬(p∨q) ↔ ¬p∧¬q
  3. ¬(p→q) ↔ p∧¬q
• 等价命题：条件语句p→q与其逆否命题¬q→¬p等价；逆命题q→p与反命题¬p→¬q等价

三、量词与推理规则

1. 量词

量词类型	符号	含义	否定等价式
全称量词	∀	域中所有x	¬∀xP(x) ↔ ∃x¬P(x)
存在量词	∃	域中存在至少一个x	¬∃xP(x) ↔ ∀x¬P(x)
唯一性量词	∃!	域中恰好有一个x	-

2. 核心推理规则

• 命题逻辑推理：假言推理、取拒式、附加律、析取三段论、化简律、合取律、假言三段论、消解律
• 量化命题推理：全称实例、全称引入、存在实例、存在引入

四、证明导论

1. 专用术语

• 定理：可证明为真的重要命题；命题：次要定理；公理：不证自明的命题
• 引理：辅助证明其他结论的定理；推论：由定理直接推出的定理；猜想：待证明的命题

2. 证明方法

证明类型	适用场景	核心思路
直接证明法	p→q	假设p为真，证明q为真
反证法	p→q（直接证明困难）	假设¬q为真，证明¬p为真（证逆否命题）
等价证明法	p↔q	分别证明p→q和q→p均为真
穷举证明法	情况有限且少量	检验所有可能情况
分情形证明法	无法穷举但可分有限类	覆盖所有可能情形逐一证明
归谬证明法	缺乏直接前提	假设命题为假，推出矛盾结论
数学归纳法	∀nP(n)（n为正整数等）	基础步骤（证P(1)成立）+ 归纳步骤（证P(k)→P(k+1)）

三、图论

1. 图的基本概念与分类

• 定义：G=(V,E)，V为顶点集，E为边集
• 分类：
  • 按边：简单图（无多重边无环）、多重图（有多重边无环）、伪图（有环或多重边）
  • 按方向：有向图、无向图、混合图
  • 特殊简单图：完全图（Kₙ，每两顶点有边）、二分图（顶点分两色，同色不相邻）、完全二分图（Kₘₙ，两色顶点各m、n个）

2. 图的核心术语

• 相邻：顶点（同边端点）、边（共端点）；邻居N(v)：与v相邻的顶点集
• 顶点度：无向图deg(v)（关联边数，环计2次）；有向图入度deg⁻(v)、出度deg⁺(v)
• 握手定理：无向图∑deg(v)=2m（m为边数）；有向图∑deg⁺(v)=∑deg⁻(v)=m

3. 图的表示

• 邻接表：列出每个顶点的邻居（无向图）或出边终点（有向图）
• 邻接矩阵：简单图中aᵢⱼ=1（顶点i,j相邻），否则0；多重图中aᵢⱼ为边数

4. 同构与连通性

• 同构：两图顶点存在一一对应，保持相邻关系（图形不变量：顶点数、边数、度分布等）
• 路径相关：路径（边首尾相连）、通路（不重复顶点）、路线（不重复边）、回路（闭合通路）
• 连通性：
  • 连通图：任意两顶点有路径；连通分支：极大连通子图
  • 割点/割边：删去后连通分支数增加；边为割边当且仅当不属于任何回路
  • 点连通度κ(G)：最小删顶点数使图不连通；边连通度λ(G)：最小删边数使图不连通

5. 欧拉图与哈密顿图

类型	定义	判定条件
欧拉图	有欧拉闭合路线（过所有边）	无向图：最多1个不平凡分支，所有顶点度为偶数；有向图：最多1个不平凡分支，∀v有deg⁺(v)=deg⁻(v)
半欧拉图	有不闭合欧拉路线	无向图：最多1个不平凡分支，恰好2个顶点度为奇数
哈密顿图	有哈密顿回路（过所有顶点）	无统一判定，可参考狄拉克定理（n≥3，每个顶点度≥n/2）、欧尔定理（n≥3，不相邻顶点度和≥n）

6. 平面图与填色问题

• 平面图：存在无交叉边的画法；欧拉公式（连通）：V-E+F=2（F为面数）
• 关键推论：顶点数≥3的简单连通平面图，E≤3V-6；无三角形时E≤2V-4
• 四色定理：任意平面图4色可填（相邻面颜色不同）
• 着色数χ(G)：顶点着色最少颜色数，χ(G)≥ω(G)（ω(G)为团数），χ(G)≤1+d（d为最大顶点度）

7. 树与最优化问题

• 树的性质：无回路的连通图；n个顶点的树有n-1条边；任意两顶点有唯一通路
• 生成树：包含图所有顶点的树；连通图必有生成树
• 最优化算法：
  • 最小生成树：Kruskal算法（选无回路的最小权重边）
  • 最短通路：Dijkstra算法（从起点逐步更新最短距离）
  • 最大流：Ford-Fulkerson算法（通过增广路径迭代增流）
  • 最大流最小割定理：最大流量=最小割容量

四、函数与递推

1. 函数基础

• 定义：f:A→B，为A中每个元素指派B中唯一元素
• 核心概念：定义域（A）、陪域（B）、值域（A中元素的像集）
• 特殊函数：单射（一一对应，f(a₁)=f(a₂)→a₁=a₂）、满射（映上，∀b∈B∃a∈A使f(a)=b）、复合函数（g∘f(a)=g(f(a))）

2. 函数增长与算法复杂度

• 大O记号：f(x)∈O(g(x))，即∃C,k，∀x>k有|f(x)|≤C|g(x)|（g(x)为渐进上界）
• 常见复杂度：O(1)（常数）< O(logn)（对数）< O(n)（线性）< O(nlogn) < O(n²)（二次）< O(2ⁿ)（指数）< O(n!)（阶乘）

3. 递推关系

• 典型递推：
  • 冒泡排序：Tₙ=Tₙ₋₁+n-1，复杂度O(n²)
  • 汉诺塔：Tₙ=2Tₙ₋₁+1，复杂度O(2ⁿ)
  • 归并排序：Tₙ=2Tₙ/₂+n-1，复杂度O(nlogn)
• 分治法：将问题拆分为子问题，递推形式T(x)=a₁T(b₁x+ε₁(x))+...+aₖT(bₖx+εₖ(x))+g(x)

五、关系

1. 关系基础

• 定义：A到B的关系是A×B的子集，A上的关系是A×A的子集
• 表示：集合描述、关系矩阵（aᵢⱼ=1当(aᵢ,aⱼ)∈R）、有向图（顶点为A元素，有向边表示关系）

2. 关系的性质

性质	定义
自反性	∀a∈A，aRa
对称性	∀a,b∈A，aRb→bRa
反对称性	∀a,b∈A，aRb∧bRa→a=b
传递性	∀a,b,c∈A，aRb∧bRc→aRc

3. 特殊关系

• 偏序关系：自反、反对称、传递；偏序集(A,≤)，哈塞图（简化有向图）
• 全序关系：偏序+任意两元素可比较
• 拓扑排序：将偏序转化为全序，满足原关系优先级
• 等价关系：自反、对称、传递；等价类[x]={y∈A|x~y}，构成A的划分

六、数论

1. 整除与最大公约数

• 整除：a|b（∃k使b=ak）；除法定理：n=q·d+r（0≤r<<d）
• 最大公约数gcd(a,b)：
  • 性质：gcd(a,b)是a和b最小的正线性组合
  • 欧几里得算法：gcd(a,b)=gcd(b,a mod b)

2. 模算术

• 同余：a≡b(mod n)（n|(a-b)），等价于a mod n=b mod n
• 逆元：若a·b≡1(mod n)，则b是a模n的逆；逆存在当且仅当gcd(a,n)=1

3. 核心定理

• 费马小定理：p为质数，k不是p的倍数，则kᵖ⁻¹≡1(mod p)
• 欧拉定理：k和n互质，则k^φ(n)≡1(mod n)（φ(n)为欧拉函数，1~n中与n互质的数的个数）
• 欧拉函数：n=p₁^k₁p₂^k₂...pₘ^kₘ，则φ(n)=n(1-1/p₁)(1-1/p₂)...(1-1/pₘ)

4. RSA密码系统（公式无需记忆）

• 步骤：
  1. 接收者选两个大质数p、q（保密），令n=pq
  2. 选e与(p-1)(q-1)互质，计算e的逆d（私钥(d,n)，公钥(e,n)）
  3. 加密：m*=mᵉ mod n；解密：m=(m*)ᵈ mod n

七、计数问题

1. 基本计数法则

• 双射法则：|A|=|B|若A、B存在双射
• 乘积法则：序列第i位有nᵢ种可能，总个数=n₁×n₂×...×nₖ
• 求和法则：互不相交集合的并集大小=各集合大小之和
• 鸽巢原理：|A|>|B|，则A中至少两个元素有同一像；推广：|A|>k|B|，则至少k+1个元素同像
• 除法法则：k对1的满射f:A→B，则|A|=k|B|

2. 排列与组合

• 排列：n个元素的排列数=n!；n选k的排列数=P(n,k)=n!/(n-k)!
• 组合：n选k的组合数=C(n,k)=n!/(k!(n-k)!)，满足C(n,k)=C(n,n-k)
• 多项式系数：n个元素分m组（各组k₁,k₂,...,kₘ个），排列数=n!/(k₁!k₂!...kₘ!)

3. 二项式与多项式定理

• 二项式定理：(a+b)ⁿ=∑ₖ=₀ⁿC(n,k)aᵏbⁿ⁻ᵏ
• 多项式定理：(z₁+z₂+...+zₘ)ⁿ=∑C(n,k₁,k₂,...,kₘ)z₁^k₁z₂^k₂...zₘ^kₘ（k₁+k₂+...+kₘ=n）