【文章內容簡介】 （ Not） 表示否定，～、 — 均可表示 謂詞邏輯法37w量詞 全稱量詞（ Universal Quantifier） ：若一個原子公式 P（ x），對于所有可能變量 x都具有 T值， 則用 （ ? x） P（ x）表示例如 : 所有的機器人都是灰色的（ ? x ） [ ROBOT(x) = COLOR(x,GRAY) ]約束變元全程量詞作用域存在量詞（ Existential Quantifier） 若一個原子公式 P（ x），至少有一個變元 x，可使 P （ x）為 T值， 則用（ ? x） P（ x）表示。 例： (?x)INROOM(x,r1)（ 1號房間內有個物體）38 謂詞公式– 原子公式的的定義：? 用 P(x1， x2， … ， xn)表示一個 n元謂詞公式，其中 P為 n元謂詞， x1,x2,… ， xn為客體變量或變元。通常把 P(x1,x2,…,x n)叫做謂詞演算的 原子公式 ，或 原子謂詞公式 。– 分子謂詞公式? 可以用連詞把原子謂詞公式組成復合謂詞公式，并把它叫做 分子謂詞公式 。 謂詞邏輯法39w 合式公式 （ WFF， wellformed formulas）– 合式公式的遞歸定義(1)原子謂詞公式是 合式 公式。(2)若 A為合適公式，則～ A也是一個 合式 公式。(3)若 A和 B都是 合式 公式，則 (A∧B) ， (A∨B) ，(A?B)和 (A←→B) 也都是 合式 公式。(4)若 A是 合式 公式， x為 A中的自由變元，則 (?x)A和 (?x)A都是 合式 公式。(5)只有按上述規(guī)則 (1)至 (4)求得的那些公式，才是合式 公式。例題： 試把下列命題表示為謂詞公式：任何整數，或者為整數或者為負數。 謂詞邏輯法40w 合式 公式的性質– 合式 公式的真值– 等價（ Equivalence) 如果兩個 合式 公式，無論如何解釋，其真值表都是相同的，那么我們就稱此兩 合式 公式是等價的。T F T F F F表 21 真值表P Q P∨ Q P ∧ Q P?Q ～ PT T T T T FF T T F T TF F F F T T 謂詞邏輯法41等價關系w (1 〉否定之否定~(~P) 等價于 Pw (2)P ∨ Q 等價于 ~P= Qw (3) 狄 摩根定律~(P ∨ Q) 等價于 ~P ∧ ~Q~(P ∧ Q) 等價于 ~P ∨ ~Qw (4 〉 分配律P ∧ (Q ∨ R) 等價于 (P ∧ Q) ∨ (P ∧ R)P ∨ (Q ∧ R) 等價于 (P ∨ Q) ∧ (P ∨ R)w (5) 交換律P ∧ Q 等價于 Q ∧ PP ∨ Q 等價于 Q ∨ P 謂詞邏輯法42w 6) 結合律(P ∧ Q) ∧ R 等價于 P ∧ (Q ∧ R)(P ∨ Q) ∨ R 等價于 P ∨ (Q ∨ R)w (7) 逆否律P = Q 等價于 ~Q = ~Pw (8)~(? x)P(x) 等價于 (? x)[~P (x) ]~(? x)P(x) 等價于 (? x)[~P (x) ]w (9)(? x)[P(x) ∧ Q(x)] 等價于 (? x)P(x) ∧ (? x)Q(x) (? x)[P(x) ∨ Q(x)] 等價于 (? x)P(x) ∨ (? x)Q(x) w (10 〉 (? x)P(x 〉 等價于 (? y)P(y)(? x)P(x) 等價于 (? y)P(y) 43 置換與合一w謂詞邏輯的推理– 將推理規(guī)則應用于一定的合式公式（集），以產生新的合式公式。? 假元推理? 全稱化推理? 綜合推理? 思考：推理規(guī)則中存在項的變換與同一問題，如何實施？ 謂詞邏輯法W 1W 1?W 2 ? W 2（ ?x） W （ x） ? W （ A）任意變量約束變元( ?x ) [ W 1( x ) ? W 2( x ) ] W 1（ A） ? W 2（ A）44w置換 (Substitution) ：– 在表達式中用置換項置換變量，例如用項（ A）替換函數表達式中的變量（ x）。一個表達式 E（Expression）用一個置換 S（ Substitution）而得到的表達式的置換，記為 ES。w 例題：表達式 E： P[x,f(y),B]；置換：s1={z/x,w/y},s2={A/y}, s3={q(z)/x,A/y},s4={c/x,A/y}– Solution:ES1 = P[z,f(w),B]。 ES2 = P[x,f(A),B]。ES3 = P[q(z),f(A),B]。 ES4 = P[c,f(A),B]。 ES1S2 = P[z,f(w),B]。 ES2S1 = P[z,f(A),B]思考： (1) ES4S1， ES3S2？ (2) 置換的運算規(guī)則？ 謂詞邏輯法45w置換的性質? 可結合律 : （ LS1） S2 = L（ S1S2） （ S1S2） S3 = S1（ S2S3）問題：請舉例說明？? 不可交換律 : S1S2 = S2S1問題：請舉例說明？思考：什么置換是謂詞邏輯推理所需要的？ 謂詞邏輯法 /46w合一（ Unification)：– 合一： 尋找項對變量的置換，以使多個表達式一致的操作稱為 合一 。如果一個置換 s作用于表達式集 {Ei}的每個元素，則我們用 {Ei} s來表示置換例的集。– 可合一： 如果存在置換 s使得表達式集 {Ei}置換后有： E1S＝ E2S＝ E3S＝ …, 則我們稱表達式集 {Ei}是可合一的 ， s 稱為 {Ei} 的 合一者 。w例題： 表達式集 {P[x,f(y),B], P[x,f(B),B]} 的合一者：s ＝ { A/x,B/y }– 說明： P[x,f(y),B]s ＝ P[x,f(B),B]s ＝ P[A,f(B),B]思考：還有其他合一者嗎？ 謂詞邏輯法47w最通用的合一者： 如果對表達式集 {Ei}的任一合一者 s，都存在某一 s’，使得 {Ei}s ＝ {Ei}gs’，則稱 g為 {Ei}的最通用合一者。w 問題：上例題中，最通用的合一者是什么？w 置換與合一的作用：謂詞邏輯推理的基本方法，就是尋找簡單有效置換合一，采用消解原理利用消解反演方法求解問題，詳見第三章。 謂詞邏輯法48 語義網絡法 (Semantic Network Representa