本筆記參照西安電子科技大學、浙江工業大學、哈爾濱工業大學慕課以及北京交通大學課程PPT記錄，

如有錯誤，敬請指正！

第三章

一階謂詞邏輯表示法

謂詞

謂詞包括一元謂詞、二元謂詞、多元謂詞

• 個體是常量：一個或者一組指定的個體；
• 個體也可以是變數：沒有制定的一個或者一組個體；
  • 變數具體賦值后，才能確定真偽
• 個體可以是函式：一個個體到另一個個體的映射；
• 個體可以是謂詞，

謂詞公式：

單個謂詞是謂詞公式，稱為原子謂詞公式，

謂詞公式的性質：

• 永真性

• 可滿足性

• 等價性
• 永真蘊含

連接詞

蘊含關系：P→Q，僅當Q為F時，運算式才為假

量詞

• 全稱量詞
• 存在量詞

全稱量詞和存在量詞在同一命題中的次序會影響命題意思，

量詞轄域：

量詞轄域：位于量詞后面的單個謂詞或者用括弧括起來的謂詞公式，

約束變元與自由變元：轄域內與量詞中間名的變元稱為約束變元，不同名的變元稱為自由變元，

一階謂詞邏輯知識表示法

步驟：

• 定義謂詞及個體
• 變元賦值
• 用連接詞連接各個謂詞，形成謂詞公式

特點：

• 優點
  • 自然性
  • 精確性
  • 嚴密性
  • 容易實作
• 缺點
  • 不能表示不確定的知識
  • 組合爆炸
  • 效率低

產生式規則表示法

確定性規則：

只要前提滿足，結論一定正確

基本形式：IF P THEN Q、 或 P→Q、

不確定性規則：

基本形式：IF P THEN Q(置信度) 或 P→Q(置信度)

確定性事實性知識：

表示：(物件，屬性，值) 或 (關系，物件1，物件2)

不確定性事實性知識：

表示：(物件，屬性，值，置信度) 或 (關系，物件1，物件2，置信度)

產生式與蘊含式的區別：

• 除邏輯蘊含外，產生式還包括各種操作、規則、變換、算子、函式等，
• 蘊含式只能表示精確知識，產生式還可以表示不精確的知識，

巴科斯范式BNF(backus normal form)：

產生式系統

• 規則庫：相應領域內知識的產生式集合
• 綜合資料庫：存放問題求解程序中各種當前資訊的資料結構
• 控制系統：由一組程式組成，負責整個產生式系統的運行，實作對問題的求解

產生式系統就是不斷對特征進行匹配，并將匹配結果加入特征中，知道匹配到相應結果，

語意網路表示法

兩個弧連接的結點之間的關系默認為合取關系，用封閉的虛線作為析取界限，表示析取關系，并注以DIS，

如果合取關系嵌套在析取關系內部，也應用虛線圍起來，并標以CONJ，

“非”的關系用NEG表示，

蘊涵關系用一對封閉虛線表示，前項標以ANTE，后項標以CONSE，

具有繼承性的關系：

• ISA：表示層次關系
• AKO：表示集合關系
• ISPART：表示組成關系

分塊語意網路

結點：物理物體、概念、性質和關系，

弧：該關系所涉及引數，

lFORM-OF、COMP-OF均為LISP函式，在語意網路中表示為：

分類學網路

推理網路

點：斷言，取值為真、假，或附以確信度，

弧：規則，

結點格式：

規則格式：

推理方式——混合主動式：

程序：不斷修改各結點的可信度（后驗概率），直至頂層結點的可信度超過某一閾值為止，

• 正向推理：每當用戶輸入一個證據E及其可信度，系統就沿推理網路修改各結點的可信度，
• 主動式推理：在推理的任何時刻，用戶都可以為系統提供資訊（任何層次結點的資訊），
• 反向推理：正向推理結束后，如果已經確定了存在某種礦藏，則輸出結果；否則進行反向推理，為斷定某種礦藏的成礦尋找有關資料，

框架表示法

一種描述所論物件屬性的資料結構，

框架結構

例：教師框架

框架表示法的特點

• 結構性：便于表達結構性知識，能夠將知識的內部結構關系及知識間的聯系表示出來
• 繼承性：框架網路中，下層框架可以繼承上層框架的槽值，也可以進行補充、修改

第四章

問題規模很大或很復雜，以至于不可能考慮其目標的全部可能性時，以解決尋優問題為目標的優化演算法就轉變為區域搜索，

區域搜索演算法的終止條件一般有兩種選擇：

• 時間限制
• 搜索獲得的當前目標不能再改善

狀態空間表示法

狀態空間法：基于解答空間的問題表示和求解方法，它是以狀態和算符為基礎來表示和求解問題的，

主要包括：狀態、算符、狀態空間

狀態

狀態：表示問題求解程序中每一步問題狀態的資料結構，一般用一組資料表示：
S k = { S k 0 , S K 1 , . . . } S_k=\{Sk_0, SK_1, ...\} Sk?={Sk0?,SK1?,...}
? 式中每個元素為集合的分量，稱為狀態變數，

迷宮問題的狀態表示：

八數碼問題的狀態表示：

算符

算符：當對一個問題狀態使用某個可用操作時，它將引起該狀態中某些分量值的變化，從而使問題從一個具體狀態變為另一個具體狀態，

迷宮問題的算符：

八數碼難題的算符：

問題的狀態空間

問題的狀態空間：用來描述一個問題的全部狀態以及這些狀態之間的互相關系，

狀態空間常用一個三元組表示： ( S , F , G ) (S, F, G) (S,F,G)，

• S S S：為問題的所有初始狀態的集合；
• F F F：算符的集合；
• G G G：為目標狀態的集合，

八數碼的狀態空間：

狀態圖示法：狀態空間的圖示形式，其中節點表示狀態，邊表示算符，求解程序就是求相應路徑的問題（搜索），

二階梵塔難題

狀態：

算符：

狀態空間圖：

爬山法

區域最大值可能出現在區域最大值、“平坦”區域最大值、山肩的平坦處，

爬山法是一種貪心演算法，即從當前狀態出發，向相鄰狀態進行試探，若發現某個相鄰轉臺比當前狀態更好，則轉入相鄰狀態并放棄當前狀態，

八皇后問題

八皇后問題若不做任何約束，則可能的排列數很大，若限制每個皇后只能再同一行或同一列移動，則排列數大大減少，

八皇后問題中，需要采用一個代價函式h，其代表再八皇后問題中，兩兩沖突對的個數h值不能增加，只能慢慢減少，以此作為標準判斷是否從當前狀態移動到相鄰狀態，

圖搜索問題

圖的概念

• OPEN表：記錄帶拓展節點
• CLOSED表：記錄已拓展的節點
• 必須記住從目標回傳的路徑

圖搜索流程：

搜索圖：演算法結束后，所生成的“足跡”為一個圖 G G G，

搜索樹：由于每個節點都有一個指標指向父節點，這些指標指向的節點構成 G G G的一個支撐樹，

圖搜索分類

對OPEN表中節點排序方式產生了不同的搜索策略，不同的搜索搜索策略效率不同，

• 無資訊搜索（盲目式搜索）
• 寬度優先搜索
• 深度優先搜索
• 等代價搜索
• 有資訊搜索（啟發式搜索）
• A演算法
• A*演算法

盲目式搜索

按預定的控制策略進行搜索，在搜索程序中獲得的中間資訊不用來改進控制策略，

寬度優先搜索（BFS）：

BFS的性質：

• 屬于圖搜索
• 新拓展的節點排在OPEN表末端
• 當問題有解時，一定能找到解
• 方法與問題無關，具有通用性
• 效率較低

深度優先搜索（DFS）：

與BFS的不同在于，DFS將待拓展的節點放在OPEN表的開頭，

節點深度：

• 起始節點深度為0，
• 任何其他節點的深度為其父輩節點深度加1，

DFS的特點：

• 搜索一般不能找到最優解，若解在該分支上，則能很快找到解；若解不在該分支上，則不能；若該分支為無窮深度，則永遠不可能找到解，可以定義深度界限 d m d_m dm?來解決這個問題，
• 深度界限 d m d_m dm? 不合理時，也有可能找不到解，如 d m d_m dm?定義過小的情況，將 d m d_m dm?更改為可變深度限制可以在一定程度上解決這個問題，

等代價搜索：

核心思想：利用邊的代價，對OPEN表進行排序，若每條邊的代價為1，則等代價搜索即為BFS，

小結：

• BFS按“層”進行搜索，先進入OPEN表的節點先被考察，
• DFS沿縱深方向進行搜索，后進入OPEN表的節點先被考察，
• 等代價搜索首先擴展最小代價節點，

啟發式搜索

盲目式搜索的缺點：效率低，耗費過多的計算空間與時間，

盲目式搜索只知道 S 0 → n S_0→n S0?→n，但是啟發式搜索可以通過 S 0 → n S_0→n S0?→n及 n → S g n→S_g n→Sg?兩者來判斷目標，向最有希望的方向搜索，

八數碼難題：

S 0 S_0 S0?與 S A S_A SA?、 S B S_B SB?、 S C S_C SC?相比， S B S_B SB?與 S g S_g Sg?最相似，變為 S g S_g Sg?移動次數最少，故先拓展 B B B節點，

啟發式資訊：與具體問題求解程序有關的，并可知道搜索程序朝著最有希望的方向前進的控制資訊，

啟發式需要猜測：

• 從節點 n n n開始，找到最優解的可能性？
• 從起始節點開始，經過節點 n n n，到達目標節點的最佳路徑的費用？

要解決這些問題，需要定義一個評價函式 f ( n ) f(n) f(n)，用于估算節點“希望”程度，
f ( n ) = g ( n ) + h ( n ) f(n)=g(n)+h(n) f(n)=g(n)+h(n)
g ( n ) g(n) g(n)：從起始狀態到當前狀態 n n n的代價，

h ( n ) h(n) h(n)：從當前狀態到目標狀態的估計代價（啟發函式），

A演算法：

• 區域擇優演算法

  1. 把初始節點 S 0 S_0 S0?放入OPEN表中，表示 f ( S 0 ) f(S_0) f(S0?)；
  2. 如果OPEN表為空，則問題無解，退出；
  3. 把OPEN表的第一個節點（記為節點 n n n），放入CLOSED表中；
  4. 考察節點 n n n是否為目標節點，若是，則得解，退出；
  5. 若節點 n n n不可拓展，則轉第2步；
  6. 拓展節點 n n n，用評價函式 f ( x ) f(x) f(x)計算每個子節點，并按評價值從小到大的順序依次放入OPEN表的首部，并為每一個子節點都配置指向父節點的指標，轉第2步，

• 有序搜索演算法：選擇OPEN表中具有最小 f f f值的節點作為下一個要拓展的節點，

八數碼難題難題的有序搜索搜索圖：

有序搜索有一點兒類似DFS，

A*演算法：

g ? ( n ) g^*(n) g?(n)：從初始節點 S 0 S_0 S0?到任意節點 n n n的一條最佳路徑的代價，

h ? ( n ) h^*(n) h?(n)：從節點 n n n到目標節點的一條最佳路徑的代價，

A*演算法有評價函式：
f ( n ) = g ( n ) + h ( n ) f(n)=g(n)+h(n) f(n)=g(n)+h(n)

• g ( n ) g(n) g(n)是對 g ? ( n ) g^*(n) g?(n)的估計， g ( n ) > = g ? ( n ) g(n)>=g^*(n) g(n)>=g?(n)
• h ( n ) h(n) h(n)是對 h ? ( n ) h^*(n) h?(n)的估計，且滿足對所有的 n n n， h ( n ) ? h ? ( n ) h(n) \leqslant h^*(n) h(n)?h?(n)

八數碼難題：

根據 h ( x ) h(x) h(x)函式值，有：
0 ? h 1 ( n ) ? h 2 ( n ) ? h ? ( n ) 0\leqslant h_1(n)\leqslant h_2(n)\leqslant h^*(n) 0?h1?(n)?h2?(n)?h?(n)
由于 h 2 ( n ) h_2(n) h2?(n)相較于 h 1 ( n ) h_1(n) h1?(n)更接近于 h ? ( n ) h^*(n) h?(n)，故方案二與方案一相比，方案二更好，

A*演算法的搜索效率在很大程度上取決于 h ( n ) h(n) h(n)，在滿足 h ( n ) < = h ? ( n ) h(n)<= h^*(n) h(n)<=h?(n)的前提下， h ( n ) h(n) h(n)的值越大越好，

衡量一個搜索策略性能的準則：

• 問題有解是否能找到
• 搜索空間小
• 解最佳

與或圖

• 與圖：要解決A問題，需要解決B、C、D三個問題，從而求解，
• 或圖：要解決A問題，需要解決B或C問題，從而求解，

• 弧線：父輩節點指向子節點的連線，表示運算子；
• 或節點：只要解決某個問題就可以解決其父輩問題的節點集合；
• 與節點：只有解決所有子問題，才能解決其父輩問題的節點集合，

當所有節點都是或節點時，這是變為狀態空間圖，

除起始節點外，所有節點只有一個父節點，此時為與或樹，

與或圖的結構：

• 初始節點對應于原始問題描述；
• 對應本院問題的節點叫做葉節點；
• 中間問題對應非終葉節點，

與或圖有解的條件是：起使節點是可解的，

與或圖BFS搜索：

1. 把原始問題作為初始節點 S 0 S_0 S0?，并把它作為當前節點；
2. 應用分解或等價變換對當前節點進行拓展；
3. 為每個節點設定指向父節點的指標；
4. 選擇適合的節點作為當前節點，反復執行第2步和第3步，在此期間要多次呼叫可解標志程序和不可解標志程序，直到初始節點被標為可解節點或不可解節點為止，

與或圖DFS搜索：

4. 要判斷從OPEN表取出來的節點深度，如果等于深度界限，認定它是不可解節點，

5. 拓展節點 n n n把其子節點放入OPEN表的前端，即新產生的節點先拓展

在對與或圖進行搜索時，需要關注節點是與節點還是或節點，

博弈與博弈樹

博弈樹

一種特殊的與或樹，其節點為博弈的格局（棋局），相當于狀態空間中的狀態，反映了博弈的資訊，并且與節點、或節點隔層交替出現，

與或節點交替出現的原因：我方走步時，我方只需選擇一種好步驟執行，是或關系；而對方走步時，我方則需要考慮所有好步驟，是與關系，

在博弈樹中，所有能使自己一方獲勝的終局是本原問題，相應節點為可解節點，所有能使對方獲勝的終局都是不可解節點，

極大極小搜索（Max-Min搜索）

基本思想：

• 目的是為博弈雙方中的一方尋找一個最優行動方案；
• 要尋找最優方案，就要通過計算所有可能的方案進行比較；
• 方案的比較是根據問題的特征來定義一個估價函式，用來估算當前博弈樹端節點的得分；
• 當計算出端節點的估值后，再推出父節點的得分：
  • 對或節點，選擇子節點中的最大得分為父節點得分
  • 對與節點，選擇子節點中的最小得分為父節點得分
• 若一個行動方案能獲得較大得分，則它就是當前最好的行動方案，

搜索步驟：

1. 生成k-步博弈樹

2. 評估棋局（博弈狀態）

打分評估方法是從葉節點自下而上進行打分，

3. 回溯評估

4. 遞回回圈

α \alpha α- β \beta β剪枝搜索

在生成博弈樹的程序中計算評估各節點的倒推值，

搜索策略：k-步博弈；深度優先；每次擴展一個節點；一邊擴展一邊評估，

基本概念：

• 對或節點，選擇子節點中的最大得分為父節點得分的下界，稱為 α \alpha α值
• 對與節點，選擇子節點中的最小得分為父節點得分的上界，稱為 β \beta β值

由于在最左側分支中，已經求得 α \alpha α=-1，又求得第二分支的第一次分支中得分為-1，那么第二分支的 β \beta β=-1，即使第二分支中還有次分支的值比-1大或小， α \alpha α的也不會受到影響，故X處進行剪枝，

以上程序是根據Min節點上界與Max節點下界進行判斷，

剪枝規則：

• 任何與節點 x x x的 β \beta β值如果不能升高其父節點的 α \alpha α值，則對節點 x x x以下的分支可停止搜索，并使 x x x的倒推值為 β \beta β
• 任何或節點 x x x的 α \alpha α值如果不能降低其父節點的 β \beta β值，則對節點 x x x以下的分支可停止搜索，并使 x x x的倒推值為 α \alpha α

第五章

合一及合一演算法

文字：正、負原子公式，前面有否定連接詞的謂詞公式為負原子公式，

子句：僅使用析取連接詞將原子公式連接后的公式，

空子句：不包含任何文字的子句，

• 空子句是永假的，不可滿足的，

Horn子句：至多有一個正文字的子句，其中正文字稱為Horn子句頭，其他稱為子句體，

置換：設 x 1 , … , x n x_1,…,x_n x1?,…,xn?是 n n n個變數，且各不相同， t 1 , … , t n t_1,…,t_n t1?,…,tn?是 n n n個項（常量、變數、函式）， t i ≠ x i t_i\ne x_i ti??=xi?，則用 t i t_i ti?替換變數 x i x_i xi?操作形成的有限序列 x 1 / t 1 , … , x n / t n {x_1/t_1, …,x_n/t_n} x1?/t1?,…,xn?/tn?稱為一個置換（運算），

置換乘積（置換合成）：設 θ \theta θ和 λ \lambda λ是2兩個置換，則先 θ \theta θ后 λ \lambda λ作用于公式或項，稱為置換乘積，用 θ o λ \theta^o\lambda θoλ表示，

合一：通過相關置換使不同的一階謂詞公式稱為相同的程序，

合一置換：設有一組謂詞公式 { F 1 , … , F k } \{F_1,…,F_k\} {F1?,…,Fk?}和置換 θ \theta θ，使得 F 1 θ = F 2 θ = … = F k θ F_1\theta=F_2\theta=…=F_k\theta F1?θ=F2?θ=…=Fk?θ，則 θ \theta θ稱為合一置換， F 1 , … , F k F_1,…,F_k F1?,…,Fk?稱為可合一的，

最一般合一置換（mgu）：如果 σ \sigma σ和 θ \theta θ都是公式組 { F 1 , … , F k } \{F_1,…,F_k\} {F1?,…,Fk?}的合一置換，且有置換 λ \lambda λ存在，使得 θ = σ o λ \theta=\sigma^o\lambda θ=σoλ，則稱 σ \sigma σ為公式組 { F 1 , … , F k } \{F_1,…,F_k\} {F1?,…,Fk?}的最一般合一置換，

歸結演繹推理

定理： Q Q Q為 P 1 , P 2 , … , P n P_1,P_2,…,P_n P1?,P2?,…,Pn?的邏輯結論，當且僅當 ( P 1 ∧ P 2 ∧ … ∧ P n ) ∧ ? Q (P_1\wedge P_2\wedge …\wedge P_n)\wedge \lnot Q (P1?∧P2?∧…∧Pn?)∧?Q是不可滿足的，

謂詞公式生成子句集步驟：

魯濱遜歸結原理

子句集中子句之間是合取關系，只要有一個子句不可滿足，則子句集就不可滿足，

基本思想：檢查子句集 S S S中是否包含空子句，若包含，則 S S S不可滿足，若不包含，在 S S S中選擇合適的子句進行歸結，一旦歸結出空子句，就說明 S S S是不可滿足的，

定義3.1（歸結）：設 C 1 C_1 C1?與 C 2 C_2 C2?是子句集中的任意兩個子句，如果 C 1 C_1 C1?中的文字 L 1 L_1 L1?與 C 2 C_2 C2?中的文字 L 2 L_2 L2?互補，那么從 C 1 C_1 C1?和 C 2 C_2 C2?中分別消去 L 1 L_1 L1?和 L 2 L_2 L2?，并將兩個子句余下的的部分析取，構成新的子句 C 12 C_{12} C12?，

定理3.2：歸結式 C 12 C_{12} C12?是其親本子句 C 1 C_1 C1?與 C 2 C_2 C2?的邏輯結論，如果 C 1 C_1 C1?與 C 2 C_2 C2?為真，則 C 12 C_{12} C12?為真，

推論1：設 C 1 C_1 C1?與 C 2 C_2 C2?是子句集 S S S中的兩個子句， C 12 C_{12} C12?是它們的歸結式，若用 C 12 C_{12} C12?代替 C 1 C_1 C1?與 C 2 C_2 C2?后得到新子句集 S 1 S_1 S1?，則由 S 1 S_1 S1?不滿足性可推出原子句集 S S S的不可滿足行，即：
S 1 的 不 可 滿 足 性 ? S 的 不 可 滿 足 性 S_1的不可滿足性\Rightarrow S的不可滿足性 S1?的不可滿足性?S的不可滿足性
推論2：設 C 1 C_1 C1?與 C 2 C_2 C2?是子句集 S S S中的兩個子句， C 12 C_{12} C12?是它們的歸結式，若 C 12 C_{12} C12?新子句集加入原子句集 S S S得到新子句集 S 2 S_2 S2?，則 S 1 S_1 S1?與 S 2 S_2 S2?在不滿足性的意義上是等價的，即：
S 2 的 不 可 滿 足 性 ? S 的 不 可 滿 足 性 S_2的不可滿足性\Longleftrightarrow S的不可滿足性 S2?的不可滿足性?S的不可滿足性
謂詞邏輯中的歸結原理（上一小節有講）：

定義3.2：設 C 1 C_1 C1?與 C 2 C_2 C2?是兩個沒有相同變元的子句， L 1 L_1 L1?和 L 2 L_2 L2?分別是 C 1 C_1 C1?和 C 2 C_2 C2?中的文字，若 σ \sigma σ是 L 1 L_1 L1?和 ? L 2 \lnot L_2 ?L2?的最一般合一，則稱 C 12 = ( C 1 σ ? { L 1 σ } ∨ ( C 2 σ ? { L 2 σ } ) ) C_{12}=(C_1\sigma-\{L_1\sigma\} \vee (C_2\sigma-\{L_2\sigma\})) C12?=(C1?σ?{L1?σ}∨(C2?σ?{L2?σ}))為 C 1 C_1 C1?和 C 2 C_2 C2?的二元歸結式，

歸結反演

證明步驟：

1. 將已知前提表示為謂詞公式 F F F，
2. 將待證明的結論表示為謂詞公式 Q Q Q，并否定得到 ? Q \lnot Q ?Q，
3. 把謂詞公式集 { F , ? Q } \{F,\lnot Q\} {F,?Q}化為子句集 S S S，
4. 應用歸結原理把子句集 S S S中的子句進行歸結，并把每次歸結得到的歸結式并入到 S S S中，如此反復，若出現空子句，則停止歸結， Q Q Q為真得證；未出現空子句，則繼續，

正向和反向推理方法

正向演繹系統

一個與或圖表示的子句集就對應于在圖的文字結點上結束的解圖集，

將相應規則轉換為與或圖：

正向演繹系統中，所推出的目標即葉子節點之間的關系為析取，與歸結反演系統對偶，

逆向演繹系統

與或圖的描述：