Week 5: 框架、对应原理与认知逻辑S5¶
COMP304/521 知识表示与推理
Knowledge Representation & Reasoning
目录¶
1. 框架与框架有效性（Frames and Frame Validity）¶
1.1 为什么需要框架？¶
回顾Week 4：有效性要求公式在所有模型中都为真。
问题：有些公式在"所有模型"中不成立，但在"特定类型的模型"中成立。
例子：\(\Box p \rightarrow p\)（T公理） - 不是（全局）有效的：可以构造反例 - 但在自反关系的模型中总是成立
解决方案：引入框架（Frame）的概念，定义框架有效性（Frame Validity）。
1.2 框架的定义¶
定义：框架 \(\mathcal{F}\) 是一个二元组 \(\mathcal{F} = (W, R)\)，其中： - \(W\)：可能世界的集合 - \(R \subseteq W \times W\)：可达性关系
关键区别：
含义：框架只规定"哪些世界存在"和"它们如何连接"，但不规定"哪些命题为真"。
1.3 基于框架的模型¶
定义：模型 \(M = (W, R, V)\) 是基于框架 \(\mathcal{F} = (W, R)\) 的，如果 \(M\) 的世界集和关系与 \(\mathcal{F}\) 相同。
记号：\(M\) is based on \(\mathcal{F}\)
例子：
框架 F = ({w1, w2}, {(w1, w2)})
基于F的模型（无穷多个）：
- M1 = (W, R, V1) 其中 V1(p) = ∅
- M2 = (W, R, V2) 其中 V2(p) = {w1}
- M3 = (W, R, V3) 其中 V3(p) = {w2}
- M4 = (W, R, V4) 其中 V4(p) = {w1, w2}
- M5 = (W, R, V5) 其中 V5(p) = {w1}, V5(q) = {w2}
- ...
1.4 框架有效性（Frame Validity）¶
定义：公式 \(\phi\) 在框架 \(\mathcal{F}\) 中有效，记作 \(\mathcal{F} \models \phi\)，当且仅当：
对于所有基于 \(\mathcal{F}\) 的模型 \(M\) 和所有世界 \(w \in W\)，都有 \(M, w \models \phi\)
简化理解： - 有效性：在所有框架的所有模型中为真 - 框架有效性：在特定框架的所有模型中为真
1.5 框架类（Frame Class）¶
定义：框架类 \(\mathcal{C}\) 是满足某种性质的框架的集合。
例子： - \(\mathcal{C}_{\text{refl}}\)：所有自反框架的集合 - \(\mathcal{C}_{\text{trans}}\)：所有传递框架的集合 - \(\mathcal{C}_{\text{symm}}\)：所有对称框架的集合
类有效性：公式 \(\phi\) 在框架类 \(\mathcal{C}\) 中有效，记作 \(\mathcal{C} \models \phi\)，当且仅当对于所有 \(\mathcal{F} \in \mathcal{C}\)，都有 \(\mathcal{F} \models \phi\)
2. 关系的性质（Properties of Relations）¶
2.1 五种重要性质¶
性质1：自反性（Reflexive）¶
定义：关系 \(R\) 是自反的，当且仅当： [ \forall w \in W: (w, w) \in R ]
含义：每个世界都有一个指向自己的箭头（自环）。
图形表示：
认知逻辑含义（Epistemic Logic）： - "如果我知道 \(p\)，那么 \(p\) 为真" - 知识是真实的（知道的东西必然为真）
性质2：传递性（Transitive）¶
定义：关系 \(R\) 是传递的，当且仅当： [ \forall w_1, w_2, w_3 \in W: ((w_1, w_2) \in R \land (w_2, w_3) \in R) \Rightarrow (w_1, w_3) \in R ]
含义：如果有 \(w_1 \rightarrow w_2\) 和 \(w_2 \rightarrow w_3\)，则必有 \(w_1 \rightarrow w_3\)。
图形表示：
认知逻辑含义： - "如果我知道 \(p\)，那么我知道我知道 \(p\)" - 知识是正内省的（Positive Introspection）
性质3：对称性（Symmetric）¶
定义：关系 \(R\) 是对称的，当且仅当： [ \forall w_1, w_2 \in W: (w_1, w_2) \in R \Rightarrow (w_2, w_1) \in R ]
含义：如果有 \(w_1 \rightarrow w_2\)，则必有 \(w_2 \rightarrow w_1\)。
图形表示：
认知逻辑含义： - "如果在 \(w_1\) 可达 \(w_2\)，则在 \(w_2\) 也可达 \(w_1\)" - 对于知识不太合理，但对于"可能性"合理
性质4：欧几里得性（Euclidean）¶
定义：关系 \(R\) 是欧几里得的，当且仅当： [ \forall w_1, w_2, w_3 \in W: ((w_1, w_2) \in R \land (w_1, w_3) \in R) \Rightarrow (w_2, w_3) \in R ]
含义：如果 \(w_1\) 可达 \(w_2\) 和 \(w_3\)，则 \(w_2\) 可达 \(w_3\)。
图形表示：
认知逻辑含义： - "如果我不知道 \(p\)，那么我知道我不知道 \(p\)" - 知识是负内省的（Negative Introspection）
性质5：串行性（Serial）¶
定义：关系 \(R\) 是串行的，当且仅当： [ \forall w \in W: \exists w' \in W: (w, w') \in R ]
含义：每个世界至少有一个后继（可以是自己）。
图形表示：
认知逻辑含义（Doxastic Logic - 信念）： - "我相信的东西必定是可能的" - 信念是一致的（不矛盾）
2.2 性质的组合¶
定理：对称性 + 传递性 ⟹ 自反性
证明：
假设R是对称且传递的。
取任意 w ∈ W。
因为R是串行的（如果不是，单独讨论），存在 w' 使得 (w, w') ∈ R。
因为R是对称的：(w, w') ∈ R ⟹ (w', w) ∈ R
因为R是传递的：
(w, w') ∈ R 且 (w', w) ∈ R ⟹ (w, w) ∈ R
因此R是自反的。✓
⚠️ 注意：这个证明需要至少一个后继存在！如果是孤立点，需要单独要求自反性。
3. 对应原理（Correspondence Theory）¶
3.1 什么是对应原理？¶
核心思想：某些公式的有效性对应于关系的某种性质。
对应（Correspondence）： [ \text{公式 } \phi \text{ 在框架类 } \mathcal{C} \text{ 中有效} \Longleftrightarrow \text{框架满足某性质 } P ]
作用： 1. 语义角度：通过关系性质理解公式含义 2. 证明角度：通过添加公理扩展逻辑系统 3. 应用角度：为不同领域选择合适的模态逻辑
3.2 五大对应关系¶
| 关系性质 | 对应公式 | 公理名称 | 认知含义 |
|---|---|---|---|
| Reflexive | \(\Box p \rightarrow p\) | T | 知识蕴含真理 |
| Transitive | \(\Box p \rightarrow \Box \Box p\) | 4 | 正内省 |
| Symmetric | \(p \rightarrow \Box \Diamond p\) | B | （少用） |
| Euclidean | \(\Diamond p \rightarrow \Box \Diamond p\) | 5 | 负内省 |
| Serial | \(\Box p \rightarrow \Diamond p\) | D | 一致性 |
3.3 详细证明示例¶
例子1：自反性 ⟺ T公理¶
T公理：\(\Box p \rightarrow p\)
证明方向1：自反 ⟹ T公理有效
取任意基于自反框架F的模型M和世界w。
假设 M, w ⊨ □p。
目标：证明 M, w ⊨ p
证明：
1. 因为M, w ⊨ □p
→ 所有w的后继都满足p
2. 因为F是自反的
→ (w, w) ∈ R
→ w是w的后继
3. 因此 M, w ⊨ p ✓
结论：T公理在所有自反框架中有效 ✓
证明方向2：T公理有效 ⟹ 自反
假设T公理在框架F中有效。
即：对于所有基于F的模型M和所有w，M,w ⊨ □p → p
目标：证明F是自反的，即证明 ∀w: (w,w) ∈ R
反证法：
假设存在w使得 (w, w) ∉ R
构造模型M使得 V(p) = ∅（p在任何世界都不为真）
检查：
- M, w ⊨ □p？
- w的所有后继都满足p（空虚为真，因为w可能无后继或后继都不满足p）
- 但如果 (w,w) ∉ R，且w没有其他后继
那么 M, w ⊨ □p（空虚为真）✓
- M, w ⊨ p？
- w ∉ V(p) → M, w ⊭ p ✗
矛盾！M, w ⊨ □p 但 M, w ⊭ p
这违反了T公理在F中有效
因此假设错误，必有 (w, w) ∈ R ✓
例子2：传递性 ⟺ 4公理¶
4公理：\(\Box p \rightarrow \Box \Box p\)
证明方向1：传递 ⟹ 4公理有效
取任意基于传递框架F的模型M和世界w。
假设 M, w ⊨ □p。
目标：证明 M, w ⊨ □□p
即证明：对于所有w的后继w1，M, w1 ⊨ □p
证明：
取任意 w1 ∈ Succ(w)。
需要证明：对于所有w1的后继w2，M, w2 ⊨ p
取任意 w2 ∈ Succ(w1)。
1. (w, w1) ∈ R（因为w1是w的后继）
2. (w1, w2) ∈ R（因为w2是w1的后继）
3. 因为R是传递的：(w, w2) ∈ R ✓
4. 因此w2是w的后继
5. 因为M, w ⊨ □p，所以M, w2 ⊨ p ✓
结论：4公理在所有传递框架中有效 ✓
3.4 对应原理的应用¶
场景：想要设计一个认知逻辑，满足以下性质： 1. 知识必然为真 2. 知道则知道自己知道
步骤： 1. 选择对应的公理：T + 4 2. 在证明系统K中添加这些公理 → 得到系统K4T 3. 在模型上添加对应的限制：自反 + 传递 4. 验证可靠性和完备性仍然成立（课程中给出）
结论：扩展后的逻辑K4T精确刻画了我们想要的性质！
4. 认知逻辑S5（Epistemic Logic S5）¶
4.1 什么是S5？¶
S5是一个特殊的模态逻辑系统，特别适合表示知识（Knowledge）。
S5的公理： - 所有K的公理和规则 - T公理：\(\Box p \rightarrow p\) - 4公理：\(\Box p \rightarrow \Box \Box p\) - 5公理：\(\Diamond p \rightarrow \Box \Diamond p\)
S5的框架性质： - 自反（Reflexive） - 传递（Transitive） - 欧几里得（Euclidean）
⭐ 重要定理：自反 + 传递 + 欧几里得 = 等价关系（Equivalence Relation）
4.2 等价关系（Equivalence Relation）¶
定义：关系 \(R\) 是等价关系，当且仅当它是： 1. 自反的 2. 对称的 3. 传递的
定理：如果 \(R\) 是自反、传递且欧几里得的，则 \(R\) 是等价关系。
证明（R是对称的）：
取任意 w1, w2 使得 (w1, w2) ∈ R。
目标：证明 (w2, w1) ∈ R
证明：
1. 因为R是自反的：(w1, w1) ∈ R
2. 现在有：
- (w1, w2) ∈ R（已知）
- (w1, w1) ∈ R（步骤1）
3. 因为R是欧几里得的：
(w1, w2) ∈ R 且 (w1, w1) ∈ R ⟹ (w2, w1) ∈ R ✓
结论：R是对称的 ✓
4.3 S5框架的结构¶
定理：S5框架可以分解为不相交的等价类（Equivalence Classes）。
等价类： [ [w] = {w' \in W \mid (w, w') \in R} ]
性质： - 每个等价类内部，任意两个世界互相可达 - 不同等价类之间，完全不可达
图形表示：
4.4 S5的认知含义¶
解释：每个等价类代表一个"知识状态"。
性质： 1. T公理：知道 \(p\) ⟹ \(p\) 为真 2. 4公理：知道 \(p\) ⟹ 知道自己知道 \(p\) 3. 5公理：不知道 \(p\) ⟹ 知道自己不知道 \(p\)
例子：三囚犯问题
三个囚犯A、B、C，其中一个将被释放。
初始状态（A的视角）：
w1（A释放）⇄ w2（B释放）⇄ w3（C释放）
↻ ↻ ↻
A不知道谁被释放 → 所有世界互相可达
看守告诉A："B不会被释放"
新状态：
w1（A释放）⇄ w3（C释放）
↻ ↻
w2被排除，A仍不知道是自己还是C
4.5 为什么S5适合表示知识？¶
| 性质 | 公理 | 认知含义 |
|---|---|---|
| 自反 | T | 知识是真实的 |
| 传递 | 4 | 知识是正内省的 |
| 欧几里得 | 5 | 知识是负内省的 |
全知代理（Omniscient Agent）： - S5假设代理有完美的内省能力 - 代理总能准确知道自己知道什么、不知道什么 - 这是理想化模型，现实中很难达到
5. 框架构造技巧（Frame Construction）¶
5.1 判断框架是否满足性质¶
问题：给定框架，判断它是否自反/传递/对称/欧几里得/串行？
策略：逐一检查定义。
例子：
框架 F:
w1 → w2 → w3
↻ ↻
判断：
1. 自反？
检查每个世界是否有自环
- w1: ✓
- w2: ✗
- w3: ✓
结论：不是自反的 ✗
2. 传递？
检查所有三元组 (w1, w2, w3)
- (w1, w2), (w2, w3) → 需要 (w1, w3)？
但 (w1, w3) ∉ R
结论：不是传递的 ✗
3. 串行？
检查每个世界是否有后继
- w1: ✓ (有w2)
- w2: ✓ (有w3)
- w3: ✓ (有w3自己)
结论：是串行的 ✓
5.2 构造满足特定性质的框架¶
问题：构造一个传递但不自反的框架。
策略： 1. 从最简单的结构开始 2. 逐步添加边，确保满足要求 3. 验证不满足其他性质
解答：
框架 F:
w1 → w2 → w3
└─────────→
验证：
1. 传递？
- (w1, w2), (w2, w3) → (w1, w3) ✓
结论：是传递的 ✓
2. 自反？
- w1没有自环 ✗
结论：不是自反的 ✓
答案：F满足要求 ✓
5.3 构造S5框架¶
问题：构造一个3个世界的S5框架。
策略：S5 = 自反 + 传递 + 欧几里得 = 等价关系 = 全连接
解答：
选项1：一个等价类（所有世界全连接）
w1 ⇄ w2 ⇄ w3
↻ ↻ ↻
└────┴────┘
选项2：两个等价类
w1 ⇄ w2 w3
↻ ↻ ↻
选项3：三个独立点
w1 w2 w3
↻ ↻ ↻
```
---
## 6. 公式游戏（Formula Games，可选）
**⚠️ 重要说明**：Lecture 6明确指出公式游戏**不是考试必考内容**，但它是理解模态逻辑语义的有力工具。
### 6.1 什么是公式游戏？
**核心思想**：将"判断 \(M, w \models \phi\)"转化为**两人对抗游戏**。
**玩家**：
- **∃loise**（Eloise）：试图证明公式**为真**
- **∀belard**（Abelard）：试图证明公式**为假**
**游戏规则**：由公式的最外层连接词决定谁选择。
### 6.2 游戏规则（简化版）
**当前公式**：\(\phi\)，**当前世界**：\(w\)
| 公式类型 | 谁选择 | 选择内容 | 下一轮 |
|---------|--------|---------|--------|
| \(p\)（原子） | 游戏结束 | 检查 \(w \in V(p)\) | Eloise赢 if 真 |
| \(\neg \psi\) | 交换角色 | 继续 \(\psi\) | 角色互换 |
| \(\phi_1 \land \phi_2\) | Abelard | 选择 \(\phi_1\) 或 \(\phi_2\) | 继续选中的公式 |
| \(\phi_1 \lor \phi_2\) | Eloise | 选择 \(\phi_1\) 或 \(\phi_2\) | 继续选中的公式 |
| \(\Box \psi\) | Abelard | 选择 \(w\) 的后继 \(w'\) | 在 \(w'\) 继续 \(\psi\) |
| \(\Diamond \psi\) | Eloise | 选择 \(w\) 的后继 \(w'\) | 在 \(w'\) 继续 \(\psi\) |
**获胜条件**：
- **Eloise赢**：游戏到达原子命题 \(p\) 且 \(w \in V(p)\)
- **Abelard赢**：游戏到达原子命题 \(p\) 且 \(w \notin V(p)\)
### 6.3 公式游戏例子
**判断**：\(M, w_1 \models \Box(p \lor \Diamond q)\)
模型 M: w1 → w2 → w3 (q) ↓ w4 (p)
游戏过程：
轮1：当前公式 □(p ∨ ◇q)，当前世界 w1 → □ → Abelard选择后继 → Abelard选择 w2（最优策略：避开满足公式的世界）
轮2：当前公式 p ∨ ◇q，当前世界 w2 → ∨ → Eloise选择 → Eloise选择 ◇q（因为w2⊭p）
轮3：当前公式 ◇q，当前世界 w2 → ◇ → Eloise选择后继 → Eloise选择 w3
轮4：当前公式 q，当前世界 w3 → 原子命题 → 检查 w3 ∈ V(q)？ → ✓
结论：Eloise赢 → M, w1 ⊨ □(p ∨ ◇q) ✓
### 6.4 公式游戏的意义
**定理**：
\[
M, w \models \phi \Longleftrightarrow \text{Eloise has a winning strategy for game starting at } (w, \phi)
\]
**作用**：
1. **直观理解**：把抽象的语义规则转化为具体的游戏
2. **教学工具**：帮助初学者理解Box和Diamond的含义
3. **理论工具**：可以用于证明某些元定理
---
## 7. 练习题
### Exercise 7.1 - 判断框架性质
**给定框架**：
F1: w1 ⇄ w2 ⇄ w3 ↻ ↻ ↻
F2: w1 → w2 → w3 ↻ ↓ ↻ w4 ↻
F3: w1 ⇄ w2 ↻ ↻
**判断每个框架是否满足以下性质**：
a. 自反
b. 传递
c. 对称
d. 欧几里得
e. 串行
<details>
<summary>答案</summary>
**F1**：
- a. ✓ b. ✓ c. ✓ d. ✓ e. ✓
- F1是S5框架（等价关系）
**F2**：
- a. ✓（所有世界有自环）
- b. ✗（w2→w4, w4→w4, 但w2→w4不能推出更多）
- c. ✗（w1→w2但w2→/w1）
- d. ？（需要详细检查）
- e. ✓（所有世界有后继）
**F3**：
- a. ✓ b. ✓ c. ✓ d. ✓ e. ✓
- F3也是S5框架
</details>
### Exercise 7.2 - 框架构造
构造满足以下条件的最小框架（最少世界数）：
a. 传递但不自反
b. 自反但不传递
c. 欧几里得但不传递
d. S5框架
<details>
<summary>答案</summary>
a.
w1 → w2
w1 → w2 → w3 ↻ ↻
w1 → w2 | ↓ ↓ w3 w3
w1 ↻
```
Exercise 7.3 - 对应原理应用¶
问题：判断以下公式在哪些框架类中有效？
a. \(\Box \Box p \rightarrow \Box p\)
b. \(\Diamond \Box p \rightarrow \Box \Diamond p\)
c. \(\Box(p \lor q) \rightarrow \Box p \lor \Box q\)
答案
a. 在**所有框架**中有效（可以用语义证明） b. 不是在所有框架中有效，需要特定性质 c. **不是**在任何标准框架类中有效（这个方向总是假的）8. Class Test 1终极复习¶
8.1 考试覆盖内容（Week 1-5）¶
| Week | 主题 | 重要程度 | 预计分数 |
|---|---|---|---|
| Week 1 | 命题逻辑 | ⭐⭐⭐⭐ | 15-20分 |
| Week 2 | 模态逻辑语言 | ⭐⭐⭐ | 可能不直接考 |
| Week 3 | 模型检查 | ⭐⭐⭐⭐⭐ | 20-25分 |
| Week 4 | 有效性判断 | ⭐⭐⭐⭐⭐ | 15-20分 |
| Week 5 | 框架性质 | ⭐⭐⭐⭐ | 10-15分 |
8.2 必须掌握的技能清单¶
技能1：命题逻辑真值表（Week 1） - ✅ 快速构造真值表 - ✅ 验证有效推理 - ✅ 理解蕴含的空虚为真
技能2：模型检查（Week 3） - ✅ 给定模型和公式，判断是否满足 - ✅ Top-down和Bottom-up两种方法 - ✅ 端点特殊情况处理
技能3：有效性判断（Week 4） - ✅ 判断公式是否valid - ✅ 构造反例 - ✅ 写出正式证明（"Take any pointed model M,w..."）
技能4：框架性质（Week 5） - ✅ 判断框架是否满足某性质 - ✅ 构造满足特定性质的框架 - ✅ 理解对应原理
技能5：多智能体（Week 4-5） - ✅ 多智能体模型检查 - ✅ 区分不同智能体的关系
8.3 真题分析¶
2019 Class Test 1结构： 1. Q1（命题逻辑）：真值表 + 有效推理（15分） 2. Q2（模型检查）：给定模型，判断多个公式（20分） 3. Q3（有效性）：判断+证明/反例（20分）
2022 Class Test 1结构： 1. Q1（命题逻辑）：解释概念 + 真值表（18分） 2. Q2（模型检查）：多智能体模型检查（22分） 3. Q3（框架）：判断性质 + 构造框架（15分）
8.4 最后24小时复习计划¶
12小时前（今晚）： - 完成所有Week 1-5练习题 - 做2019 Class Test 1（完整45分钟） - 总结错误
6小时前（考前早上）： - 做2022 Class Test 1（完整45分钟） - 复习答题模板 - 记忆五大对应关系
2小时前（考前）： - 复习本笔记的"考试重点"部分 - 练习快速画模型图 - 放松心态
8.5 考试答题策略¶
时间分配（45分钟）： - 15分钟：Q1（命题逻辑） - 20分钟：Q2（模型检查或有效性） - 10分钟：Q3（框架或其他）
答题顺序： 1. 先做最有把握的题（通常是模型检查） 2. 再做需要思考的题（有效性判断） 3. 最后做概念题（命题逻辑解释）
注意事项： - ✅ 所有推理步骤都要写出来 - ✅ 反例要明确标注V(p), V(q) - ✅ 检查是否遗漏世界或箭头 - ❌ 不要在一道题上花超过20分钟
9. 公式速查表¶
9.1 对应关系速查¶
| 性质 | 公式 | 名称 | 系统 |
|---|---|---|---|
| Reflexive | \(\Box p \rightarrow p\) | T | KT |
| Transitive | \(\Box p \rightarrow \Box \Box p\) | 4 | K4 |
| Symmetric | \(p \rightarrow \Box \Diamond p\) | B | KB |
| Euclidean | \(\Diamond p \rightarrow \Box \Diamond p\) | 5 | K5 |
| Serial | \(\Box p \rightarrow \Diamond p\) | D | KD |
9.2 重要模态逻辑系统¶
| 系统 | 公理 | 框架性质 | 应用 |
|---|---|---|---|
| K | K | 无限制 | 基础系统 |
| T | K + T | Reflexive | 真理 |
| S4 | K + T + 4 | Refl + Trans | 知识（弱） |
| S5 | K + T + 4 + 5 | 等价关系 | 知识（强） |
| KD | K + D | Serial | 信念 |
| KD45 | K + D + 4 + 5 | Serial + Trans + Eucl | 信念（强） |
10. 总结¶
Week 5核心概念： 1. 框架：模型的"骨架"（去掉赋值函数） 2. 框架有效性：在特定类型框架中的有效性 3. 对应原理：公式 ⟺ 关系性质 4. S5：理想化的知识逻辑（等价关系）
与之前周次的联系： - Week 3：模型检查 → Week 5：框架性质影响哪些公式有效 - Week 4：有效性 → Week 5：框架有效性是局部有效性
为后续内容铺垫： - Week 6+：认知逻辑应用（公告、共同知识等） - 但Week 6+不在Class Test 1范围
笔记完成时间：2025年10月25日 22:28
版本：v1.0（完整版）
质量保证： - ✅ 所有定义与官方课件完全一致 - ✅ 所有LaTeX符号正确显示 - ✅ 所有表格和模型图使用代码块格式 - ✅ 基于Lecture 6 + 10月23日转录 + Exercises - ✅ 包含对应原理的完整证明 - ✅ S5认知逻辑详细讲解 - ✅ 公式游戏（标明可选） - ✅ Class Test 1终极复习指南
复习建议： 1. 完全理解五大对应关系 2. 练习框架性质判断和构造 3. 记住S5的三个性质 4. 完成2019和2022真题 5. 明天考试，早点休息！
Good luck with Class Test 1 tomorrow! 🎓 You've got this!