【正文】 第四章 確定性推理 規(guī)則的 演繹推理 —— 逆向演繹 2/27/2023 67 化目標(biāo)表達(dá)式為與或形 ? 消去蘊(yùn)涵符號： ～ P∨Q 取代 P→Q ? 減少否定符號的管轄域 ? 對變量標(biāo)準(zhǔn)化 ? 消去全稱量詞 ： 引入 Skolem函數(shù) ? 消去存在量詞 第四章 確定性推理 規(guī)則的 演繹推理 —— 逆向演繹 2/27/2023 68 目標(biāo)表達(dá)式化為與或形舉例 例： (?z) (?x)(?y){[(P(x) ?Q(x)) ?R(y)] ?U(z)} 前三步： 1, 消蘊(yùn)涵符 2, 移動否定符 3, 變量標(biāo)準(zhǔn)化 等 3步與正向推理中化事實(shí)的表達(dá)式方法相同 4, 消全稱量詞 (skolem化 (對偶形 ) ） 原則：對于一個(gè)受全稱量詞約束的變量，如果他受存在量詞約束，則該變量用一個(gè)函數(shù)代替。當(dāng)產(chǎn)生的圖包含有終止在目標(biāo)節(jié)點(diǎn)上的一個(gè)解圖時(shí)，系統(tǒng)便成功地結(jié)束。 對于一個(gè)受存在量詞約束的變量，消去原則： ? 如果他不受全程量詞約束，則該變量用一個(gè)常量代替 ? 如果他受全程量詞約束，則該變量用一個(gè)函數(shù)代替，且全稱量詞變?yōu)榇嬖诹吭~。 ? 事實(shí)是 有關(guān)問題狀態(tài)和環(huán)境的知識， ? 規(guī)則演繹的任務(wù)就是從給定的事實(shí)證明某個(gè)目標(biāo)公式成立。 第四章 確定性推理 演繹推理 2/27/2023 53 消解方法小結(jié) ? 求子句集，進(jìn)行歸結(jié)，方法簡單 ? 通過修改證明樹的方法，提取回答 ? 方法通用 ? 求解效率低，不宜引入啟發(fā)信息 ? 不宜理解推理過程 第四章 確定性推理 演繹推理 2/27/2023 54 基于規(guī)則的演繹推理（一） ? 歸結(jié)反演系統(tǒng)解決問題的效率低下 ? 歸結(jié)演繹并非人類的自然思維方式，不利于人們從自然思維的角度組織問題的求解和提供問題求解所需的知識 ? 基于 規(guī)則的演繹推理，運(yùn)用推理規(guī)則，直接推導(dǎo)目標(biāo)公式 ? 這符合人的自然思維方式，也能通過規(guī)則 (作為啟發(fā)式知識 )更有效地引導(dǎo)演繹推理過程。 第四章 確定性推理 演繹推理 2/27/2023 52 祖先過濾策略 ? 祖先過濾策略 ：參與歸結(jié)的兩個(gè)子句中至少有一個(gè)是初始子句集中的子句，或者一個(gè)子句是另一個(gè)子句的祖先。 ? 線性輸入策略是不完備的。即對一個(gè)不可滿足的子句集運(yùn)用支持集策略進(jìn)行歸結(jié)，最終總會導(dǎo)出空子句。 第四章 確定性推理 演繹推理 2/27/2023 50 支持集策略 ? 支持集策略： 每次歸結(jié)時(shí)．參與歸結(jié)的子句中至少應(yīng)有一個(gè)是由目標(biāo)公式的否定所得到的子句，或者是它們的后裔 ? 后裔的定義：設(shè) α1是子句 ? α1 與另外某子句的歸結(jié)式是 α1 的后裔 ? α1 的后裔與其他子句的歸結(jié)式是 α1 的后裔。 第四章 確定性推理 演繹推理 2/27/2023 49 包孕刪除法 ? 設(shè) C1， C2是兩個(gè)子句，若存在置換 σ，使得C1σ? C2，則稱子句 C2包孕 C1 ? 例如， P(a)VQ(y)包孕 P(x) (σ={a/x}) ? P(a)VQ(y)包孕 Q(y) ? 對于一個(gè)子句集，刪去一個(gè)被別的子句包孕的子句，不會影響它的不可滿足性。 ?重言式是真值為真的子句。 第四章 確定性推理 演繹推理 2/27/2023 48 重言式刪除法 ?如果一個(gè)子句中同時(shí)包含互補(bǔ)文字對，則稱該子句為重言式。 ? 因此，這樣的子句對歸結(jié)是無意義的，把它從子句集中刪去，不會影響子句集的不可滿足性。 ? (3)包孕刪除法 第四章 確定性推理 演繹推理 2/27/2023 47 純文字刪除法 ? 如果某文字 L在子句集中不存在可與之互補(bǔ)的文字~L，則稱該文字為純文字。 ? 刪除策略有幾種刪除方法： ? (1)純文字刪除法。 第四章 確定性推理 演繹推理 2/27/2023 46 刪除策略 ? 如果在歸結(jié)時(shí)能把子句集中的無用子句刪除掉，這樣就會縮小尋找范圍，減少比較次數(shù)。 ? 線性輸入策略。 第四章 確定性推理 演繹推理 2/27/2023 45 限制策略 ? 限制策略不涉及被歸結(jié)子句的排序．只允許某些歸結(jié)發(fā)生。 ? 寬度優(yōu)先： ? 先生成第 1層的所有歸結(jié)式．然后是第 2層所有的歸結(jié)式，依次類推，直到產(chǎn)生空子句或不能再進(jìn)行歸結(jié)為止。 ? 把原始子句看成 0層歸結(jié)式。 ? 歸結(jié)搜索策略一般包括：排序策略和限制策略 第四章 確定性推理 演繹推理 2/27/2023 44 排序策略 ? 歸結(jié)順序與狀態(tài)空間的擴(kuò)展順序類似。 ? 下面以猴子摘香蕉問題為例來說明 第四章 確定性推理 演繹推理 2/27/2023 39 用消解原理解猴子摘香蕉問題 ? 為了把狀態(tài)空間的算符描述與謂詞演算結(jié)合起來，將狀態(tài)添到謂詞上； ? 將算符看成是把一種狀態(tài)映射成另一種狀態(tài)的函數(shù)； ? 問題簡化成沒有 goto()規(guī)則； c 第四章 確定性推理 演繹推理 2/27/2023 40 猴子摘香蕉問題的表示 問題可以描述如下 ： 1, ~ONBOX(s0) 2, (?x)(?s)(~ONBOX(s) ? AT(box, x, push(x, s))) 3, (?s)(ONBOX(climbbox(s))) 4, (?s)((ONBOX(s) ? AT(box, c, s)) ? HB(grasp(s))) 5, (?x)(?s)(AT(box, x, s) ? AT(box, x, climb(s))) 求解： (?s)HB(s) 第四章 確定性推理 演繹推理 2/27/2023 41 猴子摘香蕉問題的子句集 1, ~ON(s0) 2, ON(s1) ? AT(box, x1, push(x1, s1)) 3, ON(climb(s2)) 4, ~ON(s3) ? ~AT(box, c, s3) ? HB(grasp(s3)) 5, ~AT(box, x4, s4) ?AT(box, x4, climb(s4)) 6, ~HB(s5) 第四章 確定性推理 演繹推理 2/27/2023 42 ~HB(s5) ~ON(s3) ? ~AT(box, c, s3) ? HB(grasp(s3)) ~ON(s3) ? ~AT(box, c, s3) {grasp(s3)/s5} ON(climb(s2)) {climb(s2)/s3} ~AT(box, c, climb(s2)) ~ON(s0) ON(s1) ? AT(box, x1, push(x1, s1)) {s0/s1} AT(box, x1, push(x1, s0)) ~AT(box, x4, s4) ?AT(box, x4, climb(s4)) {x4/x1,push(x4,s0)/s4} AT(box, x4, climb(push(x4,s0))) NIL {c/x4,push(c,s0)/s2} HB(s5) ? HB(grasp(s3)) ? ? HB(grasp(climb(s2))) HB(grasp(climb(push(c,s0)))) 猴子摘香蕉問題的（修正）消解樹 第四章 確定性推理 演繹推理