【正文】 是二元謂詞，而 P(x1,x2,…,x n )則是 n元謂詞。如果某個 xi本身又是一個一階謂詞，則稱它為 二階謂詞 ，依次類推。 謂詞邏輯 謂詞公式 1. 連接詞 ～ ， ∨ ， ∧ ， → ， ? 2. 量詞 為刻畫謂詞與個體間的關(guān)系 ， 引入了兩個量詞：全稱量詞（ ?x） ,和存在量詞 （ ?x） 。 謂詞邏輯 由原子公式的定義出發(fā) ， 可定義謂詞演算的合式公式如下 。 （ 2） 若 A是合式公式 ， 則～ A也是合式公式 。 （ 4） 若 A是合式公式 ， x是任一個體變元 ， 則 (?x)A和 (?x)A也都是合式公式 。 謂詞邏輯 4. 量詞轄域與約束變元 在一個公式中，如果有量詞出現(xiàn)，位于量詞后面的單個謂詞或者用括弧括起來的合式公式稱為 量詞的轄域 。 謂詞邏輯 謂詞公式的永真性和可滿足性 1． 謂詞公式的解釋 定義 設(shè) D為謂詞公式 P的個體域 ， 若對 P中的個體常量 、 函數(shù)和謂詞按照如下規(guī)定賦值： （ 1） 為每個個體常量指派 D中的一個元素； （ 2） 為每個 n元函數(shù)指派一個從 Dn到 D的映射 ， 其中 Dn={(x1,x2,… ,xn)|x1,x2,… ,xn ?D} （ 3） 為每個 n元謂詞指派一個從 Dn到 {F,T}的映射； 則稱這些指派為公式 P在 D上的一個 解釋 。 詳細的求解過程參見教材 謂詞邏輯 2． 謂詞公式的永真性 定義 如果謂詞公式 P， 對個體域 D上的任何一個解釋都取得真值 T， 則稱 P在 D上是 永真的 ；如果 P在每個非空個體域上均永真 ， 則稱 P永真 。 謂詞公式的永假性又稱為不可滿足性或不相容性 。 按照定義 ，對謂詞公式 P，如果不存在任何解釋，使得 P的取值為 T，則稱公式 P是 不可滿足的 。若 P永假，則也可稱 P是不可滿足的。若對 D上的任何一個解釋， P與 Q的取值都相同，則公式 P和 Q在域D上是 等價的 。 常用的一些等價式參見教材 定義 對于謂詞公式 P和 Q，如果 P→ Q永真，則稱 P永真蘊含Q，且稱 Q為 P的 邏輯結(jié)論 ，稱 P為 Q的 前提 ，記作 P=Q。 （ 2） T規(guī)則：推理時 ， 如果前面步驟中有一個或多個永真蘊含公式 S， 則可把 S引入推理過程中 。 （ 4） 反證法： P=Q， 當且僅當 P∧ ～ Q?F， 即 Q為 P的邏輯結(jié)論 ， 當且僅當 P∧ ～ Q 是不可滿足的 。 定理 Q為 P1， P2， … ， Pn的邏輯結(jié)論 ， 當且僅當 (P1∧ P2∧ … ∧ Pn)∧ ～ Q是不可滿足的 。其中 xi是變量， ti是不同于 xi的項（常量，變量，函數(shù)），且 xi ?xj（ I?j）， i， j=1,2,…,n 。 不含任何元素的置換稱為空置換，以 ?表示。 定義 ?={t1/x1,t2/x2,? ,tn/xn} ?={u1/y1,u2/y2,? ,um/ym} 是兩個置換 ， 則它們的乘積是一個新置換 ， 其作用于公式 E時 ， 相當于先 ?后 λ對 E的作用 。 ?/x1,t2 ? /xn,u1/y1,u2/y2,? ,um/ym}。 若 ti ? /xi 。 ? 。 ?) ( ? 即只有 ? ? = ? 。 定義 若 E1， E2， … ， En 有合一置換 σ， 且對 E1， E2， … ， En 的任一置換都存在一個置換 λ， 使得 θ= σ 謂詞邏輯 ? 最一般合一置換的求取算法 設(shè)有兩個謂詞公式： E1： P(x,y,z)。 （ 2） 令 k=0， Wk=W， σk=ε ； ε是空置換 ， 它表示不作置換 。 （ 4） 找出 Wk的不一致集 Dk 。{tk/xk } Wk+1=wk{tk/xk } k=k+1 然后轉(zhuǎn) （ 3） 。 可以證明，如果 E1和 E2可合一，則算法必停止于第（ 3）步。 解題請參見教材 答案為： σ3= {a/z ,f(a)/v,g(y)/u} σ3就是 E1 和 E2的 mgu。 假言三段論的基本形式為 P→Q ， Q→R ?P→R 它表示如果謂詞公式 P→Q 和 Q→R 均為真，則謂詞公式 P→R 也為真。 自然演繹推理方法 拒取式的一般形式為 P→Q ， ～ Q ? ～ P 它表示如果謂詞公式 P→Q 為真且 Q為假，則可推得 P為假的結(jié)論。 自然演繹推理方法 肯定后件的錯誤 是指當 P→ Q為真時，希望通過肯定后件 Q為真來推出前件 P為真。 否定前件的錯誤 是指當 P→ Q為真時，希望通過否定前件 P來推出后件 Q為假。 相關(guān)的例題請參見教材 自然演繹推理方法 演繹推理的特點 參見教材 歸結(jié)推理方法 研究用計算機實現(xiàn)定理證明的機械化 ， 已是人工智能研究的一個重要領(lǐng)域 。 然而 ， 要證明這個謂詞公式的永真性 ， 必須對所有個體域上的每一個解釋進行驗證 ， 這是極其困難的 。 即 ， 我們先否定邏輯結(jié)論 Q， 再由否定后的邏輯結(jié)論～ Q及前提條件 P出發(fā)推出矛盾 ， 即可證明原問題 。 例如 ， 公式 (? x)(?y)(? z)(P(x)∧ F(y,z)∧ Q(y,z)) 即是一個前束形的公式 。 例如 ， 如果用 f(x)代替上面前束形范式中的 y即得到 Skolem范式： (? x) (? z)(P(x)∧ F(f(x), z)∧ Q(f(x), z)) Skolem標準型的一般形式是 (? x1)(? x2)… (? xn)M(x1,x2,… ,xn) 其中 ， M(x1,x2,… ,xn)是一個合取范式 ， 稱為 Skolem標準型的母式 。 （ 2） 減少否定符號 （ ～ ） 的轄域 ， 使否定符號 “ ～ ” 最多只作用到一個謂詞上 。 歸結(jié)推理方法 （ 4） 消去存在量詞 。 （ 5） 把全稱量詞全部移到公式的左邊 ， 并使每個量詞的轄域包括這個量詞后面公式的整個部分 。 需要指出的是 ， 由于在化解過程中 ， 消去存在量詞時作了一些替換 ，一般情況下 ， G的 Skolem標準型與 G并不等值 。 定義 子句 就是由一些文字組成的析取式 。 定義 由子句構(gòu)成的集合稱為 子句集 。 要再次強調(diào)： 公式 G與其子句集 S并不等值 ， 只是在不可滿足意義下等價 。 但是 ， 在不可滿足的意義下 ， 子句集 SP與 S1∪ S2∪ S3… ∪ Sn是一致的 ， 即 SP不可滿足 ?S1∪ S2∪ S3… ∪ Sn不可滿足 歸結(jié)推理方法 Herbrand理論 1． H域 定義 設(shè)謂詞公式 G的子句集為 S， 則按下述方法構(gòu)造的個體變元域 H。 （ 1） 令 H0是 S中所出現(xiàn)的常量的集合 。 （ 2） 令 Hi+1=Hi∪ {S中所有的形如 f(t1,… ,tn)的元素 } 其中 f(t1,… ,tn)是出現(xiàn)于 G中的任一函數(shù)符號 ， 而 t1， … ， tn是 Hi中的元素 。 歸結(jié)推理方法 例 求子句集 S＝ {T(x)∨ Q(z),R(f(y))}的 H域 。 歸結(jié)推理方法 定義 將沒有變元出現(xiàn)的原子 、 文字 、 子句和子句集分別稱作 基原子 、 基文字 、 基子句 和 基子句集 。 例如 ， 對于子句集 S＝ {P(a),～ P(x)∨ P(f(x))} 它的 H域為 {a,f(a),f(f(a)),? }。 歸結(jié)推理方法 3． H域上的解釋 定義 如果子句集 S的原子集為 A， 則對 A中各元素的真假值的一個具體設(shè)定都是 S的一個 H解釋 。相關(guān)舉例參見教材 歸結(jié)推理方法 定理 設(shè) I是子句集 S在域 D上的一個解釋 ， 則存在對應于 I的 H域解釋I*， 使得若有 S