撤回和新增事實有何不同
規則系統可能因感應器報告過熱,或技術員報告冒煙,而推論設備需要檢查。若感應器後來證實失靈,但冒煙報告仍可靠,結論應保留;只靠失靈感應器得出的結論則應撤回。刪除報告之後曾推出的所有結論過於激進:一個結論可以有多條獨立推導路徑。反過來,永久保留所有曾推出的結論也不正確。
以下以重新計算定義一個小型真值維護服務,作為更快的增量算法應滿足的正確性標準。模型只含有限命題及正規則,不處理否定、概率或互相矛盾的專家證詞。例子只是教學模型,並非設備安全指引。
有根據的規則語義
定義 17.1.1
(規則與推論算子)
設 是有限命題集合, 是目前接受的假設, 是有限規則集合;每條規則寫作 ,其中有限前提集合 ,結論 。容許空前提,表示無條件規則。定義
定義 17.1.2
(閉合集與有根據的閉包)
若每條 在 時都滿足 ,就稱 為閉集。
從 開始,令 。算子具單調性,因此序列遞增; 有限,所以最後穩定。對固定規則集 ,把穩定值記為 。從空集開始很重要:規則可以互相引用,但只有最終根植於現存假設或無條件規則的推導才被接受。
定理 17.1.3
(重新計算得到最小閉集)
在上述有限正規則模型中,迭代經至多 次嚴格增加便穩定。所得 包含 、對所有規則閉合,且包含於每個包含 的閉集中。特別地,若 ,則 。
證明
證明
(單調迭代與最小性)
單調性表示 蘊涵 。由 和歸納法得 。每次嚴格增加至少加入一個命題,所以這種增加最多發生 次。一旦 ,再應用同一算子便保持不變,因此序列穩定於固定點。固定點滿足 ,故包含假設,而且每條前提已在其中的規則,其結論也在其中。
令 包含 並對規則閉合。顯然 ;若 ,則 :假設在 中,而閉合性保證每條可用規則的結論也在 ,所以 。歸納得 。若 ,則 是包含 的閉集;由最小性得最後的包含關係。故在此模型撤回不會創造新結論;加入預設否定後不一定如此。
證明透視
固定點本身並不足夠
一組循環命題可以滿足所有蘊涵式,卻沒有根據。從空集出發選出最小固定點,而非任意自我支持的固定點。單調性依賴規則為正;檢查某命題不存在的規則會改變論證。
明確的更新契約
保持規則不變,記錄被接受的假設識別碼。撤回識別碼後,先建立剩餘假設集 ,再從空集重新算出 。舊畫面需要撤走的命題恰為 。若兩個獨立觀察都斷言同一命題,只撤回一個識別碼時,另一個仍使該命題保留在 。但同一觀察複製成兩行數據,不應被當作獨立證據;識別碼如何對應底層事件,是與閉包運算分開的數據來源問題。
可記下每個新命題首次推出的迭代階段,形成簡短解釋:所用規則的前提在更早階段已有。這條軌跡證明命題屬於閉包,卻不一定列出所有替代解釋。實際增量算法可以用依賴索引及支持數據,但每次更新都必須得到與重新計算相同的結果。僅因舊解釋指向另一個仍保留的命題,就繼續保留結論,並不符合這個契約。
常見錯誤
(混淆事件識別碼與命題)
從事件對應到命題時會出現兩種錯誤。若命題 由識別碼 與 斷言,而系統在撤回 時就刪除 ,便移除了仍有根據的結論。反過來,若第 行與第 行是同一份感應器報告的副本,撤回該報告就必須同時撤回兩行;把它們當作獨立證據,會令 因第 行而留在假設集內。
例子:兩條推導路徑
例題 17.1.4
(同一結論的替代路徑)
設 ,規則為 、、。其中 是分別接受的報告, 是中間結論, 是待考慮的檢查建議。從空集迭代得到
撤回 而保留 ,重新計算依次得 、、、。只有 消失: 仍支持 ,而 支持 。再撤回 ,閉包便是空集;相對上一次畫面消失的是 。所以更新時須考慮替代推導,而不是單純逆轉第一次產生 的軌跡。
例題 17.1.5
(合取支持與替代支持)
設 ,規則為 、、 及 。閉包是 。撤回 ,得 。從空集開始,依次得 、、、,最後一個已穩定。命題 消失,因為它唯一的規則需要 和 同時成立; 與 保留,因為 仍支持 。因此,含多個命題的前提像是支持的合取,而頭部相同的多條規則則像是替代支持。
例題 17.1.6
(假設、可推導命題與無條件規則)
設 ,規則為 及 。則 ,其中 在第一步由空前提規則得到。只撤回假設 :,迭代依次得 、、,所以 仍然保留,只是現在成為推導出來的命題。若改為撤回 :,,只有 消失。兩者都撤回:,,因為無條件規則不需要任何假設。
概念視角結構
證據、推論與行動
閉包只說明模型和現時接受的輸入推出哪些命題;它既不證明報告可靠,也不授權實際行動。接受哪些輸入是另一個證據政策;如何根據結論行動亦是另一個決策。
局部支持計數失效的循環
推導必須從結論以外的東西開始。只數算現時有多少條規則支持某個命題的更新程序並不檢查這一點,下面的個案說明了這個問題。
反例模式
互相支持不是根據
設 ,規則為 和 。起初 。撤回 後,;從空集開始甚麼也推不出,所以 。若簡單更新器只檢查每個舊命題是否有一條規則,其前提仍被保留(等價地,其目前滿足的支持規則數目大於零),就可能保留兩者: 似乎由 支持,而 又由 支持。此集合雖然閉合,卻不是最小閉集。沒有排除無根據循環的機制,單靠計數無法保證正確。
這並非禁止循環。若獨立假設 仍保留,且另有規則 ,那麼撤回假設 後, 都仍有根據。關鍵是有限推導能否從剩餘假設或空前提規則開始,而不是依賴圖是否含循環。
常見錯誤
(以為撤回只會移除結論)
在這個模型中, 蘊涵 。只要規則可以測試「不存在」,這個性質就不再成立,而這已超出上述正規則模型。例如規則「有 且沒有 則得 」使 ,但撤回 之後會推出 。只處理撤回的更新算法不可沿用於這類規則。
練習
練習 17.1.7
(設 ,規則為 、、。求閉包及撤回 後的閉包。哪些命題消失?)
基礎
解答(3)
- 1
撤回之前的閉包
從空集開始,迭代先得 ,再得 ,因為 已可觸發, 亦可觸發。最初的閉包是 。
- 2
撤回 p 之後的閉包
關鍵一步
剩下的假設是 。規則 仍適用,但 不適用。閉包是 。
依據: 只剩假設 ,而 的前提含兩個命題。
- 3
比較兩個閉包
命題 與 消失。另一條路徑 保住了 。
快速檢查
(設 ,規則為 、、。撤回 。為何不能靠互相支持保留 ?若再加 ,結果如何?)
解答 · 答案
沒有剩餘假設或空前提規則時,從空集迭代仍是空集。因此 與 都沒有根據,即使集合 是閉合的。若加入 ,第一次迭代推出 ,下一次推出 ,閉包是 。
快速檢查
(獨立事件識別碼 17 和 18 均斷言輸入命題 。程式員一撤回 17 就刪除 。說明錯誤,並提出正確的輸入表示。)
解答 · 答案
識別碼 18 仍斷言 ,所以單獨撤回 17 不會把 移出假設集。應為每個命題維護有效事件識別碼的集合,只要至少有一個有效而且獨立識別的事件斷言它,就保留該命題。套用這個政策之前,先去除複製的記錄。