第五课：逻辑等价、蕴涵、范式¶
Page 2 — 逻辑等价¶
- 当A↔B是重言式时，称A逻辑等价于B——记作A≡B
- 在任何赋值状况下A和B都等值
- 如果说A≡B，"证明A↔B每一列都是T"
Page 3-4 — 重要逻辑等价式（⭐必记）¶
| 编号 | 公式 | 名称 |
|---|---|---|
| E1 | ¬¬A ≡ A | 双重否定律 |
| E2 | A∨A≡A, A∧A≡A | 幂等律 |
| E3 | A∨B≡B∨A, A∧B≡B∧A | 交换律 |
| E4 | (A∨B)∨C≡A∨(B∨C), (A∧B)∧C≡A∧(B∧C) | 结合律 |
| E5 | A∧(B∨C)≡(A∧B)∨(A∧C), A∨(B∧C)≡(A∨B)∧(A∨C) | 分配律 |
| E6 | ¬(A∨B)≡¬A∧¬B, ¬(A∧B)≡¬A∨¬B | 德摩根律 |
| E7 | A∨(A∧B)≡A, A∧(A∨B)≡A | 吸收律 |
| E8 | A→B ≡ ¬A∨B | 蕴涵等值式 |
| E9 | A↔B ≡ (A→B)∧(B→A) | 等价等值式 |
| E10 | A∨T≡T, A∧F≡F | 零律 |
| E11 | A∨F≡A, A∧T≡A | 同一律 |
| E12 | A∨¬A≡T, A∧¬A≡F | 排中律和矛盾律 |
| E13 | ¬T≡F, ¬F≡T | |
| E14 | (A∧B)→C ≡ A→(B→C) | 输出律 |
| E15 | A→B ≡ ¬B→¬A | 假言易位 |
| E16 | (A→B)∧(A→¬B)≡¬A | 归谬论 |
| E17 | A↔B ≡ (A∧B)∨(¬A∧¬B) | 等价等值式2 |
💡 人话：这些是逻辑运算的"代数法则"，就像算术里的交换律结合律分配律一样。做题时可以用它们把复杂公式化简。
Page 5-6 — 逻辑蕴涵式¶
- 当A→B是重言式时，称A逻辑蕴涵B——记作A⊨B
- A的所有成真赋值都是B的成真赋值
- 每个逻辑等价可以看作两个逻辑蕴涵式：A≡B既是A⊨B也是B⊨A
| 编号 | 公式 | 名称 |
|---|---|---|
| I1 | A ⊨ A∨B | 析取引入 |
| I2 | A∧B ⊨ A | 合取消去 |
| I3 | A∧(A→B) ⊨ B | 假言推理（Modus Ponens） |
| I4 | (A→B)∧¬B ⊨ ¬A | 归谬推理（Modus Tollens） |
| I5 | ¬A∧(A∨B) ⊨ B | 析取三段论 |
| I6 | (A→B)∧(B→C) ⊨ A→C | 传递律（三段论） |
| I7 | (A→B)∧(C→D) ⊨ (A∧C)→(B∧D) | |
| I8 | (A↔B)∧(B↔C) ⊨ A↔C | 等价传递 |
Page 7 — 逻辑结果¶
- Γ⊨B：使Γ中每一个公式成真的赋值，都是公式B的成真赋值
- Γ中所有公式的合取逻辑蕴涵B
- ⊨B：Γ为空集，B永真
Page 8 — 性质总结¶
- A≡B ⟺ ⊨A↔B
- A⊨B ⟺ ⊨A→B
- 若A⊨B，则¬B⊨¬A（逆否）
- 若A⊨B，B⊨C，则A⊨C（传递）
Page 9 — 代入原理（RS）¶
- 将重言式A中的某个命题变元p的所有出现都代换为命题公式B
- 得到的A(B/p)也是重言式
- 注意：只代换部分出现不成立！
- 思考：若B包含p或A中的其它变元，还成立吗？
Page 10 — 替换原理（RR）¶
- 将命题公式A中的子公式C的部分出现替换为和C逻辑等价的公式D（C≡D）
- 得到的B与原公式等价（A≡B）
- 注意：不要求全部出现都替换
Page 11 — RS与RR的区别¶
| 代入原理RS | 替换原理RR | |
|---|---|---|
| 使用对象 | 任意永真式 | 任意命题公式 |
| 代换对象 | 任意命题变元 | 任意子公式 |
| 代换物 | 任意命题公式 | 与替换对象等价的公式 |
| 代换方式 | 同一变元的所有出现 | 子公式的部分出现 |
| 结果 | 仍为永真式 | 与原公式等价 |
💡 人话： - 代入：把重言式里的一个变元通通换成别的公式，结果还是重言式 - 替换：把公式中的某部分换成逻辑等价的东西，整体还是等价的
Page 12 — 证明逻辑等价/蕴涵¶
- 真值表法：分别列出A↔B和A→B的真值表，看最后一列
- 对赋值讨论：证明A⊨B，只需证A的任意成真赋值也是B的成真赋值
- 推演法：用已知等价式一步步变形
Page 16-20 — 析取范式与合取范式¶
- 文字（literal）：命题变元p（正文字）或¬p（负文字）
- 合取子句：文字的合取，如 p∧¬q∧r
- 析取子句：文字的析取，如 p∨¬q∨r
- 析取范式（DNF）：合取子句的析取
- 例：(p∧q)∨(¬p∧r)
- 合取范式（CNF）：析取子句的合取
- 例：(p∨q)∧(¬p∨r)
Page 26-27 — 极小项（min term）¶
- 极小项mᵢ：包含所有n个变元的合取子句，每个变元恰好出现一次（正或负）
- i的n位二进制表示决定每个变元的否定状态：
- 该位=0 → 负文字（¬），=1 → 正文字
- 例：m₇ = p₁∧p₂∧p₃（7=111）
- 例：m₄ = p₁∧¬p₂∧¬p₃（4=100）
- 每个极小项有且仅有一个成真赋值（对应下标i的二进制值）
- 主析取范式：极小项按下标从小到大排列的析取
Page 28-29 — 主析取范式的存在性和唯一性¶
- 存在性：任何命题公式都可以化成主析取范式（用分配律、补全变元）
- 唯一性：反证法，若有不同的主析取范式则存在某个极小项不同，导致真值不同
Page 30 — 等值类的数量 ⭐考试重点¶
- n个变元 → 极小项数量 N = 2ⁿ
- 主析取范式数量 = 2ᴺ = 2^(2ⁿ)
- 等值类的数量 = 主析取范式的数量
💡 人话（核心）：n=3时，N=2³=8个极小项。每个极小项可以选择"出现在主析取范式中"或"不出现在主析取范式中"，所以有2⁸=256种不同的主析取范式，对应256个等价类（真值函数）。
Page 31 — 主合取范式¶
- 与主析取范式对称
- 使用极大项和成假赋值
- 等值类数量相同：2ᴺ
Page 32-33 — 真值函数与功能完备集¶
- 真值函数F(p₁,...,pₙ)：每个变元定义域{0,1}，值域{0,1}
- 真值函数与等值类一一对应
- 每个等值类对应唯一的真值函数
- 功能完备集：任意真值函数都能用该联结词集中的联结词表示
- {¬,∧,∨,→,↔}是功能完备集
- {¬,∧,∨}是功能完备集（因为主析取范式只用这三个）