【正文】 …… H∞={a,f(a),f(f(a)),f(f(f(a))),… } 歸結推理方法 2． 原子集 定義 下列集合稱為子句集 S的 原子集 ： A＝ ｛ 所有形如 P(t1, t2,… ,tn)的元素 ｝ 其中 ， P(t1, t2,… ,tn)是出現(xiàn)在 S中的任一謂詞符號 ，而 t1， t2， … ， tn則是 S的 H域上的任意元素 。i=0， 1， 2， … 。 若 S中沒有常量出現(xiàn) ， 就任取一個常量 a?D， 規(guī)定 H0={a}。 稱為公式 G或子句集 S的 Herbrand域 ， 簡稱 H域 。 相關的例子參見教材中的例 歸結推理方法 4． P＝ P1∧ P2∧ … Pn的子句集 當 P＝ P1∧ P2∧ … Pn時 ， 若設 P的子句集為 SP，Pi的子句集為 Si， 則一般情況下 ， SP并不等于S1∪ S2∪ S3… ∪ Sn， 而是要比 S1∪ S2∪ S3… ∪ Sn復雜得多 。 歸結推理方法 3． 不可滿足意義下的一致性 定理 設有謂詞公式 G， 而其相應的子句集為 S，則 G是不可滿足的充分必要條件是 S是不可滿足的 。 定義 不包含任何文字的子句稱為 空子句 ， 記為 NIL。 歸結推理方法 2． 子句與子句集 定義 不含有任何連接詞的謂詞公式叫 原子公式 ， 簡稱原子 ， 而原子或原子的否定統(tǒng)稱 文字 。 （ 6） 母式化為合取范式：任何母式都可以寫成由一些謂詞公式和謂詞公式否定的析取的有限集組成的合取 。 這里分兩種情況 ， 一種情況是存在量詞不出現(xiàn)在全稱量詞的轄域內 ， 此時 ， 只要用一個新的個體常量替換該存在量詞約束的變元 ， 就可以消去存在量詞；另一種情況是 ， 存在量詞位于一個或多個全稱量詞的轄域內 ， 這時需要用一個 Skolem函數(shù)替換存在量詞而將其消去 。 （ 3） 重新命名變元名 ， 使所有的變元的名字均不同 ， 并且自由變元及約束變元亦不同 。 歸結推理方法 將謂詞公式 G化為 Skolem標準型的步驟如下： （ 1） 消去謂詞公式 G中的蘊涵 （ → ） 和雙條件符號（ ? ） ， 以～ A∨ B代替 A→ B， 以 (A∧ B)∨ (～ A∧ ～ B)替換A?B。 歸結推理方法 ? 斯克林范式 從前束形范式中消去全部存在量詞所得到的公式即為 Skolem范式 ，或稱 Skolem標準型 。 歸結推理方法 1． 范式 ? 前束形范式 一個謂詞公式 ， 如果它的所有量詞均非否定地出現(xiàn)在公式的最前面 ，且它的轄域一直延伸到公式之末 ， 同時公式中不出現(xiàn)連接詞 → 及 ? ，這種形式的公式稱作前束形范式 。 為了化簡問題 ， 和數(shù)學上常采用的方法一樣 ， 我們考慮反證法 。 對于定理證明問題 ， 如果用一階謂詞邏輯表示的話 ， 就是要求對前提 P和結論 Q證明 P→ Q是永真的 。這也是不允許的，因為當 P→ Q及 P為假時，后件 Q既可能為真，也可能為假。這顯然是錯誤的推理邏輯，因為當 P→ Q及 Q為真時，前件 P既可能為真，也可能為假。 利用演繹推理解決問題 在利用自然演繹推理方法求解問題時，一定要注意避免兩種類型的錯誤：肯定后件的錯誤和否定前件的錯誤。 假言推理可用下列形式表示 P， P→Q ? Q 它表示如果謂詞公式 P和 P→Q 都為真，則可推得 Q為真結論。 自然演繹推理方法 自然演繹推理的概念 自然演繹推理是指從一組已知為真的事實出發(fā)，直接運用命題邏輯或謂詞邏輯中的推理規(guī)則推出結論的過程。 謂詞邏輯 例 設 E1=P(a,v,f(g(y)))， E2=P(z,f(a),f(u))， 求 E1 和 E2的 mgu。 （ 6） 算法終止 ， W的 mgu不存在 。 （ 5） 若 Dk中存在元素 xk和 tk ， 其中 xk是變元 ， tk是項 ， 且 xk不在 tk中 出現(xiàn) ， 則置： σk+1=σk （ 3） 如果 Wk只有一個表達式 ， 則算法停止 ， σk就是所要求的 mgu。 E2： P(x,f(a),g(b)) 分別從 E1與 E2的第一個符號開始逐個向右比較 ， 此時發(fā)現(xiàn) E1中的 y與 E2中的 f(a)不同 ， 則它們構成了一個不一致集： D1={y,f(a)} 當繼續(xù)向右比較時 ， 又發(fā)現(xiàn)中 E1中的 z與 E2中 g(b)不同 ， 則又得到一個不一致集： D2={z,g(b)} 下面給出求公式 {E1,E2}的最一般合一置換的算法： 謂詞邏輯 （ 1） 令 W={ E1,E2 }。 λ ， 則稱 σ是 E1， E2， … ， En 的最一般合一置換 ， 記為 mgu。 謂詞邏輯 2. 合一 ? 合一的概念 定義 設有公式集 {E1,E2,… ,En}和置換 θ ， 使 E1 θ = E2 θ =… =En θ 便稱 E1， E2， … ， En是 可合一的 ， 且 θ稱為 合一置換 。 ?=? ?) 但除了空置換外，置換的交換律不成立。 ?= ? ? 置換結合率 一般地說 ， 下列的置換結合律成立 (? 刪除以后剩下元素所構成的集合稱作 ?與 ?的乘積，記作 ? ? =xi時 ， 再從上述集合中刪除 ti 若 yi?{ x1,? ,xn}時 ， 先從上述集合中刪除 ui/yi 。 ?/x2,? ,tn 它的定義如下： 謂詞邏輯 先作置換 {t1 ? 置換乘法 置換乘法作用是將兩個置換合成為一個置換 。 謂詞邏輯 例如 ， {a/x,b/y,f(x)/z}， {f(z)/x,y/z}都是置換 。 謂詞邏輯 置換與合一 1. 置換 ? 置換的定義 定義 置換是形如 {t1/x1,t2/x2,…,t n/xn}的一個有限集。 推廣之 ， 可得如下定理 。 （ 3） CP規(guī)則：如果能從 R和前提集合中推出 S來 ， 則可從前提集合推出R→ S來 。 以后要用到的一些永真蘊含式參見教材 謂詞邏輯 謂詞邏輯中還有如下一些推理規(guī)則： （ 1） P規(guī)則：在推理的任何步驟上都可引入前提 。如果 D是任意個體域，則稱 P和 Q是 等價的 ，記作P? Q。 謂詞邏輯 謂詞公式的等價性與永真蘊含 定義 設 P與 Q是兩個謂詞公式， D是它們共同的個體域。所以，謂詞公式 P永假與不可滿足是等價的。 謂詞邏輯 3． 謂詞公式的可滿足性 定義 對于謂詞公式 P， 如果至少存在一個解釋使得公式 P在此解釋下的真值為 T， 則稱公式 P是 可滿足的 。 定義 如果謂詞公式 P對于個體域 D上的所有解釋都取得假值 F， 則稱 P在 D上是 永假的 ；如果 P在每個非空個體域上均永假 ， 則稱 P永假 。 謂詞邏輯 例 設個體域 D={1,2}， 求公式 A=(?x)(P(x)→ Q(f(x),b))在D上的某一個解釋 ， 并指出在此解釋下公式 A的真值 。在轄域內與量詞中同名的變元稱為 約束變元 。 （ 5） 只有按 （ 1） — （ 4） 所得的公式才是合式公式 。 （ 3） 若 A和 B都是合式公式 ， 則 A∧ B、 A∨ B、 A→ B、 A?B也都是合式公式 。 定義 可按下述規(guī)則得到謂詞演算的合式公式： （ 1） 原子謂詞公式是合式公式 。 3. 謂詞演算公式 定義 謂詞演算中 ， 由單個謂詞構成的不含任何連接詞的公式 ，叫做 原子謂詞公式 。 謂詞和函數(shù)的區(qū)別： 謂詞具有邏輯值“真”或“假”，而函數(shù)則是某個個體到另一個個體（按數(shù)學上的概念是自變量到因變量）之間的映射。 謂詞的階數(shù)： 在謂詞 P(x1,x2,?,x n )中，若 xi(i=1,2,?,n)都是個體常量、變元或函數(shù)，則稱它為 一階謂詞 。個體常數(shù) 、 變量和函數(shù)統(tǒng)稱為 項 。 項： 在謂詞中 ， 個體可以是 常量 ， 也可以是 變量 ， 還可以是一個 函數(shù) 。 謂詞邏輯 謂詞的一般形式： P(x1,x2,… ,x