第三章 確定性推理

1、第三章 確定性推理 3.1 概述概述 3.2 自然演繹推理自然演繹推理 3.3 歸結(jié)演繹推理歸結(jié)演繹推理 3.4 與或形演繹推理與或形演繹推理 所謂推理就是按某種策略由已知判斷推 出另一判斷的思維過程。 一般來說，推理都包括兩種判斷：一種 是已知的判斷，包括已知的知識(shí)和已知 事實(shí)；另一種是由已知判斷推出的新判 斷，即推理的結(jié)論。 在人工智能中，推理是由程序?qū)崿F(xiàn)的， 稱為推理機(jī)。 2 1. 演繹推理、歸納推理、默認(rèn)推理 演繹推理：從一般到特殊。例如三段論。 歸納推理：從個(gè)體到一般。 默認(rèn)推理：缺省推理，在知識(shí)不完全的情況下假設(shè)某 些條件已經(jīng)具備所進(jìn)行的推理。 2. 確定性、不確定性推理 3. 單

2、調(diào)性、非單調(diào)推理 推出的結(jié)論是否單調(diào)增加。 4. 啟發(fā)式、非啟發(fā)式推理 所謂啟發(fā)性知識(shí)是指與問題有關(guān)且能加快推理進(jìn)程、 求得問題最優(yōu)解的知識(shí)。 5. 基于知識(shí)的推理、統(tǒng)計(jì)推理、直覺推理 從方法論的角度劃分。 3 推理的控制策略主要包括：推理方向、搜索策略、 沖突消解策略、求解策略及限制策略。 1. 正向推理 正向推理的基本思想是：從用戶提供的初始已知事 實(shí)出發(fā)，在知識(shí)庫KB中找出當(dāng)前可適用的知識(shí)，構(gòu) 成可適用知識(shí)集KS，然后按某種沖突消解策略從 KS中選出一條知識(shí)進(jìn)行推理，并將推出的新事實(shí)加 入到數(shù)據(jù)庫中作為下一步推理的已知事實(shí)，在此之 后再在知識(shí)庫中選取可適用知識(shí)進(jìn)行推理。如此重 復(fù)進(jìn)行這一

3、過程，直到求得了所要求的解或者知識(shí) 庫中再無可使用的知識(shí)為止。 4 開始 退出 把初始已知事實(shí)送入DB DB中包含問題的 解？ KB中有可適用的 知識(shí)？ 把KB中所有使用知識(shí)都 選出來送入KS KS為空？ 按沖突消解策略從KS中 選出一條知識(shí)進(jìn)行推理 推出的是新事 實(shí)？ 將該新事實(shí)加入DB中 用戶可補(bǔ)充新事 實(shí)？ 把用戶提供的新 事實(shí)加入DB中 Y N N Y N Y N Y N Y 成功 失敗 5 逆向推理的基本思想是：首先選定一個(gè)假 設(shè)目標(biāo)，然后尋找支持該假設(shè)的證據(jù)，若 所需的證據(jù)都能找到，則說明原假設(shè)是成 立的；若無論如何都找不到所需要的證據(jù)， 則說明原假設(shè)不成立，此時(shí)需要另作新的 假設(shè)

4、。 6 開始 退出 提出假設(shè) 該假設(shè)在DB中？ 該假設(shè)是證據(jù)？ 在KB中找出所有能導(dǎo)出 該假設(shè)的知識(shí)送入KS 有此事實(shí)？ 該假設(shè)成立 該假設(shè)成立， 并將此事實(shí)存 入數(shù)據(jù)庫 Y N Y N N N Y 從KS中選出一條知 識(shí)，并將該知識(shí)的 一個(gè)運(yùn)用條件作為 新的假設(shè)目標(biāo) 還有假設(shè)？ 詢問用戶 Y 7 3. 混合推理 先正向后逆向推理 先逆向后正向推理 4. 雙向推理 正向推理與逆向推理同時(shí)進(jìn)行，且在推理過程 中的某一步上“碰頭”。 5. 求解策略 只求一個(gè)解，還是求所有解以及最優(yōu)解。 6. 限制策略 限制推理的深度、寬度、時(shí)間、空間等等。 8 所謂知識(shí)匹配是指對兩個(gè)知識(shí)模式(例如兩個(gè)謂詞公式、

5、框架片斷、語義網(wǎng)絡(luò)片斷)的比較與耦合，及檢查這兩個(gè) 知識(shí)模式是否完全一致或者近似一致。 按匹配時(shí)兩個(gè)知識(shí)模式的相似程度，模式匹配可分為確 定性匹配與不確定性匹配。 確定性匹配是指兩個(gè)知識(shí)模式完全一致，或者經(jīng)過變量 代換后變得完全一致。 例如： P1:father(李四，李小四) and man(李小四) P2:father(x,y) and man(y) 不確定性匹配是指兩個(gè)知識(shí)模式不完全一致，但是它們 的相似程度又在規(guī)定的限度內(nèi)。 9 定義3.1 代換是一個(gè)形如 t1/x1,t2/x2,tn/xn 的有限集合。 其中是t1,t2,tn項(xiàng)； x1,x2,xn是互不相同的 變元；ti/xi表示用

6、ti代換xi，不允許ti與xi相同， 也不允許變元xi循環(huán)地出現(xiàn)在另一個(gè)tj中。 例如： a/x,f(b)/y,w/z是一個(gè)代換 g(y)/x,f(x)/y不是代換 g(a)/x,f(x)/y是代換 10 定義3.2 設(shè) = t1/x1,t2/x2,tn/xn = u1/y1,u2/y2,um/ym 是兩個(gè)代換，則此兩個(gè)代換的復(fù)合也是一個(gè)代換，它是 從 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)成的集合，記為 。 注： ti表示對ti運(yùn)用代換。實(shí)際上就是對一個(gè)公式 先運(yùn)

7、用代換，然后再運(yùn)用代換。 11 例如，設(shè)有代換 = f(y)/x,z/y = a/x,b/y,y/z 則 =f(y)/x,z/y,a/x,b/y,y/z =f(b)/x,y/y,a/x,b/y,y/z =f(b)/x,y/z 12 定義3.3 設(shè)有公式集F=F1,F2,Fn，若存在一個(gè)代換使得 F1=F2=Fn 則稱為公式集F的一個(gè)合一，且稱F1,F2,Fn是可合一的。 例如，設(shè)有公式集 F=P(x,y,f(y),P(a,g(x),z) 則下式是它的一個(gè)合一： =a/x,g(a)/y,f(g(a)/z 一個(gè)公式集的合一一般不唯一。 定義3.4 設(shè)是公式集F的一個(gè)合一，如果對任一個(gè)合一都存 在一

8、個(gè)代換，使得= 則稱是一個(gè)最一般的合一。 最一般合一是唯一的。(算法列在第二章) 13 從一組已知為真的事實(shí)出發(fā)，直接運(yùn)用經(jīng) 典邏輯的推理規(guī)則推出結(jié)論的過程，稱為 自然演繹推理。其中，基本的推理規(guī)則是P 規(guī)則、T規(guī)則、假言推理、拒取式推理等。 假言推理的一般形式 拒取式推理的一般形式 ,P PQQ ,PQQP 14 肯定后件：PQ，Q P （1）如果行星系統(tǒng)是以太陽為中心的，則金 星會(huì)顯示出位相變化。 （2）金星顯示出位相變化。 （3）所以，行星系統(tǒng)是以太陽為中心的。 否定前件： PQ，P Q （1）如果看報(bào)紙，則能知道新聞。 （2）沒有看報(bào)紙。 （3）所以，不知道新聞。 15 設(shè)已知如下事實(shí)

9、： （1）凡是容易的課程小王（Wang）都喜 歡； （2）C班的課程都是容易的； （3）ds是C班的一門課程。 求證：小王喜歡ds這門課程。 16 證明： （1）定義謂詞： EASY (x)：x是容易的。 LIKE (x， y)：x喜歡y。 C(x)： x是C班的一門課程。 將上述事實(shí)及待求的問題用謂詞公式表示出來： EASY (x) LIKE(Wang， x)凡是容易的課程 小王都喜歡。 (x) (C(x) EASY(x) C班的課程都是容易的。 C(ds) ds是C班的一門課程。 LIKE(Wang， ds)小王喜歡ds這門課程。 17 （2）應(yīng)用推理規(guī)則進(jìn)行推理： (x) (C(x) E

10、ASY(x) C(y) EASY(y) （全稱固化） C(ds)，C(y) EASY(y) EASY(ds) （P規(guī)則及假言推理） EASY(ds)，EASY (x)LIKE(Wang，x) LIKE(Wang，ds) （T規(guī)則及假言推理） 即小王喜歡ds這門課。 證畢。 18 定理證明即證明PQ(PQ)的永真性。根 據(jù)反證法，只要證明其反面(PQ)的不可 滿足性即可。 海伯倫(Herbrand)定理為自動(dòng)定理證明奠定 了理論基礎(chǔ)；魯濱遜(Robinson)提出的歸結(jié) 原理使機(jī)器定理證明成為現(xiàn)實(shí)。 19 在謂詞邏輯中，把原子謂詞公式及其否定統(tǒng)稱為 文字。 定義3.5 任何文字的析取式稱為子句。

11、 例如： P(x)Q(x), P(x,f(x)Q(x,g(x) 定義3.6 不包含任何文字的子句稱為空子句。 空子句不含有文字，不能被任何解釋滿足，所以 空子句是永假的，不可滿足的。 任何謂詞公式都可通過等價(jià)關(guān)系及推理規(guī)則化成 相應(yīng)的子句集。 20 1. 利用等價(jià)關(guān)系消去“”和“” 例如公式 可等價(jià)變換成 2. 利用等價(jià)關(guān)系把“”移到緊靠謂詞的位置上 上式經(jīng)等價(jià)變換后 3. 重新命名變元，使不同量詞約束的變元有不同的名字 上式經(jīng)變換后 ()() ( , )()( ( , )( , )xy P x yy Q x yR x y ()( () ( , )()( , )( , )xy P x yyQ

12、x yR x y ()()( , ) ()( ( , )( , )xyP x yy Q x yR x y ()()( , ) ()( ( , )( , )xyP x yz Q x zR x z 21 4. 消去存在量詞 a.存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)，則只要用一 個(gè)新的個(gè)體常量替換受該量詞約束的變元。 b.存在量詞位于一個(gè)或者多個(gè)全稱量詞的轄域內(nèi)，此 時(shí)要用Skolem函數(shù)f(x1,x2,xn)替換受該存在量詞約 束的變元。 上式中存在量詞(y)及(z)都位于(x)的轄域內(nèi)， 所以需要用Skolem函數(shù)替換，設(shè)替換y和z的Skolem 函數(shù)分別是f(x)和g(x)，則替換后得到 5. 把

13、全稱量詞全部移到公式的左邊 ()( , ( ) ( ( , ( )( , ( )xP x f xQ x g xR x g x 22 6. 利用等價(jià)關(guān)系把公式化為Skolem標(biāo)準(zhǔn)形 Skolem標(biāo)準(zhǔn)形的一般形式是 其中，M是子句的合取式，稱為Skolem標(biāo)準(zhǔn)形的母式。 上式化為Skolem標(biāo)準(zhǔn)形后得到 7. 消去全稱量詞 8. 對變元更名，使不同子句中的變元不同名 上式化為 9. 消去合取詞，就得到子句集 ()() ()PQ RP QP R 1 2 ()()() n xxx M ()( , ( )( , ( ) ( , ( )( , ( )xP x f xQ x g xP x f xR x g

14、x ( , ( )( , ( ) ( , ( )( , ( )P x f xQ x g xP y f yR y g y ( , ( )( , ( ) ( , ( )( , ( ) P x f xQ x g x P y f yR y g y 23 定理3.1 設(shè)有謂詞公式F，其標(biāo)準(zhǔn)形的子句 集為S，則F不可滿足性的充要條件是S不可 滿足。 所以： 如果要證明一個(gè)謂詞公式是不可滿足的， 則只要證明其相應(yīng)的子句集是不可滿足的 就可以了。 24 判斷一個(gè)子句的不可滿足性，需要對個(gè) 體域上的一切解釋逐個(gè)進(jìn)行判定，只有 當(dāng)子句對任何非空個(gè)體域上的任何一個(gè) 解釋都是不可滿足的，該子句才是不可 滿足的。 海伯

15、倫構(gòu)造了一個(gè)特殊的域(海伯倫域)， 并證明只要對這個(gè)特殊域上的一切解釋 進(jìn)行判定，就可知子句集是否不可滿足。 25 定義3.7 設(shè)S為子句集，則按下述方法構(gòu)造的域H稱為海伯倫域，記 為H域。 (1)令H0是S中所有個(gè)體常量的集合，若S中不包含個(gè)體常量，則 令H0a，其中a為任意指定的一個(gè)個(gè)體常量。 (2)令Hi+1=HiS中所有n元函數(shù)f(x1,xn)|xj(j=1,n)是Hi中的元 素，其中i=0,1,2,。 例. 求子句集S=P(x)Q(x),R(f(y)的H域。 解：此例中沒有個(gè)體常量，任意指定一個(gè)常量a作為個(gè)體常量，得到 H0=a H1=a,f(a) H2=a,f(a),f(f(a)

16、H3=a,f(a),f(f(a),f(f(f(a) H=a,f(a),f(f(a),f(f(f(a), 26 用H域中的元素代換子句中的變元，則所得的 子句稱為基子句，其中的謂詞稱為基原子。子 句集中所有基原子構(gòu)成的集合稱為原子集。子 句集S在H域上的解釋就是對S中出現(xiàn)的常量、 函數(shù)及謂詞取值，一次取值就是一個(gè)解釋。 定義3.8 子句集S在H域上的一個(gè)解釋I滿足下列條 件： (1)在解釋I下，常量映射到自身； (2)S中的任一個(gè)n元函數(shù)是HnH的映射。即設(shè) h1,h2,H，則f(h1,h2,hn)H; (3)S中的任一個(gè)n元謂詞是HnT,F的映射。謂 詞的真值可以指派為T，也可為F。 27 例

17、如， 設(shè)子句集S=P(a),Q(f(x)，它的H域?yàn)?a,f(a),f(f(a),。S的原子集為 P(a),Q(f(a),Q(f(f(a),，則S的解釋為： I1=P(a),Q(f(a),Q(f(f(a), I2=P(a),Q(f(a),Q(f(f(a), 28 可以證明，對給定域D上的任一個(gè)解釋，總能在H域上構(gòu)造一 個(gè)解釋與它對應(yīng)，如果D域上的解釋能滿足子句集S，則在H 域上的相應(yīng)解釋也能滿足S。 定理3.2 子句集S不可滿足的充要條件是S對H域上一切解釋都 為假。 定理3.3(海伯倫定理) 子句集不可滿足的充要條件是存在一個(gè) 有限的不可滿足的基子句集S。 29 子句集中子句之間是合取關(guān)系，

18、只要有一個(gè) 子句不可滿足，則子句集就不可滿足。而空 子句是不可滿足的。所以若一個(gè)子句集中包 含空子句，則這個(gè)子句集一定是不可滿足的。 魯濱遜歸結(jié)原理的基本思想：檢查子句集S中 是否包含空子句。若包含，則S不可滿足；若 不包含，就在子句集中選擇合適的子句進(jìn)行 歸結(jié)，一旦通過歸結(jié)能推出空子句，就說明 子句集S是不可滿足的。 定義3.9 若P是原子謂詞公式，則稱P與P為 互補(bǔ)文字。 30 定義3.10 設(shè)C1與C2是子句集中的任意兩個(gè)子句。如果 C1中的文字L1與C2中文字L2互補(bǔ)，那么從C1和C2中分別 消去L1和L2，并將兩個(gè)子句中余下的部分析取，構(gòu)成一 個(gè)新子句C12，則稱這一過程為歸結(jié)。稱C

19、12為C1和C2的 歸結(jié)式，C1和C2為C12的親本子句。 例. 設(shè) C1=PQ, C2=QR, C3=P C1與C2歸結(jié)得到：C12=PR C12與C3歸結(jié)得到：C123=R 31 定理3.4 C12是其親本子句C1與C2的邏輯結(jié)論。 證明：設(shè) C1=LC1, C2=LC2, 則C12=C1C2 111 222 () () 1212 () () 1212 121212 1212 CCLCL CL CLC CCCLLC CLLCCC CCCCC CCC 由假言三段論 32 推論1 設(shè)C1與C2是子句集S中的兩個(gè)子句，C12 是它們的歸結(jié)式。若用C12代替C1和C2后得到 新子句集S1，則由S1

20、的不可滿足性可推出原子 句集S的不可滿足性，即 S1的不可滿足性S的不可滿足性 推論2 設(shè)C1與C2是子句集S中的兩個(gè)子句，C12 是它們的歸結(jié)式。若把C12加入S中得到新子句 集S2，則S與S2在不可滿足的意義上是等價(jià)的， 即 S2的不可滿足性S的不可滿足性 33 為了要證明子句集S的不可滿足性，只要對其中 可進(jìn)行歸結(jié)的子句進(jìn)行歸結(jié)，并把歸結(jié)式加入子 句集S，或者用歸結(jié)式替換它的親本子句，然后 對新子句集(S1或者S2)證明不可滿足性就可以了。 如果經(jīng)過歸結(jié)能得到空子句，則立即可得原子句 集S是不可滿足的結(jié)論。 在命題邏輯中，對不可滿足的子句集S，歸結(jié)原 理是完備的。即，若子句集不可滿足，則

21、必然存 在一個(gè)從S到空子句的歸結(jié)演繹；若存在一個(gè)從S 到空子句的歸結(jié)演繹，則S一定是不可滿足的。 對于可滿足的子句集，用歸結(jié)原理得不到任何結(jié) 果。 34 在謂詞邏輯中，由于子句中含有變元，所以不能像命題 邏輯那樣直接消去互補(bǔ)文字，而需要先用最一般合一對 變元進(jìn)行代換，然后才能進(jìn)行歸結(jié)。 例如,設(shè)有兩個(gè)子句 C1=P(x)Q(x), C2= P(a)R(y) 由于P(x)與P(a)不同，所以C1與C2不能直接進(jìn)行歸結(jié)。但是 若用最一般合一 =a/x 對兩個(gè)子句分別進(jìn)行代換： C1 =P(a)Q(a) C2 = P(a)R(y) 就可對它們進(jìn)行歸結(jié)，得到歸結(jié)式： Q(a)R(y) 35 定義3.1

22、1 設(shè)C1與C2是兩個(gè)沒有相同變元的子句，L1和L2分別是C1和C2中 的文字。若是L1和L2的最一般合一，則稱 C12=(C1-L1)(C2-L2) 為C1和C2的二元?dú)w結(jié)式，L1和L2稱為歸結(jié)式上的文字。 例. 設(shè) C1=P(a)Q(x)R(x), C2=P(y)Q(b) 若選L1=P(a),L2=P(y)，則=a/y是L1與L2的最一般合一。 可得： C12=(C1-L1)(C2-L2) =(P(a),Q(x),R(x)-P(a)(P(a),Q(b)-P(a) =(Q(x),R(x)(Q(b) =Q(x),R(x),Q(b) = Q(x)R(x)Q(b) 36 一般來說，若子句C中有兩個(gè)

23、或者兩個(gè)以上的文 字具有最一般合一，則稱C為子句C的因子。 定義3.12 子句C1和C2的歸結(jié)式是下列二元?dú)w結(jié)式之 一： C1與C2的二元?dú)w結(jié)式； C1與C2的因子C22的二元?dú)w結(jié)式； C1的因子C11與C2的二元?dú)w結(jié)式； C1的因子C11與C2的因子C22的二元?dú)w結(jié)式。 1. 對于謂詞邏輯定理3.4仍然適用。對于一階謂詞 邏輯，在不可滿足的意義上歸結(jié)原理也是完備 的。 37 歸結(jié)原理給出了證明子句集不可滿足性的方法。 如欲證明Q為P1,P2,Pn的邏輯結(jié)論，只需證 (P1P2Pn)Q 是不可滿足的。根據(jù)定理3.1知，在不可滿足的意義上，上式 與其子句集是等價(jià)的。 應(yīng)用歸結(jié)原理證明定理的過程稱

24、為歸結(jié)反演。 設(shè)F為已知前提的公式集，Q為目標(biāo)公式(結(jié)論)，用歸結(jié)反 演證明Q為真的步驟是： 否定Q，得到Q； 把Q并入到公式集F中，得到F, Q; 把公式集F, Q化為子句集S； 應(yīng)用歸結(jié)原理對子句集S中的子句進(jìn)行歸結(jié)，并把每次歸 結(jié)得到的歸結(jié)式都并入S中。如此反復(fù)進(jìn)行，若出現(xiàn)了空 子句，則停止歸結(jié)，此時(shí)就證明了Q為真。38 例. 已知 求證：G是F的邏輯結(jié)論。 證明：首先把F和G化為子句集： 然后進(jìn)行歸結(jié)： (6)A(x,y)B(y)由(1)與(3)歸結(jié)，f(x)/z (7)B(b)由(4)與(6)歸結(jié)，a/x, b/y (8)NIL由(5)與(7)歸結(jié) 所以G是F的邏輯結(jié)論。 : ()(

25、)( ( , )( )()( ( )( , ) :() ( )()()( ( , )( ) Fxy A x yB yy C yD x y Gx C xxy A x yB y ( , )( )( ( ),( , )( )( , ( ) ( ), ( , ), ( ) FA x yB yC f xA x yB yD x f x GC zA a b B b 39 A(x,y)B(y)C(f(x) A(x,y)B(y) B(b) NIL C(z) A(a,b) B(b) w上述歸結(jié)過程如下圖歸結(jié)樹所示。 f(x)/z a/x,b/y 40 歸結(jié)策略可分為兩大類： 一類是刪除策略； 刪除某些無用的子句來

26、縮小歸結(jié)的范圍。 一類是限制策略。 通過對參加歸結(jié)的子句進(jìn)行種種限制，盡可能減小歸結(jié)的盲目性， 使其盡快地歸結(jié)出空子句。 歸結(jié)的一般過程 設(shè)有子句集S=C1,C2,C3,C4，則對此子句集歸結(jié)的一般過程是： S內(nèi)任意子句兩兩逐一進(jìn)行歸結(jié)，得到一組歸結(jié)式，稱為第一級(jí)歸 結(jié)式，記為S1。 把S與S1內(nèi)的任意子句兩兩逐一進(jìn)行歸結(jié)，得到一組歸結(jié)式，稱 為第二級(jí)歸結(jié)式，記為S2。 S和S1內(nèi)的子句與S2內(nèi)的任意子句兩兩逐一進(jìn)行歸結(jié)，得到一組 歸結(jié)式，稱為第三級(jí)歸結(jié)式，記為S3。 1.如此繼續(xù)，直到出現(xiàn)了空子句或者不能再繼續(xù)歸結(jié)為止。 41 例. 設(shè)有子句集S=P, R,PQ,QR。歸結(jié)過程為： S: (

27、1)P (2)R (3)PQ (4)QR S1: (5)Q(1)與(3)歸結(jié) (6)Q (2)與(4)歸結(jié) (7)PR (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é) 42 純文字刪除法 如果某文字L在子句集中不存在可與之互補(bǔ)的文字 L，則稱該文字為純文字。包含純文字的子句可 以刪除。 重言式刪除法 如果一個(gè)子句中同時(shí)包含互補(bǔ)文字對，則該字句 稱為重言式。重言式是永遠(yuǎn)為真的子句，可以刪 除。 包孕刪除法 設(shè)有子句C1和C2，如果存在一個(gè)代換，使

28、得 ，則稱C1包孕于C2。 12 CC 43 對參加歸結(jié)的子句提出如下限制：每一次歸結(jié)時(shí)，親本 子句中至少有一個(gè)是由目標(biāo)公式的否定所得到的子句， 或者是它們的后裔。 可以證明，支持集策略是完備的。 例. 設(shè)有子句集S=I(x)R(x),I(a),R(y)L(y),L(a)， 其中I(x)R(x)是目標(biāo)公式否定后得到的子句。 44 I(x)R(x)I(a)R(y)L(y)L(a) R(a) L(a) I(x)L(x) L(a)I(a) NIL 1234 56 87 9 10 a/xx/y a/xa/ya/x 45 限制：參加歸結(jié)的兩個(gè)子句中必須至少有一 個(gè)是初始子句集中的子句。 線性輸入策略可限

29、制生成歸結(jié)式的數(shù)量，具 有簡單、高效的優(yōu)點(diǎn)。 但是它是不完備的。 46 I(x)R(x)I(a)R(y)L(y)L(a) R(a) L(a) I(x)L(x) L(a)I(a) NIL 1234 56 10811 12 R(a) I(a) 7 9 a/xx/ya/y a/x a/xa/ya/x 47 該策略與線性策略比較相似，但放寬了 限制。當(dāng)對兩個(gè)子句C1和C2進(jìn)行歸結(jié)時(shí)， 只要它們滿足下述任一個(gè)條件就可以歸 結(jié)。 C1和C2中至少有一個(gè)是初始子句集中的 子句。 C1和C2中一個(gè)是另外一個(gè)的祖先子句。 1.祖先過濾策略是完備的。 48 求解的步驟： 把已知前提用謂詞公式表示出來，并且化為相應(yīng) 的子句集。設(shè)該子句集的名字為S。 把待求解的問題也用謂詞公式表示出來，然后把 它否定并與謂詞Answer構(gòu)成析取式。Answer是 一個(gè)為了求解問題而專設(shè)的謂詞，其變元必須與 問題公式的變元完全一致。 把此析取式化為子句集，并且把該子句集并入到 子句集S中，得到子句集S。 對S應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)。 1. 若