离散数学

离散数学是分析程序与算法的底层语言。建议遵循以下经典学习路径：

1. 命题、谓词与证明技巧；
2. 集合、函数与关系；
3. 归纳法与递归；
4. 计数与组合数学；
5. 图与树；
6. 离散概率。

本页提供证明与有限结构的入门速查，不试图覆盖整门组合数学或图论。Berkeley CS 70 系统讲解证明与概率；具体算法笔记见计算机科学。

命题与证明

命题有真有假；$P(n)$ 这样的谓词，需要指定变量或加上量词，才能成为命题。全称命题 $\forall n\,P(n)$ 需要覆盖所有允许的 $n$，一个反例即可推翻；存在命题 $\exists n\,P(n)$ 则只需给出一个满足条件的对象。定义域不能省略：“每个数都有乘法逆元”在实数域上因零而不成立，对非零实数则成立。

蕴含 $P\Rightarrow Q$ 不能推出逆命题 $Q\Rightarrow P$，但等价于逆否命题 $\neg Q\Rightarrow\neg P$。例如对整数 $n$，要证明“$n$ 为偶数则 $n^2$ 为偶数”，可令 $n=2k$，得到 $n^2=2(2k^2)$。检验几个偶数只能举例，不能完成证明。

归纳法通过起始情形和“$P(n)$ 推出 $P(n+1)$”，证明所有整数 $n\ge n_0$ 都满足 $P(n)$。例如证明 $1+\cdots+n=n(n+1)/2$：$n=1$ 时成立；在假设的和上加 $n+1$，得到 $(n+1)(n+2)/2$，于是下一项成立。循环不变量也采用这一结构：初始化成立，每次迭代保持成立，退出时据此得出结论。终止性仍需另证，例如找出一个每轮严格递减的非负整数。

先确定究竟在数什么

集合中的元素互异且没有顺序。函数为每个输入指定唯一输出；关系是有序对的集合，不必满足函数的要求。计数取决于顺序是否重要、能否重复：

从 $n$ 个不同对象中选 $r$ 个	个数
有顺序、可重复	$n^r$
有顺序、不重复	$n!/(n-r)!$
无顺序、不重复	$\binom nr=n!/[r!(n-r)!]$

这里 $n,r$ 是非负整数；不重复选择时要求 $r\le n$，并约定 $0!=1$。空选择计为一种；在这个计数公式中约定 $0^0=1$。从五人中选两个不同的人，分别担任两个不同职位，有 20 种安排；若只组成两人小组，则有 10 种，因为每组在有序计数中被算了两次。只有基本结果等可能时，才能用“有利结果数除以总结果数”计算概率。

图、树与有限博弈

图 $G=(V,E)$ 由顶点和边组成。使用时要说明边是否有向、是否允许自环和重边。有限简单无向树是连通无环图；若有 $n\ge1$ 个顶点，就有 $n-1$ 条边，任意两点之间恰有一条简单路径。仅靠边数不能判定树：一个三角形加一个孤立顶点，有四个顶点和三条边，却不连通。

游戏树表示行动历史，而不只是互不相同的棋盘局面：不同历史可能到达同一局面。有限博弈的必胜策略运用归纳、不变量和树，区分策略的存在性证明、构造与执行。

我的阅读 · 打开过的笔记会记在当前浏览器里。