《人工智能與專家系統(tǒng)(第二版)》第4章 邏輯推理

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

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

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

4、模式匹配: 兩個知識模式（如兩個謂詞公式、兩個框架片斷等）比較，檢查這兩個知識模式是否完全一致或近似一致。如果兩者完全一致，或者雖不完全一致但其相似程度落在指定的限度內(nèi)，就稱它們是可匹配的，否則為不可匹配。 確定性匹配: 兩個知識模式完全一致，或者經(jīng)過變量代換后變得完全一致。 例:設(shè)有如下兩個知識模式：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是項(xiàng)； x1, x2 xn是互不相同的變元； ti /xi 表示用ti 代換 xi , 不允許ti 與 xi 相同，也不允許變元xi循環(huán)地出現(xiàn)在另一個tj中。 定義4.2 設(shè) =t1/x1, t2/x2, ，tn/xn =u1/y1, u2/y2, ，um/ym是兩個代換，則此兩個代換的復(fù)合也是一個代換，它是從t1/x1, t2/x2, , tn/xn, u1/y1, u2/y2, ，um/ym中刪去如下兩種元素： ti/xi 當(dāng)ti=xi ui/yi 當(dāng)yix1, x2, ，xn后剩下的元素所構(gòu)成的集合，記為 定義4.3 設(shè)有公式集F=F1, F2, , Fn,若存在一個代換使得F1

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

7、最一般合一；否則轉(zhuǎn)步驟（3）。 （3）找出Fk的差異集Dk。 （4）若Dk中存在變元xk和項(xiàng)tk，且xk不在tk中出現(xiàn)，則：k+1=k 。tk/ xk Fk+1=Fk tk/ xk k=k+1 轉(zhuǎn)步驟（2）；否則， 算法終止，F(xiàn)的最一般合一不存在。例4.1 設(shè)有公式集：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個表達(dá)式，故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個表達(dá)式，故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中只含有一個表達(dá)式，故算法成功終止。公式集 F的最一般合一為3 =A/z, f (A)/x, g (y)/u4.2 歸結(jié)演繹推理 4.2.1 謂詞公式化為子句集的方法 4.2.2 歸結(jié)原理 4.2.3 歸結(jié)反演 定理證明的實(shí)質(zhì)是對已知前提P和待證結(jié)論Q證明PQ的永真性。 應(yīng)用反證法的思想可把關(guān)于永真性的證明轉(zhuǎn)化為不可滿足性的證明，即證明PQ是不可滿足的。4.2.1 謂詞公式化為子句集的方法 定義4.5 在謂詞邏輯中，

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

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

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

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

14、示。 圖4.1 例4.3的一種歸結(jié)樹 若選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)上述歸結(jié)過程的歸結(jié)樹如圖4.2所示。圖4.2 例4.3的另一種歸結(jié)樹4.2.3 歸結(jié)反演 應(yīng)用歸結(jié)原理證明結(jié)論為真的過程稱為歸結(jié)反演。 設(shè)F為已知前提的公式集，Q為目標(biāo)公式（結(jié)論），用歸結(jié)反演證明Q為真的步驟： 否定Q，得到 Q； 把 Q并入到公式集F中，得到F， Q； 把公式集F， Q化為子句集S； 應(yīng)用

15、歸結(jié)原理對子句集S中的子句進(jìn)行歸結(jié)，并把每次歸結(jié)得到的歸結(jié)式都并入S中。如此反復(fù)進(jìn)行，若出現(xiàn)了空子句，則停止歸結(jié)，此時就證明了Q為真。例4.6 已知求證：G 是F的邏輯結(jié)論。證：首先把F和G 化為子句集圖4.4 例4.6的歸結(jié)樹例4.7 在第2章例2.4中曾經(jīng)得到如下公式： 自然數(shù)都是大于零的整數(shù)。所有整數(shù)不是偶數(shù)就是奇數(shù)。偶數(shù)除以是整數(shù)。求證：所有自然數(shù)不是奇數(shù)就是其一半為整數(shù)的數(shù)。證：首先把求證的問題用謂詞公式表示出來：把F1，F(xiàn)2，F(xiàn)3及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的歸結(jié)樹4.3 基于歸結(jié)反演的問題求解問題求解的步驟： 把已知前提用謂詞公式表示，并且化為相應(yīng)的子句集S。 把待求解的問題也用謂詞公式表示，把它的否定式與謂詞ANSWER構(gòu)成一個析取式，ANSWER的變元數(shù)量和變元名必須與問題公式的變元一致。 把此析取式化為子句集，并且把該子句集加入到子句集S中，得到子句集S。 對S應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)。 若在歸結(jié)樹的根節(jié)點(diǎn)中僅得到歸結(jié)式ANSWER，則答案就在ANSWER中。例4.8 已知F1：王（Wang ）先生是小李（Li）的老師。F2：小李與小張（Zhang ）是同班同學(xué)。F3：如果x與y是同班同學(xué)，則

17、x的老師也是y的老師。求：小張的老師是誰？解： 1 定義謂詞 T(x, y) x是y的老師。 C(x, y) x與y是同班同學(xué)。2 謂詞公式表示目標(biāo)公式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的歸結(jié)樹 例4.9 設(shè)A，B，C三人中有人從不說真話，也有人從不說假話，某人向這三人分別提出同一個問題：誰是說謊者？A答：“B和C都是說謊者”；B答：“A和C都是說謊者”；C答：“A和B中至少有一個是說謊者”。求

18、誰是老實(shí)人，誰是說謊者？解：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)求誰是老實(shí)人的目標(biāo)公式：( x)T(x) (8

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