【正文】 (?z) (?x)(?y){[(~P(x) ?~Q(x)) ? R(y)] ?U(z)} = (? x) {[(~P(x) ?~Q(x)) ? R(f(x))] ?U(a)} ? 消存在量詞 [(~P(x) ?~Q(x)) ? R(f(x))] ?U(a) ? 隱含目標公式的變量都受 存在量詞的約束 第四章 確定性推理 規(guī)則的 演繹推理 —— 正向演繹 2/27/2023 58 事實表達式的與或圖表示 ? 用 K連線表示析取，無連線表示合取 例： Q(w, A)?((~R(v) ? ~P(v)) ? ~S(A, v)) Q(w, A)?((~R(v) ? ~P(v)) ? ~S(A, v)) Q(w, A) (~R(v) ? ~P(v)) ? ~S(A, v) ~R(v) ? ~P(v) ~S(A, v) ~R(v) ~P(v) 第四章 確定性推理 規(guī)則的 演繹推理 —— 正向演繹 2/27/2023 59 將規(guī)則變換為限定形式 ? 如果規(guī)則不是形式： L ? W 其中， L是單文字， W是與或形，變量受全稱量詞約束 ? 則首先變換為這種形式 ? 例： (?x)(((?y)(?z)P(x, y, z)) ? (?u)Q(x, u)) = (?x)(~((?y)(?z)P(x, y, z)) ? (?u)Q(x, u)) = (?x)((?y)(?z)~P(x, y, z) ? (?u)Q(x, u)) = (?x)(?y)(?z) (?u)(~P(x, y, z) ? Q(x, u)) = ~P(x, y, f(x, y)) ? Q(x, u) (Skolem化 ) = P(x, y, f(x, y)) ? Q(x, u) (恢復蘊涵式 ) ? 例： (L1 ? L2) ? W = L1 ? W 和 L2 ? W 第四章 確定性推理 規(guī)則的 演繹推理 —— 正向演繹 2/27/2023 60 對與或圖作變換例 ? 例： 事實： ((P ? Q) ? R) ? (S ? (T ? U)) 規(guī)則： S ? (X ? Y) ? Z ? 事實的 與或圖與 規(guī)則對其進行的變換過程如下圖： 第四章 確定性推理 規(guī)則的 演繹推理 —— 正向演繹 2/27/2023 61 ((P ? Q) ? R) ? (S ? (T ? U)) (P ? Q) ? R P ? Q R P Q S ? (T ? U) S T ? U T U S X ? Y Z X Y P? Q? S P? Q? T? U S? R R? T? U P? Q? X? Z P? Q? Y? Z R? X? Z R? Y? Z 規(guī)則的子句： S ? (X ? Y) ? Z = ~S?(X ? Y) ? Z = ~S ? X ? Z ~S ? Y ? Z 結(jié)論：加入規(guī)則后得到的解圖，是事實與規(guī)則對應子句的歸結(jié)式 第四章 確定性推理 規(guī)則的 演繹推理 —— 正向演繹 2/27/2023 62 目標公式作為終止條件 ? 應用規(guī)則進行推理的目的是為了證明某個目標公式 ? 在正向推理系統(tǒng)中，這種目標表達式只限于可證明的表達式，尤其是可證明的文字析取形的目標公式表達式 ? 在與或圖的產(chǎn)生過程中，目標文字或規(guī)則與圖中文字節(jié)點匹配時，產(chǎn)生新后裔節(jié)點，標記為匹配的目標文字。對于某些不可滿足的子句集，無法用線性輸入歸結(jié)得到結(jié)果。 ?對于一個子句集，增加或刪去一個重言式子句都不會影響它的不可滿足性， ?因而可從子句集中刪去重言式。 ? (2)重言式刪除法。 ? 深度優(yōu)先： ? 產(chǎn)生一個第 1層的歸結(jié)式，然后用第 1層的歸結(jié)式和第 0層的歸結(jié)式進行歸結(jié)，得到第 2層的歸結(jié)式，直到產(chǎn)生空子句結(jié)束，或者不能歸結(jié)，則回溯到其他的上層子句繼續(xù)歸結(jié) ? 單元優(yōu)先： ? 在歸結(jié)過程中優(yōu)先考慮僅由一個文字構(gòu)成的子句，這樣的子句稱為單元子句。這個過程稱為修改證明過程（或修改歸結(jié)過程）。 ?而用反證法，只要能夠證明 ～ (P ? Q)是不可滿足的。 ? 沖突消解的基本思想是對可用知識進行排序。 ? 取一個假設對其進行驗證， ? 若在綜合數(shù)據(jù)庫里，則假設成立 ? 若能被用戶認定為事實，則假設成立，并放入綜合數(shù)據(jù)庫 ? 若可由知識庫中的一個或多個知識導出，則這些知識構(gòu)成可用知識集。 ? 推理策略主要解決推理方向、沖突消解等問題。 ? 重新按新情況進行推理。 第四章 確定性推理 2/27/2023 4 推理的基本問題 ? 智能系統(tǒng)的推理包括兩個基本問題： ?一個是推理的方法 ?一個是推理的控制策略 ? 推理方法主要解決： ?在推理過程中前提與結(jié)論之間的邏輯關(guān)系 ?在非精確性推理中不確定性的傳遞問題 第四章 確定性推理 2/27/2023 5 推理方法的分類 ? 推理可以有多種不同的分類方法 ? 按照推理的邏輯基礎分類： ? 演繹推理 ? 歸納推理 ? 默認推理 ? 按照所用知識的確定性分類： ? 確定性推理 ? 不確定性推理 ? 按照推理過程的單調(diào)性分類（推理過程所得到的結(jié)論是否越來越接近目標）： ? 單調(diào)推理 ? 非單調(diào)推理 第四章 確定性推理 2/27/2023 6 演繹推理 ? 從已知的一般性知識出發(fā)，去推出蘊含在這些已知知識中的適合于某種個別情況的結(jié)論。 ? 推理機就是智能系統(tǒng)中用來實現(xiàn)推理的程序。 ? 按照所選事例的廣泛性，歸納推理可分為： ? 完全歸納推理和不完全歸納推理； ? 按照推理所使用的方法可分為： ? 枚舉歸納推理、類比歸納推理、統(tǒng)計歸納推理和差異歸納推理等。 ? 非單調(diào)推理往往是在知識不完全的情況下發(fā)生的。 ? 基本思想是： ? 用戶需要事先提供一組初始證據(jù)，并將其放入綜合數(shù)據(jù)庫。 ? 這種把正向推理和逆向推理結(jié)合起來所進行的推理稱為混合推理。 ? 歸結(jié)原理亦稱消解原理，是魯賓遜 1965年提出的 ? 歸結(jié)演繹推理實際上是一種“反正法”， 基本思想 ： ? 推理就是要對前提 P和結(jié)論 Q，證明 P ? Q永真。 第四章 確定性推理 演繹推理 2/27/2023 28 歸結(jié) 原理分類 ? 魯賓遜歸結(jié)原理可分為 : ?命題邏輯歸結(jié)原理 ?謂詞邏輯歸結(jié)原理 第四章 確定性推理 演繹推理 2/27/2023 29 歸結(jié)式 ? 歸結(jié)推理的核心是求兩個子句的歸結(jié)式 ? 若 P是原子謂詞公式，則稱 P與 ~P為互補文字 ? 設 C1和 C2是子句集中的任意兩個子句 ? 如果 C1中的文字 L1與 C2中的文字 L2互補 ? 那么可從 C1和 C2中分別消去 L1和 L2 ? 并將 C1和 C2中余下的部分按析取關(guān)系構(gòu)成一個新的子句 C12， ? 則稱這一過程為歸結(jié)， ? 稱 C12為 C1和 C2的歸結(jié)式， C1和 C2為 C12的親本子句。 ? 把原始子句看成 0層歸結(jié)式。 第四章 確定性推理 演繹推理 2/27/2023 46 刪除策略 ? 如果在歸結(jié)時能把子句集中的無用子句刪除掉，這樣就會縮小尋找范圍，減少比較次數(shù)。 第四章 確定性推理 演繹推理 2/27/2023 48 重言式刪除法 ?如果一個子句中同時包含互補文字對，則稱該子句為重言式。即對一個不可滿足的子句集運用支持集策略進行歸結(jié)，最終總會導出空子句。 ? 事實是 有關(guān)問題狀態(tài)和環(huán)境的知識， ? 規(guī)則演繹的任務就是從給定的事實證明某個目標公式成立。 第四章 確定性推理 規(guī)則的 演繹推理 —— 逆向演繹 2/27/2023 67 化目標表達式為與或形 ? 消去蘊涵符號：