【文章內(nèi)容簡(jiǎn)介】 ti 替換，記為 E? ，得到的結(jié)果稱為 E在 ?下的 替換實(shí)例 (Instance)。 Eg： E=P(x,y,g(z)), ?＝ {a / x, f(b) /y ,c /z }， E?= P(a,f(b),g(c)) ? 定義８ 設(shè) ?＝ {t1 / x1, t2 / x2 ,…,t n / xn }， ?＝ {u1 / y1, u2 / y2 ,…,u m / ym }是兩個(gè)替換，則將集合 {t1 ? / x1, t2 ? / x2 ,…,t n ? / xn， u1 / y1, u2 / y2 ,…,u m / ym }中符合下列條件的兩種情形刪除： ? ti ? / xi ，當(dāng) ti ? ＝ xi ? ui / yi ，當(dāng) yi ? { x1, x2 ,…, xn } ＊ 得到的集合仍是一個(gè)替換，稱為 ?與 ?的 復(fù)合 或 乘積 ，記為 ?? 例 : 設(shè) ? ={f(y)/x,z/y} ?={a/x,b/y,y/z} ??={f(b)/x,y/y,a/x,b/y,y/z}={f(b)/x,y/z} 替換與合一 ?定義９ 設(shè) S= { F1, F2 ,…, Fn }是一個(gè)原子謂詞公式集，若存在一個(gè)替換 ?，使得 F1 ?＝ F2 ?＝ … ＝ Fn ?，則稱 ?為 S的一個(gè) 合一 (Unifier)，并稱 S為可合一的。 ? 一個(gè)公式集的合一一般不唯一 ?定義 10 設(shè) ?是公式集 S的一個(gè)合一，如果對(duì) S的任何一個(gè)合一 ?，都存在一個(gè)替換 ?，使得 ?＝ ? ?，則稱 ?為 S的一個(gè) 最一般合一 (Most General Unifier)，簡(jiǎn)稱MGU 設(shè) S={P(u,y,g(y)),P(x,f(u),z)},有 ?={u/x,f(u)/y,g(f(u))/z} 對(duì)其它某個(gè)合一 ,如 ?={a/x,f(a)/y,g(f(a))/z,a/u}，可找到替換 ?={a/u}，使得 ?＝ ? ? 替換與合一 ?定義 11 設(shè) S是一個(gè)非空的具有 相同 謂詞名的原子公式集，從 S中各公式的左邊第一個(gè)項(xiàng)開始，同時(shí)向右比較，每一組不都相同的項(xiàng)的差異部分組成的集合稱為S的 差異集 。 ?公式集 S={P(a,x,f(g(y))) , P(z,h(z,u),f(u))}的差異集為{a,z}, {x,h(z,u)}, {g(y),u } 替換與合一 ?設(shè) S為一非空有限具有相同謂詞名的原子謂詞公式集，求 S的 MGU的算法： ? (1) 令 k=0, Sk=S, ?k= ?（ ? 表示空替換） ? (2) 若 Sk只含有一個(gè)謂詞公式，則算法停止， ?k就是要求的最一般合一 ? (3) 求 Sk的差異集 Dk ? (4) 若 Dk中存在元素 xk 和 tk ，其中 xk是變?cè)? tk是項(xiàng)且 xk不在 tk中出現(xiàn)，則置 Sk+1 = Sk{tk /xk} ， ?k+1 = ?k{tk /xk} ，k=k+1，然后轉(zhuǎn)步 (2) ? (5) 算法停止， S的最一般合一不存在 替換與合一 ?求 S={P(a,x,f(g(y))) , P(z,h(z,u),f(u))}的 MGU ?k=0 ?S0=S, ?0= ? , D0={a,z} ??1= ?0{a/z}={a/z} ?S1=S0{a/z} ={P(a,x,f(g(y))) , P(a,h(a,u),f(u))} ?k=1 ?D1={x,h(a,u)} ??2= ?1{h(a,u)/x}={a/z }{h(a,u)/x}={a/z, h(a,u)/x} ?S2=S1{h(a,u)/x}= {P(a,h(a,u),f(g(y))) , P(a,h(a,u),f(u))} 替換與合一 ?S2=S1{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= ?2{g(y)/u}={a/z, h(a, g(y))/x, g(y)/u} ?S3=S2{g(y)/u}={P(a,h(a,g(y)),f(g(y))), P(a,h(a,g(y)),f(g(y)))} = {P(a,h(a,g(y)),f(g(y)))} ?k=3 ?S3為單元素集，所以 ?3為所求的 S的 MGU 說(shuō)明： MGU可能是不唯一的，如 Dk={xk,yk}時(shí) 謂詞邏輯中的歸結(jié)原理 ?定義 12 設(shè) C1,C2是兩個(gè)沒(méi)有相同變?cè)淖泳洌?L1,L2分別是 C1,C2中的兩個(gè)文字，如果 L1與 ?L2有最一般合一? ，則子句 C12=(C1?{L1?})? (C2?{L2?})，稱作 C1和C2的 二元?dú)w結(jié)式 (二元消解式 )。 C1和 C2稱為 C12的 親本子句 ， L1， L2稱為 消解文字 。 例： C1=P(x)?Q(x) , C2= ? P(a)?R(y), C12=Q(a)?R(y) 說(shuō)明：當(dāng)子句內(nèi)部有可合一的文字時(shí)，應(yīng)在歸結(jié)前進(jìn)行合一，使子句最簡(jiǎn) 例： C1=P(x) ?P(f(a))?Q(x)，則 C1=P(f(a))?Q(x) ?歸結(jié)原理： C1 ? C2 ?(C1?{L1?})? (C2?{L2?}) 謂詞邏輯中的歸結(jié)原理 ?歸結(jié)時(shí)的注意事項(xiàng) ? 謂詞的一致性 . 名稱不一致的謂詞不能歸結(jié) ?? P (x) ， R (x) 不能歸結(jié) ? 常量的一致性 . 含有不同常量的謂詞不能歸結(jié) ?P(a,…) ， ? P(b,…) 不能歸結(jié) ? 變量與函數(shù) ?P(x,x,…) ， P(x,f(x),…) 不能歸結(jié) ?P(x,x,…) ， P(x,f(y),…) 能歸結(jié) ? 不能同時(shí)消去兩個(gè)互補(bǔ)對(duì) ?P ? Q 與 ?P ? ?Q 不能同時(shí)消去 歸結(jié)反演 ?歸結(jié)反演：應(yīng)用歸結(jié)原理證明定理的過(guò)程 ?若 F為已知前提的公式集， Q為結(jié)論，用歸結(jié)反演證明Q為真的步驟是： ? （ 1）、否定 Q，得到 ?Q； ? （ 2）、把 ?Q并入到公式集 F中，得到 {F, ?Q}； ? （ 3）、把公式集 {F, ?Q}化為子句集 S； ? （ 4）、應(yīng)用歸結(jié)原理對(duì)子句集 S中的子句進(jìn)行歸結(jié)，并把每次歸結(jié)得到的歸結(jié)式都并入 S中。如此反復(fù)進(jìn)行，直到出現(xiàn)空子句，就證明了 Q為真。 ?定理 5（歸結(jié)原理的 完備性 ）、如果子句集 S是不可滿足的，則必存在一個(gè)由 S推出空子句的歸結(jié)序列。 歸結(jié)反演舉例 例：自然數(shù)都是大于零的整數(shù)；所有整數(shù)不是偶數(shù)就是奇數(shù)；偶數(shù)除以 2是整數(shù)。求證：所有自然數(shù)不是奇數(shù)就是其一半為整數(shù)的數(shù)。 證明：前提： F1 ： ?x(N(x) ?GZ(x) ?I(x)) N(x)： x是自然數(shù) F2 ： ?x(I(x) ?E(x) ? O(x)) GZ(x)： x0 I(x)： x是整數(shù) F3 ： ?x(E(x) ?I(h(x))) E(x)： x是偶數(shù) O(x)： x是奇數(shù) 結(jié)論： G： ?x(N(x) ?O(x) ? I(h(x))) h(x)： half(x) F F F3 及 ?G 化為子句集： （ 1） ?N(x)?GZ(x) （ 2） ?N(y)?I(y) （ 3） ?I(z)?E(z) ? O(z) （ 4） ?E(u)?I(h(u)) （ 5） N( c) （ 6） ?O(c) （ 7） ?I(h( c)) 歸結(jié)： （ 8） I( c) ( (2), (5), c/y ) （ 9） ?I(c) ? E( c) ( (3), (6), c/z ) （ 10） E( c) ( (8), (9) ) （ 11） I(h( c)) ( (4), (10), c/u ) （ 12） ? ( (7), (11) ) 應(yīng)用歸結(jié)原理求解 ?應(yīng)用歸結(jié)原理求取問(wèn)題答案的步驟 ?把已知前提用謂詞公式表示出來(lái)，并化為子句集 S ?把待求解問(wèn)題也用謂詞公式表示出來(lái)，然后把它的否定與 謂詞 ANS構(gòu)成析取式。 ANS的變?cè)獞?yīng)與問(wèn)題的變?cè)耆恢? ?把此析取式化為子句集，并把該子句集并入 S中得到子句集 S‘ ?對(duì) S‘應(yīng)用歸結(jié)原理進(jìn)行歸結(jié) ?若得到歸結(jié)式 ANS，則答案就在 ANS中 應(yīng)用歸結(jié)原理求解 ? 例：設(shè) A、 B、 C三人中有人從不說(shuō)真話，也有人從不說(shuō)假話，某人向這三人分別提出同一個(gè)問(wèn)題： 誰(shuí)是說(shuō)謊者？ A答：“ B和 C都是說(shuō)謊者”； B答：“ A和 C都是說(shuō)謊者”； C答：“ A和B中至少有一個(gè)是說(shuō)謊者”。問(wèn)：誰(shuí)是老實(shí)人？ 解、設(shè) T(x)表示 x說(shuō)真話。如果 A說(shuō)的是真話，則有： T(A) ? ? T(B) ? ?T(C ) 如果 A說(shuō)的是假話，則有： ?T(A) ?T(B)? T(C )。 同理，對(duì) B和 C有： T(B) ? ? T(A) ??T(C ) ?T(B) ?T(A)? T(C ) T(C) ? ? T(A)? ? T(B ) ? T(C) ? T(A) ?T(B ) 應(yīng)用歸結(jié)原理求解 化為子句集 S： 1) ? T(A)? ? T(B ) 2) ? T(A)? ? T(C ) 3) T(A)?T(B)?T(C ) 4) ? T(B)? ? T(C ) 5) ? T(A)? ? T(B ) ? ? T(C ) 6) T(C)?T(A) 7) T(C)?T(B) 把 ?T(x)? ANS(x)并入 S 8) ?T(x)? ANS(x) 9) T(A)? ANS( C) ( 8, 6, C/x ) 10)T(B)? ANS(C) ( 7, 8, C/x ) 11) ?T(B)? ANS(C) ( 9, 1) 12) ANS(C ) ( 10, 11) 因此 C是老實(shí)人。無(wú)論如何歸結(jié)，推不出 ANS(A), ANS(B) 歸結(jié)策略 ? 歸結(jié)反演的一般過(guò)程。 ? 步 1 將子句集 S置入 CLAUSES表； ? 步 2 若空子句 NIL在 CLAUSES中，則歸結(jié)成功，結(jié)束。 ? 步 3 若 CLAUSES表中存在可歸結(jié)的子句對(duì)，則歸結(jié)之，并將歸結(jié)式并入 CLAUSES表，轉(zhuǎn)步２； ? 步 4 歸結(jié)失敗，退出。 ? 窮舉算法（廣度優(yōu)先策略） ? 第一輪：將原子句集 S中的子句兩兩歸結(jié)，產(chǎn)生的歸結(jié)式集合記為 S1，再將 S1并入 CLAUSES表； ? 第二輪：將新的 CLAUSES表，即 S ? S1中的子句與 S1中的子句兩兩歸結(jié)，產(chǎn)生的歸結(jié)式集合記為 S2，再將 S2并入 CLAUSES； ? 第三輪：將新的 CLAUSES表即 S ? S1 ? S2中的子句與 S2中的子句兩兩歸結(jié)， … 。 ? 如此下去，直到出現(xiàn)空子句。 歸結(jié)策略 例 1 設(shè)有如下的子句集，用窮舉算法歸結(jié)如下： S： （ 1） P?Q （ 2） ? P?Q （ 3） P? ? Q （ 4） ? P? ? Q S1： （ 5） Q [(1), (2)] （ 6） P [(1), (3)] （ 7） Q? ? Q [(1), (4)] （ 8） P? ? P [(1), (4)] （ 9） Q? ? Q [(2), (3)] （ 10） P? ? P [(2), (3)] （ 11） ? P [(2), (4)] （ 12） ? Q [(3), (4)] S2：（ 13） P? Q [(1), (7)] （ 14） P? Q [(1), (8)] 歸結(jié)策略 （ 15） P? Q [(1), (9)] （ 16） P? Q [(1), (10)] （ 17） Q [(1), (11)] （ 18） P