命题逻辑等值演算
- 等值式：两个公式在所有真值下都等值。
常见等值式
① 双否律
¬¬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 ∨ (A ∧ B) ⟺ A，A ∧ (A ∨ B) ⟺ A
⑧ 零律
A ∨ 1 ⟺ 1，A ∧ 0 ⟺ 0
⑨ 同一律
A ∧ 1 ⟺ A，A ∨ 0 ⟺ A
⑩ 排中律
A ∨ ¬A ⟺ 1
⑪ 矛盾律
A ∧ ¬A ⟺ 0
⑫ 蕴含等值式 ⭐
A → B ⟺ ¬A ∨ B
⑬ 等价等值式
A ↔ B ⟺ (A → B) ∧ (B → A)
⑭ 假言易位
A → B ⟺ ¬B → ¬A
⑮ 等价否定
A ↔ B ⟺ ¬A ↔ ¬B
⑯ 归谬论
(A → B) ∧ (A → ¬B) ⟺ ¬A
例题
1. p ∧ r ∧ ¬(q → p),判断公式类型
| 步骤 | 公式 | 依据 |
|---|---|---|
| 原式 | p ∧ r ∧ ¬(q → p) | |
| ⟺ | p ∧ r ∧ ¬(¬q ∨ p) | 蕴含等值式，去掉 → |
| ⟺ | p ∧ r ∧ (q ∧ ¬p) | 德摩根律，换成 ¬ ∧ ∨ |
| ⟺ | p ∧ ¬p ∧ q ∧ r | 交换律、结合律 |
| ⟺ | 0 | 矛盾律 |
∴ 公式为矛盾式
2.证: q → (p → r) ⟺ (p ∧ q) → r
法一：从左边证到右边
q → (p → r)
⟺ ¬q ∨ (¬p ∨ r) （蕴含等值式）
⟺ ¬p ∨ ¬q ∨ r （结合律）
⟺ ¬(p ∧ q) ∨ r （德摩根律）
⟺ (p ∧ q) → r （蕴含等值式）
法二：从右边证到左边
(p ∧ q) → r
⟺ ¬(p ∧ q) ∨ r （蕴含等值式）
⟺ ¬p ∨ ¬q ∨ r （德摩根律）
⟺ ¬q ∨ ¬p ∨ r （交换律）
⟺ ¬q ∨ (p → r) （蕴含等值式）
⟺ q → (p → r) （蕴含等值式）■
析取范式、合取范式
def 1 p 为任意命题变量，则 p 和 ¬p 称为文字。
def 2 有限个文字的析取称为析取式；例如：p ∨ q，p ∨ ¬q，¬p
有限个文字的合取称为合取式。例如：¬p ∧ q，p ∧ q ∧ r，¬r
def 3 有限个合取式的析取称为析取范式；例如：(… ∧ …) ∨ (… ∧ …) ∨ …
有限个析取式的合取称为合取范式。例如：(… ∨ …) ∧ (… ∨ …) ∧ …
极小项和主析取范式、极大项和主合取范式
极小项
这是含两个命题变元 p、q 的小项表： p和q都要出现且仅出现一次，中间用且连接起来，就是（极）小项。
对析取范式 A₁ ∨ A₂ ∨ ··· ∨ Aₙ，若其中每个合取式 Aᵢ(i=1,2,···,n) 都是小项，则称该析取范式为主析取范式。
极大项
这是含两个命题变元 p、q 的小项表： p和q都要出现且仅出现一次，中间用或连接起来，就是（极）大项。
对合取范式 A₁ ∧ A₂ ∧ ··· ∧ Aₙ，若其中每个析取式 Aᵢ(i=1,2,···,n) 都是大项，则称该合取范式为主合取范式。
例题
1.求 (P→Q) 的主合取范式和主析取范式
法一：真值表法
| 小项 | 公式 | 成真赋值 | P→Q |
|---|---|---|---|
| m₀ | ¬p ∧ ¬q | 00 | 1 |
| m₁ | ¬p ∧ q | 01 | 1 |
| m₂ | p ∧ ¬q | 10 | 0 |
| m₃ | p ∧ q | 11 | 1 |
成假赋值为 10，对应大项 ¬p ∨ q
主析取范式：
P→Q ⟺ (¬p ∧ ¬q) ∨ (¬p ∧ q) ∨ (p ∧ q) ⟺ m₀ ∨ m₁ ∨ m₃
主合取范式：
P→Q ⟺ ¬p ∨ q
法二：等值演算
P→Q ⟺ ¬p ∨ q （主合取范式）
⟺ (¬p ∧ (q ∨ ¬q)) ∨ ((p ∨ ¬p) ∧ q)
⟺ (¬p ∧ q) ∨ (¬p ∧ ¬q) ∨ (p ∧ q) ∨ (¬p ∧ q)
⟺ (¬p ∧ q) ∨ (¬p ∧ ¬q) ∨ (p ∧ q)
2.：用等值演算求 p → ((P→Q) ∧ ¬(¬Q ∨ ¬P)) 的主合取范式和主析取范式
p → ((p→q) ∧ ¬(¬q ∨ ¬p))
⟺ ¬p ∨ ((¬p ∨ q) ∧ q ∧ p)
⟺ (¬p ∨ ¬p ∨ q) ∧ (¬p ∨ q) ∧ (¬p ∨ p)
⟺ (¬p ∨ q) （主合取范式）
⟺ (¬p ∧ (q ∨ ¬q)) ∨ ((p ∨ ¬p) ∧ q)
⟺ (¬p ∧ q) ∨ (¬p ∧ ¬q) ∨ (p ∧ q) ∨ (¬p ∧ q)
⟺ (¬p ∧ q) ∨ (¬p ∧ ¬q) ∨ (p ∧ q) （主析取范式）
3.：求 Q ∧ (¬P → (Q ∨ ¬(Q→R))) 的主析取范式
Q ∧ (¬P → (Q ∨ ¬(Q→R)))
⟺ Q ∧ (P ∨ (Q ∨ ¬(¬Q ∨ R))) （消去蕴含）
⟺ Q ∧ (P ∨ (Q ∨ (Q ∧ ¬R))) （德摩根律）
⟺ Q ∧ (P ∨ Q) （吸收律：Q ∨ (Q ∧ ¬R) ⟺ Q）
⟺ (P ∧ Q) ∨ Q （分配律）
⟺ (P ∧ Q ∧ (R ∨ ¬R)) ∨ (Q ∧ (P ∨ ¬P) ∧ (R ∨ ¬R)) （补全变量）
⟺ (P ∧ Q ∧ R) ∨ (P ∧ Q ∧ ¬R) ∨ (P ∧ Q ∧ R) ∨ (P ∧ Q ∧ ¬R) ∨ (¬P ∧ Q ∧ R) ∨ (¬P ∧ Q ∧ ¬R)
⟺ (¬P ∧ Q ∧ ¬R) ∨ (¬P ∧ Q ∧ R) ∨ (P ∧ Q ∧ ¬R) ∨ (P ∧ Q ∧ R) （去重）
⟺ m2 ∨ m3 ∨ m6 ∨ m7 （主析取范式）
4.求 (p→q)∧r 的主析取范式和主合取范式
(p→q)∧r
⟺ (¬p ∨ q) ∧ r （合取范式）
⟺ (¬p ∨ q ∨ 0) ∧ (0 ∨ 0 ∨ r) （补全变量，2×2）
⟺ (¬p ∨ q ∨ (r ∧ ¬r)) ∧ ((¬p ∧ p) ∨ (q ∧ ¬q) ∨ r )
⟺ (¬p ∨ q ∨ r) ∧ (¬p ∨ q ∨ ¬r) ∧ ...
⟺ (¬p ∨ q ∨ r) ∧ (¬p ∨ q ∨ ¬r) ∧ (p ∨ q ∨ r) ∧ (p ∨ ¬q ∨ r) ∧ (¬p ∨ ¬q ∨ r)
成假赋值：100, 010, 000, 010, 010
⟺ M₀ ∧ M₂ ∧ M₄ ∧ M₅ ∧ M₆ （主合取范式）
(p→q)∧r
⟺ (¬p ∨ q) ∧ r （合取范式）
⟺ (¬p ∧ r) ∨ (q ∧ r) （析取范式）
⟺ (¬p ∧ 1 ∧ r) ∨ (1 ∧ q ∧ r)
⟺ (¬p ∧ (q ∨ ¬q) ∧ r) ∨ ((p ∨ ¬p) ∧ q ∧ r)
⟺ (¬p ∧ q ∧ r) ∨ (¬p ∧ ¬q ∧ r) ∨ (p ∧ q ∧ r) ∨ (¬p ∧ q ∧ r)
成真赋值：011, 001, 111, 011
⟺ (¬p ∧ ¬q ∧ r) ∨ (¬p ∧ q ∧ r) ∨ (p ∧ q ∧ r) （去重）
⟺ m₁ ∨ m₃ ∨ m₇ （主析取范式）
主合取范式互补验证：m₁ ∨ m₃ ∨ m₇ ⟹ M₀ ∧ M₂ ∧ M₄ ∧ M₅ ∧ M₆
5.快速求 (p→q)∧r 的主析取范式和主合取范式
(p→q)∧r
⟺ (¬p ∨ q) ∧ r
⟺ (¬p ∧ r) ∨ (q ∧ r)
⟺ (¬p ∧ q ∧ r) ∨ (¬p ∧ ¬q ∧ r) ∨ (p ∧ q ∧ r) ∨ (¬p ∧ q ∧ r)
011 001 111 011
⟺ m₁ ∨ m₃ ∨ m₇ （主析取范式）
⟺ M₀ ∧ M₂ ∧ M₄ ∧ M₅ ∧ M₆ （主合取范式）