西電人工智能確定性推理ar2

ArtificialIntelligence(AI)

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

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→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)生知識爆炸，推理過程中得到的中間結論一般按指數(shù)規(guī)律遞增，對于復雜問題的推理不利，甚至難以實現(xiàn)。內容提要要第三章：：確定性性推理1.推理的基基本概念念2.搜索策略略3.自然演繹繹推理4.歸結演繹繹推理5.基于規(guī)則則的演繹繹推理歸結演繹繹推理歸結演繹繹推理：：是一種基基于魯濱濱遜（Robinson）歸結原原理的機機器推理理技術。。魯濱遜歸歸結原理理亦稱為為消解原理理，是魯濱濱遜于1965年在海伯伯倫（Herbrand）理論的的基礎上上提出的的一種基基于邏輯輯的“反證法”。在人工智智能中，，幾乎所所有的問問題都可可以轉化化為一個個定理證證明問題題。定理理證明的的實質，，就是要證明P→Q永真，就是要證明P→Q在任何一個非空的個體域上都是永真的。這將是非常困難的，甚至是不可實現(xiàn)的。歸結演繹繹推理歸結演繹繹推理：：魯濱遜歸歸結原理理把永真真性的證證明轉化化為關于于不可滿滿足性的的證明。。要證明P→Q永真，只需證證明P∧﹁Q不可滿足足因為：﹁(P→Q)?﹁﹁(﹁﹁P∨∨Q)??P∧﹁Q海伯倫(Herbrand)定理為自自動定理理證明奠奠定了理理論基礎礎。魯濱遜(Robinson)提出的歸歸結原理理使機器器定理證證明成為為現(xiàn)實。。歸結演繹繹推理歸結演繹繹推理子句集及及其化簡簡魯濱遜歸歸結原理理歸結反演用歸結反演求取問題的答案歸結演繹繹推理歸結演繹繹推理子句集及及其化簡簡魯濱遜歸歸結原理理歸結反演演推理的的歸結策策略用歸結反反演求取取問題的的答案子句集及及其化簡簡無論是海海伯倫理理論，還還是魯濱濱遜歸結結原理是是在子句集的基礎上上討論問問題的。。因此，，討論歸歸結演繹繹推理之之前，需需要先討討論子句句集的有有關概念念。子句和子子句集原子謂詞詞公式及及其否定定統(tǒng)稱為為文字。例如:P(x)、Q(x)、﹁P(x)、﹁Q(x)等都是文文字。任何文字的析取式稱為子句。例如，P(x)∨Q(x)，P(x，f(x))∨Q(x，g(x))都是子句句。子句集及及其化簡簡子句和子子句集不含任何何文字的的子句稱稱為空子句。由于空子子句不含含有任何何文字，，也就不不能被任任何解釋釋所滿足足，因此此空子句句是永假的，不可滿足足的?？兆泳湟灰话惚挥浻洖镹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量詞轉換率：：﹁(?x)P(x)??(?x)﹁P(x)﹁(?x使得每個否定符號最多只作用于一個謂詞上。例如：上式經(jīng)等價變換后為

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

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

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

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

P

NIL﹁P∨Q

P

Q﹁Q

NIL命題邏邏輯的的歸結結定理：：歸結式式C12是其親親本子子句C1和C2的邏輯輯結論論。證明：：設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的邏輯結結論。命題邏輯輯的歸結結推論1：設C1和C2是子句集集S中的兩個個子句，，C12是C1和C2的歸結式式，若用C12代替C1和C2后得到新新的子句句集S1，則由S1的不可滿滿足性可可以推出出原子句句集S的不可滿滿足性。。即：S1的不可滿滿足性?S的不可滿滿足性推論2：設C1和C2是子句集集S中的兩個個子句，，C12是C1和C2的歸結式式，若把C12加入S中得到新新的子句句集S2，則S與S2的不可滿滿足性是是等價的的。即：：S2的不可滿滿足性?S的不可滿滿足性命題邏輯輯的歸結結上述兩個個推論說說明，為為證明子子句集S的不可滿滿足性，，只要對對其中可可進行歸歸結得子子句進行行歸結，，并把歸結結式加入入到子句句集S中，或者者用歸結結式代替替他的親親本子句句，然后對對新的子子句集證證明其不不可滿足足性就可可以了。。如果經(jīng)歸歸結能得得到空子子句，根根據(jù)空子子句的不不可滿足足性，即即可得到到原子句句集S是不可滿滿足的結