人工智能ch6 經(jīng)典邏輯推理

第二部分推理第6章經(jīng)典邏輯推理第7章不確定性推理第8章模糊推理推理與人工智能推理是人類求解問題的主要思維方法，其任務(wù)是利用知識(shí)得到結(jié)論，因而與知識(shí)的表達(dá)方法有密切的關(guān)系。計(jì)算機(jī)雖可以存儲(chǔ)大量知識(shí)，卻并不代表它擁有智能。只有當(dāng)它能利用這些知識(shí)進(jìn)行推理，求解問題（即具有思維能力），才認(rèn)為它擁有智能。因此，關(guān)于推理及其方法的研究成為人工智能的一個(gè)重要研究課題。經(jīng)典邏輯推理是最先提出的一種方法。推理的概念

例如：醫(yī)療診斷專家系統(tǒng)。知識(shí)庫(kù)存儲(chǔ)專家的經(jīng)驗(yàn)及醫(yī)學(xué)常識(shí)；數(shù)據(jù)庫(kù)存放病人的癥狀、化驗(yàn)結(jié)果等初始事實(shí)。利用該專家系統(tǒng)為病人診治疾病就是一次推理過程。即從病人的癥狀及化驗(yàn)結(jié)果等初始事實(shí)出發(fā)，利用知識(shí)庫(kù)中的知識(shí)及一定的控制策略，對(duì)病情作出診斷，并開出醫(yī)療處方。按照某種策略從已有事實(shí)和知識(shí)推出另一判斷的過程。從初始事實(shí)出發(fā)，不斷運(yùn)用知識(shí)庫(kù)中的已知知識(shí)，逐步推出結(jié)論的過程就是推理。推理的概念推理一般包括兩種判斷：已知的判斷，包括已掌握的與求解問題有關(guān)的知識(shí)及關(guān)于問題的已知事實(shí)；由已知判斷推出的新判斷，即推理的結(jié)論。在人工智能系統(tǒng)中，推理是由程序?qū)崿F(xiàn)的，稱為推理機(jī)。推理機(jī)利用知識(shí)庫(kù)中的知識(shí)，按一定的控制策略求解問題。推理方式分類推理方式演繹推理、歸納推理、默認(rèn)推理確定性推理、不確定性推理單調(diào)推理、非單調(diào)推理啟發(fā)式推理、非啟發(fā)式推理基于知識(shí)的推理、統(tǒng)計(jì)推理、直覺推理推出新判斷的途徑推理時(shí)所用知識(shí)的確定性推出結(jié)論是否越來越接近最終目標(biāo)，即結(jié)論是否單調(diào)增加推理時(shí)是否應(yīng)用與問題相關(guān)的啟發(fā)性知識(shí)從方法論角度出發(fā)推理的控制策略推理是一個(gè)求解問題的過程。求解的質(zhì)量和效率與求解方法以及求解問題的策略有關(guān)?？刂撇呗灾饕ǎ和评矸较虻倪x擇、搜索策略、沖突消解策略、求解策略、限制策略等。求解策略確定推理是只求一個(gè)解，還是求所有解及最優(yōu)解。限制策略為防止無窮推理過程，或由于推理過程太長(zhǎng)增加時(shí)間及空間的復(fù)雜性，對(duì)推理的深度、寬度、時(shí)間、空間等進(jìn)行限制。推理的控制策略推理方向確定推理的驅(qū)動(dòng)方式。分為：正向推理、反向(逆向)推理、混合推理、雙向推理。無論采用哪種方向，系統(tǒng)一般都包含：存放知識(shí)的知識(shí)庫(kù)、存放初始已知事實(shí)及問題狀態(tài)的數(shù)據(jù)庫(kù)、用于推理的推理機(jī)。模式匹配模式匹配：對(duì)兩個(gè)知識(shí)模式(如謂詞公式、框架片斷、語義網(wǎng)絡(luò)片斷等)的比較與耦合，即檢查這兩個(gè)知識(shí)模式是否完全一致或近似一致。按匹配時(shí)兩個(gè)知識(shí)模式的相似程度劃分：確定性匹配(完全匹配、精確匹配)——兩個(gè)模式完全一致，或經(jīng)過變量代換后變得完全一致。置換與合一(謂詞邏輯表示法)不確定性匹配——兩個(gè)模式不完全一致，但相似程度在規(guī)定限度內(nèi)。沖突消解策略在推理過程中，系統(tǒng)不斷地用DB中的事實(shí)與KB中的規(guī)則進(jìn)行匹配，當(dāng)發(fā)生以下情況之一：已知事實(shí)可與KB中的多各個(gè)知識(shí)匹配成功；有多個(gè)(組)已知事實(shí)都可與KB中某個(gè)知識(shí)匹配成功；有多個(gè)(組)已知事實(shí)可與KB中的多個(gè)知識(shí)匹配成功。需要用沖突消解策略來決定先使用哪個(gè)知識(shí)。沖突消解策略實(shí)際上就是確定規(guī)則的啟用順序。沖突消解策略以產(chǎn)生式系統(tǒng)為例，在產(chǎn)生式系統(tǒng)中，若出現(xiàn)以下情況就認(rèn)為發(fā)生了沖突：對(duì)正向推理，如果有多條產(chǎn)生式規(guī)則的前件都和已知事實(shí)匹配成功；或有多組不同的已加事實(shí)都與同一條產(chǎn)生式規(guī)則的前件匹配成功；或以上兩種情況同時(shí)出現(xiàn)。對(duì)逆向推理而言，如果有多條產(chǎn)生式規(guī)則的后件都和某個(gè)假設(shè)匹配成功；或有多條產(chǎn)生式規(guī)則的后件可與多個(gè)假設(shè)匹配成功。常用的沖突解決策略有：專一性排序、按己知事實(shí)的新鮮性排序、數(shù)據(jù)排序、上下文限制、按條件個(gè)數(shù)排序、按匹配度排序。第六章經(jīng)典邏輯推理技術(shù)經(jīng)典邏輯推理是根據(jù)經(jīng)典邏輯(命題邏輯及一階謂詞邏輯)的邏輯規(guī)則進(jìn)行的一種推理，又稱為機(jī)械—自動(dòng)定理證明(mechanical-automatictheoremproving)。主要推理方法有：自然演繹推理、歸結(jié)演繹推理、與/或形演繹推理。由于以經(jīng)典邏輯理論為基礎(chǔ)，這種推理只有“真”和“假”兩種真值，因此是一種精確推理(確定性推理)。6.1歸納演繹推理謂詞演算中，利用等價(jià)式和永真蘊(yùn)含式，從一些已知公式推導(dǎo)出新公式，新公式也被稱為定理。推導(dǎo)過程中使用的推理規(guī)則序列就是該定理的證明。自動(dòng)定理證明是人工智能的一個(gè)重要研究領(lǐng)域，不僅因?yàn)樵S多數(shù)學(xué)問題使用定理證明，許多非數(shù)學(xué)問題(如醫(yī)療診斷、機(jī)器人行動(dòng)規(guī)劃等)也可以歸結(jié)為定理證明問題。定理證明的實(shí)質(zhì)是對(duì)前提P和結(jié)論Q證明PQ的永真性。由于謂詞公式永真性證明的困難性，一般用反證法思想把“永真性”問題轉(zhuǎn)化為“不可滿足性”證明，即證明P∧Q是不可滿足的。定理：設(shè)有謂詞公式F，其標(biāo)準(zhǔn)形的子句集為S，則F不可滿足的充要條件是S不可滿足。6.1歸納演繹推理子句魯賓遜歸結(jié)原理歸結(jié)反演應(yīng)用歸結(jié)原理求問題答案歸結(jié)策略子句的定義定義1：原子公式及原子公式的否定統(tǒng)稱為文字。定義2：任何文字的析取式稱為子句。P∨Q、P(x,f(x),y)∨Q(y)∨R(f(x))特例：不包含任何文字的子句稱為空子句?？兆泳洳话淖郑荒鼙蝗魏谓忉対M足，所以空子句是永假的，即不可滿足的。定義3：由子句構(gòu)成的集合稱為子句集。任何一個(gè)謂詞公式都可以化成一個(gè)子句集。謂詞公式化為子句集的步驟將謂詞公式化為子句集的步驟如下：(等價(jià)式和蘊(yùn)含式詳見合式公式性質(zhì))(1)利用連接詞化歸率消去、P→QP∨QPQ(P→Q)∧(Q→P)PQ(P∧Q)∨(Q∧P)例：(x){[P(x)∨Q(x)](y)[S(x,y)∧Q(x)]}∧(x)[P(x)∨B(x)]Step1：(x){[(P(x)∨Q(x))]∨(y)[S(x,y)∧Q(x)]}∧(x)[P(x)∨B(x)]Step1：(x){[(P(x)∨Q(x))]∨(y)[S(x,y)∧Q(x)]}∧(x)[P(x)∨B(x)]謂詞公式化為子句集的步驟(2)利用等價(jià)關(guān)系把移到緊靠謂詞的位置PP(P∧Q)P∨Q(P∨Q)P∧Q(x)P(x)P(x)P(x)P(3)重新命名變?cè)?，使不同量詞約束的變?cè)胁煌?x)P(x)(y)P(y)(x)P(x)(y)P(y)Step2：(x){[P(x)∧Q(x)]∨(y)[S(x,y)∧Q(x)]}∧(x)[P(x)∨B(x)]Step3：(x){[P(x)∧Q(x)]∨(y)[S(x,y)∧Q(x)]}∧(w)[P(w)∨B(w)](4)消去不在轄域內(nèi)，采用存在固化，用個(gè)體常量代替受該約束的變?cè)?，消除。在轄域?nèi)，用Skolem函數(shù)代替有相互依賴關(guān)系變量，消除。

(y)[(x)P(x,y)](y)P(g(y),y)其中，g(y)是Skolem函數(shù)，g(y)應(yīng)是原合式公式中沒有的符號(hào)。Step3：(x){[P(x)∧Q(x)]∨(y)[S(x,y)∧Q(x)]}∧(w)[P(w)∨B(w)]謂詞公式化為子句集的步驟Step4：(x){[P(x)∧Q(x)]∨[S(x,f(x))∧Q(x)]}∧(w)[P(w)∨B(w)](5)將公式化為前束形把所有移到公式左邊，使每個(gè)量詞的轄域包含這個(gè)量詞后面的整個(gè)部分，所得公式稱為前束形。

前束形公式由前綴和母式組成，前綴由串組成，母式由沒有量詞的公式組成。

謂詞公式化為子句集的步驟Step4：(x){[P(x)∧Q(x)]∨[S(x,f(x))∧Q(x)]}∧(w)[P(w)∨B(w)]Step5：(x)(w){[P(x)∧Q(x)]∨[S(x,f(x))∧Q(x)]}∧[P(w)∨B(w)](6)利用分配律將母式化為合取范式P∨(Q∧R)(P∨Q)∧(P∨R)P∧(Q∨R)(P∧Q)∨(P∧R)(7)略去由于公式中所有的變量都是量化的變量，因此可以把省略。母式中，省略的變量被默認(rèn)為量化變量。謂詞公式化為子句集的步驟Step5：(x)(w){[P(x)∧Q(x)]∨[S(x,f(x))∧Q(x)]}∧[P(w)∨B(w)]Step6：(x)(w){[P(x)∨[S(x,f(x))]∧Q(x)}∧[P(w)∨B(w)](8)消去，把母式用子句集表示P∧D可表示為子句集：P

D(9)子句變量標(biāo)準(zhǔn)化，即重新命名變量，使每個(gè)子句中的變量符號(hào)不同謂詞公式化為子句集的步驟Step6：(x)(w){[P(x)∨[S(x,f(x))]∧Q(x)}∧[P(w)∨B(w)]Step7：{[P(x)∨[S(x,f(x))]∧Q(x)}∧[P(w)∨B(w)]Step8：P(x)∨[S(x,f(x))Q(x)P(w)∨B(w)Step9：P(x)∨[S(x,f(x))Q(y)P(w)∨B(w)魯賓遜歸結(jié)原理由謂詞公式轉(zhuǎn)化為子句集的過程中可以看出：子句集中，子句間是合取關(guān)系，只要有一個(gè)子句不可滿足，則子句集就不可滿足。若子句集中包含空子句，則該子句集一定不可滿足。

歸結(jié)原理又稱為消解原理，它是定理證明的基礎(chǔ)。魯賓遜歸結(jié)原理基本思想：檢查子句集S是否包含空子句，若包含，則S不可滿足；若不包含，在S中選擇合適的子句進(jìn)行歸結(jié)，一旦推導(dǎo)出空子句，則S不可滿足。命題邏輯中的歸結(jié)原理定義1：若P是原子謂詞公式，則稱P與P為互補(bǔ)文字。定義2：基子句是指沒有變量的子句?；泳涞臍w結(jié)：設(shè)C1、C2是子句集中任意兩個(gè)基子句，若Cl中文字L1與C2中文字L2互補(bǔ)，那么從Cl和C2中分別消去L1和L2，將兩個(gè)子句的剩余部分析取，構(gòu)成新子句Cl2，該過程被稱為歸結(jié)。C12稱為C1、C2的歸結(jié)式。C1、C2是Cl2的父子句。命題邏輯中的歸結(jié)原理例：C1=P∨Q∨R

C2=P∨S∨TC12=Q∨R∨S∨T歸結(jié)過程的樹形表示P∨Q∨RQ∨R∨S∨TP∨S∨T命題邏輯中的歸結(jié)原理定理：歸結(jié)式C12是其父子句C1和C2的邏輯結(jié)論。推論1：設(shè)C1和C2是子句集S中的兩個(gè)子句，C12是它們的歸結(jié)式，若用C12代替C1和C2后得到新子句集S1，則由S1的不可滿足性可推出原子句集S的不可滿足性。推論2：設(shè)C1和C2是子句集S中的兩個(gè)子句，C12是它們的歸結(jié)式，若把C12加入S中，得到新子句集S2，則S和S2在不可滿足性的意義上是等價(jià)的。命題邏輯中的歸結(jié)原理注意：命題邏輯中，對(duì)不可滿足的子句集S，歸結(jié)原理是完備的。即若子句集S不可滿足，則必然存在一個(gè)從S到空子句的歸結(jié)演繹。對(duì)于可滿足的子句集S，用歸結(jié)原理得不到任何結(jié)果。謂詞邏輯中的歸結(jié)原理在謂詞邏輯中，需要先用最一般合一對(duì)子句進(jìn)行代換，使它們包括互補(bǔ)的文字，然后才能進(jìn)行歸結(jié)。定義：設(shè)Cl、C2是兩個(gè)沒有相同變?cè)淖泳?，分別表示成兩個(gè)文字集合{Li}和{Mi}，{li}是{Li}的一個(gè)子集，{mi}是{Mi}的一個(gè)子集，若是{li}和{mi}的最一般合一，則稱：C12={C1-{li}}∪{C2-{mi}}為C1和C2的二元?dú)w結(jié)式，{li}和{mi}是歸結(jié)式上的文字。謂詞邏輯中的歸結(jié)原理例：設(shè)C1=P(x)∨Q(a)，C2=P(b)∨R(x)C1和C2有相同的變?cè)獂，修改C2為：C2=P(b)∨R(y)L1=P(x)，L2=P(b)L1與L2的最一般合一：={b/x}C12={{P(b),Q(a)}-{P(b)}}∪{{P(b),R(y)}-{P(b)}}={Q(a),R(y)}=Q(a)∨R(y)謂詞邏輯中的歸結(jié)原理例：設(shè)C1=P(x)∨P(f(a))∨Q(x)，C2=P(y)∨R(b)C1中有可合一的文字，用它們的最一般合一：1={f(a)/x}，置換C1為：C11=P(f(a))∨Q(f(a))

C1的因子對(duì)C11和C2進(jìn)行歸結(jié)：L1=P(f(a))，L2=P(y)L1與L2的最一般合一：2={f(a)/y}C12=Q(f(a))∨R(b)謂詞邏輯中的歸結(jié)原理定義：子句C1和C2的歸結(jié)式是下列二元?dú)w結(jié)式之一：(1)C1和C2的二元?dú)w結(jié)式；(2)C1和C2的因子的二元?dú)w結(jié)式；(3)C1的因子和C2的二元?dú)w結(jié)式；(4)C1的因子和C2的因子的二元?dú)w結(jié)式；與命題邏輯相同，謂詞邏輯中歸結(jié)式也是它的父子句的邏輯結(jié)論。用歸結(jié)式取代子句集中的父子句，得到的新子句集仍保持原子句集的不可滿足性。歸結(jié)反演應(yīng)用歸結(jié)原理證明定理的過程稱為歸結(jié)反演。歸結(jié)反演的步驟：(1)將定理證明的前提謂詞公式轉(zhuǎn)化為子句集F。(2)將要求證明的目標(biāo)表示成的謂詞公式G(目標(biāo)公式)。(3)將G的否定G轉(zhuǎn)化成子句，加入到F中，得到子句集S。(4)應(yīng)用歸結(jié)原理對(duì)S中的子句進(jìn)行歸結(jié)，把每次歸結(jié)得到的歸結(jié)式都并入S中。如此反復(fù)進(jìn)行，當(dāng)歸結(jié)得到空子句NIL，則停止歸結(jié)，此時(shí)就證明了G為真。例：歸結(jié)反演例：已知前提F：(x){[P(x,y)∧Q(y)](y)[R(y)∧S(x,y)]}試證明結(jié)論G：(x)R(x)(x)(y)[P(x,y)Q(y)]前提F的子句集：P(x,y)∨Q(y)]∨R(f(x))P(x,y)∨Q(y)]∨S(x,f(x))]結(jié)論G的否定子句集：R(z)P(A,B)Q(B)例：歸結(jié)反演例：已知：能閱讀的都是有文化的；海豚是沒有文化的；某些海豚是有智能的。試用歸結(jié)反演證明：某些有智能的并不能閱讀。謂詞定義：R(x)：x能閱讀L(x)：x有文化D(x)：x是海豚I(x)：x有智能將前提形式化地表示為：(x)(R(x)L(x))(y)(D(y)L(y))(z)(D(x)∧I(x))將結(jié)論形式化地表示為：(w)(I(w)∧R(w))前提的子句集：R(x)∨L(x))D(y)∨L(y))D(A)I(A)結(jié)論的子句集：I(w)∨R(w)應(yīng)用歸結(jié)原理求問題答案除定理證明外，歸結(jié)原理可用來求問題答案，其思想與定理證明類似。歸結(jié)原理求問題答案的一般步驟：(1)把已知前提用謂詞公式表示出來，并化為子句集S。(2)把待求解問題用謂詞公式G表示出來，構(gòu)造G和謂詞ANSWER的析取式。ANSWER是為求解問題而設(shè)的謂詞，變?cè)仨毰c問題公式的完全一致。(3)把析取式化為子句集，加入到S中，得到子句集S'。(4)對(duì)S'進(jìn)行歸結(jié)，形成歸結(jié)反演樹——修改的證明樹。(5)若得到歸結(jié)式ANSWER，答案就在ANSWER中。例：應(yīng)用歸結(jié)原理求問題答案例：已知：王先生是小李的老師；小李與小張是同班同學(xué)；如果x和y是同班同學(xué)，則x的老師就是y的老師。求：小張的老師是誰？謂詞定義：T(x,y)：x是y的老師C(x,y)：x和y同班同學(xué)前提的謂詞公式表示：T(Wang,Li)C(Li,Zhang)(x)(y)(z)C(x,y)∧T(z,x)T(z,y)待求解問題的謂詞公式表示：(x)T(x,Zhang)∨ANSWER(x)6.2.4應(yīng)用歸結(jié)原理求問題答案前提的謂詞公式表示：T(Wang,Li)C(Li,Zhang)(x)(y)(z)C(x,y)∧T(z,x)T(z,y)待求解問題的謂詞公式表示：(x)T(x,Zhang)∨ANSWER(x)前提的子句集：T(Wang,Li)(1)C(Li,Zhang)(2)C(x,y)∨T(z,x)∨T(z,y)(3)待求解問題子句集：T(u,Zhang)∨ANSWER(u)(4)將子句(1)、(3)歸結(jié)：C(Li,y)∨T(Wang,x)(5)將子句(4)、(5)歸結(jié)：C(Li,Zhang)∨ANSWER(Wang)(6)將子句(2)、(6)歸結(jié)：ANSWER(Wang)(7)應(yīng)用歸結(jié)原理求問題答案歸結(jié)的一般過程歸結(jié)的一般過程：對(duì)子句集中所有子句逐對(duì)進(jìn)行比較，對(duì)任何一對(duì)可歸結(jié)的子句對(duì)都進(jìn)行歸結(jié)。設(shè)有子句集：S={C1,C2,C3,C4}，其中，C1,C2,C3,C4是S中的子句。(1)從C1開始，逐個(gè)與C2,C3,C4比較，若找到可以與C1歸結(jié)的子句，就求出歸結(jié)式。然后用C2與C3,C4進(jìn)行比較，凡可歸結(jié)的都進(jìn)行歸結(jié)，最后用C3與C4比較，若能歸結(jié)也對(duì)它們進(jìn)行歸結(jié)。經(jīng)過以上比較及歸結(jié)，得到一組歸結(jié)式，稱為第一級(jí)歸結(jié)式。(2)從C1開始，用S中的子句分別與第一級(jí)歸結(jié)式中的子句逐個(gè)比較、歸結(jié)，得到一組歸結(jié)式，稱為第二級(jí)歸結(jié)式。(3)從C1開始，用S中的子句和第一級(jí)歸結(jié)式中的子句逐個(gè)與第二級(jí)歸結(jié)式中的子句比較，得到第三級(jí)歸結(jié)式。(4)如此繼續(xù)，直到出現(xiàn)了空子句或不能再繼續(xù)歸結(jié)為止。只要子句集是不可滿足的，上述歸結(jié)過程一定會(huì)歸結(jié)出空子句而終止。歸結(jié)的一般過程例：設(shè)有子句集：S={P,R,P∨Q,Q∨R}一般歸結(jié)過程為：S:(1)P(2)R(3)P∨Q(4)Q∨RS1:(5)Q(1)與(3)歸結(jié)(6)Q

(2)與(4)歸結(jié)(7)P∨R

(3)與(4)歸結(jié)S2:(8)R(1)與(7)歸結(jié)(9)P(2)與(7)歸結(jié)(10)P(3)與(6)歸結(jié)(11)R(4)與(5)歸結(jié)S3:(12)NIL(1)與(9)歸結(jié)問題：按一般歸結(jié)過程進(jìn)行歸結(jié)時(shí)，不僅歸結(jié)出許多無用子句，而且有些歸結(jié)式還是重復(fù)的，既浪費(fèi)時(shí)間又多占空間。對(duì)子句集進(jìn)行歸結(jié)時(shí)，如何從中找出可進(jìn)行歸結(jié)的一對(duì)子句。歸結(jié)策略歸結(jié)策略大致分為兩大類：刪除策略基本思想：歸結(jié)時(shí)刪除子句集中無用子句，縮小尋找范圍，減少比較次數(shù)，提高歸結(jié)效率。純文字刪除法、重言式刪除法、包孕刪除法。限制策略基本思想：對(duì)參加歸結(jié)的子句進(jìn)行限制，盡可能減小歸結(jié)盲目性，使其盡快歸結(jié)出空子句。支持集策略、線性輸入策略、單文字子句策略、祖先過濾形策略歸結(jié)策略以上列出的是幾種最基本的歸結(jié)策略。注意：具體應(yīng)用時(shí)可組合在一起使用。下面討論的歸結(jié)過程都是按廣度優(yōu)先策略進(jìn)行搜索的，也可用其它策略進(jìn)行搜索，可根據(jù)實(shí)際情況決定。歸結(jié)策略——?jiǎng)h除策略1.純文字刪除法定義：如果某文字L在子句集中不存在可與之互補(bǔ)的文字L，則該文字被稱為純文字。顯然，歸結(jié)時(shí)純文字不可能被消去，因而用包含它的子句進(jìn)行歸結(jié)時(shí)，也不可能得到空子句，因此在不影響子句集不可滿足性條件下，可以把包含純文字的子句從子句集中刪去。歸結(jié)策略——?jiǎng)h除策略2.重言式刪除法定義：如果一個(gè)子句中同時(shí)包含互補(bǔ)文字對(duì)，則該子句被稱為重言式。

重言式是真值為真的子句。對(duì)一個(gè)子句集來說，增加或刪去一個(gè)真值為真的子句，不會(huì)影響它的不可滿足性，因此可從子句集中刪去重言式。歸結(jié)策略——?jiǎng)h除策略3.包孕刪除法定義：設(shè)有子句C1和C2，如果存在一個(gè)置換，使得C1C2，則稱C1包孕于C2。刪去子句集中被包孕的子句，不會(huì)影響子句集的不可滿足性，因而可從子句集中刪去。歸結(jié)策略——限制策略1.支持集策略支持集策略是沃斯等人在1965年提出的一種歸結(jié)策略。它對(duì)參加歸結(jié)的子句提出以下限制：每次歸結(jié)時(shí)，父子句中至少應(yīng)有一個(gè)是由目標(biāo)公式的否定所得到的子句，或者是它們的后商。可以證明：支持集策略是完備的，即若子句集是不可滿足的，則由支持集策略一定可以歸結(jié)出空子句。歸結(jié)策略——限制策略例：設(shè)有子句集：S={I(x)∨R(x),I(a),R(y)∨L(y),L(a)}其中，I(x)∨R(x)是目標(biāo)公式否定后得到的子句。用支持集策略進(jìn)行歸結(jié)的過程：S:(1)I(x)∨R(x)(2)I(a)(3)R(y)∨L(y)(4)L(a)S1:(5)R(a)

(1)與(2)歸結(jié)(6)I(x)∨L(x)

(1)與(3)歸結(jié)S2:(7)L(a)(2)與(6)歸結(jié)(8)L(a)

(3)與(5)歸結(jié)(9)I(a)

(4)與(6)歸結(jié)S3:(10)NIL(2)與(9)歸結(jié)歸結(jié)策略——限制策略2.線性輸入策略對(duì)參加歸結(jié)的子句的限制：參加歸結(jié)的兩個(gè)子句中必須至少有一個(gè)是初始子句集中的子句。定義：初始子句集是指初始時(shí)要求進(jìn)行歸結(jié)的子句集。例如：歸結(jié)反演中，初始子句集就是由已知前提及結(jié)論的否定化構(gòu)成的子句集。線性輸入策略可限制生成歸結(jié)式的數(shù)目，具有簡(jiǎn)單、高效的優(yōu)點(diǎn)。但它是不完備的。也就是說，即使子句集是不可滿足的，用線性輸入策略進(jìn)行歸結(jié)時(shí)不一定能歸結(jié)出空子句。歸結(jié)策略——限制策略例：設(shè)有子句集：S={I(x)∨R(x),I(a),R(y)∨L(y),L(a)}其中，I(x)∨R(x)是目標(biāo)公式否定后得到的子句。用線性輸入策略進(jìn)行歸結(jié)的過程：S:(1)I(x)∨R(x)(2)I(a)(3)R(y)∨L(y)(4)L(a)S1:(5)R(a)

(1)與(2)歸結(jié)(6)I(x)∨L(x)

(1)與(3)歸結(jié)(7)R(a)

(3)與(4)歸結(jié)S2:(8)I(a)(1)與(7)歸結(jié)(9)L(a)(2)與(6)歸結(jié)(10)L(a)

(3)與(5)歸結(jié)(11)I(a)

(4)與(6)歸結(jié)S3:(12)NIL(2)與(8)歸結(jié)歸結(jié)策略——限制策略3.單文字子句策略定義：若一個(gè)子句只包含一個(gè)文字，稱它為單文字子句。單文字子句策略要求參加歸結(jié)的兩個(gè)子句中必須至少有一個(gè)是單文字子句。用單文字子句策略歸結(jié)時(shí)，歸結(jié)式比父子句含有較少的文字，有利于朝著空子句的方向前進(jìn)，因此它有較高的歸結(jié)效率。當(dāng)初始子句集中不包含單文字子句時(shí)，歸結(jié)就無法進(jìn)行。因此，這種歸結(jié)策略是不完備的。歸結(jié)策略——限制策略例：設(shè)有子句集：S={I(x)∨R(x),I(a),R(y)∨L(y),L(a)}其中，I(x)∨R(x)是目標(biāo)公式否定后得到的子句。用單文字子句策略進(jìn)行歸結(jié)的過程：S:(1)I(x)∨R(x)(2)I(a)(3)R(y)∨L(y)(4)L(a)S1:(5)R(a)

(1)與(2)歸結(jié)(7)R(a)

(3)與(4)歸結(jié)S2:(8)I(a)(1)與(6)歸結(jié)(9)L(a)(3)與(5)歸結(jié)S3:(12)NIL(2)與(7)歸結(jié)歸結(jié)策略——限制策略4.祖先過濾形策略當(dāng)對(duì)兩個(gè)子句C1和C2進(jìn)行歸結(jié)時(shí)，只要它們滿足下述兩個(gè)條件中的任意一個(gè)就可進(jìn)行歸結(jié)：(1)C1與C2中至少有一個(gè)是初始子句集中的子句。(2)如果兩個(gè)子句都不是初始子句集中的子句，則一個(gè)應(yīng)是另一個(gè)的祖先。一個(gè)子句(例如C1)是另一個(gè)子句(例如C2)的祖先是指：C2是由Cl與別的子句歸結(jié)后得到的歸結(jié)式。該策略與線性輸入策略比較相似，但放寬了限制，而且它是完備的。歸結(jié)演繹推理缺點(diǎn)歸結(jié)反演中，必須先將謂詞公式轉(zhuǎn)化為子句，使得歸結(jié)演繹推理存在以下缺點(diǎn)：不便于閱讀與理解；可能丟失一些重要的控制信息；許多人工智能系統(tǒng)中，知識(shí)一般由蘊(yùn)含式直接表示。歸結(jié)反演中將它們轉(zhuǎn)化為子句，推理效率較低。針對(duì)歸結(jié)演繹推理存在的上述問題，人們提出了多種非子句定理證明方法：自然演繹推理、尼爾遜提出的基于與／或形的演繹推理等。6.2自然演繹推理從一組已知為真的事實(shí)出發(fā)，直接運(yùn)用經(jīng)典邏輯的推理規(guī)則推出結(jié)論的過程稱為自然演繹推理?；镜耐评硪?guī)則：P規(guī)則、T規(guī)則、假言推理、拒取式推理P規(guī)則：在推理的任何步驟上都可引入前提。T規(guī)則：推理時(shí)，如果前面步驟中有一個(gè)或多個(gè)公式永真蘊(yùn)含公式S，則可把S引入推理過程中。CP規(guī)則：如果能從R和前提集合P推出S來，則可從前提集合推出：RS。(詳見合式公式性質(zhì))伽利略在論證哥白尼的日心說時(shí)，使用了如下推理：(1)如果行星系統(tǒng)是以太陽為中心的，則金星會(huì)顯示出位相變化；(2)金星顯示出位相變化；(3)所以，行星系統(tǒng)是以太陽為中心的。6.2自然演繹推理假言推理的一般形式：P,PQQ拒取式推理的一般形式：PQ,QP注意應(yīng)避免以下兩類錯(cuò)誤：肯定后件Q的錯(cuò)誤否定前件P的錯(cuò)誤6.2自然演繹推理例：設(shè)已知下列事實(shí)：A,B,AC,B∧CD,DQ求證：Q為真。證明：A,ACCB,CB∧CB∧C,B∧CDDD,DQQQ為真P規(guī)則和假言推理引入合取詞T規(guī)則和假言推理T規(guī)則和假言推理6.2自然演繹推理例：設(shè)已知下列事實(shí)：(1)凡是容易的課程小王都喜歡。(2)C班的課程都是容易的(3)ds是C班的一門課程。求證：小王喜歡ds這門課程。證明：定義謂詞：EASY(x)x是容易的

LIKE(x,y)x喜歡y

C(x)x是C班的一門課程EASY(x)LIKE(Wang,x)(x)(C(x)EASY(x))C(ds)LIKE(Wang,ds)6.2自然演繹推理(x)(C(x)EASY(x))C(y)EASY(y)C(ds),C(y)EASY(y)EASY(ds)EASY(ds),EASY(x)LIKE(Wang,x)LIKE(Wang,ds)全稱固化P規(guī)則和假言推理T規(guī)則和假言推理6.2自然演繹推理優(yōu)點(diǎn)：表達(dá)定理證明過程自然，容易理解，而且它擁有豐富的推理規(guī)則，推理過程靈活，便于在它的推理規(guī)則中嵌入領(lǐng)域啟發(fā)式知識(shí)。缺點(diǎn)：容易產(chǎn)生組合爆炸，推理過程中得到的中間結(jié)論一般呈指數(shù)形式遞增。6.3與/或形演繹推理與/或形演繹推理是一種直接的推理方法，基本思想：把有關(guān)問題的知識(shí)和信息分為規(guī)則與事實(shí)兩類。規(guī)則由包含蘊(yùn)含式的表達(dá)式表示。事實(shí)由無蘊(yùn)含式的表達(dá)式表示。畫出與/或樹，然后通過蘊(yùn)含式進(jìn)行演繹推理。

推理形式：正向演繹、逆向演繹和雙向演繹。6.3.1與/或形正向演繹推理正向演繹推理對(duì)應(yīng)于正向推理，從已知事實(shí)出發(fā)，反復(fù)嘗試所有可利用的規(guī)則(F規(guī)則)進(jìn)行演繹推理，直至得到某個(gè)目標(biāo)公式的一個(gè)終止條件為止。這種推理對(duì)已知事實(shí)、F規(guī)則及目標(biāo)公式的表示形式都有一定的要求，如果不是所要求的形式，就需要進(jìn)行變換。6.3.1與/或形正向演繹推理事實(shí)表達(dá)式的與/或形變換及其與/或樹表示F規(guī)則的表示形式目標(biāo)公式的表示形式推理過程含有變量的表達(dá)式6.3.1與/或形正向演繹推理一、事實(shí)表達(dá)式及其與或形表示正向演繹推理要求事實(shí)用不包含的與/或形表示。把一個(gè)表達(dá)式轉(zhuǎn)化為標(biāo)準(zhǔn)的與/或形的步驟如下：(1)利用等價(jià)式：PQPQ，消去；(2)把移到每個(gè)謂詞符號(hào)的前面；(3)重新命名變?cè)?，使不同量詞約束的變?cè)胁煌拿郑?4)引人Skolem函數(shù)消去存在量詞；(5)將公式化為前束形；(6)略去全稱量詞；(7)重新命名變量，使主要合取式中的變?cè)煌?。過程與化子句集類似，但不必把公式化為子句的合取形式，也不能消去公式中的合取符。標(biāo)準(zhǔn)的與/或形：Q(z,a){[R(y)P(y)]S(a,y)}6.3.1與/或形正向演繹推理根節(jié)點(diǎn)：整個(gè)表達(dá)式葉節(jié)點(diǎn)：謂詞公式中的單個(gè)文字節(jié)點(diǎn)：表示事實(shí)表達(dá)式及其子表達(dá)式(x)(y){Q(y,x)[(R(y)P(y))S(x,y)]}Q(z,a){[R(y)P(y)]S(a,y)}Q(z,a)[R(y)P(y)]S(a,y)[R(y)P(y)]S(a,y)[R(y)P(y)]6.3.1與/或形正向演繹推理用與/或樹表示事實(shí)表達(dá)式的重要性質(zhì)：從與/或樹中可以讀出由變換表達(dá)式得到的一組子句。每個(gè)子句是由葉節(jié)點(diǎn)組成的公式。每個(gè)子句相當(dāng)于與/或樹的一個(gè)解圖。3個(gè)子句：Q(z,a)S(a,y)R(y)S(a,y)P(y)Q(z,a){[R(y)P(y)]S(a,y)}Q(z,a)[R(y)P(y)]S(a,y)[R(y)P(y)]S(a,y)[R(y)P(y)]6.3.1與/或形正向演繹推理二、F規(guī)則的表示形式通常，F(xiàn)規(guī)則具有以下形式： LW

要求：L是單文字，W是任意的與或形表達(dá)式；L、W中所有變?cè)际橇炕?，默認(rèn)作用于整個(gè)蘊(yùn)含式。各條規(guī)則的變?cè)鞑幌嗤?，而且?guī)則中的變?cè)c事實(shí)表達(dá)式中的變量也不相同。6.3.1與/或形正向演繹推理問題：為什么F規(guī)則的左部L限制為單文字？

演繹推理時(shí)，要用F規(guī)則作用于表示事實(shí)的與/或樹。與/或樹的葉節(jié)點(diǎn)都是單文字。L為單文字時(shí)，可用F規(guī)則的左部與葉節(jié)點(diǎn)進(jìn)行匹配，簡(jiǎn)化規(guī)則的應(yīng)用過程。6.3.1與/或形正向演繹推理若規(guī)則(即知識(shí))的表示形式不滿足要求，可用如下步驟將其變換成標(biāo)準(zhǔn)形式：(1)暫時(shí)消去；(2)把移到每個(gè)謂詞的前面；(3)引入Skolem函數(shù)消去存在量詞；(4)將公式化為前束形，并略去全稱量詞；(5)利用等價(jià)關(guān)系：P∨QPQ恢復(fù)為蘊(yùn)含式。6.3.1與/或形正向演繹推理三、目標(biāo)公式的表示形式用子句表示，是文字的析取式，否則要化成子句形式。轉(zhuǎn)化方法同“6.2.1”。6.3.1與/或形正向演繹推理四、推理過程將F規(guī)則作用于表示事實(shí)的與/或樹，改變與/或樹結(jié)構(gòu)，產(chǎn)生新的事實(shí)，直至推出目標(biāo)公式，則推理就成功結(jié)束。推理過程為：(1)首先用與/或樹把已知事實(shí)表示出來；(2)用F規(guī)則的左部和與/或樹的葉節(jié)點(diǎn)進(jìn)行匹配，將匹配成功的F規(guī)則加入到與/或樹中。(3)重復(fù)第(2)步，直到產(chǎn)生一個(gè)含有以目標(biāo)節(jié)點(diǎn)作為終止節(jié)點(diǎn)的解圖為止。6.3.1與/或形正向演繹推理例：設(shè)已知事實(shí)為：AB，F(xiàn)規(guī)則為：ACD，BEG試證明公式：CGABCDEGF規(guī)則ABAB已知事實(shí)匹配匹配CG證明公式：CG6.3.1與/或形正向演繹推理例：設(shè)已知事實(shí)為：AB，F(xiàn)規(guī)則為：ACD，BEG試證明公式：CG由已知事實(shí)、F規(guī)則和目標(biāo)的否定構(gòu)成的子句集為：

AB

ACADBEBGCG歸結(jié)反演圖ACCGBGABABBNIL6.3.1與/或形正向演繹推理五、含有變量的表達(dá)式如果事實(shí)表達(dá)式、規(guī)則和目標(biāo)表達(dá)式中有變量，則在推理中需要用最一般合一進(jìn)行變?cè)闹脫Q。R16.3.1與/或形正向演繹推理注意：當(dāng)事實(shí)表達(dá)式、F規(guī)則和目標(biāo)表達(dá)式中包含變量，只有解圖中所用置換是一致的，解圖對(duì)應(yīng)的子句才成立。P(A)[Q(A)R(A)]P(A)Q(A)R(A)Q(A)R(A)Q(y)N(A)N(z)P(x)S(A)S(z){A/z}{A/z}{A/y}{A/x}R26.3.1與/或形正向演繹推理定義：設(shè)有一個(gè)置換集U：{u1，u2，…，un}，每個(gè)ui是一個(gè)置換對(duì)的集合，ui={ti1/vi1,ti2/vi2，…，tim(i)/vim(i)}，其中：t為項(xiàng)，v為變量。令：U1=(v11，…，v1m(1)，v21，…，v2m(2)，…，vnm(n))

U2=(t11，…，t1m(2)，t21，…，t2m(2)，…，tnm(n))則置換U一致的充要條件是Ul和U2可合一。U的合一復(fù)合u=mgu(Ul，U2)6.3.1與/或形正向演繹推理例1：u1={A/x,A/z}，u2={A/y,A/z}

U={u1，u2}是一致的，其合一復(fù)合為{A/x，A/y，A/z}例2：u1={x/y}，u2={y/z}

U={u1，u2}是一致的，其合一復(fù)合為{x/y，y/z}例3：u1={A/y}，u2={B/y}

U={u1，u2}是不一致的。例4：u1={f(z)/x}，u2={f(A)/x}

U={u1，u2}是一致的，其合一復(fù)合為={f(A)/x，A/z}6.3.2與/或形逆向演繹推理從目標(biāo)表達(dá)式出發(fā)，通過逆向使用蘊(yùn)含式(B規(guī)則)進(jìn)行演繹推理，直到得到包含已知事實(shí)的終止條件為止。目標(biāo)表達(dá)式的與/或形變換及其與/或樹表示B規(guī)則的表示形式已知事實(shí)的表示形式推理過程6.3.2與/或形逆向演繹推理一、目標(biāo)表達(dá)式及其與/或樹表示將目標(biāo)表達(dá)式轉(zhuǎn)化成無的與或形式，并用與/或樹表示，轉(zhuǎn)化過程與正向演繹中對(duì)事實(shí)表達(dá)式的變換相似。6.3.2與/或形逆向演繹推理不同處：用約束的變?cè)腟kolem函數(shù)替換，由約束的相應(yīng)變?cè)缓舐匀?，再消去?/p>

例：目標(biāo)表達(dá)式：(y)(x){P(x)[Q(x,y)∧(R(x)∧S(y))]}與/或形：P(f(z))∨{Q(f(y),y)∧[(R(f(y))∨S(y)]}與/或圖中的n連接符把具有合取關(guān)系的子表達(dá)式連接起來，而在正向演繹中是把具有析取關(guān)系的子表達(dá)式連接起來。主要的析取式具有不同的變量名6.3.2與/或形逆向演繹推理目標(biāo)表達(dá)式：(y)(x){P(x)[Q(x,y)(R(x)S(y))]}與/或形：P(f(z)){Q(f(y),y)[(R(f(y))S(y)]}P(f(z)){Q(f(y),y)[(R(f(y))S(y)]}(R(f(y))P(f(z))Q(f(y),y)[(R(f(y))S(y)]Q(f(y),y)(R(f(y))S(y)S(y)6.3.2與/或形逆向演繹推理二、B規(guī)則的表示形式B規(guī)則的表示形式為：WL其中：W為任一與/或形式表達(dá)式，L為單一文字。6.3.2與/或形逆向演繹推理B規(guī)則：WLL限制為單一文字。推理時(shí)要用L與目標(biāo)樹中的葉節(jié)點(diǎn)匹配，而葉節(jié)點(diǎn)是文字，這樣可簡(jiǎn)化B規(guī)則對(duì)與/或樹的應(yīng)用。如果規(guī)則不符合這一要求，則要變換成這種形式。例：規(guī)則WL1L2轉(zhuǎn)化為兩個(gè)B規(guī)則：WL1，WL2規(guī)則中應(yīng)Skolem化量化的變量，并略去，即規(guī)則中尚存的變量都是量化的變量。6.3.2與/或形逆向演繹推理三、已知事實(shí)的表示形式

文字的合取式，可表示為文字的集合。對(duì)任一事實(shí)表達(dá)式，應(yīng)當(dāng)用Skolem函數(shù)代替事實(shí)表達(dá)式中量化的變量，并略去量化的變量，將表達(dá)式轉(zhuǎn)化成標(biāo)準(zhǔn)的文字合取式。6.3.2與/或形逆向演繹推理四、推理過程(1)用與/或樹將目標(biāo)表達(dá)式表示出來。(2)用B規(guī)則的右部和與/或樹的葉節(jié)點(diǎn)進(jìn)行匹配，并將匹配成功的B規(guī)則加入到與/或樹中。一條規(guī)則可用多次，每次應(yīng)使用不同的變量。當(dāng)一個(gè)事實(shí)文字和與/或樹中的一個(gè)文字可以合一時(shí)，可將該事實(shí)文字通過匹配弧連接到與/或樹中相應(yīng)的文字上，匹配弧應(yīng)標(biāo)明兩個(gè)文字的最一般合一。(3)重復(fù)進(jìn)行第(2)步，直到產(chǎn)生某個(gè)終止在事實(shí)節(jié)點(diǎn)上的一致解圖。一致解圖：推理時(shí)所用的置換是一致的。問題：是否存在一只貓和一只狗，試這只貓不怕這只狗？CAT