【正文】 Q(y)?R(z) 定義 12 C1， C2為無相同變元的子句； L1， L2為其中的兩個文字， L1和 172。 對任一非空有限可合一的公式集，一定存在最一般合一，而且 用合一算法一定能找到最一般合一。{g(y),u} = {P(a,h(a,g(y)),f(g(y)))} S3單元素集 ， σ3為 MGU。{a/z}= {a/z} S1= S0 例： 設(shè) S＝ {P(u, y, g(y)), P(x, f(u), z)},S有一個最一般合一 σ＝ {u/x， f(u)/y， g(f(u))/z} 對 S的任一合一，例如： θ＝ {a/x， f(a)/y， g(f(a))/z， a/u} 存在一個替換 λ＝ {a/u} 使得 θ ＝ σ ?λ 2022/8/17 72 (7) 定義 11 設(shè) S是一個非空的具有相同謂詞名的原子公式集， 從 S中各公式左邊的第一項開始，同時向右比較， 直到發(fā)現(xiàn)第一個不都相同的項為止，用這些項 的差異部分組成的集合就是 S的一個 差異集 。 例：設(shè) θ= {f(y)/x,z/y}, λ ={a/x,b/y,y/z} {t1 λ /x1, t2 λ /x2, u1/y1, u2/y2, u3/yn} ={f(b)/x， y/y， a/x， b/y， y/z} 從而 θ ?λ ={f(b)/x， y/z} 2022/8/17 70 (5) 定義 9 設(shè) S＝ {F1,F2,… ,Fn} 是一個原子謂詞公式集，若 存在一個替換 θ，可使 F1 θ =F2 θ =…=F n θ ，則稱 θ 為 S的一個 合一 ，稱 S為 可合一 的。 基表達式 ：沒有變元的表達式。 P(f(y))?R(y) P(a)?Q(y), 172。 P, Q}是不可滿足。Q 172。Q?R 172。Q (2, 6) (8) 172。S?Q (4) 172。T?Q (5) T (6) 172。T?Q} 子句集： (1) P (2) 172。T)?Q = (172。P?172。 2022/8/17 62 (8) 推論 設(shè) C1， C2是子句集 S的兩個子句， C1 2是 它們的歸結(jié)式，則 （ 1）若用 C1 2來代替 C1， C2 ，得到新的子句集 S1 ，則由 S1不可滿 足性可以推出原子句集 S的不可滿足性。 ? 歸結(jié)原理是正確的推理形式，由正確的推理形式推出了 F，則說明前提不真，即歸結(jié)出空子句的兩個親本子句至少有一個為假。 ? 由歸結(jié)原理可知 ： L ∧ 172。 L ? C2’= L → C2’ 由假言三段論得： C1 ∧ C2 = （ 172。 證明：設(shè) C1=L?C1’ ， C2 = 172。 2022/8/17 56 (2) 定義 4 設(shè) L為一個文字，則 L與 172。 有公式： G ＝ ?xP(x) 它的 Skolem標(biāo)準(zhǔn)型是 G’ ＝ P(a) 我們給出如下的解釋 I： D＝ {0,1}, a/0, P(0)/F, P(1)/T 在此解釋下， G＝ T,G’ ＝ F 2022/8/17 54 (12) 定理 1：謂詞公式 G不可滿足當(dāng)且僅當(dāng)其子句集 S不可滿 足。 P(y， f(y)) ? 172。 P(x， f(x)) ? Q(x,g(x)) ] ? [ 172。 P(x， y) ? ? z[Q(x,z) ? 172。E(u) ? I(s(u)) （ 5） N(a) （ 6） 172。G的子句集為 （ 1） 172。 結(jié)論：所有自然數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù)。 2022/8/17 49 (7) 練習(xí)：用謂詞公式表示下述命題。 消去全稱量詞。（ 6， 7， 8） 化子句集的步驟： 消去蘊含詞和等值詞。 P(y， f(y)) ? 172。 P(x， f(x)) ? Q(x,g(x))] ? [172。 2022/8/17 47 (5) [172。 P(x， f(x)) ? [Q(x， g(x)) ? 172。 R(x,y)]} 2022/8/17 46 (4) 消去存在量詞 (Skolem化） ,同時進行變元替換 原則：對于一個受存在量詞約束的變量，如果它 不受全稱量詞約束 ，則該變量用一個 常量代替 （這 個常量叫 Skolem常量 ），如果它 受全稱量詞約束 ， 則該變量用一個全稱量詞指導(dǎo)變元的 函數(shù)代替 （這 個函數(shù)叫 Skolem函數(shù) ） 。P(x) 172。(A ?B) 172。A) A 172。 Q(x,y) ?R(x,y)]} ?x {? y 172。A ?B) ?( 172。 ? y P(x， y) ? 172。R 172。B ? 172。 ?xA(x)=A(y) y是個體域中任一確定元素 (A ? B) ? A = B 2022/8/17 40 （ 3） 例 證明 是 和 邏輯 結(jié)果。 2022/8/17 32 （ 1） ? 自然演繹推理 利用一階謂詞推理規(guī)則的符號表示形式，可以把關(guān)于自然語言的邏輯推理問題，轉(zhuǎn)化為符號表達式的推演變換。 2022/8/17 31 （ 15） 定義 7：謂詞公式全個體域上的永真、永假、可滿足 設(shè) P為謂詞公式，對于任何個體域： （ 1）若 P都永真，則稱 P為永真式。 即對個體域 D中的所有 x均有 P（ x） ?Q（ f(x),b），所以公式 B在此解釋下的真值為 T。 在此解釋下： 當(dāng) x＝ 1時有 y＝ 1使 P（ x， y）的真值為 T； 當(dāng) x＝ 2時有 y＝ 1使 P（ x， y）的真值為 T； 即對于 D中的所有 X都有 y＝ 1使 P（ x， y）的真值為 T， 所以在此解釋下公式 A的真值為 T。P(x) ?R(x,y) ) 就是一個析取范式 2022/8/17 26 （ 10） 謂詞公式的解釋 設(shè) D為謂詞公式 P的個體域，若對 P中的個體常量、函數(shù)和謂詞按如下規(guī)定賦值： （ 1）為 每個個體常量 指派 D中的一個元素； （ 2）為 每個 n元函數(shù) 指派一個從 Dn到 D的映射，其中 Dn＝ {(x1,x2,?,x n)/x1,x2,?,x n ∈ D} （ 3）為 每個 n元謂詞 指派一個從 Dn到 {F,T}的映射。 R(x,y) ) 就是一個合取范式 2022/8/17 25 （ 9） 定義 5：析取范式 （ Disjunctive Normal Form） 設(shè) A為如下形式的謂詞公式： B1 ? B2 ?… ? Bn 其中 Bi（ i=1,2,… ， n）形如 L1 ? L2 ? … ? Lm， Lj（ j=1， 2,… ， m）為原子公式或其否定，則 A稱為析取范式 。 ? P ? x P（ x） ? 全稱命題： ? x P(x)等價于 P (a1)?P(a2)? ? ?P(an) ? 特稱命題 ? x G(x)等價于 P (a1)?P(a2)? ? ? P (an) 2022/8/17 24 （ 8） 定義 4：合取范式（ Conjunctive Normal Form） 設(shè) A為如下形式的謂詞公式： B1 ? B2 ? … ? Bn 其中 Bi（ i=1,2,… ， n）形如 L1 ? L2 ?… ? Lm， Lj（ j=1， 2,… ， m）為原子公式或其否定，則 A稱為合取范式。 ? 一個謂詞公式中所有個體變元被量化，謂詞公式就變成了一個命題。 ? 自由變元 ：在一個量詞轄域中與該量詞的指導(dǎo)變元不同的變元稱為自由變元。所以全體命題公式也是謂詞公式。 （ 2）若 A、 B是謂詞公式，則 A， A ? B， A ? B， A ? B， A←→ B， ?xA， ?xA也是謂詞公式。 （ 3）只有有限次使用（ 1），（ 2）得到的符號串才是項。 F2: ?x (I(x)?(E(x) ?O(x))) （ 3）偶數(shù) 除以 2是整數(shù)。 GZ(x):x大于零。 首先定義如下謂詞： N(x):x是自然數(shù)。 已知前提： （ 1） 自然數(shù) 都是 大于零 的 整數(shù) 。即 ? x(P(x) ?…) 例：對于所有的自然數(shù)，均有 x+yx ?x ?y（ N （ x） ? N（ y） ? S(x,y,x)） 例 ：某些人對某些食物過敏 ? x ? y(M(x) ? N(y) ?G（ x， y）） (1)對全稱量詞，把限定詞作為蘊含式之前件加入。 記為 ?x 全稱量詞 表示“在個體域中存在個體”。 函數(shù) father(x): 值為 x的父親。 個體變元的變化范圍稱為 個體域 。 F：老李是小李的父親。 P:今天天氣好 Q:去旅游 S1：我有名字 S2：你有名字 P?Q表示：如果今天天氣好，就去旅游。 2022/8/17 6 機器推理概述（ 4） ? 本章主要解決以下幾個問題： 一階謂詞邏輯及基于一階謂詞邏輯的知識表示 謂詞公式到子句集的轉(zhuǎn)換 命題邏輯和謂詞邏輯中的歸結(jié)原理 歸結(jié)策略 2022/8/17 7 謂詞、函數(shù)、量詞 謂詞公式 謂詞邏輯中的形式演繹推理 2022/8/17 8 、函數(shù)、量詞（ 1） 命題（ proposition）： 是具有真假意義的語句。 2022/8/17 5 ? 基于歸結(jié)原理的自動定理證明過程： 機器推理概述（ 3） 定理的自然語言描述 定理的謂詞公式描述 子句集 生成子句集 定理得證 應(yīng)用歸結(jié)規(guī)則＋歸結(jié)策略 自然語言處理生成謂詞公式 已知前提：（ 1）自然數(shù)都是大于零的整數(shù)。 判定法 ：該方法是對一類問題找出統(tǒng)一的計算機上可實現(xiàn)的算法。 2022/8/17 4 ?自動定理證明的基本方法： 機器推理概述（ 2） 定理證明器 ：它是研究一切可判定問題的證明方法。推理是人腦的一個基本功能和重要功能。它是人工智能的核心課題之一。 ?自動定理證明： 是機器推理的一種重要應(yīng)用，它是利用計算機證明非數(shù)值性的結(jié)果，很多非數(shù)值領(lǐng)域的任務(wù)如醫(yī)療診斷、信息檢索、規(guī)劃制定和難題求解等方法都可以轉(zhuǎn)化一個定理證明問題 。四色定理。LT程序、證明平面幾何的程序。 結(jié)論：所有自然數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù)。 ?用命題符號可以表示簡單的邏輯關(guān)系和推理。 ? 無法把不同事物間的共同特征表達出來。 S(x): x是學(xué)生； P(x,y): x是 y的雙親。用形如 f(x1， x2， ? ，xn)來表示個體變元對應(yīng)的個體 y，并稱之為 n元個體函數(shù) ，簡稱函數(shù)。 P(a,Y) 2022/8/17 12 、函數(shù)、量詞（ 5） 表示“對個體域中所有的（或任一個）個體” 。 (2)對存在量詞，把限定詞作為一個合取項加入。 2022/8/17 15 、函數(shù)、量詞（ 8） 練習(xí)：用謂詞公式表示下述命題。 結(jié)論：所有自然數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù)。 O(x):x是奇數(shù)。 F1: ?x (N(x)?GZ(x) ? I(x)) （ 2）所有整數(shù)不是 偶數(shù) 就是 奇數(shù) 。 （ 2） f是 n元函數(shù)符號，若 t1， t2， … ， tn是項，