文章目錄

• • • KBA(Knowledge based agent)與邏輯
    • • KBA
      • Wumpus世界
    • 知識庫KB的完備性、可靠性
    • 命題邏輯：一種簡單邏輯
    • • 語法
      • 語義
      • • 區分?和╞
    • 命題邏輯定理的證明
    • • 推導和證明
      • 歸結證明（只針對文字的析取式：子句）
      • • 單元歸結
        • 全歸結
        • 合取范式CNF
        • 析取范式DNF
        • 歸結算法-如何證明蘊含(歸結演繹推理)╞
      • horn子句和限定子句
      • 命題邏輯的前向鏈接和反向鏈接
      • • 前向鏈接
        • 反向鏈接
    • 總結
    • 資源分享

基于知識的Agent。第3,4章中的問題求解Agent有局限性，而且法法靈活性。
第6章介紹了 用變量賦值表示狀態的思想，這是朝向正確方向的一步，使得Agent的部分工作可以獨立于領域，并允許更有效的算法。

本文旨在講清楚：
1）KBA（knowledge based agent）與邏輯
2）模型，有效性，可滿足性，蘊含，推理過程
3）如何證明KB蘊含a（模型檢驗，邏輯等價，推理規則）

KBA(Knowledge based agent)與邏輯

KBA

基于知識的Agent的核心部件是其知識庫，或稱KB。
知識庫(KB)：是一個語句（用知識表示語言表達，表示了關于世界的某些斷言）集合。有時，當某語句是直接給定而不是推導得到的時候，我們將其尊稱為公理。

Ask：查詢目前所知內容
Tell：將新語句添加到知識庫
二者都涉及推理，即從原有語句中推導出新語句。

KBA（Knowledge based agent），即基于知識的Agent，通過感知器，把感知信息加入知識庫，向知識庫詢問最好改采取哪個行動，并告訴知識庫它會實施該行動。

Wumpus世界

PEAS描述：

• 1）性能度量：帶著金子爬出洞口+1000，掉入洞or被Wumpus吃-1000，采用一個行動-1，用掉箭-10。Agen死亡or出洞，則游戲結束。
• 2）環境：[1,1]始發為止，Wumpus，無底洞均勻分布
• 3）執行器：Agent移動，射箭。

Left turn,Right turn,Forward,Grab,Shoot

Agent可以向前移動、左轉或者右轉；

Agent碰上無底洞pit或者活著的Wumpus，它將悲慘的死去；

如果Agent前方是一堵墻，那么它將不能移動；

行動Grab可以用于撿起Agent所處方格內的物體；

行動Shoot用于向Agent所對的方向射箭，箭向前運動直到擊中Wumpus（此時Wumpus死亡）或者墻；

Agent只有一支箭；

行動Climb用于爬出洞口；

Wumpus不能移動

• 4）傳感器：5個
  Stench(臭氣) , in,4-adjacent
  Breeze(微風), 4-adjacent
  Glitter(閃光), in
  Bump(碰撞), walking into a wall
  Scream(尖叫), wumpus killed, anywhere

在與無底洞相鄰的方格內，Agent能感知到微風；

在與Wumpus相鄰的方格內，Agent能感受到臭氣；

在金子所處方格，Agent能感受到閃閃金光；

當Agent碰到墻時，它感知到碰撞；

當Wumpus被殺死后，它發出的嚎叫聲在洞穴（所有房間組成一個山洞）內的任何地方都能感受到；

Wumpus world can be solved using logic：

• Agent在[1,1]的感知是[None,None,None,None,None](對應于(stench ,breeze,glitter,bump,scream))，因此Agent可以判斷相鄰的[1,2]和[2,1]是安全的，標注為ok；
• 假設Agent移動到安全的[2,1]。Agent感受到微風，因此在相鄰的方格內必有一個無底洞。用于無底洞不可能在[1,1]，因此只能在[2,2]或者[3,1]或者二者都有，Pit？表示可能有無底洞；
• 此時標注ok的只有[1,2],因此Agent轉身到[1,1],然后前進到[1,2];
• Agent在[1,2]感受到臭氣，意味著周圍一定有Wumpus。而Wumpus不可能在[1,1],也不可能在[2,2],否則Agent在[2,1]時就會感受到臭氣；
• 前面講到無底洞在[2,2]或者[3,1],而在[1,2]中感受不到微風，因此無底洞不在[2,2],故只能在[3,1];
• 現在檢測到[2,2]中沒有無底洞和Wumpus，因此Agent可以移動到[2,2]；
• 假定Agent轉身并移動到[2,3]，感受到閃閃發光，撿到金子。

知識庫KB的完備性、可靠性

一個知識庫KB就是句子構成的集合。
一個模型m是一個知識庫的模型當且僅當這個模型是知識庫中所有句子的模型。也就是說在知識庫中的所有句子在模型m下都是真的。
例如：
KB={P, P∨R}
M(KB)={“P=T,R=T”,“P=T,R=F”}

一個知識庫KB是可滿足的當且僅當這個知識庫的模型M(KB)是非空集合。即，一個知識庫KB是不可滿足的當且僅當這個知識庫的模型M(KB)是空集。
KB1 = {P, ￢Q∧ R} is satisfiable
KB2 = {￢P∨RP} is satisfiable
KB3 = {P, ￢P} is unsatisfiable

知識庫KB蘊含α：KB ╞ α，
x+y = 4 ╞ 4 = x+y ? (yes)
x^2 +y^2 <=4 ╞ x^2 +y^2 <=16 ? (yes)
P ╞ P ∧ R ? (no)

KB ╞ α

• iff M(KB) ? M(α)
• iff {KB,￢α} is unsatisfiable,
• iff KB ? α is valid,
• iff KB,￢α ╞ False

推理算法i從KB中導出語句α或語句α通過i從KB導出記為: $KB{?}_i\alpha$
Soundness(可靠性)：對于推理過程i從KB推理出的每條語句α,都有KB╞α,則i是可靠的或真值保持的
Completeness(完備性)：對于KB蘊涵的每條語句α,推理過程i都能從KB推理出α,則i是完備的

命題邏輯：一種簡單邏輯

語法

原子語句：單個命題詞組成，每個命題詞代表一個真或假的命題
復合句：簡單語句和邏輯連接詞構造而成
文字：原子命題及其否定。
互補文字：一個文字是另一文字的否定。
子句：文字的析取式。單個文字可以被視為只有一個文字的析取式，也叫單元子句。
歸并：去除文字的多余副本。

5種常用邏輯連接詞：
1）非 ￢，否定式
2）與 ∧，合取式
3）或 ∨，析取式
4）蘊含 ?或→或?，蘊含式
蘊含式也稱為規則或if-then語句。
5）當且僅當 ?(英文：If and only if, 或者：iff)，雙向蘊含式

語義

定義了用于判定特定模型中的語句真值的規則。在命題邏輯里面，命題詞的真值只有兩個——true或false。

模型：語句α在模型m中為真，稱m滿足α，或者m是α的一個模型。M(α)表示α的所有模型。

• “x=2,y=2” is a model of x 2 +y 2 <=16
• “x=3,y=3” is not a model of x 2 +y 2 <=16
• “P=T,Q=T” is a model of P ∧ Q.
• “P=T,Q=F” is not a model of P ∧ Q

考慮一個具有四個命題A、B、C、D的詞表，對于下列語句分別有多少個模型？

• B∨C ,(2^4-1* 2^2=12)
• ￢A∨￢B∨￢C∨￢D ,(2^4-1=15)

區分?和╞

（1）?表示語言的一個組成部分
語句P?Q只有當P=true，Q=false時為False，其余為True。
P?Q等價于￢P∨Q
不要有P為真則Q為真的錯覺
命題邏輯不要求P和Q之間存在相關性或因果關系。例如，語句“5是奇數蘊含北京是中國的首都”是命題邏輯的真語句
前提為假的任意蘊含都為真

（2）╞表示推理，語句間的邏輯蘊含關系
邏輯蘊含關系類似于算術：語句x=0蘊含了語句xy=0。
α╞β（蘊含）當且僅當在使α為真的每個模型中，β也為真。
α╞β 當且僅當 M(α) ? M(β)
P?Q為假，除非P在m中為真且Q在m中為假

對任意語句α和β，α╞β 當且僅當語句α?β是有效的
對任意語句α和β，α╞β 當且僅當語句α∧￢β是不可滿足的

命題邏輯定理的證明

邏輯推理：用蘊含推導出結論
模型檢驗：通過枚舉所有可能的模型來檢驗KB為真的情況下α都為真，即M(KB) ? M(α)

有效性：一個語句是有效的，如果在所有的模型中它都為真。（有效語句也叫重言式——必定為真）例如￢P∨P為有效的
對任意語句α和β，α╞β 當且僅當語句α?β是有效的

可滿足性：如果一個語句在某些模型中為真，則可滿足。
對任意語句α和β，α╞β 當且僅當語句α∧￢β是不可滿足的

SAT問題：命題邏輯語句的可滿足性判定。是第一個被證明為NP完全的問題。（如CSP，就是詢問在某個賦值下約束是否滿足的）

單調性：邏輯蘊含語句集會隨著添加到知識庫的信息的增長而增長。
對任意語句α和β，如果KB╞α，那么KB∧β╞α

推導和證明

推導規則：
1）假言推理規則（Modus Ponens，拉丁文）

$$\frac{\alpha ?\beta ,\alpha }{\beta }$$

2）消去合取詞

$$\frac{\alpha \wedge \beta }{\alpha }$$
3）邏輯等價
邏輯等價：如果兩個語句在同樣的模型集合中為真，則二者邏輯等價。

$$\alpha ?\beta \equiv (\alpha ?\beta )\wedge (\beta ?\alpha )$$
$$\frac{\alpha ?\beta }{(\alpha ?\beta )\wedge (\beta ?\alpha )}$$
$$\frac{(\alpha ?\beta )\wedge (\beta ?\alpha )}{\alpha ?\beta }$$

任意搜索算法來找出證明序列，只需定義如下證明問題：

• 初始狀態：初始KB
• 行動：行動集合由應用于語句的所有推理規則組成
• 結果：將推理規則下半部分的語句實例加入KB
• 目標：要證明的語句狀態

（這叫搜索證明，是模型枚舉的一個替代方法）

歸結證明（只針對文字的析取式：子句）

單元歸結

若每個l都是一個文字，而且$l_i$和m是互補文字，則有：
$$\frac{l1\vee ...\vee l_k,m}{l1\vee ...\vee l_{i?1}\vee l_{i+1}\vee ,...,\vee l_k}$$

全歸結

$l_i$和$m_j$是互補文字：
$$\frac{l_1\vee ...\vee l_k,m_1\vee ...\vee m_n}{l_1\vee ...\vee l_{i?1}\vee l_{i+1}\vee ,...,\vee l_k\vee m_1\vee ...\vee m_{j?1}\vee m_{j+1}\vee ...\vee m_n}$$
歸結規則的可靠性證明：已知$l_1\vee ...\vee l_k和m_1\vee ...\vee m_n$,則這兩個子句為真。如果$l_i$為真，則由于是互補文字知$m_j$為假，則$m_1\vee ...\vee m_{j?1}\vee m_{j+1}\vee ...\vee m_n$必為真。如果$l_i$為假，則$j_1\vee ...\vee j_{i?1}\vee j_{i+1}\vee ...\vee j_k$必為真。因此，結論必定成立。

歸結選取兩個子句并生成一個新的子句，該子句包含除了兩個互補文字以外的原始子句中的所有文字。
歸結規則中每個文字只能出現一次。例如，（A∨B）和（A∨￢B）歸結得(A∨A)，簡化為A。

合取范式CNF

CNF：子句的合取式

析取范式DNF

歸結算法-如何證明蘊含(歸結演繹推理)╞

歸結演繹推理是一種基于邏輯“反證法”的機械化定理證明方法。其基本思想是把永真性的證明轉化為不可滿足性的證明。即要證明 P→QP永真，只要能夠證明P∧﹁Q 為不可滿足即可。
對于知識庫而言，為了證明KB ╞ α，需要證明{KB,?α}(或KB∧?α)是不可滿足的。

步驟：
（1）將(KB∧?α)轉化成CNF。
（2）對結果子句運用歸結規則，對含有互補文字的子句進行歸結產生新的子句，如果該新的子句沒有出現過就將其加入子句集中。
如果含有多個互補文字，需要一次性進行歸結(￢B、A∨B,C∨B)歸結得(A,C)而不是(A,C∨B)
（3）持續上面兩步，直到：

• 沒有可以添加的新語句，此時，KB不蘊含α
• 兩個子句歸結出空子句，則KB ╞ α

horn子句和限定子句

限定子句：受限形式的一種子句,它是指恰好只含一個正文字的析取式。例如：(A∨B∨￢C)不是限定子句，而(A∨￢B∨￢C)是限定子句。
每個限定子句可寫為蘊含式

Horn子句：至多只有一個正文字的析取式。如：(A∨￢B∨￢C)和(￢A∨￢B∨￢C)都是horn子句。
Horn子句在歸結下是封閉的:如果對兩個Horn子句進行歸結,結果依然是Horn子句。

目標子句：沒有正文字的析取式。如：(￢A∨￢B∨￢C)就是目標子句。
horn子句=限定子句+目標子句

命題邏輯的前向鏈接和反向鏈接

前向鏈接

前向鏈接：從知識庫中的已知事實(正文字)開始。如果蘊涵的所有前提已知，那么把它的結論加到已知事實集。持續這一過程，直到詢問q被添加或者直到無法進行更進一步的推理。前向鏈接的運行時間是線性的。

前向鏈接是數據驅動推理的實例——即推理是從已知數據開始的。對于Horn KB，前向鏈接是

• 可靠的：每個推理本質上是分離規則的一個應用
• 完備的：每個被蘊涵的原子語句都將得以生成

反向鏈接

反向鏈接：反向鏈接算法正如它的名字，從查詢開始進行推理。如果查詢q已知為真,那么無需進行任何操作。否則,尋找知識庫中那些以q為結論的蘊含式。如果其中某個蘊含式的所有前提都能證明為真(通過反向鏈接),則q為真。 與前向鏈接一樣,有效實現的時間復雜度是線性的。
反向鏈接是一種目標制導的推理形式。

總結

本章討論丁基于知識的 Agent,指明了如何定義一種邏輯,使得 Agent 可以使用這種邏輯對世界進行推理。
本章主要知識點如下:

• 智能Agent需要關于世界的知識以制訂好的決策。
• Agent 的知識以知識表示語言的語句形式存儲在Agent 的知識庫中。
• 基于知識的Agent 由知識庫和推理機制組成。它的工作方式是把描述世界的語句存儲到它的知識庫中,使用推理機制推導出新的語句,并根據這些語句來決策采取什么行動。
• 一種表示語言是通過語法和語義來定義的,其中語法指明語句的結構,而語義定義了每個語句在每個可能世界或模型中的真值。
• 語句之間的蘊涵關系對于理解推理至關緊要。如果b語句在所有a語句為真的世界中都為真,則a蘊涵b。等價定義包括語句a?b是有效的和語句a∧￢b是不可滿足的.
• 推理是從舊語句生成新語句的過程。 可靠的推理算法只生成被蘊涵的語句;完備的算法生成所有被蘊涵的語句。
• 命題邏輯是由命題詞和邏輯連接詞組成的簡單語言。它可以處理已知為真、已知為假或完全未知的命題。
• 給定一個固定的命題詞匯表,它的可能模型集是有限的,因此蘊涵可以通過枚舉模型來進行檢驗。用于命題邏輯的有效模型檢驗推理算法包括回溯和局部搜索方法,通常可以快速求解大規模的問題。
• 推理規則是用來尋找證明的可靠推理模式。消解規則是用在表示為合取范式的知識庫上的完備推理算法。前向鏈接和反向鏈接都是用在Horn子句表示的知識庫上的自然的推理算法。
• 局部搜索算法如WALKSAT可以用于問題求解。 這樣的算法是可靠的但是不完備。
• 邏輯狀態評估涉及的是維護與觀察歷史一致的描述可能狀態集的邏輯語句。每一更新步驟要求使用環境的轉移模型,轉移模型可以從后繼狀態公理構建。
• 邏輯 Agent 的決策可以通過 SAT 求解進行:找出模型規范到達目標的未來可能的行動序列。這種方法只適用于完全可觀察或無傳感信息的環境。
• 命題邏輯無法擴展到無限的環境,原因是它缺之足夠的表達能力來準確地處理時間、空間以及對象間關系的模式。

資源分享

實驗代碼下載：
https://github.com/yyl424525/AI_Homework
人工智能-一種現代方法中文第三版pdf、課件、作業及解答、課后習題答案、實驗代碼和報告、歷年考博題下載：https://download.csdn.net/download/yyl424525/11310392

總結

以上是生活随笔為你收集整理的人工智能 一种现代方法 第7章 逻辑Agent（命题逻辑）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。