ArtificialIntelligence(AI)

人工智能第二章：知識表示與推理ArtificialIntelligence(AI)

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

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

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

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

P(x)使得每個(gè)否定符號最多只作用于一個(gè)謂詞上。例如：上式(?x)(﹁(?y)P(x,y)∨﹁(?y)(﹁Q(x,y)∨R(x,y)))經(jīng)等價(jià)變換后為

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

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

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

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

(?x)(

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

∧(﹁P(x,f(x))﹁R(x,g(x))))Step7：消去全稱量詞。由于母式中的全部變元均受全稱量詞的約束，并且全稱量詞的次序已無關(guān)緊要，因此可以省掉全稱量詞。例如：上式消去全稱量詞后為(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x)))Step8：對變元更名，使不同子句中的變元不同名例如：上式經(jīng)更名后得到(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(y,f(y))∨﹁R(y,g(y)))子句集及其化簡例如：前面的公式化為Skolem標(biāo)準(zhǔn)形后為子句集及其化簡Step9：消去合取詞，就得到子句集。例如：消去合取詞后，上式(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(y,f(y))∨﹁R(y,g(y)))

就變?yōu)橄率鲎泳浼鑀(x,f(x))∨Q(x,g(x))﹁P(y,f(y))∨﹁R(y,g(y))子句集及其化簡Step9：消去合取詞，就得到子句集。子句集及其化簡子句集的意義在上述化簡過程中，由于在消去存在量詞時(shí)所用的Skolem函數(shù)可以不同，因此化簡后的標(biāo)準(zhǔn)子句集是不唯一的。因此，當(dāng)原謂詞公式為非永假時(shí)，它與其標(biāo)準(zhǔn)子句集并不等價(jià)。但當(dāng)原謂詞公式為永假（或不可滿足）時(shí)，其標(biāo)準(zhǔn)子句集則一定是永假的，即Skolem化并不影響原謂詞公式的永假性。子句集S的不可滿足性：對于任意論域中的任意一個(gè)解釋，S中的子句不能同時(shí)取得真值T。子句集及其化簡子句集的意義子句集及其化簡定理：設(shè)有謂詞公式F，其子句集為S，則F不可滿足的充要條件是S不可滿足。由此定理可知，要證明一個(gè)謂詞公式是不可滿足的，只要證明其相應(yīng)的標(biāo)準(zhǔn)子句集是不可滿足的就可以了。由于子句集中的子句之間是合取關(guān)系，子句集中只要有一個(gè)子句為不可滿足，則整個(gè)子句集就是不可滿足的?？兆泳涫遣豢蓾M足的。因此，一個(gè)子句集中如果包含有空子句，則此子句集就一定是不可滿足的。這個(gè)結(jié)論是魯濱遜消解原理的主要依據(jù)。子句集及其化簡定理：設(shè)有謂詞公式F，其子句集為S，則F不可滿消解演繹推理消解演繹推理子句集及其化簡魯濱遜消解原理消解反演推理的消解策略用消解反演求取問題的答案消解演繹推理消解演繹推理魯濱遜消解原理魯濱遜消解原理的基本思想首先把欲證明問題的結(jié)論否定，并加入子句集，得到一個(gè)擴(kuò)充的子句集S'；然后設(shè)法檢驗(yàn)子句集S'是否含有空子句，若含有空子句，則表明S'是不可滿足的；若不含有空子句，則繼續(xù)使用消解法，在子句集中選擇合適的子句進(jìn)行消解，直至導(dǎo)出空子句或不能繼續(xù)消解為止。魯濱遜消解原理包括命題邏輯的消解謂詞邏輯的消解魯濱遜消解原理魯濱遜消解原理的基本思想命題邏輯的消解消解推理的核心是求兩個(gè)子句的消解式消解式的定義及性質(zhì)若P是原子謂詞公式，則稱P與﹁P為互補(bǔ)文字設(shè)C1和C2是子句集中的任意兩個(gè)子句，如果C1中的文字L1與C2中的文字L2互補(bǔ)，那么可從C1和C2中分別消去L1和L2，并將C1和C2中余下的部分按析取關(guān)系構(gòu)成一個(gè)新的子句C12，則稱這一過程為消解，稱C12為C1和C2的消解式，稱C1和C2為C12的親本子句。命題邏輯的消解消解推理的核心是求兩個(gè)子句的消解式命題邏輯的消解例如：設(shè)C1=P∨Q∨R，C2=﹁P∨S，求C1和C2的消解式C12。解：這里L(fēng)1=P，L2=﹁P，通過消解可以得到C12=Q∨R∨S例如：設(shè)C1=﹁Q，C2=Q，求C1和C2的消解式C12。解：這里L(fēng)1=﹁Q，L2=Q，通過消解可以得到

C12=NIL命題邏輯的消解例如：設(shè)C1=P∨Q∨R，C2=﹁P∨S，求C命題邏輯的消解例如：設(shè)設(shè)C1=﹁P∨

Q

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

P

NIL﹁P∨Q

P

Q﹁Q

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

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

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

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

人工智能第二章：知識表示與推理ArtificialIntelligence(AI)

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

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

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

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

P(x)使得每個(gè)否定符號最多只作用于一個(gè)謂詞上。例如：上式(?x)(﹁(?y)P(x,y)∨﹁(?y)(﹁Q(x,y)∨R(x,y)))經(jīng)等價(jià)變換后為

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

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

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

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

(?x)(

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

∧(﹁P(x,f(x))﹁R(x,g(x))))Step7：消去全稱量詞。由于母式中的全部變元均受全稱量詞的約束，并且全稱量詞的次序已無關(guān)緊要，因此可以省掉全稱量詞。例如：上式消去全稱量詞后為(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x)))Step8：對變元更名，使不同子句中的變元不同名例如：上式經(jīng)更名后得到(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(y,f(y))∨﹁R(y,g(y)))子句集及其化簡例如：前面的公式化為Skolem標(biāo)準(zhǔn)形后為子句集及其化簡Step9：消去合取詞，就得到子句集。例如：消去合取詞后，上式(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(y,f(y))∨﹁R(y,g(y)))

就變?yōu)橄率鲎泳浼鑀(x,f(x))∨Q(x,g(x))﹁P(y,f(y))∨﹁R(y,g(y))子句集及其化簡Step9：消去合取詞，就得到子句集。子句集及其化簡子句集的意義在上述化簡過程中，由于在消去存在量詞時(shí)所用的Skolem函數(shù)可以不同，因此化簡后的標(biāo)準(zhǔn)子句集是不唯一的。因此，當(dāng)原謂詞公式為非永假時(shí)，它與其標(biāo)準(zhǔn)子句集并不等價(jià)。但當(dāng)原謂詞公式為永假（或不可滿足）時(shí)，其標(biāo)準(zhǔn)子句集則一定是永假的，即Skolem化并不影響原謂詞公式的永假性。子句集S的不可滿足性：對于任意論域中的任意一個(gè)解釋，S中的子句不能同時(shí)取得真值T。子句集及其化簡子句集的意義子句集及其化簡定理：設(shè)有謂詞公式F，其子句集為S，則F不可滿足的充要條件是S不可滿足。由此定理可知，要證明一個(gè)謂詞公式是不可滿足的，只要證明其相應(yīng)的標(biāo)準(zhǔn)子句集是不可滿足的就可以了。由于子句集中的子句之間是合取關(guān)系，子句集中只要有一個(gè)子句為不可滿足，則整個(gè)子句集就是不可滿足的。空子句是不可滿足的。因此，一個(gè)子句集中如果包含有空子句，則此子句集就一定是不可滿足的。這個(gè)結(jié)論是魯濱遜消解原理的主要依據(jù)。子句集及其化簡定理：設(shè)有謂詞公式F，其子句集為S，則F不可滿消解演繹推理消解演繹推理子句集及其化簡魯濱遜消解原理消解反演推理的消解策略用消解反演求取問題的答案消解演繹推理消解演繹推理魯濱遜消解原理魯濱遜消解原理的基本思想首先把欲證明問題的結(jié)論否定，并加入子句集，得到一個(gè)擴(kuò)充的子句集S'；然后設(shè)法檢驗(yàn)子句集S'是否含有空子句，若含有空子句，則表明S'是不可滿足的；若不含有空子句，則繼續(xù)使用消解法，在子句集中選擇合適的子句進(jìn)行消解，直至導(dǎo)出空子句或不能繼續(xù)消解為止。魯濱遜消解原理包括命題邏輯的消解謂詞邏輯的消解魯濱遜消解原理魯濱遜消解原理的基本思想命題邏輯的消解消解推理的核心是求兩個(gè)子句的消解式消解式的定義及性質(zhì)若P是原子謂詞公式，則稱P與﹁P為互補(bǔ)文字設(shè)C1和C2是子句集中的任意兩個(gè)子句，如果C1中的文字L1與C2中的文字L2互補(bǔ)，那么可從C1和C2中分別消去L1和L2，并將C1和C2中余下的部分按析取關(guān)系構(gòu)成一個(gè)新的子句C12，則稱這一過程為消解，稱C12為C1和C2的消解式，稱C1和C2為C12的親本子句。命題邏輯的消解消解推理的核心是求兩個(gè)子句的消解式命題邏輯的消解例如：設(shè)C1=P∨Q∨R，C2=﹁P∨S，求C1和C2的消解式C12。解：這里L(fēng)1=P，L2=﹁P，通過消解可以得到C12=Q∨R∨S例如：設(shè)C1=﹁Q，C2=Q，求C1和C2的消解式C12。解：這里L(fēng)1=﹁Q，L2=Q，通過消解可以得到

C12=NIL命題邏輯的消解例如：設(shè)C1=P∨Q∨R，C2=﹁P∨S，求C命題邏輯的消解例如：設(shè)設(shè)C1=﹁P∨

Q

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

P

NIL﹁P∨Q

P

Q﹁Q