1、人工智能導(dǎo)論方若宇方若宇2009年秋季汕頭大學(xué)計(jì)算機(jī)系本科課程年秋季汕頭大學(xué)計(jì)算機(jī)系本科課程推理推理正向與反向推理正向與反向推理歸結(jié)推理歸結(jié)推理不確定性推理概述不確定性推理概述貝葉斯網(wǎng)絡(luò)貝葉斯網(wǎng)絡(luò)正向與反向推理方式正向與反向推理方式- -以產(chǎn)生式系統(tǒng)為例以產(chǎn)生式系統(tǒng)為例1.1.正向推理正向推理 正向推理又稱(chēng)為正向鏈接推理，其推理基礎(chǔ)是邏輯演繹的推理鏈，它從一組表示事實(shí)的謂詞或正向推理又稱(chēng)為正向鏈接推理，其推理基礎(chǔ)是邏輯演繹的推理鏈，它從一組表示事實(shí)的謂詞或命題出發(fā)，使用一組推理規(guī)則，來(lái)證明目標(biāo)謂詞公式或命題是否成立。命題出發(fā)，使用一組推理規(guī)則，來(lái)證明目標(biāo)謂詞公式或命題是否成立。 實(shí)現(xiàn)正向推理的

2、一般策略是：先提供一批數(shù)據(jù)實(shí)現(xiàn)正向推理的一般策略是：先提供一批數(shù)據(jù)( (事實(shí)事實(shí)) )到總數(shù)據(jù)庫(kù)中，系統(tǒng)利用這些事實(shí)與規(guī)則到總數(shù)據(jù)庫(kù)中，系統(tǒng)利用這些事實(shí)與規(guī)則的前提匹配，觸發(fā)匹配成功的規(guī)則的前提匹配，觸發(fā)匹配成功的規(guī)則( (即啟用規(guī)則即啟用規(guī)則) )，把其結(jié)論作為新的事實(shí)添加到總數(shù)據(jù)庫(kù)中。繼，把其結(jié)論作為新的事實(shí)添加到總數(shù)據(jù)庫(kù)中。繼續(xù)上述過(guò)程，用更新過(guò)的總數(shù)據(jù)庫(kù)中的所有事實(shí)再與規(guī)則庫(kù)中另一條規(guī)則匹配，用其結(jié)論再修改續(xù)上述過(guò)程，用更新過(guò)的總數(shù)據(jù)庫(kù)中的所有事實(shí)再與規(guī)則庫(kù)中另一條規(guī)則匹配，用其結(jié)論再修改總數(shù)據(jù)庫(kù)的內(nèi)容，直到?jīng)]有可匹配的新規(guī)則，不再有新的事實(shí)加到總數(shù)據(jù)庫(kù)為止?？倲?shù)據(jù)庫(kù)的內(nèi)容，直到?jīng)]有可

3、匹配的新規(guī)則，不再有新的事實(shí)加到總數(shù)據(jù)庫(kù)為止。例如，有規(guī)則集如下例如，有規(guī)則集如下: :規(guī)則規(guī)則1: IF P1 THEN P2 1: IF P1 THEN P2 規(guī)則規(guī)則2: IF P2 THEN P3 2: IF P2 THEN P3 規(guī)則規(guī)則3: IF P3 THEN q3 3: IF P3 THEN q3 規(guī)則中的規(guī)則中的P1P1、P2P2、P3P3、q3q3可以是謂詞公式或命題。設(shè)總數(shù)據(jù)庫(kù)（工作存儲(chǔ)器）中已有事實(shí)可以是謂詞公式或命題。設(shè)總數(shù)據(jù)庫(kù)（工作存儲(chǔ)器）中已有事實(shí)P1P1，則，則應(yīng)用這三條規(guī)則進(jìn)行正向推理，即從應(yīng)用這三條規(guī)則進(jìn)行正向推理，即從P1P1出發(fā)推導(dǎo)出出發(fā)推導(dǎo)出q3q3的

4、過(guò)程如圖的過(guò)程如圖4.164.16所示。所示。 前面已經(jīng)指出，前件和后件可以用命題或謂詞來(lái)表示，當(dāng)它們是謂詞時(shí)，全局前提與總數(shù)據(jù)庫(kù)前面已經(jīng)指出，前件和后件可以用命題或謂詞來(lái)表示，當(dāng)它們是謂詞時(shí)，全局前提與總數(shù)據(jù)庫(kù)中的事實(shí)匹配成功是指：對(duì)前件謂詞中出現(xiàn)的變量進(jìn)行某種統(tǒng)一的置換，使置換后的前件謂詞成中的事實(shí)匹配成功是指：對(duì)前件謂詞中出現(xiàn)的變量進(jìn)行某種統(tǒng)一的置換，使置換后的前件謂詞成為總數(shù)據(jù)庫(kù)中某個(gè)謂詞的實(shí)例，即實(shí)例化后前件謂詞與總數(shù)據(jù)庫(kù)中某個(gè)事實(shí)相同。執(zhí)行后件是指：為總數(shù)據(jù)庫(kù)中某個(gè)謂詞的實(shí)例，即實(shí)例化后前件謂詞與總數(shù)據(jù)庫(kù)中某個(gè)事實(shí)相同。執(zhí)行后件是指：當(dāng)前件匹配成功時(shí)，用前件匹配時(shí)使用的相同變量，按

5、同一方式對(duì)后件謂詞進(jìn)行置換，并把置換當(dāng)前件匹配成功時(shí)，用前件匹配時(shí)使用的相同變量，按同一方式對(duì)后件謂詞進(jìn)行置換，并把置換結(jié)果（后件謂詞實(shí)例）加進(jìn)總數(shù)據(jù)庫(kù)。結(jié)果（后件謂詞實(shí)例）加進(jìn)總數(shù)據(jù)庫(kù)。正向推理鏈接過(guò)程示意圖正向推理鏈接過(guò)程示意圖 2.2.反向推理反向推理 反向推理又稱(chēng)為后向鏈接推理，其基本原理是從表示目標(biāo)的謂詞或命題出發(fā)，使用一組規(guī)反向推理又稱(chēng)為后向鏈接推理，其基本原理是從表示目標(biāo)的謂詞或命題出發(fā)，使用一組規(guī)則證明事實(shí)謂詞或命題成立，即提出一批假設(shè)則證明事實(shí)謂詞或命題成立，即提出一批假設(shè)( (目標(biāo)目標(biāo)) )，然后逐一驗(yàn)證這些假設(shè)。，然后逐一驗(yàn)證這些假設(shè)。 舉例如下：仍用上述的三條規(guī)則為例，

6、應(yīng)用反向推理方法，從舉例如下：仍用上述的三條規(guī)則為例，應(yīng)用反向推理方法，從P1P1出發(fā)推導(dǎo)出出發(fā)推導(dǎo)出q3q3的過(guò)程如圖的過(guò)程如圖4.184.18所示：所示： 首先假定目標(biāo)首先假定目標(biāo)q3q3成立，由規(guī)則成立，由規(guī)則3 3（P3q3P3q3），為證明），為證明q3q3成立，須先驗(yàn)證成立，須先驗(yàn)證P3P3是否成立；但總數(shù)是否成立；但總數(shù)據(jù)庫(kù)沒(méi)有事實(shí)據(jù)庫(kù)沒(méi)有事實(shí)P3P3，所以假定子目標(biāo)，所以假定子目標(biāo)P3P3成立；由規(guī)則成立；由規(guī)則2(P2P3)2(P2P3)，應(yīng)驗(yàn)證，應(yīng)驗(yàn)證P2P2；同樣，由于數(shù)據(jù)庫(kù)；同樣，由于數(shù)據(jù)庫(kù)中沒(méi)有事實(shí)中沒(méi)有事實(shí)P2P2，假定子目標(biāo)，假定子目標(biāo)P2P2成立；由規(guī)則成立；由

7、規(guī)則1(P1P2)1(P1P2)，為驗(yàn)證，為驗(yàn)證P2P2成立，須先驗(yàn)證成立，須先驗(yàn)證P1P1。因?yàn)閿?shù)。因?yàn)閿?shù)據(jù)庫(kù)中有事實(shí)據(jù)庫(kù)中有事實(shí)P1P1，所以假定的目標(biāo)，所以假定的目標(biāo)P2P2成立，因而成立，因而P3P3成立，最終導(dǎo)出結(jié)論成立，最終導(dǎo)出結(jié)論q3q3確實(shí)成立。確實(shí)成立。 總之，反向推理的具體實(shí)現(xiàn)策略是：先假定一個(gè)可能的目標(biāo)，系統(tǒng)試圖證明它，看此假設(shè)總之，反向推理的具體實(shí)現(xiàn)策略是：先假定一個(gè)可能的目標(biāo)，系統(tǒng)試圖證明它，看此假設(shè)目標(biāo)是否在總數(shù)據(jù)庫(kù)中，若在，則假設(shè)成立。否則，看這些假設(shè)是否證據(jù)目標(biāo)是否在總數(shù)據(jù)庫(kù)中，若在，則假設(shè)成立。否則，看這些假設(shè)是否證據(jù)( (葉子葉子) )結(jié)點(diǎn)，若是，結(jié)點(diǎn)，若是

8、，向用戶詢(xún)問(wèn)，若不是，則再假定另一個(gè)目標(biāo)，即找出結(jié)論部分中包含此假設(shè)的那些規(guī)則，把它向用戶詢(xún)問(wèn)，若不是，則再假定另一個(gè)目標(biāo)，即找出結(jié)論部分中包含此假設(shè)的那些規(guī)則，把它們的前提作為新的假設(shè)，試圖證明它。這樣周而復(fù)始，直到所有目標(biāo)被證明，或所有路徑被測(cè)們的前提作為新的假設(shè)，試圖證明它。這樣周而復(fù)始，直到所有目標(biāo)被證明，或所有路徑被測(cè)試。試。 反向推理鏈接過(guò)程示意圖反向推理鏈接過(guò)程示意圖3.3.雙向推理雙向推理還有歸結(jié)推理方法歸結(jié)推理方法概述概述 歸結(jié)原理由歸結(jié)原理由J.A.RobinsonJ.A.Robinson由由19651965年提出。年提出。 與演繹法與演繹法(deductive infer

9、ence)(deductive inference)完全不同，是一種新的邏輯演完全不同，是一種新的邏輯演算算(inductive inference)(inductive inference)算法。至今為止一階邏輯中最有效的半可算法。至今為止一階邏輯中最有效的半可判定的算法。一階邏輯中任意恒真公式，使用歸結(jié)原理，總可以在判定的算法。一階邏輯中任意恒真公式，使用歸結(jié)原理，總可以在有限步內(nèi)給以判定。有限步內(nèi)給以判定。 語(yǔ)義網(wǎng)絡(luò)、框架表示、產(chǎn)生式規(guī)則等等以推理方法為前提的。即，語(yǔ)義網(wǎng)絡(luò)、框架表示、產(chǎn)生式規(guī)則等等以推理方法為前提的。即，有了規(guī)則已知條件，順藤摸瓜找到結(jié)果。有了規(guī)則已知條件，順藤摸瓜找到

10、結(jié)果。 歸結(jié)方法沒(méi)有這樣一個(gè)循歸結(jié)方法沒(méi)有這樣一個(gè)循序漸進(jìn)的過(guò)程，而是在一個(gè)規(guī)則指導(dǎo)下，進(jìn)行自動(dòng)推導(dǎo)（序漸進(jìn)的過(guò)程，而是在一個(gè)規(guī)則指導(dǎo)下，進(jìn)行自動(dòng)推導(dǎo)（“數(shù)學(xué)定數(shù)學(xué)定理機(jī)器證明理機(jī)器證明”）。）。 本課程只討論一階謂詞邏輯描述下的歸結(jié)推理方法，不涉及高階本課程只討論一階謂詞邏輯描述下的歸結(jié)推理方法，不涉及高階 謂詞邏輯問(wèn)題。謂詞邏輯問(wèn)題。 命題邏輯的歸結(jié)法命題邏輯的歸結(jié)法命題邏輯基礎(chǔ)：命題邏輯基礎(chǔ)： 定義：定義：合取式：合取式：p p與與q q，記做，記做p p q q析取式：析取式：p p或或q q，記做，記做p p q q蘊(yùn)含式：如果蘊(yùn)含式：如果p p則則q q，記做，記做p p q q等

11、價(jià)式：等價(jià)式：p p當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)q q，記做，記做p p q q析取范式：僅由有限個(gè)簡(jiǎn)單合取式組成的析取式。析取范式：僅由有限個(gè)簡(jiǎn)單合取式組成的析取式。合取范式：僅由有限個(gè)簡(jiǎn)單析取式組成的合取式。合取范式：僅由有限個(gè)簡(jiǎn)單析取式組成的合取式。.基本等值式基本等值式2424個(gè)個(gè)(1)(1)交換率：交換率：p pq q q q p p ； p p q q q q p p 結(jié)合率：結(jié)合率： ( (p pq q) ) r r p p(q q r);r); ( (p p q) q) r r p p (q q r) r)分配率：分配率： p p(q q r) (r) (p pq q)()(p p r)

12、r) ； p p (q q r) (r) (p p q q) () (p p r) r) 摩根率摩根率: : ( (p pq q) ) p p q q ； ( (p p q q) ) p p q q 吸收率吸收率: : p p(p pq q ) ) p p ； p p (p pq q ) ) p p 同一律同一律: : p p0 0 p p ； p p1 1 p p 蘊(yùn)含等值式蘊(yùn)含等值式: :p p q q p pq q 假言易位式假言易位式: : p p q q p p q q命題邏輯的歸結(jié)法命題邏輯的歸結(jié)法 歸結(jié)法的基本單元是簡(jiǎn)單命題（陳述句）歸結(jié)法的基本單元是簡(jiǎn)單命題（陳述句）命題：命題

13、： A A1 1、A A2 2、A A3 3 和和 B B求證：求證： A A1 1AA2 2AA3 3成立，則成立，則B B成立，成立，即求證：即求證：A A1 1AA2 2AA3 3 B B歸結(jié)法使用反證法：歸結(jié)法使用反證法： 證明證明A A1 1AA2 2AA3 3B B 是矛盾式（即永假式）是矛盾式（即永假式） 首先需要建立子句集首先需要建立子句集 1.1.寫(xiě)出合取范式：寫(xiě)出合取范式：PP（ PQPQ）（PQPQ）（即（命題）、（命題和）的與）（即（命題）、（命題和）的與）2.2.從合取范式得到子句集從合取范式得到子句集S S：合取范式形式下的子命題（元素）的集合合取范式形式下的子命題

14、（元素）的集合例：將命題公式寫(xiě)成合取范式的形式：例：將命題公式寫(xiě)成合取范式的形式：PP（ PQPQ）（ PQPQ） 得到子句集得到子句集 S S：S = P, PQ, S = P, PQ, PQPQ 其次進(jìn)行歸結(jié)其次進(jìn)行歸結(jié) 歸結(jié)式歸結(jié)式 設(shè)設(shè)C1C1和和C2C2是子句集中的任意兩個(gè)子句是子句集中的任意兩個(gè)子句, ,如果如果C1C1中的文字中的文字L1L1與與C2C2中的文字中的文字L2L2互補(bǔ)互補(bǔ), ,那么可以從那么可以從C1C1和和C2C2中分別消去中分別消去L1L1和和L2,L2,并將并將C1C1和和C2C2中余下的部分按析取關(guān)系構(gòu)成一個(gè)新子句中余下的部分按析取關(guān)系構(gòu)成一個(gè)新子句C12,

15、C12,則稱(chēng)這個(gè)過(guò)程為歸則稱(chēng)這個(gè)過(guò)程為歸結(jié)結(jié), ,稱(chēng)稱(chēng)C12C12為為C1C1和和C2C2的歸結(jié)式的歸結(jié)式 歸結(jié)法的核心是在子句集之上求兩個(gè)子句間的歸結(jié)式歸結(jié)法的核心是在子句集之上求兩個(gè)子句間的歸結(jié)式. . 歸結(jié)過(guò)程歸結(jié)過(guò)程 ： 1.1.將命題寫(xiě)成合取范式將命題寫(xiě)成合取范式 2.2.求出子句集求出子句集 3.3.對(duì)子句集使用歸結(jié)推理規(guī)則對(duì)子句集使用歸結(jié)推理規(guī)則 4.4.歸結(jié)式作為新子句參加歸結(jié)歸結(jié)式作為新子句參加歸結(jié) 5.5.歸結(jié)式為空子句，歸結(jié)式為空子句，S S是不可滿足的（矛盾），原命題成立。是不可滿足的（矛盾），原命題成立。（證明完畢）（證明完畢）命題邏輯歸結(jié)例題命題邏輯歸結(jié)例題例題，證

16、明公式：例題，證明公式：(P Q) (P Q) (Q Q P)P)證明：證明： 1. 1. 根據(jù)歸結(jié)原理，將待證明公式轉(zhuǎn)化成待歸結(jié)命題公式：根據(jù)歸結(jié)原理，將待證明公式轉(zhuǎn)化成待歸結(jié)命題公式：(P Q) (P Q) ( (Q Q P)P)2. 2. 將公式前項(xiàng)化為合取范式：將公式前項(xiàng)化為合取范式：P Q P Q P QP Q結(jié)論求后的后項(xiàng)化為合取范式：結(jié)論求后的后項(xiàng)化為合取范式：( (Q Q P)P) (Q(QP) P) Q PQ P兩項(xiàng)合并后化為合取范式：兩項(xiàng)合并后化為合取范式： （P QP Q）Q PQ P 3. 3. 則子句集為：則子句集為： PQPQ，Q Q，PP假定結(jié)論不成立假定結(jié)論不成

17、立子句集為：子句集為： PQPQ，Q Q，PP4.4.對(duì)子句集中的子句進(jìn)行歸結(jié)可得：對(duì)子句集中的子句進(jìn)行歸結(jié)可得：1.1. PQPQ2.2. Q Q3.3. P P4.4. Q Q （1 1，3 3歸結(jié)）歸結(jié)）5.5. NilNil （2 2，4 4歸結(jié)）歸結(jié)）由上可知假設(shè)矛盾，即原公式成立。由上可知假設(shè)矛盾，即原公式成立。謂詞歸結(jié)原理基礎(chǔ)謂詞歸結(jié)原理基礎(chǔ)一階邏輯一階邏輯基本概念基本概念 個(gè)體詞個(gè)體詞 ：表示主語(yǔ)的詞：表示主語(yǔ)的詞 謂詞謂詞 ：刻畫(huà)個(gè)體性質(zhì)或個(gè)體之間關(guān)系的詞：刻畫(huà)個(gè)體性質(zhì)或個(gè)體之間關(guān)系的詞 量詞量詞 ：表示數(shù)量的詞：表示數(shù)量的詞公式及其解釋公式及其解釋 個(gè)體常量：個(gè)體常量：a,

18、b,ca,b,c 個(gè)體變量：個(gè)體變量：x,y,zx,y,z 謂詞符號(hào)：謂詞符號(hào)：P,Q,RP,Q,R 量詞符號(hào)：量詞符號(hào)： , , 例如：例如：（1 1）所有的人都是要死的。）所有的人都是要死的。（2 2）有的人活到一百歲以上。）有的人活到一百歲以上。在個(gè)體域在個(gè)體域D D為人類(lèi)集合時(shí)，可符號(hào)化為：為人類(lèi)集合時(shí)，可符號(hào)化為： x x P P( (x x) )，其中，其中P P( (x x) )表示表示x x是要死的。是要死的。 x x Q Q( (x x), ), 其中其中Q Q( (x x) )表示表示x x活到一百歲以上?；畹揭话贇q以上。引入特殊謂詞引入特殊謂詞R R( (x x) )表示

19、表示x x是人，可符號(hào)化為：是人，可符號(hào)化為：（1 1） x x（R R( (x x) ) P P( (x x) )）, , 其中，其中，R R( (x x) )表示表示x x是人；是人；P P( (x x) )表示表示x x是要死的。是要死的。（2 2） x x（R R( (x x) ) Q Q( (x x) )），），其中，其中，R R( (x x) )表示表示x x是人；是人；Q Q( (x x) )表示表示x x活到一百歲以上活到一百歲以上。 量詞否定等值式：量詞否定等值式：( ( x x）M M（x x）（ x x）M M（x x） ( ( x x）M M（x x）（ x x）M M

20、（x x）量詞分配等值式：量詞分配等值式：( ( x x）(P(P（x x）QQ（x x）)()( x x）P P（x x）( x x）Q Q（x x）( ( x x）(P(P（x x）Q Q（x x）) () ( x x）P P（x x）( ( x x）Q Q（x x）消去量詞等值式：設(shè)個(gè)體域?yàn)橛懈F集合（消去量詞等值式：設(shè)個(gè)體域?yàn)橛懈F集合（a a1 1, a, a2 2, , a an n）( ( x x）P P（x x）PP（a a1 1）PP（a a2 2） P P（a an n）( ( x x）P P（x x）PP（a a1 1）P P（a a2 2） P P（a an n）量詞轄域收

21、縮與擴(kuò)張等值式：量詞轄域收縮與擴(kuò)張等值式：( ( x x）( ( P P（x x） Q) (Q) ( x x）P P（x x） Q Q( ( x x）( ( P P（x x） Q) ( Q) ( x x）P P（x x） Q Q ( ( x x）( ( P P（x x） Q) (Q) ( x x）P P（x x） Q Q ( ( x x）( QP( QP（x x）) ) Q(Q( x x）P P（x x） ( ( x x）( ( P P（x x） Q) (Q) ( x x） P P（x x） Q Q( ( x x）( ( P P（x x） Q) ( Q) ( x x） P P（x x） Q Q

22、 ( ( x x）( ( P P（x x） Q) (Q) ( x x） P P（x x） Q Q ( ( x x）( Q( Q PP（x x）) ) Q(Q( x x） P P（x x）謂詞歸結(jié)子句形謂詞歸結(jié)子句形( ( SkolemSkolem 標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形) ) 前束范式定義：前束范式定義： 如果如果A A中的一切量詞都位于該公式的最左邊（不含否中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端，則說(shuō)定詞），且這些量詞的轄域都延伸到公式的末端，則說(shuō)公式公式A A是一個(gè)前束范式。是一個(gè)前束范式。 即即: :把所有的量詞都提到前面去，然后消掉所有量詞把所有的量詞

23、都提到前面去，然后消掉所有量詞 (Q1x1)(Q2x2)(Q1x1)(Q2x2)(Qnxn)M(x1,x2,(Qnxn)M(x1,x2, ,xnxn) ) 約束變項(xiàng)換名規(guī)則：約束變項(xiàng)換名規(guī)則： ( (QxQx） M M（x x） （QyQy） M M（y y） ( (QxQx） M M（x,zx,z） （QyQy） M M（y,zy,z）量詞消去原則：量詞消去原則： 1. 1. 消去存在量詞消去存在量詞“ ”， 左邊有全程量詞的存在量詞，消去時(shí)該變量改寫(xiě)成為全程量詞的函數(shù)；左邊有全程量詞的存在量詞，消去時(shí)該變量改寫(xiě)成為全程量詞的函數(shù)；如沒(méi)有，改寫(xiě)成為常量。如沒(méi)有，改寫(xiě)成為常量。 2. 2. 略

24、去全程量詞略去全程量詞“ ”。例例: :將下式化為將下式化為SkolemSkolem標(biāo)準(zhǔn)形：標(biāo)準(zhǔn)形：( ( x)(x)( y)P(a,x,yy)P(a,x,y) () ( x)(x)( ( y)Q(y,b)R(xy)Q(y,b)R(x) 第一步，消去第一步，消去號(hào)，得：號(hào)，得：( ( ( x)(x)( y)P(a,x,yy)P(a,x,y) ( ( x)(x)( ( y)Q(y,b)R(xy)Q(y,b)R(x)第二步，深入到量詞內(nèi)部，得：第二步，深入到量詞內(nèi)部，得：( ( x)(x)( y)P(a,x,yy)P(a,x,y) ( ( x)(x)( y)Q(y,b)R(xy)Q(y,b)R(x

25、)( ( x)(x)( y)P(a,x,y)(y)P(a,x,y)( x)(x)( y)Q(y,b)R(xy)Q(y,b)R(x)第三步，變?cè)酌?，得第三步，變?cè)酌?，? ( x)(x)( y)P(a,x,yy)P(a,x,y) ) ( ( u u)()( v v)(Q(v,b)(Q(v,b) ) R(uR(u)第四步，存在量詞左移，直至所有的量詞移到前面，得：第四步，存在量詞左移，直至所有的量詞移到前面，得： ( ( x)(x)( y)(y)( u u)()( v v)P(a,x,y)P(a,x,y) ) ( (Q(v,b)R(uQ(v,b)R(u)由此得到前由此得到前束束范式范式 ( (

26、 x)(x)( y)(y)( u u)()( v v)P(a,x,y)(Q(v,b)R(u)P(a,x,y)(Q(v,b)R(u)第五步，消去第五步，消去“ ”（存在量詞），略去（存在量詞），略去“ ”全稱(chēng)量詞全稱(chēng)量詞 消去消去( ( y)y)，因?yàn)樗筮呏挥?，因?yàn)樗筮呏挥? ( x)x)，所以使用，所以使用x x的函的函數(shù)數(shù)f(xf(x) )代替之，這樣得到：代替之，這樣得到：( ( x)(x)( u)(u)( v)(P(a,x,f(x)Q(vv)(P(a,x,f(x)Q(v, , b)R(ub)R(u) 消去消去( ( u)u)，同理使用，同理使用g(xg(x) )代替之，這樣得到：代替

27、之，這樣得到：( ( x)(x)( v)(P(a,x,f(x)Q(v,b)R(g(xv)(P(a,x,f(x)Q(v,b)R(g(x)） 略去全稱(chēng)變量，原式的略去全稱(chēng)變量，原式的SkolemSkolem標(biāo)準(zhǔn)形為：標(biāo)準(zhǔn)形為： P(a,x,f(x)Q(v,b)R(g(xP(a,x,f(x)Q(v,b)R(g(x)置換與合一置換與合一 一階謂詞邏輯的歸結(jié)比命題邏輯的歸結(jié)要復(fù)雜得多一階謂詞邏輯的歸結(jié)比命題邏輯的歸結(jié)要復(fù)雜得多, ,其中一個(gè)原因其中一個(gè)原因就是謂詞邏輯公式中含有個(gè)體變量與函數(shù)就是謂詞邏輯公式中含有個(gè)體變量與函數(shù). .因此因此, ,尋找互補(bǔ)子句的過(guò)程尋找互補(bǔ)子句的過(guò)程就比較復(fù)雜就比較復(fù)雜.

28、 . 例如例如, , P(xP(x) ) Q(yQ(y) ) 與與 P(aP(a) ) R(zR(z) ) 就不容易從直接比較中發(fā)現(xiàn)這兩個(gè)子句中含有互補(bǔ)對(duì)就不容易從直接比較中發(fā)現(xiàn)這兩個(gè)子句中含有互補(bǔ)對(duì), ,但如果將但如果將x x 取取a a值值, ,則很明顯這兩個(gè)子句為互補(bǔ)對(duì)則很明顯這兩個(gè)子句為互補(bǔ)對(duì). . 這就是將要討論的置換與合一這就是將要討論的置換與合一, ,即對(duì)個(gè)體變量做適當(dāng)?shù)奶鎿Q即對(duì)個(gè)體變量做適當(dāng)?shù)奶鎿Q. .置換置換置換置換：可以簡(jiǎn)單的理解為是在一個(gè)謂詞公式中用置換項(xiàng)去置換變量。：可以簡(jiǎn)單的理解為是在一個(gè)謂詞公式中用置換項(xiàng)去置換變量。定義：定義： 置換是形如置換是形如tt1 1/x/

29、x1 1, t, t2 2/x/x2 2, , , , t tn n/x/xn n 的有限集合。的有限集合。 其中，其中，x x1 1, x, x2 2, , , , x xn n是互不相同的變量，是互不相同的變量， t t1 1, t, t2 2, , , , t tn n是不同于是不同于x xi i的項(xiàng)（常量、變量、函數(shù)）；的項(xiàng)（常量、變量、函數(shù)）； t ti i/x/xi i表示用表示用t ti i置換置換x xi i，并且要求，并且要求t ti i與與x xi i不能相同，而且不能相同，而且x xi i不能循環(huán)地出現(xiàn)在另一個(gè)不能循環(huán)地出現(xiàn)在另一個(gè)t ti i中。中。例如例如a/xa/x

30、，c/yc/y，f(b)/zf(b)/z 是一個(gè)置換；是一個(gè)置換； g(y)/xg(y)/x，f(x)/yf(x)/y 不是一個(gè)置換。不是一個(gè)置換。置換的合成置換的合成 設(shè)設(shè) tt1 1/x/x1 1, t, t2 2/x/x2 2, , , , t tn n/x/xn n ， uu1 1/y/y1 1, u, u2 2/y/y2 2, , , u, un n/ /y yn n ，是兩個(gè)置換。，是兩個(gè)置換。 則則 與與 的合成也是一個(gè)置換，記作的合成也是一個(gè)置換，記作 。它是從集合。它是從集合tt1 1 /x/x1 1, t, t2 2 /x/x2 2, , , , t tn n /x/xn

31、n, u, u1 1/y/y1 1, u, u2 2/y/y2 2, , , u, un n/ /y yn n 中刪去以下兩種元素：中刪去以下兩種元素： 1.1.當(dāng)當(dāng)t ti i =x=xi i時(shí)，刪去時(shí)，刪去t ti i /x/xi i (i = 1, 2, (i = 1, 2, , n);, n); 2. 2.當(dāng)當(dāng)y yi i xx1 1,x,x2 2, , , , x xn n 時(shí)，刪去時(shí)，刪去u uj j/y/yj j (j = 1, 2, (j = 1, 2, , m), m) 最后剩下的元素所構(gòu)成的集合。最后剩下的元素所構(gòu)成的集合。 合成即是對(duì)合成即是對(duì)t ti i先做先做 置換然

32、后再做置換然后再做 置換，置換置換，置換x xi i置換的合成例子置換的合成例子 設(shè)：設(shè)： f(y)/xf(y)/x, , z/yz/y ， a/x, a/x, b/yb/y, , y/zy/z ，求，求 與與 的合成。的合成。 解：先求出集合解：先求出集合 f(b/y)/xf(b/y)/x, (, (y/z)/yy/z)/y, a/x, , a/x, b/yb/y, , y/zy/z f(b)/xf(b)/x, , y/yy/y, a/x, , a/x, b/yb/y, , y/zy/z 其中，其中，f(b)/xf(b)/x中的中的f(bf(b) )是置換是置換 作用于作用于f(yf(y)

33、)的結(jié)果的結(jié)果; ;y/yy/y中的中的y y是置是置換換 作用于作用于z z的結(jié)果。的結(jié)果。 在該集合中，在該集合中，y/yy/y滿足定義中的條件滿足定義中的條件i i，需要?jiǎng)h除；，需要?jiǎng)h除；a/xa/x，b/yb/y滿足滿足定義中的條件定義中的條件iiii，也需要?jiǎng)h除。，也需要?jiǎng)h除。 最后得最后得 f(b)/xf(b)/x，y/zy/z 合一合一 合一合一可以簡(jiǎn)單地理解為可以簡(jiǎn)單地理解為“尋找相對(duì)變量的置換，使兩個(gè)謂詞公式一致尋找相對(duì)變量的置換，使兩個(gè)謂詞公式一致”。 定義：定義： 設(shè)有公式集設(shè)有公式集F FFF1 1，F(xiàn) F2 2，F(xiàn) Fn n ，若存在一個(gè)置換，若存在一個(gè)置換 ，可使，

34、可使F F1 1 F F2 2 = F= Fn n ，則稱(chēng)，則稱(chēng) 是是F F的一個(gè)合一。同時(shí)稱(chēng)的一個(gè)合一。同時(shí)稱(chēng)F F1 1，F(xiàn) F2 2，. . ，F(xiàn) Fn n是可合一的。是可合一的。 例：例： 設(shè)有公式集設(shè)有公式集F F P(xP(x, y, , y, f(yf(y), ), P(a,g(x),zP(a,g(x),z)， 則則 a/x, a/x, g(a)/yg(a)/y, , f(g(a)/zf(g(a)/z 是它的一個(gè)合一。是它的一個(gè)合一。 注意：一般說(shuō)來(lái)，一個(gè)公式集的合一不是唯一的。注意：一般說(shuō)來(lái)，一個(gè)公式集的合一不是唯一的。 歸結(jié)式歸結(jié)式 C1,C2C1,C2是兩個(gè)沒(méi)有公共變量的子

35、句是兩個(gè)沒(méi)有公共變量的子句,L1,L2,L1,L2分別是分別是C1,C2C1,C2的文字的文字, ,如果如果L1L1與與 L2L2有有mgumgu , ,則則 R=(c1 R=(c1 -L1 -L1 ) ) (c2 (c2 -L2 -L2 ) 通俗的說(shuō)通俗的說(shuō): :如果兩個(gè)子句中分別有可以合一的互補(bǔ)文字如果兩個(gè)子句中分別有可以合一的互補(bǔ)文字, ,則可以通過(guò)置換則可以通過(guò)置換, ,減去互補(bǔ)對(duì)的并集便是歸結(jié)式減去互補(bǔ)對(duì)的并集便是歸結(jié)式. . 例例: : 1. 1. P(xP(x) ) Q(x,yQ(x,y) ) 與與P(aP(a) ) R(b,zR(b,z) )的歸結(jié)式為的歸結(jié)式為 Q(a,yQ(

36、a,y) ) R(b,zR(b,z) ) 2.P(x,y) 2.P(x,y)Q(x)Q(x)R(x)R(x)與與P(a,zP(a,z)Q(bQ(b) )的歸結(jié)式有以下兩種的歸結(jié)式有以下兩種: : Q(a)R(aQ(a)R(a)Q(bQ(b) ) 或或 P(b,y)R(bP(b,y)R(b)P(a,zP(a,z) ) 歸結(jié)的注意事項(xiàng)：歸結(jié)的注意事項(xiàng)：1.1.謂詞的一致性，謂詞的一致性，P()P()與與Q()Q()，不可以歸結(jié)，不可以歸結(jié)2.2.常量的一致性，常量的一致性，P(aP(a, , ) )與與P(bP(b, ,.).)，不可以歸結(jié)，不可以歸結(jié) 變量，變量，P(aP(a, ,.).)與與P

37、(xP(x, ,) )，可以歸結(jié)，可以歸結(jié)3.3.變量與函數(shù)，變量與函數(shù)，P(xP(x, ,.).)與與P(f(xP(f(x),),) )，不可以歸結(jié)；，不可以歸結(jié)；4.4.不能同時(shí)消去兩個(gè)互補(bǔ)對(duì)不能同時(shí)消去兩個(gè)互補(bǔ)對(duì)5.5.先進(jìn)行內(nèi)部簡(jiǎn)化（置換、合并）先進(jìn)行內(nèi)部簡(jiǎn)化（置換、合并） 例例: : c1= c1=P(y)QP(y)Q(x)(x)R(g(xR(g(x), c2=), c2=P(f(g(aP(f(g(a)Q(bQ(b) )歸結(jié)的過(guò)程歸結(jié)的過(guò)程 寫(xiě)出謂詞關(guān)系公式寫(xiě)出謂詞關(guān)系公式 用反演法寫(xiě)出謂詞表達(dá)式用反演法寫(xiě)出謂詞表達(dá)式SKOLEMSKOLEM標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形 子句集子句集S S 對(duì)對(duì)S

38、S中可歸結(jié)的子句做歸結(jié)中可歸結(jié)的子句做歸結(jié) 歸結(jié)式仍放入歸結(jié)式仍放入S S中，反復(fù)歸結(jié)過(guò)程中，反復(fù)歸結(jié)過(guò)程 得到空子句得到空子句得證得證例題例題“快樂(lè)學(xué)生快樂(lè)學(xué)生”問(wèn)題問(wèn)題 假設(shè)任何通過(guò)計(jì)算機(jī)考試并獲獎(jiǎng)的人都是快樂(lè)的，任何肯學(xué)習(xí)或幸運(yùn)的人都假設(shè)任何通過(guò)計(jì)算機(jī)考試并獲獎(jiǎng)的人都是快樂(lè)的，任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過(guò)所有的考試，張不肯學(xué)習(xí)但他是幸運(yùn)的，任何幸運(yùn)的人都能獲獎(jiǎng)。求可以通過(guò)所有的考試，張不肯學(xué)習(xí)但他是幸運(yùn)的，任何幸運(yùn)的人都能獲獎(jiǎng)。求證：張是快樂(lè)的。證：張是快樂(lè)的。 解：先將問(wèn)題用謂詞表示如下：解：先將問(wèn)題用謂詞表示如下：R1:R1:“任何通過(guò)計(jì)算機(jī)考試并獲獎(jiǎng)的人都是快樂(lè)的任何通過(guò)計(jì)算機(jī)考

39、試并獲獎(jiǎng)的人都是快樂(lè)的”( ( x)(Pass(xx)(Pass(x, , computer)Win(xcomputer)Win(x, , prize)Happy(xprize)Happy(x)R2:R2:“任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過(guò)所有考試任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過(guò)所有考試”( ( x)(x)( y)(Study(x)Lucky(x)Pass(xy)(Study(x)Lucky(x)Pass(x, y), y)R3:R3:“張不肯學(xué)習(xí)但他是幸運(yùn)的張不肯學(xué)習(xí)但他是幸運(yùn)的”Study(zhang)Lucky(zhangStudy(zhang)Lucky(zhang) )R4:R4:“任何幸運(yùn)的人都能獲獎(jiǎng)任何幸運(yùn)的人都能獲獎(jiǎng)”( ( x)(Luck(x)Win(x,prizex)(Luck(x)Win(x,prize)結(jié)論：結(jié)論：“張是快樂(lè)的張是快樂(lè)的”的否定的否定 Happy(zhangHappy(zhang) )由由R1R1及邏輯轉(zhuǎn)換公式及邏輯轉(zhuǎn)換公式:PWH = :PWH = （PWPW） H H ，可得，可得(1)(1)Pass(xPass(x, computer), computer)Win(xWin(x, , prize)Happy(xprize)Happy(x) )由由R2R2： (2)(2)Study(y)Pass(y,