Week 1: 课程介绍 + 命题逻辑基础¶
COMP304/521 知识表示与推理
Knowledge Representation & Reasoning
目录¶
1. 课程概览¶
1.1 课程信息¶
- 讲师：Dr. Louwe Kuijer
- 课程代码：
- COMP304：本科Year 3
- COMP521：研究生MSc
- 差异：COMP521对证明系统要求更高，需要主动构造证明
1.2 评估方式¶
| 考核项目 | 占比 | 时间 | 时长 | 形式 |
|---|---|---|---|---|
| Class Test 1 | 13% | Week 6 (10月28日) | 45分钟 | 线下笔试 |
| Class Test 2 | 12% | Week 11 | 45分钟 | 线下笔试 |
| 期末考试 | 75% | 考试周 | - | 线下笔试 |
⚠️ 重点：Class Test 1 覆盖 Week 1-5（命题逻辑 + 模态逻辑基础）
1.3 课程结构（11周）¶
| 周次 | 主题 | 说明 |
|---|---|---|
| Week 1 | 命题逻辑（Propositional Logic） | 前置知识复习 |
| Week 2-4 | 模态逻辑（Modal Logic） | 核心内容 |
| Week 5-7 | 认知逻辑（Epistemic Logic） | 特化的模态逻辑 |
| Week 8-10 | 描述逻辑（Description Logic） | 本体论应用 |
| Week 11 | 复习 | 考试准备 |
1.4 学习资源¶
- Canvas：所有课件、练习题、往年试卷
- Panopto：讲座录播（2025现场 + 2020专门录播）
- Message Board：提问优先渠道
- 教材（可选）：图书馆有电子版和纸质版
1.5 练习题类型¶
1. 普通练习（Regular Exercises） - 难度：从简单到考试难度 - 目标：60-70分及格水平 - 答案：每个block结束后一周公布
2. 额外练习（Extra Exercises） - 难度：超过考试难度 - 目标：90+分追求卓越 - 答案：不公布（但逻辑题容易自我验证） - 注意：Tutor可能不会帮助这部分
2. 命题逻辑语言¶
命题逻辑是最简单的逻辑系统，也是所有其他逻辑的基础。
2.1 语法定义¶
最小语言（核心）： [ \phi \coloneqq p \mid \neg \phi \mid \phi \land \psi ]
其中： - \(p \in \mathbb{P}\)：原子命题集合 \(\{p, q, r, p_1, q_1, \ldots\}\) - \(\neg\)：否定（Negation） - \(\land\)：合取（Conjunction）
完整语言（包含派生连接词）： [ \phi \coloneqq p \mid \neg \phi \mid \phi \land \psi \mid \phi \lor \psi \mid \phi \rightarrow \psi \mid \phi \leftrightarrow \psi ]
2.2 逻辑连接词¶
| 符号 | 名称 | 读作 | 英文 |
|---|---|---|---|
| \(\neg\) | 否定 | not | Negation |
| \(\land\) | 合取 | and | Conjunction |
| \(\lor\) | 析取 | or | Disjunction |
| \(\rightarrow\) | 蕴含 | implies / if...then | Implication |
| \(\leftrightarrow\) | 双向蕴含 | if and only if (iff) | Bi-implication |
符号读音指南： - \(\phi\)：phi（发音：fai） - \(\psi\)：psi（发音：sai） - \(\gamma\)：gamma - \(\Gamma\)：大写Gamma（表示公式集合）
2.3 合式公式（Well-Formed Formulas, WFF）¶
递归构造规则： 1. 每个原子命题 \(p \in \mathbb{P}\) 是公式 2. 如果 \(\phi\) 是公式，则 \(\neg \phi\) 是公式 3. 如果 \(\phi\) 和 \(\psi\) 都是公式，则以下都是公式： - \((\phi \land \psi)\) - \((\phi \lor \psi)\) - \((\phi \rightarrow \psi)\) - \((\phi \leftrightarrow \psi)\) 4. 仅此而已（没有其他方式构造公式）
括号省略规则：
✅ 允许省略（不产生歧义）： - \(p \lor q \lor r\)（结合律成立） - 最外层括号可以省略
❌ 不允许省略（会产生歧义）： - \(p \lor q \land r\)（可能是 \((p \lor q) \land r\) 或 \(p \lor (q \land r)\)） - \(p \rightarrow q \rightarrow r\)（蕴含不满足结合律）
⭐ 否定绑定优先级最高： - \(\neg p \rightarrow q\) = \((\neg p) \rightarrow q\)，不是 \(\neg(p \rightarrow q)\)
3. 语义与真值表¶
3.1 赋值函数（Valuation）¶
定义： [ V: \mathbb{P} \rightarrow {0, 1} ] 给每个原子命题分配真值（True = 1，False = 0）。
3.2 基本连接词真值表¶
否定（\(\neg\)）¶
合取（\(\land\)）："and"，全真才真¶
析取（\(\lor\)）："or"，至少一个真¶
蕴含（\(\rightarrow\)）⭐ 重点理解¶
p | q | p→q | 解释
---+---+-----+------------------
0 | 0 | 1 | 前件假，空虚为真
0 | 1 | 1 | 前件假，空虚为真
1 | 0 | 0 | 唯一为假的情况
1 | 1 | 1 | 承诺履行
理解方法1：承诺解释
把 \(p \rightarrow q\) 看作承诺"如果 \(p\)，那么 \(q\)"。
例子："如果下雨（\(p\)），我就带伞（\(q\)）"
情况分析：
1. 不下雨，不带伞 (p=0, q=0) → 承诺未触发 → 没违背 → 真
2. 不下雨，带伞 (p=0, q=1) → 承诺未触发 → 没违背 → 真
3. 下雨，不带伞 (p=1, q=0) → 违背承诺 → 假 ❌
4. 下雨，带伞 (p=1, q=1) → 履行承诺 → 真 ✓
理解方法2：等价变换 [ p \rightarrow q \equiv \neg p \lor q ] "要么前提不成立，要么结论成立"
⚠️ 空虚为真（Vacuously True）： - 当前件 \(p\) 为假时，无论 \(q\) 真假，\(p \rightarrow q\) 都为真 - 例子："如果我是总统，月亮是奶酪做的" — 逻辑上是真（因为我不是总统）
常见错误： - ❌ 不要把 \(p \rightarrow q\) 理解成因果关系 - ❌ 不要认为 \(p\) 和 \(q\) 必须有实际联系 - ✅ 蕴含只是逻辑关系，不是时间或因果关系
双向蕴含（\(\leftrightarrow\)）¶
含义：\(p\) 和 \(q\) 真值相同时为真。
等价定义： [ p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p) ]
3.3 缩写符号¶
| 符号 | 定义 | 名称 |
|---|---|---|
| \(\top\) | \(p \lor \neg p\) | True / Tautology |
| \(\bot\) | \(p \land \neg p\) | False / Contradiction |
派生连接词的等价定义： - \(\phi \land \psi \coloneqq \neg(\neg \phi \lor \neg \psi)\)（德摩根律） - \(\phi \rightarrow \psi \coloneqq \neg \phi \lor \psi\) - \(\phi \leftrightarrow \psi \coloneqq (\phi \rightarrow \psi) \land (\psi \rightarrow \phi)\)
4. 有效性（Validity）¶
4.1 公式分类¶
4.1.1 有效公式（Valid / Tautology）¶
定义：在所有赋值下都为真。记号：\(\models \phi\)
例子： - \(p \lor \neg p\)（排中律） - \(p \rightarrow p\) - \((p \land q) \rightarrow p\) - \(\neg(p \land \neg p)\)（矛盾律） - \((p \rightarrow q) \leftrightarrow (\neg q \rightarrow \neg p)\)（逆否命题）
4.1.2 矛盾公式（Contradiction）¶
定义：在所有赋值下都为假。记号：\(\models \neg \phi\)
例子： - \(p \land \neg p\) - \((p \rightarrow q) \land (p \land \neg q)\)
4.1.3 偶然公式（Contingent）¶
定义：真值取决于赋值（有时真，有时假）。
例子： - \(p \land q\) - \(p \rightarrow q\)
关系总结：
| 公式类型 | 含义 | 否定 |
|---|---|---|
| Valid | 永真 | 否定是Contradiction |
| Satisfiable | 至少有一个赋值为真 | 否定不是Valid |
| Contradiction | 永假 | 否定是Valid |
4.2 有效推理（Valid Inference）¶
定义： [ \Gamma \models \phi ] 对于所有赋值 \(V\)，如果 \(\Gamma\) 中所有公式为真，则 \(\phi\) 也为真。
特殊情况： [ \models \phi \equiv \emptyset \models \phi ] 表示 \(\phi\) 无条件为真（即valid）。
例子：
✅ 有效推理： - \(\{p, p \rightarrow q\} \models q\)（Modus Ponens） - \(\{p \rightarrow q, \neg q\} \models \neg p\)（Modus Tollens） - \(\{p \land q\} \models p\)（合取消除）
❌ 无效推理（常见谬误）： - \(\{p \rightarrow q, q\} \not\models p\)（肯定后件谬误） - \(\{p \rightarrow q, \neg p\} \not\models \neg q\)（否定前件谬误）
4.3 用真值表验证推理¶
步骤： 1. 列出所有原子命题的所有可能赋值（\(2^n\) 行） 2. 计算前提和结论的真值 3. 检查：是否存在前提全真但结论为假的行 - 不存在 → 有效 - 存在 → 无效（该行是反例）
完整例题：验证 \(\{p \rightarrow (p \land q)\} \models \neg q \rightarrow \neg p\)
步骤1：构造真值表
p | q | p∧q | p→(p∧q) | ¬q | ¬p | ¬q→¬p
---+---+-----+---------+----+----+-------
0 | 0 | 0 | 1 | 1 | 1 | 1
0 | 1 | 0 | 1 | 0 | 1 | 1
1 | 0 | 0 | 0 | 1 | 0 | 0
1 | 1 | 1 | 1 | 0 | 0 | 1
步骤2：标记前提为真的行
第1行：前提=1, 结论=1 ✓
第2行：前提=1, 结论=1 ✓
第3行：前提=0 (跳过)
第4行：前提=1, 结论=1 ✓
步骤3：结论
所有前提为真的行(1,2,4)，结论也为真
因此推理 VALID ✅
反例示例：验证 \(\{q, p \rightarrow q\} \models p\)
真值表：
p | q | p→q | 前提q | 前提p→q | 结论p | 分析
---+---+-----+-------+---------+-------+------
0 | 0 | 1 | 0 | 1 | 0 | 前提不全真
0 | 1 | 1 | 1 | 1 | 0 | ❌反例
1 | 0 | 0 | 0 | 0 | 1 | 前提不全真
1 | 1 | 1 | 1 | 1 | 1 | ✓
反例：第2行
前提全真 (q=1, p→q=1)
但结论为假 (p=0)
因此推理 INVALID ❌
4.4 可满足性（Satisfiability）¶
定义：公式 \(\phi\) 是可满足的，当且仅当至少存在一个赋值使其为真。
关系： - \(\phi\) 是satisfiable ⟺ \(\phi\) 不是contradiction - \(\phi\) 是valid ⟺ \(\neg \phi\) 是unsatisfiable
重要性：SAT问题是NP-完全问题 - 判断可满足性在理论上很难（指数时间） - 但验证一个解是容易的（多项式时间）
5. 证明系统P（可选内容）¶
⚠️ 提示：证明系统P不在Class Test 1考试范围，但了解它有助于理解后续的证明系统K。
5.1 什么是形式化证明？¶
从 \(\Gamma\) 到 \(\phi\) 的证明是一个编号的公式列表，满足： 1. 最后一行是结论 \(\phi\) 2. 每一行都有正当理由（Justification）： - Premise：来自 \(\Gamma\) - Axiom：来自证明系统的公理 - Rule：从前面的行通过规则推导
5.2 证明系统P的公理¶
蕴含公理（→）： - (→1)：\(\phi \rightarrow (\psi \rightarrow \phi)\) - (→2)：\((\phi \rightarrow (\chi \rightarrow \psi)) \rightarrow ((\phi \rightarrow \chi) \rightarrow (\phi \rightarrow \psi))\)
合取公理（∧）： - (∧1)：\((\phi \land \psi) \rightarrow \phi\) - (∧2)：\((\phi \land \psi) \rightarrow \psi\) - (∧3)：\(\phi \rightarrow (\psi \rightarrow (\phi \land \psi))\)
析取公理（∨）： - (∨1)：\(\phi \rightarrow (\phi \lor \psi)\) - (∨2)：\(\psi \rightarrow (\phi \lor \psi)\) - (∨3)：\(((\phi \rightarrow \chi) \land (\psi \rightarrow \chi)) \rightarrow ((\phi \lor \psi) \rightarrow \chi)\)
否定公理（¬）： - (¬1)：\(((\phi \rightarrow \psi) \land (\phi \rightarrow \neg \psi)) \rightarrow \neg \phi\) - (¬2)：\((\phi \land \neg \phi) \rightarrow \psi\) - (¬3)：\(\phi \lor \neg \phi\)
双向蕴含公理（↔）： - (↔1)：\((\phi \leftrightarrow \psi) \rightarrow (\phi \rightarrow \psi)\) - (↔2)：\((\phi \leftrightarrow \psi) \rightarrow (\psi \rightarrow \phi)\) - (↔3)：\(((\phi \rightarrow \psi) \land (\psi \rightarrow \phi)) \rightarrow (\phi \leftrightarrow \psi)\)
推理规则： - Modus Ponens (MP)：从 \(\phi\) 和 \(\phi \rightarrow \psi\) 推出 \(\psi\)
5.3 证明示例¶
证明：\(p \land q \vdash_{\mathcal{P}} q \land p\)
1. p ∧ q Premise
2. (p ∧ q) → p (∧1)
3. (p ∧ q) → q (∧2)
4. p MP on 1,2
5. q MP on 1,3
6. q → (p → (q ∧ p)) (∧3)
7. p → (q ∧ p) MP on 5,6
8. q ∧ p MP on 4,7
5.4 记号说明¶
语义推理（Semantic Entailment）： [ \Gamma \models \phi ] 基于含义，用真值表验证
语法推理（Syntactic Derivation）： [ \Gamma \vdash_{\mathcal{P}} \phi ] 基于符号操作，用形式化证明
6. 可靠性与完备性¶
6.1 可靠性（Soundness）¶
定义： [ \text{如果 } \Gamma \vdash_{\mathcal{P}} \phi, \text{ 则 } \Gamma \models \phi ]
含义：证明系统不会产生假阳性 - 如果能证明，那么语义上也有效 - 证明系统不会证明错误的东西
6.2 完备性（Completeness）¶
定义： [ \text{如果 } \Gamma \models \phi, \text{ 则 } \Gamma \vdash_{\mathcal{P}} \phi ]
含义：证明系统不会产生假阴性 - 如果语义上有效，一定能找到证明 - 证明系统足够强大
6.3 重要性¶
证明系统P是可靠且完备的，因此： [ \Gamma \vdash_{\mathcal{P}} \phi \Longleftrightarrow \Gamma \models \phi ]
这保证了语法推理和语义推理的完全一致性。
7. 练习题¶
Exercise 7.1 - 公式分类¶
判断以下公式是 valid、contradiction 还是 contingent？
- \(p \rightarrow (q \rightarrow p)\)
- \(p \rightarrow (p \rightarrow q)\)
- \(p \lor \neg q\)
- \((p \rightarrow q) \lor (q \rightarrow p)\)
- \(p \land \neg p\)
- \((p \lor q) \rightarrow p\)
答案
1. **Valid** —— 蕴含公理(→1) 2. **Contingent** —— 当p=1,q=0时为假 3. **Contingent** —— 取决于赋值 4. **Valid** —— 验证真值表 5. **Contradiction** —— 矛盾律 6. **Contingent** —— 当p=0,q=1时为假Exercise 7.2 - 真值表验证¶
使用真值表验证以下推理：
- \(\{p, p \rightarrow q\} \models q\)
- \(\{\neg q, p \rightarrow q\} \models \neg p\)
- \(\{p, p \rightarrow q, \neg r \rightarrow \neg q\} \models r\)
答案
1. **Valid** —— Modus Ponens 2. **Valid** —— Modus Tollens 3. **Valid** —— 链式推理 详细真值表请自行构造练习。Exercise 7.3 - 构造反例¶
给出以下无效推理的反例：
- \(\{q, p \rightarrow q\} \models p\)
- \(\{\neg p, p \rightarrow q\} \models \neg q\)
答案
1. **反例**：\(V(p)=0, V(q)=1\) - 前提全真，结论为假 2. **反例**：\(V(p)=0, V(q)=1\) - 前提全真，结论为假Exercise 7.4 - 等价性证明¶
用真值表证明以下等价关系：
- \(\neg(p \land q) \equiv \neg p \lor \neg q\)（德摩根律）
- \(p \rightarrow q \equiv \neg q \rightarrow \neg p\)（逆否命题）
- \(p \rightarrow (q \rightarrow r) \equiv (p \land q) \rightarrow r\)
8. 考试重点¶
8.1 Class Test 1命题逻辑部分（约20分）¶
根据2019和2022年真题：
第1题：概念解释（5分）
问题：解释 \(\Gamma \models \phi\) 的含义
答题要点： - 对于所有赋值 \(V\)... - 如果 \(\Gamma\) 中所有公式为真... - 则 \(\phi\) 也为真
第2题：方法说明（5分）
问题：如何用真值表验证推理有效性
答题要点： - 列出所有原子命题的赋值组合 - 计算前提和结论的真值 - 检查是否存在前提全真但结论为假的行 - 不存在则有效，存在则无效
第3题：实际验证（10-11分）
问题：用真值表判断具体推理是否valid
答题结构： 1. 画出完整真值表（使用代码块格式） 2. 标注前提为真的行 3. 检查这些行的结论 4. 给出明确结论
8.2 答题模板¶
问题：判断 \(\{p \rightarrow (p \land q)\} \models \neg q \rightarrow \neg p\)
步骤1：构造真值表
p | q | p∧q | p→(p∧q) | ¬q | ¬p | ¬q→¬p
---+---+-----+---------+----+----+-------
0 | 0 | 0 | 1 | 1 | 1 | 1
0 | 1 | 0 | 1 | 0 | 1 | 1
1 | 0 | 0 | 0 | 1 | 0 | 0
1 | 1 | 1 | 1 | 0 | 0 | 1
步骤2：分析
前提为真的行：第1、2、4行
- 第1行：结论为真 ✓
- 第2行：结论为真 ✓
- 第4行：结论为真 ✓
步骤3：结论
在所有前提为真的行中，结论也为真。
因此，{p→(p∧q)} ⊨ ¬q→¬p 是 VALID。
8.3 必须掌握的技能¶
| 技能 | 重要程度 | 练习建议 |
|---|---|---|
| 快速构造真值表 | ⭐⭐⭐⭐⭐ | 每天练5题 |
| 理解蕴含的空虚为真 | ⭐⭐⭐⭐⭐ | 专项练习 |
| 识别反例 | ⭐⭐⭐⭐ | 练无效推理 |
| 清晰解释过程 | ⭐⭐⭐⭐ | 模拟写作 |
8.4 常见错误¶
❌ 错误1：忘记检查所有行 - 必须遍历整个真值表
❌ 错误2：混淆"前提假"和"推理无效" - 前提假的行可以跳过
❌ 错误3：蕴含理解错误 - \(p \rightarrow q\) 在 \(p=0\) 时总是真
❌ 错误4：省略解释 - 必须有清晰的文字说明
8.5 三天复习计划¶
Day 1（今天）： - 复习所有定义 - 做10道真值表练习 - 熟记等价式
Day 2（明天）： - 做2019 Class Test 1命题逻辑部分 - 对照答案找错误 - 总结答题技巧
Day 3（考前）： - 做2022 Class Test 1命题逻辑部分 - 计时模拟考试 - 整理错误清单
9. 公式速查表¶
9.1 重要等价公式¶
| 名称 | 公式 |
|---|---|
| 德摩根律 | \(\neg(p \land q) \equiv \neg p \lor \neg q\) |
| 德摩根律 | \(\neg(p \lor q) \equiv \neg p \land \neg q\) |
| 双重否定 | \(\neg \neg p \equiv p\) |
| 蕴含消除 | \(p \rightarrow q \equiv \neg p \lor q\) |
| 逆否命题 | \(p \rightarrow q \equiv \neg q \rightarrow \neg p\) |
| 双向蕴含 | \(p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)\) |
| 分配律 | \(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\) |
| 分配律 | \(p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)\) |
| 交换律 | \(p \land q \equiv q \land p\) |
| 结合律 | \((p \land q) \land r \equiv p \land (q \land r)\) |
| 幂等律 | \(p \land p \equiv p\) |
| 吸收律 | \(p \land (p \lor q) \equiv p\) |
9.2 重要推理规则¶
| 名称 | 规则 | 拉丁名 |
|---|---|---|
| 分离规则 | \(\{p, p \rightarrow q\} \models q\) | Modus Ponens |
| 否定后件式 | \(\{p \rightarrow q, \neg q\} \models \neg p\) | Modus Tollens |
| 假言三段论 | \(\{p \rightarrow q, q \rightarrow r\} \models p \rightarrow r\) | Hypothetical Syllogism |
| 析取三段论 | \(\{p \lor q, \neg p\} \models q\) | Disjunctive Syllogism |
| 合取引入 | \(\{p, q\} \models p \land q\) | Conjunction Introduction |
| 合取消除 | \(\{p \land q\} \models p\) | Conjunction Elimination |