附录 A：常用符号表¶
附录导引
本页保留原讲义附录锚点，集中放置符号、证明模板、更新记录和后续扩展边界。
参考资料与引用边界¶
- 整理者：Lumner。
- 课程来源：根据
DM/目录下现有离散数学课件整理。 - 原始讲义文件：
note/离散数学讲义.md。 - 引用边界：附录用于辅助复习，不替代课程正式教材、教师课件或考试要求。
| 符号 | 含义 |
|---|---|
| \(\neg p\) | 非 \(p\) |
| \(p\land q\) | \(p\) 且 \(q\) |
| \(p\lor q\) | \(p\) 或 \(q\) |
| \(p\to q\) | 若 \(p\) 则 \(q\) |
| \(p\leftrightarrow q\) | \(p\) 当且仅当 \(q\) |
| \(\forall x\) | 对所有 \(x\) |
| \(\exists x\) | 存在 \(x\) |
| \(\exists!x\) | 存在唯一 \(x\) |
| \(A\subseteq B\) | \(A\) 是 \(B\) 的子集 |
| \(A\cup B\) | 并集 |
| \(A\cap B\) | 交集 |
| \(A-B\) | 差集 |
| \(\mathcal P(A)\) | 幂集 |
| $ | A |
| \(f:A\to B\) | 从 \(A\) 到 \(B\) 的函数 |
| \(\lfloor x\rfloor\) | 下取整 |
| \(\lceil x\rceil\) | 上取整 |
| \(O(g(n))\) | 渐近上界 |
| \(\Omega(g(n))\) | 渐近下界 |
| \(\Theta(g(n))\) | 同阶增长 |
| \(\binom nr\) | 组合数 |
| \(P(n,r)\) | r 排列数 |
| \(S(n,k)\) | 第二类 Stirling 数 |
| \(R^{-1}\) | 逆关系 |
| \(S\circ R\) | 关系复合 |
| \(R^n\) | 关系的 n 次幂 |
| \([a]\) | 元素 \(a\) 的等价类 |
附录 B：常用证明模板¶
直接证明模板¶
要证 \(p\to q\)。
假设 \(p\) 成立。根据定义、已知定理和代数变形推出 \(q\) 成立。因此 \(p\to q\) 成立。
逆否证明模板¶
要证 \(p\to q\)。
改证 \(\neg q\to\neg p\)。假设 \(\neg q\) 成立，推出 \(\neg p\) 成立。由于原命题与逆否命题等价，故 \(p\to q\) 成立。
反证法模板¶
要证 \(p\)。
假设 \(\neg p\) 成立。由此推出矛盾，例如 \(r\land\neg r\)，或与已知定理矛盾。因此假设错误，\(p\) 成立。
分情况证明模板¶
要证 \((p_1\lor p_2\lor\cdots\lor p_n)\to q\)。
分别证明 \(p_1\to q\)、\(p_2\to q\)、...、\(p_n\to q\)。由于这些情况覆盖全部可能，所以结论成立。
数学归纳法模板¶
要证对所有 \(n\ge b\)，\(P(n)\) 成立。
基础步：证明 \(P(b)\) 成立。
归纳步：任取 \(k\ge b\)，假设 \(P(k)\) 成立，证明 \(P(k+1)\) 成立。
结论：由数学归纳法，\(P(n)\) 对所有 \(n\ge b\) 成立。
强归纳模板¶
要证对所有 \(n\ge b\)，\(P(n)\) 成立。
基础步：证明初始情形成立。
归纳步：任取 \(k\ge b\)，假设 \(P(b),P(b+1),\ldots,P(k)\) 全部成立，证明 \(P(k+1)\) 成立。
结论：由强归纳法，命题成立。
结构归纳模板¶
对递归定义的对象证明性质 \(P\)。
基础步：证明所有基础对象满足 \(P\)。
递归步：假设构造新对象所用的已有对象满足 \(P\)，证明新对象也满足 \(P\)。
结论：所有递归生成的对象都满足 \(P\)。
附录 C：后续更新记录¶
| 日期 | 更新内容 |
|---|---|
| 2026-05-13 | 根据 DM/ 目录现有课件生成初版讲义，覆盖第 1、2、3、5、6、8、9 章，并为第 4、7 章和矩阵细节保留后续扩展。 |
附录 D：后续扩展清单¶
- 第 2.6 节矩阵：补充矩阵运算、0-1 矩阵、布尔积例题。
- 第 4 章：等待新课件后确定主题。
- 第 7 章：等待新课件后确定主题。
- 第 9 章：若后续出现偏序关系、Hasse 图、格论或图论内容，可在第 9 章后扩展。
- 课后题详解：当前只整理知识点，未展开课件中所有作业题。