西電人工智能12確定性推理課件

ArtificialIntelligence(AI)

人工智能主講：戚玉濤Email：qi_yutao@163.com第三章：確定性推理ArtificialIntelligence(AI)

人內(nèi)容提要第三章：確定性推理1.推理的基本概念2.搜索策略3.自然演繹推理4.歸結(jié)演繹推理5.基于規(guī)則的演繹推理內(nèi)容提要第三章：確定性推理1.推理的基本概念2.搜索策略3.自然演繹推理自然演繹推理：從一組已知為真的事實出發(fā)，直接運用經(jīng)典邏輯中的推理規(guī)則推出結(jié)論的過程稱為自然演繹推理。自然演繹推理最基本的推理規(guī)則是三段論推理，它包括：假言推理拒取式假言三段論自然演繹推理自然演繹推理：從一組已知為真的事實出發(fā)，直接運用自然演繹推理假言推理：

P,P→Q?Q表示：由P→Q以及P為真，可以推出Q為真例如：由“如果x是金屬，則x能導電”，以及“銅是金屬”，可以推出“銅能導電”。拒取式：P→Q,﹁Q?﹁P表示：由P→Q為真以及Q為假，可以推出P為假例如：由“如果下雨，則地上會濕”，以及“地上不濕”，可以推出“沒有下雨”。假言三段論：P→Q,Q→R?P→R自然演繹推理假言推理：P,P→Q?Q自然演繹推理注意避免以下兩類錯誤：肯定后件的錯誤：當P→Q為真時，希望通過肯定后件Q為真來推出前件P為真，這是不允許的。例如：伽利略在論證哥白尼的日心說時，曾使用了如下推理：(1)如果行星系統(tǒng)是以太陽為中心的，則金星會顯示出位相變化；(2)金星顯示出位相變化；(3)所有，行星系統(tǒng)是以太陽為中心的這就是使用了肯定后件的推理，違反了經(jīng)典邏輯的邏輯規(guī)則。自然演繹推理注意避免以下兩類錯誤：自然演繹推理注意避免以下兩類錯誤：否定前件的錯誤：當P→Q為真時，希望通過否定前件P來推出后件Q為假，這也是不允許的。例如：(1)如果下雨，則地上會濕(2)沒有下雨(3)所有，地上不濕事實上，如果向地上灑水，地上也是會濕的。這就是使用了否定前件的推理，違反了經(jīng)典邏輯的邏輯規(guī)則。自然演繹推理注意避免以下兩類錯誤：自然演繹推理自然演繹推理的例子設已知如下事實：A,B,A→C,B∧C→D,D→Q求證：Q為真。證明：因為A,A→C?C假言推理B,C?B∧C引入合取詞B∧C，B∧C→D?D假言推理D,D→Q?Q假言推理因此，Q為真自然演繹推理自然演繹推理的例子自然演繹推理自然演繹推理的例子設已知如下事實：(1)只要是需要編程序的課，王程都喜歡。(2)所有的程序設計語言課都是需要編程序的課。(3)C是一門程序設計語言課。求證：王程喜歡C這門課。證明：首先定義謂詞Prog(x)：x是需要編程序的課。Like(x,y):x喜歡y。Lang(x):x是一門程序設計語言課自然演繹推理自然演繹推理的例子自然演繹推理自然演繹推理的例子把已知事實及待求解問題用謂詞公式表示如下：Prog(x)→Like(Wang,x)(?x)(Lang(x)→Prog(x))Lang(C)應用推理規(guī)則進行推理：Lang(y)→Prog(y)全稱固化Lang(C)，Lang(y)→Prog(y)?Prog(C)假言推理{C/y}Prog(C),Prog(x)→Like(Wang,x)?Like(Wang,C)假言推理{C/x}因此，王程喜歡C這門課。自然演繹推理自然演繹推理的例子自然演繹推理自然演繹推理的優(yōu)缺點優(yōu)點：定理證明過程自然，易于理解，并且有豐富的推理規(guī)則可用。缺點：是容易產(chǎn)生知識爆炸，推理過程中得到的中間結(jié)論一般按指數(shù)規(guī)律遞增，對于復雜問題的推理不利，甚至難以實現(xiàn)。自然演繹推理自然演繹推理的優(yōu)缺點內(nèi)容提要第三章：確定性推理1.推理的基本概念2.搜索策略3.自然演繹推理4.歸結(jié)演繹推理5.基于規(guī)則的演繹推理內(nèi)容提要第三章：確定性推理1.推理的基本概念2.搜索策略3.歸結(jié)演繹推理歸結(jié)演繹推理：是一種基于魯濱遜（Robinson）歸結(jié)原理的機器推理技術。魯濱遜歸結(jié)原理亦稱為消解原理，是魯濱遜于1965年在海伯倫（Herbrand）理論的基礎上提出的一種基于邏輯的“反證法”。在人工智能中，幾乎所有的問題都可以轉(zhuǎn)化為一個定理證明問題。定理證明的實質(zhì)，就是要對前提P和結(jié)論Q，證明P→Q永真。要證明P→Q永真，就是要證明P→Q在任何一個非空的個體域上都是永真的。這將是非常困難的，甚至是不可實現(xiàn)的。歸結(jié)演繹推理歸結(jié)演繹推理：是一種基于魯濱遜（Robinson歸結(jié)演繹推理歸結(jié)演繹推理：魯濱遜歸結(jié)原理把永真性的證明轉(zhuǎn)化為關于不可滿足性的證明。要證明P→Q永真，只需證明P∧﹁Q不可滿足因為：﹁(P→Q)?﹁(﹁P∨Q)?P∧﹁Q海伯倫(Herbrand)定理為自動定理證明奠定了理論基礎。魯濱遜(Robinson)提出的歸結(jié)原理使機器定理證明成為現(xiàn)實。歸結(jié)演繹推理歸結(jié)演繹推理：歸結(jié)演繹推理歸結(jié)演繹推理子句集及其化簡魯濱遜歸結(jié)原理歸結(jié)反演推理的歸結(jié)策略用歸結(jié)反演求取問題的答案歸結(jié)演繹推理歸結(jié)演繹推理歸結(jié)演繹推理歸結(jié)演繹推理子句集及其化簡魯濱遜歸結(jié)原理歸結(jié)反演推理的歸結(jié)策略用歸結(jié)反演求取問題的答案歸結(jié)演繹推理歸結(jié)演繹推理子句集及其化簡無論是海伯倫理論，還是魯濱遜歸結(jié)原理是在子句集的基礎上討論問題的。因此，討論歸結(jié)演繹推理之前，需要先討論子句集的有關概念。子句和子句集原子謂詞公式及其否定統(tǒng)稱為文字。例如:P(x)、Q(x)、﹁P(x)、﹁Q(x)等都是文字。任何文字的析取式稱為子句。例如，P(x)∨Q(x)，P(x，f(x))∨Q(x，g(x))都是子句。子句集及其化簡無論是海伯倫理論，還是魯濱遜歸結(jié)原理是在子句集子句集及其化簡子句和子句集不含任何文字的子句稱為空子句。由于空子句不含有任何文字，也就不能被任何解釋所滿足，因此空子句是永假的，不可滿足的?？兆泳湟话惚挥洖镹IL。由子句或空子句所構成的集合稱為子句集。在子句集中，子句之間是合取關系子句集中的變元受全稱量詞的約束任何謂詞公式都可通過等價關系及推理規(guī)則化為相應的子句集子句集及其化簡子句和子句集子句集及其化簡把謂詞公式化成子句集的步驟Step1：利用等價關系消去“→”和“?”反復使用如下等價公式：P→Q?﹁P∨QP?Q?(P∧Q)∨(﹁P∧﹁Q)即可消去謂詞公式中的連接詞“→”和“?”。例如：

(?x)((?y)P(x,y)→﹁(?y)(Q(x,y)→R(x,y)))經(jīng)等價變化后為：

(?x)(﹁(?y)P(x,y)∨﹁(?y)(﹁Q(x,y)∨R(x,y)))子句集及其化簡把謂詞公式化成子句集的步驟子句集及其化簡Step2：利用等價關系把“?”移到緊靠謂詞的位置上反復使用雙重否定率：﹁(﹁P)?P摩根定律：﹁(P∧Q)?﹁P∨﹁Q﹁(P∨Q)?﹁P∧﹁Q量詞轉(zhuǎn)換率：﹁(?x)P(x)?(?x)﹁P(x)﹁(?x)P(x)?(?x)﹁

P(x)使得每個否定符號最多只作用于一個謂詞上。例如：上式經(jīng)等價變換后為

(?x)((?y)﹁P(x，y)∨(?y)(Q(x，y)∧﹁R(x，y))子句集及其化簡Step2：利用等價關系把“?”移到緊靠謂詞子句集及其化簡Step3：重新命名變元，使不同量詞約束的變元有不同的名字例如：上式經(jīng)重新命名變換后為

(?x)((?y)﹁P(x，y)∨(?z)(Q(x，z)∧﹁R(x，z)))Step4：消去存在量詞。消去存在量詞時，需要區(qū)分以下兩種情況：1）存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)，只要用一個新的個體常量替換受該存在量詞約束的變元，就可消去該存在量詞。2）存在量詞位于一個或者多個全稱量詞的轄域內(nèi)子句集及其化簡Step3：重新命名變元，使不同量詞約束的變子句集及其化簡如下面的謂詞公式：(?x1)…(?xn)(?y)P(x1，x2,…,xn,y)則需要用Skolem函數(shù)f(x1，x2,…,xn)替換受該存在量詞約束的變元y，然后再消去該存在量詞。例如：繼續(xù)上面的例子(?x)((?y)﹁P(x，y)∨(?z)(Q(x，z)∧﹁R(x，z)))式子中存在量詞(y)及(z)都位于(x)的轄域內(nèi)，所以需要用Skolem函數(shù)替換，設替換y和z的Skolem函數(shù)分別是f(x)和g(x)，則替換后得到：(?x)(﹁P(x,f(x))∨(Q(x,g(x))∧﹁R(x,g(x))))子句集及其化簡如下面的謂詞公式：子句集及其化簡Step5：把全稱量詞全部移到公式的左邊上式中由于只有一個全稱量詞，而且它位于公式的最左邊，所以這里不需要做任何工作。如果在公式內(nèi)部有全稱量詞，就需要把它們都移到公式的左邊。Step6：利用等價關系

P∨(Q∧R)?(P∨Q)∧(P∨R)

把公式化為Skolem標準形Skolem標準形的一般形式為(?x1)…(?xn)M(x1,x2,……,xn)其中，M(x1,x2,……,xn)是Skolem標準形的母式，它由子句的合取所構成。子句集及其化簡Step5：把全稱量詞全部移到公式的左邊子句集及其化簡Skolem標準形的一般形式為(?x1)…(?xn)M(x1,x2,……,xn)其中，M(x1,x2,……,xn)是Skolem標準形的母式，它由子句的合取所構成。例如：前面的公式化為Skolem標準形后為

(?x)(

(﹁P(x,f(x))∨Q(x,g(x)))

∧(﹁P(x,f(x))﹁R(x,g(x))))Step7：消去全稱量詞。由于母式中的全部變元均受全稱量詞的約束，并且全稱量詞的次序已無關緊要，因此可以省掉全稱量詞。例如：上式消去全稱量詞后為(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x)))子句集及其化簡Skolem標準形的一般形式為子句集及其化簡Step8：對變元更名，使不同子句中的變元不同名由于每一個子句都對應著母式中的一個合取元，并且所有變元都是由全稱量詞量化的，因此任意兩個不同子句的變量之間實際上不存在任何關系，更換變量名不會影響公式的真值。例如：上式經(jīng)更名后得到(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(y,f(y))∨﹁R(y,g(y)))Step9：消去合取詞，就得到子句集。例如：消去合取詞后，上式就變?yōu)橄率鲎泳浼鑀(x,f(x))∨Q(x,g(x))﹁P(y,f(y))∨﹁R(y,g(y))子句集及其化簡Step8：對變元更名，使不同子句中的變元不子句集及其化簡子句集的意義在上述化簡過程中，由于在消去存在量詞時所用的Skolem函數(shù)可以不同，因此化簡后的標準子句集是不唯一的。因此，當原謂詞公式為非永假時，它與其標準子句集并不等價。但當原謂詞公式為永假（或不可滿足）時，其標準子句集則一定是永假的，即Skolem化并不影響原謂詞公式的永假性。子句集S的不可滿足性：對于任意論域中的任意一個解釋，S中的子句不能同時取得真值T。子句集及其化簡子句集的意義子句集及其化簡定理：設有謂詞公式F，其子句集為S，則F不可滿足的充要條件是S不可滿足。由此定理可知，要證明一個謂詞公式是不可滿足的，只要證明其相應的標準子句集是不可滿足的就可以了。由于子句集中的子句之間是合取關系，子句集中只要有一個子句為不可滿足，則整個子句集就是不可滿足的?？兆泳涫遣豢蓾M足的。因此，一個子句集中如果包含有空子句，則此子句集就一定是不可滿足的。這個結(jié)論是魯濱遜歸結(jié)原理的主要依據(jù)。子句集及其化簡定理：設有謂詞公式F，其子句集為S，則F不可滿歸結(jié)演繹推理歸結(jié)演繹推理子句集及其化簡魯濱遜歸結(jié)原理歸結(jié)反演推理的歸結(jié)策略用歸結(jié)反演求取問題的答案歸結(jié)演繹推理歸結(jié)演繹推理魯濱遜歸結(jié)原理海伯倫（Herbrand）理論為了判斷子句集的不可滿足性，需要對所有可能論域上的所有解釋進行判定。只有當子句集對任何非空個體域上的任何一個解釋都是不可滿足的，才可斷定該子句集不可滿足。海伯倫構造了一個特殊的論域（海伯倫域），并證明只要對這個特殊域上的一切解釋進行判定，就可知子句集是否不可滿足。海伯倫定理：子句集不可滿足的充要條件是存在一個有限的不可滿足的基子句集。海伯倫從理論上給出了證明子句集不可滿足性的可行性及方法，但是要在計算機上實現(xiàn)是很困難的。魯濱遜歸結(jié)原理海伯倫（Herbrand）理論魯濱遜歸結(jié)原理魯濱遜歸結(jié)原理的基本思想首先把欲證明問題的結(jié)論否定，并加入子句集，得到一個擴充的子句集S'；然后設法檢驗子句集S'是否含有空子句，若含有空子句，則表明S'是不可滿足的；若不含有空子句，則繼續(xù)使用歸結(jié)法，在子句集中選擇合適的子句進行歸結(jié)，直至導出空子句或不能繼續(xù)歸結(jié)為止。魯濱遜歸結(jié)原理包括命題邏輯消解原理謂詞邏輯消解原理魯濱遜歸結(jié)原理魯濱遜歸結(jié)原理的基本思想命題邏輯的歸結(jié)歸結(jié)推理的核心是求兩個子句的歸結(jié)式歸結(jié)式的定義及性質(zhì)若P是原子謂詞公式，則稱P與﹁P為互補文字設C1和C2是子句集中的任意兩個子句，如果C1中的文字L1與C2中的文字L2互補，那么可從C1和C2中分別消去L1和L2，并將C1和C2中余下的部分按析取關系構成一個新的子句C12，則稱這一過程為歸結(jié)，稱C12為C1和C2的歸結(jié)式，稱C1和C2為C12的親本子句。命題邏輯的歸結(jié)歸結(jié)推理的核心是求兩個子句的歸結(jié)式命題邏輯的歸結(jié)例如：設C1=P∨Q∨R，C2=﹁P∨S，求C1和C2的歸結(jié)式C12。解：這里L1=P，L2=﹁P，通過歸結(jié)可以得到C12=Q∨R∨S例如：設C1=﹁Q，C2=Q，求C1和C2的歸結(jié)式C12。解：這里L1=﹁Q，L2=Q，通過歸結(jié)可以得到

C12=NIL命題邏輯的歸結(jié)例如：設C1=P∨Q∨R，C2=﹁P∨S，求C命題邏輯的歸結(jié)例如：設設C1=﹁P∨

Q

，C2=﹁Q，C3=P，求C1、C2、C3的歸結(jié)式C123。解：若先對C1、C2歸結(jié)，可得到C12=﹁P然后再對C12和C3歸結(jié)，得到C123=NIL如果改變歸結(jié)順序，同樣可以得到相同的結(jié)果，即其歸結(jié)過程是不唯一的。其歸結(jié)歸結(jié)過程可用右圖來表示，該樹稱為歸結(jié)樹。﹁P∨Q﹁Q﹁P

P

NIL﹁P∨Q

P

Q﹁Q

NIL命題邏輯的歸結(jié)例如：設設C1=﹁P∨Q，C2=﹁Q，命題邏輯的歸結(jié)定理：歸結(jié)式C12是其親本子句C1和C2的邏輯結(jié)論。證明：設C1=L∨C1’，C2=﹁L∨C2’關于解釋I為真，則只需證明C12=C1’∨C2’關于解釋I也為真。對于解釋I，L和﹁L中必有一個為假。若L為假，則必有C1'為真，不然就會使C1為假，這將與前提假設C1為真矛盾，因此只能有C1'為真。同理，若﹁L為假，則必有C2'為真。因此，必有C12=C1'∨C2'關于解釋I也為真。即C12是C1和C2的邏輯結(jié)論。命題邏輯的歸結(jié)定理：歸結(jié)式C12是其親本子句C1和C2的邏輯命題邏輯的歸結(jié)推論1：設C1和C2是子句集S中的兩個子句，C12是C1和C2的歸結(jié)式，若用C12代替C1和C2后得到新的子句集S1，則由S1的不可滿足性可以推出原子句集S的不可滿足性。即：

S1的不可滿足性?S的不可滿足性推論2：設C1和C2是子句集S中的兩個子句，C12是C1和C2的歸結(jié)式，若把C12加入S中得到新的子句集S2，則S與S2的不可滿足性是等價的。即：

S2的不可滿足性?S的不可滿足性命題邏輯的歸結(jié)推論1：設C1和C2是子句集S中的兩個子句，C命題邏輯的歸結(jié)上述兩個推論說明，為證明子句集S的不可滿足性，只要對其中可進行歸結(jié)得子句進行歸結(jié)，并把歸結(jié)式加入到子句集S中，或者用歸結(jié)式代替他的親本子句，然后對新的子句集證明其不可滿足性就可以了。如果經(jīng)歸結(jié)能得到空子句，根據(jù)空子句的不可滿足性，即可得到原子句集S是不可滿足的結(jié)論。在命題邏輯中，對不可滿足的子句集S，其歸結(jié)原理是完備的。即：子句集S是不可滿足的，當且僅當存在一個從S到空子句的歸結(jié)過程。

命題邏輯的歸結(jié)上述兩個推論說明，為證明子句集S的不可滿足性，命題邏輯的歸結(jié)命題邏輯的歸結(jié)反演歸結(jié)原理：假設F為已知前提，G為欲證明的結(jié)論，歸結(jié)原理把證明G為F的邏輯結(jié)論轉(zhuǎn)化為證明F∧﹁G為不可滿足。再根據(jù)上述定理，在不可滿足的意義上，公式集F∧﹁G與其子句集是等價的，即把公式集上的不可滿足轉(zhuǎn)化為子句集上的不可滿足。應用歸結(jié)原理證明定理的過程稱為歸結(jié)反演。命題邏輯的歸結(jié)命題邏輯的歸結(jié)反演命題邏輯的歸結(jié)命題邏輯的歸結(jié)反演：在命題邏輯中，已知F，證明G為真的歸結(jié)反演過程如下：①否定目標公式G，得﹁G;②把﹁G并入到公式集F中，得到{F，﹁G}；③把{F，﹁G}化為子句集S。④應用歸結(jié)原理對子句集S中的子句進行歸結(jié)，并把每次得到的歸結(jié)式并入S中。如此反復進行，若出現(xiàn)空子句，則停止歸結(jié)，此時就證明了G為真。命題邏輯的歸結(jié)命題邏輯的歸結(jié)反演：在命題邏輯中，已知F，證明命題邏輯的歸結(jié)例如：設已知的公式集為{P,(P∧Q)→R,(S∨T)→Q,T}，求證結(jié)論R。解：假設結(jié)論R為假,將﹁R加入公式集，并化為子句集：S={P,﹁P∨﹁Q∨R,﹁S∨Q,﹁T∨Q,T,﹁R}其歸結(jié)過程如右圖的歸結(jié)演繹樹所示。該樹根為空子句。子句集S不可滿足，即假設﹁R為真是錯誤的，于是R為真。﹁P∨﹁Q∨R﹁R﹁P∨﹁QP﹁Q﹁T∨Q﹁TTNIL命題邏輯的歸結(jié)例如：設已知的公式集為{P,(P∧Q)→R問題？問題？ArtificialIntelligence(AI)

人工智能主講：戚玉濤Email：qi_yutao@163.com第三章：確定性推理ArtificialIntelligence(AI)

人內(nèi)容提要第三章：確定性推理1.推理的基本概念2.搜索策略3.自然演繹推理4.歸結(jié)演繹推理5.基于規(guī)則的演繹推理內(nèi)容提要第三章：確定性推理1.推理的基本概念2.搜索策略3.自然演繹推理自然演繹推理：從一組已知為真的事實出發(fā)，直接運用經(jīng)典邏輯中的推理規(guī)則推出結(jié)論的過程稱為自然演繹推理。自然演繹推理最基本的推理規(guī)則是三段論推理，它包括：假言推理拒取式假言三段論自然演繹推理自然演繹推理：從一組已知為真的事實出發(fā)，直接運用自然演繹推理假言推理：

P,P→Q?Q表示：由P→Q以及P為真，可以推出Q為真例如：由“如果x是金屬，則x能導電”，以及“銅是金屬”，可以推出“銅能導電”。拒取式：P→Q,﹁Q?﹁P表示：由P→Q為真以及Q為假，可以推出P為假例如：由“如果下雨，則地上會濕”，以及“地上不濕”，可以推出“沒有下雨”。假言三段論：P→Q,Q→R?P→R自然演繹推理假言推理：P,P→Q?Q自然演繹推理注意避免以下兩類錯誤：肯定后件的錯誤：當P→Q為真時，希望通過肯定后件Q為真來推出前件P為真，這是不允許的。例如：伽利略在論證哥白尼的日心說時，曾使用了如下推理：(1)如果行星系統(tǒng)是以太陽為中心的，則金星會顯示出位相變化；(2)金星顯示出位相變化；(3)所有，行星系統(tǒng)是以太陽為中心的這就是使用了肯定后件的推理，違反了經(jīng)典邏輯的邏輯規(guī)則。自然演繹推理注意避免以下兩類錯誤：自然演繹推理注意避免以下兩類錯誤：否定前件的錯誤：當P→Q為真時，希望通過否定前件P來推出后件Q為假，這也是不允許的。例如：(1)如果下雨，則地上會濕(2)沒有下雨(3)所有，地上不濕事實上，如果向地上灑水，地上也是會濕的。這就是使用了否定前件的推理，違反了經(jīng)典邏輯的邏輯規(guī)則。自然演繹推理注意避免以下兩類錯誤：自然演繹推理自然演繹推理的例子設已知如下事實：A,B,A→C,B∧C→D,D→Q求證：Q為真。證明：因為A,A→C?C假言推理B,C?B∧C引入合取詞B∧C，B∧C→D?D假言推理D,D→Q?Q假言推理因此，Q為真自然演繹推理自然演繹推理的例子自然演繹推理自然演繹推理的例子設已知如下事實：(1)只要是需要編程序的課，王程都喜歡。(2)所有的程序設計語言課都是需要編程序的課。(3)C是一門程序設計語言課。求證：王程喜歡C這門課。證明：首先定義謂詞Prog(x)：x是需要編程序的課。Like(x,y):x喜歡y。Lang(x):x是一門程序設計語言課自然演繹推理自然演繹推理的例子自然演繹推理自然演繹推理的例子把已知事實及待求解問題用謂詞公式表示如下：Prog(x)→Like(Wang,x)(?x)(Lang(x)→Prog(x))Lang(C)應用推理規(guī)則進行推理：Lang(y)→Prog(y)全稱固化Lang(C)，Lang(y)→Prog(y)?Prog(C)假言推理{C/y}Prog(C),Prog(x)→Like(Wang,x)?Like(Wang,C)假言推理{C/x}因此，王程喜歡C這門課。自然演繹推理自然演繹推理的例子自然演繹推理自然演繹推理的優(yōu)缺點優(yōu)點：定理證明過程自然，易于理解，并且有豐富的推理規(guī)則可用。缺點：是容易產(chǎn)生知識爆炸，推理過程中得到的中間結(jié)論一般按指數(shù)規(guī)律遞增，對于復雜問題的推理不利，甚至難以實現(xiàn)。自然演繹推理自然演繹推理的優(yōu)缺點內(nèi)容提要第三章：確定性推理1.推理的基本概念2.搜索策略3.自然演繹推理4.歸結(jié)演繹推理5.基于規(guī)則的演繹推理內(nèi)容提要第三章：確定性推理1.推理的基本概念2.搜索策略3.歸結(jié)演繹推理歸結(jié)演繹推理：是一種基于魯濱遜（Robinson）歸結(jié)原理的機器推理技術。魯濱遜歸結(jié)原理亦稱為消解原理，是魯濱遜于1965年在海伯倫（Herbrand）理論的基礎上提出的一種基于邏輯的“反證法”。在人工智能中，幾乎所有的問題都可以轉(zhuǎn)化為一個定理證明問題。定理證明的實質(zhì)，就是要對前提P和結(jié)論Q，證明P→Q永真。要證明P→Q永真，就是要證明P→Q在任何一個非空的個體域上都是永真的。這將是非常困難的，甚至是不可實現(xiàn)的。歸結(jié)演繹推理歸結(jié)演繹推理：是一種基于魯濱遜（Robinson歸結(jié)演繹推理歸結(jié)演繹推理：魯濱遜歸結(jié)原理把永真性的證明轉(zhuǎn)化為關于不可滿足性的證明。要證明P→Q永真，只需證明P∧﹁Q不可滿足因為：﹁(P→Q)?﹁(﹁P∨Q)?P∧﹁Q海伯倫(Herbrand)定理為自動定理證明奠定了理論基礎。魯濱遜(Robinson)提出的歸結(jié)原理使機器定理證明成為現(xiàn)實。歸結(jié)演繹推理歸結(jié)演繹推理：歸結(jié)演繹推理歸結(jié)演繹推理子句集及其化簡魯濱遜歸結(jié)原理歸結(jié)反演推理的歸結(jié)策略用歸結(jié)反演求取問題的答案歸結(jié)演繹推理歸結(jié)演繹推理歸結(jié)演繹推理歸結(jié)演繹推理子句集及其化簡魯濱遜歸結(jié)原理歸結(jié)反演推理的歸結(jié)策略用歸結(jié)反演求取問題的答案歸結(jié)演繹推理歸結(jié)演繹推理子句集及其化簡無論是海伯倫理論，還是魯濱遜歸結(jié)原理是在子句集的基礎上討論問題的。因此，討論歸結(jié)演繹推理之前，需要先討論子句集的有關概念。子句和子句集原子謂詞公式及其否定統(tǒng)稱為文字。例如:P(x)、Q(x)、﹁P(x)、﹁Q(x)等都是文字。任何文字的析取式稱為子句。例如，P(x)∨Q(x)，P(x，f(x))∨Q(x，g(x))都是子句。子句集及其化簡無論是海伯倫理論，還是魯濱遜歸結(jié)原理是在子句集子句集及其化簡子句和子句集不含任何文字的子句稱為空子句。由于空子句不含有任何文字，也就不能被任何解釋所滿足，因此空子句是永假的，不可滿足的。空子句一般被記為NIL。由子句或空子句所構成的集合稱為子句集。在子句集中，子句之間是合取關系子句集中的變元受全稱量詞的約束任何謂詞公式都可通過等價關系及推理規(guī)則化為相應的子句集子句集及其化簡子句和子句集子句集及其化簡把謂詞公式化成子句集的步驟Step1：利用等價關系消去“→”和“?”反復使用如下等價公式：P→Q?﹁P∨QP?Q?(P∧Q)∨(﹁P∧﹁Q)即可消去謂詞公式中的連接詞“→”和“?”。例如：

(?x)((?y)P(x,y)→﹁(?y)(Q(x,y)→R(x,y)))經(jīng)等價變化后為：

(?x)(﹁(?y)P(x,y)∨﹁(?y)(﹁Q(x,y)∨R(x,y)))子句集及其化簡把謂詞公式化成子句集的步驟子句集及其化簡Step2：利用等價關系把“?”移到緊靠謂詞的位置上反復使用雙重否定率：﹁(﹁P)?P摩根定律：﹁(P∧Q)?﹁P∨﹁Q﹁(P∨Q)?﹁P∧﹁Q量詞轉(zhuǎn)換率：﹁(?x)P(x)?(?x)﹁P(x)﹁(?x)P(x)?(?x)﹁

P(x)使得每個否定符號最多只作用于一個謂詞上。例如：上式經(jīng)等價變換后為

(?x)((?y)﹁P(x，y)∨(?y)(Q(x，y)∧﹁R(x，y))子句集及其化簡Step2：利用等價關系把“?”移到緊靠謂詞子句集及其化簡Step3：重新命名變元，使不同量詞約束的變元有不同的名字例如：上式經(jīng)重新命名變換后為

(?x)((?y)﹁P(x，y)∨(?z)(Q(x，z)∧﹁R(x，z)))Step4：消去存在量詞。消去存在量詞時，需要區(qū)分以下兩種情況：1）存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)，只要用一個新的個體常量替換受該存在量詞約束的變元，就可消去該存在量詞。2）存在量詞位于一個或者多個全稱量詞的轄域內(nèi)子句集及其化簡Step3：重新命名變元，使不同量詞約束的變子句集及其化簡如下面的謂詞公式：(?x1)…(?xn)(?y)P(x1，x2,…,xn,y)則需要用Skolem函數(shù)f(x1，x2,…,xn)替換受該存在量詞約束的變元y，然后再消去該存在量詞。例如：繼續(xù)上面的例子(?x)((?y)﹁P(x，y)∨(?z)(Q(x，z)∧﹁R(x，z)))式子中存在量詞(y)及(z)都位于(x)的轄域內(nèi)，所以需要用Skolem函數(shù)替換，設替換y和z的Skolem函數(shù)分別是f(x)和g(x)，則替換后得到：(?x)(﹁P(x,f(x))∨(Q(x,g(x))∧﹁R(x,g(x))))子句集及其化簡如下面的謂詞公式：子句集及其化簡Step5：把全稱量詞全部移到公式的左邊上式中由于只有一個全稱量詞，而且它位于公式的最左邊，所以這里不需要做任何工作。如果在公式內(nèi)部有全稱量詞，就需要把它們都移到公式的左邊。Step6：利用等價關系

P∨(Q∧R)?(P∨Q)∧(P∨R)

把公式化為Skolem標準形Skolem標準形的一般形式為(?x1)…(?xn)M(x1,x2,……,xn)其中，M(x1,x2,……,xn)是Skolem標準形的母式，它由子句的合取所構成。子句集及其化簡Step5：把全稱量詞全部移到公式的左邊子句集及其化簡Skolem標準形的一般形式為(?x1)…(?xn)M(x1,x2,……,xn)其中，M(x1,x2,……,xn)是Skolem標準形的母式，它由子句的合取所構成。例如：前面的公式化為Skolem標準形后為

(?x)(

(﹁P(x,f(x))∨Q(x,g(x)))

∧(﹁P(x,f(x))﹁R(x,g(x))))Step7：消去全稱量詞。由于母式中的全部變元均受全稱量詞的約束，并且全稱量詞的次序已無關緊要，因此可以省掉全稱量詞。例如：上式消去全稱量詞后為(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x)))子句集及其化簡Skolem標準形的一般形式為子句集及其化簡Step8：對變元更名，使不同子句中的變元不同名由于每一個子句都對應著母式中的一個合取元，并且所有變元都是由全稱量詞量化的，因此任意兩個不同子句的變量之間實際上不存在任何關系，更換變量名不會影響公式的真值。例如：上式經(jīng)更名后得到(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(y,f(y))∨﹁R(y,g(y)))Step9：消去合取詞，就得到子句集。例如：消去合取詞后，上式就變?yōu)橄率鲎泳浼鑀(x,f(x))∨Q(x,g(x))﹁P(y,f(y))∨﹁R(y,g(y))子句集及其化簡Step8：對變元更名，使不同子句中的變元不子句集及其化簡子句集的意義在上述化簡過程中，由于在消去存在量詞時所用的Skolem函數(shù)可以不同，因此化簡后的標準子句集是不唯一的。因此，當原謂詞公式為非永假時，它與其標準子句集并不等價。但當原謂詞公式為永假（或不可滿足）時，其標準子句集則一定是永假的，即Skolem化并不影響原謂詞公式的永假性。子句集S的不可滿足性：對于任意論域中的任意一個解釋，S中的子句不能同時取得真值T。子句集及其化簡子句集的意義子句集及其化簡定理：設有謂詞公式F，其子句集為S，則F不可滿足的充要條件是S不可滿足。由此定理可知，要證明一個謂詞公式是不可滿足的，只要證明其相應的標準子句集是不可滿足的就可以了。由于子句集中的子句之間是合取關系，子句集中只要有一個子句為不可滿足，則整個子句集就是不可滿足的。空子句是不可滿足的。因此，一個子句集中如果包含有空子句，則此子句集就一定是不可滿足的。這個結(jié)論是魯濱遜歸結(jié)原理的主要依據(jù)。子句集及其化簡定理：設有謂詞公式F，其子句集為S，則F不可滿歸結(jié)演繹推理歸結(jié)演繹推理子句集及其化簡魯濱遜歸結(jié)原理歸結(jié)反演推理的歸結(jié)策略用歸結(jié)反演求取問題的答案歸結(jié)演繹推理歸結(jié)演繹推理魯濱遜歸結(jié)原理海伯倫（Herbrand）理論為了判斷子句集的不可滿足性，需要對所有可能論域上的所有解釋進行判定。只有當子句集對任何非空個體域上的任何一個解釋都是不可滿足的，才可斷定該子句集不可滿足。海伯倫構造了一個特殊的論域（海伯倫域），并證明只要對這個特殊域上的一切解釋進行判定，就可知子句集是否不可滿足。海伯倫定理：子句集不可滿足的充要條件是存在一個有限的不可滿足的基子句集。海伯倫從理論上給出了證明子句集不可滿足性的可行性及方法，但是要在計算機上實現(xiàn)是很困難的。魯濱遜歸結(jié)原理海伯倫（Herbrand）理論魯濱遜歸結(jié)原理魯濱遜歸結(jié)原理的基本思想首先把欲證明問題的結(jié)論否定，并加入子句集，得到一個擴充的子句集S'；然后設法檢驗子句集S'是否含有空子句，若含有空子句，則表明S'是不可滿足的；若不含有空子句，則繼續(xù)使用歸結(jié)法，在子句集中選擇合適的子句進行歸結(jié)，直至導出空子句或不能繼續(xù)歸結(jié)為止。魯濱遜歸結(jié)原理包括命題邏輯消解原理謂詞邏輯消解原理魯濱遜歸結(jié)原理魯濱遜歸結(jié)原理的基本思想命題邏輯的歸結(jié)歸結(jié)推理的核心是求兩個子句的歸結(jié)式歸結(jié)式的定義及性質(zhì)若P是原子謂詞公式，則稱P與﹁P為互補文字設C1和C2是子句集中的任意兩個子句，如果C1中的文字L1與C2中的文字L2互補，那么可從C1和C2中分別消去L1和L2，并將C1和C2中余下的部分按析取關系構成一個新的子句C12，則稱這一過程為歸結(jié)，稱C12為C1和C2的歸結(jié)式，稱C1和C2為C12的親本子句。命題邏輯的歸結(jié)歸結(jié)推理的核心是求兩個子句的歸結(jié)式命題邏輯的歸結(jié)例如：設C1=P∨Q∨R，C2=﹁P∨S，求C1和C2的歸結(jié)式C12。解：這里L1=P，L2=﹁P，通過歸結(jié)可以得到C12=Q∨R∨S例如：設C1=﹁Q，C2=Q，求C1和C2的歸結(jié)式C12。解：這里L1=﹁Q，L2=Q，通過歸結(jié)可以得到

C12=NIL命題邏輯的歸結(jié)例如：設C1=P∨Q∨R，C2=﹁P∨S，求C命題邏輯的歸結(jié)例如：設設C1=﹁P∨

Q

，C2=﹁Q，C3=P，求C1、C2、C3的歸結(jié)式C123。解：若先對C1、C2歸結(jié)，可得到C12=﹁P然后再對C12和C3歸結(jié)，得到C123=NIL如果改變歸結(jié)順序，同樣可以得到相同的結(jié)果，即其歸結(jié)過程是不唯一的。其歸結(jié)歸結(jié)過程可用右圖來