1、人工智能與專家系統第4章 邏輯推理4.1 推理的基本概念4.2 歸結演繹推理4.4 歸結反演的改進策略4.3 基于歸結反演的問題求解4.1 推理的基本概念4.1.1 推理方式及其分類4.1.2 推理的控制策略4.1.3 模式匹配及其變量代換4.1.1 推理方式及其分類1 演繹推理、歸納推理、默認推理 演繹推理:是從全稱判斷推導出特稱判斷的過程，即由一般性知識推理適合于某一具體情況的結論，是一種從一般到個別的推理。 歸納推理:是從足夠多的事例中歸納出一般性結論的推理過程，是一種從個別到一般的推理。 默認推理:是在知識不完全的情況下假設某些條件已經具備所進行的推理 2 確定性推理、不確定性推理 確

2、定性推理:是指推理時所用的知識都是精確的，推出的結論也是確定的，其真值或者為真，或者為假。 不確定性推理:是指推理時所用的知識不都是精確的，推出的結論也不完全是肯定的，其真值位于真與假之間。3 單調推理、非單調推理 單調推理:隨著推理過程向前推進及新知識的進入，推出的結論呈單調增加的趨勢。 非單調推理:由于新知識的加入，不僅沒有加強已推出的結論，反而要使得推理退回到前面的某一步，重新開始。4 啟發式推理、非啟發式推理 啟發式推理:運用與問題有關的啟發性知識，且能加快推理進程的推理。5 基于知識的推理、直覺推理 基于知識的推理:根據已掌握的事實，通過運用知識進行推理。 直覺推理:根據常識進行的推

3、理。4.1.2 推理的控制策略1 推理方向 （1）正向推理 （2）逆向推理 （3）混合推理2 求解策略 推理的求解策略:推理是只求一個解，還是求所有解以及最優解等。3 限制策略 推理的限制策略:在控制策略中指定推理的限制條件，以對推理的深度、寬度、時間、空間等進行限制。4 沖突消解策略 在推理過程中，可能發生已知事實可與知識庫中的多個知識匹配成功；或者有多個已知事實可與知識庫中的多個知識匹配成功。稱這種情況為發生了沖突。 沖突消解:需要按一定策略解決沖突，以便從中挑選一個知識用于當前的推理，稱這一解決沖突的過程為沖突消解。 解決沖突所用的方法稱為沖突消解策略。4.1.3 模式匹配及其變量代換

4、模式匹配: 兩個知識模式（如兩個謂詞公式、兩個框架片斷等）比較，檢查這兩個知識模式是否完全一致或近似一致。如果兩者完全一致，或者雖不完全一致但其相似程度落在指定的限度內，就稱它們是可匹配的，否則為不可匹配。 確定性匹配: 兩個知識模式完全一致，或者經過變量代換后變得完全一致。 例:設有如下兩個知識模式：P1：Father（李四，李小四）and Man (李小四)P2：Father(x,y) and Man (y) 若用常量“李四”代換變量x，用常量“李小四”代換變量y，則P1與P2就變得完全一致。 定義4.1 代換是形如 t1/x1 , t2/x2, ，tn/xn 的有限集合。其中 t1, t

5、2 tn是項； x1, x2 xn是互不相同的變元； ti /xi 表示用ti 代換 xi , 不允許ti 與 xi 相同，也不允許變元xi循環地出現在另一個tj中。 定義4.2 設 =t1/x1, t2/x2, ，tn/xn =u1/y1, u2/y2, ，um/ym是兩個代換，則此兩個代換的復合也是一個代換，它是從t1/x1, t2/x2, , tn/xn, u1/y1, u2/y2, ，um/ym中刪去如下兩種元素： ti/xi 當ti=xi ui/yi 當yix1, x2, ，xn后剩下的元素所構成的集合，記為 定義4.3 設有公式集F=F1, F2, , Fn,若存在一個代換使得F1

6、=F2= =Fn則稱為公式集F的一個合一，且稱F1, F2, Fn是可合一的。 定義4.4 設是公式集F的一個合一，如果對任一個合一都存在一個代換，使得= 。則稱是公式集F的最一般合一(mgu)。 差異集：設有如下兩個謂詞公式：F1：P（x, y, z） F2：P (x, f (A), h(B) )分別從F1與F2的第一個符號開始比較，得到第一個差異集：D1=y, f (A)當繼續比較，又發現F1中的z與F2中的h(B)不同，則得到第二個差異集： D2=z, h(B)求最一般合一算法: （1）初始化，令k=0, Fk=F,k=。其中，是代換空集。 （2）若Fk只含一個表達式，則算法停止，k就是

7、最一般合一；否則轉步驟（3）。 （3）找出Fk的差異集Dk。 （4）若Dk中存在變元xk和項tk，且xk不在tk中出現，則：k+1=k 。tk/ xk Fk+1=Fk tk/ xk k=k+1 轉步驟（2）；否則， 算法終止，F的最一般合一不存在。例4.1 設有公式集：F=P(A, x, f (g (y), P(z, f (z), f (u) ，求其最一般合一。解：初始化，令k=0，0=， F0=F= P (A, x, f (g (y), P(z, f (z), f (u) Loop 1： F0含有2個表達式，故0不是最一般合一， F0的差異集D0=A，z， 可有代換A/z， 1=0A/z=A

8、/z F1=F0A/z = P(A, x, f (g (y), P(A, f (A), f (u) Loop 2： F1含有2個表達式，故1不是最一般合一， F1的差異集D1=x，f (A)，可有代換f (A)/x，2=1 。f (A)/x =A/z 。f (A)/x =A/z, f (A)/x F2=F1f (A)/x = P(A, f (A), f (g (y), P(A, f (A), f (u)Loop 3： F2的差異集D2=g (y)，u，可有代換g (y)/u， 3=2 。g (y)/u = A/z, f (A)/x 。g (y)/u =A/z, f (A)/x, g (y)/u

9、 F3=F2g (y)/u = P(A, f (A), f (g (y), P(A, f (A), f (g(y) = P(A, f (A), f (g (y) Loop 4：F3中只含有一個表達式，故算法成功終止。公式集 F的最一般合一為3 =A/z, f (A)/x, g (y)/u4.2 歸結演繹推理 4.2.1 謂詞公式化為子句集的方法 4.2.2 歸結原理 4.2.3 歸結反演 定理證明的實質是對已知前提P和待證結論Q證明PQ的永真性。 應用反證法的思想可把關于永真性的證明轉化為不可滿足性的證明，即證明PQ是不可滿足的。4.2.1 謂詞公式化為子句集的方法 定義4.5 在謂詞邏輯中，

10、把原子謂詞公式及其否定統稱為文字。任何文字的析取式稱為子句。 定義4.6 不包含任何文字的子句稱為空子句。 由于空子句不含有文字，它不能被任何解釋滿足，所以空子句是永假的，不可滿足的。謂詞公式化成子句集的步驟: （1）消去蘊涵連詞 利用下述等價關系消去謂詞公式中的蘊涵連詞“”：PQ PQ （2）減小否定連詞的轄域 利用下述等價關系把“”移到緊靠謂詞的位置上： （3）約束變元標準化 （4）消去存在量詞 若存在量詞不在全稱量詞的轄域內，則用一個個體常量替換受該存在量詞約束的變元。 若存在量詞位于一個或多個全稱量詞的轄域內，則需要用Skolem函數f (x1, x2, ，xn )替換受該存在量詞約束

11、的變元y。 （5）組成全稱量詞前綴 （6）利用等價關系把母式化為Skolem標準形： （7）消去全稱量詞。 （8）對變元更名，使不同子句中的變元不同名。 （9）消去合取連詞，得到子句集。例4.2 請將下述謂詞公式化為子句集：解：4.2.2 歸結原理 子句集中的子句之間是合取關系，其中只要有一個子句不可滿足，子句集就不可滿足。空子句是不可滿足的。因此，若一個子句集中包含空子句，則這個子句集是不可滿足的。1. 命題邏輯中的歸結原理 定義4.7 若P是原子謂詞公式，則稱P與P為互補文字。 定義4.8 設C1與C2是子句集中的任意兩個子句，如果C1中的文字L1與C2中的文字L2互補，那么從C1和C2中

12、分別消去L1和L2，并將二個子句中余下的部分析取，構成一個新子句C12，則稱這一過程為歸結，稱C12為C1和C2的歸結式，稱C1和C2為C12的親本子句。 定理4.2 歸結式C12是其親本子句C1與C2的邏輯結論。 推論4.1 設C1與C2是子句集S中的兩個子句，C12是它們的歸結式，若用C12代替C1和C2后得到新子句集S1，則由S1的不可滿足性可推出原子句集S的不可滿足性，即 S1的不可滿足性 S的不可滿足性 推論4.2 設C1與C2是子句集S中的兩個子句，C12是它們的歸結式，若把C12加入S中，得到新子句集S2，則S與S2在不可滿足的意義上是等價的，即 S2的不可滿足性 S的不可滿足性

13、2. 謂詞邏輯中的歸結原理 在謂詞邏輯中，由于子句中含有變元，所以不可直接消去互補文字，先對變元代換，才能進行歸結。例如： 用最一般合一：=A / x 對兩個子句分別進行代換： C1=P(A)Q(A) C2=P(A)R(y) 得到歸結式：Q(A) R(y) 定義4.9 設C1與C2是兩個沒有相同變元的子句，L1和L2分別是C1和C2中的文字，若是L1和L2的最一般合一，則稱C12=(C1-L1)(C2-L2)為C1和C2的二元歸結式，L1和L2稱為歸結式的文字。例4.3 設C1=P(A)Q(x)R(x)，C2=P(y)Q(B)，給出C1和C2的歸結式。 上述歸結過程可以用歸結樹表示如圖4.1所

14、示。 圖4.1 例4.3的一種歸結樹 若選L1= Q(x), L2=Q(B), =B/x, 則可得：C12 = (P(A), Q(B), R(B)- Q(B)( P(y), Q(B)-Q(B) =(P(A), R(B)(P(y) =P(A), R(B), P(y) =P(A)R(B)P(y)上述歸結過程的歸結樹如圖4.2所示。圖4.2 例4.3的另一種歸結樹4.2.3 歸結反演 應用歸結原理證明結論為真的過程稱為歸結反演。 設F為已知前提的公式集，Q為目標公式（結論），用歸結反演證明Q為真的步驟： 否定Q，得到 Q； 把 Q并入到公式集F中，得到F， Q； 把公式集F， Q化為子句集S； 應用

15、歸結原理對子句集S中的子句進行歸結，并把每次歸結得到的歸結式都并入S中。如此反復進行，若出現了空子句，則停止歸結，此時就證明了Q為真。例4.6 已知求證：G 是F的邏輯結論。證：首先把F和G 化為子句集圖4.4 例4.6的歸結樹例4.7 在第2章例2.4中曾經得到如下公式： 自然數都是大于零的整數。所有整數不是偶數就是奇數。偶數除以是整數。求證：所有自然數不是奇數就是其一半為整數的數。證：首先把求證的問題用謂詞公式表示出來：把F1，F2，F3及G 化成子句集：(1) N(x) GZ(x) (2) N(u) I(u)(3) I(y)E(y)O(y) (4) E(z)I(s(z)(5)N(t)(6

16、) O(t)(7) I(s(t)圖4.5 例4.7的歸結樹4.3 基于歸結反演的問題求解問題求解的步驟： 把已知前提用謂詞公式表示，并且化為相應的子句集S。 把待求解的問題也用謂詞公式表示，把它的否定式與謂詞ANSWER構成一個析取式，ANSWER的變元數量和變元名必須與問題公式的變元一致。 把此析取式化為子句集，并且把該子句集加入到子句集S中，得到子句集S。 對S應用歸結原理進行歸結。 若在歸結樹的根節點中僅得到歸結式ANSWER，則答案就在ANSWER中。例4.8 已知F1：王（Wang ）先生是小李（Li）的老師。F2：小李與小張（Zhang ）是同班同學。F3：如果x與y是同班同學，則

17、x的老師也是y的老師。求：小張的老師是誰？解： 1 定義謂詞 T(x, y) x是y的老師。 C(x, y) x與y是同班同學。2 謂詞公式表示目標公式G的否定式與ANSWER的析取式為：3 化為子句集(1)T(Wang , Li)(2) C (Li, Zhang )(3) C(x, y) T(z, x)T(x, y)(4) T(u, Zhang )ANSWER(u)圖4.6 例4.8的歸結樹 例4.9 設A，B，C三人中有人從不說真話，也有人從不說假話，某人向這三人分別提出同一個問題：誰是說謊者？A答：“B和C都是說謊者”；B答：“A和C都是說謊者”；C答：“A和B中至少有一個是說謊者”。求

18、誰是老實人，誰是說謊者？解：1 定義謂詞： T(x) 表示x說真話。 2 謂詞公式表示如果A說的是真話，則有： T(A) T(B)T(C)如果A說的是假話，則有： T(A) T(B)T(C)對B和C說的話作相同的處理，可得： T(B) T(A) T(C) T(B) T(A)T(C) T(C ) T(A) T(B) T(C ) T(A)T(B)3 化成子句集S(1) T(A) T(B)(2) T(A) T(C)(3)T(A)T(B)T(C)(4) T(B) T(C)(5) T(C ) T(A) T(B)(6)T(C )T(A)(7)T(C )T(B)求誰是老實人的目標公式：( x)T(x) (8

19、) T(x)ANSWER(x) 圖4.7 求誰是老實人的歸結樹 證明A和B不是老實人： 設A不是老實人，則有T(A)，把它的否定式T(A) 加入到S中，得到子句集S2。 對S2歸結，從而證明了A不是老實人。 同理，可證明B也不是老實人。圖4.8 例4.9證明A不是老實人的歸結樹4.4 歸結反演的改進策略4.4.1 刪除策略4.4.2 限制策略4.4.1 刪除策略1 純文字刪除 如果某文字L在子句集中不存在可與之互補的文字L，則稱該文字為純文字。 在歸結時純文字不可能被消去，因而用包含它的子句進行歸結時不可能得到空子句。例如，設有子句集：S= PQR, QR，Q, R 其中，P是純文字，因此可將子句 PQR從S中刪去。2 重言式刪除 如果一個子句中同時包含互補文字時，則稱該子句為重言式。 例如 P(x) P(x), P(x)Q(x) P(x)都是重言式。 重言式是真值為真的子句。對于一個子句集來說，增加或者刪去一個真值為真的子句都不會影響它的不可滿足性，因而可從子句集中刪去重言式。3 包孕刪除 設有子句C1和C2，如果存在一個代換，使得 則稱C1包孕于C2。 例如： P(x) 包孕于 P(y)Q(z) =y/x 或稱 P(x) 被 P(y)Q(z) 包孕 把子句集中被包孕的子句刪去后，不會影響子句集的不可