大学第3阶段数学知识讲解 · 命题逻辑与证明方法至二阶线性方程与振动

返回分篇目录

知识讲解 · 公式速查 · 逐点习题

本版采用大学四阶段建议路线，专业、学校和选课顺序可能不同，不对应统一教材或固定学期。覆盖口径：本页列出的 22 个知识点；配套 44 道习题，每点两题。 它不声称穷尽大学数学，专业拓展只提供明确的入门范围。

大学第3阶段数学知识讲解

知识讲解 · 公式速查 · 逐点习题

本版采用大学四阶段建议路线，专业、学校和选课顺序可能不同，不对应统一教材或固定学期。覆盖口径：本页列出的 22 个知识点；配套 44 道习题，每点两题。 它不声称穷尽大学数学，专业拓展只提供明确的入门范围。

把证明、离散结构、微分方程、数值方法和优化联系起来。离散数学可与分析课程并行；数值计算应结合误差、条件数与稳定性一起练习，不能只背迭代公式。

本版知识点清单

编号	知识点	配套练习
u3-01	命题逻辑与证明方法	题 1、2
u3-02	集合、关系与等价分类	题 3、4
u3-03	组合计数与容斥原理	题 5、6
u3-04	递推关系与生成函数	题 7、8
u3-05	图、度数与连通性	题 9、10
u3-06	树、生成树与树结构	题 11、12
u3-07	Euler 路径与 Hamilton 回路	题 13、14
u3-08	最短路径与最小生成树	题 15、16
u3-09	可分离变量微分方程	题 17、18
u3-10	一阶线性微分方程	题 19、20
u3-11	二阶线性方程与振动	题 21、22
u3-12	微分方程组与平衡稳定性	题 23、24
u3-13	数值误差、条件数与稳定性	题 25、26
u3-14	非线性求根：二分与 Newton 法	题 27、28
u3-15	插值与逼近	题 29、30
u3-16	数值积分与误差阶	题 31、32
u3-17	微分方程的数值解	题 33、34
u3-18	线性规划与可行域	题 35、36
u3-19	对偶、弱对偶与互补松弛	题 37、38
u3-20	凸优化与梯度下降	题 39、40
u3-21	网络流与割	题 41、42
u3-22	整数规划与动态规划	题 43、44

顶点表示对象，边表示关系。最短路、生成树和网络流的目标不同，题目中须分别建立模型。

命题逻辑与证明方法

证明把明确的前提通过有效推理连接到结论。蕴含的逆命题未必成立，逆否命题与原命题等价。全称命题可用一个反例否定；存在命题只需给出合适实例。归纳法必须同时给出起点和从任意第 $n$ 步到下一步的论证。

关键关系与条件

$P\Rightarrow Q$ 等价于 $\mathrm{\neg }Q\Rightarrow \mathrm{\neg }P$。$\mathrm{\neg }(\mathrm{\forall }x,P(x))$ 等价于 $\mathrm{\exists }x,\mathrm{\neg }P(x)$；$\mathrm{\neg }(\mathrm{\exists }x,P(x))$ 等价于 $\mathrm{\forall }x,\mathrm{\neg }P(x)$。归纳法：证明 $P(1)$ 与对所有 $n\ge 1$ 的 $P(n)\Rightarrow P(n+1)$。

公式定位 · 练习与讲解

集合、关系与等价分类

关系描述集合元素之间的关联。自反、对称、传递同时成立时为等价关系，它把集合划分为互不重叠的等价类。偏序则用自反、反对称、传递刻画“先后”或“包含”，不要求所有元素都可比较。函数的单射、满射分别关注不合并输入与覆盖目标集合。

关键关系与条件

同余 $a\equiv b(\mathrm{mod}m)$ 定义为 $m\mid (a-b)$（整数 $m\ge 1$），是等价关系。单射：$f(x)=f(y)\Rightarrow x=y$；满射：对陪域每个 $y$ 存在原像；双射同时满足二者。有限集合上的等价类构成划分。

公式定位 · 练习与讲解

组合计数与容斥原理

乘法原理用于连续选择，分类相加要求各类互斥。排列区分顺序，组合不区分顺序。容斥原理先加各集合，再纠正重复计数；抽屉原理通过数量比较证明某种重复必然存在。计数题先确定对象是否可区分、是否允许重复。

关键关系与条件

$P(n,k)=n!/(n-k)!$，$(\genfrac{}{}{0ex}{}{n}{k})=n!/[k!(n-k)!]$。$|A\cup B|=|A|+|B|-|A\cap B|$。把 $N$ 个对象放入 $m$ 个盒子，至少一盒含 $\lceil N/m\rceil$ 个对象。

公式定位 · 练习与讲解

递推关系与生成函数

递推关系由先前状态定义后续项，初始条件决定具体序列。线性常系数递推可用特征方程求解；生成函数把整个序列编码为形式幂级数，通过代数运算得到递推或显式公式。形式幂级数运算可以不讨论数值收敛，但代入具体数值时必须检查。

关键关系与条件

若 $a_n=r{a}_{n-1}$ 且 $a_0=c$，则 $a_n=c{r}^n$。生成函数 $A(z)=\sum _{n\ge 0}{a}_n{z}^n$；常数序列 $1$ 的生成函数为 $1/(1-z)$，序列 $n$ 为 $z/(1-z{)}^2$（形式恒等，数值解释取 $|z|<1$）。

公式定位 · 练习与讲解

图、度数与连通性

图由顶点与边组成，可描述网络关系。本篇简单无向图没有自环和重边。顶点度数是相邻边数，连通表示任意两点之间存在路径；邻接矩阵则把图转成线性代数对象。路径长度按边数计算，带权图另用权重和定义距离。

关键关系与条件

无向图握手定理：$\sum _{v\in V}\mathrm{deg}v=2|E|$，所以奇度顶点个数为偶数。简单无向图邻接矩阵 $A$ 对称，$A_{ij}=1$ 表示有边。$(A^k{)}_{ij}$ 是从 $i$ 到 $j$ 长为 $k$ 的游走数（允许重复顶点）。

公式定位 · 练习与讲解

树、生成树与树结构

树是连通且无环的无向图，任意两点之间恰有一条简单路径。生成树保留原图所有顶点，只选择足够连接它们且不成环的边。树常用于层级结构、网络骨架和递归算法；有根树中的父子关系来自选定根节点，不是无向图本身额外的边。

关键关系与条件

$n$ 个顶点的有限树有 $n-1$ 条边。对有限简单无向图，连通且有 $n-1$ 条边等价于树。完全图 $K_n$（$n\ge 2$）的标号生成树数为 $n^{n-2}$（Cayley 公式）。

公式定位 · 练习与讲解

Euler 路径与 Hamilton 回路

Euler 问题要求每条边恰经过一次，Hamilton 问题要求每个顶点恰访问一次。二者关注对象不同。对于所有非孤立顶点连通的无向图，奇度顶点数量完全决定 Euler 路径的存在；Hamilton 回路没有同样简单的度数充要判据。

关键关系与条件

有限无向图的非孤立部分连通时：所有度数为偶数则有 Euler 回路；恰有两个奇度顶点则有从一个奇点到另一个奇点的 Euler 通路。$n\ge 3$ 的简单图若最小度数至少 $n/2$，则有 Hamilton 回路（Dirac 充分条件，非必要）。

公式定位 · 练习与讲解

最短路径与最小生成树

最短路径最小化指定端点之间的路径权重，最小生成树最小化连接全部顶点的总边权。Dijkstra 用已确定最短距离扩展，要求边权非负；Kruskal 按边权从小到大选不成环的边，用于连通无向图的生成树。负权最短路需要其他算法及负环检查。

关键关系与条件

最短路松弛：$d(v)\leftarrow min\{d(v),d(u)+w(u,v)\}$。最小生成树含 $|V|-1$ 条边。割性质：对任意割，跨割的唯一最轻边必属于每一棵最小生成树；并列最轻时可选择某条用于某棵最小生成树。

公式定位 · 练习与讲解

可分离变量微分方程

微分方程联系未知函数与导数，初值选择具体解。可分离变量方程能把未知函数相关项与自变量相关项分开积分；除以函数前要保留使该函数为零的平衡解。得到隐式解后还要检查定义域和初值，不能越过使方程失去意义的点。

关键关系与条件

$y^{\prime }=g(x)h(y)$ 在 $h(y)\ne 0$ 的区间可写成 $\int \mathrm{d}y/h(y)=\int g(x)\mathrm{d}x+C$。若 $h(c)=0$，则 $y\equiv c$ 为平衡解。$y^{\prime }=ky$ 的解为 $y=C{e}^{kx}$。

公式定位 · 练习与讲解

一阶线性微分方程

一阶线性方程中未知函数及其导数只以一次形式出现。积分因子把左侧转成一个乘积的导数，进而直接积分。连续系数和连续外力在区间上保证每个初值的唯一解；非齐次解可理解为自然响应与外部输入响应相加。

关键关系与条件

对 $y^{\prime }+p(x)y=q(x)$，令 $\mu (x)=e^{\int p(x)\mathrm{d}x}$，则 $(\mu y{)}^{\prime }=\mu q$，故 $y={\mu }^{-1}(\int \mu q\mathrm{d}x+C)$。若 $p,q$ 在含初值点的区间连续，该初值问题有唯一解。

公式定位 · 练习与讲解

二阶线性方程与振动

常系数二阶齐次方程可用指数试探导出特征方程；互异实根、重根、共轭复根对应不同解型。无阻尼系统受到固有频率的周期外力时会出现共振，试探特解需要乘额外的 $x$ 因子。两个初值通常决定两个积分常数。

关键关系与条件

$a{y}^{″}+b{y}^{\prime }+cy=0$（$a\ne 0$）的特征方程为 $a{r}^2+br+c=0$。互异实根时 $y=C_1{e}^{r_{1}x}+C_2{e}^{r_{2}x}$；重根 $r$ 时 $y=(C_1+C_{2}x)e^{rx}$；根 $\alpha \pm i\beta$ 时 $y=e^{\alpha x}(C_1\cos \beta x+C_2\sin \beta x)$。

公式定位 · 练习与讲解