谓词逻辑
用谓词逻辑将下列命题符号化
① 所有的偶数均能被2整除。
设 A(x)：x是偶数，B(x)：x能被2整除。
符号化为：∀x(A(x) → B(x))
② 有一些人登上过月球。
设 A(x)：x是人，B(x)：x登上过月球。
符号化为：∃x(A(x) ∧ B(x))
③ 每列火车都比某些汽车快。
设 F(x)：x是火车，G(x)：x是汽车，H(x,y)：x比y快。
符号化为：∀x(F(x) → ∃y(G(y) ∧ H(x,y)))
④ 没有不犯错的人。
设 A(x)：x是人，B(x)：x犯错误。
符号化为：¬∃x(A(x) ∧ ¬B(x))
⑤ 尽管有人聪明，但未必所有人都聪明。
设 A(x)：x是人，B(x)：x聪明。
符号化为：∃x(A(x) ∧ B(x)) ∧ ¬∀x(A(x) → B(x))
总结：
- 全称量词 ∀ 后加 "→"
- 存在量词 ∃ 后加 "∧"
量词的辖域
- 辖域：量词的作用范围
- 约束出现：受约束的出现
- 约束变元：在辖域内受量词约束的变元
- 自由出现：不受任何量词约束的出现
- 自由变元：自由出现的变元
例：
① ∀x(P(x) ∧ Q(x))
- ∀ 指导变元 x
- ∀x 的辖域：P(x) ∧ Q(x)
- x：约束变元
② ∀x∀y(P(x,y) ∧ Q(y,z)) ∧ ∃xR(x,y)
- ∀x 的辖域：P(x,y) ∧ Q(y,z)
- ∀y 的辖域：P(x,y) ∧ Q(y,z)
- ∃x 的辖域：R(x,y)
在 ∀x∀y(P(x,y) ∧ Q(y,z)) 中：x、y 是约束变元，z 是自由变元
在 ∃xR(x,y) 中：x 是约束变元，y 是自由变元
熟记等价式
① 命题逻辑中的等价式的代换实例是谓词逻辑中的等价式。
- A → B ⟺ ¬A ∨ B →
P(x) → Q(x) ⟺ ¬P(x) ∨ Q(x) - ¬(A ∧ B) ⟺ ¬A ∨ ¬B →
¬(∃xP(x) ∧ ∀xQ(x)) ⟺ ¬∃xP(x) ∨ ¬∀xQ(x)
② 量词否定转换。
- ¬∀x P(x) ⟺ ∃x ¬P(x)
- ¬∃x P(x) ⟺ ∀x ¬P(x)
③ 量词辖域的扩张和收缩。（略）
- ∀x(A(x) ∧ B) ⟺ ∀xA(x) ∧ B
⑤ 量词否定转换。
- ¬∀x P(x) ⟺ ∃x ¬P(x)
- ¬∃x P(x) ⟺ ∀x ¬P(x)
⑥ 量词辖域的扩张和收缩。（略）
- ∀x(A(x) ∧ B) ⟺ ∀xA(x) ∧ B
⑤ 谓词等值式
- ∀x(B → A(x)) ⟺ B → ∀xA(x)
- ∀x(A(x) → B) ⟺ (∃xA(x)) → B
⑦ 量词分配律
∀x(A(x) ∧ B(x)) ⟺ ∀xA(x) ∧ ∀xB(x)
∃x(A(x) ∨ B(x)) ⟺ ∃xA(x) ∨ ∃xB(x)
注意：∀x(A(x) ∨ B(x)) 和 ∃x(A(x) ∧ B(x)) 不能进行分配。
例题
① 证明：谓词公式 ∀y(A(x) → A(y)) 是永真式。
证明：利用谓词等值式 ∀y(B → A(y)) ⟺ B → ∀yA(y)** 可得：
∀y(A(x) → A(y))
⟺ ∀xA(x) → ∀yA(y)
⟺ ∀yA(y) → ∀yA(y)
易见这是一个永真式。
所以，谓词公式 ∀y(A(x) → A(y)) 是永真式。