2.1范式：命题的标准化形式
概念卡
文字：命题变元及其否定。
简单析取式：只含析取的文字串，如 P∨¬Q∨R。简单合取式：只含合取的文字串，如 P∧¬Q∧R。
合取范式(CNF)：简单析取式的合取，形如 A₁∧A₂∧…∧Aₙ。
析取范式(DNF)：简单合取式的析取，形如 A₁∨A₂∨…∨Aₙ。
一个公式等值的范式不唯一；但主范式唯一(下节)。
定理 2.1 · 一眼判类型
简单析取式是重言式 ⟺ 同时含有某个变元及其否定(如 P∨¬P∨Q ⇔ T)。
简单合取式是矛盾式 ⟺ 同时含有某个变元及其否定(如 P∧¬P∧Q ⇔ F)。
推论：合取范式是重言式 ⟺ 每个简单析取式都是重言式；析取范式是矛盾式 ⟺ 每个简单合取式都是矛盾式。
求范式的三步法(必会)
- 消去 →、↔：蕴涵等值式 A→B⇔¬A∨B、等价等值式 A↔B⇔(A→B)∧(B→A)。
- 把 ¬ 深入到变元前：双重否定律 ¬¬A⇔A + 德摩根律 ¬(A∧B)⇔¬A∨¬B、¬(A∨B)⇔¬A∧¬B。
- 分配律展开：求析取范式时消去 A∧(B∨C)；求合取范式时消去 A∨(B∧C)。
例题思路 · 例 2.1
求 (P∧(Q→R))→S 的范式：先消 →：¬(P∧(¬Q∨R))∨S，德摩根：¬P∨(Q∧¬R)∨S。
析取范式：¬P ∨ (Q∧¬R) ∨ S
求合取范式：对 ¬P∨(Q∧¬R)∨S 用分配律把合取展开到变元层：
(¬P∨Q∨S) ∧ (¬P∨¬R∨S)
规律：先析取范式，再对其中含 ∧ 的项做分配律,就得到合取范式。
2.2小项与大项(编码必背)
概念卡
小项(布尔合取/极小项)：n 个变元的简单合取式，每个变元恰好出现一次(或其否定)。如 ¬P∧Q∧R。
大项(布尔析取/极大项)：n 个变元的简单析取式，每个变元恰好出现一次(或其否定)。如 P∨¬Q∨R。
n 个变元共有 2ⁿ 个小项、2ⁿ 个大项。
编码规则(最容易搞反)
小项：变元出现 → 1，否定 → 0。¬P∧Q∧R 编码 011，记 m₃。
大项：恰好相反，变元出现 → 0，否定 → 1。P∨¬Q∨R 编码 010，记 M₂。
下标相同的小项与大项互为否定：¬mᵢ = Mᵢ，¬Mᵢ = mᵢ。
三变元小项速查表
| 下标 | 编码 | 小项 mᵢ |
|---|
| m₀ | 000 | ¬P∧¬Q∧¬R |
| m₁ | 001 | ¬P∧¬Q∧R |
| m₂ | 010 | ¬P∧Q∧¬R |
| m₃ | 011 | ¬P∧Q∧R |
| m₄ | 100 | P∧¬Q∧¬R |
| m₅ | 101 | P∧¬Q∧R |
| m₆ | 110 | P∧Q∧¬R |
| m₇ | 111 | P∧Q∧R |
大项 Mᵢ 把表中变元换成否定、否定换成变元、∧ 换成 ∨，下标不变即可(如 M₃ = P∨¬Q∨¬R)。
性质(必背)
| 性质 | 小项 m | 大项 M |
|---|
| 真值分布 | 恰有 1 个成真赋值(按编码指派)；其余 2ⁿ−1 个成假 | 恰有 1 个成假赋值(按编码指派)；其余 2ⁿ−1 个成真 |
| 两个不同项 | mᵢ∧mⱼ ⇔ F | Mᵢ∨Mⱼ ⇔ T |
| 全体 | m₀∨m₁∨…∨m₂ₙ₋₁ ⇔ T | M₀∧M₁∧…∧M₂ₙ₋₁ ⇔ F |
记忆：小项「独真」(1 个成真)；大项「独假」(1 个成假)。全体小项析取是真、全体大项合取是假。
2.3主范式：唯一的规范形式
概念卡
主析取范式：仅由小项的析取组成。
主合取范式：仅由大项的合取组成。
定理 2.2/2.4：真值表中真值为 T 的指派对应的小项取析取 = 主析取范式；真值为 F 的指派对应的大项取合取 = 主合取范式。
定理 2.3/2.5：任何公式都存在且唯一的主范式。
求主析取范式 · 等值演算法(三步)
- 按 2.1 节求出析取范式；
- 拼全变元：简单合取式缺变元 Pᵢ 时，乘上 (Pᵢ∨¬Pᵢ) 再分配展开(排中律 + 同一律 + 分配律)：A⇔(A∧Pᵢ)∨(A∧¬Pᵢ)；
- 去掉重复小项。
例题思路 · 例 2.2 / 2.3
例 2.3：求 (P∨(Q∧R))→(P∧Q∧R) 的主析取范式。消 → 得 ¬P∨(¬Q∨¬R)∨…，展开并拼全变元后，真值表中真值为 T 的是 PQR＝000、001、010、111 四组，故：
主析取范式 = Σ(0, 1, 2, 7) (= m₀∨m₁∨m₂∨m₇)
Σ(… ) 就是「下标集合」的简写，考试填空、选择都这么写。
求主合取范式 · 互补捷径(必会)
捷径
设公式含 n 个变元，主析取范式含 k 个小项、记 Σ(S)，则主合取范式含 2ⁿ − k 个大项，下标是 S 的补集：
主合取范式 = Π(补集下标)
例：Σ(0,1,2,7) → Π(3,4,5,6)(共 2³=8 个下标，补集是剩下 4 个)。
用主范式判别公式类型(必背)
| 类型 | 主范式特征(含 n 个变元) |
|---|
| 重言式 | 主析取范式含全部 2ⁿ 个小项 |
| 矛盾式 | 主合取范式含全部 2ⁿ 个大项 |
| 可满足式 | 主析取范式至少含 1 个小项(或主合取范式至多含 2ⁿ−1 个大项) |
易错
矛盾式的主析取范式不含任何小项(记作「空析取」)；重言式的主合取范式不含任何大项。看到「主析取含 0 个小项 → 矛盾式」「主析取含满 2ⁿ 个 → 重言式」要立刻反应。
2.4有效推理 · 三种方法
概念卡
有效推理(有效结论)：一组前提 H₁,H₂,…,Hₙ 推出结论 C，当且仅当 H₁∧H₂∧…∧Hₙ ⇒ C，记为 H₁∧H₂∧…∧Hₙ ⊢ C。
定理 2.6：H₁∧…∧Hₙ ⊢ C 有效 ⟺ H₁∧…∧Hₙ→C 是重言式。
只关心形式：前提真则结论必真，不关心结论内容是否符合常识(前提矛盾时推理总是有效)。
方法一 · 真值表法
列真值表,检查有没有「前提全真、结论为假」的行——有则无效,没有则有效。
例 2.6判断 (P→R)∧(Q→R)∧(P∨Q) ⇒ R 是否有效
符号化：P＝学了离散数学，Q＝学了数据结构，R＝问题可解答。
真值表中，前提 (P→R)∧(Q→R)∧(P∨Q) 为真的行是 4、6、8 行，这三行结论 R 都为真，没有「前提真结论假」 → 推理有效。
本质：析取三段论(学了其中一门)→ 该门课的蕴含成立 → R 成立。
例 2.7反例：{P, Q→P} 能否推出 Q?
不能。真值表里 P=1、Q=0 时：前提 P 真、Q→P 真(空真)，但结论 Q 假 —— 前提真结论假，推理无效。
「Q→P」只说了 Q 蕴含 P，反过来 P 推不出 Q。
方法二 · 主范式 / 等值演算法
把 H₁∧…∧Hₙ→C 化成主析取范式：含满 2ⁿ 个小项 → 重言式 → 有效；否则无效。
例 2.8(P→Q)∧¬P 能否推出 ¬Q?(经典谬误)
演算 ((P→Q)∧¬P)→¬Q：化主析取范式只得到 Σ(0,2,3)，缺 m₁，不是重言式 → 推理无效。
语义：「天气好 → 爬山」推不出「天气不好 → 不爬山」。命题的否命题(¬P→¬Q)不等价于原命题；只有逆否命题(¬Q→¬P)才等价。
方法三 · 推理法(构造论证)
假定前提为真，按推理定律 + 等值公式逐步推出结论。每一步注明使用的规则——这是简答/证明题的规范写法。
例 2.9推理法示范：¬Q→P，¬Q∨R，¬R ⊢ P
(1) ¬Q∨R P 规则
(2) ¬R P 规则
(3) ¬Q T(1)(2) 析取三段论
(4) ¬Q→P P 规则
(5) P T(3)(4) 假言推理 ✓
写法：左侧列推导出的公式，右侧标 来源 + 规则名。P＝引入前提，T＝由已有步骤变形得到。
2.5推理规则 · 归谬法 · CP 规则
两条基本规则
P 规则(前提引入)：证明的任何步骤都可引入前提。
T 规则(结论引入/转换)：已推出的结论可作为后续前提；公式中的子公式可用等值式置换(如用 ¬P∨Q 换 P→Q)。
归谬法(反证法)
定理 2.7
若 H₁∧…∧Hₙ∧¬C 是矛盾式，则 H₁∧…∧Hₙ ⊢ C 有效。
做法：把结论的否定 ¬C 当附加前提，推到出矛盾(F),原推理即有效。逻辑上类似反证法。
例 2.10归谬法：(p∧q)→r，¬r∨s，¬s，p ⊢ q
附加 ¬q 为临时前提,推出矛盾：
(1) ¬q CP 规则(结论否定,附加前提)
(2) ¬r∨s P 规则
(3) ¬s P 规则
(4) ¬r T(2)(3) 析取三段论
(5) (p∧q)→r P 规则
(6) ¬(p∧q) T(4)(5) 拒取式
(7) ¬p∨¬q T(6) 德摩根
(8) p P 规则
(9) ¬q T(7)(8) 析取三段论
(10) q∨¬q T(1)(9) 合取引入 → 矛盾 F ✓
推出 q 与 ¬q 同时成立(矛盾),故原推理有效。
CP 规则(结论是条件式时)
定理 2.8
若 H₁∧…∧Hₙ∧R ⊢ C，则 H₁∧…∧Hₙ ⊢ R→C。
做法：结论是 R→C 时，把前件 R 当附加前提，推出 C 即可。
例 2.11CP 规则：(p∧q)→r，s→p，q ⊢ s→r
结论是 s→r,把 s 当附加前提：
(1) s CP 规则(附加前提)
(2) s→p P 规则
(3) p T(1)(2) 假言推理
(4) q P 规则
(5) p∧q T(3)(4) 合取引入
(6) (p∧q)→r P 规则
(7) r T(5)(6) 假言推理 ✓
必背：等值公式 & 推理定律(第 1 章表的整理版)
证明题每一步的「T(… ) 规则名」都从这两张表里来,务必熟到随手能用。
| 等值公式 | 形式 |
|---|
| 双重否定 | ¬¬A ⇔ A |
| 幂等 | A∨A⇔A；A∧A⇔A |
| 交换 | A∨B⇔B∨A；A∧B⇔B∧A |
| 结合 | (A∨B)∨C⇔A∨(B∨C)；(A∧B)∧C⇔A∧(B∧C) |
| 分配 | A∨(B∧C)⇔(A∨B)∧(A∨C)；A∧(B∨C)⇔(A∧B)∨(A∧C) |
| 德摩根 | ¬(A∧B)⇔¬A∨¬B；¬(A∨B)⇔¬A∧¬B |
| 同一 / 零律 | A∨F⇔A，A∧T⇔A；A∨T⇔T，A∧F⇔F |
| 排中 / 否定 | A∨¬A⇔T；A∧¬A⇔F |
| 蕴涵等值 | A→B⇔¬A∨B；¬(A→B)⇔A∧¬B |
| 假言易位 | A→B⇔¬B→¬A |
| 输出规则 | A→(B→C)⇔(A∧B)→C |
| 前件交换 | A→(B→C)⇔B→(A→C) |
| 等价等值 | A↔B⇔(A→B)∧(B→A)⇔(A∧B)∨(¬A∧¬B) |
| 等价否定 | ¬(A↔B)⇔A↔¬B |
| 推理定律 | 形式 |
|---|
| 化简律 | A∧B⇒A；A∧B⇒B |
| 附加律 | A⇒A∨B；B⇒A∨B |
| 变形附加 | ¬A⇒A→B；B⇒A→B |
| 变形化简 | ¬(A→B)⇒A；¬(A→B)⇒¬B |
| 合取引入 | A，B ⇒ A∧B |
| 假言推理 MP | A，A→B ⇒ B |
| 拒取式 MT | A→B，¬B ⇒ ¬A |
| 析取三段论 | A∨B，¬B ⇒ A |
| 条件三段论 | A→B，B→C ⇒ A→C |
| 构造性二难 | A∨B，A→C，B→C ⇒ C |
| 前后件附加 | A→B⇒(A∨C)→(B∨C)；A→B⇒(A∧C)→(B∧C) |
!常考易错点
易错 1
小项、大项编码规则相反：小项「变元=1、否定=0」，大项「变元=0、否定=1」。背下来,或者现场靠「小项独真、大项独假」反推。
易错 2
下标相同的小项与大项互为否定：¬m₃ = M₃。求主合取范式时正好用「补下标」对应。
易错 3
范式不唯一,主范式唯一。题目要求「主」范式时,少项、漏项、带重复项都算错。
易错 4
等值演算法求主析取:简单合取式缺变元要补全,用 A∧(Pᵢ∨¬Pᵢ) 分配展开,最后去重。这两步最容易丢分。
易错 5
「前提真结论必真」判有效;不看结论内容是否合理。若前提本身就是矛盾式,任何结论都推得出(空真)。
易错 6
拒取式(MT) vs 析取三段论:MT 是 A→B, ¬B ⇒ ¬A;析取三段论是 A∨B, ¬B ⇒ A。看到 → 配 ¬后件 → 拒取式;看到 ∨ 配 ¬支 → 析取三段论。
易错 7
归谬法加的是「结论的否定」;CP 规则加的是「条件式结论的前件」。两者别混。