本科课程 · 离散数学 ①
数理逻辑与集合论
逻辑是数学的语法，集合是数学的词汇。把推理变成计算——真值表、等值式、范式让"证明"变成机械的演算；关系与等价关系则是数据库、图论乃至程序语义的地基。
1 命题与联结词
概念能判断真假的陈述句
| 联结词 | 符号 | 真值条件 | 自然语言 |
|---|---|---|---|
| 非 | ¬P | P 假则真 | 并非…… |
| 合取 | P ∧ Q | 两者皆真 | 并且 |
| 析取 | P ∨ Q | 至少一真（相容或） | 或者 |
| 蕴含 | P → Q | 仅 P 真 Q 假时为假 | 如果…那么… |
| 等价 | P ↔ Q | 真假相同 | 当且仅当 |
蕴含的"怪论"：P 假时 P → Q 恒真（空真，vacuously true）。"如果 2 是奇数，那么月亮是奶酪做的"是真命题！这是约定，保证 P→Q ⇔ ¬P ∨ Q 的演算律成立。
2 真值表与等值演算
概念重言式、矛盾式、可满足式
重要等值式：
双重否定 ¬¬P ⇔ P；德摩根 ¬(P∧Q) ⇔ ¬P∨¬Q；
蕴含等值式 P→Q ⇔ ¬P∨Q；逆否 P→Q ⇔ ¬Q→¬P；
假言易位 (P→Q)∧(P→R) ⇔ P→(Q∧R)；分配律、吸收律同集合运算。
双重否定 ¬¬P ⇔ P；德摩根 ¬(P∧Q) ⇔ ¬P∨¬Q；
蕴含等值式 P→Q ⇔ ¬P∨Q；逆否 P→Q ⇔ ¬Q→¬P；
假言易位 (P→Q)∧(P→R) ⇔ P→(Q∧R)；分配律、吸收律同集合运算。
随堂检测命题逻辑
3 范式
概念公式的"标准像"
主析取范式：若干极小项（每个变元恰出现一次，带或不带非）的析取——"真值表中为真的行"各贡献一个极小项，是公式的指纹：两个公式等值 ⇔ 主析取范式相同。
主合取范式：极大项的合取（为假的行）。恒真式的主合取范式为空（记作 1），矛盾式的主析取范式为空（记作 0）。
求法：真值表法或等值演算（消去 →、↔，内移 ¬，化归分配律）。
主合取范式：极大项的合取（为假的行）。恒真式的主合取范式为空（记作 1），矛盾式的主析取范式为空（记作 0）。
求法：真值表法或等值演算（消去 →、↔，内移 ¬，化归分配律）。
4 命题逻辑的推理理论
概念有效的推理形式
推理有效 ⇔ 前提的合取蕴含结论是重言式。
推理规则：假言推理（P, P→Q ⊢ Q）、附加、化简、拒取式（¬Q, P→Q ⊢ ¬P）、假言三段论、析取三段论、构造性二难；
证明方法：直接法、附加前提证明法（证 P→R 时把 P 加入前提）、归谬法（把 ¬结论 加入前提推出矛盾）。
推理规则：假言推理（P, P→Q ⊢ Q）、附加、化简、拒取式（¬Q, P→Q ⊢ ¬P）、假言三段论、析取三段论、构造性二难；
证明方法：直接法、附加前提证明法（证 P→R 时把 P 加入前提）、归谬法（把 ¬结论 加入前提推出矛盾）。
5 谓词逻辑（一阶逻辑）
概念量词与辖域
量词否定等值式：¬∀x P(x) ⇔ ∃x ¬P(x)；¬∃x P(x) ⇔ ∀x ¬P(x)。
量词顺序不可交换：∀x∃y R(x,y) ≠ ∃y∀x R(x,y)——"人人有书" ≠ "有一本书人人都有"。
前束范式：所有量词提到最前（¬¬ 消去、量词辖域扩张收缩）。
量词顺序不可交换：∀x∃y R(x,y) ≠ ∃y∀x R(x,y)——"人人有书" ≠ "有一本书人人都有"。
前束范式：所有量词提到最前（¬¬ 消去、量词辖域扩张收缩）。
6 二元关系
概念关系是笛卡尔积的子集
定义：A 到 B 的关系 R ⊆ A×B。矩阵表示 M_R、关系图表示。
复合与逆：R∘S（先 S 后 R）、R⁻¹；
三大性质：自反（全对角线）、对称（矩阵对称）、传递（R∘R ⊆ R）。
闭包：自反闭包 r(R)=R∪I_A、对称闭包 s(R)=R∪R⁻¹、传递闭包 t(R)=R∪R²∪…（沃舍尔算法）。
复合与逆：R∘S（先 S 后 R）、R⁻¹；
三大性质：自反（全对角线）、对称（矩阵对称）、传递（R∘R ⊆ R）。
闭包：自反闭包 r(R)=R∪I_A、对称闭包 s(R)=R∪R⁻¹、传递闭包 t(R)=R∪R²∪…（沃舍尔算法）。
7 等价关系、划分与偏序
概念自反+对称+传递 ⇒ 分类
等价关系（自反、对称、传递）⇔ 集合的划分（等价类互不相交、并起来是全集）。例：模 n 同余把整数分成 n 类。
偏序关系（自反、反对称、传递）：哈斯图只画"盖住"边。极大/极小元（局部）、最大/最小元（全局，至多一个）。全序 = 任意两元素可比。
良序：非空子集有最小元（N 是，Z 不是）——数学归纳法的逻辑根基。
偏序关系（自反、反对称、传递）：哈斯图只画"盖住"边。极大/极小元（局部）、最大/最小元（全局，至多一个）。全序 = 任意两元素可比。
良序：非空子集有最小元（N 是，Z 不是）——数学归纳法的逻辑根基。