Appearance
命题逻辑研究命题之间的逻辑关系。本笔记梳理命题与联结词、命题公式分类、等值演算、范式（含主范式）以及推理理论——是后续一阶逻辑和所有逻辑推理的基础。
命题与联结词
命题
- 命题：能判断真假的陈述句。真值为真（1）或假（0）
- 原子命题：不能再分解的命题
- 复合命题：由联结词联结原子命题构成
五个联结词（核心考点）
| 联结词 | 记号 | 读法 | 真值特点 |
|---|---|---|---|
| 否定 | ¬p | 非 p | 真值取反 |
| 合取 | p∧q | p 且 q | 全真才真 |
| 析取 | p∨q | p 或 q | 全假才假（相容或） |
| 蕴含 | p→q | 若 p 则 q | 只有 p 真 q 假时为假 |
| 等价 | p↔q | p 当且仅当 q | 同真同假才真 |
蕴含式的易错点："p→q 为假当且仅当 p 真 q 假"，即"假前提蕴含一切"（p 假时 p→q 恒为真）。
命题公式与真值表
- 命题公式：原子命题经联结词和括号构成的合法表达式
- 真值表：列出公式在所有赋值下的取值，是判断公式类型和验证等值的基本工具
公式分类
| 类型 | 定义 | 举例 |
|---|---|---|
| 重言式（永真式） | 所有赋值下为真 | p∨¬p |
| 矛盾式（永假式） | 所有赋值下为假 | p∧¬p |
| 可满足式 | 至少一个赋值为真 | p∧q |
A 与 B 等值（A⇔B）：A↔B 是重言式。
等值演算
常用等值式（考点，需熟练）
| 名称 | 等值式 |
|---|---|
| 双重否定律 | ¬¬p ⇔ p |
| 德摩根律 | ¬(p∧q) ⇔ ¬p∨¬q，¬(p∨q) ⇔ ¬p∧¬q |
| 蕴含等值式 | p→q ⇔ ¬p∨q |
| 等价等值式 | p↔q ⇔ (p→q)∧(q→p) |
| 归谬论 | (p→q)∧(p→¬q) ⇔ ¬p |
| 吸收律 | p∨(p∧q) ⇔ p |
| 分配律 | p∨(q∧r) ⇔ (p∨q)∧(p∨r) |
- 置换规则：公式中某子公式用其等值式替换，所得公式与原公式等值
范式（考点）
析取范式与合取范式
- 析取范式（DNF）：有限个简单合取式（合取项）的析取，如 (p∧q)∨(¬p∧r)
- 合取范式（CNF）：有限个简单析取式（析取项）的合取，如 (p∨q)∧(¬p∨r)
任何命题公式都存在等值的析取范式和合取范式。
主范式（重点）
- 极小项：包含所有命题变元的简单合取式（每个变元或其否定恰好出现一次）。n 个变元有 2^n 个极小项
- 极大项：包含所有命题变元的简单析取式
- 主析取范式：由极小项组成的析取；主合取范式：由极大项组成的合取
- 用真值表或等值演算求主范式；由主析取范式可直接看出公式的可满足性（非空则可满足，且可数满足赋值个数）
技巧：真值表中取值为 1 的行对应极小项，取值为 0 的行对应极大项。主析取范式与主合取范式互补。
推理理论（考点）
推理的形式结构
推理是指从前提 A1, A2, …, An 推出结论 B：A1∧A2∧…∧An → B 是重言式。
常用推理规则
| 规则 | 形式 |
|---|---|
| 假言推理（MP） | p→q，p ⇒ q |
| 拒取式（MT） | p→q，¬q ⇒ ¬p |
| 假言三段论 | p→q，q→r ⇒ p→r |
| 析取三段论 | p∨q，¬p ⇒ q |
| 合取引入 | p，q ⇒ p∧q |
| 构造性二难 | (p→q)∧(r→s)，p∨r ⇒ q∨s |
证明方法
- 直接构造：从前提逐步用推理规则推出结论
- 附加前提法（CP 规则）：要证 A→B，把 A 加入前提证 B
- 归谬法：把结论的否定加入前提，推出矛盾
一句话总结
命题逻辑五联结词中"蕴含"最易错（p 假则 p→q 真）；主范式是判断公式类型的利器；推理的本质是证明"前提合取→结论"为重言式。