Knowledge-Based Agents & Logical Reasoning

1. Knowledge-Based Agents（基于知识的智能体）

指通过对知识的内部表示进行操作来推理和行动的智能体。

• 在智能体内部，其能理解“知道”的含义（例如，区分关于世界的事实是真还是假）。
• 配备算法或技术，可利用存储的知识解决问题或推导新的有用信息。

2. Core Definitions（核心定义）

2.1 Sentence（语句）

用知识表示语言（一种为计算机编码知识的方式）表达的关于世界的断言。

• 本课程中，我们主要以命题逻辑（Propositional Logic） 作为核心表示语言，命题逻辑用于对“命题”（关于世界的陈述）进行推理。

2.2 Propositional Symbols（命题符号）

• 符号（如 P、Q、R），代表关于世界的特定事实（每个符号非真即假）。
• 示例：
  • P = “It is raining”（正在下雨）
  • Q = “Harry visited Hagrid today”（哈利今天拜访了海格）
  • R = “Harry will go for a run”（哈利会去跑步）

2.3 Logical Connectives（逻辑连接词）

用于组合命题符号以表达复杂关系的符号。以下是 5 个核心连接词，附带它们的真值表（Truth Table）（定义组合语句何时为真/假）：

Connective（连接词）	Symbol (Text)（符号/文本）	Meaning（含义）	Truth Rule & Example（真值规则及示例）
Not（非）	¬ (Not)	“相反情况”	反转真值：若 P（下雨）为真，则 ¬P（没下雨）为假。 真值表：P=False → ¬P=True；P=True → ¬P=False。
And（与）	∧ (And)	“两者都为真”	仅当两个操作数都为真时为真（否则为假）。 示例：P∧Q（下雨且哈利拜访海格）仅在 P 和 Q 都为真时成立。 真值表：4 种情况（P/Q：F/F→F、F/T→F、T/F→F、T/T→T）。
Or（或）	∨ (Or)	“至少一个为真”	若任一操作数为真则为真（仅当所有操作数都为假时才为假）。 注意：此处为“兼容或（Inclusive Or）”，即 P∨Q 允许 P 和 Q 同时为真；“互斥或（Exclusive Or，仅其一为真）”本次不涉及。 示例：P∨Q（下雨或哈利拜访海格）仅在“既没下雨也没拜访”时为假。
Implication（蕴含）	→ (Implies)	“若 P，则 Q”	仅当P 为真且 Q 为假时为假（其他所有情况均为真）。 关键：若 P 为假（无此条件），则蕴含式“默认成立”（不对 Q 做任何断言）。 示例：P→Q（若下雨，则哈利待在室内）仅在“下雨（P=True）但哈利外出（Q=False）”时为假。
Biconditional（双蕴含）	↔ (Iff)	“P 当且仅当 Q”	仅当P 和 Q 真值相同（都为真或都为假）时为真。 示例：P↔Q（下雨当且仅当哈利待在室内）意味着：下雨（P=True）则哈利在室内（Q=True）；哈利在室内（Q=True）则下雨（P=True）。

2.4 Model（模型）

为每个命题符号分配一个真值（真/假） 的过程——代表一个“可能世界（Possible World）”。

• 示例：对于符号 P（下雨）和 Q（周二），一个模型可以是：P=True，Q=False（下雨，且不是周二）。
• N 个符号对应的模型数量：(2^N)（每个符号有 2 种选择，相互独立）。

2.5 Knowledge Base (KB)（知识库）

智能体已知为真的一组命题逻辑语句。

• 智能体将关于世界的事实（如问题约束、观察结果）存储在知识库中。
• 示例（哈利·波特知识库）：
  1. ¬Rain → Hagrid（若没下雨，则哈利拜访了海格）
  2. Hagrid ∨ Dumbledore（哈利拜访了海格或邓布利多）
  3. ¬(Hagrid ∧ Dumbledore)（哈利没有同时拜访两人）
  4. Dumbledore（哈利拜访了邓布利多）

2.6 Entailment（蕴含关系）

一种逻辑关系：若语句 α 为真，则语句 β 在所有可能世界中也必为真。

• 符号表示：(KB \models \alpha)（读作“KB 蕴含 α”，即 KB 的真值可保证 α 的真值）。
• 示例：α = “It is Tuesday in January”（1 月的某个周二）蕴含 β = “It is January”（现在是 1 月）——所有使 α 为真的世界，β 也必然为真。

2.7 Inference（推理）

从知识库中推导新语句的过程（利用逻辑得出结论）。

• 示例：从上述哈利·波特知识库中，可推理出两个结论：
  1. ¬Hagrid（哈利没拜访海格——因为他拜访了邓布利多，且未同时拜访两人）
  2. Rain（下雨了——因为 ¬Rain → Hagrid 为真，但 Hagrid 为假，故 ¬Rain 必为假）

3. Model Checking: An Inference Algorithm（模型检验：一种推理算法）

一种简单（但效率较低）的算法，通过枚举所有可能模型来判断 (KB \models \alpha)（知识库是否蕴含查询 α）。

3.1 How It Works（工作原理）

1. Enumerate all models（枚举所有模型）：列出所有命题符号的真值组合（总数为 (2^N)）。
2. Filter valid models（筛选有效模型）：仅保留使知识库 KB 为真的模型（这些是“与智能体已知事实一致的可能世界”）。
3. Check entailment（检查蕴含关系）：若 α 在所有有效模型中都为真，则 (KB \models \alpha)；否则不蕴含。

3.2 Example（示例）

• 符号：P（Tuesday，周二）、Q（rain，下雨）、R（Harry runs，哈利跑步）。
• 知识库 KB：(P ∧ ¬Q) → R（若周二且没下雨，则哈利跑步）、P（是周二）、¬Q（没下雨）。
• 查询 α：R（哈利跑步）。

步骤 1：枚举 8 个模型（3 个符号 → (2^3=8)）。
步骤 2：筛选有效模型：仅满足“P=True、¬Q=True、(P∧¬Q)→R=True”的模型，最终只剩 1 个：P=True、Q=False、R=True。
步骤 3：检查 α：R 在有效模型中为真 → (KB \models R)。

3.3 Limitation（局限性）

模型检验在符号数量 N 较大时计算不可行：(2^N) 个模型呈指数级增长（例如 N=30 时，模型数达 10 亿）。

4. Practical Examples: Knowledge Engineering（实际案例：知识工程）

知识工程是将现实问题转化为逻辑符号和语句，以便智能体推理的过程。以下是 3 个案例：

4.1 Game: Clue（《妙探寻凶》游戏）

Problem Setup（问题背景）

• 目标：找出凶手（Mustard/Plum/Scarlet）、犯罪地点（Ballroom/Kitchen/Library）和凶器（Knife/Revolver/Wrench）。
• 规则：每个类别选 1 张牌隐藏；玩家通过手中的牌排除选项。

Logical Encoding（逻辑编码）

• Propositional Symbols（命题符号）：Mustard（真=凶手）、Plum、 Scarlet、Ballroom、Kitchen、Library、Knife、Revolver、Wrench。
• Initial KB（初始知识库）：
  1. Mustard ∨ Plum ∨ Scarlet（必有一名凶手）
  2. Ballroom ∨ Kitchen ∨ Library（必有一个犯罪地点）
  3. Knife ∨ Revolver ∨ Wrench（必有一件凶器）
• Added Knowledge（游戏过程中添加的知识）：
  • 若你持有 Mustard 牌：添加 ¬Mustard（Mustard 不是凶手）。
  • 若某猜测（Scarlet、Library、Wrench）被揭示：添加 ¬Scarlet ∨ ¬Library ∨ ¬Wrench（至少一个不在隐藏牌中）。

Inference Result（推理结果）

添加知识 ¬Mustard、¬Kitchen、¬Revolver、¬Plum、¬Ballroom 后：
(KB \models Scarlet)（Scarlet 是凶手）、(KB \models Library)（犯罪地点是图书馆）、(KB \models Knife)（凶器是刀）。

4.2 Logic Puzzle: Hogwarts Houses（霍格沃茨学院逻辑谜题）

Problem Setup（问题背景）

• 人物：Gilderoy、Minerva、Pomona、Horace。
• 学院：Gryffindor（格兰芬多）、Hufflepuff（赫奇帕奇）、Ravenclaw（拉文克劳）、Slytherin（斯莱特林）。
• 规则：每人仅属一个学院；每个学院仅一人。
• 已知事实：
  1. Gilderoy ∈ Gryffindor ∨ Gilderoy ∈ Ravenclaw（吉德罗在格兰芬多或拉文克劳）
  2. Pomona ∉ Slytherin（波莫娜不在斯莱特林）
  3. Minerva ∈ Gryffindor（米勒娃在格兰芬多）

Logical Encoding（逻辑编码）

• Propositional Symbols（命题符号）：GilderoyGryffindor、GilderoyHufflepuff、…、HoraceSlytherin（共 16 个：4 人 × 4 学院）。
• Initial KB Constraints（初始知识库约束）：
  1. 每人必属一个学院：例如 GilderoyGryffindor ∨ GilderoyHufflepuff ∨ GilderoyRavenclaw ∨ GilderoySlytherin。
  2. 每人仅属一个学院：例如 Implication(GilderoyGryffindor, ¬GilderoyHufflepuff)（若吉德罗在格兰芬多，则不在赫奇帕奇）。
  3. 每个学院仅一人：例如 Implication(MinervaRavenclaw, ¬GilderoyRavenclaw)（若米勒娃在拉文克劳，则吉德罗不在）。
• Added Facts（添加的已知事实）：
  1. GilderoyGryffindor ∨ GilderoyRavenclaw
  2. ¬PomonaSlytherin
  3. MinervaGryffindor

Inference Result（推理结果）

(KB \models)（知识库蕴含）：

• GilderoyRavenclaw（吉德罗在拉文克劳）、PomonaHufflepuff（波莫娜在赫奇帕奇）、MinervaGryffindor（米勒娃在格兰芬多）、HoraceSlytherin（霍拉斯在斯莱特林）。

4.3 Game: Mastermind（《珠玑妙算》游戏）

Problem Setup（问题背景）

• 目标：找出 4 种颜色（Red/Blue/Green/Yellow）的排列顺序。
• 线索：
  1. 猜测 1：Red、Blue、Green、Yellow → 2 个位置正确。
  2. 猜测 2：Blue、Red、Green、Yellow → 0 个位置正确。

Logical Encoding（逻辑编码）

• Propositional Symbols（命题符号）：Red0（红色在位置 0）、Red1、…、Yellow3（共 16 个：4 个位置 × 4 种颜色）。
• KB Constraints（知识库约束）：
  1. 每个位置仅有一种颜色：例如 Red0 ∨ Blue0 ∨ Green0 ∨ Yellow0；Implication(Red0, ¬Blue0)（若红色在位置 0，则蓝色不在）。
  2. 每种颜色仅在一个位置：例如 Implication(Red0, ¬Red1)（若红色在位置 0，则不在位置 1）。
• Clue 1（线索 1）：(Red0, Blue1, Green2, Yellow3) 中恰好 2 个为真。
• Clue 2（线索 2）：(Blue0, Red1, Green2, Yellow3) 中全为假。

Inference Result（推理结果）

(KB \models Red0)（红色在位置 0）、(KB \models Blue1)（蓝色在位置 1）、(KB \models Yellow2)（黄色在位置 2）、(KB \models Green3)（绿色在位置 3），即排列顺序为 Red→Blue→Yellow→Green。

5. Inference Rules: A More Efficient Alternative（推理规则：更高效的替代方案）

推理规则无需枚举模型，直接从知识库推导新语句（无需检查所有可能世界）。以下是核心规则，符号 (\vdash) 表示“推导出”：

5.1 Modus Ponens（假言推理）

• Rule（规则）：若 (α→β)（若 α 则 β）和 (α) 都为真，则 (β) 为真。
• Notation（符号表示）：(α→β, α \vdash β)
• Example（示例）：KB = “Rain→Indoors（下雨则待室内）, Rain（下雨）” → 推理结果：“Indoors（待室内）”。

5.2 And Elimination（与消除）

• Rule（规则）：若 (α∧β)（α 且 β）为真，则 (α)（或 (β)）为真。
• Notation（符号表示）：(α∧β \vdash α)
• Example（示例）：KB = “Hagrid∧Dumbledore（拜访海格且邓布利多）” → 推理结果：“Hagrid（拜访海格）”。

5.3 Double Negation Elimination（双重否定消除）

• Rule（规则）：两个否定词相互抵消。
• Notation（符号表示）：(\neg\negα \vdash α)
• Example（示例）：KB = “¬¬(Harry passed)（并非哈利没通过）” → 推理结果：“Harry passed（哈利通过）”。

5.4 Implication Elimination（蕴含消除）

• Rule（规则）：将蕴含式转化为“或”语句。
• Notation（符号表示）：(α→β \vdash \negα∨β)
• Example（示例）：KB = “Rain→Indoors（下雨则待室内）” → 推理结果：“¬Rain∨Indoors（没下雨，或下雨且待室内）”。

5.5 Biconditional Elimination（双蕴含消除）

• Rule（规则）：双蕴含式（“当且仅当”）可拆分为两个蕴含式的组合。
• Notation（符号表示）：(α↔β \vdash (α→β)∧(β→α))
• Example（示例）：KB = “Rain↔Indoors（下雨当且仅当待室内）” → 推理结果：“(Rain→Indoors)∧(Indoors→Rain)（下雨则待室内，且待室内则下雨）”。

5.6 De Morgan’s Laws（德摩根定律）

• Rule 1（规则 1）：“与”的否定 → “或”的否定。
  • Notation（符号表示）：(\neg(α∧β) \vdash \negα∨\negβ)
  • Example（示例）：KB = “¬(Harry passed∧Ron passed)（并非哈利和罗恩都通过）” → 推理结果：“¬Harry passed∨¬Ron passed（哈利没通过或罗恩没通过）”。
• Rule 2（规则 2）：“或”的否定 → “与”的否定。
  • Notation（符号表示）：(\neg(α∨β) \vdash \negα∧\negβ)
  • Example（示例）：KB = “¬(Harry passed∨Ron passed)（并非哈利或罗恩通过）” → 推理结果：“¬Harry passed∧¬Ron passed（哈利和罗恩都没通过）”。

5.7 Distributive Property（分配律）

• Rule 1（规则 1）：“与”对“或”分配。
  • Notation（符号表示）：(α∧(β∨γ) \vdash (α∧β)∨(α∧γ))
• Rule 2（规则 2）：“或”对“与”分配。
  • Notation（符号表示）：(α∨(β∧γ) \vdash (α∨β)∧(α∨γ))
• Example（示例）：KB = “Tuesday∧(Rain∨Windy)（周二且下雨或刮风）” → 推理结果：“(Tuesday∧Rain)∨(Tuesday∧Windy)（周二且下雨，或周二且刮风）”。

5.8 Theorem Proving as Search（定理证明即搜索）

推理规则将定理证明（检查 (KB \models α)）转化为搜索问题：

• Initial State（初始状态）：知识库 KB（已知语句集合）。
• Actions（行动）：应用任意推理规则推导新语句。
• Transition Model（转移模型）：新知识库 = 旧知识库 + 新推导语句。
• Goal Test（目标测试）：检查 α 是否在知识库中。
• Path Cost（路径代价）：推理步骤数（需最小化）。

6. Resolution: A Powerful Inference Technique（决议法：一种强大的推理技术）

决议法是单一且强大的规则，可证明任何存在的蕴含关系。其依赖合取范式（Conjunctive Normal Form, CNF） 和反证法（Proof by Contradiction）。

6.1 Key Definitions for Resolution（决议法核心定义）

• Literal（文字）：命题符号或其否定（如 P、¬Q）。
• Clause（子句）：文字的析取（“或”组合，如 P∨Q∨¬R）。
• Conjunctive Normal Form (CNF)（合取范式）：由子句的合取（“与”组合）构成的语句（如 (P∨Q)∧(¬R∨S)∧T）。
  • 任何逻辑语句都可转化为合取范式（见 6.2 节）。

6.2 Converting to CNF (4 Steps)（转化为合取范式的 4 步）

1. Eliminate biconditionals（消除双蕴含）：将 (α↔β) 替换为 ((α→β)∧(β→α))。
2. Eliminate implications（消除蕴含）：将 (α→β) 替换为 (\negα∨β)。
3. Move negations inward（否定词内移）：利用德摩根定律（如 (\neg(α∧β)→\negα∨\negβ)）。
4. Distribute OR over AND（“或”对“与”分配）：利用分配律（如 ((¬P∧¬Q)∨R→(¬P∨R)∧(¬Q∨R))）。

Example Conversion（转化示例）

• 原始语句：((P∨Q)→R)
• 步骤 1：无双向蕴含 → 跳过。
• 步骤 2：将“→”替换为“¬∨” → (\neg(P∨Q)∨R)。
• 步骤 3：否定词内移（德摩根定律） → ((¬P∧¬Q)∨R)。
• 步骤 4：分配“或” → ((¬P∨R)∧(¬Q∨R))（合取范式）。

6.3 Resolution Rule（决议规则）

• Core Idea（核心思想）：若两个子句包含互补文字（P 和 ¬P），则可将它们决议为一个新子句（合并其他所有文字）。
• Notation（符号表示）：
  • 子句 1：(P∨α)（α 为任意文字的析取）
  • 子句 2：(\negP∨β)（β 为任意文字的析取）
  • 决议子句：(α∨β)
• Example（示例）：
  • 子句 1：(A∨B)
  • 子句 2：(\negB∨C)
  • 决议子句：(A∨C)

6.4 Inference by Resolution (Proof by Contradiction)（决议推理：反证法）

要证明 (KB \models α)（知识库蕴含 α）：

1. Assume ¬α（假设 α 为假）：采用反证法，假设查询结果不成立。
2. Convert (KB∧¬α) to CNF（将 (KB∧¬α) 转化为合取范式）：所有语句变为子句，通过“与”连接。
3. Resolve clauses repeatedly（反复决议子句）：
   • 对每对子句，检查是否存在互补文字。
   • 若存在，决议生成新子句（添加到子句集合中）。
   • Factoring（因子提取）：移除重复文字（如 (Q∨S∨R∨S→Q∨R∨S)）。
4. Check for empty clause（检查空字句）：
   • 若生成空字句（⊥）：出现矛盾！（⊥ 等价于“假”，仅当 (KB∧¬α) 不可能成立时才会出现），故 (KB \models α)。
   • 若无法生成新子句：无蕴含关系（(KB \nvdash α)）。

6.5 Example Resolution Proof（决议证明示例）

• KB（知识库）：((A∨B)∧(¬B∨C)∧¬C)
• Query α（查询）：A

步骤 1：假设 α 为假 → ¬A。
步骤 2：(KB∧¬A) 的合取范式：((A∨B), (¬B∨C), ¬C, ¬A)。
步骤 3：决议子句：

• 决议 ((¬B∨C)) 和 (¬C) → (\negB)。
• 决议 ((A∨B)) 和 (\negB) → A。
• 决议 A 和 ¬A → ⊥（空字句）。
  步骤 4：生成空字句 → (KB \models A)（知识库蕴含 A）。

7. First-Order Logic (FOL): Beyond Propositional Logic（一阶逻辑：超越命题逻辑）

命题逻辑在复杂问题中存在局限性（如霍格沃茨谜题需 16 个符号）。一阶逻辑（FOL）通过引入对象（Objects） 和关系（Relations） 提升表达能力，减少冗余。

7.1 FOL Symbols（一阶逻辑符号）

• Constant Symbols（常量符号）：代表特定对象（如 Minerva、Gryffindor、Pomona）。
• Predicate Symbols（谓词符号）：代表属性（1 个参数）或关系（2 个及以上参数），对对象取真/假值。
  • 示例：
    • (Person(x))：x 是一个人（1 元谓词）。
    • (House(x))：x 是一个学院（1 元谓词）。
    • (BelongsTo(x,y))：x 属于 y（2 元谓词）。

7.2 FOL Sentences (Examples)（一阶逻辑语句示例）

• (Person(Minerva))：Minerva 是一个人。
• (House(Gryffindor))：Gryffindor 是一个学院。
• (BelongsTo(Minerva, Gryffindor))：Minerva 属于 Gryffindor 学院。
• (\neg House(Minerva))：Minerva 不是一个学院。

7.3 Quantifiers (FOL’s Superpower)（量词：一阶逻辑的核心优势）

量词让一阶逻辑能表达通用规则（无需为每个情况定义单独符号）。

1. Universal Quantification (∀x: “For all x”，全称量词)

• Meaning（含义）：某个语句对所有对象 x 都成立。
• Example（示例）：(\forall x (BelongsTo(x, Gryffindor) → \neg BelongsTo(x, Hufflepuff)))
  • 中文含义：“所有属于格兰芬多的人，都不属于赫奇帕奇。”

2. Existential Quantification (∃x: “There exists x”，存在量词)

• Meaning（含义）：某个语句对至少一个对象 x 成立。
• Example（示例）：(\exists x (House(x) ∧ BelongsTo(Minerva, x)))
  • 中文含义：“存在一个学院 x，Minerva 属于 x（即 Minerva 属于某个学院）。”

3. Combined Quantifiers（量词组合）

• Example（示例）：(\forall x (Person(x) → \exists y (House(y) ∧ BelongsTo(x,y))))
  • 中文含义：“对所有对象 x，若 x 是人，则存在一个学院 y，使得 x 属于 y（即每个人都属于某个学院）。”

8. Summary（总结）

• Knowledge-Based Agents（基于知识的智能体）：通过知识的内部表示进行推理。
• Propositional Logic（命题逻辑）：用符号和连接词编码事实，通过模型检验或推理规则实现推理。
• Resolution（决议法）：基于合取范式和反证法的高效推理技术。
• First-Order Logic（一阶逻辑）：比命题逻辑更具表达性，通过对象、谓词和量词建模通用规则。

注意：该文章为ai根据cs50ai视频与我的笔记生成，因逻辑清晰且更具阅读性而发布，仅供学习参考