為甚麼要搜尋真假指派?
知識庫可以包含「至少一個感應器正常」這類析取句。對定言霍恩(Horn)規則進行前向鏈推,並不能直接表達所有這類選擇。有限命題問題可以用窮舉真假指派來判定,但我們往往能一次排除多個指派:當一個尚未滿足的子句只剩下一個選項尚未為假,該選項便必須為真。單子句傳播正是利用這個觀察;沒有選項被迫成立時,仍須搜尋。
本節建立一個精確而簡單的 DPLL 算法,連結前面的搜尋和邏輯推理,補充歸結法單元的變量消去方法。下述程序判定有限命題公式,不判定任意一階公式。
子句、部分指派與傳播
定義 24.1.1
(文字、子句與 CNF)
固定有限個布林(Boole)原子。文字是原子 或其否定 ;子句是有限個文字的析取,合取範式(CNF)則是子句的合取。把子句視為文字的集合,重複文字不影響結果。空合取為真,空子句為假。CNF 的模型是令每個子句為真的完整指派;有模型的 CNF 稱為可滿足,否則稱為不可滿足。
定義 24.1.2
(部分指派與化簡)
部分指派只為部分原子指定真或假。按指派化簡公式時,刪除含有真文字的整個子句,再從其餘子句刪去假文字。若出現空子句,當前指派不可能延伸為模型;若沒有子句剩下,當前指派的任何完整延伸都滿足原公式。尚未指派的原子,其正負文字都未定真假。
定義 24.1.3
(單子句與單子句傳播)
只含一個文字的子句稱為單子句。任何滿足公式的延伸都必須使它的文字為真。單子句傳播就是作出這個指派並化簡,重複直至出現矛盾或沒有單子句。
被迫指派的先後次序不影響是否存在滿足它們的延伸,但程式首次報告的衝突可能不同。含 和 的子句永遠為真,可以預先刪去;保留它也不影響以下算法的正確性。
對已化簡的 CNF 和當前部分指派,遞歸執行:
- 反覆傳播單子句,直到沒有單子句或出現空子句。
- 若有空子句,回報此分支不可滿足;若沒有子句,回傳當前指派,未定原子任意補成完整指派。
- 否則選一個仍出現在公式中、尚未指派的原子,先遞歸試真。若找到模型就回傳;若失敗,還原父節點的指派,再試假。兩個分支都失敗才回報不可滿足。
各遞歸調用可以有自己的指派副本;若共用記錄,便須撤銷失敗分支中所有指派,包括傳播得到的指派。選哪個原子、先試真假哪一個,影響工作量而不影響最終的可滿足性答案。這裏沒有假設純文字規則、子句學習或特定選擇啟發式。
概念視角幾何
把子句看作立方體上的禁區
把 個全指派看作 維立方體的頂點。含 個文字的子句,恰在使其每個文字為假的指派上為假,這些指派構成維數為 的面。CNF 可滿足,當且僅當這些禁區不能覆蓋所有頂點。單子句禁掉半個立方體,空子句禁掉整個立方體,分支決策則把注意力限制在其中一半。在兩個原子上,後文四個子句的例子各禁掉一個頂點,所以沒有任何頂點剩下。
定理 24.1.4
(有限 DPLL 的可靠性與完備性)
對有限 CNF,上述程序會終止。若它回傳一個指派,該指派滿足原 CNF;它回報不可滿足,當且僅當原 CNF 沒有滿足指派。最壞情況下搜尋量可以隨原子數呈指數增長。
證明
(對未定原子數歸納)
在目前部分指派下,化簡恰好保留滿足公式的所有延伸:已為真的子句不再增加要求,而假文字不能滿足其子句。任何滿足延伸都使單子句中的文字為真,因此傳播也保留全部滿足延伸。空子句沒有滿足延伸;沒有剩餘子句時,任何完整延伸皆可滿足。
若兩種停止情況都沒有出現,選出的原子尚未指派。每個完整延伸必定在該原子取真或取假的其中一類,兩個分支涵蓋所有可能。每次分支至少指定一個原本未定的原子,故分支深度不超過原子數。對未定原子數作歸納,每個分支恰在存在模型時回傳模型;把兩個分支合起來便證明父節點也有此性質,得到可靠性和完備性。每次成功傳播都指定一個未定原子,因此傳播亦會終止。真假指派構成的二叉樹可能有指數多個節點;定理保證能判定,並不保證多項式時間。
證明透視
分支失敗為甚麼不等於全域矛盾?
證明依靠一個不變量:化簡與傳播恰好保留當前部分指派的全部滿足延伸。單子句的文字只是相對於已作出的指派而被迫為真,所以傳播是在當前分支條件下必須作出的推論。因此衝突只證明無模型能延伸該分支的選擇,不能單憑它斷言原公式無模型。二分是窮盡的,因為每個完整延伸都給所選原子一個值;須排除所有相關決策的兩種真假情況,才可在根節點宣告不可滿足。有限性最後才用到:每個分支都指定一個原本未定的原子,所以搜尋會終止。
以反證判定蘊涵
定義 24.1.5
(蘊涵)
若 的每個模型都使 為真,便稱公式 蘊涵公式 。
命題 24.1.6
(蘊涵即不可滿足)
對同一組原子上的公式 與 , 蘊涵 ,當且僅當 沒有模型。
證明
(展開定義)
的模型,恰好就是使 為假的 的模型。所以 沒有模型,當且僅當沒有 的模型使 為假,也就是 的每個模型都使 為真。
因此上述搜尋也能判定蘊涵:對 的 CNF 形式執行搜尋,把「不可滿足」讀作「蘊涵」。
算例追蹤
例題 24.1.7
(蘊涵鏈與一個模型)
設
起初沒有單子句。先試 。第一個子句迫使 ;接著 迫使 ;最後 迫使 。子句 因 為假而早已為真。所有子句均消失,故 是模型。若先試 ,也可以得到模型。找到一個模型足以證明可滿足,但不等於列出所有模型。
例題 24.1.8
(以反證檢驗蘊涵)
同一個 蘊涵 。加入單子句 :傳播先得 ,再由 得 。接著兩個子句分別迫使 和 ,令 成為空子句。因此 沒有模型,按定義即每個 的模型都滿足 。對任意命題查詢 ,一般方法是檢驗 是否可滿足;轉成 CNF 時須保留可滿足性。若原合取式可滿足,它的模型便是蘊涵的反例。若編碼引入輔助變量,僅知兩個公式可滿足性相同,並不能保證編碼所得模型可直接給出反例:應使用其模型投影後必定滿足原合取式的轉換,或另行重建並驗證反模型。
例題 24.1.9
(不需任何決策的反證,與空公式)
設 。子句 是單子句,故 ,第二個子句變成單子句 。指派 後,子句 成為空子句。衝突在根節點、未作任何決策前便出現,所有延伸都被排除: 不可滿足,且不需要分支。另一個極端是空 CNF:它沒有子句,所以第二條停止規則立即適用,任何完整指派都是模型。這兩個邊界情況說明,第 2 步的兩條停止規則都可以在沒有任何決策的情況下到達。
反例模式
沒有撤銷的分支指派會改變答案
設 。試 時,第一個子句成為單子句 ,傳播令 ,隨後第二個子句 變成空子句:此分支失敗。還原父節點後, 使第三個子句成為單子句 ,其餘兩個子句為真,於是 , 是模型。若錯誤保留失敗分支的 ,第二分支中第三個子句 便為假, 被誤報為不可滿足。回溯不但要撤銷決策,還須撤銷由決策傳播出的指派。
答案代表甚麼?
回傳的模型是可直接檢查的證據:把各值代入原來的每個子句。不可滿足意味具證明性的搜尋已排除所有可能指派;若另一個程式要驗證大型運算,可能還需要另設證明證書格式。可滿足的知識庫可以蘊涵某個查詢,儘管許多變量尚未確定。反過來,一個不完備規則系統未能導出查詢,本身並不證明其否定。
若知識庫本身不一致,就沒有模型,在古典邏輯中因而蘊涵任何查詢。這是「每個模型皆為真」之定義的後果,不是每個結論都有實用證據。數據可能矛盾時,應另外檢查一致性。計算成本取決於表示和搜尋選擇;一個例子算得快,不代表最壞情況也快。
常見錯誤
常見錯誤
(傳播靜靜停下並不是判決)
公式 既沒有單子句也沒有空子句,傳播無事可做,也不報告衝突。把這讀作「可滿足」是錯的:以 分支,兩個分支都衝突,公式不可滿足。仍有子句剩下的不動點,只表示需要作出決策。
常見錯誤
(檢驗了查詢本身,而不是它的否定)
對 與 ,合取式 可滿足,例如取 。 有模型,只說明 與 相容,不說明 蘊涵 。應檢驗 有沒有模型:有,取 ,所以 不蘊涵 。
習題
快速檢查
(對 執行上述程序,先選 。給出一個模型,指出所有被迫指派。)
每次化簡後,找出單子句。
解答 · 答案
令 ,第一子句變為單子句 ,故 ;最後一個子句再迫使 。第二子句因 為真而滿足。所以 滿足每個子句。
快速檢查
(對 ,以 分支,說明兩個分支都會衝突。)
化簡每個分支,找出成對的單子句 和 。
解答 · 答案
時,第二和第四子句分別變為 和 ,傳播產生衝突。 時,第一和第三子句分別變為 和 ,同樣衝突。 的兩個值已涵蓋全部情況,故公式不可滿足。
快速檢查
( 是否蘊涵 ?給出 的反證或一個反模型。)
嘗試令 為假,同時保持兩個子句為真。
解答 · 答案
不蘊涵。取 ,第一子句由 滿足,第二子句由 滿足,但 為假。這是 的模型,也是蘊涵的反例。
快速檢查
( 起初沒有單子句。僅因傳播停止而未見衝突,能否宣告它可滿足?它是否蘊涵 ?請說明。)
加入單子句 來檢驗蘊涵。
解答 · 答案
不能:既沒有單子句,也沒有發現衝突,並非可滿足的證明,因為仍有子句未決定。此例確實蘊涵 :加入 後,原來兩個子句分別變為 和 ,產生衝突。原公式亦可滿足,例如取 ;加入 的反證顯示蘊涵,而這個模型顯示原公式一致。