CS50ai: week1 knowledge我的笔记A版

haa_y

1092人浏览 · 2025-09-20 14:47:53

haa_y · 2025-09-20 14:47:53 发布

该篇文章为随手笔记，如想要阅读更系统与细致的笔记请阅读B版

knowledge-based agents

agents that reason by operating on internal representations of knowledge

sentence

an assertion about the world in a knowledge representation language

Proposition Symbols

P Q R（每个符号代表着一个知识或者一个事实）

Logical Connectives

Not

And

其中一者为Flase，and都为False，都为True时and为Ture

Or

符号和and相比倒置
其中一者为True，or都为True，都为False时or为False
exclusive

Implication

Read: P implies Q , 表示if P 则 Q 单条件，“意味着”

如果P is false,那么Q无所谓（没有条件假设），都为true(前件为假，蕴含式恒真)
如果整件事都是真的，那么右边一定为True

Biconditional

双条件相同才成立，only true when P is same with Q

model

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

assignment of a truth value to every propositional symbol (a "possible world")

knowledge base

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

a set of sentences known by a knowledge-based agent

Entailment

Alpha entails Beta 这是决定关系
通过多个entailment来进行判断，这个过程就叫做推理

inference

the process of deriving new sentences from old ones

首先定义三个命题符号（不论对错）
KB（Knowledge Base）解析：(P and not Q) implies R周二并且不下雨，意味着去跑步

Does KB entail Alpha?

通过我们知识库的知识能否得出Alpha是正确的这个结论

要进行Model Checking
记住: model is just some assignment of all of the propositional symbols inside of our language to a truth value, true or false.
print(knowledge.formula())可以看我们的蕴含式符号表示

Model Checking

To determine if KB = α:
- Enumerate all possible models.
- If in every model where KB is true, a(Alpha)is true, then KB entails a.

Example:

Query及Alpha
列出了所有各种的可能
在这个知识中只有一个世界是真实的（知识库 (KB) 要同时满足 “自身的逻辑式为真”，以及题目中额外给定的事实（P 为真、not Q 为真））
From logic import *
如果KB不为True，我们就不会去验证和关心Query是不是为True

model_check(knowledge, rain)用knowledge来检查是否rain，结果是不存在满足knowledge且not rain的世界，因此为True
Limitation: 模型检验在符号数量 N 较大时计算不可行：2N 个模型呈指数级增长（例如 N=30 时，模型数达 10 亿）

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

Logical Encoding（逻辑编码）

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

游戏: Logic Puzzles

Gilderoy, Minerva, Pomona and Horace each belong to a different one of the four houses: Gryffindor, Hufflepuff, Ravenclaw, and Slytherin House.

Gilderoy belongs to Gryffindor or Ravenclaw.

Pomona does not belong in Slytherin.

Minerva belongs to Gryffindor.

列出所有的可能（不确定真假）
每个人只住一个房子，每个房子只住一人，因此：

# Only one house per person.
for person in people:
    for h1 in houses:
        for h2 in houses:
            if h1 != h2:
                knowledge.add(Implication(Symbol(f"{person}{h1}"), Not(Symbol(f"{person}{h2})
# Only one person per house.(代码基本同上)

添加题干的三个条件：
最后遍历得到各个Symbols是否为True

游戏: Mstermind

如图有四种颜色，其中第一行只有两个颜色的位置是正确的，而第二行无正确位置的颜色，求每个颜色的正确位置

但随着变量的增加，model check也会越来越慢变得不太合适

Inference rules

Modus Ponens

与model check完全不同
Model check查看所有的世界并查看每个世界的真实情况
Modus Ponens不处理特定世界，只处理我们知道的知识以及基于这些知识得出的结论

And Elimination

a and b 是True, 那么a也一定是True

Double Negation Elimination

如果前提中有两个not, 那我们可以将他们全部删掉

Implication Elimination（“蕴含消除”）

将if/then转化为or语句的方法

If: 要么没发生，要么完全对

Biconditional Elimination

双条件消除，A当且仅当A时B

如果下雨了且仅在下雨时Harry在屋内

——如果下雨Harry就在屋里，如果Harry在屋里就说明下雨了

De Morgan's Law

简单来说，就是把整体的not符号可以提到两个变量，两变量中间and or变换

将and变成or, “他和她有一个没有/有”变成了“要么他没有要么她没有”

另一个说法，“不是他或她有xx”变成了“他和她都没有xx”

Distributive Property

分配属性，相当于分配律

Theorem Proving（定理证明）

initial state: starting knowledge base
actions: inference rules
transition model: new knowledge base after inference
goal test: check statement we're trying to prove
path cost function: number of steps in proof
像是search一样处理knowledge

Resolution

使用冲突和矛盾来确定事实，通过二式推一式
如果我们有P or Q，以及not P, 那么则Q(其中的P、Q也可以不只是一个proposition symbol，也可以是一个蕴含式)

clauses

a disjunction of literals

子句

Where a disjunction means it's a bunch of things that are connected with or.
Disjunction means things connected with or.
Conjunction, meanwhile, is things connected with and.
a literal is either a propositional symbol or the opposite propositional symbol

conjunctive normal form

logical sentence that is a conjunction of clauses

合取范式（将双条件，蕴含......转化为更符合范式的形式）

要求子句和子句（clause and clause）
例子如下，只存在and not or

Conversion to CNF

eliminate消除蕴含式

Eliminate biconditionals
- turn (α 双箭头 β)into (α→β) ^ (β→α)
Eliminate implications
- turn (α→β) into ﹁ α ν β
Move ﹁ inwards using De Morgan's Laws德摩根定理
Use distributive law to distribute v wherever possiblee分配属性

Example:

此时最后化为了合取范式conjunctive normal form

Inference by resolution

根据两个clauses的冲突推理得到结论clause

To determine if KB |= a:

Check if (KB ^ ﹁α) is a contradiction?

If so, then KB = α.

Otherwise, no entailment.

反证法思想证明冲突否

To determine if KB = a:

Convert (KB ^ ﹁α) to Conjunctive Normal Form.

Keep checking to see if we can use resolution to produce a new clause.

  If ever we produce the empty clause (equivalent to False), we have a contradiction, and KB = α.

  Otherwise, if we can't add new clauses, no entailment.

  寻找新子句，反复寻找各个句子间是否有冲突或者补充产生新子句

在编程中进行，只需要遍历所有可能的子句并对其检查是否有可补充产生的新子句

factoring

分解，提取任何出现的重复变量并消除

如果遇到了这样的，则得出empty clause，它恒为False

First Order Logic(FOL)

前面所讲都为Propositional Logic 命题逻辑
提供两个符号来解决（Constant Symbol Predicate Symbol）
- Constant Symbol常量符号（比如：具体人名Minerva）
- Predicate Symbol谓词符号（比如：person,house等代称）