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

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

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

(y)[(x)P(x,y)](y)P(g(y),y)其中，g(y)是Skolem函數(shù)，g(y)應是原合式公式中沒有的符號。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)將公式化為前束形把所有移到公式左邊，使每個量詞的轄域包含這個量詞后面的整個部分，所得公式稱為前束形。

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

謂詞公式化為子句集的步驟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)略去由于公式中所有的變量都是量化的變量，因此可以把省略。母式中，省略的變量被默認為量化變量。謂詞公式化為子句集的步驟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)子句變量標準化，即重新命名變量，使每個子句中的變量符號不同謂詞公式化為子句集的步驟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)魯賓遜歸結原理由謂詞公式轉化為子句集的過程中可以看出：子句集中，子句間是合取關系，只要有一個子句不可滿足，則子句集就不可滿足。若子句集中包含空子句，則該子句集一定不可滿足。

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

C2=P∨S∨TC12=Q∨R∨S∨T歸結過程的樹形表示P∨Q∨RQ∨R∨S∨TP∨S∨T命題邏輯中的歸結原理定理：歸結式C12是其父子句C1和C2的邏輯結論。推論1：設C1和C2是子句集S中的兩個子句，C12是它們的歸結式，若用C12代替C1和C2后得到新子句集S1，則由S1的不可滿足性可推出原子句集S的不可滿足性。推論2：設C1和C2是子句集S中的兩個子句，C12是它們的歸結式，若把C12加入S中，得到新子句集S2，則S和S2在不可滿足性的意義上是等價的。命題邏輯中的歸結原理注意：命題邏輯中，對不可滿足的子句集S，歸結原理是完備的。即若子句集S不可滿足，則必然存在一個從S到空子句的歸結演繹。對于可滿足的子句集S，用歸結原理得不到任何結果。謂詞邏輯中的歸結原理在謂詞邏輯中，需要先用最一般合一對子句進行代換，使它們包括互補的文字，然后才能進行歸結。定義：設Cl、C2是兩個沒有相同變元的子句，分別表示成兩個文字集合{Li}和{Mi}，{li}是{Li}的一個子集，{mi}是{Mi}的一個子集，若是{li}和{mi}的最一般合一，則稱：C12={C1-{li}}∪{C2-{mi}}為C1和C2的二元歸結式，{li}和{mi}是歸結式上的文字。謂詞邏輯中的歸結原理例：設C1=P(x)∨Q(a)，C2=P(b)∨R(x)C1和C2有相同的變元x，修改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)謂詞邏輯中的歸結原理例：設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的因子對C11和C2進行歸結：L1=P(f(a))，L2=P(y)L1與L2的最一般合一：2={f(a)/y}C12=Q(f(a))∨R(b)謂詞邏輯中的歸結原理定義：子句C1和C2的歸結式是下列二元歸結式之一：(1)C1和C2的二元歸結式；(2)C1和C2的因子的二元歸結式；(3)C1的因子和C2的二元歸結式；(4)C1的因子和C2的因子的二元歸結式；與命題邏輯相同，謂詞邏輯中歸結式也是它的父子句的邏輯結論。用歸結式取代子句集中的父子句，得到的新子句集仍保持原子句集的不可滿足性。歸結反演應用歸結原理證明定理的過程稱為歸結反演。歸結反演的步驟：(1)將定理證明的前提謂詞公式轉化為子句集F。(2)將要求證明的目標表示成的謂詞公式G(目標公式)。(3)將G的否定G轉化成子句，加入到F中，得到子句集S。(4)應用歸結原理對S中的子句進行歸結，把每次歸結得到的歸結式都并入S中。如此反復進行，當歸結得到空子句NIL，則停止歸結，此時就證明了G為真。例：歸結反演例：已知前提F：(x){[P(x,y)∧Q(y)](y)[R(y)∧S(x,y)]}試證明結論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))]結論G的否定子句集：R(z)P(A,B)Q(B)例：歸結反演例：已知：能閱讀的都是有文化的；海豚是沒有文化的；某些海豚是有智能的。試用歸結反演證明：某些有智能的并不能閱讀。謂詞定義：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))將結論形式化地表示為：(w)(I(w)∧R(w))前提的子句集：R(x)∨L(x))D(y)∨L(y))D(A)I(A)結論的子句集：I(w)∨R(w)應用歸結原理求問題答案除定理證明外，歸結原理可用來求問題答案，其思想與定理證明類似。歸結原理求問題答案的一般步驟：(1)把已知前提用謂詞公式表示出來，并化為子句集S。(2)把待求解問題用謂詞公式G表示出來，構造G和謂詞ANSWER的析取式。ANSWER是為求解問題而設的謂詞，變元必須與問題公式的完全一致。(3)把析取式化為子句集，加入到S中，得到子句集S'。(4)對S'進行歸結，形成歸結反演樹——修改的證明樹。(5)若得到歸結式ANSWER，答案就在ANSWER中。例：應用歸結原理求問題答案例：已知：王先生是小李的老師；小李與小張是同班同學；如果x和y是同班同學，則x的老師就是y的老師。求：小張的老師是誰？謂詞定義：T(x,y)：x是y的老師C(x,y)：x和y同班同學前提的謂詞公式表示：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應用歸結原理求問題答案前提的謂詞公式表示：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)歸結：C(Li,y)∨T(Wang,x)(5)將子句(4)、(5)歸結：C(Li,Zhang)∨ANSWER(Wang)(6)將子句(2)、(6)歸結：ANSWER(Wang)(7)應用歸結原理求問題答案歸結的一般過程歸結的一般過程：對子句集中所有子句逐對進行比較，對任何一對可歸結的子句對都進行歸結。設有子句集：S={C1,C2,C3,C4}，其中，C1,C2,C3,C4是S中的子句。(1)從C1開始，逐個與C2,C3,C4比較，若找到可以與C1歸結的子句，就求出歸結式。然后用C2與C3,C4進行比較，凡可歸結的都進行歸結，最后用C3與C4比較，若能歸結也對它們進行歸結。經(jīng)過以上比較及歸結，得到一組歸結式，稱為第一級歸結式。(2)從C1開始，用S中的子句分別與第一級歸結式中的子句逐個比較、歸結，得到一組歸結式，稱為第二級歸結式。(3)從C1開始，用S中的子句和第一級歸結式中的子句逐個與第二級歸結式中的子句比較，得到第三級歸結式。(4)如此繼續(xù)，直到出現(xiàn)了空子句或不能再繼續(xù)歸結為止。只要子句集是不可滿足的，上述歸結過程一定會歸結出空子句而終止。歸結的一般過程例：設有子句集：S={P,R,P∨Q,Q∨R}一般歸結過程為：S:(1)P(2)R(3)P∨Q(4)Q∨RS1:(5)Q(1)與(3)歸結(6)Q

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

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

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

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

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

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

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

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

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

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

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

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

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

(3)與(4)歸結S2:(8)I(a)(1)與(6)歸結(9)L(a)(3)與(5)歸結S3:(12)NIL(2)與(7)歸結歸結策略——限制策略4.祖先過濾形策略當對兩個子句C1和C2進行歸結時，只要它們滿足下述兩個條件中的任意一個就可進行歸結：(1)C1與C2中至少有一個是初始子句集中的子句。(2)如果兩個子句都不是初始子句集中的子句，則一個應是另一個的祖先。一個子句(例如C1)是另一個子句(例如C2)的祖先是指：C2是由Cl與別的子句歸結后得到的歸結式。該策略與線性輸入策略比較相似，但放寬了限制，而且它是完備的。歸結演繹推理缺點歸結反演中，必須先將謂詞公式轉化為子句，使得歸結演繹推理存在以下缺點：不便于閱讀與理解；可能丟失一些重要的控制信息；許多人工智能系統(tǒng)中，知識一般由蘊含式直接表示。歸結反演中將它們轉化為子句，推理效率較低。針對歸結演繹推理存在的上述問題，人們提出了多種非子句定理證明方法：自然演繹推理、尼爾遜提出的基于與／或形的演繹推理等。6.2自然演繹推理從一組已知為真的事實出發(fā)，直接運用經(jīng)典邏輯的推理規(guī)則推出結論的過程稱為自然演繹推理。基本的推理規(guī)則：P規(guī)則、T規(guī)則、假言推理、拒取式推理P規(guī)則：在推理的任何步驟上都可引入前提。T規(guī)則：推理時，如果前面步驟中有一個或多個公式永真蘊含公式S，則可把S引入推理過程中。CP規(guī)則：如果能從R和前提集合P推出S來，則可從前提集合推出：RS。(詳見合式公式性質(zhì))伽利略在論證哥白尼的日心說時，使用了如下推理：(1)如果行星系統(tǒng)是以太陽為中心的，則金星會顯示出位相變化；(2)金星顯示出位相變化；(3)所以，行星系統(tǒng)是以太陽為中心的。6.2自然演繹推理假言推理的一般形式：P,PQQ拒取式推理的一般形式：PQ,QP注意應避免以下兩類錯誤：肯定后件Q的錯誤否定前件P的錯誤6.2自然演繹推理例：設已知下列事實：A,B,AC,B∧CD,DQ求證：Q為真。證明：A,ACCB,CB∧CB∧C,B∧CDDD,DQQQ為真P規(guī)則和假言推理引入合取詞T規(guī)則和假言推理T規(guī)則和假言推理6.2自然演繹推理例：設已知下列事實：(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)點：表達定理證明過程自然，容易理解，而且它擁有豐富的推理規(guī)則，推理過程靈活，便于在它的推理規(guī)則中嵌入領域啟發(fā)式知識。缺點：容易產(chǎn)生組合爆炸，推理過程中得到的中間結論一般呈指數(shù)形式遞增。6.3與/或形演繹推理與/或形演繹推理是一種直接的推理方法，基本思想：把有關問題的知識和信息分為規(guī)則與事實兩類。規(guī)則由包含蘊含式的表達式表示。事實由無蘊含式的表達式表示。畫出與/或樹，然后通過蘊含式進行演繹推理。

推理形式：正向演繹、逆向演繹和雙向演繹。6.3.1與/或形正向演繹推理正向演繹推理對應于正向推理，從已知事實出發(fā)，反復嘗試所有可利用的規(guī)則(F規(guī)則)進行演繹推理，直至得到某個目標公式的一個終止條件為止。這種推理對已知事實、F規(guī)則及目標公式的表示形式都有一定的要求，如果不是所要求的形式，就需要進行變換。6.3.1與/或形正向演繹推理事實表達式的與/或形變換及其與/或樹表示F規(guī)則的表示形式目標公式的表示形式推理過程含有變量的表達式6.3.1與/或形正向演繹推理一、事實表達式及其與或形表示正向演繹推理要求事實用不包含的與/或形表示。把一個表達式轉化為標準的與/或形的步驟如下：(1)利用等價式：PQPQ，消去；(2)把移到每個謂詞符號的前面；(3)重新命名變元，使不同量詞約束的變元有不同的名字；(4)引人Skolem函數(shù)消去存在量詞；(5)將公式化為前束形；(6)略去全稱量詞；(7)重新命名變量，使主要合取式中的變元不同名。過程與化子句集類似，但不必把公式化為子句的合取形式，也不能消去公式中的合取符。標準的與/或形：Q(z,a){[R(y)P(y)]S(a,y)}6.3.1與/或形正向演繹推理根節(jié)點：整個表達式葉節(jié)點：謂詞公式中的單個文字節(jié)點：表示事實表達式及其子表達式(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與/或形正向演繹推理用與/或樹表示事實表達式的重要性質(zhì)：從與/或樹中可以讀出由變換表達式得到的一組子句。每個子句是由葉節(jié)點組成的公式。每個子句相當于與/或樹的一個解圖。3個子句：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是任意的與或形表達式；L、W中所有變元都是量化，默認作用于整個蘊含式。各條規(guī)則的變元各不相同，而且規(guī)則中的變元與事實表達式中的變量也不相同。6.3.1與/或形正向演繹推理問題：為什么F規(guī)則的左部L限制為單文字？

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

AB

ACADBEBGCG歸結反演圖ACCGBGABABBNIL6.3.1與/或形正向演繹推理五、含有變量的表達式如果事實表達式、規(guī)則和目標表達式中有變量，則在推理中需要用最一般合一進行變元的置換。R16.3.1與/或形正向演繹推理注意：當事實表達式、F規(guī)則和目標表達式中包含變量，只有解圖中所用置換是一致的，解圖對應的子句才成立。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與/或形正向演繹推理定義：設有一個置換集U：{u1，u2，…，un}，每個ui是一個置換對的集合，ui={ti1/vi1,ti2/vi2，…，tim(i)/vim(i)}，其中：t為項，v為變量。令：U1=(v11，…，v1m(1)，v21，…，v2m(2)，…，vnm(n))

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

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

U={u1，u2}是一致的，其合一復合為{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(A)/x，A/z}6.3.2與/或形逆向演繹推理從目標表達式出發(fā)，通過逆向使用蘊含式(B規(guī)則)進行演繹推理，直到得到包含已知事實的終止條件為止。目標表達式的與/或形變換及其與/或樹表示B規(guī)則的表示形式已知事實的表示形式推理過程6.3.2與/或形逆向演繹推理一、目標表達式及其與/或樹表示將目標表達式轉化成無的與或形式，并用與/或樹表示，轉化過程與正向演繹中對事實表達式的變換相似。6.3.2與/或形逆向演繹推理不同處：用約束的變元的Skolem函數(shù)替換，由約束的相應變元，然后略去，再消去。

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

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