動機
一條適用所有物件的規則,不應要求為每個名字另寫副本。由「所有已檢查包裹均放行」與「A 已檢查」,推理程序應找到合適代換。遇上巢狀項及多個變量時,所有相同變量都必須換成同一項,不能逐個出現位置獨立猜測,否則所得「證明」可能根本不受原前提支持。
合一處理這個一致代換問題,歸結則用它消去互補文字。把兩者分開,有助理解為何每步可靠的推理程序仍可能永不停止:局部步驟保持後果,並不表示可能步驟只有有限多個。本節完整證明有限項合一、一階歸結可靠性,以及有限命題片段的歸謬完備性;每個保證都有明確範圍。
讀者應先熟悉解釋、量詞與語義蘊涵。
定義
定義 4.1.1
(項與代換)
有限項可以是變量、常數,或由有限項組成的 。合一把函數符號看成語法構造器;不同構造器不會因代入而相同,即使某個特定解釋碰巧給它們相同值。代換 把有限多個變量換成項,並穿過所有構造器延伸;同一變量的各次出現一律一致。合成約定為 ,所以次序不能倒轉。
定義 4.1.2
(合一代換與最一般合一代換)
方程集 的合一代換,令每對項在語法上完全相同。最一般合一代換,簡稱 MGU,是合一代換 ,使任意其他解 在原方程變量上都能寫成 。它不必有唯一寫法;重新命名未受限制的變量,可得到等價答案。
定義 4.1.3
(子句與歸結)
文字是原子或其否定;子句是文字的析取,其中變量隱含全稱量化。空子句在任何解釋都假。結合兩子句之前,要把變量重新命名至兩邊互不相交,因為兩個全稱量詞各自獨立。對原子 ,若 合一它們,通常選 MGU,便由 及 歸結出 。
一般公式轉子句時,要消去蘊涵、把否定往內移、重新命名束縛變量並分配連接詞。存在見證尤其要小心: 可用新函數 取代 ,在擴充語言保持可滿足性。原模型為每個 選見證,擴充模型則在忘掉函數後給原公式見證。這不是原語言中的邏輯等價,也不能一般地換成同一常數。此處使用非空論域的普通古典語義及通常的見證選擇設定。
定理/命題
定理 4.1.4
(用方程簡化合一有限項)
對有限個有限一階項方程,下列程序會終止,無解時報失敗,有解時構造 MGU:刪除 ;把同構造器方程按分量分解;把變量方程定向為 ;不同構造器或 真正出現在 內部時失敗;其餘情況以 全面替換 並記錄綁定。依應用次序合成所有已記錄綁定。
定理 4.1.5
(歸結可靠,有限命題歸謬完備)
使用真正合一代換的一階歸結步驟可靠,即父子句蘊涵歸結子句。對有限原子上的有限命題子句,系統地以所有正負子句對消去變量,可判定可滿足性;當且僅當原集合不可滿足時導出空子句。下述有限證明本身不證任意一階實作完備。
證明思路
證明
(方程簡化的正確性與終止性)
刪去恆等式及分解 ,準確保留所有語法解。不同構造器不能靠換變量變成相同。若 真正在 內,任何有限代換後,右邊仍包含 作真子樹,比它大,不能與它相等。這就是出現檢查;容許循環無窮項將是另一種模型。
對合法方程 ,任何解都必須令 取 經該解代換後的值。因此把此綁定傳到其餘方程,不會失去任何解;反過來,變換後方程的解也可經此綁定延伸為舊解。逐步重複這個分解性質,得任意原解皆為記錄代換的實例。成功終止時已無剩餘方程,所以記錄本身是解,且最一般。
終止不能只說「式子變小」,因代換可能令式子變大。用字典序比較三個自然數:未解系統中的相異變量數目、項符號總數,以及左邊非變量而右邊是變量的 方程數。消去嚴格減第一量,即使代換增大第二量也無妨;分解與刪恆等式不增第一量而減第二量;定向只轉此種 ,保持前兩量而減第三量。此良基量度排除無窮運行。
證明透視
出現檢查是一條數學界線
若有有限樹解,該樹便要包含自己作真部分,與有限大小矛盾。接受循環圖的程式正在解另一個問題;它的答案不能預設為本定理中的有限項代換。這個限制來自物件的定義,並非無關緊要的程式習慣。
證明
(歸結步驟的可靠性)
證歸結可靠性:滿足全稱父子句的模型,也滿足每個代換實例。合一後,所選原子一致;假如歸結子句所有剩餘文字都假,第一父句會逼該原子真,第二父句會逼它假,矛盾。因此所有父句模型都滿足歸結子句。預先把變量分開,避免意外把兩個獨立量詞當成同一變量。
證明
(消去一個原子保持可滿足性)
有限完備性可用消元證明。先刪恆真句與重複文字,再消去原子 ,把相關子句寫成 、;餘式不含 的任一符號。保留無關句,加入所有 ,再刪恆真句。可靠性給舊模型必滿足新句。反過來,取滿足新句的其餘原子賦值。某個 假會要求 真;某個 假會要求 假。兩要求不可能同時出現,否則對應歸結子句也假。按唯一要求選 ,沒有要求則任選,便延伸成舊模型。因此消元雙向保持可滿足性。對有限原子數歸納,最後只剩恆真句或空子句,故不可滿足恰好導出空句。
證明透視
延拓一步為何需要每一個歸結式
容易的方向是可靠性:每個歸結式都被蘊涵,所以舊集合的模型也滿足新集合。真正的想法在逆向。在新集合的模型中,餘式 為假會迫使 為真,餘式 為假則迫使 為假。兩項要求不會同時出現,因為子句 屬於新集合,若兩者皆假它就會是假的。所以歸結式恰好是令 所受要求保持一致的子句;缺少任何一對 ,都可能留下無法延拓的模型。捨棄恆真式沒有影響,因為它們處處為真;原子個數有限只用於重複此步,直至沒有原子剩下。
例題詳解
例題 4.1.6
(MGU 需要合成代換)
合一 與 ,分解得 、。先綁定 ,再綁定 ,後者也要傳入先前 的像,得 。兩原子直接代入都成為 。只記 而不說後續合成,是未完成的答案;其他無關變量無須限制。
概念視角結構
按一般程度排序的合一子
若存在代換 使 ,記作 ,即 是 的一個實例。可解問題的所有合一子在此預序下構成一個集合,而 MGU 就是其中的最小元:它位於每個合一子之下,即每個合一子都是它的實例。任何兩個 MGU 互為對方的實例,只相差變量改名。對 與 , 與 都是 MGU;合一子 則是第一個 MGU 後接 。
例題 4.1.7
(以全稱規則歸謬)
子句為 、、。首兩句以 歸結得 ,再與第三句得空子句。因此原規則及事實蘊涵 ,因加入其否定便不一致。這不表示原來一致的知識庫蘊涵語言中所有原子;矛盾只用來證指定後果。
例題 4.1.8
(消元可得矛盾,也可重建模型)
、、、 消去 得 ,再與 歸結得 ,最後得空句。若移除 ,可取 假、 真滿足消元系統。首個原句要求 真,這也滿足第二句,於是重建原模型。延伸論證不是只說「有解」,而能實際給賦值。
常見錯誤
反例模式
不能各次出現獨立匹配
不同常數 下, 與 無法合一,因同時要求 、。把第一個出現配 、第二個配 ,並不是代換。修正方法是使用共同方程系統,全面傳播每個綁定。
常見錯誤
(混淆可靠性、完備性與終止)
可靠性、歸謬完備性與終止各不相同。有限命題消元會終止,但子句數仍可指數增長。有函數符號的一階語言可產生無窮多基項,所以「試所有實例」不是有限判定算法。適當公平的歸結演算配合因子化等規則,有更廣的歸謬完備性結果;本節有限證明並未提供該結果的證明。一直重試無關子句的任意策略,也不自動享有它。
常見錯誤
(以為等號已內建於歸結)
若等號指真正相等,普通謂詞歸結不會自動提供等者代換、函數同餘等性質,須有相等專用演算或合適公理。限時內找不到證明,也不等於找到反模型。精確有限推論與受資源限制的搜尋,不能標上同一種確定性。
常見錯誤
(歸結前沒有把變量改名分開)
子句 與 合起來不可滿足: 給出 ,而 給出 。若不改名,直接合一 與 ,會在出現檢查失敗,找不到歸結式。把第二個子句改名為 後,MGU 就得到空子句。
總結
合一強制共享變量承諾,對有限項給最一般代換。歸結保持後果地消去互補實例。有限命題消元完備,關鍵是任何縮減模型都能逐步延伸回原模型。無窮項空間、公平策略、因子化及相等,各需要額外分析;一步可靠不等於整個程序已解決它們。
練習
快速檢查
(求 與 的 MGU,直接代入驗證,指出自由變量。)
把原子的方程拆成各分量的方程,分解至每條方程一側是變量。
解答 · 答案
方程為 、、。分解中式與末式一致,得 ,而 不受限制。兩原子同成 。其他解只能再選 的值,並把同值放進 ,驗證最一般性。
快速檢查
(解釋 與 為何無有限項合一,導出觸發出現檢查的方程。)
把第一個代換代入第二條方程,看變量現在出現在哪裏。
解答 · 答案
有 、,把前者代後者得 。定向為 ,右邊真正包含 ,故出現檢查失敗。循環式不是有限項解。
快速檢查
(從 消去 ,判斷可滿足性並重建原模型。)
按 的正負號分組,作出所有正負配對的歸結式,並丟棄恆真式。
解答 · 答案
正餘式為 ,負餘式為 ,得歸結句 及恆真句 。刪恆真句,取 真;第三原句再要求 真,所有原句均滿足。得到單文字子句與得到空子句不同。
快速檢查
(要求 及 ,用兩元素模型說明把 換成 為何可改變可滿足性。)
試試 為相等的兩元素模型,再看常數版本強制了甚麼。
解答 · 答案
兩個指定句子與原句可在 、 為相等時成立,每個物件見證自己。常數替換配合明確的相等公理,卻要求所有物件等於同一 ,與兩物件不同矛盾。若沒有該公理,無限制謂詞 可關聯所有元素對,只選一個相等解釋不足以證不可滿足。新函數 能讓見證隨 變,保留原可能性;普通謂詞歸結仍非自動內建相等推理。