人工智能課件第4章

第四章推理方法

要使計算機具有智能，僅僅使它擁有知識還不夠，還必須使其具有運用知識進行推理，實現(xiàn)問題求解的能力。因此有關(guān)推理方法的研究是人工智能的重要課題之一。第四章推理方法要使計算機具有智能，僅僅使14.1推理概述4.1推理概述4.1.1推理的基本概念所謂推理是指從已知事實出發(fā)，運用已掌握的知識，推導(dǎo)出其中蘊涵的事實性結(jié)論或歸納出某些新的結(jié)論的過程。推理過程實際上也就是一個問題求解的過程。4.1推理概述4.1推理概述2推理概述4.1.2推理的方法及其分類1.按照推理的邏輯基礎(chǔ)分類（1）演繹推理演繹推理是從已知的一般性知識出發(fā)，推理出適合于某種個別情況的結(jié)論的過程。它是一種由一般到個別的推理方法。推理概述4.1.2推理的方法及其分類3例如：A.音樂系的學(xué)生至少會彈奏一種樂器；B.李聰是音樂系的學(xué)生；C.李聰至少會彈奏一種樂器。例如：4（2）歸納推理歸納推理是從大量特殊事例出發(fā)，歸納出一般性結(jié)論的推理過程，是一種由個別到一般的推理方法。其基本思想是：首先從已知事實中猜測出一個結(jié)論，然后對這個結(jié)論的正確性加以證明確認(rèn)，數(shù)學(xué)歸納法就是歸納推理的一種典型例子。（2）歸納推理5（3）默認(rèn)推理默認(rèn)推理又稱缺省推理，是在知識不完全的情況下假設(shè)某些已經(jīng)具備所進行的推理。（3）默認(rèn)推理62.按所用知識的確定性分類（1）確定性推理（2）不確定性推理2.按所用知識的確定性分類73.按推理過程的單調(diào)性分類（1）單調(diào)推理所謂單調(diào)推理是指在推理過程中，由于新知識的加入和使用，使推理所得到的結(jié)論會越來越接近于最終目標(biāo)，而不會出現(xiàn)反復(fù)情況，即不會由于新知識的加入否定了前面推出的結(jié)論，從而使推理過程又退回到前面的某一步。（2）非單調(diào)推理非單調(diào)推理則是指在推理過程中，當(dāng)某些新知識加入后，不但沒有加強已經(jīng)推出的結(jié)論，反而會否定原來已推出的結(jié)論，使推理過程要退回到先前的某一步，重新進行推理。3.按推理過程的單調(diào)性分類8

4.1.3推理的控制策略智能系統(tǒng)的推理過程其實就是問題求解的過程，它不僅依賴于所用的推理方法，同時也依賴于推理的控制策略。推理的控制策略包括推理方向、搜索策略、沖突消解策略、求解策略、限制策略；而推理方法則是推理控制策略確定之后，在進行具體推理時所要采取的匹配方法或不確定性傳遞算法等方法。4.1.3推理的控制策略91.正向推理

正向推理又稱為正向鏈接推理，它是一種數(shù)據(jù)驅(qū)動的推理方式，其推理基礎(chǔ)是邏輯演繹的推理鏈，它從一組表示事實的謂詞或命題出發(fā)，使用一組推理規(guī)則，來證明目標(biāo)謂詞公式或命題是否成立。

1.正向推理

正向推理又稱為正向鏈接推理，它是一種數(shù)據(jù)驅(qū)動10正向推理過程的算法描述：（1）把用戶提供的初始數(shù)據(jù)或已知事實放入到綜合數(shù)據(jù)庫。（2）檢查綜合數(shù)據(jù)庫中是否包含了問題的解，若有，則求解結(jié)束，并成功推出；否則執(zhí)行（3）；（3）檢查知識庫中是否有與綜合數(shù)據(jù)庫中已有事實相匹配的知識，若有，則將所有的匹配知識構(gòu)成當(dāng)前匹配知識集，轉(zhuǎn)（4）；否則轉(zhuǎn)（5）；（4）按照某種沖突消解策略，從當(dāng)前匹配知識集中選出一條知識作為啟用知識用于進行推理，并將推出的新事實或證據(jù)加入到綜合數(shù)據(jù)庫中，然后轉(zhuǎn)（2）；（5）詢問用戶是否可以進一步補充新的事實或證據(jù)，若可補充，則將補充的事實或證據(jù)加入綜合數(shù)據(jù)庫中，然后轉(zhuǎn)（3）；否則表示無解，失敗退出。正向推理過程的算法描述：11例如，有規(guī)則集如下：

規(guī)則1：IFP1THENP2

規(guī)則2：IFP2THENP3

規(guī)則3：IFP3THENq3

規(guī)則中的P1、P2、P3、q3可以是謂詞公式或命題。設(shè)總數(shù)據(jù)庫（工作存儲器）中已有事實P1，則應(yīng)用這三條規(guī)則進行正向推理，即從P1出發(fā)推導(dǎo)出q3的過程如下圖所示。例如，有規(guī)則集如下：

規(guī)則1：IFP1THEN122.反向推理（逆向推理）

反向推理又稱為后向鏈接推理，它是一種目標(biāo)驅(qū)動的推理方式，其基本原理是從表示目標(biāo)的謂詞或命題出發(fā)，使用一組規(guī)則證明事實謂詞或命題成立，即提出一批假設(shè)（目標(biāo)），然后逐一驗證這些假設(shè)。

2.反向推理（逆向推理）

反向推理又稱為后向鏈接推理13

首先假定目標(biāo)q3成立，由規(guī)則３（P3→q3），為證明q3成立，須先驗證P3是否成立；但總數(shù)據(jù)庫沒有事實P3，所以假定子目標(biāo)P3成立；由規(guī)則２（P2→P3），應(yīng)驗證P2；同樣，由于數(shù)據(jù)庫中沒有事實P2，假定子目標(biāo)P2成立；由規(guī)則１（P1→P2），為驗證P2成立，須先驗證P1。因為數(shù)據(jù)庫中有事實P1，所以假定的目標(biāo)P2成立，因而P3成立，最終導(dǎo)出結(jié)論q3確實成立。舉例如下：仍用上述的三條規(guī)則為例，應(yīng)用反向推理方法，從P1出發(fā)推導(dǎo)出q3的過程如下圖所示：首先假定目標(biāo)q3成立，由規(guī)則３（P3→q3），為證明q14總之，反向推理的具體實現(xiàn)策略是：先假定一個可能的目標(biāo)，系統(tǒng)試圖證明它，看此假設(shè)目標(biāo)是否在總數(shù)據(jù)庫中，若在，則假設(shè)成立。否則，看這些假設(shè)是否證據(jù)（葉子）結(jié)點，若是，向用戶詢問，若不是，則再假定另一個目標(biāo)，即找出結(jié)論部分中包含此假設(shè)的那些規(guī)則，把它們的前提作為新的假設(shè)，試圖證明它。這樣周而復(fù)始，直到所有目標(biāo)被證明，或所有路徑被測試。

總之，反向推理的具體實現(xiàn)策略是：先假定一個可能的目標(biāo)，153.雙向推理

雙向推理又稱為正反向混合推理，它綜合了正向推理和逆向推理的長處，克服了了兩者的短處。雙向推理的推理策略是同時從目標(biāo)向事實推理和從事實向目標(biāo)推理，并在推理過程中的某個步驟，實現(xiàn)事實與目標(biāo)的匹配。具體的推理策略有多種。例如，通過數(shù)據(jù)驅(qū)動幫助選擇某個目標(biāo)，即從初始證據(jù)（事實）出發(fā)進行正向推理，同時以目標(biāo)驅(qū)動求解該目標(biāo)，通過交替使用正逆向混合推理對問題進行求解。雙方推理的控制策略比前兩種方法都要復(fù)雜。美國斯坦福研究所人工智能中心研制的基于規(guī)則的專家系統(tǒng)工具KAS，就是采用正、逆向混合推理的產(chǎn)生式系統(tǒng)的一個典型例子。

下圖給出雙向混合推理過程的示意圖。3.雙向推理

雙向推理又稱為正反向混合推理，它綜合了正向16

4.1.2推理的沖突消解策略在利用推理求解問題的過程中，如果綜合數(shù)據(jù)庫中的已知事實與知識庫中的多條知識相匹配，或者有多個已知事實都可與知識庫中的某一條知識相匹配，或者有多個已知事實與知識庫中的多條知識相匹配，則稱這種情況為知識沖突。此時，需要按照某種策略從這多條匹配的知識中選擇一條最佳知識用于推理，這種解決沖突的過程稱為沖突消解。4.1.2推理的沖突消解策略17（1）按就近原則排序（2）按知識特殊性排序（3）按上下文限制排序（4）按知識的新鮮性排序（5）按知識的差異性排序（6）按領(lǐng)域知識的特點排序（7）按規(guī)則的次序排序（8）按前提條件的規(guī)模排序

（1）按就近原則排序184.2命題邏輯命題邏輯與謂詞邏輯是最先應(yīng)用于人工智能的兩種邏輯，對于知識的形式化表示，特別是定理的自動證明發(fā)揮了重要作用，在人工智能的發(fā)展史中占有重要地位。謂詞邏輯是在命題邏輯的基礎(chǔ)上發(fā)展起來的，命題邏輯可看作是謂詞邏輯的一種特殊形式，在討論謂詞邏輯之前，先來介紹命題邏輯的基本概念。4.2命題邏輯命題邏輯與謂詞邏輯是最先應(yīng)用于人194.2.1命題

定義3.1能夠分辨真假的語句稱做命題。定義3.2

一個語句如果不能再進一步分解成更簡單的語句，并且又是一個命題，則稱此命題為原子命題。原子命題是命題中的基本單位。命題，比如“太陽從東邊升起”，“雪是白的”4.2.1命題204.2.2命題公式1.連接詞命題邏輯中，可以通過連接詞將一些原子命題連接起來，構(gòu)成復(fù)合命題，以表示復(fù)雜的定義。

～稱為“非”或“否定”。

∨稱為“析取”。表示被它連接的兩個命題具有“或”的關(guān)系。

4.2.2命題公式21

∧稱為“合取”。表示被它連接的兩個命題具有“與”的關(guān)系。

→稱為“條件”或“蘊涵”.P→Q表示“P蘊涵Q”，即“如果P，則Q”，其中P為條件的前提，Q為條件的后件。

?稱為“雙條件”.P?Q表示“P當(dāng)且僅當(dāng)Q”∧稱為“合取”。表示被它連接的兩個命題具有“與”的22AI的產(chǎn)生及主要學(xué)派2.命題公式定義4.3下面的遞歸形式給出命題公式的定義：（1）原子公式是命題公式（2）A是命題公式，則～A也是命題公式；（3）若A和B都是命題公式，則A∧B，A∨B，A→B，A?B也都是命題公式（4）只有（1）～（3）所得的公式才是命題公式。AI的產(chǎn)生及主要學(xué)派2.命題公式234.3謂詞邏輯3.3.1謂詞與個體在謂詞邏輯中，將原子命題分解為謂詞與個體兩部分。例如，“貝多芬是作曲家”中，“是作曲家”是謂詞，“貝多芬”是個體。所謂個體是指可以獨立存在的物體，它可以是抽象的，也可以是具體的。例如，“李白是詩人”這個命題，若用poet表示“是詩人”，用Libai表示個體“李白”，則得到的謂詞是poet(Libai).又如，5>3,這個不等式可用謂詞表示為greater(5,3)4.3謂詞邏輯3.3.1謂詞與個體24謂詞的一般形式是：

P（x1,x2,…,xn）其中P是謂詞，x1,x2,…,xn是個體。

例如，“小劉的哥哥是工人”，可以表示為worker(brother(Liu)),其中brother(Liu)是一個函數(shù)。個體常數(shù)，變量和函數(shù)統(tǒng)稱為項。謂詞的一般形式是：25謂詞中包含的個體數(shù)目稱為謂詞的元數(shù)，例如P(x)是一元謂詞，P(x,y)是二元謂詞，而P(x1,x2,…,xn)是n元謂詞。在謂詞P(x1,x2,…,xn)中，若xi(i=1,2,…,n)都是個體常量、變元或函數(shù)，則稱它為一階謂詞。如果xi本身又是一個一階謂詞，則稱它為二階謂詞，依次類推。謂詞和函數(shù)從形式上看很相似，其實它們有著本質(zhì)的區(qū)別，是兩個完全不同的概念。謂詞具有邏輯值“真”或“假”，而函數(shù)則是某個個體到另一個個體之間的映射。謂詞中包含的個體數(shù)目稱為謂詞的元數(shù)，例如P(x)是263.3.2謂詞公式1.連接詞與命題邏輯中相同。2.量詞全稱量詞（?x）表示“對于個體域中的所有個體x”；存在量詞(?x)表示“在個體域中存在個體x”.3.3.2謂詞公式273.謂詞演算公式

定義4.4謂詞演算中，由某個謂詞構(gòu)成的不含任何連接詞的公式，叫做原子謂詞公式。一般一個形如F(x1,x2,…,xn)的謂詞公式，稱作原子謂詞公式，或簡稱原子，其中F為n元謂詞，而x1,x2,…,xn為個體變元。3.謂詞演算公式28定義4.5可按下列規(guī)則得到謂詞演算的合式公式如下：(1)原子謂詞公式是合式公式；(2)A是合式公式，則～A也是合式公式；(3)若A和B都是合式公式，則A∧B，A∨B，A→B，A?B也都是合式公式(4)若A是合式公式，x是一個體變元，則(?x)A和(?x)A也都是合式公式(5)只有(1)～(4)所得的公式才是合式公式。定義4.5可按下列規(guī)則得到謂詞演算的合式公式如下：29謂詞演算公式就是一個按照一定規(guī)則由原子公式、連接詞、量詞及圓括號所組成的字符串。例如：

(?x)P(x,y),(?x)(P(x)∨P(y))謂詞演算公式就是一個按照一定規(guī)則由原子公式、連接30

4.謂詞轄域與約束變元在一個公式中，如果有量詞出現(xiàn)，位于量詞后面的單個量詞或者用括弧括起來的合式公式稱為量詞的轄域。在轄域內(nèi)與量詞中同名的變元稱為約束變元，不受約束的變元稱為自由變元。4.謂詞轄域與約束變元31

3.3.3謂詞公式的永真性與可滿足性1.謂詞公式的解釋定義4.6設(shè)D為謂詞公式P的個體域，若對P中的個體常量、函數(shù)和謂詞按照下列規(guī)定賦值：（1）為每個個體常量指派D中的一個元素；（2）為每個n元函數(shù)指派一個從Dn到D的映射，其中Dn＝{(x1,x2,…,xn)|x1,x2,…,xn∈D}（3）為每個n元謂詞指派一個從Dn到{F,T}的映射；則稱這些指派為公式P在D上的一個解釋。3.3.3謂詞公式的永真性與可滿足性32一般情況下，謂詞公式的真值都是針對某一解釋而言的。同一個公式可能在一種解釋下其真值是T，而在另一種解釋下，其真值是F。一般情況下，謂詞公式的真值都是針對某一解釋而言的。同一個33

2.謂詞公式的永真性定義4.7如果謂詞公式P，對個體域D上的任何一個解釋都取得真值T，則稱P在D上是永真的；如果P在每個非空個體域上均永真，則稱P永真。定義4.8如果謂詞公式P，對個體域D上的任何一個解釋都取得真值F，則稱P在D上是永假的；如果P在每個非空個體域上均永假，則稱P永假。謂詞公式的永假性又稱為不可滿足性或不相容性。2.謂詞公式的永真性343.謂詞公式的可滿足性定義4.9對于謂詞公式P，如果至少存在一個解釋使得公式P在此解釋下的真值為T，則稱公式P是可滿足的。如果不存在任何解釋，使得P的取值為T，則稱公式P是不可滿足的。3.謂詞公式的可滿足性353.3.4謂詞公式的等價性與永真蘊涵定義4.10設(shè)P和Q是兩個謂詞公式，D為它們共同的個體域。若對D上的任何一個解釋，P與Q的取值都相同，則公式P和Q在域D上是等價的。如果D是任意個體域，則稱P和Q是等價的，記做P?Q。3.3.4謂詞公式的等價性與永真蘊涵36常用的等價式：交換律P∧Q?Q∧PP∨Q?Q∨P結(jié)合律(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)狄.摩根定律～(P∨Q)?～P∧～Q～(P∧Q)?～P∨～Q否定之否定定律～(～P)?P

常用的等價式：37吸收律P∨(P∧Q)?P

P∧(P∨Q)?P補余律P∨～P?TP∧～P?F逆否定律P→Q?～Q→～P

連接詞化歸律P→Q?～P∨Q

P?Q?(P→Q)∧(Q→P)

P?Q?(P∧Q)∨(～P∧～Q)吸收律P∨(P∧Q)?P38量詞轉(zhuǎn)換律～(?x)P?(?x)(～P)

～(?x)P?(?x)(～P)量詞分配律(?x)(P∧Q)?(?x)P∧(?x)Q

(?x)(P∨Q)?(?x)P∨(?x)Q量詞轉(zhuǎn)換律～(?x)P?(?x)(～P)39定義4.11對于謂詞公式P和Q，如果P→

Q永真，則稱P永真蘊涵Q，且稱Q為P的邏輯結(jié)論，稱P為Q的前提，記作P?Q。下面是一些常用到的永真蘊涵式：化簡式

P∧Q?P

P∧Q?Q附加式

P?P∨Q

Q?P∨Q

析取三段論～P，P∨Q?Q

假言推理

P，P→

Q?Q

拒取式～Q，P→

Q?～P

假言三段論

P→Q，Q→R?P→R

二難推論

P∨Q，P→R，Q→R?R

定義4.11對于謂詞公式P和Q，如果P→Q永真，則稱P40全稱固化

(?x)(P(x))?P(y),其中y是個體域上的任一個體，利用此永真蘊涵式可以消去公式中的全稱量詞

存在固化

(?x)(P(x))?P(y),其中y是個體域中某個使P(y)為真的個體，利用此式可以消去公式中的存在量詞全稱固化(?x)(P(x))413.3.5置換與合一1.置換定義4.12置換是形如{t1/x1,t2/x2,…,tn/xn}的一個有限集。其中，xi是變量，ti是不同于xi的項（常量、變量、函數(shù)），且xi≠xj(i≠j),i,j=1,2,…,n.例如：{a/x,b/y,f(x)/z},{f(z)/x,y/z}

3.3.5置換與合一422.合一定義4.13設(shè)有公式集{E1,E2,…,En}和置換θ，使E1θ=E2θ=…=Enθ便稱E1，E2，…En是可合一的，且θ稱為合一置換。定義4.14若E1，E2，…En有合一置換σ，且對E1，E2，…En的任一置換θ都存在一個置換λ，使得

θ=σ×

λ，則稱σ為E1，E2，…En的最一般合一置換，記為mgu。2.合一43例若E1＝Q(y)，E2=Q(z),對E1和E2來說，σ={y/z}和σ={z/y}都是它們的最一般合一置換。例若E1＝Q(y)，E2=Q(z),對E1和E2來說444.5.1謂詞公式與字句集1.范式（1）前束形范式一個謂詞公式，如果它的所有量詞均非否定地出現(xiàn)在公式的最前面，且它的轄域一直延伸到公式之末，同時公式中不出現(xiàn)連接詞→及?，這種形式的公式稱做前束形范式。例如：(?x)(?x)(?z)(P(x)∧F(y,x)∧Q(y,x))4.5.1謂詞公式與字句集45（2）斯克林（skolem）范式為了克服前束性范式的缺點，斯可林對它進行了改進，使前束性范式的首標(biāo)不出現(xiàn)存在量詞。從前束性范式中消去全部存在量詞所得到公式即為斯克林（skolem）范式，或稱skolem標(biāo)準(zhǔn)型。（2）斯克林（skolem）范式46將謂詞公式G化為skolem標(biāo)準(zhǔn)型的步驟如下：(1)消去謂詞公式G中的蘊涵→及雙條件?，以～A∨B代替A→B，以（A∧B）∨（～A∧～B）替換A?B(2)減少否定負(fù)號～的轄域，使否定符號～最多只作用到一個謂詞上。(3)重新命名變元名，使所有的變元的名字均不同，并且自由變元及約束變元亦不同。將謂詞公式G化為skolem標(biāo)準(zhǔn)型的步驟如下：47(4)消去存在量詞。分兩種情況，一種使存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)，此時，只要用一個新的個體變量替換該存在量詞約束的變元，就可以消去存在量詞；另一中情況是，存在量詞位于一個或多個全稱量詞的轄域內(nèi)，比如(?x1)(?x2)…(?xn)(?y)P(x1,x2,…,xn,y)此時變元y實際受前面的變元x1,x2,…,xn的約束，需要用Skolem函數(shù)f(x1,x2,…,xn)替換y即可將存在量詞y消去，得到(?x1)(?x2)…(?xn)(?y)P(x1,x2,…,xn,f(x1,x2,…,xn))(4)消去存在量詞。分兩種情況，一種使存在量詞不出現(xiàn)在全稱48(5)把全稱量詞全部移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。(6)母式化為合取范式：任何母式都可以寫成由一些謂詞公式否定的析取的有限集組成的合取。(5)把全稱量詞全部移到公式的左邊，并使每個量詞的轄域包括49例：將謂詞公式G=(?x)(?y)P(x,y)→～(?y)(Q(x,y)→R(x,y))化為Skolem標(biāo)準(zhǔn)型。解：（1）消去→及?連接詞。(?x)(~(?y)P(x,y)∨～(?y)(~Q(x,y)∨R(x,y)))（2）把～的轄域減少到最多只作用于一個謂詞。(?x)((?y)~P(x,y)∨(?y)(Q(x,y)∧～R(x,y)))（3）變量更名(?x)((?y)~P(x,y)∨(?z)(Q(x,z)∧～R(x,z)))例：將謂詞公式G=(?x)(?y)P(x,y)→50（4）消去存在量詞。因為存在量詞(?y)和(?z)都在轄域(?x)內(nèi)，屬于上述所講的第二種情況，所以分別用skolem函數(shù)f(x)和g(x)替換y和z。(?x)(~P(x,f(x))∨(Q(x,g(x))∧～R(x,g(x))))（5）全稱量詞移到左邊。由于只有一個全稱量詞(?x)，已在左邊，所以不移。（6）將母式化為合取范式。(?x)((~P(x,f(x))∨(Q(x,g(x))∧(~P(x,f(x))～R(x,g(x))))（4）消去存在量詞。因為存在量詞(?y)和(?z)都在轄域(512.字句與字句集定義4.16不含有任何連接詞的謂詞公式稱作原子公式，簡稱原子，而原子或原子的否定統(tǒng)稱為文字。例如：P(x),~P(x,c),R(x,y)定義4.17字句就是由一些文字組成的析取式。例如：P(x)∨~Q(x,y),~P(x,c)∨R(x,y,f(x))定義4.18不含有任何文字的字句稱為空子句，記做NIL。由于空子句不含有任何文字，它不能被任何解釋所滿足，所以空子句是永假的，不可滿足的。2.字句與字句集52定義4.19由字句構(gòu)成的集合稱為字句集。謂詞公式skolem標(biāo)準(zhǔn)型的母式是由一些字句的合取組成的。如果將謂詞公式G的skolem標(biāo)準(zhǔn)型前面的全稱量詞全部消去，并用逗號代替合取符號，便可得到謂詞公式G的字句集S。定義4.19由字句構(gòu)成的集合稱為字句集。533.不可滿足意義下的一致性公式G與其字句集S并不等價，但它們在不可滿足的意義下是一致的。定理4.2設(shè)有謂詞公式G，而其相應(yīng)的字句集為S，則G是不可滿足的充分必要條件是S是不可滿足的。3.不可滿足意義下的一致性544.5.2Herbrand理論1.H域定義4.20設(shè)謂詞公式G的字句集為S，則按下述方法構(gòu)造的個體變元域H∞稱為公式集或字句集S的Herbrand域，簡稱H域。（1）令H0為S中所出現(xiàn)的常量的集合。若S中沒有常量出現(xiàn)，就任取一個常量a∈D,規(guī)定H0＝{a}。（2）令Hi+1=Hi∪{S中所有的形如f(t1,t2,…,tn)的元素}其中，f(t1,t2,…,tn)是出現(xiàn)于G中的任一函數(shù)負(fù)號，而t1,t2,…,tn是Hi中的元素。這里i=1,2,…,n4.5.2Herbrand理論554.5.3歸結(jié)原理歸結(jié)原理又稱為消解原理，是Robinson提出的證明字句集不可滿足性，從而實現(xiàn)了定理證明的一種理論和方法。定義4.25若P是原子謂詞公式或原子命題，則稱P與～P為互補文字。4.5.3歸結(jié)原理561.命題邏輯中的歸結(jié)原理(1)歸結(jié)與歸結(jié)式定義3.26設(shè)C1與C2式字句集中的任意兩個子句，如果C1中的文字L1與C2中文字L2互補，則從C1和C2中可以分別消去L1和L2，并將兩個子句余下的部分做析取構(gòu)成一個新的子句C12，稱這一過程為歸結(jié)，所得到的子句C12為C1和C2的歸結(jié)式，而稱C1和C2為C12的親本子句。歸結(jié)過程是一種推理規(guī)則，即C1∧C2→

C121.命題邏輯中的歸結(jié)原理57定理3.6歸結(jié)式C12是其親本子句C1和C2的邏輯結(jié)論。推論設(shè)C1和C2是子句集S上的子句，C12是C1和C2的歸結(jié)式。如果把C12加入到子句集S得到新的子句集S1，則S1和S在不可滿足的意義下是等價的。定理3.6歸結(jié)式C12是其親本子句C1和C2的邏輯結(jié)論。58(2)歸結(jié)推理過程由上面的推論以及空子句的不可滿足性，可以得出證明子句集S不可滿足性的推理過程如下：A對子句集S中的各子句間使用歸結(jié)推理規(guī)則。B將歸結(jié)所得的歸結(jié)式放入子句集S中，得到新的子句集S’。C檢查子句集S’中是否有空子句，若有，則停止推理；否則轉(zhuǎn)步驟D。D置S＝S’，轉(zhuǎn)步驟A。(2)歸結(jié)推理過程59例4.14證明子句集S={~P∨Q,~Q,P}是不可滿足的。證明：(1)~P∨Q(2)~Q(3)P(4)~P(1)和(2)歸結(jié)(5)NIL(3)和(4)歸結(jié)例4.14證明子句集S={~P∨Q,~Q,P}是不可602.一階謂詞邏輯中的歸結(jié)原理在一階謂詞邏輯中，由于子句中含有變元，所以不能像命題邏輯中那樣可以直接消去互補文字進行子句歸結(jié)。而是要首先使用置換與合一的思想，對子句中的某些變元進行合一置換，對置換后的新子句再次使用歸結(jié)規(guī)則。2.一階謂詞邏輯中的歸結(jié)原理61定義4.27設(shè)C1與C2是兩個沒有相同變元的子句，L1和L2分別為C1和C2的文字，如果L1與～L2有mguσ,則把C12＝(C1σ-{L1σ})∪(C2σ-{L2σ})，稱作子句C1和C2的一個二元歸結(jié)式，而L1和L2是被歸結(jié)的文字。定義4.27設(shè)C1與C2是兩個沒有相同變元的子句，L1和L62在謂詞邏輯中，對子句進行歸結(jié)推理時，要注意以下幾個問題：（1）若被歸結(jié)的子句C1和C2中具有相同的變元，則需要將其中一個子句的變元更名；否則可能無法作合一置換，從而沒有辦法進行歸結(jié)。在謂詞邏輯中，對子句進行歸結(jié)推理時，要注意以下幾個63（2）在求歸結(jié)式時，不能同時消去兩個互補文字時，消去兩個互補文字對所得的結(jié)果不是兩個親本子句的邏輯推論。例：C1＝P∨QC2＝～P∨～Q（2）在求歸結(jié)式時，不能同時消去兩個互補文字時，消去兩個互補64（3）如果在參加歸結(jié)的子句內(nèi)含有可合一的文字，則在進行歸結(jié)之前，應(yīng)對這些文字進行合一，以實現(xiàn)這些子句內(nèi)部的簡化。例：C1=P(x)∨P(f(a))∨Q(x)C2=~P(x)∨R(b)用它們最一般合一θ={f(a)/x}進行置換得到C1θ=P(f(a))∨Q(f(a))再對C1θ和C2進行歸結(jié)，選用mgu為σ={f(a)/x},得到C1和C2的二元歸結(jié)式為C12＝R(b)∨Q(f(a))（3）如果在參加歸結(jié)的子句內(nèi)含有可合一的文字，則在進行歸結(jié)之65定義4.28設(shè)C1與C2是沒有相同變元的子句，則下列四種二元歸結(jié)式都叫做C1與C2的歸結(jié)式，仍記做C12。（1）C1與C2的二元歸結(jié)式。（2）C1的因子C1σ1與C2的二元歸結(jié)式。（3）C1與C2的因子C2σ2的二元歸結(jié)式。（4）C1的因子C1σ1與C2的因子C2σ2的二元歸結(jié)式。定義4.28設(shè)C1與C2是沒有相同變元的子句，則下列四種二664.5.4利用歸結(jié)原理進行定理證明設(shè)要證明的定理可用謂詞公式表示為如下的形式A1∧A2∧…∧An→B，應(yīng)用歸結(jié)原理進行定理證明的步驟如下：

(1)首先否定結(jié)論B，并將否定后的公式～B與前提公式集組成如下形式的謂詞公式：G=A1∧A2∧…∧An∧～B

(2)求謂詞公式G的子句集S。(3)應(yīng)用歸結(jié)原理，證明子句集S的不可滿足性，從而證明謂詞公式G的不可滿足性。這就說明對結(jié)論B的否定是錯誤的，推斷出定理的成立。4.5.4利用歸結(jié)原理進行定理證明67例4.18已知：A：(?x)((?y)~P(x,y)∧Q(y))→

(?y)(R(y)∧T(x,y)))B:～(?x)R(x)→((?y)~P(x,y)∧Q(y))→

(?x)(?y)P(x,y)→～Q(y))證明：例4.18已知：68首先將A和～B化為子句集。(1)~P(x,y)∨～Q(y)∨R(f(x))(2)~P(x,y)∨～Q(y)∨T(x,f(x))(3)~R(z)(4)P(a,b)(5)Q(b)下面進行歸結(jié)：(6)~P(x,y)∨～Q(y)(1)與(3)進行歸結(jié)(7)～Q(b)(4)與(6)進行歸結(jié)(8)NIL(5)與(7)進行歸結(jié)首先將A和～B化為子句集。694.5.5利用歸結(jié)原理進行問題求解歸結(jié)原理不僅可以應(yīng)用于定理證明，而且也可以用來求取問題的答案，其步驟如下：(1)把已知前提條件用謂詞公式表示出來，并化為相應(yīng)的子句集，設(shè)該子句集的名字為S1。(2)把待求解的問題也用謂詞公式表示出來，然后將其否定，并與一謂詞ANSWER構(gòu)成析取式。謂詞ANSWER是一個專為求解問題而設(shè)置的謂詞，其變量必須與問題公式的變量完全一致。4.5.5利用歸結(jié)原理進行問題求解70(3)把問題公式與謂詞ANSWER構(gòu)成的析取式化為子句集，并把該子句集與S1后并構(gòu)成子句集S。(4)對子句集S應(yīng)用謂詞歸結(jié)原理進行歸結(jié)，再歸結(jié)過程中，通過合一置換，改變ANSWER中的變元。(5)如果得到歸結(jié)式ANSWER，則問題的答案即在ANSWER謂詞中。(3)把問題公式與謂詞ANSWER構(gòu)成的析取式化為子句集，71例：某人被盜，公安局派出所派出5個偵察員去調(diào)查。研究案情時，偵察員A說“趙與錢中至少有一人作案”；偵察員B說“錢與孫中至少有一人作案”；偵察員C說“孫與李中至少有一人作案”；偵察員D說“趙與孫中至少有一人與此案無關(guān)”；偵察員E說“錢與李中至少有一人與此案無關(guān)”。如果5個偵察員的話都是可信的，試問誰是盜竊犯呢？例：某人被盜，公安局派出所派出5個偵察員去調(diào)查。研究案情時，72解：第一步將5個偵察員的話表示成謂詞公式，為此先定義謂詞。設(shè)謂詞P(x)表示作案者，則根據(jù)題意：A：P(zhao)∨P(qian)B：P(qian)∨P(sun)C：P(sun)∨P(li)D：~P(zhao)∨~P(sun)E：~P(qian)∨~P(li)第二步將待求問題表示成謂詞。設(shè)y為盜竊犯，則~P(y)∨ANSWER(y)解：73第三步求前提條件及~P(y)∨ANSWER(y)的子句集，并將各子句列表如下：(1)P(zhao)∨P(qian)(2)P(qian)∨P(sun)(3)P(sun)∨P(li)(4)~P(zhao)∨~P(sun)(5)~P(qian)∨~P(li)(6)~P(y)∨ANSWER(y)第三步求前提條件及~P(y)∨ANSWER(y)的子句集74第四步應(yīng)用歸結(jié)原理進行推理(7)P(qian)∨～P(sun)(1)和(4)歸結(jié)(8)P(zhao)∨~P(li)(1)和(5)歸結(jié)(9)P(qian)∨~P(zhao)(2)和(4)歸結(jié)(10)P(sun)∨～P(li)(2)和(5)歸結(jié)(11)～P(zhao)∨P(li)(3)和(4)歸結(jié)(12)P(sun)∨～P(qian)(3)和(5)歸結(jié)(13)P(qian)(2)和(7)歸結(jié)(14)P(sun)(2)和(12)歸結(jié)(15)ANSWER(qian)(6)和(13)歸結(jié)(16)ANSWER(sun)(6)和(14)歸結(jié)所以，本題的盜竊犯是兩個人：錢和孫第四步應(yīng)用歸結(jié)原理進行推理754.6歸結(jié)過程中的控制策略4.6.1引入控制策略1.引入控制策略的原因?qū)ψ泳浼疭進行歸結(jié)時，首先要從子句集中找出可進行歸結(jié)的一對子句進行歸結(jié)。如果采用盲目的歸結(jié)策略，會產(chǎn)生大量的無用的歸結(jié)式，而且歸結(jié)式還會重復(fù)出現(xiàn)，這不僅浪費計算機的存儲空間，而且要浪費大量的計算時間，如果子句集的規(guī)模較大的情況下，這種浪費是驚人的。4.6歸結(jié)過程中的控制策略4.6.1引入控制策略762.控制策略分類歸結(jié)策略大致可以分為兩大類：第一類是刪除策略。主要是通過刪除某些無用的子句來縮小歸結(jié)的范圍，從而提高歸結(jié)效率；另一類是限制策略，是通過對參加歸結(jié)的子句進行種種限制，盡可能地減少歸結(jié)的盲目性，使其盡快歸結(jié)出空子句。2.控制策略分類774.6.2歸結(jié)控制策略1.刪除策略（1）純文字刪除法如果文字L出現(xiàn)在S中，而～L不出現(xiàn)在S中，便說L為S的純文字。顯然歸結(jié)過程中，純文字是不可能被消去的，因而包含它的子句進行歸結(jié)時，不可能得到空子句，即這樣的子句對歸結(jié)是毫無意義的，所以可以把它所在的子句從子句集中刪除。4.6.2歸結(jié)控制策略78（2）重言式刪除法如果一個子句中同時包含互補文字時，則稱該子句為重言式。重言式是取值用真的子句。因此可以從子句集中刪除。（3）包孕刪除法設(shè)有子句C1和C2，如果存在一個置換σ，使C1σ∈C2，則稱C1包孕于C2。把子句集中包孕的子句刪去后，不會影響子句集的不可滿足性，因而可從子句集中刪去那些被包孕的子句。（2）重言式刪除法792.線性歸結(jié)策略線性歸結(jié)策略對參加歸結(jié)的子句提出如下限制：首先從子句集S中先取一個稱作頂子句的的子句C0開始作歸結(jié)；其次將歸結(jié)過程中所得到的歸結(jié)式Ci立即同另一子句Bi進行歸結(jié)，得歸結(jié)式Ci+1,而Bi是原子子句S中一個子句或是已經(jīng)歸結(jié)出的某個歸結(jié)式Cj（j<i）。2.線性歸結(jié)策略803.單文字（單元）歸結(jié)策略如果一個子句只含有一個文字，則稱該子句為單文字子句或單元子句。如果歸結(jié)過程中，每次歸結(jié)都有一個子句是單文字子句，則稱這種歸結(jié)就是單文字歸結(jié)。也就是說，單文字歸結(jié)策略要求參加歸結(jié)的兩個子句中至少有一個是單文字子句。用單文字歸結(jié)策略時，歸結(jié)式將比親本子句含有較少的文字，這有利于朝著空子句的方向前進，因此它有較高的效率。3.單文字（單元）歸結(jié)策略814.輸入歸結(jié)策略輸入歸結(jié)策略對參加歸結(jié)的子句有如下限制：參加歸結(jié)的兩個子句中，必須至少有一個子句是初始子句集中的子句。本歸結(jié)策略是不完備的，也就是說，該子句集S是不可滿足的，用該歸結(jié)原理進行歸結(jié)時，也不一定能歸結(jié)出空子句。但是，輸入歸結(jié)策略具有簡單高效的優(yōu)點。4.輸入歸結(jié)策略82人工智能課件第4章83第四章推理方法

要使計算機具有智能，僅僅使它擁有知識還不夠，還必須使其具有運用知識進行推理，實現(xiàn)問題求解的能力。因此有關(guān)推理方法的研究是人工智能的重要課題之一。第四章推理方法要使計算機具有智能，僅僅使844.1推理概述4.1推理概述4.1.1推理的基本概念所謂推理是指從已知事實出發(fā)，運用已掌握的知識，推導(dǎo)出其中蘊涵的事實性結(jié)論或歸納出某些新的結(jié)論的過程。推理過程實際上也就是一個問題求解的過程。4.1推理概述4.1推理概述85推理概述4.1.2推理的方法及其分類1.按照推理的邏輯基礎(chǔ)分類（1）演繹推理演繹推理是從已知的一般性知識出發(fā)，推理出適合于某種個別情況的結(jié)論的過程。它是一種由一般到個別的推理方法。推理概述4.1.2推理的方法及其分類86例如：A.音樂系的學(xué)生至少會彈奏一種樂器；B.李聰是音樂系的學(xué)生；C.李聰至少會彈奏一種樂器。例如：87（2）歸納推理歸納推理是從大量特殊事例出發(fā)，歸納出一般性結(jié)論的推理過程，是一種由個別到一般的推理方法。其基本思想是：首先從已知事實中猜測出一個結(jié)論，然后對這個結(jié)論的正確性加以證明確認(rèn)，數(shù)學(xué)歸納法就是歸納推理的一種典型例子。（2）歸納推理88（3）默認(rèn)推理默認(rèn)推理又稱缺省推理，是在知識不完全的情況下假設(shè)某些已經(jīng)具備所進行的推理。（3）默認(rèn)推理892.按所用知識的確定性分類（1）確定性推理（2）不確定性推理2.按所用知識的確定性分類903.按推理過程的單調(diào)性分類（1）單調(diào)推理所謂單調(diào)推理是指在推理過程中，由于新知識的加入和使用，使推理所得到的結(jié)論會越來越接近于最終目標(biāo)，而不會出現(xiàn)反復(fù)情況，即不會由于新知識的加入否定了前面推出的結(jié)論，從而使推理過程又退回到前面的某一步。（2）非單調(diào)推理非單調(diào)推理則是指在推理過程中，當(dāng)某些新知識加入后，不但沒有加強已經(jīng)推出的結(jié)論，反而會否定原來已推出的結(jié)論，使推理過程要退回到先前的某一步，重新進行推理。3.按推理過程的單調(diào)性分類91

4.1.3推理的控制策略智能系統(tǒng)的推理過程其實就是問題求解的過程，它不僅依賴于所用的推理方法，同時也依賴于推理的控制策略。推理的控制策略包括推理方向、搜索策略、沖突消解策略、求解策略、限制策略；而推理方法則是推理控制策略確定之后，在進行具體推理時所要采取的匹配方法或不確定性傳遞算法等方法。4.1.3推理的控制策略921.正向推理

正向推理又稱為正向鏈接推理，它是一種數(shù)據(jù)驅(qū)動的推理方式，其推理基礎(chǔ)是邏輯演繹的推理鏈，它從一組表示事實的謂詞或命題出發(fā)，使用一組推理規(guī)則，來證明目標(biāo)謂詞公式或命題是否成立。

1.正向推理

正向推理又稱為正向鏈接推理，它是一種數(shù)據(jù)驅(qū)動93正向推理過程的算法描述：（1）把用戶提供的初始數(shù)據(jù)或已知事實放入到綜合數(shù)據(jù)庫。（2）檢查綜合數(shù)據(jù)庫中是否包含了問題的解，若有，則求解結(jié)束，并成功推出；否則執(zhí)行（3）；（3）檢查知識庫中是否有與綜合數(shù)據(jù)庫中已有事實相匹配的知識，若有，則將所有的匹配知識構(gòu)成當(dāng)前匹配知識集，轉(zhuǎn)（4）；否則轉(zhuǎn)（5）；（4）按照某種沖突消解策略，從當(dāng)前匹配知識集中選出一條知識作為啟用知識用于進行推理，并將推出的新事實或證據(jù)加入到綜合數(shù)據(jù)庫中，然后轉(zhuǎn)（2）；（5）詢問用戶是否可以進一步補充新的事實或證據(jù)，若可補充，則將補充的事實或證據(jù)加入綜合數(shù)據(jù)庫中，然后轉(zhuǎn)（3）；否則表示無解，失敗退出。正向推理過程的算法描述：94例如，有規(guī)則集如下：

規(guī)則1：IFP1THENP2

規(guī)則2：IFP2THENP3

規(guī)則3：IFP3THENq3

規(guī)則中的P1、P2、P3、q3可以是謂詞公式或命題。設(shè)總數(shù)據(jù)庫（工作存儲器）中已有事實P1，則應(yīng)用這三條規(guī)則進行正向推理，即從P1出發(fā)推導(dǎo)出q3的過程如下圖所示。例如，有規(guī)則集如下：

規(guī)則1：IFP1THEN952.反向推理（逆向推理）

反向推理又稱為后向鏈接推理，它是一種目標(biāo)驅(qū)動的推理方式，其基本原理是從表示目標(biāo)的謂詞或命題出發(fā)，使用一組規(guī)則證明事實謂詞或命題成立，即提出一批假設(shè)（目標(biāo)），然后逐一驗證這些假設(shè)。

2.反向推理（逆向推理）

反向推理又稱為后向鏈接推理96

首先假定目標(biāo)q3成立，由規(guī)則３（P3→q3），為證明q3成立，須先驗證P3是否成立；但總數(shù)據(jù)庫沒有事實P3，所以假定子目標(biāo)P3成立；由規(guī)則２（P2→P3），應(yīng)驗證P2；同樣，由于數(shù)據(jù)庫中沒有事實P2，假定子目標(biāo)P2成立；由規(guī)則１（P1→P2），為驗證P2成立，須先驗證P1。因為數(shù)據(jù)庫中有事實P1，所以假定的目標(biāo)P2成立，因而P3成立，最終導(dǎo)出結(jié)論q3確實成立。舉例如下：仍用上述的三條規(guī)則為例，應(yīng)用反向推理方法，從P1出發(fā)推導(dǎo)出q3的過程如下圖所示：首先假定目標(biāo)q3成立，由規(guī)則３（P3→q3），為證明q97總之，反向推理的具體實現(xiàn)策略是：先假定一個可能的目標(biāo)，系統(tǒng)試圖證明它，看此假設(shè)目標(biāo)是否在總數(shù)據(jù)庫中，若在，則假設(shè)成立。否則，看這些假設(shè)是否證據(jù)（葉子）結(jié)點，若是，向用戶詢問，若不是，則再假定另一個目標(biāo)，即找出結(jié)論部分中包含此假設(shè)的那些規(guī)則，把它們的前提作為新的假設(shè)，試圖證明它。這樣周而復(fù)始，直到所有目標(biāo)被證明，或所有路徑被測試。

總之，反向推理的具體實現(xiàn)策略是：先假定一個可能的目標(biāo)，983.雙向推理

雙向推理又稱為正反向混合推理，它綜合了正向推理和逆向推理的長處，克服了了兩者的短處。雙向推理的推理策略是同時從目標(biāo)向事實推理和從事實向目標(biāo)推理，并在推理過程中的某個步驟，實現(xiàn)事實與目標(biāo)的匹配。具體的推理策略有多種。例如，通過數(shù)據(jù)驅(qū)動幫助選擇某個目標(biāo)，即從初始證據(jù)（事實）出發(fā)進行正向推理，同時以目標(biāo)驅(qū)動求解該目標(biāo)，通過交替使用正逆向混合推理對問題進行求解。雙方推理的控制策略比前兩種方法都要復(fù)雜。美國斯坦福研究所人工智能中心研制的基于規(guī)則的專家系統(tǒng)工具KAS，就是采用正、逆向混合推理的產(chǎn)生式系統(tǒng)的一個典型例子。

下圖給出雙向混合推理過程的示意圖。3.雙向推理

雙向推理又稱為正反向混合推理，它綜合了正向99

4.1.2推理的沖突消解策略在利用推理求解問題的過程中，如果綜合數(shù)據(jù)庫中的已知事實與知識庫中的多條知識相匹配，或者有多個已知事實都可與知識庫中的某一條知識相匹配，或者有多個已知事實與知識庫中的多條知識相匹配，則稱這種情況為知識沖突。此時，需要按照某種策略從這多條匹配的知識中選擇一條最佳知識用于推理，這種解決沖突的過程稱為沖突消解。4.1.2推理的沖突消解策略100（1）按就近原則排序（2）按知識特殊性排序（3）按上下文限制排序（4）按知識的新鮮性排序（5）按知識的差異性排序（6）按領(lǐng)域知識的特點排序（7）按規(guī)則的次序排序（8）按前提條件的規(guī)模排序

（1）按就近原則排序1014.2命題邏輯命題邏輯與謂詞邏輯是最先應(yīng)用于人工智能的兩種邏輯，對于知識的形式化表示，特別是定理的自動證明發(fā)揮了重要作用，在人工智能的發(fā)展史中占有重要地位。謂詞邏輯是在命題邏輯的基礎(chǔ)上發(fā)展起來的，命題邏輯可看作是謂詞邏輯的一種特殊形式，在討論謂詞邏輯之前，先來介紹命題邏輯的基本概念。4.2命題邏輯命題邏輯與謂詞邏輯是最先應(yīng)用于人1024.2.1命題

定義3.1能夠分辨真假的語句稱做命題。定義3.2

一個語句如果不能再進一步分解成更簡單的語句，并且又是一個命題，則稱此命題為原子命題。原子命題是命題中的基本單位。命題，比如“太陽從東邊升起”，“雪是白的”4.2.1命題1034.2.2命題公式1.連接詞命題邏輯中，可以通過連接詞將一些原子命題連接起來，構(gòu)成復(fù)合命題，以表示復(fù)雜的定義。

～稱為“非”或“否定”。

∨稱為“析取”。表示被它連接的兩個命題具有“或”的關(guān)系。

4.2.2命題公式104

∧稱為“合取”。表示被它連接的兩個命題具有“與”的關(guān)系。

→稱為“條件”或“蘊涵”.P→Q表示“P蘊涵Q”，即“如果P，則Q”，其中P為條件的前提，Q為條件的后件。

?稱為“雙條件”.P?Q表示“P當(dāng)且僅當(dāng)Q”∧稱為“合取”。表示被它連接的兩個命題具有“與”的105AI的產(chǎn)生及主要學(xué)派2.命題公式定義4.3下面的遞歸形式給出命題公式的定義：（1）原子公式是命題公式（2）A是命題公式，則～A也是命題公式；（3）若A和B都是命題公式，則A∧B，A∨B，A→B，A?B也都是命題公式（4）只有（1）～（3）所得的公式才是命題公式。AI的產(chǎn)生及主要學(xué)派2.命題公式1064.3謂詞邏輯3.3.1謂詞與個體在謂詞邏輯中，將原子命題分解為謂詞與個體兩部分。例如，“貝多芬是作曲家”中，“是作曲家”是謂詞，“貝多芬”是個體。所謂個體是指可以獨立存在的物體，它可以是抽象的，也可以是具體的。例如，“李白是詩人”這個命題，若用poet表示“是詩人”，用Libai表示個體“李白”，則得到的謂詞是poet(Libai).又如，5>3,這個不等式可用謂詞表示為greater(5,3)4.3謂詞邏輯3.3.1謂詞與個體107謂詞的一般形式是：

P（x1,x2,…,xn）其中P是謂詞，x1,x2,…,xn是個體。

例如，“小劉的哥哥是工人”，可以表示為worker(brother(Liu)),其中brother(Liu)是一個函數(shù)。個體常數(shù)，變量和函數(shù)統(tǒng)稱為項。謂詞的一般形式是：108謂詞中包含的個體數(shù)目稱為謂詞的元數(shù)，例如P(x)是一元謂詞，P(x,y)是二元謂詞，而P(x1,x2,…,xn)是n元謂詞。在謂詞P(x1,x2,…,xn)中，若xi(i=1,2,…,n)都是個體常量、變元或函數(shù)，則稱它為一階謂詞。如果xi本身又是一個一階謂詞，則稱它為二階謂詞，依次類推。謂詞和函數(shù)從形式上看很相似，其實它們有著本質(zhì)的區(qū)別，是兩個完全不同的概念。謂詞具有邏輯值“真”或“假”，而函數(shù)則是某個個體到另一個個體之間的映射。謂詞中包含的個體數(shù)目稱為謂詞的元數(shù)，例如P(x)是1093.3.2謂詞公式1.連接詞與命題邏輯中相同。2.量詞全稱量詞（?x）表示“對于個體域中的所有個體x”；存在量詞(?x)表示“在個體域中存在個體x”.3.3.2謂詞公式1103.謂詞演算公式

定義4.4謂詞演算中，由某個謂詞構(gòu)成的不含任何連接詞的公式，叫做原子謂詞公式。一般一個形如F(x1,x2,…,xn)的謂詞公式，稱作原子謂詞公式，或簡稱原子，其中F為n元謂詞，而x1,x2,…,xn為個體變元。3.謂詞演算公式111定義4.5可按下列規(guī)則得到謂詞演算的合式公式如下：(1)原子謂詞公式是合式公式；(2)A是合式公式，則～A也是合式公式；(3)若A和B都是合式公式，則A∧B，A∨B，A→B，A?B也都是合式公式(4)若A是合式公式，x是一個體變元，則(?x)A和(?x)A也都是合式公式(5)只有(1)～(4)所得的公式才是合式公式。定義4.5可按下列規(guī)則得到謂詞演算的合式公式如下：112謂詞演算公式就是一個按照一定規(guī)則由原子公式、連接詞、量詞及圓括號所組成的字符串。例如：

(?x)P(x,y),(?x)(P(x)∨P(y))謂詞演算公式就是一個按照一定規(guī)則由原子公式、連接113

4.謂詞轄域與約束變元在一個公式中，如果有量詞出現(xiàn)，位于量詞后面的單個量詞或者用括弧括起來的合式公式稱為量詞的轄域。在轄域內(nèi)與量詞中同名的變元稱為約束變元，不受約束的變元稱為自由變元。4.謂詞轄域與約束變元114

3.3.3謂詞公式的永真性與可滿足性1.謂詞公式的解釋定義4.6設(shè)D為謂詞公式P的個體域，若對P中的個體常量、函數(shù)和謂詞按照下列規(guī)定賦值：（1）為每個個體常量指派D中的一個元素；（2）為每個n元函數(shù)指派一個從Dn到D的映射，其中Dn＝{(x1,x2,…,xn)|x1,x2,…,xn∈D}（3）為每個n元謂詞指派一個從Dn到{F,T}的映射；則稱這些指派為公式P在D上的一個解釋。3.3.3謂詞公式的永真性與可滿足性115一般情況下，謂詞公式的真值都是針對某一解釋而言的。同一個公式可能在一種解釋下其真值是T，而在另一種解釋下，其真值是F。一般情況下，謂詞公式的真值都是針對某一解釋而言的。同一個116

2.謂詞公式的永真性定義4.7如果謂詞公式P，對個體域D上的任何一個解釋都取得真值T，則稱P在D上是永真的；如果P在每個非空個體域上均永真，則稱P永真。定義4.8如果謂詞公式P，對個體域D上的任何一個解釋都取得真值F，則稱P在D上是永假的；如果P在每個非空個體域上均永假，則稱P永假。謂詞公式的永假性又稱為不可滿足性或不相容性。2.謂詞公式的永真性1173.謂詞公式的可滿足性定義4.9對于謂詞公式P，如果至少存在一個解釋使得公式P在此解釋下的真值為T，則稱公式P是可滿足的。如果不存在任何解釋，使得P的取值為T，則稱公式P是不可滿足的。3.謂詞公式的可滿足性1183.3.4謂詞公式的等價性與永真蘊涵定義4.10設(shè)P和Q是兩個謂詞公式，D為它們共同的個體域。若對D上的任何一個解釋，P與Q的取值都相同，則公式P和Q在域D上是等價的。如果D是任意個體域，則稱P和Q是等價的，記做P?Q。3.3.4謂詞公式的等價性與永真蘊涵119常用的等價式：交換律P∧Q?Q∧PP∨Q?Q∨P結(jié)合律(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)狄.摩根定律～(P∨Q)?～P∧～Q～(P∧Q)?～P∨～Q否定之否定定律～(～P)?P

常用的等價式：120吸收律P∨(P∧Q)?P

P∧(P∨Q)?P補余律P∨～P?TP∧～P?F逆否定律P→Q?～Q→～P

連接詞化歸律P→Q?～P∨Q

P?Q?(P→Q)∧(Q→P)

P?Q?(P∧Q)∨(～P∧～Q)吸收律P∨(P∧Q)?P121量詞轉(zhuǎn)換律～(?x)P?(?x)(～P)

～(?x)P?(?x)(～P)量詞分配律(?x)(P∧Q)?(?x)P∧(?x)Q

(?x)(P∨Q)?(?x)P∨(?x)Q量詞轉(zhuǎn)換律～(?x)P?(?x)(～P)122定義4.11對于謂詞公式P和Q，如果P→

Q永真，則稱P永真蘊涵Q，且稱Q為P的邏輯結(jié)論，稱P為Q的前提，記作P?Q。下面是一些常用到的永真蘊涵式：化簡式

P∧Q?P

P∧Q?Q附加式

P?P∨Q

Q?P∨Q

析取三段論～P，P∨Q?Q

假言推理

P，P→

Q?Q

拒取式～Q，P→

Q?～P

假言三段論

P→Q，Q→R?P→R

二難推論

P∨Q，P→R，Q→R?R

定義4.11對于謂詞公式P和Q，如果P→Q永真，則稱P123全稱固化

(?x)(P(x))?P(y),其中y是個體域上的任一個體，利用此永真蘊涵式可以消去公式中的全稱量詞

存在固化

(?x)(P(x))?P(y),其中y是個體域中某個使P(y)為真的個體，利用此式可以消去公式中的存在量詞全稱固化(?x)(P(x))1243.3.5置換與合一1.置換定義4.12置換是形如{t1/x1,t2/x2,…,tn/xn}的一個有限集。其中，xi是變量，ti是不同于xi的項（常量、變量、函數(shù)），且xi≠xj(i≠j),i,j=1,2,…,n.例如：{a/x,b/y,f(x)/z},{f(z)/x,y/z}

3.3.5置換與合一1252.合一定義4.13設(shè)有公式集{E1,E2,…,En}和置換θ，使E1θ=E2θ=…=Enθ便稱E1，E2，…En是可合一的，且θ稱為合一置換。定義4.14若E1，E2，…En有合一置換σ，且對E1，E2，…En的任一置換θ都存在一個置換λ，使得

θ=σ×

λ，則稱σ為E1，E2，…En的最一般合一置換，記為mgu。2.合一126例若E1＝Q(y)，E2=Q(z),對E1和E2來說，σ={y/z}和σ={z/y}都是它們的最一般合一置換。例若E1＝Q(y)，E2=Q(z),對E1和E2來說1274.5.1謂詞公式與字句集1.范式（1）前束形范式一個謂詞公式，如果它的所有量詞均非否定地出現(xiàn)在公式的最前面，且它的轄域一直延伸到公式之末，同時公式中不出現(xiàn)連接詞→及?，這種形式的公式稱做前束形范式。例如：(?x)(?x)(?z)(P(x)∧F(y,x)∧Q(y,x))4.5.1謂詞公式與字句集128（2）斯克林（skolem）范式為了克服前束性范式的缺點，斯可林對它進行了改進，使前束性范式的首標(biāo)不出現(xiàn)存在量詞。從前束性范式中消去全部存在量詞所得到公式即為斯克林（skolem）范式，或稱skolem標(biāo)準(zhǔn)型。（2）斯克林（skolem）范式129將謂詞公式G化為skolem標(biāo)準(zhǔn)型的步驟如下：(1)消去謂詞公式G中的蘊涵→及雙條件?，以～A∨B代替A→B，以（A∧B）∨（～A∧～B）替換A?B(2)減少否定負(fù)號～的轄域，使否定符號～最多只作用到一個謂詞上。(3)重新命名變元名，使所有的變元的名字均不同，并且自由變元及約束變元亦不同。將謂詞公式G化為skolem標(biāo)準(zhǔn)型的步驟如下：130(4)消去存在量詞。分兩種情況，一種使存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)，此時，只要用一個新的個體變量替換該存在量詞約束的變元，就可以消去存在量詞；另一中情況是，存在量詞位于一個或多個全稱量詞的轄域內(nèi)，比如(?x1)(?x2)…(?xn)(?y)P(x1,x2,…,xn,y)此時變元y實際受前面的變元x1,x2,…,xn的約束，需要用Skolem函數(shù)f(x1,x2,…,xn)替換y即可將存在量詞y消去，得到(?x1)(?x2)…(?xn)(?y)P(x1,x2,…,xn,f(x1,x2,…,xn))(4)消去存在量詞。分兩種情況，一種使存在量詞不出現(xiàn)在全稱131(5)把全稱量詞全部移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。(6)母式化為合取范式：任何母式都可以寫成由一些謂詞公式否定的析取的有限集組成的合取。(5)把全稱量詞全部移到公式的左邊，并使每個量詞的轄域包括132例：將謂詞公式G=(?x)(?y)P(x,y)→～(?y)(Q(x,y)→R(x,y))化為Skolem標(biāo)準(zhǔn)型。解：（1）消去→及?連接詞。(?x)(~(?y)P(x,y)∨～(?y)(~Q(x,y)∨R(x,y)))（2）把～的轄域減少到最多只作用于一個謂詞。(?x)((?y)~P(x,y)∨(?y)(Q(x,y)∧～R(x,y)))（3）變量更名(?x)((?y)~P(x,y)∨(?z)(Q(x,z)∧～R(x,z)))例：將謂詞公式G=(?x)(?y)P(x,y)→133（4）消去存在量詞。因為存在量詞(?y)和(?z)都在轄域(?x)內(nèi)，屬于上述所講的第二種情況，所以分別用skolem函數(shù)f(x)和g(x)替換y和z。(?x)(~P(x,f(x))∨(Q(x,g(x))∧～R(x,g(x))))（5）全稱量詞移到左邊。由于只有一個全稱量詞(?x)，已在左邊，所以不移。（6）將母式化為合取范式。(?x)((~P(x,f(x))∨(Q(x,g(x))∧(~P(x,f(x))～R(x,g(x))))（4）消去存在量詞。因為存在量詞(?y)和(?z)都在轄域(1342.字句與字句集定義4.16不含有任何連接詞的謂詞公式稱作原子公式，簡稱原子，而原子或原子的否定統(tǒng)稱為文字。例如：P(x),~P(x,c),R(x,y)定義4.17字句就是由一些文字組成的析取式。例如：P(x)∨~Q(x,y),~P(x,c)∨R(x,y,f(x))定義4.18不含有任何文字的字句稱為空子句，記做NIL。由于空子句不含有任何文字，它不能被任何解釋所滿足，所以空子句是永假的，不可滿足的。2.字句與字句集135定義4.19由字句構(gòu)成的集合稱為字句集。謂詞公式skolem標(biāo)準(zhǔn)型的母式是由一些字句的合取組成的。如果將謂詞公式G的skolem標(biāo)準(zhǔn)型前面的全稱量詞全部消去，并用逗號代替合取符號，便可得到謂詞公式G的字句集S。定義4.19由字句構(gòu)成的集合稱為字句集。1363.不可滿足意義下的一致性公式G與其字句集S并不等價，但它們在不可滿足的意義下是一致的。定理4.2設(shè)有謂詞公式G，而其相應(yīng)的字句集為S，則G是不可滿足的充分必要條件是S是不可滿足的。3.不可滿足意義下的一致性1374.5.2Herbrand理論1.H域定義4.20設(shè)謂詞公式G的字句集為S，則按下述方法構(gòu)造的個體變元域H∞稱為公式集或字句集S的Herbrand域，簡稱H域。（1）令H0為S中所出現(xiàn)的常量的集合。若S中沒有常量出現(xiàn)，就任取一個常量a∈D,規(guī)定H0＝{a}。（2）令Hi+1=Hi∪{S中所有的形如f(t1,t2,…,tn)的元素}其中，f(t1,t2,…,tn)是出現(xiàn)于