高級人工智能-確定性推理.pptx

人工智能,確定性推理,2016年秋季,羅平luop,本章內(nèi)容,推理的基本概念推理的邏輯基礎(chǔ)自然演繹推理歸結(jié)推理,本章內(nèi)容,推理的基本概念推理的邏輯基礎(chǔ)自然演繹推理歸結(jié)推理,什么是推理,推理是指按照某種策略從已知事實(shí)出發(fā)去推出結(jié)論的過程。推理所用的事實(shí)：初始證據(jù)：推理前用戶提供的中間結(jié)論：推理過程中所得到的推理過程：由推理機(jī)來完成推理的兩個基本問題推理的方法：解決前提和結(jié)論的邏輯關(guān)系，不確定性傳遞推理的控制策略：解決推理方向，沖突消解策略,推理方法及其分類,演繹推理：一般到個別的推理方法：從已知的一般性知識出發(fā)，去推出蘊(yùn)含在這些已知知識中的適合于某種個別情況的結(jié)論核心：三段論。常用的三段論包括：大前提：已知的一般性知識或推理過程得到的判斷小前提：關(guān)于某種具體情況或某個具體實(shí)例的判斷結(jié)論：由大前提推出的，并且適合于小前提的判斷。例如，有如下三個判斷：計(jì)算機(jī)系的學(xué)生都會編程序；（一般性知識）程強(qiáng)是計(jì)算機(jī)系的一位學(xué)生；（具體情況）程強(qiáng)會編程序。（結(jié)論）結(jié)論是蘊(yùn)含在大前提中的,歸納推理：由個別到一般的推理方法完全歸納推理：是指在進(jìn)行歸納時需要考察相應(yīng)事物的全部對象，并根據(jù)這些對象是否都具有某種屬性，推出該類事物是否具有此屬性。不完全歸納推理：是指在進(jìn)行歸納時只考察了相應(yīng)事物的部分對象，就得出了關(guān)于該事物的結(jié)論。例如，隨機(jī)抽查。枚舉歸納推理：是指在進(jìn)行歸納時，如果已知某類事物的有限可數(shù)個具體事物都具有某種屬性，則可推出該類事物都具有此種屬性。例如，設(shè)有如下事例：王強(qiáng)是計(jì)算機(jī)系學(xué)生，他會編程序；高華是計(jì)算機(jī)系學(xué)生，她會編程序；當(dāng)這些具體事例足夠多時，就可歸納出一個一般性的知識：凡是計(jì)算機(jī)系的學(xué)生，就一定會編程序。,推理方法及其分類,類比歸納推理：是在兩個或兩類事物有許多屬性都相同或相似的基礎(chǔ)上，推出它們在其他屬性上也相同或相似的一種歸納推理設(shè)A、B分別是兩類事物的集合：A=a1,a2,B=b1,b2,并設(shè)ai與bi總是成對出現(xiàn)，且當(dāng)ai有屬性P時，bi就有屬性Q與此對應(yīng)，即P(ai)Q(bi)i=1,2,.則當(dāng)A與B中有一新的元素對出現(xiàn)時，若已知a有屬性P，b有屬性Q，即P(a)Q(b)類比歸納推理的基礎(chǔ)是相似原理，其可靠程度取決于兩個或兩類事物的相似程度以及這兩個或兩類事物的相同屬性與推出的那個屬性之間的相關(guān)程度。,推理方法及其分類,演繹推理與歸納推理的區(qū)別演繹推理：在已知領(lǐng)域內(nèi)的一般性知識的前提下，通過演繹求解一個具體問題或者證明一個結(jié)論的正確性不能增殖新知識：所得出的結(jié)論蘊(yùn)含在一般性知識的前提中，推理過程是將已有事實(shí)揭露出來歸納推理所推出的結(jié)論是沒有包含在前提內(nèi)容中的增殖新知識的過程：是由個別事物或現(xiàn)象推出一般性知識的過程。,推理方法及其分類,按所用知識的確定性分類確定性推理vs.不確定性推理按推理過程的單調(diào)性分類單調(diào)推理vs.非單調(diào)推理單調(diào)：不會由于新知識的加入否定前面的結(jié)論(不能取消原有的結(jié)論)非單調(diào)：知識不完全情況下，某些新知識的加入會否定前面的結(jié)論,推理方法及其分類,推理的控制策略及其分類,推理的控制策略推理過程不僅依賴于所用的推理方法，同時也依賴于推理的控制策略推理的控制策略是指如何使用領(lǐng)域知識使推理過程盡快達(dá)到目標(biāo)的策略控制策略的分類推理策略主要解決推理方向、沖突消解等問題，如推理方向控制策略、求解策略、限制策略、沖突消解策略等推理方向控制策略：確定推理的控制方向，可分為正向推理、逆向推理、混合推理及雙向推理。求解策略：確定是僅求一個解、求所有解、還是最優(yōu)解等。限制策略：對推理的深度、寬度、時間、空間等進(jìn)行的限制。沖突消解策略：當(dāng)推理過程有多條知識可用時，如何從這多條可用知識中選出一條最佳知識用于推理的策略。搜索策略主要解決推理線路、推理效果、推理效率等問題,正向推理,逆向推理,混合推理,混合推理把正向推理和逆向推理結(jié)合起來所進(jìn)行的推理用于解決較復(fù)雜問題?；旌贤评淼姆椒ㄏ日蚝竽嫦颍合冗M(jìn)行正向推理，從已知事實(shí)出發(fā)推出部分結(jié)果，然后再用逆向推理對這些結(jié)果進(jìn)行證實(shí)或提高它們的可信度。先逆向后正向：先進(jìn)行逆向推理，從假設(shè)目標(biāo)出發(fā)推出一些中間假設(shè)，然后再用正向推理對這些中間假設(shè)進(jìn)行證實(shí)。雙向混合：正向推理和逆向推理同時進(jìn)行，使推理過程在中間的某一步結(jié)合起來。,本章內(nèi)容,推理的基本概念推理的邏輯基礎(chǔ)自然演繹推理歸結(jié)推理,謂詞公式的解釋（語義）,命題邏輯vs.謂詞邏輯命題邏輯：命題符號P，Q代表一定的命題，看不出關(guān)系，表達(dá)不出共同特征謂詞邏輯：可表示關(guān)系。如：Weather(Tuesday，Rain）允許包含變元。如：Weather（X，Rain）命題公式的解釋：命題公式的一個解釋就是對該謂詞公式中各個命題變元的一次真值指派可根據(jù)解釋求出該命題公式的真值謂詞公式的解釋：先考慮這些個體常量和函數(shù)在個體域上的取值，然后根據(jù)其具體取值為謂詞分別指派真值。,設(shè)D是謂詞公式P的非空個體域，若對P中的個體常量、函數(shù)和謂詞按如下規(guī)定賦值：為每個個體常量指派D中的一個元素；對每一個變元，指派D的一個非空集合，這是該變元的變域(個體域)；為每個n元函數(shù)指派一個從Dn到D的一個映射，其中Dn=(x1,x2,xn)|x1,x2,xnD為每個n元謂詞指派一個從Dn到F，T的映射。則稱這些指派為P在D上的一個解釋I,謂詞公式的解釋（語義）,謂詞公式的解釋（語義）,例1：設(shè)個體域D=1,2，求公式A=(x)(y)P(x,y)在D上的解釋，并指出在每一種解釋下公式A的真值。解：由于公式A中沒有包含個體常量和函數(shù)，故可直接為謂詞指派真值，設(shè)有把P理解為一個元素為二元組的集合P=(1,1),(2,1),謂詞公式的解釋（語義）,例1：設(shè)個體域D=1,2，求公式A=(x)(y)P(x,y)在D上的解釋，并指出在每一種解釋下公式A的真值。解：由于公式A中沒有包含個體常量和函數(shù)，故可直接為謂詞指派真值，設(shè)有這就是公式A在D上的一個解釋。從這個解釋可以看出：當(dāng)x=1、y=1時，有P(x,y)的真值為T;當(dāng)x=2、y=1時，有P(x,y)的真值為T;即對x在D上的任意取值，都存在y=1使P(x,y)的真值為T。因此，在此解釋下公式A的真值為T。,P=(1,1),(2,1),說明：一個謂詞公式在其個體域上的解釋不是唯一的。例如，對公式A，若給出另一組真值指派這也是公式A在D上的一個解釋。從這個解釋可以看出：當(dāng)x=2、y=1時，有P(x,y)的真值為F;當(dāng)x=2、y=2時，有P(x,y)的真值為F;即對x在D上的任意取值，不存在一個y使得P(x,y)的真值為T。因此，在此解釋下公式A的真值為F。,謂詞公式的解釋（語義）,公式A=(x)(y)P(x,y),P=(1,1),(1,2),例2設(shè)個體域D=1,2，給出公式B=(x)P(f(x),a)在D上的解釋，并指出在該解釋下公式B的真值。解：設(shè)對個體常量a和函數(shù)f(x)的值指派為：對謂詞的真值指派為：根據(jù)此解釋下有當(dāng)x=1時，a=1使P(1,1)=T當(dāng)x=2時，a=1使P(2,1)=T即對x在D上的任意取值，都存在a=1使P(f(x),a)的真值為T。因此，在此解釋下公式B的真值為T。可以看出，謂詞公式的真值都是針對某一個解釋而言的，它可能在某一個解釋下真值為T，而在另一個解釋下為F。,謂詞公式的解釋（語義）,謂詞公式的永真性和可滿足性,永真性：如果謂詞公式P對非空個體域D上的任一解釋都取得真值T，則稱P在D上是永真的；如果P在任何非空個體域上均是永真的，則稱P永真。判定一謂詞公式為永真，必須對每個非空個體域上的每個解釋逐一進(jìn)行判斷可滿足性（相容性）：對于謂詞公式P，如果至少存在D上的一個解釋，使公式P在此解釋下的真值為T，則稱公式P在D上是可滿足的。永假性（不可滿足性）：如果謂詞公式P對非空個體域D上的任一解釋都取真值F，則稱P在D上是永假的；如果P在任何非空個體域上均是永假的，則稱P永假。,謂詞公式的等價性,謂詞公式的等價性：,設(shè)P與Q是D上的兩個謂詞公式，若對D上的任意解釋，P與Q都有相同的真值，則稱P與Q在D上是等價的。如果D是任意非空個體域，則稱P與Q是等價的，記作PQ。,(1)雙重否定律PP(2)交換律(PQ)(QP)，(PQ)(QP)(3)結(jié)合律(PQ)RP(QR)(PQ)RP(QR)(4)分配律P(QR)(PQ)(PR)P(QR)(PQ)(PR)(5)德摩根(否定)律(PQ)PQ(PQ)PQ(6)吸收律P(PQ)PP(PQ)P(7)補(bǔ)余律PPT,PPF(8)連詞化歸律PQPQPQ(PQ)(QP)PQ(PQ)(QP)(9)量詞轉(zhuǎn)換律(x)P(x)(P)(x)P(x)(P)(10)量詞分配律(x)(PQ)(x)P(x)Q(x)(PQ)(x)P(x)Q,置換律：(PQ)(QP),常用的等價式,謂詞公式的永真蘊(yùn)含式,永真蘊(yùn)含：對謂詞公式P和Q，如果PQ永真，則稱P永真蘊(yùn)含Q，且稱Q為P的邏輯結(jié)論，P為Q的前提，記作PQ。常用的永真蘊(yùn)含式如下：(1)化簡式PQP，PQQ(2)附加式PPQ，QPQ(3)析取三段論P(yáng),PQQ(4)假言推理P,PQQ(5)拒取式Q,PQP(6)假言三段論P(yáng)Q,QRPR(7)二難推理PQ,PR,QRR(8)全稱固化(x)P(x)P(y)其中，y是個體域中的任一個體，依此可消去謂詞公式中的全稱量詞。(9)存在固化(x)P(x)P(y)其中，y是個體域中某一個可以使P(y)為真的個體，依此可消去謂詞公式中的存在量詞。等價式和永真蘊(yùn)含式也稱推理規(guī)則,謂詞公式的范式,范式是謂詞公式的標(biāo)準(zhǔn)形式。在謂詞邏輯中，范式分為兩種：前束范式例如，(x)(y)(z)(P(x)Q(y,z)R(x,z)是前束范式。任一謂詞公式均可化為與其對應(yīng)的前束范式Skolem范式任一謂詞公式均可化為與其對應(yīng)的Skolem范式,置換可簡單的理解為是在一個謂詞公式中用置換項(xiàng)去替換變量,置換,a/x,c/y,f(b)/z,g(y)/x,f(x)/y,x與y之間出現(xiàn)了循環(huán)置換現(xiàn)象。即當(dāng)用g(y)置換x,用f(g(y)置換y時，既沒有消去x，也沒有消去y,g(a)/x,f(x)/y,用g(a)置換x，用f(g(a)置換y，則消去了x和y,通常，置換是用希臘字母、等來表示的,一個謂詞公式的任何例示都是該公式的邏輯結(jié)論,合一:尋找項(xiàng)對變量的置換，使兩個謂詞公式一致例如，設(shè)有公式集F=P(x,y,f(y),P(a,g(x),z)，則=a/x,g(a)/y,f(g(a)/z是它的一個合一。一個公式集的合一不是唯一的，但最一般合一是唯一的。,合一,合一,如何高效實(shí)現(xiàn)合一算法呢？提示：由于謂詞、函數(shù)等只是符號，合一過程中沒有使用其語義信息，僅僅使用其語法信息，因此，將其轉(zhuǎn)換成list的表示形式,合一的算法可以通過遞歸實(shí)現(xiàn),本章內(nèi)容,推理的基本概念推理的邏輯基礎(chǔ)自然演繹推理歸結(jié)推理,自然演繹推理,自然演繹推理：從一組已知為真的事實(shí)出發(fā)，直接運(yùn)用經(jīng)典邏輯中的推理規(guī)則推出結(jié)論的過程稱為自然演繹推理。自然演繹推理最基本的推理規(guī)則是三段論推理，它包括：假言推理P,PQQ拒取式Q,PQP假言三段論P(yáng)Q,QRPR例：設(shè)已知如下事實(shí)：A,B,AC,BCD,DQ。求證：Q為真。證明：因?yàn)锳,ACC假言推理B,CBC引入合取詞BC，BCDD假言推理D,DQQ假言推理因此，Q為真,機(jī)器自動推理,能否設(shè)計(jì)一個算法，自動證明PQ永真。如果這個算法存在，則證明過程，變成了一個計(jì)算過程,歸結(jié)演繹推理,在人工智能中，很多問題都可以轉(zhuǎn)化為一個定理證明問題，即對前提P和結(jié)論Q，證明PQ永真。途徑1：證明PQ在任何一個非空的個體域上都永真（非常困難，甚至不可實(shí)現(xiàn)）的途徑2：反證法.把關(guān)于永真性的證明轉(zhuǎn)化為關(guān)于不可滿足性的證明。即：證明(PQ)或PQ是不可滿足魯賓遜歸結(jié)原理(亦稱為消解原理):魯賓遜于1965年在海伯倫（Herbrand）理論的基礎(chǔ)上提出的基于邏輯的“反證法”使定理證明的機(jī)械化成為現(xiàn)實(shí)。歸結(jié)演繹推理是一種基于魯賓遜（Robinson）歸結(jié)原理的機(jī)器推理技術(shù)。,JohnAlanRobinson,J.A.Robinson.Amachine-orientedlogicbasedontheresolutionprinciple.JournaloftheACM,1965,12(1):23-41,機(jī)器自動推理,子句集的化簡歸結(jié),子句和子句集,魯濱遜歸結(jié)原理的基礎(chǔ)是子句集子句和子句集文字：原子謂詞公式及其否定例如：P(x)、Q(x)、P(x)、Q(x)子句：任何文字的析取式例如：P(x)Q(x)，P(x，f(x)Q(x，g(x)空子句：不含任何文字的子句，通常被一般被記為或NIL空子句是永假的，不可滿足的。子句集：由子句或空子句所構(gòu)成的集合,子句集的化簡,任何一個謂詞公式都可以通過應(yīng)用等價關(guān)系及推理規(guī)則化成相應(yīng)的子句集?；啿襟E：(1)消去連接詞“”和“”反復(fù)使用等價公式：PQPQPQ(PQ)(PQ)例如：(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),(2)減少否定符號的轄域反復(fù)使用雙重否定律：(P)P摩根定律：(PQ)PQ(PQ)PQ量詞轉(zhuǎn)換律：(x)P(x)(x)P(x)(x)P(x)(x)P(x)將每個否定符號“”移到緊靠謂詞的位置，使得每個否定符號最多只作用于一個謂詞上。例如：(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),子句集的化簡,(3)對變元標(biāo)準(zhǔn)化在一個量詞的轄域內(nèi)，把謂詞公式中受該量詞約束的變元全部用另外一個沒有出現(xiàn)過的任意變元代替，使不同量詞約束的變元有不同的名字。例如：(x)(y)P(x，y)(y)(Q(x，y)R(x，y)經(jīng)變換后為(x)(y)P(x，y)(z)(Q(x，z)R(x，z)(4)化為前束范式把所有量詞都移到公式的左邊，并且在移動時不能改變其相對順序。移動的可行性：由于變元已被標(biāo)準(zhǔn)化，每個量詞都有自己的變元，消除了任何由變元引起沖突的可能。例如，(x)(y)P(x，y)(z)(Q(x，z)R(x，z)化為前束范式后為(x)(y)(z)(P(x，y)(Q(x，z)R(x，z),子句集的化簡,(5)消去存在量詞存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)（即它的左邊沒有全稱量詞）：只要用一個新的個體常量替換受該存在量詞約束的變元，就可消去該存在量詞若存在量詞位于一個或多個全稱量詞的轄域內(nèi)，例如(x1)(xn)(y)P(x1，x2,xn,y)則需要用Skolem函數(shù)f(x1，x2,xn)替換受該存在量詞約束的變元y，然后再消去該存在量詞例如，(x)(y)(z)(P(x，y)(Q(x，z)R(x，z)替換后的式子為(x)(P(x,f(x)(Q(x,g(x)R(x,g(x),子句集的化簡,(6)化為Skolem標(biāo)準(zhǔn)形Skolem標(biāo)準(zhǔn)形:(x1)(xn)M(x1,x2,xn)把謂詞公式化為Skolem標(biāo)準(zhǔn)形需要使用以下等價關(guān)系P(QR)(PQ)(PR)例如，為(x)(P(x,f(x)(Q(x,g(x)R(x,g(x)化為Skolem標(biāo)準(zhǔn)形后為(x)(P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x)(7)消去全稱量詞由于母式中的全部變元均受全稱量詞的約束，并且全稱量詞的次序已無關(guān)緊要，因此可以省掉全稱量詞。剩下的母式，仍假設(shè)其變元是被全稱量詞量化的。例如，(x)(P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x)消去全稱量詞后為(P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x),子句集的化簡,(8)消去合取詞在母式中消去所有合取詞，把母式用子句集的形式表示出來例如，(P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x)的子句集中包含以下兩個子句P(x,f(x)Q(x,g(x)P(x,f(x)R(x,g(x)(9)更換變量名稱對子句集中的某些變量重新命名，使任意兩個子句中不出現(xiàn)相同的變量名。例如，對前面的公式，可把第二個子句集中的變元名x更換為y，得到如下子句集P(x,f(x)Q(x,g(x)P(y,f(y)R(y,g(y),子句集的化簡,練習(xí)：子句集化簡,1.(X)(a(X)b(X)c(X,l)(Y)(Zc(Y，Z)d(X,Y)(X)(e(X),2.(X)(a(X)b(X)c(X，l)(y)(Zc(Y,Z)d(X,Y)(）(e(X),3.(X)(a(X)b(X)c(X,l)(Y)(Z)c(Y,Z)d(X,Y)(X)(e(X),4.(X)(a(X)b(X)c(X,l)(Y)(Z)c(Y,Z)d(X,Y)(W)(e(W),5.(X)(Y)(Z)(W)(a(X)b(X)c(X,l)c(Y,Z)d(X,Y)e(W),練習(xí)：子句集化簡,6.(X)(Z)(W)(a(X)b(X)c(X,l)c(f(X),Z)d(X,f(X)e(W),5.(X)(彐Y)(Z)(W)(a(X)b(X)c(X,l)c(Y,Z)d(X,Y)e(W),7.(a(X)b(X)c(X,l)c(f(X),Z)d(X,f(X)e(W),8.a(X)b(X)c(X,l)e(W)a(X)b(X)c(f(X),Z)d(X,f(X)e(W),9a:a(X)b(X)c(X,l)e(W)9b:a(X)b(X)c(f(X),Z)d(X,f(X)e(W),10a:a(X)b(X)c(X,l)e(W)10b:a(U)b(U)c(f(U),Z)d(U,f(U)e(V),子句集的應(yīng)用,注意：由于在消去存在量詞時所用的Skolem函數(shù)可以不同，因此化簡后的標(biāo)準(zhǔn)子句集是不唯一的。Skolem化并不影響原謂詞公式的永假性。Skolem化后得到的公式與原公式不等價，但具有相同的不可滿足性,魯濱遜歸結(jié)原理-基本思想,兩個關(guān)鍵子句集中的子句之間是合取關(guān)系:子句集中只要有一個子句為不可滿足，則整個子句集就是不可滿足的；空子句是不可滿足的:一個子句集中如果包含有空子句，則此子句集就一定是不可滿足的。魯濱遜歸結(jié)原理基本思想首先把欲證明問題的結(jié)論否定，并加入子句集，得到一個擴(kuò)充的子句集S。然后設(shè)法檢驗(yàn)子句集S是否含有空子句，若含有空子句，則表明S是不可滿足的；若不含有空子句，則繼續(xù)使用歸結(jié)法，在子句集中選擇合適的子句進(jìn)行歸結(jié)，直至導(dǎo)出空子句或不能繼續(xù)歸結(jié)為止。,魯濱遜歸結(jié)原理-命題邏輯的歸結(jié),歸結(jié)推理的核心是求兩個子句的歸結(jié)式歸結(jié)式的定義:互補(bǔ)文字:若P是原子謂詞公式，則稱P與P為。設(shè)C1和C2是子句集中的任意兩個子句，如果C1中的文字L1與C2中的文字L2互補(bǔ)，那么可從C1和C2中分別消去L1和L2，并將C1和C2中余下的部分按析取關(guān)系構(gòu)成一個新的子句C12，則稱這一過程為歸結(jié)，稱C12為C1和C2的歸結(jié)式，稱C1和C2為C12的親本子句。例:設(shè)C1=PQR，C2=PS，求C1和C2的歸結(jié)式C12。解：這里L(fēng)1=P，L2=P，通過歸結(jié)可以得到C12=QRS例:設(shè)C1=Q，C2=Q，求C1和C2的歸結(jié)式C12。解：這里L(fēng)1=Q，L2=Q，通過歸結(jié)可以得到C12=NIL,例:設(shè)C1=PQ，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é)原理-命題邏輯的歸結(jié),證明：設(shè)C1=LC1，C2=LC2關(guān)于解釋I為真只需證明C12=C1C2關(guān)于解釋I也為真因?yàn)?，對于解釋I，L和L中必有一個為假若L為假，則必有C1為真，不然就會使C1為假，這將與前提假設(shè)C1為真矛盾，因此只能有C1為真。同理，若L為假，則必有C2為真。因此，必有C12=C1C2關(guān)于解釋I也為真。即C12是C1和C2的邏輯結(jié)論。,魯濱遜歸結(jié)原理-命題邏輯的歸結(jié),證明：設(shè)S=C1，C2，C3，Cn，C12是C1和C2的歸結(jié)式，則用C12代替C1和C2后可得到一個新的子句集S1=C12，C3，,Cn。設(shè)S1是不可滿足的，則對不滿足S1的任一解釋I，都可能有以下兩種情況：解釋I使C12為真，則C3，Cn中必有一個為假，即S是不可滿足的。解釋I使C12為假，即C12為真，根據(jù)上述定理有(C1C2)永真，即C1C2永真，它說明解釋I使C1為假，或C2為假。即S也是不可滿足的。因此可以得出S1的不可滿足性S的不可滿足性,魯濱遜歸結(jié)原理-命題邏輯的歸結(jié),先證明設(shè)S=C1，C2，C3，Cn是不可滿足的，則C1，C2，C3，Cn中必有一子句為假，因而S2=C12，C1，C2，C3，Cn必為不可滿足。再證明設(shè)S2是不可滿足的,則對不滿足S2的任一解釋I,都可能有以下兩種情況：解釋I使C12為真，則C1，C2，C3，Cn中必有一個為假，即S是不可滿足的。解釋I使C12為假，即C12為真，根據(jù)定理3.2有(C1C2)永真，即C1C2永真，它說明解釋I使C1為假，或C2為假。即S也是不可滿足的。由此可見S與S2的不可滿足性是等價的。即S的不可滿足性S2的不可滿足性,魯濱遜歸結(jié)原理-命題邏輯的歸結(jié),為證明子句集S的不可滿足性，只要對其中可進(jìn)行歸結(jié)的子句進(jìn)行歸結(jié)，并把歸結(jié)式加入到子句集S中，或者用歸結(jié)式代替他的親本子句，然后對新的子句集證明其不可滿足性即可。如果經(jīng)歸結(jié)能得到空子句，根據(jù)空子句的不可滿足性，即可得到原子句集S是不可滿足的結(jié)論。在命題邏輯中，對不可滿足的子句集S，歸結(jié)原理是完備的。,魯濱遜歸結(jié)原理-命題邏輯的歸結(jié),例設(shè)已知的公式集為P,(PQ)R,(ST)Q,T，求證結(jié)論R。解：假設(shè)結(jié)論R為假,將R加入公式集，并化為子句集S=P,PQR,SQ,TQ,T,R其歸結(jié)過程如右圖的歸結(jié)演繹樹所示。該樹根為空子句。其含義為：先假設(shè)子句集S中的所有子句均為真，即原公式集為真,R也為真；然后利用歸結(jié)原理，對子句集進(jìn)行歸結(jié)，并把所得的歸結(jié)式并入子句集中；重復(fù)這一過程，最后歸結(jié)出了空子句。,魯濱遜歸結(jié)原理-命題邏輯的歸結(jié),在謂詞邏輯中，由于子句集中的謂詞一般都含有變元，因此不能象命題邏輯那樣直接消去互補(bǔ)文字。而需要先用一個最一般合一對變元進(jìn)行代換，然后才能進(jìn)行歸結(jié)。謂詞邏輯中的歸結(jié)式：,魯濱遜歸結(jié)原理謂詞邏輯的歸結(jié),例設(shè)C1=P(a)R(x)，C2=P(y)Q(b)，求C12解：取L1=P(a),L2=P(y)，則L1和L2的最一般合一是=a/y。C12=(C1-L1)(C2-L2)=(P(a),R(x)-P(a)(P(a),Q(b)-P(a)=(R(x)(Q(b)=R(x),Q(b)=R(x)Q(b),魯濱遜歸結(jié)原理-謂詞邏輯的歸結(jié),例設(shè)C1=P(x)Q(a)，C2=P(b)R(x)，求C12解：由于C1和C2有相同的變元x，不符合定義3.20的要求。為了進(jìn)行歸結(jié)，需要修改C2中變元的名字，令C2=P(b)R(y)。此時L1=P(x),L2=P(b)，L1和L2的最一般合一是=b/x。則有C12=(C1-L1)(C2-L2)=(P(b),Q(a)-P(b)(P(b),R(y)-P(b)=(Q(a)(R(y)=Q(a),R(y)=Q(a)R(y),魯濱遜歸結(jié)原理-謂詞邏輯的歸結(jié),例設(shè)C1=P(x)Q(b)，C2=P(a)Q(y)R(z)解：對C1和C2通過最一般合一（=a/x,b/y）的作用，可以得到兩個互補(bǔ)對。注意：求歸結(jié)式不能同時消去兩個互補(bǔ)對，這樣的結(jié)果不是二元?dú)w結(jié)式。如在=a/x,b/y下，若同時消去兩個互補(bǔ)對，所得的R(z)不是C1和C2的二元?dú)w結(jié)式。,魯濱遜歸結(jié)原理-謂詞邏輯的歸結(jié),例:設(shè)C1=P(x)P(f(a)Q(x)，C2=P(y)R(b)，求C12解：對參加歸結(jié)的某個子句，若其內(nèi)部有可合一的文字，則在進(jìn)行歸結(jié)之前應(yīng)先對這些文字進(jìn)行合一。C1中有可合一的文字P(x)與P(f(a)，用它們的最一般合一=f(a)/x進(jìn)行代換，可得到C1=P(f(a)Q(f(a)對C1與C2進(jìn)行歸結(jié)。選L1=P(f(a),L2=P(y)，L1和L2的最一般合一是=f(a)/y，則可得到C1和C2的二元?dú)w結(jié)C12=R(b)Q(f(a)若子句C中有兩個或兩個以上的文字具有最一般合一，則稱C為子句C的因子。如果C是一個單文字，則稱它為C的單元因子。,魯濱遜歸結(jié)原理-謂詞邏輯的歸結(jié),定義若C1和C2是無公共變元的子句，則C1和C2的二元?dú)w結(jié)式;C1和C2的因子C22的二元?dú)w結(jié)式；C1的因子C11和C2的二元?dú)w結(jié)式；C1的因子C11和C2的因子C22的二元?dú)w結(jié)式。這四種二元?dú)w結(jié)式都是子句C1和C2的二元?dú)w結(jié)式，記為C12。,魯濱遜歸結(jié)原理-謂詞邏輯的歸結(jié),例3.15設(shè)C1=P(y)P(f(x)Q(g(x)，C2=P(f(g(a)Q(b)，求C12。解：對C1，取最一般合一=f(x)/y，得C1的因子C1=P(f(x)Q(g(x)對C1的因子和C2歸結(jié)（=g(a)/x），可得到C1和C2的二元?dú)w結(jié)式C12=Q(g(g(a)Q(b)說明：對謂詞邏輯，歸結(jié)式C12是其親本子句C1和C2的邏輯結(jié)論。用歸結(jié)式取代它在子句集S中的親本子句，所得到的子句集仍然保持著原子句集S的不可滿足性。對謂詞邏輯，從不可滿足的意義上說，一階謂詞邏輯的歸結(jié)原理也是完備的,魯濱遜歸結(jié)原理-謂詞邏輯的歸結(jié),歸結(jié)演繹推理的歸結(jié)策略,歸結(jié)演繹推理實(shí)際上就是從子句集中不斷尋找可進(jìn)行歸結(jié)的子句對，并通過對這些子句對的歸結(jié)，最終得出一個空子句的過程。由于事先并不知道哪些子句對可進(jìn)行歸結(jié)，更不知道通過對哪些子句對的歸結(jié)能盡快得到空子句，因此就需要對子句集中的所有子句逐對進(jìn)行比較，直到得出空子句為止。盲目的全面進(jìn)行歸結(jié)的方法，不僅會產(chǎn)生許多無用的歸結(jié)式，更嚴(yán)重的是會產(chǎn)生組合爆炸問題。,廣度優(yōu)先是一種窮盡子句比較的復(fù)雜搜索方法設(shè)初始子句集為S0，廣度優(yōu)先策略的歸結(jié)過程：從S0出發(fā)，對S0中的全部子句作所有可能的歸結(jié)，得到第一層歸結(jié)式，把這些歸結(jié)式的集合記為S1;用S0中的子句與S1中的子句進(jìn)行所有可能的歸結(jié)，得到第二層歸結(jié)式，把這些歸結(jié)式的集合記為S2;用S0和S1中的子句與S2中的子句進(jìn)行所有可能的歸結(jié)，得到第三層歸結(jié)式，把這些歸結(jié)式的集合記為S3;如此繼續(xù)，直到得出空子句或不能再繼續(xù)歸結(jié)為止。,歸結(jié)演繹推理的歸結(jié)策略,例設(shè)有如下子句集：S=I(x)R(x),I(a),R(y)L(y),L(a)用廣度優(yōu)先策略證明S為不可滿足。廣度優(yōu)先策略的歸結(jié)樹如下：,歸結(jié)演繹推理的歸結(jié)策略,廣度優(yōu)先策略的優(yōu)點(diǎn)：當(dāng)問題有解時保證能找到最短歸結(jié)路徑。是一種完備的歸結(jié)策略。廣度優(yōu)先策略的缺點(diǎn)：歸結(jié)出了許多無用的子句既浪費(fèi)時間，又浪費(fèi)空間廣度優(yōu)先對大問題的歸結(jié)容易產(chǎn)生組合爆炸，但對小問題卻仍是一種比較好的歸結(jié)策略。,歸結(jié)演繹推理的歸結(jié)策略,常用的歸結(jié)策略可分為兩大類:刪除策略是通過刪除某些無用的子句來縮小歸結(jié)范圍限制策略是通過對參加歸結(jié)的子句進(jìn)行某些限制，來減少歸結(jié)的盲目性，以盡快得到空子句。,歸結(jié)演繹推理的歸結(jié)策略,支持集策略（Setofsupport）：每一次參加歸結(jié)的兩個親本子句中，至少應(yīng)該有一個是由目標(biāo)公式的否定所得到的子句或它們的后裔。支持集策略是完備的，即當(dāng)子句集為不可滿足時，則由支持集策略一定能夠歸結(jié)出一個空子句。也可以把支持集策略看成是在廣度優(yōu)先策略中引入了某種限制條件，這種限制條件代表一種啟發(fā)信息，因而有較高的效率,歸結(jié)演繹推理的歸結(jié)策略,I(x)R(x),I(a),R(y)L(y),L(a),R(a),I(x)L(x),L(a),L(a),I(a),NIL,歸結(jié)演繹推理的歸結(jié)策略,目標(biāo)公式的否定,注：支持集策略限制了子句集元素的劇增，但會增加空子句所在的深度。支持集策略具有逆向推理的含義，由于進(jìn)行歸結(jié)的親本子句中至少有一個與目標(biāo)子句有關(guān)，因此推理過程可以看作是沿目標(biāo)、子目標(biāo)的方向前進(jìn)的。,歸結(jié)演繹推理的歸結(jié)策略,刪除法主要想法是：把子句集中無用的子句刪除掉，這就會縮小搜索范圍，減少比較次數(shù)，從而提高歸結(jié)效率。純文字刪除法如果某文字L在子句集中不存在可與其互補(bǔ)的文字L，則稱該文字為純文字。在歸結(jié)過程中，純文字不可能被消除，用包含純文字的子句進(jìn)行歸結(jié)也不可能得到空子句對子句集而言，刪除包含純文字的子句，是不影響其不可滿足性的。例如，對子句集S=PQR,QR,Q,R,其中P是純文字，因此可以將子句PQR從子句集S中刪除。,歸結(jié)演繹推理的歸結(jié)策略,重言式刪除法如果一個子句中包含有互補(bǔ)的文字對，則稱該子句為重言式。例如P(x)P(x),P(x)Q(x)P(x)都是重言式，不管P(x)的真值為真還是為假，P(x)P(x)和P(x)Q(x)P(x)都均為真。重言式是真值為真的子句。對一個子句集來說，不管是增加還是刪除一個真值為真的子句，都不會影響該子句集的不可滿足性。因此，可從子句集中刪去重言式。,歸結(jié)演繹推理的歸結(jié)策略,如果一個子句只包含一個文字，則稱此子句為單文字子句。單文字子句策略是對支持集策略的進(jìn)一步改進(jìn)，它要求每次參加歸結(jié)的兩個親本子句中至少有一個子句是單文字子句。采用單文字子句策略，歸結(jié)式包含的文字?jǐn)?shù)將少于其非單文字親本子句中的文字?jǐn)?shù)，這將有利于向空子句的方向發(fā)展，因此會有較高的歸結(jié)效率。,歸