《人工智能原理》第三章歸結推理方法第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述《人工智能原理》第三章歸結推理方法歸結推理命題邏輯謂詞邏輯Skolem標準形、子句集基本概念謂詞邏輯歸結原理合一和置換、控制策略數理邏輯命題邏輯歸結Herbrand定理歸結命題謂詞邏Skolem標準形、基本謂詞邏輯合一和置換、數《人工智能原理》第三章歸結推理方法第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制第三章歸結推理方法概述《人工智能原理》第三章歸結推理方法概述歸結原理由J.A.Robinson由1965年提出。與演繹法(deductiveinference)完全不同，新的邏輯演算(inductiveinference)算法。一階邏輯中，至今為止的最有效的半可判定的算法。即，一階邏輯中任意恒真公式，使用歸結原理，總可以在有限步內給以判定。語義網絡、框架表示、產生式規則等等都是以推理方法為前提的。即，有了規則已知條件，順藤摸瓜找到結果。而歸結方法是自動推理、自動推導證明用的。（“數學定理機器證明”）本課程只討論一階謂詞邏輯描述下的歸結推理方法，不涉及高階謂詞邏輯問題。

概述歸結原理由J.A.Robinson由1965年提出。《人工智能原理》第三章歸結推理方法第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述《人工智能原理》第三章歸結推理方法第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述《人工智能原理》第三章歸結推理方法命題例命題：能判斷真假（不是既真又假）的陳述句。

簡單陳述句描述事實、事物的狀態、關系等性質。例如：1．

1+1=22．

雪是黑色的。3．

北京是中國的首都。4．

到冥王星去渡假。

判斷一個句子是否是命題，有先要看它是否是陳述句，而后看它的真值是否唯一。以上的例子都是陳述句，第4句的真值現在是假，隨著人類科學的發展，有可能變成真，但不管怎樣，真值是唯一的。因此，以上4個例子都是命題。而例如：1．

快點走吧！

2．

到那去？

3．

x+y>10

等等句子，都不是命題。命題例命題：能判斷真假（不是既真又假）的陳述句。《人工智能原理》第三章歸結推理方法命題表示公式（1）將陳述句轉化成命題公式。如：設“下雨”為p，“騎車上班”為q，，1．“只要不下雨，我騎自行車上班”。～p

是q的充分條件， 因而，可得命題公式：～p→q2．“只有不下雨，我才騎自行車上班”。～p

是q的必要條件， 因而，可得命題公式：q→～p命題表示公式（1）將陳述句轉化成命題公式。《人工智能原理》第三章歸結推理方法命題表示公式（2）例如：1．

“如果我進城我就去看你，除非我很累。” 設：p，我進城，q，去看你，r，我很累。 則有命題公式：～r→(p→q)。2．“應屆高中生，得過數學或物理競賽的一等獎， 保送上北京大學。” 設：p，應屆高中生，q，保送上北京大學上學，

r，是得過數學一等獎。t，是得過物理一等獎。 則有命題公式公式：p

∧(r∨t)→

q。

命題表示公式（2）例如：《人工智能原理》第三章歸結推理方法命題邏輯的歸結法命題邏輯基礎：定義：合取式：p與q，記做pΛ

q析取式：

p或q，記做p∨

q蘊含式：如果p則q，記做p→

q等價式：p當且僅當q，記做p<=>

q

。。。。。。命題邏輯的歸結法命題邏輯基礎：《人工智能原理》第三章歸結推理方法命題邏輯基礎定義：若A無成假賦值，則稱A為重言式或永真式；若A無成真賦值，則稱A為矛盾式或永假式；若A至少有一個成真賦值，則稱A為可滿足的；析取范式：僅由有限個簡單合取式組成的析取式。合取范式：僅由有限個簡單析取式組成的合取式。命題邏輯基礎定義：《人工智能原理》第三章歸結推理方法命題邏輯基礎基本等值式24個(1)交換率：p∨q<=>q

∨p

；

pΛq<=>qΛp

結合率：(p∨q)∨

r<=>p∨(q∨r); (pΛq)Λ

r<=>pΛ(qΛr)分配率：p∨(qΛ

r)<=>(p∨q)Λ(p∨r)

；

pΛ(q∨

r)<=>(pΛq)∨(pΛr)

命題邏輯基礎基本等值式24個(1)《人工智能原理》第三章歸結推理方法命題邏輯基礎基本等值式（1）摩根率:～

(p∨q)

<=>～

pΛ

～

q

；

～

(pΛq)

<=>～

p∨

～

q

吸收率:p∨(pΛq)<=>p

；

pΛ(p∨q)<=>p

同一律:p∨0

<=>p

；

pΛ1

<=>p

蘊含等值式:p→

q

<=>～

p∨q

假言易位式:p→

q

<=>～p→～

q

命題邏輯基礎基本等值式（1）《人工智能原理》第三章歸結推理方法命題邏輯的歸結法基本單元：簡單命題（陳述句）例：

命題：A1、A2、A3

和B求證：A1ΛA2ΛA3成立，則B成立，即：A1ΛA2ΛA3→B反證法：證明A1ΛA2ΛA3Λ～B是矛盾式（永假式）

命題邏輯的歸結法基本單元：簡單命題（陳述句）《人工智能原理》第三章歸結推理方法命題邏輯的歸結法建立子句集合取范式：命題、命題和的與，如：

PΛ（P∨Q）Λ（～P∨Q）子句集S：合取范式形式下的子命題（元素）的集合例：命題公式：PΛ（P∨Q）Λ（～P∨Q）子句集S：S={P,P∨Q,～P∨Q}

命題邏輯的歸結法建立子句集《人工智能原理》第三章歸結推理方法命題邏輯的歸結法歸結式消除互補對，求新子句→得到歸結式。如子句：C1,C2， 歸結式：R(C1,C2)=C1ΛC2

注意：C1ΛC2→R(C1,C2)

，反之不一定成立。命題邏輯的歸結法歸結式《人工智能原理》第三章歸結推理方法命題邏輯的歸結法歸結過程

將命題寫成合取范式求出子句集對子句集使用歸結推理規則歸結式作為新子句參加歸結歸結式為空子句□，S是不可滿足的（矛盾），原命題成立。?（證明完畢）謂詞的歸結：除了有量詞和函數以外，其余和命題歸結過程一樣。命題邏輯的歸結法歸結過程《人工智能原理》第三章歸結推理方法命題邏輯歸結例題（1）例題，證明公式：(P→Q)→(～Q→～P)證明：（1）根據歸結原理，將待證明公式轉化成待歸結命題公式：

(P→Q)∧～(～Q→～P)（2）分別將公式前項化為合取范式：

P→Q＝～P∨Q

結論求～后的后項化為合取范式： ～(～Q→～P)＝～(Q∨～P)＝～Q∧P

兩項合并后化為合取范式： （～P∨Q）∧～Q∧P

（3）則子句集為：

{～P∨Q，～Q，P}命題邏輯歸結例題（1）例題，證明公式：(P→Q)→(《人工智能原理》第三章歸結推理方法命題邏輯歸結例題（2）子句集為： {～P∨Q，～Q，P}（4）對子句集中的子句進行歸結可得：1.

～P∨Q2.

～Q3.

P4.

Q， （1，3歸結）5.

， （2，4歸結）

由上可得原公式成立。命題邏輯歸結例題（2）子句集為： {～P∨Q，～Q，P}《人工智能原理》第三章歸結推理方法第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述《人工智能原理》第三章歸結推理方法第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述《人工智能原理》第三章歸結推理方法謂詞歸結原理基礎一階邏輯基本概念個體詞：表示主語的詞謂詞：刻畫個體性質或個體之間關系的詞量詞：表示數量的詞謂詞歸結原理基礎一階邏輯《人工智能原理》第三章歸結推理方法謂詞歸結原理基礎

小王是個工程師。

8是個自然數。 我去買花。 小麗和小華是朋友。其中，“小王”、“工程師”、“我”、“花”、“8”、“小麗”、“小華”都是個體詞，而“是個工程師”、“是個自然數”、“去買”、“是朋友”都是謂詞。顯然前兩個謂詞表示的是事物的性質，第三個謂詞“去買”表示的一個動作也表示了主、賓兩個個體詞的關系，最后一個謂詞“是朋友”表示兩個個體詞之間的關系。謂詞歸結原理基礎 小王是個工程師。《人工智能原理》第三章歸結推理方法謂詞歸結原理基礎一階邏輯公式及其解釋個體常量：a,b,c個體變量：x,y,z謂詞符號：P,Q,R量詞符號：

,謂詞歸結原理基礎一階邏輯《人工智能原理》第三章歸結推理方法謂詞歸結原理基礎例如：（1）所有的人都是要死的。（2）

有的人活到一百歲以上。在個體域D為人類集合時，可符號化為：（1）xP(x)，其中P(x)表示x是要死的。（2）xQ(x),其中Q(x)表示x活到一百歲以上。在個體域D是全總個體域時，引入特殊謂詞R(x)表示x是人，可符號化為：（1）x（R(x)→P(x)）,

其中，R(x)表示x是人；P(x)表示x是要死的。（2）x（R(x)∧Q(x)）， 其中，R(x)表示x是人；Q(x)表示x活到一百歲以上。

謂詞歸結原理基礎例如：（1）所有的人都是要死的。《人工智能原理》第三章歸結推理方法謂詞歸結原理基礎量詞否定等值式：～(x

）

M（x）<=>（

y

）～

M（y）～(x

）

M（x）<=>（

y

）～

M（y）量詞分配等值式：(x

）(

P（x）ΛQ（x）)<=>(x

）

P（x）Λ(x

）

Q（x）(x

）(

P（x）∨

Q（x）)<=>(x

）

P（x）∨

(x

）

Q（x）消去量詞等值式：設個體域為有窮集合（a1,a2,…an）(x

）

P（x）<=>P（a1

）ΛP（a2

）Λ…ΛP（an

）(x

）P（x）<=>P（a1

）∨

P（a2

）∨

…

∨

P（an

）謂詞歸結原理基礎量詞否定等值式：《人工智能原理》第三章歸結推理方法謂詞歸結原理基礎量詞轄域收縮與擴張等值式：(x

）(

P（x）∨Q)<=>(x

）

P（x）∨Q(x

）(

P（x）ΛQ)<=>(x

）

P（x）ΛQ

(x

）(

P（x）→Q)<=>(x

）

P（x）→Q

(x

）(Q

→P（x）)<=>Q

→(x

）

P（x）(x

）(

P（x）∨Q)<=>(x

）

P（x）∨Q(x

）(

P（x）ΛQ)<=>(x

）

P（x）ΛQ

(x

）(

P（x）→Q)<=>(x

）

P（x）→Q

(x

）(Q

→P（x）)<=>Q

→(x

）

P（x）謂詞歸結原理基礎量詞轄域收縮與擴張等值式：《人工智能原理》第三章歸結推理方法謂詞歸結子句形(Skolem標準形)SKOLEM標準形前束范式

定義：說公式A是一個前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。謂詞歸結子句形(Skolem標準形)SKOLEM標準形《人工智能原理》第三章歸結推理方法謂詞歸結子句形(Skolem標準形)即：把所有的量詞都提到前面去，然后消掉所有量詞

(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)約束變項換名規則：(Qx

）

M（x）<=>（Qy

）

M（y）(Qx

）

M（x,z）<=>（Qy

）

M（y,z）謂詞歸結子句形(Skolem標準形)即：把所有的量詞都《人工智能原理》第三章歸結推理方法謂詞歸結子句形(Skolem標準形)

量詞消去原則： 消去存在量詞“”，略去全程量詞“”。 注意：左邊有全程量詞的存在量詞，消去時該變量改寫成為全程量詞的函數；如沒有，改寫成為常量。

謂詞歸結子句形(Skolem標準形) 《人工智能原理》第三章歸結推理方法謂詞歸結子句形(Skolem標準形)Skolem定理： 謂詞邏輯的任意公式都可以化為與之等價的前束范式，但其前束范式不唯一。SKOLEM標準形定義： 消去量詞后的謂詞公式。注意：謂詞公式G的SKOLEM標準形同G并不等值。謂詞歸結子句形(Skolem標準形)《人工智能原理》第三章歸結推理方法謂詞歸結子句形(Skolem標準形)例:將下式化為Skolem標準形： ～(x)(y)P(a,x,y)→(x)(～(y)Q(y,b)→R(x))解：第一步，消去→號，得： ～(～(x)(y)P(a,x,y))∨(x)(～～(y)Q(y,b)∨R(x))第二步，～深入到量詞內部，得：

(x)(y)P(a,x,y)∨(x)((y)Q(y,b)∨R(x))第三步，變元易名，得

(x)((y)P(a,x,y)∨(u)(v)(Q(v,b)∨R(u))第四步，存在量詞左移，直至所有的量詞移到前面，得：

(x)(y)(u)(v)P(a,x,y)∨(Q(v,b)∨R(u))由此得到前述范式謂詞歸結子句形(Skolem標準形)《人工智能原理》第三章歸結推理方法謂詞歸結子句形(Skolem標準形)

第五步，消去“”（存在量詞），略去“”全稱量詞 消去(y)，因為它左邊只有(x)，所以使用x的函數f(x)代替之，這樣得到：

(x)(z)(P(a,x,f(x))∧～Q(z,b)∧～R(x))

消去(z)，同理使用g(x)代替之，這樣得到：

(x)(P(a,x,f(x))∧～Q(g(x),b)∧～R(x))

則，略去全稱變量，原式的Skolem標準形為：

P(a,x,f(x))∧～Q(g(x),b)∧～R(x)

謂詞歸結子句形(Skolem標準形) 第五步，消去“”《人工智能原理》第三章歸結推理方法謂詞歸結子句形子句與子句集文字：不含任何連接詞的謂詞公式。子句：一些文字的析取（謂詞的和）。子句集S的求取：

G→SKOLEM標準形 →消去存在變量 →以“，”取代“Λ”，并表示為集合形式。謂詞歸結子句形子句與子句集《人工智能原理》第三章歸結推理方法謂詞歸結子句形

G是不可滿足的<=>S是不可滿足的G與S不等價，但在不可滿足得意義下是一致的。

定理： 若G是給定的公式，而S是相應的子句集，則G是不可滿足的<=>S是不可滿足的。

注意：G真不一定S真，而S真必有G真。 即：S=>G謂詞歸結子句形G是不可滿足的<=>S是不可滿足的《人工智能原理》第三章歸結推理方法謂詞歸結子句形G=G1ΛG2ΛG3Λ…ΛGn

的子句形G的字句集可以分解成幾個單獨處理。

有SG=S1US2US3U…USn

則SG

與S1US2US3U…USn在不可滿足得意義上是一致的。 即SG

不可滿足<=>S1US2US3U…USn不可滿足謂詞歸結子句形G=G1ΛG2ΛG3Λ…ΛGn的《人工智能原理》第三章歸結推理方法求取子句集例(1)例：對所有的x,y,z來說，如果y是x的父親，z又是y的父親，則z是x的祖父。又知每個人都有父親，試問對某個人來說誰是它的祖父？求：用一階邏輯表示這個問題，并建立子句集。解：這里我們首先引入謂詞：

P(x,y)表示x是y的父親

Q(x,y)表示x是y的祖父

ANS(x)表示問題的解答求取子句集例(1)例：對所有的x,y,z來說，如果y是x的父《人工智能原理》第三章歸結推理方法求取子句集例(2)對于第一個條件，“如果x是y的父親，y又是z的父親，則x是z的祖父”，一階邏輯表達式如下：

A1：(x)(y)(z)(P(x,y)∧P(y,z)→Q(x,z)) SA1：～P(x,y)∨～P(y,z)∨Q(x,z)對于第二個條件：“每個人都有父親”，一階邏輯表達式：

A2：(y)(x)P(x,y) SA2：P(f(y),y)對于結論：某個人是它的祖父

B：(x)(y)Q(x,y)

否定后得到子句：～（(x)(y)Q(x,y)）∨ANS(x) S～B：～Q(x,y)∨ANS(x)則得到的相應的子句集為：{SA1，SA2，S～B}求取子句集例(2)對于第一個條件，“如果x是y的父親，y《人工智能原理》第三章歸結推理方法第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述《人工智能原理》第三章歸結推理方法第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述《人工智能原理》第三章歸結推理方法歸結原理歸結原理正確性的根本在于，找到矛盾可以肯定不真。方法：和命題邏輯一樣。但由于有函數，所以要考慮合一和置換。

歸結原理歸結原理正確性的根本在于，找到矛盾可以肯定不真。《人工智能原理》第三章歸結推理方法置換置換：可以簡單的理解為是在一個謂詞公式中用置換項去置換變量。定義： 置換是形如{t1/x1,t2/x2,…,tn/xn}的有限集合。其中，x1,x2,…,xn是互不相同的變量，t1,t2,…,tn是不同于xi的項（常量、變量、函數）；ti/xi表示用ti置換xi，并且要求ti與xi不能相同，而且xi不能循環地出現在另一個ti中。例如

{a/x，c/y，f(b)/z}是一個置換。

{g(y)/x，f(x)/y}不是一個置換，

置換置換：可以簡單的理解為是在一個謂詞公式中用置換項去置換變《人工智能原理》第三章歸結推理方法置換的合成設＝{t1/x1,t2/x2,…,tn/xn}， ＝{u1/y1,u2/y2,…,un/yn}，是兩個置換。 則與的合成也是一個置換，記作·。它是從集合

{t1·/x1,t2·/x2,…,tn·/xn,u1/y1,u2/y2,…,un/yn}

中刪去以下兩種元素：當ti=xi時，刪去ti/xi(i=1,2,…,n);

當yi{x1,x2,…,xn}時，刪去uj/yj(j=1,2,…,m)

最后剩下的元素所構成的集合。合成即是對ti先做置換然后再做置換，置換xi置換的合成設＝{t1/x1,t2/x2,…,tn/x《人工智能原理》第三章歸結推理方法置換的合成例：設：＝{f(y)/x,z/y}，＝{a/x,b/y,y/z}，求與的合成。解：先求出集合

{f(b/y)/x,(y/z)/y,a/x,b/y,y/z}＝{f(b)/x,y/y,a/x,b/y,y/z}

其中，f(b)/x中的f(b)是置換作用于f(y)的結果；y/y中的y是置換作用于z的結果。在該集合中，y/y滿足定義中的條件i，需要刪除；a/x，b/y滿足定義中的條件ii，也需要刪除。最后得

·＝{f(b)/x，y/z}置換的合成例：《人工智能原理》第三章歸結推理方法合一合一可以簡單地理解為“尋找相對變量的置換，使兩個謂詞公式一致”。定義：設有公式集F＝{F1，F2，…，Fn}，若存在一個置換，可使F1＝F2＝…=Fn，則稱是F的一個合一。同時稱F1，F2，...，Fn是可合一的。

例： 設有公式集F＝{P(x,y,f(y)),P(a,g(x),z)}，則＝{a/x,g(a)/y,f(g(a))/z}是它的一個合一。注意：一般說來，一個公式集的合一不是唯一的。

合一合一可以簡單地理解為“尋找相對變量的置換，使兩個謂詞公式《人工智能原理》第三章歸結推理方法歸結原理歸結的注意事項：謂詞的一致性，P()與Q()，不可以常量的一致性，P(a,…)與P(b,….)，不可以 變量，P(a,….)與P(x,…)，可以變量與函數，P(a,x,….)與P(x,f(x),…)，不可以；是不能同時消去兩個互補對，P∨Q與～P∨～Q的空，不可以先進行內部簡化（置換、合并）

歸結原理歸結的注意事項：《人工智能原理》第三章歸結推理方法歸結原理歸結的過程寫出謂詞關系公式→用反演法寫出謂詞表達式→SKOLEM標準形→子句集S→對S中可歸結的子句做歸結→歸結式仍放入S中，反復歸結過程→得到空子句

?得證歸結原理歸結的過程《人工智能原理》第三章歸結推理方法例題“快樂學生”問題假設任何通過計算機考試并獲獎的人都是快樂的，任何肯學習或幸運的人都可以通過所有的考試，張不肯學習但他是幸運的，任何幸運的人都能獲獎。求證：張是快樂的。

解：先將問題用謂詞表示如下：R1:“任何通過計算機考試并獲獎的人都是快樂的”

(x)((Pass(x,computer)∧Win(x,prize))→Happy(x))R2:“任何肯學習或幸運的人都可以通過所有考試”

(x)(y)(Study(x)∨Lucky(x)→Pass(x,y))R3:“張不肯學習但他是幸運的” ～Study(zhang)∧Lucky(zhang)R4:“任何幸運的人都能獲獎”

(x)(Luck(x)→Win(x,prize))結論：“張是快樂的”的否定～Happy(zhang)例題“快樂學生”問題假設任何通過計算機考試并獲獎的人都是快樂《人工智能原理》第三章歸結推理方法例題“快樂學生”問題由R1及邏輯轉換公式:P∧W→H=～（P∧W）∨H，可得

(1)～Pass(x,computer)∨～Win(x,prize)∨Happy(x)由R2：(2)～Study(y)∨Pass(y,z)(3)～Lucky(u)∨Pass(u,v)由R3：(4)～Study(zhang)(5)Lucky(zhang)由R4：(6)～Lucky(w)∨Win(w，prize)由結論：(7)～Happy(zhang) （結論的否定）(8)～Pass(w,computer)∨Happy(w)∨～Luck(w)(1)(6)，{w/x}(9)～Pass(zhang,computer)∨～Lucky(zhang)(8)(7)，{zhang/w}(10)

～Pass(zhang,computer) (9)(5)(11)

～Lucky(zhang) (10)(3)，{zhang/u,computer/v}(12)

?

(11)(5)

例題“快樂學生”問題由R1及邏輯轉換公式:P∧W→H=～《人工智能原理》第三章歸結推理方法歸結原理歸結法的實質：歸結法是僅有一條推理規則的推理方法。歸結的過程是一個語義樹倒塌的過程。歸結法的問題子句中有等號或不等號時，完備性不成立。※Herbrand定理的不實用性引出了可實用的歸結法。歸結原理歸結法的實質：《人工智能原理》第三章歸結推理方法第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述《人工智能原理》第三章歸結推理方法第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述《人工智能原理》第三章歸結推理方法歸結過程的控制策略要解決的問題：歸結方法的知識爆炸。控制策略的目的歸結點盡量少控制策略的原則給出控制策略，以使僅對選擇合適的子句間方可做歸結。避免多余的、不必要的歸結式出現。或者說，少做些歸結仍能導出空子句。歸結過程的控制策略要解決的問題：《人工智能原理》第三章歸結推理方法控制策略的方法(1)

刪除策略 => 完備名詞解釋：歸類：設有兩個子句C和D，若有置換使得C

D成立，則稱子句C把子句D歸類。 由于小的可以代表大的，所以小的吃掉大的了。若對S使用歸結推理過程中，當歸結式Cj是重言式（永真式）和Cj被S中子句和子句集的歸結式Ci(i<j)所歸類時，便將Cj刪除。這樣的推理過程便稱做使用了刪除策略的歸結過程。主要思想：歸結過程在尋找可歸結子句時，子句集中的子句越多，需要付出的代價就會越大。如果在歸結時能把子句集中無用的子句刪除掉，就會縮小搜索范圍，減少比較次數，從而提高歸結效率。刪除策略對阻止不必要的歸結式的產生來縮短歸結過程是有效的。然而要在歸結式Cj產生后方能判別它是否可被刪除，這部分計算量是要花費的，只是節省了被刪除的子句又生成的歸結式。盡管使用刪除策略的歸結，少做了歸結但不影響產生空子句，就是說刪除策略的歸結推理是完備的。控制策略的方法(1) 刪除策略 => 完備《人工智能原理》第三章歸結推理方法控制策略的方法(2)采用支撐集 <=>完備

支撐集：設有不可滿足子句集S的子集T，如果S-T是可滿足的，則T是支持集。

采用支撐集策略時，從開始到得到的整個歸結過程中，只選取不同時屬于S-T的子句，在其間進行歸結。就是說，至少有一個子句來自于支撐集T或由T導出的歸結式。

例如：A1ΛA2ΛA3Λ～B中的～B可以作為支撐集使用。要求每一次參加歸結的親本子句中，只要應該有一個是有目標公式的否定（～B）所得到的子句或者它們的后裔。支撐集策略的歸結是完備的，同樣，所有可歸結的謂詞公式都可以用采用支撐集策略達到加快歸結速度的目的。問題是如何尋找合適的支撐集。一個最容易找到的支撐集是目標子句的非，即S～B。

控制策略的方法(2)采用支撐集 <=>完備《人工智能原理》第三章歸結推理方法ST可滿足支撐集示意圖ST可滿足支撐集示意圖《人工智能原理》第三章歸結推理方法控制策略的方法(3)

語義歸結 <=> 完備

語義歸結策略是將子句S按照一定的語義分成兩部分，約定每部分內的子句間不允許作歸結。同時還引入了文字次序，約定歸結時其中的一個子句的被歸結文字只能是該子句中“最大”的文字。 語義歸結策略的歸結是完備的，同樣，所有可歸結的謂詞公式都可以用采用語義歸結策略達到加快歸結速度的目的。問題是如何尋找合適的語義分類方法，并根據其含義將子句集兩個部分中的子句進行排序。

控制策略的方法(3) 語義歸結 <=> 完備《人工智能原理》第三章歸結推理方法控制策略的方法(4)

線性歸結 <=>完備線性歸結策略首先從子句集中選取一個稱作頂子句的子句C0開始作歸結。歸結過程中所得到的歸結式Ci立即同另一子句Bi進行歸結得歸結式Ci+1。而Bi屬于S或是已出現的歸結式Cj(j<i)。即，如下圖所示歸結得到的新子句立即參加歸結。線性歸結是完備的，同樣，所有可歸結的謂詞公式都可以采用線性歸結策略達到加快歸結速度的目的。如果能搞找到一個較好的頂子句，可以式歸結順利進行。否則也可能事與愿違。

控制策略的方法(4) 線性歸結 <=>完備《人工智能原理》第三章歸結推理方法C0C1C2C3C4C5空線性歸結策略示意圖C0C1C2C3C4C5空線性歸結策略示意圖《人工智能原理》第三章歸結推理方法控制策略的方法(5)

單元歸結 => 完備

單元歸結策略要求在歸結過程中，每次歸結都有一個子句是單元子句（只含一個文字的子句）或單元因子。顯而易見，詞中方法可以簡單地削去另一個非單子句中的一個因子，使其長度減少，構成簡單化，歸結效率較高。初始子句集中沒有單元子句時，單元歸結策略無效。所以說“反之不成立”，即此問題不能采用單元歸結策略。

控制策略的方法(5) 單元歸結 => 完備《人工智能原理》第三章歸結推理方法控制策略的方法(6)

輸入歸結 => 完備

與單元歸結策略相似，輸入歸結策略要求在歸結過程中，每一次歸結的兩個子句中必須有一個是S的原始子句。這樣可以避免歸結出的不必要的新子句加入歸結，造成惡性循環。可以減少不必要的歸結次數。如同單元歸結策略，不是所有的可歸結謂詞公式的最后結論都是可以從原始子句集中的得到的。簡單的例子，歸結結束時，即最后一個歸結式為空子句的條件是，參加歸結的雙方必須是兩個單元子句。原始子句集中沒有單元子句的謂詞公式一定不能采用輸入歸結策略。

控制策略的方法(6) 輸入歸結 => 完備《人工智能原理》第三章歸結推理方法第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述《人工智能原理》第三章歸結推理方法第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述《人工智能原理》第三章歸結推理方法Herbrand定理問題： 一階邏輯公式的永真性（永假性）的判定是否能在有限步內完成？Herbrand定理問題：《人工智能原理》第三章歸結推理方法Herbrand定理1936年圖靈(Turing)和邱吉(Church)互相獨立地證明了：

“沒有一般的方法使得在有限步內判定一階邏輯的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步內判定它是永真（或永假）。對于非永真（或永假）的公式就不一定能在有限步內得到結論。判定的過程將可能是不停止的。”

Herbrand定理1936年圖靈(Turing)和邱吉(C《人工智能原理》第三章歸結推理方法Herbrand定理Herbrand的思想定義： 公式G永真：對于G的所有解釋，G都為真。思想：

尋找一個已給的公式是真的解釋。然而，如果所給定的公式的確是永假的，就沒有這樣的解釋存在，并且算法在有限步內停止。Herbrand定理Herbrand的思想《人工智能原理》第三章歸結推理方法Herbrand定理H域H解釋語義樹結論：Herbrand定理Herbrand定理H域《人工智能原理》第三章歸結推理方法Herbrand定理H域H解釋語義樹結論：Herbrand定理Herbrand定理H域《人工智能原理》第三章歸結推理方法Herbrand定理（H域）基本方法：因為量詞是任意的，所討論的個體變量域D是任意的，所以解釋的個數是無限、不可數的。簡化討論域。建立一個比較簡單、特殊的域，使得只要在這個論域上，該公式是不可滿足的。此域稱為H域。

Herbrand定理（H域）基本方法：《人工智能原理》第三章歸結推理方法D域H域H域與D域關系示意圖D域H域H域與D域關系示意圖《人工智能原理》第三章歸結推理方法H域例題設子句集S={P(x),Q(y,f(z,b)),R(a)}，求H域解：H0

＝{a,b}為子句集中出現的常量H1

＝{a,b,f(a,b),f(a,a),f(b,a),f(b,b)}H2

＝{a,b,f(a,b),f(a,a),f(b,a),f(b,b)，f(a,f(a,b)),f(a,f(a,a)),f(a,f(b,a)),f(a,f(b,b)),f(b,f(a,b)),f(b,f(a,a)),f(b,f(b,a)),f(b,f(b,b)),f(f(a,b),f(a,b)),f(f(a,b),f(a,a)),f(f(a,b),f(b,a)),f(f(a,b),f(b,b)),f(f(a,a),f(a,b)),f(f(a,a),f(a,a)),f(f(a,a),f(b,a)),f(f(a,a),f(b,b)),f(f(b,a),f(a,b)),f(f(b,a),f(a,a)),f(f(b,a),f(b,a)),f(f(b,a),f(b,b)),f(f(b,b),f(a,b)),f(f(b,b),f(a,a)),f(f(b,b),f(b,a)),f(f(b,b),f(b,b))}

……… H∞=H1∪H2∪H3………H域例題設子句集S={P(x),Q(y,f(z,b)《人工智能原理》第三章歸結推理方法Herbrand定理（H域）幾個基本概念f（tn）：f為子句集S中的所有函數變量。t1,t2,…tn為S的H域的元素。通過它們來討論永真性。原子集A：謂詞套上H域的元素組成的集合。如

A={所有形如P(t1,t2,…tn)的元素}

即把H中的東西填到S的謂詞里去。S中的謂詞是有限的，H是可數的，因此，A也是可數的。Herbrand定理（H域）幾個基本概念《人工智能原理》第三章歸結推理方法原子集例題上例題的原子集為：A={

P(a),Q(a,a),R(a),P(b),Q(b,a), Q(b,b),Q(a,b),R(b),P(f(a,b)),Q(f(a,b),f(a,b)),R(f(a,b),P(f(a,a)),P(f(b,a)),P(f(b,b)),……)

一旦原子集內真值確定好（規定好），則S在H上的真值可確定。成為可數問題。原子集例題上例題的原子集為：《人工智能原理》第三章歸結推理方法Herbrand定理H域H解釋語義樹結論：Herbrand定理Herbrand定理H域《人工智能原理》第三章歸結推理方法Herbrand定理H域H解釋語義樹結論：Herbrand定理Herbrand定理H域《人工智能原理》第三章歸結推理方法Herbrand定理（H解釋）解釋I：謂詞公式G在論域D上任何一組真值的指定稱為一個解釋。H解釋：子句集S在的H域上的解釋稱為H解釋。

問題：對于所有的解釋，全是假才可判定。因為所有解釋代表了所有的情況，如可窮舉，問題便可解決。Herbrand定理（H解釋）解釋I：謂詞公式G在論域D上任《人工智能原理》第三章歸結推理方法Herbrand定理（H解釋）如下三個定理保證了歸結法的正確性：定理1：

設I是S的論域D上的解釋，存在對應于I的H解釋I*，使得若有S|I=T，必有S|I*=T。定理2： 子句集S是不可滿足的，當且僅當所有的S的H解釋下為假。定理3： 子句集S是不可滿足的，當且僅當對每一個解釋I下，至少有S的某個子句的某個基例為假。Herbrand定理（H解釋）如下三個定理保證了歸結法的正確《人工智能原理》第三章歸結推理方法Herbrand定理（H解釋）基例S中某子句中所有變元符號均以S的H域中的元素代入時，所得的基子句C’稱為C的一個基例。若一個子句為假，則此解釋為假。一般來說，D是無窮不可列的，因此，子句集S也是無窮不可列的。但S確定后H是無窮可列的。不過在H上證明S的不可滿足性仍然是不可能的。解決問題的方法：語義樹Herbrand定理（H解釋）基例《人工智能原理》第三章歸結推理方法Herbrand定理H域H解釋語義樹結論：Herbrand定理Herbrand定理H域《人工智能原理》第三章歸結推理方法Herbrand定理H域H解釋語義樹結論：Herbrand定理Herbrand定理H域《人工智能原理》第三章歸結推理方法Herbrand定理（語義樹）構成方法原子集中所有元素逐層添加的一棵二叉樹。將元素的是與非分別標記在兩側的分枝上（可不完全畫完）。特點一般情況H是可數集，S的語義樹是無限樹。Herbrand定理（語義樹）構成方法《人工智能原理》第三章歸結推理方法N0P(a)N12Q(a)P(f(a))N24N31N38無限語義樹N11~P(a)~Q(a)Q(a)~Q(a)~P(f(a))N21S＝{～P(x)∨Q(x)，P(f(y))，～Q(f(y))}

N0P(a)N12Q(a)P(f(a))N24N31N38無《人工智能原理》第三章歸結推理方法Herbrand定理（語義樹）意義SHA語義樹可以理解語義樹為H域的圖形解釋。目的：把每個解釋都攤開。語義樹中包含原子集的全部元素。因此，語義樹是完全的。每一個直到葉子節點的分支對應S的一個解釋。可以通過對語義樹每一個分支來計算S的真值。如果每個基例都為假，則可認為是不可滿足的。Herbrand定理（語義樹）意義《人工智能原理》第三章歸結推理方法Herbrand定理（語義樹）幾個概念失敗結點： 當（由上）延伸到點N時，I(N)已表明了S的某子句的某基例假。但N以前尚不能判斷這事實。就稱N為失敗結點。

封閉語義樹： 如果S的完全語義樹的每個分枝上都有一個失敗結點，就稱它是一棵封閉語義樹。Herbrand定理（語義樹）幾個概念《人工智能原理》第三章歸結推理方法N0P(a)N1,2Q(a)P(f(a))N2,4N3,1N3,8N1,1N4,2N4,1N2,1N3,2N2,2N3,6N4,9N4,10N4,13N4,14封閉語義樹Q(f(a))S＝{～P(x)∨Q(x)，P(f(y))，～Q(f(y))}

N0P(a)N1,2Q(a)P(f(a))N2,4N3,1N《人工智能原理》第三章歸結推理方法Herbrand定理H域H解釋語義樹結論：Herbrand定理Herbrand定理H域《人工智能原理》第三章歸結推理方法Herbrand定理H域H解釋語義樹結論：Herbrand定理Herbrand定理H域《人工智能原理》第三章歸結推理方法Herbrand定理（結論）Herbrand定理：子句集S是不可滿足的，當且僅當對應于S的完全語義數是棵有限封閉樹。

子句集S是不可滿足的，當且僅當存在不可滿足的S的有限基例集。

Herbrand定理（結論）Herbrand定理：《人工智能原理》第三章歸結推理方法Herbrand定理（結論）定理的意義Herbrand定理已將證明問題轉化成了命題邏輯問題。由此定理保證，可以放心的用機器來實現自動推理了。（歸結原理）注意Herbrand定理給出了一階邏輯的半可判定算法，即僅當被證明定理是成立時，使用該算法可以在有限步得證。而當被證定理并不成立時，使用該算法得不出任何結論。但是

Herbrand定理（結論）定理的意義《人工智能原理》第三章歸結推理方法Herbrand定理（結論）仍存在的問題：基例集序列元素的數目隨子句基的元素數目成指數地增加。因此，Herbrand定理是30年代提出的，始終沒有顯著的成績。直至1965年Robinson提出了歸結原理。Herbrand定理（結論）仍存在的問題：《人工智能原理》第三章歸結推理方法歸結原理與Herbrand定理歸結原理是語義樹的一個倒塌過程最后歸結出空，就是剩一個根節點，就說明語義樹是有限封閉的，證明結束。歸結原理與Herbrand定理歸結原理是語義樹的一個倒塌過程《人工智能原理》第三章歸結推理方法第三章歸結推理方法

TheEnd.第三章歸結推理方法《人工智能原理》第三章歸結推理方法第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述《人工智能原理》第三章歸結推理方法歸結推理命題邏輯謂詞邏輯Skolem標準形、子句集基本概念謂詞邏輯歸結原理合一和置換、控制策略數理邏輯命題邏輯歸結Herbrand定理歸結命題謂詞邏Skolem標準形、基本謂詞邏輯合一和置換、數《人工智能原理》第三章歸結推理方法第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制第三章歸結推理方法概述《人工智能原理》第三章歸結推理方法概述歸結原理由J.A.Robinson由1965年提出。與演繹法(deductiveinference)完全不同，新的邏輯演算(inductiveinference)算法。一階邏輯中，至今為止的最有效的半可判定的算法。即，一階邏輯中任意恒真公式，使用歸結原理，總可以在有限步內給以判定。語義網絡、框架表示、產生式規則等等都是以推理方法為前提的。即，有了規則已知條件，順藤摸瓜找到結果。而歸結方法是自動推理、自動推導證明用的。（“數學定理機器證明”）本課程只討論一階謂詞邏輯描述下的歸結推理方法，不涉及高階謂詞邏輯問題。

概述歸結原理由J.A.Robinson由1965年提出。《人工智能原理》第三章歸結推理方法第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述《人工智能原理》第三章歸結推理方法第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述《人工智能原理》第三章歸結推理方法命題例命題：能判斷真假（不是既真又假）的陳述句。

簡單陳述句描述事實、事物的狀態、關系等性質。例如：1．

1+1=22．

雪是黑色的。3．

北京是中國的首都。4．

到冥王星去渡假。

判斷一個句子是否是命題，有先要看它是否是陳述句，而后看它的真值是否唯一。以上的例子都是陳述句，第4句的真值現在是假，隨著人類科學的發展，有可能變成真，但不管怎樣，真值是唯一的。因此，以上4個例子都是命題。而例如：1．

快點走吧！

2．

到那去？

3．

x+y>10

等等句子，都不是命題。命題例命題：能判斷真假（不是既真又假）的陳述句。《人工智能原理》第三章歸結推理方法命題表示公式（1）將陳述句轉化成命題公式。如：設“下雨”為p，“騎車上班”為q，，1．“只要不下雨，我騎自行車上班”。～p

是q的充分條件， 因而，可得命題公式：～p→q2．“只有不下雨，我才騎自行車上班”。～p

是q的必要條件， 因而，可得命題公式：q→～p命題表示公式（1）將陳述句轉化成命題公式。《人工智能原理》第三章歸結推理方法命題表示公式（2）例如：1．

“如果我進城我就去看你，除非我很累。” 設：p，我進城，q，去看你，r，我很累。 則有命題公式：～r→(p→q)。2．“應屆高中生，得過數學或物理競賽的一等獎， 保送上北京大學。” 設：p，應屆高中生，q，保送上北京大學上學，

r，是得過數學一等獎。t，是得過物理一等獎。 則有命題公式公式：p

∧(r∨t)→

q。

命題表示公式（2）例如：《人工智能原理》第三章歸結推理方法命題邏輯的歸結法命題邏輯基礎：定義：合取式：p與q，記做pΛ

q析取式：

p或q，記做p∨

q蘊含式：如果p則q，記做p→

q等價式：p當且僅當q，記做p<=>

q

。。。。。。命題邏輯的歸結法命題邏輯基礎：《人工智能原理》第三章歸結推理方法命題邏輯基礎定義：若A無成假賦值，則稱A為重言式或永真式；若A無成真賦值，則稱A為矛盾式或永假式；若A至少有一個成真賦值，則稱A為可滿足的；析取范式：僅由有限個簡單合取式組成的析取式。合取范式：僅由有限個簡單析取式組成的合取式。命題邏輯基礎定義：《人工智能原理》第三章歸結推理方法命題邏輯基礎基本等值式24個(1)交換率：p∨q<=>q

∨p

；

pΛq<=>qΛp

結合率：(p∨q)∨

r<=>p∨(q∨r); (pΛq)Λ

r<=>pΛ(qΛr)分配率：p∨(qΛ

r)<=>(p∨q)Λ(p∨r)

；

pΛ(q∨

r)<=>(pΛq)∨(pΛr)

命題邏輯基礎基本等值式24個(1)《人工智能原理》第三章歸結推理方法命題邏輯基礎基本等值式（1）摩根率:～

(p∨q)

<=>～

pΛ

～

q

；

～

(pΛq)

<=>～

p∨

～

q

吸收率:p∨(pΛq)<=>p

；

pΛ(p∨q)<=>p

同一律:p∨0

<=>p

；

pΛ1

<=>p

蘊含等值式:p→

q

<=>～

p∨q

假言易位式:p→

q

<=>～p→～

q

命題邏輯基礎基本等值式（1）《人工智能原理》第三章歸結推理方法命題邏輯的歸結法基本單元：簡單命題（陳述句）例：

命題：A1、A2、A3

和B求證：A1ΛA2ΛA3成立，則B成立，即：A1ΛA2ΛA3→B反證法：證明A1ΛA2ΛA3Λ～B是矛盾式（永假式）

命題邏輯的歸結法基本單元：簡單命題（陳述句）《人工智能原理》第三章歸結推理方法命題邏輯的歸結法建立子句集合取范式：命題、命題和的與，如：

PΛ（P∨Q）Λ（～P∨Q）子句集S：合取范式形式下的子命題（元素）的集合例：命題公式：PΛ（P∨Q）Λ（～P∨Q）子句集S：S={P,P∨Q,～P∨Q}

命題邏輯的歸結法建立子句集《人工智能原理》第三章歸結推理方法命題邏輯的歸結法歸結式消除互補對，求新子句→得到歸結式。如子句：C1,C2， 歸結式：R(C1,C2)=C1ΛC2

注意：C1ΛC2→R(C1,C2)

，反之不一定成立。命題邏輯的歸結法歸結式《人工智能原理》第三章歸結推理方法命題邏輯的歸結法歸結過程

將命題寫成合取范式求出子句集對子句集使用歸結推理規則歸結式作為新子句參加歸結歸結式為空子句□，S是不可滿足的（矛盾），原命題成立。?（證明完畢）謂詞的歸結：除了有量詞和函數以外，其余和命題歸結過程一樣。命題邏輯的歸結法歸結過程《人工智能原理》第三章歸結推理方法命題邏輯歸結例題（1）例題，證明公式：(P→Q)→(～Q→～P)證明：（1）根據歸結原理，將待證明公式轉化成待歸結命題公式：

(P→Q)∧～(～Q→～P)（2）分別將公式前項化為合取范式：

P→Q＝～P∨Q

結論求～后的后項化為合取范式： ～(～Q→～P)＝～(Q∨～P)＝～Q∧P

兩項合并后化為合取范式： （～P∨Q）∧～Q∧P

（3）則子句集為：

{～P∨Q，～Q，P}命題邏輯歸結例題（1）例題，證明公式：(P→Q)→(《人工智能原理》第三章歸結推理方法命題邏輯歸結例題（2）子句集為： {～P∨Q，～Q，P}（4）對子句集中的子句進行歸結可得：1.

～P∨Q2.

～Q3.

P4.

Q， （1，3歸結）5.

， （2，4歸結）

由上可得原公式成立。命題邏輯歸結例題（2）子句集為： {～P∨Q，～Q，P}《人工智能原理》第三章歸結推理方法第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述《人工智能原理》第三章歸結推理方法第三章歸結推理方法概述命題邏輯的歸結法謂詞歸結子句形歸結原理歸結過程的策略控制Herbrand定理第三章歸結推理方法概述《人工智能原理》第三章歸結推理方法謂詞歸結原理基礎一階邏輯基本概念個體詞：表示主語的詞謂詞：刻畫個體性質或個體之間關系的詞量詞：表示數量的詞謂詞歸結原理基礎一階邏輯《人工智能原理》第三章歸結推理方法謂詞歸結原理基礎

小王是個工程師。

8是個自然數。 我去買花。 小麗和小華是朋友。其中，“小王”、“工程師”、“我”、“花”、“8”、“小麗”、“小華”都是個體詞，而“是個工程師”、“是個自然數”、“去買”、“是朋友”都是謂詞。顯然前兩個謂詞表示的是事物的性質，第三個謂詞“去買”表示的一個動作也表示了主、賓兩個個體詞的關系，最后一個謂詞“是朋友”表示兩個個體詞之間的關系。謂詞歸結原理基礎 小王是個工程師。《人工智能原理》第三章歸結推理方法謂詞歸結原理基礎一階邏輯公式及其解釋個體常量：a,b,c個體變量：x,y,z謂詞符號：P,Q,R量詞符號：

,謂詞歸結原理基礎一階邏輯《人工智能原理》第三章歸結推理方法謂詞歸結原理基礎例如：（1）所有的人都是要死的。（2）

有的人活到一百歲以上。在個體域D為人類集合時，可符號化為：（1）xP(x)，其中P(x)表示x是要死的。（2）xQ(x),其中Q(x)表示x活到一百歲以上。在個體域D是全總個體域時，引入特殊謂詞R(x)表示x是人，可符號化為：（1）x（R(x)→P(x)）,

其中，R(x)表示x是人；P(x)表示x是要死的。（2）x（R(x)∧Q(x)）， 其中，R(x)表示x是人；Q(x)表示x活到一百歲以上。

謂詞歸結原理基礎例如：（1）所有的人都是要死的。《人工智能原理》第三章歸結推理方法謂詞歸結原理基礎量詞否定等值式：～(x

）

M（x）<=>（

y

）～

M（y）～(x

）

M（x）<=>（

y

）～

M（y）量詞分配等值式：(x

）(

P（x）ΛQ（x）)<=>(x

）

P（x）Λ(x

）

Q（x）(x

）(

P（x）∨

Q（x）)<=>(x

）

P（x）∨

(x

）

Q（x）消去量詞等值式：設個體域為有窮集合（a1,a2,…an）(x

）

P（x）<=>P（a1

）ΛP（a2

）Λ…ΛP（an

）(x

）P（x）<=>P（a1

）∨

P（a2

）∨

…

∨

P（an

）謂詞歸結原理基礎量詞否定等值式：《人工智能原理》第三章歸結推理方法謂詞歸結原理基礎量詞轄域收縮與擴張等值式：(x

）(

P（x）∨Q)<=>(x

）

P（x）∨Q(x

）(

P（x）ΛQ)<=>(x

）

P（x）ΛQ

(x

）(

P（x）→Q)<=>(x

）

P（x）→Q

(x

）(Q

→P（x）)<=>Q

→(x

）

P（x）(x

）(

P（x）∨Q)<=>(x

）

P（x）∨Q(x

）(

P（x）ΛQ)<=>(x

）

P（x）ΛQ

(x

）(

P（x）→Q)<=>(x

）

P（x）→Q

(x

）(Q

→P（x）)<=>Q

→(x

）

P（x）謂詞歸結原理基礎量詞轄域收縮與擴張等值式：《人工智能原理》第三章歸結推理方法謂詞歸結子句形(Skolem標準形)SKOLEM標準形前束范式

定義：說公式A是一個前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。謂詞歸結子句形(Skolem標準形)SKOLEM標準形《人工智能原理》第三章歸結推理方法謂詞歸結子句形(Skolem標準形)即：把所有的量詞都提到前面去，然后消掉所有量詞

(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)約束變項換名規則：(Qx

）

M（x）<=>（Qy

）

M（y）(Qx

）

M（x,z）<=>（Qy

）

M（y,z）謂詞歸結子句形(Skolem標準形)即：把所有的量詞都《人工智能原理》第三章歸結推理方法謂詞歸結子句形(Skolem標準形)