【文章內(nèi)容簡(jiǎn)介】 ， 且 xk不在 tk中 出現(xiàn) ， 則置： σk+1=σk {tk/xk } Wk+1=wk{tk/xk } k=k+1 然后轉(zhuǎn) （ 3） 。 （ 6） 算法終止 ， W的 mgu不存在 。 可以證明，如果 E1和 E2可合一，則算法必停止于第（ 3）步。 35 謂詞邏輯 例 設(shè) E1=P(a,v,f(g(y)))， E2=P(z,f(a),f(u))， 求 E1 和 E2的 mgu。 解題請(qǐng)參見(jiàn)教材 答案為： σ3= {a/z ,f(a)/v,g(y)/u} σ3就是 E1 和 E2的 mgu。 36 自然演繹推理方法 自然演繹推理的概念 自然演繹推理是指從一組已知為真的事實(shí)出發(fā)，直接運(yùn)用命題邏輯或謂詞邏輯中的推理規(guī)則推出結(jié)論的過(guò)程。 假言三段論的基本形式為 P→Q ， Q→R ?P→R 它表示如果謂詞公式 P→Q 和 Q→R 均為真，則謂詞公式 P→R 也為真。 假言推理可用下列形式表示 P， P→Q ? Q 它表示如果謂詞公式 P和 P→Q 都為真，則可推得 Q為真結(jié)論。 37 自然演繹推理方法 拒取式的一般形式為 P→Q ， ～ Q ? ～ P 它表示如果謂詞公式 P→Q 為真且 Q為假，則可推得 P為假的結(jié)論。 利用演繹推理解決問(wèn)題 在利用自然演繹推理方法求解問(wèn)題時(shí)，一定要注意避免兩種類型的錯(cuò)誤：肯定后件的錯(cuò)誤和否定前件的錯(cuò)誤。 38 自然演繹推理方法 肯定后件的錯(cuò)誤 是指當(dāng) P→ Q為真時(shí)，希望通過(guò)肯定后件 Q為真來(lái)推出前件 P為真。這顯然是錯(cuò)誤的推理邏輯，因?yàn)楫?dāng) P→ Q及 Q為真時(shí)，前件 P既可能為真，也可能為假。 否定前件的錯(cuò)誤 是指當(dāng) P→ Q為真時(shí)，希望通過(guò)否定前件 P來(lái)推出后件 Q為假。這也是不允許的，因?yàn)楫?dāng) P→ Q及 P為假時(shí)，后件 Q既可能為真，也可能為假。 相關(guān)的例題請(qǐng)參見(jiàn)教材 39 自然演繹推理方法 演繹推理的特點(diǎn) 參見(jiàn)教材 40 歸結(jié)推理方法 研究用計(jì)算機(jī)實(shí)現(xiàn)定理證明的機(jī)械化 ， 已是人工智能研究的一個(gè)重要領(lǐng)域 。 對(duì)于定理證明問(wèn)題 ， 如果用一階謂詞邏輯表示的話 ， 就是要求對(duì)前提 P和結(jié)論 Q證明 P→ Q是永真的 。 然而 ， 要證明這個(gè)謂詞公式的永真性 ， 必須對(duì)所有個(gè)體域上的每一個(gè)解釋進(jìn)行驗(yàn)證 ， 這是極其困難的 。 為了化簡(jiǎn)問(wèn)題 ， 和數(shù)學(xué)上常采用的方法一樣 ， 我們考慮反證法 。 即 ， 我們先否定邏輯結(jié)論 Q， 再由否定后的邏輯結(jié)論～ Q及前提條件 P出發(fā)推出矛盾 ， 即可證明原問(wèn)題 。 41 歸結(jié)推理方法 1． 范式 ? 前束形范式 一個(gè)謂詞公式 ， 如果它的所有量詞均非否定地出現(xiàn)在公式的最前面 ，且它的轄域一直延伸到公式之末 ， 同時(shí)公式中不出現(xiàn)連接詞 → 及 ? ，這種形式的公式稱作前束形范式 。 例如 ， 公式 (? x)(?y)(? z)(P(x)∧ F(y,z)∧ Q(y,z)) 即是一個(gè)前束形的公式 。 42 歸結(jié)推理方法 ? 斯克林范式 從前束形范式中消去全部存在量詞所得到的公式即為 Skolem范式 ，或稱 Skolem標(biāo)準(zhǔn)型 。 例如 ， 如果用 f(x)代替上面前束形范式中的 y即得到 Skolem范式： (? x) (? z)(P(x)∧ F(f(x), z)∧ Q(f(x), z)) Skolem標(biāo)準(zhǔn)型的一般形式是 (? x1)(? x2)… (? xn)M(x1,x2,… ,xn) 其中 ， M(x1,x2,… ,xn)是一個(gè)合取范式 ， 稱為 Skolem標(biāo)準(zhǔn)型的母式 。 43 歸結(jié)推理方法 將謂詞公式 G化為 Skolem標(biāo)準(zhǔn)型的步驟如下： （ 1） 消去謂詞公式 G中的蘊(yùn)涵 （ → ） 和雙條件符號(hào)（ ? ） ， 以～ A∨ B代替 A→ B， 以 (A∧ B)∨ (～ A∧ ～ B)替換A?B。 （ 2） 減少否定符號(hào) （ ～ ） 的轄域 ， 使否定符號(hào) “ ～ ” 最多只作用到一個(gè)謂詞上 。 （ 3） 重新命名變?cè)?， 使所有的變?cè)拿志煌?， 并且自由變?cè)凹s束變?cè)嗖煌?。 44 歸結(jié)推理方法 （ 4） 消去存在量詞 。 這里分兩種情況 ， 一種情況是存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi) ， 此時(shí) ， 只要用一個(gè)新的個(gè)體常量替換該存在量詞約束的變?cè)?， 就可以消去存在量詞；另一種情況是 ， 存在量詞位于一個(gè)或多個(gè)全稱量詞的轄域內(nèi) ， 這時(shí)需要用一個(gè) Skolem函數(shù)替換存在量詞而將其消去 。 （ 5） 把全稱量詞全部移到公式的左邊 ， 并使每個(gè)量詞的轄域包括這個(gè)量詞后面公式的整個(gè)部分 。 （ 6） 母式化為合取范式：任何母式都可以寫(xiě)成由一些謂詞公式和謂詞公式否定的析取的有限集組成的合取 。 需要指出的是 ， 由于在化解過(guò)程中 ， 消去存在量詞時(shí)作了一些替換 ，一般情況下 ， G的 Skolem標(biāo)準(zhǔn)型與 G并不等值 。 45 歸結(jié)推理方法 2． 子句與子句集 定義 不含有任何連接詞的謂詞公式叫 原子公式 ， 簡(jiǎn)稱原子 ， 而原子或原子的否定統(tǒng)稱 文字 。 定義 子句 就是由一些文字組成的析取式 。 定義 不包含任何文字的子句稱為 空子句 ， 記為 NIL。 定義 由子句構(gòu)成的集合稱為 子句集 。 46 歸結(jié)推理方法 3． 不可滿足意義下的一致性 定理 設(shè)有謂詞公式 G， 而其相應(yīng)的子句集為 S，則 G是不可滿足的充分必要條件是 S是不可滿足的 。 要再次強(qiáng)調(diào)： 公式 G與其子句集 S并不等值 ， 只是在不可滿足意義下等價(jià) 。 相關(guān)的例子參見(jiàn)教材中的例 47 歸結(jié)推理方法 4． P＝ P1∧ P2∧ … Pn的子句集 當(dāng) P＝ P1∧ P2∧ … Pn時(shí) ， 若設(shè) P的子句集為 SP，Pi的子句集為 Si， 則一般情況下 ， SP并不等于S1∪ S2∪ S3… ∪ Sn， 而是要比 S1∪ S2∪ S3… ∪ Sn復(fù)雜得多 。 但是 ， 在不可滿足的意義下 ， 子句集 SP與 S1∪ S2∪ S3… ∪ Sn是一致的 ， 即 SP不可滿足 ?S1∪ S2∪ S3… ∪ Sn不可滿足 48 歸結(jié)推理方法 Herbrand理論 1． H域 定義 設(shè)謂詞公式 G的子句集為 S， 則按下述方法構(gòu)造的個(gè)體變?cè)?H。 稱為公式 G或子句集 S的 Herbrand域 ， 簡(jiǎn)稱 H域 。 （ 1） 令 H0是 S中所出現(xiàn)的常量的集合 。 若 S中沒(méi)有常量出現(xiàn) ， 就任取一個(gè)常量 a?D， 規(guī)定 H0={a}。 （ 2） 令 Hi+1=Hi∪ {S中所有的形如 f(t1,… ,tn)的元素 } 其中 f(t1,… ,tn)是出現(xiàn)于 G中的任一函數(shù)符號(hào) ， 而 t1， … ， tn是 Hi中的元素 。i=0， 1， 2， … 。 49 歸結(jié)推理方法 例 求子句集 S＝ {T(x)∨ Q(z),R(f(y))}的 H域 。 解 此例中沒(méi)有個(gè)體常量 ， 任意指定一個(gè)常量 a作為個(gè)體常量；只有一個(gè)函數(shù) f(y)， 有： H0={a} H1={a,f(a)} H2={a,f(a),f(f(a))} …… H∞={a,f(a),f(f(a)),f(f(f(a))),… } 50 歸結(jié)推理方法 2． 原子集 定義 下列集合稱為子句集 S的 原子集 ： A＝ ｛ 所有形如 P(t1, t2,… ,tn)的元素 ｝ 其中 ， P(t1, t2,… ,tn)是出現(xiàn)在 S中的任一謂詞符號(hào) ，而 t1， t2， … ， tn則是 S的 H域上的任意元素 。 51 歸結(jié)推理方法 定義 將沒(méi)有變?cè)霈F(xiàn)的原子 、 文字 、 子句和子句集分別稱作 基原子 、 基文字 、 基子句 和 基子句集 。 定義 當(dāng)子句集 S中的某個(gè)子句 C中的所有變?cè)?hào)均以其 H域中的元素替換時(shí) ， 所得到的基子句稱作 C的一個(gè) 基例 。 例如 ， 對(duì)于子句集 S＝ {P(a),～ P(x)∨