【正文】 因為假設子句集 S是不可滿足的 ， 但其中卻不含有單文字子句 ， 則單元歸結就無法進行 。 例如 ， P(x)∨ Q(a)包孕于 P(f(a))∨ Q(a)∨ R(y) ， σ={f(a)/x} T(x)∨ S(y)包孕于 T(b)∨ S(v)∨ R(x) ， σ={b/x， v/y}。 包括：線性歸結策略 、 單元 （ 單文字 ） 歸結策略 、 輸入歸結策略 、 支持集策略等 。 即 Peter的父親是 David。 Father(David, John) （ 3） 將它們化成子句集得： S1={~Brother(x,y)∨ ~Father(z,x)∨ Father(z,y), Brother(John,Peter), Father(David,John)} 歸結推理方法 第二步：把問題用謂詞公式表示出來 ， 并將其否定與謂詞ANSWER作析取 。 （ 5） 如果得到歸結式 ANSWER ， 則問題的答案即在ANSWER謂詞中 。 這就說明對結論 B的否定是錯誤的 ， 推斷出定理的成立 。 （ 2） C1的因子 C1σ1與 C2的二元歸結式 。 在集合的表示下做減法或做并運算 ， 然后再寫成子句形 ， 如集合運算結果為 {P(x),～ Q(y)}， 可改寫為 P(x)∨ ～ Q(y)。 (2) 將歸結所得的歸結式放入子句集 S中 ， 得新子句集 S′。 既然至少有一個基例 Ci′ 為假 ， 因而 S的基例集 S′ 是不可滿足的 。 否則 ， 如果存在一個解釋 I0使 S為真 ， 那么依據(jù)定理 ，一定可以在 H域找到相對應的一個解釋 I*0使 S為真 。 例如 ， 對于子句集 S＝ {P(a),～ P(x)∨ P(f(x))} 它的 H域為 {a,f(a),f(f(a)),? }。 （ 1） 令 H0是 S中所出現(xiàn)的常量的集合 。 定義 子句 就是由一些文字組成的析取式 。 （ 2） 減少否定符號 （ ～ ） 的轄域 ， 使否定符號 “ ～ ” 最多只作用到一個謂詞上 。 然而 ， 要證明這個謂詞公式的永真性 ， 必須對所有個體域上的每一個解釋進行驗證 ， 這是極其困難的 。 自然演繹推理方法 拒取式的一般形式為 P→Q ， ～ Q ? ～ P 它表示如果謂詞公式 P→Q 為真且 Q為假，則可推得 P為假的結論。{tk/xk } Wk+1=wk{tk/xk } k=k+1 然后轉 （ 3） 。 定義 若 E1， E2， … ， En 有合一置換 σ， 且對 E1， E2， … ， En 的任一置換都存在一個置換 λ， 使得 θ= σ ?) ? /xn,u1/y1,u2/y2,? ,um/ym}。其中 xi是變量， ti是不同于 xi的項（常量，變量，函數(shù)），且 xi ?xj（ I?j）， i， j=1,2,…,n 。 常用的一些等價式參見教材 定義 對于謂詞公式 P和 Q，如果 P→ Q永真，則稱 P永真蘊含Q，且稱 Q為 P的 邏輯結論 ，稱 P為 Q的 前提 ，記作 P=Q。 謂詞公式的永假性又稱為不可滿足性或不相容性 。 （ 4） 若 A是合式公式 ， x是任一個體變元 ， 則 (?x)A和 (?x)A也都是合式公式 。如果某個 xi本身又是一個一階謂詞，則稱它為 二階謂詞 ，依次類推。一個謂詞也可以與多個個體相關聯(lián)，此種謂詞稱為 多元謂詞 ， 它刻畫了個體間的“關系” 。 表 命題邏輯真值表 P Q P∨Q P∧ Q P→Q P Q ~P T T T T T T F T F T F F F F F T T F T F T F F F F T T T 命題邏輯 定義 以下面的遞歸形式給出命題公式的定義： l （ 1） 原子命題是命題公式 。 前者稱為 命題常量 ， 后者稱為 命題變量 。 ?所謂雙向混合推理是指正向推理和反向推理同時進行 ，使推理過程在中間的某一步驟相匯合而結束的一種推理方法 。 推理概述 推理的控制策略 推理過程不僅依賴于所用的推理方法 ， 同時也依賴于推理的控制策略 。 （ 1） 演繹推理 演繹推理是從已知的一般性知識出發(fā) ， 推理出適合于某種個別情況的結論的過程 。第三章 確定性推理 按照推理過程所用知識的確定性，推理可分為確定性推理和不確定性推理。 它是一種由一般到個別的推理方法 。 控制策略包括推理方向 、 搜索策略 、 沖突消解策略等；而推理方法則是指在推理控制策略確定之后 ， 在進行具體推理時所要采取的匹配方法或不確定性傳遞算法等方法 。 推理概述 推理的沖突消解策略 推理過程中的沖突消解策略 ， 就是確定如何從多條匹配規(guī)則中選出一條規(guī)則作為啟用規(guī)則 ， 將它用于當前的推理 。 對于命題變量而言 ， 只有把確定的命題代入后 ， 它才可能有明確的邏輯值 （ T或 F） 。 l （ 2） A是命題公式 ， 則～ A也是命題公式 。 謂詞邏輯 謂詞的一般形式： P(x1,x2,… ,xn ) 其中 P是謂詞 ， 而 x1,x2,… ,xn是個體 。 謂詞和函數(shù)的區(qū)別： 謂詞具有邏輯值“真”或“假”，而函數(shù)則是某個個體到另一個個體（按數(shù)學上的概念是自變量到因變量）之間的映射。 （ 5） 只有按 （ 1） — （ 4） 所得的公式才是合式公式 。 謂詞邏輯 3． 謂詞公式的可滿足性 定義 對于謂詞公式 P， 如果至少存在一個解釋使得公式 P在此解釋下的真值為 T， 則稱公式 P是 可滿足的 。 以后要用到的一些永真蘊含式參見教材 謂詞邏輯 謂詞邏輯中還有如下一些推理規(guī)則： （ 1） P規(guī)則：在推理的任何步驟上都可引入前提 。 謂詞邏輯 例如 ， {a/x,b/y,f(x)/z}， {f(z)/x,y/z}都是置換 。 若 yi?{ x1,? ,xn}時 ， 先從上述集合中刪除 ui/yi 。 ?= ? λ ， 則稱 σ是 E1， E2， … ， En 的最一般合一置換 ， 記為 mgu。 （ 6） 算法終止 ， W的 mgu不存在 。 利用演繹推理解決問題 在利用自然演繹推理方法求解問題時，一定要注意避免兩種類型的錯誤：肯定后件的錯誤和否定前件的錯誤。 為了化簡問題 ， 和數(shù)學上常采用的方法一樣 ， 我們考慮反證法 。 （ 3） 重新命名變元名 ， 使所有的變元的名字均不同 ， 并且自由變元及約束變元亦不同 。 定義 不包含任何文字的子句稱為 空子句 ， 記為 NIL。 若 S中沒有常量出現(xiàn) ， 就任取一個常量 a?D， 規(guī)定 H0={a}。 對于子句 P(a)， 因為其中不含有變元 ， 所以它已是基子句 ， 而且 a?H， 所以它也是基例 。 這與 S在所有 H解釋下均為假矛盾 。 另外 ， 由于 S中的子句是有限的 ， 而每個子句又由有限的文字組成 ， 因而 S的不可滿足的基例集也是有限的 。 (3) 檢查子句集 S′中是否有空子句 (NIL),若有則停止推理 。 歸結推理方法 在謂詞邏輯中 ， 對子句進行歸結推理時 ， 要注意以下幾個問題： （ 1） 若被歸結的子句 C1 和 C2中具有相同的變元時 ， 需要將其中一個子句的變元更名 ， 否則可能無法做合一置換 。 （ 3） C1與 C2的因子 C2σ2的二元歸結式 。 歸結推理方法 例 已知： A: (?x)((? y)(P(x,y)∧ Q(y))→ (? y)(R(y)∧ T(x,y))) B: ～ (? x)R(x)→ (? x)(? y)(P(x,y)→ ～ Q(y)) 求證： B是 A的邏輯結論 。 歸結推理方法 例 任何兄弟都有同一個父親 ， John和 Peter是兄弟 ， 且John的父親是