【正文】 則 f（ t1， t2， … ， tn ）是項。 2022/8/17 19 （ 3） 定義 3：謂詞公式 （ 1）原子公式是謂詞公式。 由項的定義，當 t1， t2， … ， tn全為個體常元時，所得的原子謂詞公式就是原子命題公式（命題符號）。 ? 約束變元 ：在一個量詞轄域中與該量詞的指導變元相同的變元稱為約束變元。 ? x G(x) ? P（ x） ? x G(x) ? P（ y） 2022/8/17 22 （ 6） ? 謂詞公式與命題的區(qū)別與聯(lián)系 ? 謂詞公式是 命題函數(shù) 。 ? 二階謂詞 ：個體變元被量化，函數(shù)符號和謂詞符號也被量化。 Q(x) ? 172。P(x) ? Q(y)) ?(172。 解：公式里沒有個體常量和函數(shù)，所以直接為 謂詞指派真值 ，設為 P（ 1， 1）＝ T P（ 1， 2）＝ F P（ 2， 1）＝ T P（ 2， 2）＝ F 這就是 A在 D上的一個解釋。 當 x＝ 2時有 P(2)=T, Q(f(2),1)=Q(1,1)=T 所以 P（ x） ?Q（ f(x),b）為 T。 （ 3）若至少有一個解釋，可是 P為真，則稱 P在 D上是 可滿足式 。 謂詞公式的真值與個體域及真值有關，考慮到個體域的 數(shù)目和個體域中元素數(shù)目無限的情形，所以要通過算法 判斷一個謂詞公式永真是不可能的，所以稱一階謂詞邏 輯是不可判定的。 試問：小王學過計算機嗎？ ))x(M)x(S(x)( ??1)a(S)( 2)a(M)a(S)( ?2)a(S)(3)a(M)( 4解：令 S（ x） ： x是大學生 M（ x） ： x學過計算機； a： 小王 上面命題用謂詞公式表示為： ))x(M)x(S(x)( ??1 [前提 ] [(1),US] [前提 ] [(2),(3),I3] 我們進行形式推理： M(a)，即小王學過計算機。 A 拒取式 2022/8/17 41 （ 4） 例 證明 ))x(P)x(R(x))x(Q)x(R(x))x(Q)x(P(x ??????????證： ))x(Q)x(P(x)( ??1 [前提 ] [(1),US] [(2),E24] [(3),(5),I6] )y(Q)y(P)( ?2)()()3( yPyQ ???)y(Q)y(R)( ??5)y(P)y(R)( ??6))x(P)x(R(x)( ???7))x(Q)x(R(x)( ???4 [前提 ] [(4),US] [(1),UG] A?B = 172。D(y) I(a) P ?Q ?172。 ?y[Q(x,y) ?R(x,y)]} 由第一步可得： ?x {172。A ?B A B (172。?y[172。 (172。B 172。?xP(x) ?x172。 P(x， y) ? ? y [Q(x,y) ? 172。 R(x， z)]} = ?x {172。 R(x,g(x))] 消去所有全稱量詞。 R(x,g(x))] [172。 P(x， f(x)) ? Q(x,g(x)) , 172。 R(x,g(x))] 2022/8/17 48 (6) 子句集 ： 無量詞約束；（ 3， 4， 5） 元素只是文字的析??；（ 1） 否定符只作用于單個文字；（ 2） 元素間默認為合取。 消去存在量詞。 消去合取詞，以子句為元素組成一個集合 S。 （ 3）偶數(shù)除以 2是整數(shù)。 F1: ?x (N(x)?GZ(x) ? I(x)) F2: ?x (I(x)?(E(x) ?O(x))) F3: ? x (E(x) ? I(s(x))) G: ?x (N(x)?(I(s(x)) ?O(x))) 2022/8/17 50 (8) 解： F1 ? F2 ? F3 ? 172。I(z) ? E(z) ?O(z) （ 4） 172。 ?x {? y 172。 R(x,g(x))]} = ?x {[ 172。 P(x， f(x)) ? Q(x,g(x)) , 172。 但 Skolem標準型與原公式一般并不等價。歸結(jié)原理提出的是一種證明子句集不可滿足性，從而實現(xiàn)定理證明的一種理論及方法。 例 設 ，則 C1 、 C2的歸結(jié)式為： SQC,RQPC ??????? 21RSPC ????122022/8/17 57 (3) 定理 2 歸結(jié)式是其親本子句的邏輯結(jié)果。 C1 ’ → L C2= 172。這說明，歸結(jié)原理可以代替其他所有的推理規(guī)則，而且推理步驟比較機械，為機器推理提供了方便。 2022/8/17 61 (7) ? 推出空子句就說明子句集不可滿足，原因是： ? 空子句就是 F，推出空子句就是推出了 F。 ? 同樣的道理向上回溯，一定會推出原子句集中至少有一個子句為假，從而說明 S不可滿足。(P?Q)?R = 172。S?172。S?Q, 172。S?Q (4) 172。Q?R (3) 172。P?172。P?172。Q P 172。 Q, 172。 P(a)?R(z) ? 解決方法 對個體變元做適當替換 例如： P(f(y))?Q(z), 172。 {a/x,g(a)/y,f(g(b))/z}就是一個替換 {g(y)/x,f(x)/y}就 不是 一個替換， x與 y出現(xiàn)了循環(huán)替換 2022/8/17 68 (3) 表達式 ：項、原子公式、文字、子句的統(tǒng)稱。 例如：若 θ= {a/x,f(b)/y,c/z},G=P(x,y,z) G θ= P(a,f(b),c) 2022/8/17 69 (4) 定義 8 設 θ＝ {t1/x1, t2/x2, …, t n/xn}， λ＝ {u1/y1, u2/y2, …, u n/yn}是兩個替換，則將 {t1 λ /x1, t2 λ /x2, …, t n λ /xn ， u1/y1, u2/y2, …, u n/yn} 中符合下列條件的元素刪除 （ 1） ti λ /xi 當 ti λ ＝ xi （ 2） ui/yi 當 yi ∈ {x1,…, x n} 這樣得到的集合為 θ 與 λ 的 復合 或 乘積 ，記為 θ ?λ 。 一個公式集的 MGU也是不唯一的。 解 k＝ 0； S0＝ S， σ0＝ ε， D0＝ {a,z} σ1＝ σ0{a/z, h(a,u) /x} = {P(a, h(a,u) ,f(g(y))), P(a,h(a,u),f(u))} k＝ 2； D2＝ {g(y),u} σ3＝ {a/z ,h(a,u) /x ,g(y),u} S3= S2 2022/8/17 76 (11) 定理 3 (合一定理 ) S是非空有限可合一的公式集， 則合一算法總在 Step2停止，且最后的 σk 一定是 S的最一般合一（ MGU）。｛ ak/bk｝ 2022/8/17 77 (1) 例 ： P(x)?Q(y), 172。 P(a)∨ R(y)，求 C1,C2的歸結(jié)式。 解 由于 C1,C2中都含有變元 x,y，所以需先對其中一個進行改名 , 方可歸結(jié)（歸結(jié)過程是顯然的，故從略）。Q(x), σ={f((y)/x} C σ ＝ P(f(y)) ? 172。 2022/8/17 83 (7) 定理 4 謂詞邏輯中的消解（歸結(jié)）式是它的親本子句 的邏輯結(jié)果。 A1： (?x)(P(x)?(Q(x) ?R(x))) A2 ： (?x)(P(x) ? S(x)) G： (?x)(S(x)?R(x)) 證：利用歸結(jié)反演法，先證明 A1 ? A2 ?172。P(y) ?R(y) (3)P(a) (4)S(a) (5) 172。 R(a) [(4),(5), σ2 ={a/z}] (8)Nil [(6),(7)] 所以 S是不可滿足的，從而 G是 A1和 A2的邏輯結(jié)果 。S(z) ? 172。 L(x):x能識字。L(x)) 已知條件 (3) (?x) (D(x) ? I(x)) (4) (?x) (I(x) ? 172。L(y) （改名） (3) D(a) (4) I(a) (5) 172。 D(a) Nil I(a) 172。 試證明：所有自然數(shù)不是奇數(shù)就是其一半為整數(shù)的數(shù)。 O(x):x是奇數(shù)。G是不可滿足的。N(y) ? I(y) （ 4） 172。I(s(a)) 2022/8/17 91 (1) 例 已知： （ 1）如果 x和 y是同班同學，則 x的老師也是 y的老師。 已知條件可以表示成如下謂詞公式： F1： ?x ?y?z(C(x,y) ? T(z,x) ?T(z,y)) F2: T(Wang,Li) F3: C(Li,Zhang) 2022/8/17 92 (2) 為了得到答案，首先要先證明小張的老師是存在的。T(u,Zhang) 求 F1 ? F2 ? F3? 172。 (1) 172。 172。 172。 172。 ANS（ Wang） [(3),(6) 39。有時就用需求證的目標謂詞。 問：上述人員誰和誰是祖孫關系？ 解 首先定義如下謂詞： G(x,y)表示 x是 y的祖父。 F(y,z) ? G(x,z) (2) F(Lao,Da) (3)F(Da,Xiao) 設求證的公式為： G： ?x ?yG(x,y) (既存在 x和 y,x是 y的祖父 ) 把其否定化為子句形式再析取一個輔助謂詞 GA(u， v) (4) 172。 G(u， v) ? GA(u， v) 對上式進行歸結(jié)： (5) 172。用歸結(jié)原理求誰是老實人，誰是說謊者？ 2022/8/17 101 問題的提出 幾種常用的歸結(jié)策略 歸結(jié)策略的類型 2022/8/17 102 （ 1） ? 研究歸結(jié)原理的目的是實現(xiàn)機器推理 ? 用歸結(jié)原理實現(xiàn)機器推理的一般性算法 Step1 將子句集 S置入 CLAUSES表中； Step2 若空子句 NIL在 CLAUSES中，則歸結(jié)成功，結(jié) 束。 下一輪 歸結(jié)讓新的 CLAUSES表（ S ∪ S1 ）中的子句與 S1中 的子句互相見面進行歸結(jié)，并把產(chǎn)生的歸結(jié)式集合記為 S2，再將 S2并入 CLAUSES中； 2022/8/17 104 （ 3） S：（ 1） P ? Q （ 2） 172。 Q S1：（ 5） Q [(1),(2)] （ 6） P [(1),(3)] （ 7） Q ? 172。 P ? P [(2),(3)] （ 11） 172。 P ? Q [(2),(8)] （ 22） 172。 Q [(3),(7)] （ 27） P ? 172。 Q [(3),(11)] （ 31） 172。 Q [(4),(7)] （ 34） 172。 Q [(4),(9)] （ 36） 172。 ? 控制策略的原則 給出控制策略，以使