命题逻辑的表列式演算

祝瑞

为什么选择表列式演算？

1. 正向如“迷宫”

公理化的正向证明，如同在迷宫中寻找出路，需要技巧和灵感，对初学者不够友好。

$$ \color{white} \tiny \begin{aligned} E.g. &\vdash p\to p & \\ 1. & (p \to ((p \to p) \to p))\to &\\ ~&((p \to (p \to p)) \to (p \to p)) & \text{(A2)} \\ 2. & p \to ((p \to p) \to p) & \text{(A1)} \\ 3. & (p \to (p \to p)) \to (p \to p) & \text{(1, 2)} \\ 4. & p \to (p \to p) & \text{(A1)} \\ 5. & p \to p & \text{(3, 4)} \end{aligned} $$

2. 反向如“地图”

表列式反向分解，如同按图索骥，只需遵守规则，无需选择。树形结构也更直观。还能生成反模型。

p ∨ q ¬p p × q (Open)

3. 实践的“桥梁”

  • 教学资源稀缺，引入新视角。
  • 清晰展现算法思想，加深对“可判定性”等概念的理解。
  • 打通逻辑学与计算机科学的壁垒。

表列的结构：什么是“树”？

表列式证明的过程，就是一棵不断向下扩展的“树”。

一棵“树”是满足以下条件的节点集合：

  • 根节点 (Root)：有且仅有一个节点没有父节点，它是一切的起点。
  • 父节点 (Parent)：除根节点外，每个节点都有且仅有一个父节点。
  • 祖先与后代 (Ancestor / Descendant)：“是...的父节点的父节点...” 这种关系链构成了祖先与后代。
  • 无环性 (Acyclic)：一个节点永远不能是其自身的祖先。这是树最重要的特性。

✔ 这是一棵树

❌ 不是树 (存在多个根)

❌ 不是树 (共享子节点)

❌ 不是树 (存在循环)

表列法的规则与定理证明

A ∧ BAB A ∨ BAB A → B¬AB ¬¬AA ¬(A ∧ B)¬A¬B ¬(A ∨ B)¬A¬B ¬(A → B)A¬B

推演：证明 ((p→q)→p)→p

1. ¬(((p→q)→p)→p) 2. (p→q)→p 3. ¬p 4. ¬(p→q) 5. p × (3, 5) 6. p 7. ¬q × (3, 6)

表列法的应用：检验论证有效性

A ∧ BAB A ∨ BAB A → B¬AB ¬¬AA ¬(A ∧ B)¬A¬B ¬(A ∨ B)¬A¬B ¬(A → B)A¬B

推演：(p ∨ ¬r) ∧ (q → r) ⊢ q → p

1. (p ∨ ¬r) ∧ (q → r) 2. ¬(q → p) 3. p ∨ ¬r 4. q → r 5. q 6. ¬p 7. p 8. ¬r × (6, 7) 9. ¬q 10. r × (5, 9) × (8, 10)

表列法的应用：反例模型生成

推演：(p → q) ∧ r ⊢ q → (p ∧ r)

1. (p → q) ∧ r 2. ¬(q → (p ∧ r)) 3. p → q 4. r 5. q 6. ¬(p ∧ r) 7. ¬p 8. q 9. ¬p 10. ¬r × (4, 10) OPEN

生成的反例模型

从开放支的“字” (Literals) 中提取真值:

  • r (from 4) ➞ r = 1
  • q (from 5) ➞ q = 1
  • ¬p (from 7) ➞ p = 0
pqr前提： (p→q)∧r结论：q→(p∧r)
01110

思考与练习

  1. 根据今天的学习，请思考下列没有涉及的情况：
    • 如果一个公式 的否定 (¬φ) 的表列树 有开放分支，说明原公式 φ 是什么？
    • 如果一个公式 本身 (φ) 的表列树完全关闭，又说明 φ 是什么？
  2. 可判定性 (Decidability)：如果一个问题存在一个能在有限步骤内必定终止、并给出正确“是/否”答案的方法，那么该问题就是可判定的。

    问题：根据我们今天学习的表列法，请思考：“一个命题公式是否是重言式？” 这个问题是可判定的吗，为什么？

练习

  1. 检验以下公式是否为重言式： ((p ∧ r) → q) → ((¬q ∧ r) → ¬p)
  2. 检验以下论证的有效性： {p → (¬q ∧ r), ¬r → q} ⊢ ¬p