以下是up主人工智能實驗課的實驗報告，寫完順手發(fā)到b站上留個檔（當然如果能幫助到有需要的人更好，不過我估計也沒有人會看的啦）有問題可以在評論區(qū)留言，雖然我也很有可能不會。

一、?????? 實驗題目

一階邏輯歸結原理實驗

二、?????? 實驗內容

1.?算法原理

（1）子句歸結

???????? 子句歸結的理論原理是，假設有兩個子句（其中C_1,C_2是子句，P是文字）：

? ? ? ? ? ?

從中消去互補對（即和?? ），所得的新子句

稱作子句的歸結子句，原子稱為被歸結的原子，這個過程稱為歸結。只有存在互補對的子句才存在歸結式。對兩子句做歸結的過程即為求歸結式。

???????? 在本次實驗中，輸入的要處理的子式為已經經過轉換之后的便于計算機處理的Clausal form，即每一個子句對應一個元組，元組每一個元素是一個原子公式/原子公式的否定，元素之間的關系是析取關系，表示只要一個原子成立，該子句成立；元組的集合組成子句集S，子句集中每個句子之間是合取關系，表示每一個子句都應該被滿足。

以上面三條式子為例，

對應的Clausal Form為

但是Clausal Form只是易于計算機進行處理的形式，并不是真正要用的形式，在程序中如果要對子句執(zhí)行歸結算法，（以Python為例）還需要將其轉換成列表的形式。每個原子公式轉換成一個以字符串為元素的列表，列表組成為[“謂詞”, “項1”, “項2”, ……, “項n”]，以上面的三個式子為例，轉換之后真正進行處理的形式為：

???????? 如果是對不含變量的子句進行單步歸結，主要過程為先檢測兩個要進行的列表是否為謂詞相反、項數目相等的原子公式，然后再對除謂詞外的所有項（即列表中除了第0個元素外的所有元素）進行對比，如果一樣，則進行單步歸結。

???????? 單步歸結的算法的具體思想是：先標記兩個子句中的互補對的位置，然后對兩個子句進行深復制以后講互補對刪除，最后再將刪除互補對之后的兩條子句進行合并生成新的子句。注意在這個過程中可能出現兩條子句中存在相同的原子公式，在加入子句集的之前要對生成的新子句去重。（即將重復出現的原子公式刪除）去重在本程序中的實現方法是先轉換成集合形式，再轉變回列表。

?

（2）子句合一

???????? 當兩個子句中存在變量時，如果可以通過變量替換使得兩個子句能被歸結（具有相同的原子），則將變量替換成常量使得兩個子句歸結的過程叫作合一。合一也被定義為使得兩個原子公式等價的一組變量替換/賦值。

???????? 例如，如果兩個子句為

則可以將第二個子句中的變量y替換為A，此時兩個子句就有相反謂詞的原子公式，這時再進行歸結的操作，生成新的子句。

兩個子句合一后生成的新子句為

在程序當中，合一的操作同樣以Clausal From的形式進行處理的。程序中進行合一操作的基本思想是：

①首先判斷要進行合一的兩個子句中是否存在變量并且長度相同，然后進入函數judge中，judge輸入兩個要進行判段的子句并且返回一個列表或者false。

②在judge中，從項（即從下標為1）開始同步遍歷兩個子句，如果兩個子句中的項是常量則相等，并且繼續(xù)遍歷下一個項；如果一個子句中為變量，而第二個子句中為常量，則將這兩個項記錄到要返回的列表中。并且繼續(xù)下一個循環(huán)；如果遇到其他情況則直接返回false。最后當所有項都遍歷完并且沒有返回false的情況下返回記錄了替換項與被替換項的列表。

③judge結束后，判斷judge的返回值，如果返回值為false則不能進行合一。如果返回值為列表則依據列表中記錄的項對兩個子句進行合一操作，主要的操作是將互補對消去，并且將含變量子句中的其他相同變量改為被替換的常量，最后再進行歸結操作。生成的新子句加入到子句集合中。

????????

（3）遍歷子句集合

????因為程序的輸入不是單獨的兩個子句，而是多個子句，要保證所有的子句都能被判斷一遍是否能進行歸結和合一。所以設置一個四重循環(huán)，第一重循環(huán)遍歷第i個子句；第二個循環(huán)遍歷第j個子句；第三重循環(huán)遍歷第i個子句的第ki個原子公式；第四重循環(huán)遍歷第j個子句出現的第kj個原子公式。這樣就能將每個子句的每個原子公式判斷一遍。循環(huán)體內的內容就是前面的（1）和（2），即進行判斷是否能歸結、合一并加入新子句的操作。當生成空的子句時，就表示輸入的子句集和可以被歸結，此時直接退出循環(huán)。

????????

（4）回溯有用子句并輸出

????成功生成空子句之后，就代表著輸入的子句集合可以被歸結，但是需要注意的是，此時子句集合中所生成的子句并不是所有的子句都是用的上的，因為在上一階段即遍歷集合生成空句的過程中，所做的操作是把所有能進行歸結合一的子句進行歸結，并加入到子句集合中。這時很多生成的子句就是無用子句（即在生成空子句的過程中用不上這些子句）。

????而為了能找到正確的有用子句，此時就要從生成的空子句出發(fā)，回溯找到生成這個空子句所要用到的子句，并記錄且輸出出來。為了實現這一操作，還需要新增兩個列表，分別是記錄父歸結子句的parent列表和記錄變量、常量的assigment列表，這兩個列表和子句集合S同步更新。

????以最終生成的空子句為結點，可以得到類似下圖的二叉樹：

????要回溯有用子句，就是對上面這個二叉樹進行層序遍歷，即我們可以將回溯子句的過程視為層序遍歷二叉樹的過程。

????所以只需要以parent為索引，以隊列為數據結構，對上圖的二叉樹進行層序遍歷：創(chuàng)建一個新列表用來存儲有用子句，首先將“根節(jié)點”空子句入隊，將新入隊的子句加入列表，同時將對應編號的parent和Assignment列表中的元素記錄；然后查詢它的父子句，再將其父子句入隊、記錄，當查詢到原始輸入的子句時（子句編號小于n）則不入隊。往復循環(huán)，直到隊列為空。

????需要注意的是，此時記錄的子式編號是原編號，即在子句集合S中的編號（包含了很多無用子句的編號）。這時就需要對已經記錄的有用子句進行重新標號，以保證輸出時能對應上是哪兩個子句。比如最終生成的空子句原標號是S[42]，重新標號后為S[10]。

????最后再對已經記錄的子句轉換為Clausal Form再逆序輸出即可。

2.?偽代碼

（1）歸結生成子句階段

第一層循環(huán)以i為下標遍歷所有子式：

????????第二層循環(huán)以j為下標遍歷所有子式：

????????????第三層循環(huán)遍歷第i個子式的所有原子公式：

???????? ?????? ????第四層循環(huán)遍歷第j個子式的所有原子公式：

?????????????????? ?????????????????? if 存在原子及其的否定（如On和它的否定?On）：

?????????????????? ?????? ??????????? ????if可以直接進行歸結：

????????????????????????????????????????????進行歸結操作;

????????????????????????????????????????????將互補對消去生成新子句加入到子句集合S中;

????????????????????????????????????????????記錄變量替換情況assignment及其parents (i, ki, j, kj);

????????????????????????????????????????????If 生成的新子句為空：

???????????????????????????????????????????????? 結束所有循環(huán);

???????????????????????????????????????Else 判斷是否可以進行合一：

????????????????????????????????????????????If 不可以進行合一：

????????????????????????????????????????????????Continue;

????????????????????????????????????????????Else 可以進行合一：

????????????????????????????????????????????????對要進行變量替換的那條子句中的變量替換為對應的常量;

????????????????????????????????????????????????消去互補對并將變量替換后的兩個子句進行歸結;

????????????????????????????????????????????????并將新生成的子句加入到子句集合S中;

????????????????????????????????????????????????記錄變量替換情況assignment及其parents (i, ki, j, kj);

????????????????????????????????????????????????If 新生成的子句為空：

????????????????????????????????????????????????????結束所有循環(huán)

??????????????????????????? 第四層循環(huán)結束

?????????????????? 第三層循環(huán)結束

???????? 第二層循環(huán)結束

第一層循環(huán)結束

?

（2）回溯尋找有用子句的階段

創(chuàng)建隊列q；

將空子句的parent入隊；

記錄空子句以及其變量替換情況assignment及其parents (i, ki, j, kj)；

While 隊列不為空:

???????? 記錄隊首子句;

出隊;

???????? If 當前子句的第一個父子句的標號大于n:

?????????????????? 記錄子句以及其變量替換情況assignment及其parents (i, ki, j, kj)；

?????????????????? 將第一個父子句的parent入隊；

???????? If 第二個父子句的標號大于n:

?????????????????? 記錄子句以及其變量替換情況assignment及其parents (i, ki, j, kj)；

?????????????????? 將第二個父子句的parent入隊；

End While

3.關鍵代碼展示

（1）讀入初始子句集合

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

（2）遍歷進行合一、歸結

生成新子句函數：

轉換函數：

去重函數：

用來判斷是否能進行合一并返回Assignment的judge函數：

（4）回溯尋找有用子句：

（5）重新標號：

（6）轉換為標準形式再輸出：

三、實驗結果及分析

1. 實驗結果展示示例

本程序采用的輸入輸出方式是在命令行窗口直接輸入，并在命令行窗口即時輸出。輸入格式是首先輸入原始子句的數目，然后再按行輸入子句。

①Aipine Club

②Graduate Student

2. 評測指標展示及分析

????本次實驗的程序主要的時間復雜度集中在遍歷子句進行歸結以及合一這一階段上，按照大O表示法的規(guī)則，整體程序的時間復雜度可以近似認為就是這一階段的時間復雜度。

????這一階段的主要函數為resolution，函數利用了四重循環(huán)對，每個子句的每個原子公式都進行了一遍對比。這個函數的時間復雜度主要取決于輸入的列表s的長度n以及每個子句的原子公式的數量m。

????①當每個子句的原子公式數量比較少（只有個位數）的情況下（即本次實驗給出的三個例子），程序的時間復雜度可以近似認為為 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ；

????②當子句的原子公式個數較多的情況下，考慮到進行合一操作時還要利用judge函數對兩個子句的原子公式進行遍歷，而這個操作的時間復雜度為，所以程序的時間復雜度為。（一般來說比這個要更大，因為程序內部還有利用循環(huán)替換變量等其他操作）

四、參考資料

[1]Lab2_歸結原理課件

[2]人工智能（第三版），清華大學出版社