從事實推導後果
規則系統可以儲存事實和連接事實的規則。前向鏈推理從事實開始;當某條規則的所有前提已知,就加入其結論。使用前必須先說明語言。
定義 20.1.1
(有限 Horn 規則庫)
原子是有限個命題符號,每條規則形如
前提和結論都是原子。我們把前提視為集合,同一原子重複出現不構成第二個要求。沒有前提的規則()就是事實。本節沒有變量、函數符號、否定結論或表達矛盾的規則。
定義 20.1.2
(賦值、模型與蘊涵)
一個賦值指定哪些原子為真。若至少一個前提為假,或者結論為真,該賦值就滿足規則;因此規則不觸發也可以被滿足。若賦值滿足所有事實和規則,它就是知識庫的模型。知識庫蘊涵原子 ,意思是每個模型都令 為真;這關乎所有模型,而非某次執行處理規則的順序。
定義 20.1.3
(前向鏈閉包)
若每條前提全在集合 內的規則,其結論也在 內,就稱 是封閉的。閉包 這樣得到:從空集合開始,反覆加入某條規則的結論,條件是該規則的前提全在目前集合內而結論尚未在內,直至再沒有這樣的規則。事實沒有前提,所以最先加入。過程停下時的集合 稱為固定點。
追蹤一個小系統
例題 20.1.4
(雨天系統的前向鏈推理)
令 分別表示下雨、地面潮濕、地面易滑倒及灑水器開啟。這些名稱只供理解:下面的蘊涵是明確給定的形式規則,不是聲稱現實中每次下雨都會令地面潮濕。
| 類型 | 規則或事實 |
|---|---|
| 事實 | |
| 規則 | |
| 規則 | |
| 規則 | |
| 規則 |
從 開始。第一條規則加入 ,得到 。此時 的兩個前提都成立,故加入 ,得 。 雖可使用,但 已在集合內。沒有規則加入 ;只知道 不能令 反向觸發。於是到達固定點 。
反例模式
結論不能證明前提
由 和 推出 是錯誤的: 也可由 得到。在這個形式系統中,令恰好 為真的賦值滿足所有規則,卻令 為假。它是「知識庫蘊涵 」的具體反模型。
但這不表示知識庫蘊涵 :令四個原子全部為真也是模型。所以 和 都不被蘊涵;原子沒有出現在推導集合中,不等於一般地斷言它為假。
為甚麼固定點能回答正原子查詢?
定理 20.1.5
(閉包是最小模型)
設 是有限原子集合上的有限 Horn 規則庫。無論按甚麼次序使用可用規則,前向鏈推理都會終止,而其閉包 滿足:
- 中每個原子在 的每個模型中都為真;
- 恰好令 內原子為真的賦值本身是 的模型。
因此 按包含關係是 的最小模型,任何終止的處理次序都得到同一個 ,而且對原子 ,知識庫蘊涵 當且僅當 。
證明
(先證可靠性,再證閉包是模型)
原子集合有限,每一步有效加入都增加一個尚未出現的原子,所以過程終止。處理次序可以不同,但必須繼續至沒有規則能加入新原子。
首先, 中每個原子在每個模型都為真。初始事實如此。若某規則的所有前提都有此性質,每個模型都滿足這些前提,也因此必須滿足結論。歸納可知每次加入都可靠。
其次,考慮恰好令 內原子為真的賦值。所有事實都在 。若某規則的所有前提都在 ,其結論也必在 ;否則仍可加入新原子。若有前提不在 ,則該蘊涵在此賦值下為真。因此 本身是模型。
可靠性說明 包含於每個模型,而上一步說明它本身是模型,故 按集合包含關係是最小模型。正原子 若在 ,便在每個模型為真;若不在 ,模型 令它為假,因而證明它不被蘊涵。特別地,任何運行至固定點的規則處理順序都得到同一閉包。
證明透視
有限性、Horn 形式與兩個包含關係用在哪裏
有限性只用一次,就是保證終止:每個有效步驟都在有限的原子集合內擴大 。沒有有限性,過程可以不停。
Horn 形式,即結論只是一個正原子,是第二部分能成立的原因。每當所有前提都在 內,結論便可加入,所以 對所有規則封閉。若有一條無前提、結論為析取 的規則,則 與 都是模型,但它們的交集 不是模型,因此沒有最小模型,也沒有單一集合可追。
關鍵一步是兩個包含關係的夾逼。可靠性給出對每個模型 都有 ;規則下的封閉性給出 本身就是其中一個模型。包含於每個模型而且自身是模型的集合,必定是最小的。論證的收尾是把「不在 」變成證據:若 ,賦值 就是令 為假的模型,即具體反模型。這裏並沒有斷言 在每個模型都為假,所以得不到 。
此反模型回答的是「這個正原子是否在所有模型中必真」,並沒有採用「沒有記載的原子在現實中都為假」的封閉世界假設。上述結果也不聲稱能完整處理任意否定公式或不受限制的謂詞邏輯。
概念視角結構
閉包就是所有模型的交集
Horn 規則庫的模型集合對交集封閉:若 與 都滿足某條規則,而其全部前提都落在 內,則結論同時屬於兩者,因而屬於交集。所以所有模型的交集本身也是模型,並且是最小的一個,即 。對雨的系統,模型只有 與 ,兩者的交集是 ,正是前向鏈推理得到的閉包。被蘊涵的原子,就是落在這個交集內的原子。
下面的互動圖對這些規則重播前向鏈推理,並獨立檢查每個賦值,因此缺少的結論要由真正的反模型確認,而不是擅自當作假。
含有推不出前提的規則庫
例題 20.1.6
(沒有規則能推出的前提)
取事實 及規則 、、。前向鏈推理先加入 ,再加入 。原子 既不是事實,也不是任何規則的結論,所以永不加入, 和 也永遠推不出。閉包是 。
令恰好 為真的賦值滿足該事實和三條規則,因為後兩條規則的前提 為假。所以 都不被蘊涵。五個原子全為真的賦值也是模型,所以 同樣都不被蘊涵。事實 是沒有前提的規則,所以它的前提計數在任何步驟之前已是零。
用工作隊列實作
為有效處理,對每個不同前提建立索引,列出包含它的規則。每條規則維持一個計數器,記錄尚未處理的不同前提數。每個已知事實只入隊一次。取出一個原子時,訪問以它為前提的規則並遞減計數器;計數器到零時,若結論尚未知,就加入並入隊一次。零前提規則的結論在初始化時加入。
例題 20.1.7
(雨天系統的計數器)
計數器起始值: 為 , 為 , 為 , 為 ;隊列中有 。
取出 :規則 降至 ,所以 加入並入隊;規則 由二降至一。取出 :規則 降至 ,所以 加入並入隊。取出 :規則 降至 ,但 已知,因此不入隊,迴圈終止。此時隊列已空。 的計數器從未改變,因為 從未被處理,所以 只經由 推出。
若使用適當的鄰接索引且每個原子最多入隊一次,初始化及處理的時間與空間均為 ;其中 是有限原子集合, 是規則集合, 是各規則不同前提出現次數的總和。此界包括初始化計數器和結論,並不適用於不受限制的一階推理引擎。
常見錯誤
常見錯誤
(只按規則順序掃描一遍就停)
設規則按 在前、 在後排列,事實為 。按排列順序掃描一遍,第一條規則因 尚未知而不適用;第二條規則加入 ,然後這一遍結束,沒有得到 。但 其實被蘊涵。應該繼續掃描,直至整一遍都沒有加入新原子;或改用工作隊列,它恰在某條規則的前提變成已知時才重新檢視該規則。
常見錯誤
(按前提出現次數而非不同前提計數)
前提構成集合,所以 只有一個不同前提。若因為 寫了兩次而把計數器初始化為二,但規則只在 之下索引一次,那麼處理 只會把它減至一,該規則永不觸發, 便丟失,雖然事實 蘊涵 。每個計數器應初始化為不同前提的個數。
練習與解答
快速檢查
(移除事實 且沒有其他事實時,雨天系統的閉包是甚麼?)
想想哪一條規則可以最先觸發。
解答 · 答案
空集合。循環或前提未滿足的規則都不能自行啟動。
快速檢查
(保留原事實,再加入規則 ;現在蘊涵 嗎?)
先追蹤 和 的推導。
解答 · 答案
是。先得 ,再得 ,最後由新規則得 ;可靠性保證它在每個模型為真。
快速檢查
(單一規則 能蘊涵 嗎?)
找一個滿足該規則而令 為假的賦值。
解答 · 答案
不能。令 均為假,蘊涵仍成立,此賦值是 的反模型。
快速檢查
(處理 時,為甚麼工作隊列不可再次加入 ?)
留意此時 已在閉包內。
解答 · 答案
已知;只讓新原子入隊可以避免循環造成無限重複工作,同時保留所有結論。
前向鏈把證明和程式連起來:推導出的原子有來自事實的證明,而完整閉包為每個未出現的正原子提供反模型。