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

ArtificialIntelligence(AI)

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

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

(?x)((?y)﹁P(x，y)∨(?y)(Q(x，y)∧﹁R(x，y))子句集及其化化簡(jiǎn)Step3：重新命名變?cè)共煌苛吭~約束的變變?cè)胁煌牡拿掷纾荷鲜浇?jīng)重新命命名變換后為為(?x)((?y)﹁P(x，y)∨(?z)(Q(x，z)∧﹁R(x，z)))Step4：消去存在量詞詞。消去存在在量詞時(shí)，需需要區(qū)分以下下兩種情況：：1）存在量詞不不出現(xiàn)在全稱稱量詞的轄域域內(nèi)，只要用用一個(gè)新的個(gè)個(gè)體常量替換換受該存在量量詞約束的變變?cè)?，就可消消去該存在量量詞。2）存在量詞位位于一個(gè)或者者多個(gè)全稱量量詞的轄域內(nèi)內(nèi)子句集及其化化簡(jiǎn)如下面的謂詞詞公式：(?x1)…(?xn)(?y)P(x1，x2,…,xn,y)則需要用Skolem函數(shù)f(x1，x2,…,xn)替換受該存在在量詞約束的的變?cè)獃，然后再消去去該存在量詞詞。例如：繼續(xù)上面的例例子(?x)((?y)﹁P(x，y)∨(?z)(Q(x，z)∧﹁R(x，z)))式子中存在量量詞(y)及(z)都位于(x)的轄域內(nèi)，所所以需要用Skolem函數(shù)替換，設(shè)設(shè)替換y和z的Skolem函數(shù)分別是f(x)和g(x)，則替換后得得到：(?x)(﹁﹁P(x,f(x))∨(Q(x,g(x))∧﹁R(x,g(x))))子句集及其化化簡(jiǎn)Step5：把全稱量詞全全部移到公式式的左邊上式中由于只只有一個(gè)全稱稱量詞，而且且它位于公式式的最左邊，，所以這里不不需要做任何何工作。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)成。子句集及其化化簡(jiǎn)Skolem標(biāo)準(zhǔn)形的一般般形式為(?x1)…(?xn)M(x1,x2,……,xn)其中，M(x1,x2,……,xn)是Skolem標(biāo)準(zhǔn)形的母式式，它由子句句的合取所構(gòu)構(gòu)成。例如：前面的公式化化為Skolem標(biāo)準(zhǔn)形后為(?x)((﹁P(x,f(x))∨Q(x,g(x)))∧(﹁P(x,f(x))﹁R(x,g(x))))Step7：消去全稱量詞詞。由于母式式中的全部變變?cè)苋Q稱量詞的約束束，并且全稱稱量詞的次序序已無關(guān)緊要要，因此可以以省掉全稱量量詞。例如如：：上式式消消去去全全稱稱量量詞詞后后為為(﹁﹁P(x,f(x))∨∨Q(x,g(x))∧∧(﹁﹁P(x,f(x))∨∨﹁﹁R(x,g(x)))子句句集集及及其其化化簡(jiǎn)簡(jiǎn)Step8：對(duì)變變?cè)?，，使不不同同子子句句中中的的變變?cè)徊煌捎谟诿棵恳灰粋€(gè)個(gè)子子句句都都對(duì)對(duì)應(yīng)應(yīng)著著母母式式中中的的一一個(gè)個(gè)合合取取元元，，并并且且所所有有變變?cè)级际鞘怯捎扇Q稱量量詞詞量量化化的的，，因因此此任意意兩兩個(gè)個(gè)不不同同子子句句的的變變量量之之間間實(shí)實(shí)際際上上不不存存在在任任何何關(guān)關(guān)系系，，更更換換變變量量名名不不會(huì)會(huì)影影響響公公式式的的真真值值。。例如如：：上式式經(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))子句句集集及及其其化化簡(jiǎn)簡(jiǎn)子句句集集的的意意義義在上上述述化化簡(jiǎn)簡(jiǎn)過過程程中中，，由由于于在在消消去去存存在在量量詞詞時(shí)時(shí)所所用用的的Skolem函數(shù)數(shù)可可以以不不同同，，因因此此化簡(jiǎn)簡(jiǎn)后后的的標(biāo)標(biāo)準(zhǔn)因此，當(dāng)原謂詞公式為非永假時(shí)，它與其標(biāo)準(zhǔn)子句集并不等價(jià)。但當(dāng)原謂詞公式為永假（或不可滿足）時(shí)，其標(biāo)準(zhǔn)子句集則一定是永假的，即Skolem化并不影響原謂詞公式的永假性。子句集S的不可滿足性：對(duì)于任意論域中的任意一個(gè)解釋，S中的子句不能同時(shí)取得真值T。子句句集集及及其其化化簡(jiǎn)簡(jiǎn)定理理：：設(shè)有有謂謂詞詞公公式式F，其其子子句句集集為為S，則則F不可可滿滿足足的的充充要要條條件件是是S不可可滿滿足足。由此此定定理理可可知知，，要要證證明明一一個(gè)個(gè)謂謂詞詞公公式式是是不不可可滿滿足足的的，，只只要要證證明明其其相相應(yīng)應(yīng)的的標(biāo)標(biāo)準(zhǔn)準(zhǔn)子子句句集集是是不不可可滿滿足足的的就就可可以以了了。。由于于子子句句集集中中的的子子句句之之間間是是合合取取空子句是不可滿足的。因此，一個(gè)子句集中如果包含有空子句，則此子句集就一定是不可滿足的。這個(gè)結(jié)論是魯濱遜歸結(jié)原理的主要依據(jù)。歸結(jié)結(jié)演演繹繹推推理理歸結(jié)結(jié)演子句集及其化簡(jiǎn)魯濱遜歸結(jié)原理歸結(jié)反演推理的歸結(jié)策略用歸結(jié)反演求取問題的答案魯濱濱遜遜歸歸結(jié)結(jié)原原理理海伯伯倫倫（（Herbrand）理理論論為了了判判斷斷子子句句集集的的不不可可滿滿足足性性，，需需要要對(duì)對(duì)所所海伯倫構(gòu)造了一個(gè)特殊的論域（海伯倫域），并證明只要對(duì)這個(gè)特殊域上的一切解釋進(jìn)行判定，就可知子句集是否不可滿足。海伯倫定理：子句集不可滿足的充要條件是存在一個(gè)有限的不可滿足的基子句集。海伯倫從理論上給出了證明子句集不可滿足性的可行性及方法，但是要在計(jì)算機(jī)上實(shí)現(xiàn)是很困難的。魯濱濱遜遜歸歸結(jié)結(jié)原原理理魯濱濱遜遜歸歸結(jié)結(jié)原原理理的的基基本本思思想想首先先把把欲欲證證明明問問題題的的結(jié)結(jié)論論否定定，并并加加入入子子句句集集，，得得到到一一個(gè)個(gè)擴(kuò)擴(kuò)充充的的子子句句集集S'；然后后設(shè)設(shè)法法檢檢驗(yàn)驗(yàn)子子句句集集S'是否否含含有有空空子子句句，，若若含含有有空空子子句句，，則則表表明明S'是不不可可滿滿足足的的；；若若不不含魯濱遜歸結(jié)原理包括命題邏輯消解原理謂詞邏輯消解原理命題題邏邏輯輯的的歸歸結(jié)結(jié)歸結(jié)結(jié)歸結(jié)式的定義及性質(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，則稱這一過程為歸結(jié)，稱C12為C1和C2的歸結(jié)式，稱C1和C2為C12的親本子句。命題邏邏輯的的歸結(jié)結(jié)例如：：設(shè)C1=P∨Q∨∨R，C2=﹁P∨S，求C1和C2的歸結(jié)結(jié)式C12。解：這里L(fēng)1=P，L2=﹁P，通過過歸結(jié)結(jié)可以以得C12=Q∨R∨S例如：設(shè)C1=﹁Q，C2=Q，求C1和C2的歸結(jié)式C12。解：這里L(fēng)1=﹁Q，L2=Q，通過歸結(jié)可以得到

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

P

NIL﹁P∨Q

P

Q﹁Q

NIL命題邏邏輯的的歸結(jié)結(jié)定理：：歸結(jié)式式C12是其親親本子子句C1和C2的邏輯輯結(jié)論論。證明：：設(shè)C1=L∨∨C1’，C2=﹁L∨∨C2’關(guān)于解釋釋I為真，則則只需證證明C12=C1’∨C2’關(guān)于解釋釋I也為真。。對(duì)于解釋釋I，L和﹁L中必有一一個(gè)為假假。若L為假，則必有有C1'為真，不不然就會(huì)會(huì)使C1為假，這這將與前前提假設(shè)設(shè)C1為真矛盾盾，因此此只能有有C1'為真。同理，若﹁L為假，則必有有C2'為真。因此，必必有C12=C1'∨C2'關(guān)于解釋釋I也為真。。即C12是C1和C2的邏輯結(jié)結(jié)論。命題邏輯輯的歸結(jié)結(jié)推論1：設(shè)C1和C2是子句集集S中的兩個(gè)個(gè)子句，，C12是C1和C2的歸結(jié)式式，若用C12代替C1和C2后得到新新的子句句集S1，則由S1的不可滿滿足性可可以推出出原子句句集S的不可滿滿足性。。即：S1的不可滿滿足性?S的不可滿滿足性推論2：設(shè)C1和C2是子句集集S中的兩個(gè)個(gè)子句，，C12是C1和C2的歸結(jié)式式，若把C12加入S中得到新新的子句句集S2，則S與S2的不可滿滿足性是是等價(jià)的的。即：：S2的不可滿滿足性?S的不可滿滿足性命題邏輯輯的歸結(jié)結(jié)上述兩個(gè)個(gè)推論說說明，為為證明子子句集S的不可滿滿足性，，只要對(duì)對(duì)其中可可進(jìn)行歸歸結(jié)得子子句進(jìn)行行歸結(jié)，，并把歸結(jié)結(jié)式加入入到子句句集S中，或者者用歸結(jié)結(jié)式代替替他的親親本子句句，然后對(duì)對(duì)新的子子句集證證明其不不可滿足足性就可可以了。。如果經(jīng)歸歸結(jié)能得得到空子子句，根根據(jù)空子子句的不不可滿足足性，即即可得到到原子句句集S是不可滿滿足的結(jié)