人工智能及其應(yīng)用課件.ppt

1 2 5消解原理2 6規(guī)則演繹系統(tǒng)2 7產(chǎn)生式系統(tǒng)2 8系統(tǒng)組織技術(shù)2 9小結(jié) 第2章知識(shí)表示與推理技術(shù) 2 推理的基本概念 推理是指按照某種策略從已知事實(shí)出發(fā)去推出結(jié)論的過程 其中 推理所用的事實(shí)可分為兩種 一種是與求解問題有關(guān)的初始證據(jù) 另一種是推理過程中所得到的中間結(jié)論 通常 智能系統(tǒng)的推理過程是通過推理機(jī)來完成的 所謂推理機(jī)就是智能系統(tǒng)用來實(shí)現(xiàn)推理的那些程序 例 在醫(yī)療診斷專家系統(tǒng)中 所有與診斷有關(guān)的醫(yī)療常識(shí)和專家經(jīng)驗(yàn)都被保存在知識(shí)庫中 當(dāng)系統(tǒng)開始診斷疾病時(shí) 首先把病人的癥狀和檢查結(jié)果放到事實(shí)庫中 然后再從事實(shí)庫中的這些初始證據(jù)出發(fā) 按照某種策略在知識(shí)庫中尋找可以匹配的知識(shí) 如果得到的是一些中間結(jié)論 則需要把它們作為已知事實(shí)放入事實(shí)庫中 并繼續(xù)尋找可以匹配的知識(shí) 如此反復(fù)進(jìn)行 直到推出最終結(jié)論為止 由初始事實(shí)出發(fā)到推出最終結(jié)論的過程就是推理 實(shí)現(xiàn)這一推理過程的程序稱為推理機(jī) 3 推理的基本概念 續(xù) 智能系統(tǒng)的推理包括兩個(gè)基本問題 一個(gè)是推理的方法 另一個(gè)是推理的控制策略 推理方法主要解決在推理過程中前提與結(jié)論之間的邏輯關(guān)系 以及在非精確性推理中不確定性的傳遞問題 4 推理的基本概念 續(xù) 1 按推理的邏輯基礎(chǔ)分類按照推理的邏輯基礎(chǔ) 常用的推理方法可分為演繹推理 歸納推理和默認(rèn)推理 1 演繹推理 演繹推理是從已知的一般性知識(shí)出發(fā) 去推出組合在這些已知知識(shí)中適合于某種個(gè)別情況的結(jié)論的過程 它是一種由一般到個(gè)別的推理方法 其核心是三段論 即假言推理 拒取式推理和假言三段論 常用的三段論是由一個(gè)大前提 一個(gè)小前提和一個(gè)結(jié)論三部分組成的 其中 大前提是由已知的一般性知識(shí)或推理過程得到的判斷 小前提是關(guān)于某種具體情況或某個(gè)具體實(shí)例的判斷 結(jié)論是由大前提推出的 并且適合于小前提的判斷 5 推理的基本概念 續(xù) 2 歸納推理歸納推理的前提是一些關(guān)于個(gè)別事物或現(xiàn)象的命題 而結(jié)論則是關(guān)于該類事物或現(xiàn)象的普遍性命題 歸納推理的結(jié)論所斷定的知識(shí)范圍超出了前提所斷定的知識(shí)范圍 因此 歸納推理的前提與結(jié)論之間的聯(lián)系不是必然性的 而是或然性的 也就是說 其前提真而結(jié)論假是可能的 所以 歸納推理是一種或然性推理 基本思想 先從已知事實(shí)中猜測(cè)出一個(gè)結(jié)論 然后對(duì)這個(gè)結(jié)論的正確性加以證明確認(rèn) 如果按照所選事例的廣泛性可分為完全歸納推理和不完全歸納推理 6 推理的基本概念 續(xù) 3 默認(rèn)推理 默認(rèn)推理是在知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理 因此也稱為缺省推理 在推理過程中 如果發(fā)現(xiàn)原先的假設(shè)不正確 就撤銷原來的假設(shè)以及由此假設(shè)所推出的所有結(jié)論 重新對(duì)新情況進(jìn)行推理 由于默認(rèn)推理容許在推理過程中假設(shè)某些條件是成立的 這就解決了在一個(gè)不完備的知識(shí)集中進(jìn)行推理的問題 7 推理的基本概念 續(xù) 2 按照所用知識(shí)的確定性分類確定性推理和不確定性推理3 按推理過程的單調(diào)性分類按照推理過程的單調(diào)性 或者說按照推理過程所得到的結(jié)論是否越來越接近目標(biāo) 推理可分為單調(diào)推理與非單調(diào)推理兩類 4 按照方法論分類按照方法論 常見的推理有基于知識(shí)的推理 統(tǒng)計(jì)推理和直覺推理等 基于知識(shí)的推理 是指根據(jù)已掌握的事實(shí) 通過運(yùn)用知識(shí)進(jìn)行的推理 例如 醫(yī)生診斷疾病時(shí) 根據(jù)病人癥狀及檢驗(yàn)結(jié)果 運(yùn)用醫(yī)學(xué)知識(shí)進(jìn)行推理 給出診斷結(jié)論及治療方案 統(tǒng)計(jì)推理 是指根據(jù)對(duì)某事物的數(shù)據(jù)統(tǒng)計(jì)進(jìn)行的推理 例如 農(nóng)民根據(jù)對(duì)農(nóng)作物產(chǎn)量統(tǒng)計(jì)得出是否增產(chǎn)的結(jié)論 從而找出增產(chǎn)或者減產(chǎn)的原因 直覺推理又稱為常識(shí)性推理 是指根據(jù)常識(shí)進(jìn)行的推理 例如 當(dāng)你猛然發(fā)現(xiàn)頭上有一物體掉落時(shí) 立即會(huì)意識(shí)到危險(xiǎn) 并立即躲開 這就是直覺推理 8 推理的基本概念 續(xù) 推理的控制策略智能系統(tǒng)的推理過程相當(dāng)于人類的思維過程 即求解問題的過程 問題求解的質(zhì)量與效率不僅依賴于所采用的求解方法 而且還依賴于求解問題的策略 即推理的控制策略 推理的控制策略是指如何使用領(lǐng)域知識(shí)使推理過程盡快達(dá)到目標(biāo)的策略 由于智能系統(tǒng)的推理過程一般表現(xiàn)為一種搜索過程 因此 推理的控制策略又可分為推理策略和搜索策略 其中 推理策略主要解決推理方向 沖突消解等問題 如推理方向控制策略 求解策略 限制策略 沖突消解策略等 9 推理的基本概念 續(xù) 推理方向用來確定推理的控制方式 即用來確定推理過程是從初始證據(jù)開始到目標(biāo) 還是從目標(biāo)開始到初始證據(jù) 按照對(duì)推理方向的控制 推理可分為正向推理 逆向推理 混合推理及雙向推理等4種 求解策略是指僅求一個(gè)解 還是求所有解或最優(yōu)解等 限制策略是指為了防止無窮的推理 以及推理過程太長(zhǎng)而對(duì)推理的深度 寬度 時(shí)間 空間等進(jìn)行限制的策略 沖突消解策略是指當(dāng)推理過程有多條知識(shí)可用時(shí) 如何從這多條可用知識(shí)中選出一條最佳知識(shí)用于推理的策略 目前已有多種消解沖突的策略 其基本思想都是對(duì)知識(shí)進(jìn)行排序 比如 按針對(duì)性排序 按已知事實(shí)的更新程度排序 按匹配程度排序 按產(chǎn)生知識(shí)冗余大小排序 按產(chǎn)生結(jié)論的條件個(gè)數(shù)排序等 10 3 5消解原理 3 5 1子句集的求取3 5 2消解推理規(guī)則3 5 3含有變量的消解式3 5 4消解反演求解過程 11 2 5消解原理 續(xù) 知識(shí)表示方式 謂詞公式解決問題 定理的自動(dòng)證明問題的自動(dòng)求解消解原理由Robinson于1965年提出 又稱為歸結(jié)原理 將要證明的前提及結(jié)論合并在一起 化為子句集 利用消解原理對(duì)子句集進(jìn)行消解 如果得到空子句則成立 否則失敗 例 如果存在某個(gè)公理E1 E2和另一公理 E2 E3 那么E1 E3在邏輯上成立 這就是消解 而稱E1 E3為E1 E2和 E2 E3的消解式 resolvent 12 2 5 1子句集的求取 相關(guān)概念文字 原子謂詞公式及其否定統(tǒng)稱為文字 子句 任何文字的析取式稱為子句 空子句 不包含任何文字的子句稱為空子句 記為 或NIL子句集 由子句和空子句所構(gòu)成的集合稱為子句集例 P x y Q x y P x y U x V y Q x y U y 在謂詞邏輯中 任一謂詞演算公式可以化成一個(gè)子句集 13 2 5 1子句集的求取 續(xù) 子句集的化簡(jiǎn)步驟 例 z x y P x Q x R y U z 1 利用等價(jià)關(guān)系消去蘊(yùn)涵和雙條件符 或 P Q P Q P Q P Q Q P 對(duì)于本例有 P x Q x R y P x Q x R y z x y P x Q x R y U z 14 2 5 1子句集的求取 續(xù) 2 減小否定符號(hào)的轄域使得否定符只作用于謂詞符號(hào) 原子公式 狄 摩根定律和量詞轉(zhuǎn)換率 P Q P Q P Q P Q x P x P x P x P對(duì)于本例有 z x y P x Q x R y U z 15 2 5 1子句集的求取 續(xù) 3 對(duì)變量標(biāo)準(zhǔn)化 變?cè)獡Q名 在任一量詞轄域內(nèi) 受該量詞約束的變量為一啞元 虛構(gòu)變量 它可以在該轄域內(nèi)處處統(tǒng)一地被另一個(gè)沒有出現(xiàn)過的任意變量所代替 而不改變公式的真值 合式公式中變量的標(biāo)準(zhǔn)化 意味著對(duì)啞元改名以保證每個(gè)量詞有其自己唯一的啞元 x P x y P y x P x y P y 例 x A x x B x 化為 x A x y B y 16 2 5 1子句集的求取 續(xù) 4 消去存在量詞 skolem化 Skolem函數(shù) 在公式 y x P x y 中 存在量詞是在全稱量詞的轄域內(nèi) 我們?cè)试S所存在的x可能依賴于y值 令這種依賴關(guān)系明顯地由函數(shù)g y 所定義 它把每個(gè)y值映射到存在的那個(gè)x 這種函數(shù)叫做Skolem函數(shù) 如果用Skolem函數(shù)代替存在的x 我們就可以消去全部存在量詞 并寫成 y P g y y 不在任何全稱量詞轄域內(nèi)的存在量詞約束的變?cè)镁唧w沒有出現(xiàn)過的常量代替 x P x 化為P A 在全稱量詞轄域內(nèi)的存在量詞約束的變?cè)眯碌膕kolem函數(shù)符號(hào)代替 z x y P x Q x R y U z 化為 x P x Q x R g x U a 17 2 5 1子句集的求取 續(xù) 5 化為前束范式 量詞左移 到這一步 已不留下任何存在量詞 而且每個(gè)全稱量詞都有自己的變量 把所有全稱量詞移到公式的左邊 并使每個(gè)量詞的轄域包括這個(gè)量詞后面公式的整個(gè)部分 所得公式稱為前束形 前束形公式由前綴和母式組成 前綴由全稱量詞串組成 母式由沒有量詞的公式組成 即前束形 前綴 母式 全稱量詞串無量詞公式 18 2 5 1子句集的求取 續(xù) 6 化為合取范式 Skolem標(biāo)準(zhǔn)形 合取范式 謂詞公式或謂詞公式的否定的析取的有限集合組成的合取 叫做合取范式 結(jié)合律 分配率 P Q R P Q R P Q R P Q R P Q R P Q P R P Q R P Q P R 對(duì)于本例有 x P x Q x R g x U a 化為 x P x Q x R g x U a 結(jié)合律化為 x P x R g x U a Q x R g x U a 19 2 5 1子句集的求取 續(xù) 7 消去全稱量詞 每個(gè)全稱量詞的轄域都是整個(gè)公式 P x R f x U a Q x R f x U a 8 消去連詞符號(hào) 表示為子句集 方法 用 A B 代替 A B 對(duì)于本例有 P x R f x U a Q x R f x U a 20 2 5 1子句集的求取 續(xù) 9 更換變量名稱使任意兩個(gè)子句不出現(xiàn)同名的變量 對(duì)于本例有 P x R f x U a Q y R f y U a 21 2 5 1子句集的求取 續(xù) 例 x P x y P y P f x y y Q x y P y 1 消去蘊(yùn)含符號(hào) x P x y P y P f x y y Q x y P y 2 減否定符號(hào)轄域 x P x y P y P f x y y Q x y P y 3 對(duì)變量標(biāo)準(zhǔn)化 x P x y P y P f x y q Q x q P q 4 消去存在變量 Skolem函數(shù) q W x x P x y P y P f x y Q x W x P W x 5 化為前束形 x y P x P y P f x y Q x W x P W x 6 化為合取范式 x y P x P y P f x y P x Q x W x P x P W x 22 2 5 1子句集的求取 續(xù) 7 消去全稱變量 P x P y P f x y P x Q x W x P x P W x 8 消去合取符 P x P y P f x y P x Q x W x P x P W x 9 更換變量名 P x P y P f x y P x1 Q x1 W x1 P x2 P W x2 23 2 5 1子句集的求取 續(xù) 經(jīng)上述步驟化簡(jiǎn)得到的標(biāo)準(zhǔn)式是經(jīng)過Skolem化的前束范式 通常也稱為S 標(biāo)準(zhǔn)形 要注意S 標(biāo)準(zhǔn)形不是唯一的 若把它記為Fs 則Fs僅僅是F 未Skolem化的前束式 的一個(gè)特例 取用不同的Skolem函數(shù)會(huì)得到不同的結(jié)果 當(dāng)F為非永假公式時(shí) Fs與F并不等價(jià) 但當(dāng)F為永假時(shí) Fs也一定是永假的 即Skolem化并不影響F的永假特性 這個(gè)結(jié)論很重要 可用定理形式描述如下 定理 若S是合式公式F的S 標(biāo)準(zhǔn)形之子句集 則F為永假的充要條件是S為不可滿足的 子句集中所有元素 即子句 的合取式不為真 則稱該子句集為不可滿足的 謂詞演算體系中還有一些很重要的概念 如謂詞演算的可判定性問題 邏輯推論 推理規(guī)則的有效性 推理規(guī)則系統(tǒng)的完備性等等 對(duì)人工智能推理機(jī)制的研究都很有用 24 2 5 2消解推理規(guī)則 消解式 設(shè)C1 L1 和C2 L2 是兩個(gè)沒有公共變?cè)淖泳?L1和L2分別是原子公式 具有相同的謂詞符號(hào) 但一般具有不同的變量 如果L1和L2存在最一般合一者 那么消解C1和C2推導(dǎo)出一個(gè)新子句 稱為C1和C2的消解式 它是由取這兩個(gè)子句的析取 然后消去互補(bǔ)對(duì)而得到的 25 2 5 2消解推理規(guī)則 續(xù) a 假言推理P P Q 即P Q 消解式Qb 合并P Q P Q消解式Q Q Qc 重言式P Q P Q消解式Q Q或P Pd 空子句 PP消解式NILe 鏈?zhǔn)?三段論 P Q 即P Q Q R 即Q R 消解式 P R 即P R 26 2 5 3含有變量的消解式 對(duì)于含有變量的子句 如果謂詞符號(hào)相同 而變量名不同 則需要找一個(gè)置換作用于父輩子句 使其含有互補(bǔ)文字 再進(jìn)行消解 例1 B x B x C x 消解式C x 例2 P x Q x Q f y 置換 f y x 消解式P f y 例3 P x f y Q x R f a y P f f a z R z w 置換 f f a x f y z 消解式 Q f f a R f a y R f y w 27 2 5 4消解反演求解過程 基本思想 反證法 在反證法中首先假定要證明的結(jié)論不成立 然后通過推導(dǎo)出存在矛盾的方法 反證出結(jié)論成立 在歸結(jié)法中首先對(duì)結(jié)論求反 然后將已知條件和結(jié)論的否定合在一起用子句集表達(dá) 如果該子句集存在矛盾 則證明了結(jié)論的正確性 思路 設(shè)S是已知條件和結(jié)論的否定合并后所對(duì)應(yīng)的子句集 假定有一種變換方法 可以對(duì)S實(shí)施一系列的變換 而且該變換能夠保證變換前后的子句集 在不可滿足的意義下是等價(jià)的 這樣 如果最終得到的子句集是不可滿足的 就證明了子句集S是不可滿足的 從而證明結(jié)論成立 由前面謂詞公式轉(zhuǎn)化為子句集的過程可知 子句集中的子句是 與 的關(guān)系 如果在子句集中出現(xiàn)了空子句 則說明該子句集是不可滿足的 因此 歸結(jié)過程就是 尋找 空子句的過程 如果把這一過程看作是搜索的話 初始狀態(tài)就是已知條件和結(jié)論的否定對(duì)應(yīng)的子句集 而目標(biāo)就是空子句 規(guī)則就是歸結(jié) 28 2 5 4消解反演求解過程 1 消解反演已知一個(gè)公式集S和目標(biāo)公式L 通過反證或反演來求證目標(biāo)公式L 證明步驟如下 否定L 得到 L 把 L添加到S中去 把新產(chǎn)生的集合 L S 化成子句集 應(yīng)用消解原理 力圖推導(dǎo)出一個(gè)表示矛盾的空子句 29 2 5 4消解反演求解過程 續(xù) 反演求解的正確性設(shè)公式L在邏輯上遵循公式集S 那么按照定義滿足S的每個(gè)解釋也滿足L 決不會(huì)有滿足S的解釋能夠滿足 L的 所以不存在能夠滿足并集S L 的解釋 如果一個(gè)公式集不能被任一解釋所滿足 那么這個(gè)公式是不可滿足的 因此 如果L在邏輯上遵循S 那么S L 是不可滿足的 可以證明 如果消解反演反復(fù)應(yīng)用到不可滿足的子句集 那么最終將要產(chǎn)生空子句NIL 因此 如果L在邏輯上遵循S 那么由并集S L 消解得到的子句 最后將產(chǎn)生空子句 反之 可以證明 如果從S L 的子句消解得到空子句 那么L在邏輯上遵循S 30 2 5 4消解反演求解過程 續(xù) 例 已知 每個(gè)儲(chǔ)蓄錢的人都獲得利息結(jié)論 如果沒有利息 那么就沒有人去儲(chǔ)蓄錢 證明 定義謂詞 S x y 表示 x儲(chǔ)蓄y M x 表示 x是錢 I x 表示 x是利息 E x y 表示 x獲得y 已知 x y S x y M y y I y E x y 結(jié)論 x I x x y M y S x y 31 2 5 4消解反演求解過程 續(xù) 1 否定結(jié)論 x I x x y M y S x y 2 把結(jié)論加入已知 構(gòu)成新集合G x y S x y M y y I y E x y x I x x y M y S x y 3 將集合G化為子句集 y f x 為Skolem函數(shù) 1 S x y M y I f x 2 S x y M y E x f x 3 I z 4 S a b 5 M b 32 2 5 4消解反演求解過程 續(xù) 4 應(yīng)用消解原理進(jìn)行推導(dǎo) 1 S x y M y I f x 2 S x y M y E x f x 3 I z 4 S a b 5 M b 6 S x y M y 1 和 3 消解 f x z 7 M b 6 和 4 消解 a x b y 8 NIL 5 和 7 消解 33 2 5 4消解反演求解過程 續(xù) 消解反演可以表示為一棵反演樹 34 2 5 4消解反演求解過程 續(xù) 歸結(jié)方法很簡(jiǎn)單 但是即便是對(duì)于一個(gè)比較簡(jiǎn)單的問題 往往可以進(jìn)行歸結(jié)的子句也比較多 如何從眾多的可歸結(jié)的子句中選擇兩個(gè)子句 即為搜索策略問題 不同的搜索策略 會(huì)影響到系統(tǒng)的效率和開銷 同時(shí)也會(huì)涉及到完備性問題 搜索策略的目標(biāo)就是要找到一棵歸結(jié)反演樹 一個(gè)反演系統(tǒng)當(dāng)存在一個(gè)矛盾時(shí) 如果使用的一種策略 最終都將找到一棵反演樹 即能找到矛盾 則這種策略是完備的 在實(shí)際應(yīng)用中 有些策略雖不完備 但具有極高的效率 也是可取的 提高策略效率的一些作法是 只歸結(jié)含有互補(bǔ)對(duì)的文字 及時(shí)刪去出現(xiàn)的重言式和被其他子句所包含的子句 每次歸結(jié)都取與目標(biāo)公式否定式有關(guān)的子句作為母子句之一進(jìn)行歸結(jié)等等 35 2 5 4消解反演求解過程 續(xù) 2 反演求解過程問題的求解利用消解反演除了可以實(shí)現(xiàn)定理的自動(dòng)證明之外 也可以對(duì)簡(jiǎn)單問題進(jìn)行求解 例 張和李是同班同學(xué) 如果x和y是同班同學(xué) 則x的教室也是y的教室 現(xiàn)在張?jiān)?02教室上課 問現(xiàn)在李在哪里上課 36 2 5 4消解反演求解過程 續(xù) 從反演樹求問題答案的過程 1 把問題的已知條件用謂詞公式表示出來 并化為相應(yīng)的子句集 2 把問題的目標(biāo)的否定用謂詞公式表示出來 并化為子句集 3 對(duì)目標(biāo)否定子句集中的每個(gè)子句 構(gòu)造該子句的重言式 即把該目標(biāo)否子句和此目標(biāo)否定子句的否定之間再進(jìn)行析取所得到的子句 用這些重言式代替相應(yīng)的目標(biāo)否定子句 并把這些重言式加入到前提子句集中 得到一個(gè)新的子句集 37 2 5 4消解反演求解過程 續(xù) 4 對(duì)這個(gè)新的子句集 應(yīng)用消解原理求出其反演證明樹 這時(shí)證明樹的根子句不為空 稱這個(gè)證明樹為修改證明樹 5 用修改證明樹的根子句作為回答語句 則答案就在此根子句中 38 2 5 4消解反演求解過程 續(xù) 例 如果無論約翰 JOHN 到哪里去 菲多 FIDO 也就去那里 那么如果約翰在學(xué)校里 菲多在哪里呢 解 定義謂詞 AT x y 表示x在y處1 已知的謂詞表示 x AT JOHN x AT FIDO x AT JOHN SCHOOL 化為子句集 AT JOHN y AT FIDO y AT JOHN SCHOOL 39 2 5 4消解反演求解過程 續(xù) 2 目標(biāo)否定的謂詞表示 x AT FIDO x x AT FIDO x 化為子句集 AT FIDO x 3 構(gòu)造目標(biāo)否定子句的重言式 并代替原子句 AT FIDO x AT FIDO x 4 將3得到的子句集加入前提子句集中 G AT JOHN y AT FIDO y AT JOHN SCHOOL AT FIDO x AT FIDO x 40 2 5 4消解反演求解過程 續(xù) 5 對(duì)新子句集G應(yīng)用消解原理求出反演樹 G AT JOHN y AT FIDO y AT JOHN SCHOOL AT FIDO x AT FIDO x 41 2 5 4消解反演求解過程 續(xù) 例 張某被盜 公安局派出五個(gè)偵察員去調(diào)查 研究案情時(shí) 偵察員A說 趙與錢中至少有一人作案 偵察員B說 錢與孫中至少有一人作案 偵察員C說 孫與李中至少有一人作案 偵察員D說 趙與孫中至少有一人與此案無關(guān) 偵察員E說 錢與李中至少有一人與此案無關(guān) 如果這五個(gè)偵察員的話都是可信的 試用消解反演推理求出誰是盜竊犯 定義謂詞 P x x作案 42 2 5 4消解反演求解過程 續(xù) 由五個(gè)偵察員的話為真 有P z P q 1 P q P s 2 P s P l 3 P z P s 4 P q P l 5 把結(jié)論的否定加入結(jié)論的否定的否定的子句中去 得 P x vP x 6 因?yàn)檫@些全都是子句 所以化為子句集的步驟可以省略了 1 4 歸結(jié)得 P q P s 7 2 7 歸結(jié)得 p q 8 即 錢是盜竊犯 43 2 5 5含狀態(tài)項(xiàng)的回答語句的求取 猴子和香蕉問題 44 2 5 5含狀態(tài)項(xiàng)的回答語句的求取 ONBOX S0 AT box b S0 AT monkey a S0 HB S0 pushbox x S 在狀態(tài)S下 猴子把箱子推到水平位置xclimbbox S 在狀態(tài)S下 猴子爬上箱頂grasp S 在狀態(tài)S下 猴子摘到香蕉 45 2 5 5含狀態(tài)項(xiàng)的回答語句的求取 x S ONBOX S AT box x pushbox x S S ONBOX climbbox S S ONBOX S AT box c S HB grasp S x S AT box x S AT box x climbbox S ONBOX S0 S HB S 要證的結(jié)論 46 2 5 5含狀態(tài)項(xiàng)的回答語句的求取 ONBOX S AT box x pushbox x S ONBOX climbbox S ONBOX S AT box c S HB grasp S AT box x S AT box x climbbox S ONBOX S0 目標(biāo)的非 HB S 47 2 5 5含狀態(tài)項(xiàng)的回答語句的求取 ONBOX S1 AT box x pushbox x S1 ONBOX climbbox S2 ONBOX S3 AT box c S3 HB grasp S3 AT box x S4 AT box x climbbox S4 ONBOX S0 目標(biāo)的非 HB S5 48 HB S5 ONBOX S3 AT box c S3 HB grasp S3 ONBOX S3 AT box c S3 grasp S3 S5 ONBOX climbbox S2 climbbox S2 S3 AT box c climbbox S2 AT box x S4 AT box x climbbox S4 S4 S2 c x ONBOX S0 AT box c S4 ONBOX S1 AT box x pushbox x S1 pushbox x S1 S4 c x ONBOX S1 S0 S1 NIL 49 2 6規(guī)則演繹系統(tǒng) 消解反演的局限 實(shí)際應(yīng)用中 很多的事實(shí)更直觀地表現(xiàn)為若干的規(guī)則If Then 如果那么 其中If部分稱為前項(xiàng) Then部分稱為后項(xiàng) 其中 If部分可能由幾個(gè)if組成 而Then部分可能由一個(gè)或一個(gè)以上的then組成例 表示為蘊(yùn)含式 A B C A C B A B C B A C都與子句 A B C等價(jià)一些重要信息在求取子句集過程中丟失 問題描述方式不自然 50 2 6規(guī)則演繹系統(tǒng) 續(xù) 規(guī)則演繹系統(tǒng) 基于規(guī)則求解問題的系統(tǒng)叫做規(guī)則演繹系統(tǒng) 兩種推理方向 正向推理 從if部分向then部分推理的過程 叫做正向推理 逆向推理 從then部分向if部分推理的過程 叫做逆向推理 按推理方向分類 規(guī)則正向演繹系統(tǒng) 從事實(shí)出發(fā)利用規(guī)則推導(dǎo)出結(jié)論 規(guī)則逆向演繹系統(tǒng) 從目標(biāo)出發(fā)利用規(guī)則推導(dǎo)出事實(shí) 規(guī)則雙向演繹系統(tǒng) 51 2 6 1規(guī)則正向演繹系統(tǒng) 規(guī)則正向演繹系統(tǒng) 是從已知事實(shí)出發(fā) 正向使用規(guī)則對(duì)事實(shí)表達(dá)式的與或樹進(jìn)行變換 直到找到一個(gè)含有目標(biāo)節(jié)點(diǎn)的一致解樹為止 已知事實(shí) 事實(shí)表達(dá)式的與或樹目標(biāo)表達(dá)式 限制為文字的析取式F規(guī)則 L W 其中L為單文字 W為與或形 結(jié)束條件 目標(biāo)表達(dá)式是析取式 得到結(jié)束于目標(biāo)節(jié)點(diǎn)的一致解樹 52 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 1 事實(shí)表達(dá)式的與或形變換2 事實(shí)表達(dá)式的與或樹表示3 與或圖的F規(guī)則變換4 目標(biāo)公式的表示形式5 規(guī)則正向演繹推理過程 53 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 1 事實(shí)表達(dá)式的與或形變換規(guī)則正向演繹系統(tǒng)中要求事實(shí)表達(dá)式化簡(jiǎn)為與或形 1 消去 蘊(yùn)含 和 雙條件 符號(hào) 2 減小否定符號(hào)的轄域 使否定符號(hào)只作用于原子公式 3 利用Skolem函數(shù)消去存在量詞 4 對(duì)變量進(jìn)行換名 使得不同的主要合取式中 具有不同的變量名 5 隱去全稱量詞 默認(rèn)公式中的變量受全稱量詞約束 54 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 例 x y Q y x R y P y S x y 消去量詞化為 Q y a R y P y S a y 再變量更名化為 Q z a R y P y S a y 55 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 2 事實(shí)表達(dá)式的與或樹 圖 表示子表達(dá)式間的與 或關(guān)系規(guī)定如下 當(dāng)母表達(dá)式為E1 E2 E3 Ek時(shí) 則每一個(gè)子表達(dá)式Ei被表示成一個(gè)后繼節(jié)點(diǎn) 并由一個(gè)k 連接符來連接 當(dāng)母表達(dá)式為E1 E2 E3 Ek時(shí) 則每一個(gè)子表達(dá)式Ei均由1 連接符連接 56 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) Q z a R y P y S a y 事實(shí)表達(dá)的與或樹表達(dá)式 57 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 與或樹所有結(jié)束于葉節(jié)點(diǎn)的解樹的求法從根節(jié)點(diǎn) 初始結(jié)點(diǎn) 開始 正確選擇一個(gè)外向連接符 再從該連接符所指的每一個(gè)后繼節(jié)點(diǎn)出發(fā) 繼續(xù)選一個(gè)外向連接符 如此進(jìn)行下去直到結(jié)束在葉結(jié)點(diǎn)上為止 例 求上例中的事實(shí)表達(dá)式的與或樹的解樹 58 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 59 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 與或樹的性質(zhì) 事實(shí)表達(dá)式的子句集與事實(shí)表達(dá)式的與或樹解樹集是一一對(duì)應(yīng)的關(guān)系 事實(shí)表達(dá)式的與或樹解樹集中的每個(gè)解樹都對(duì)應(yīng)著子句集中的一個(gè)子句 解樹集中每個(gè)解樹的葉節(jié)點(diǎn)上的文字的析取就是子句集中的一個(gè)子句 例 Q z a R y P y S a y 化為子句集 Q z a R y S a y P y S a y 60 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 3 與或圖的F規(guī)則變換規(guī)則是建立在某個(gè)問題轄域中普通陳述性知識(shí)的蘊(yùn)涵公式基礎(chǔ)上的 把允許用作規(guī)則的公式類型限制為下列形式 F規(guī)則 L W其中 L為單文字 W為與或形唯一公式 假設(shè)出現(xiàn)在蘊(yùn)涵式中的任何變量都有全稱量化作用于整個(gè)蘊(yùn)涵式 這些事實(shí)和規(guī)則中的一些變量被分離標(biāo)準(zhǔn)化 使得沒有一個(gè)變量出現(xiàn)在一個(gè)以上的規(guī)則中 而且使規(guī)則變量不同于事實(shí)變量 單文字前項(xiàng)的任何蘊(yùn)涵式 不管其量化情況如何都可以化為某種量化轄域?yàn)檎麄€(gè)蘊(yùn)涵式的形式 61 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) F規(guī)則的化簡(jiǎn)例 x y z P x y z u Q x u 1 暫時(shí)消去蘊(yùn)涵符號(hào) x y z P x y z u Q x u 2 減少否定符號(hào)的轄域 使僅作用于文字 x y z P x y z u Q x u 3 消去存在量詞Skolem化 x y P x y f x y u Q x u 4 化成前束式并消去全稱量詞 P x y f x y Q x u 5 恢復(fù)蘊(yùn)涵式表示 化簡(jiǎn)為 P x y f x y Q x u 62 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 對(duì)規(guī)則作單文字前項(xiàng)的限制將大大簡(jiǎn)化了應(yīng)用時(shí)的匹配過程 對(duì)非單文字前項(xiàng)的情況 L1 L2 W轉(zhuǎn)換成 L1 W L2 W4 目標(biāo)公式的表示形式目標(biāo)公式要求 子句形即文字的析取式子句形的化簡(jiǎn)步驟 消去蘊(yùn)涵符 減小否定符號(hào)的轄域 對(duì)變?cè)獦?biāo)準(zhǔn)化 變?cè)獡Q名 化為前束范式 量詞左移 消去全稱量詞 對(duì)偶形式的skolem化 進(jìn)行變?cè)獡Q名 使不同的主析取元具有不同的變?cè)?消去存在量詞 變量都受存在量詞的約束 63 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 例 y x P x y Q x y 用Skolem函數(shù)消去全稱量詞有 y P f y y Q f y y 進(jìn)行變量更名有 y P f y y z Q f z z 消去存在量詞 P f y y Q f z z 64 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 5 規(guī)則正向演繹推理過程 規(guī)則正向演繹推理過程 就是不斷的對(duì)事實(shí)表達(dá)式的與或樹施以F規(guī)則變換 直到找到一個(gè)一致解樹 該解樹中的所有葉節(jié)點(diǎn)全部都與目標(biāo)公式中的文字匹配為止 如何進(jìn)行F規(guī)則變換 如何判斷終止 65 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 命題邏輯的規(guī)則正向演繹過程 F規(guī)則變換 如果在與或樹中有一個(gè)葉節(jié)點(diǎn)剛好與某F規(guī)則L W的前件L匹配 則將該葉節(jié)點(diǎn)與L用一個(gè)匹配弧連接起來 將規(guī)則后件W添加到與或樹中 這樣 就對(duì)與或樹用規(guī)則L W實(shí)施了一次變換 得到了一個(gè) 更新 了的與或樹 例 事實(shí)表達(dá)式的與或形為 P Q R S T U 規(guī)則 S X Y Z 66 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 應(yīng)用F規(guī)則得到的新與或樹 67 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 與或樹的變換與子句集的消解分析 事實(shí)表達(dá)式的子句集 S P Q S R T U P Q T U R 規(guī)則S X Y Z對(duì)應(yīng)的子句集 S X Z S Y Z 規(guī)則變換 新與或樹對(duì)應(yīng)的子句集 T U P Q T U R X Z P Q X Z R Y Z P Q Y Z R 68 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 消解 將事實(shí)表達(dá)式和規(guī)則子句集合并 S P Q S R T U P Q T U R S X Z S Y Z 作如下消解 S P Q S X Z X Z P Q S P Q S Y Z Y Z P Q S R S X Z X Z RS R S Y Z Y Z R得新的子句集 T U P Q T U R X Z P Q X Z R Y Z P Q Y Z R 69 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 結(jié)論 與或樹的規(guī)則變換與消解之間具有一定的聯(lián)系 應(yīng)用一條規(guī)則到與或樹的過程 以極其經(jīng)濟(jì)方式的達(dá)到了用其它方法要進(jìn)行的多次消解才能達(dá)到的目的 70 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 命題邏輯的規(guī)則演繹過程例 事實(shí)表達(dá)式 A B規(guī)則集 A C DB E G目標(biāo)公式 C G 71 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 謂詞邏輯的規(guī)則正向演繹過程a 事實(shí)表達(dá)式進(jìn)行與或樹表示 b 規(guī)則轉(zhuǎn)換成F規(guī)則L W 其中L為單文字 W為與或形 c 目標(biāo)表達(dá)式變換成子句形 d 對(duì)與或樹進(jìn)行F規(guī)則變換 e 結(jié)束條件 找到所有葉節(jié)點(diǎn)都與目標(biāo)節(jié)點(diǎn)匹配的一致解樹 72 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) F規(guī)則變換 設(shè)與或樹中有一個(gè)端節(jié)點(diǎn)的文字L 和L可合一 mgu是u 則這條規(guī)則可應(yīng)用 這時(shí)用匹配弧連接的后裔節(jié)點(diǎn)是L 它是規(guī)則后項(xiàng)Wu對(duì)應(yīng)的與或樹表示的根節(jié)點(diǎn) 在匹配弧上標(biāo)記有u 表示用u置換后可與規(guī)則匹配 73 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 例 事實(shí)與或形表示 P A y Q x A R B y 規(guī)則蘊(yùn)涵式 P z B S z X B 應(yīng)用一條規(guī)則的新與或樹 74 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 上圖應(yīng)用規(guī)則變換后得到的與或樹有兩個(gè)解樹 對(duì)應(yīng)的兩個(gè)子句是S A X B Q x A S A X B R B B 事實(shí)和規(guī)則組成的子句集 對(duì)文字P進(jìn)行歸結(jié) P A y Q x A P A y R B y P z B S z X B R B B S A X B 歸結(jié) A z B y Q x A S A X B 歸結(jié) A z B y 結(jié)論 規(guī)則的應(yīng)用結(jié)果是得到這條規(guī)則的應(yīng)用演繹出所有的邏輯推論 75 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 一致解樹一個(gè)具有一致置換的解樹稱為一致解樹 一致置換 當(dāng)置換集沒有矛盾存在時(shí) 稱該置換集是一致的 否則就是不一致的 例 1 a x b y 和 2 b x c z 例 設(shè)已知事實(shí)的與或形表示為 P x y Q x R v y F規(guī)則為 P u v S u N v 目標(biāo)公式為 S a N b Q c 76 2 6 1規(guī)則正向演繹系統(tǒng) 續(xù) 謂詞邏輯的規(guī)則演繹過程 77 2 6 2規(guī)則逆向演繹系統(tǒng) 規(guī)則逆向演繹推理 從目標(biāo)表達(dá)式出發(fā) 反方向使用規(guī)則 B規(guī)則 對(duì)表示目標(biāo)的與或樹進(jìn)行變換 直到得到含有事實(shí)節(jié)點(diǎn)的一致解樹 目標(biāo)表達(dá)式 目標(biāo)的與或樹事實(shí)表達(dá)式 限制為文字的合取形 規(guī)則 B規(guī)則 W L其中 W是任意形式的與或形 L是單文字終止條件 得到含有事實(shí)節(jié)點(diǎn)的一致解樹 78 2 6 2規(guī)則逆向演繹系統(tǒng) 續(xù) 1 目標(biāo)表達(dá)式的與或形變換2 目標(biāo)公式的與或樹表示3 B規(guī)則的表示形式4 已知事實(shí)的表示形式5 規(guī)則逆向演繹推理過程 79 2 6 2規(guī)則逆向演繹系統(tǒng) 續(xù) 1 目標(biāo)表達(dá)式的與或形變換 1 消去 蘊(yùn)含 和 雙條件 符號(hào) 2 減小否定符號(hào)的轄域 使否定符號(hào)只作用于原子公式 3 利用Skolem函數(shù)消去全稱量詞 4 對(duì)變量進(jìn)行換名 使得不同的主合取元 具有不同的變量名 5 隱去存在量詞 默認(rèn)公式中的變量受存在量詞約束 例 y x P x Q x y R x S y P f z Q f y y R f y S y 80 2 6 2規(guī)則逆向演繹系統(tǒng) 續(xù) 2 目標(biāo)公式的與或樹表示規(guī)定子表達(dá)式間的析取用1 連接符連接 即表示為 或 的關(guān)系 而子表達(dá)式的合取用k 連接符連接 即表示為 與 的關(guān)系 目標(biāo)公式的與或樹表示 81 2 6 2規(guī)則逆向演繹系統(tǒng) 續(xù) 與或樹解樹對(duì)應(yīng)的子句 文字的合取 P f z Q f y y R f y Q f y y S y 目標(biāo)公式的析取范式中子句 P f z Q f y y R f y Q f y y S y 3 B規(guī)則的表示形式 B規(guī)則形式限制為 W L其中 W是任意形式的與或形 L是單文字 它表示L可以由W推導(dǎo)出 82 2 6 2規(guī)則逆向演繹系統(tǒng) 續(xù) B規(guī)則化簡(jiǎn) 其中的變量受全稱量詞約束 如果有存在量詞 則將其Skolem化 消去存在量詞 當(dāng)B規(guī)則為W L1 L2時(shí) 則可化簡(jiǎn)為兩條規(guī)則W L1和W L2來處理 4 已知事實(shí)的表示形式事實(shí)表達(dá)式均限制為文字合取形 它可以表示為一個(gè)文字集并且進(jìn)行了普通的Skolem化簡(jiǎn) 變量受全稱量詞約束 83 2 6 2規(guī)則逆向演繹系統(tǒng) 續(xù) 5 規(guī)則逆向演繹推理過程 就是不斷的對(duì)目標(biāo)公式的與或樹施以B規(guī)則變換 直到找到一個(gè)一致解樹 該解樹中的所有葉節(jié)點(diǎn)全部都與事實(shí)表達(dá)式中的文字匹配為止 B規(guī)則匹配和變換匹配 當(dāng)與或樹中有某個(gè)端點(diǎn)的文字和L可合一且mgu為u時(shí) 則B規(guī)則可應(yīng)用變換 求出該葉節(jié)點(diǎn)與L的mguu 將該葉節(jié)點(diǎn)與L用一個(gè)匹配弧連接起來 用u對(duì)W進(jìn)行置換 然后將Wu添加到與或樹中 成功終止條件 與或樹包含終止在事實(shí)節(jié)點(diǎn)上的一致解樹 84 2 6 2規(guī)則逆向演繹系統(tǒng) 續(xù) 例 設(shè)有如下事實(shí)和規(guī)則 事實(shí) F1 DOG FIDO 狗的名字叫FidoF2 BARKS FIDO Fido是不叫的F3 WAGS TAIL FIDO Fido搖尾巴F4 MEOWS MYRTLE 貓咪的名字叫Myrtle規(guī)則 R1 WAGS TAIL x1 DOG x1 FRIENDLY x1 搖尾巴的狗是溫順的狗R2 FRIENDLY x2 BARKS x2 AFRAID y2 x2 溫順而又不叫的東西是不值得害怕的R3 DOG x3 ANIMAL x3 狗為動(dòng)物R4 CAT x4 ANIMAL x4 貓為動(dòng)物R5 MEOWS x5 CAT x5 貓咪是貓問題 是否存在這樣的一只貓和一條狗 使得這只貓不怕這條狗 85 2 6 2規(guī)則逆向演繹系統(tǒng) 續(xù) 1 目標(biāo)表示為與或樹 目標(biāo)用謂詞公式表示 x y CAT x DOG y AFRAID x y 消去存在量詞化為與或形 CAT x DOG y AFRAID x y 目標(biāo)公式表示成與或樹2 規(guī)則符合B規(guī)則要求不需變換3 事實(shí)是文字的合取形 DOG FIDO BARKS FIDO WAGSTAIL FIDO MEOWS MYRTLE 4 規(guī)則逆向推理 分別應(yīng)用規(guī)則R5 R2 R1變換5 找到一致解樹 成功終止 86 規(guī)則逆向演繹推理過程例 87 2 6 2規(guī)則逆向演繹系統(tǒng) 續(xù) 一致解樹 圖 所有匹配弧上的置換集 x x5 MYRTLE x FIDO y x y2 y x2 FIDO y y x1 FIDO y FIDO y 沒有矛盾 是一致置換集 回答語句 CAT MYRTLE DOG FIDO AFRAID MYRTLE FIDO 88 89 2 6 3規(guī)則雙向演繹系統(tǒng) 正向演繹和逆向演繹推理的局限性 正向演繹推理要求 目標(biāo)公式必須可化簡(jiǎn)為文字的析取式 逆向演繹推理要求 事實(shí)表達(dá)式必須可化簡(jiǎn)為文字的合取式 限制了正向和逆向推理的應(yīng)用范圍 規(guī)則雙向演繹推理任意形式的事實(shí)表達(dá)式和目標(biāo)公式 同時(shí)采用規(guī)則正向和規(guī)則逆向推理 90 2 6 3規(guī)則雙向演繹系統(tǒng) 續(xù) 規(guī)則雙向演繹推理綜合數(shù)據(jù)庫 事實(shí)表達(dá)式的與或樹 簡(jiǎn)稱事實(shí)樹 和目標(biāo)公式的與或樹 簡(jiǎn)稱目標(biāo)樹 規(guī)則庫 F規(guī)則和B規(guī)則 規(guī)則雙向演繹推理 運(yùn)用F規(guī)則對(duì)事實(shí)樹進(jìn)行變換 運(yùn)用B規(guī)則對(duì)目標(biāo)樹進(jìn)行變換 終止條件 事實(shí)樹與目標(biāo)樹的某個(gè)交接處 缺點(diǎn) 判斷困難 較復(fù)雜 91 2 6 3規(guī)則雙向演繹系統(tǒng) 續(xù) 終止條件 若標(biāo)記于事實(shí)文字節(jié)點(diǎn)L1和目標(biāo)文字節(jié)點(diǎn)L2上的文字有mguu 則在L1和L2之間建立匹配棱線連接 并用對(duì)應(yīng)的mguu來標(biāo)記匹配棱線 對(duì)于初始綜合數(shù)據(jù)庫 事實(shí)樹和目標(biāo)樹間的匹配棱線必須在葉節(jié)點(diǎn)之間 當(dāng)用F規(guī)則和B規(guī)則對(duì)圖進(jìn)行擴(kuò)展之后 匹配就可以出現(xiàn)在任何文字節(jié)點(diǎn)上 例 設(shè)已知事實(shí)和目標(biāo)分別為 事實(shí) Q x a R x S a 目標(biāo) P f y Q f y y R f y S y 92 規(guī)則雙向推理過程例 93 2 6 3規(guī)則雙向演繹系統(tǒng) 續(xù) 終止條件 當(dāng)在事實(shí)樹與目標(biāo)樹之間建立了所有的可能匹配棱線之后 目標(biāo)樹中根節(jié)點(diǎn)上的表達(dá)式是否已經(jīng)根據(jù)事實(shí)樹中根節(jié)點(diǎn)上的表達(dá)式和規(guī)則得到證明的問題仍然需要判定 判斷方法 一個(gè)建立在事實(shí)節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)間一種叫做CANCEL的對(duì)稱關(guān)系的基礎(chǔ)上的判定方法 94 2 6 3規(guī)則雙向演繹系統(tǒng) 續(xù) CANCEL的遞歸定義 如果 n m 中有一個(gè)為事實(shí)節(jié)點(diǎn) 另一個(gè)為目標(biāo)節(jié)點(diǎn) 如果n和m都由可合一的文字所標(biāo)記 則稱這兩節(jié)點(diǎn)n和m互相CANCEL 即互相抵消 否則如果n有外向k線連接符接至一個(gè)后繼節(jié)點(diǎn)集 Si 且對(duì)此集的每個(gè)元素CANCEL Si m 都成立 那么也稱這兩節(jié)點(diǎn)n和m互相CANCEL 95 2 6 3規(guī)則雙向演繹系統(tǒng) 續(xù) 當(dāng)事實(shí)樹的根節(jié)點(diǎn)和目標(biāo)樹的根節(jié)點(diǎn)互相CANCEL時(shí) 我們得到一個(gè)候補(bǔ)解 在事實(shí)和目標(biāo)樹內(nèi)證明該目標(biāo)根節(jié)點(diǎn)和事實(shí)根節(jié)點(diǎn)互相CANCEL的圖結(jié)構(gòu)叫做候補(bǔ)CANCEL圖 如果候補(bǔ)CANCEL圖中所有匹配的mgu都是一致的 那么這個(gè)候補(bǔ)解就是一個(gè)實(shí)際解 找到實(shí)際解 推理成功 目標(biāo)得證 96 2 7產(chǎn)生式系統(tǒng) 2 7 1產(chǎn)生式系統(tǒng)的組成2 7 2產(chǎn)生式系統(tǒng)的推理2 7 3產(chǎn)生式系統(tǒng)的控制策略 97 產(chǎn)生式系統(tǒng) productionsystem 首先是由波斯特 Post 于1943年提出的產(chǎn)生式規(guī)則 productionrule 而得名的 他們用這種規(guī)則對(duì)符號(hào)串進(jìn)行置換運(yùn)算 后來 美國(guó)的紐厄爾和西蒙利用這個(gè)原理建立一個(gè)人類的認(rèn)知模型 1965年 同時(shí) 斯坦福大學(xué)利用產(chǎn)生式系統(tǒng)結(jié)構(gòu)設(shè)計(jì)出第一個(gè)專家系統(tǒng)DENDRAL 產(chǎn)生式系統(tǒng)用來描述若干個(gè)不同的以一個(gè)基本概念為基礎(chǔ)的系統(tǒng) 這個(gè)基本概念就是產(chǎn)生式規(guī)則或產(chǎn)生式條件和操作對(duì)的概念 在產(chǎn)生式系統(tǒng)中 論域的知識(shí)分為兩部分 用事實(shí)表示靜態(tài)知識(shí) 如事物 事件和它們之間的關(guān)系 用產(chǎn)生式規(guī)則表示推理過程和行為 由于這類系統(tǒng)的知識(shí)庫主要用于存儲(chǔ)規(guī)則 因此又把此類系統(tǒng)稱為基于規(guī)則的系統(tǒng) rulebasedsystem 98 2 7產(chǎn)生式系統(tǒng) 續(xù) 產(chǎn)生式系統(tǒng)中的知識(shí)表示1 事實(shí)的表示 確定性的知識(shí) 命題 謂詞 三元組 對(duì)象 屬性 值 或 關(guān)系 對(duì)象1 對(duì)象2 老李和老張是朋友 Friend Lee Chang 不確定性的知識(shí) 四元組 對(duì)象 屬性 值 可信度因子 極少數(shù)花的顏色是黑的 花 顏色 黑 0 1 99 2 7產(chǎn)生式系統(tǒng) 續(xù) 2 推理過程和行為 規(guī)則 的表示產(chǎn)生式或規(guī)則 P QIFPTHENQP是產(chǎn)生式的前提 或稱為前件 是一組結(jié)論或操作 或稱為后件IF 動(dòng)物 本領(lǐng) 會(huì)下蛋 AND 動(dòng)物 本領(lǐng) 會(huì)飛 THEN 動(dòng)物 類別 鳥 IF 病人 癥狀 咳嗽 AND 病人 癥狀 流涕 THEN 病人 疾病 感冒 0 85 100 2 7 1產(chǎn)生式系統(tǒng)的組成 1 綜合數(shù)據(jù)庫 全局?jǐn)?shù)據(jù)庫 事實(shí)數(shù)據(jù)庫2 產(chǎn)生式規(guī)則庫 產(chǎn)生式規(guī)則3 控制系統(tǒng) 控制策略 推理機(jī) 101 2 7 1產(chǎn)生式系統(tǒng)的組成 續(xù) 1 綜合數(shù)據(jù)庫是一個(gè)用來存放與求解問題有關(guān)的各種當(dāng)前信息的數(shù)據(jù)結(jié)構(gòu) 問題的初始狀態(tài) 事實(shí) 證據(jù) 中間推理結(jié)論及最后結(jié)果等 2 產(chǎn)生式規(guī)則庫是用來存放與求解問題有關(guān)的某個(gè)領(lǐng)域知識(shí)的規(guī)則的集合及其交換規(guī)則 這里所說的產(chǎn)生式規(guī)則和謂詞邏輯中所討論的產(chǎn)生式規(guī)則 從形式上看都采用了IF THEN的形式 但這里所討論的產(chǎn)生式更為通用 在謂詞運(yùn)算中的IF THEN實(shí)質(zhì)上是表示了蘊(yùn)涵關(guān)系 也就是說要滿足相應(yīng)的真值表 這里所討論的條件和操作部分除了可以用謂詞邏輯表示外 還可以有其他多種表示形式 并不受相應(yīng)的真值表的限制 102 2 7 1產(chǎn)生式系統(tǒng)的組成 續(xù) 3 控制系統(tǒng) 1 匹配在這一步 把當(dāng)前數(shù)據(jù)庫與規(guī)則的條件部分相匹配 如果兩者完全匹配 則把這條規(guī)則稱為觸發(fā)規(guī)則 當(dāng)按規(guī)則的操作部分去執(zhí)行時(shí) 稱這條規(guī)則為啟用規(guī)則 被觸發(fā)的規(guī)則不一定總是啟用規(guī)則 因?yàn)榭赡芡瑫r(shí)有幾條規(guī)則的條件部分被滿足 這就要在解決沖突步驟中來解決這個(gè)問題 在復(fù)雜的情況下 在數(shù)據(jù)庫和規(guī)則的條件部分之間可能要進(jìn)行近似匹配 103 2 7 1產(chǎn)生式系統(tǒng)的組成 續(xù) 2 沖突解決當(dāng)有一條以上規(guī)則的條件部分和當(dāng)前數(shù)據(jù)庫相匹配時(shí) 就需要決定首先使用哪一條規(guī)則 這稱為沖突解決 a 專一性排序如果某一規(guī)則條件部分規(guī)定的情況 比另一規(guī)則條件部分規(guī)定的情況更有針對(duì)性 則這條規(guī)則有較高的優(yōu)先級(jí) b 規(guī)則排序如果規(guī)則編排的順序就表示了啟用的優(yōu)先級(jí) 則稱之為規(guī)則排序 c 數(shù)據(jù)排序把規(guī)則條件部分的所有條件按優(yōu)先級(jí)次序編排起來 運(yùn)行時(shí)首先使用在條件部分包含較高優(yōu)先級(jí)數(shù)據(jù)的規(guī)則 d 規(guī)模排序按規(guī)則的條件部分的規(guī)模排列優(yōu)先級(jí) 優(yōu)先使用被滿足的條件較多的規(guī)則 e 就近排序把最近使用的規(guī)則放在最優(yōu)先的位置 這和人類的行為有相似之處 如果某一規(guī)則經(jīng)常被使用 則人們傾向于更多地使用這條規(guī)則 104 2 7 1產(chǎn)生式系統(tǒng)的組成 續(xù) f 上下文限制把產(chǎn)生式規(guī)則按它們所描述的上下文分組 也就是說按上下文對(duì)規(guī)則分組 在某種上下文條件下 只能從與其相對(duì)應(yīng)的那組規(guī)則中選擇可應(yīng)用的規(guī)則 不同的系統(tǒng) 使用上述這些策略的不同組合 如何選擇沖突解決策略完全是啟發(fā)式的 3 操作操作就是執(zhí)行規(guī)則的操作部分 經(jīng)過操作以后 當(dāng)前數(shù)據(jù)庫將被修改 然后 其他的規(guī)則有可能被使用 105 2 7 2產(chǎn)生式系統(tǒng)的推理 106 2 7 2產(chǎn)生式系統(tǒng)的推理 續(xù) 例 用于動(dòng)物識(shí)別的產(chǎn)生式系統(tǒng) 107 2 7 2產(chǎn)生式系統(tǒng)的推理 續(xù) 初始綜合數(shù)據(jù)庫 有暗斑點(diǎn) 長(zhǎng)脖子 長(zhǎng)腿 有奶 有蹄目標(biāo)集合 長(zhǎng)頸鹿 斑馬順序選擇規(guī)則試與事實(shí)匹配 將匹配成功的規(guī)則執(zhí)行并做標(biāo)記 r1匹配失敗 r2匹配成功 綜合數(shù)據(jù)庫 有暗斑點(diǎn) 長(zhǎng)脖子 長(zhǎng)腿 有奶 有蹄 哺乳動(dòng)物 r3 r4 r5 r6匹配失敗 108 2 7 2產(chǎn)生式系統(tǒng)的推理 續(xù) r7匹配成功 綜合數(shù)據(jù)庫 有暗斑點(diǎn) 長(zhǎng)脖子 長(zhǎng)腿 有奶 有蹄 哺乳動(dòng)物 有蹄類 r8 r9 r10匹配失敗 r11匹配成功 綜合數(shù)據(jù)庫 有暗斑點(diǎn) 長(zhǎng)脖子 長(zhǎng)腿 有奶 有蹄 哺乳動(dòng)物 有蹄類 長(zhǎng)頸鹿長(zhǎng)頸鹿已在目標(biāo)集合中 故推理成功結(jié)束 109 2 7 3產(chǎn)生式系統(tǒng)的控制策略 產(chǎn)生式系統(tǒng)的控制策略 當(dāng)有多條規(guī)則可用時(shí) 對(duì)規(guī)則的選擇和處理方式 1 不可撤回方式思想 無論所使用過的規(guī)則是否有效 都不再撤回它的應(yīng)用 優(yōu)點(diǎn) 控制過程簡(jiǎn)單缺點(diǎn) 不一定能找到最優(yōu)解 110 2 7 3產(chǎn)生式系統(tǒng)的控制策略 2 回溯方式思想 如果確定某條規(guī)則的應(yīng)用不利于問題求解 則撤回此規(guī)則的應(yīng)用 兩個(gè)問題 如何確定回溯條件和減少回溯次數(shù) 優(yōu)點(diǎn) 容易實(shí)現(xiàn)且空間代價(jià)小 3 圖搜索方式思想 用圖或樹把應(yīng)用規(guī)則路徑記錄下來 從中選取最優(yōu)路徑 優(yōu)點(diǎn) 有利于尋找最優(yōu)解 111 2 7 3產(chǎn)生式系統(tǒng)的控制策略 續(xù) 產(chǎn)生式系統(tǒng)的推理方向正向推理正向推理又稱為正向鏈接推理 其推理基礎(chǔ)是邏輯演繹的推理鏈 它從一組表示事實(shí)的謂詞或命題出發(fā) 使用一組推理規(guī)則 來證明目標(biāo)謂詞公式或命題是否成立 實(shí)現(xiàn)正向推理的一般策略是 先提供一批數(shù)據(jù) 事實(shí) 到總數(shù)據(jù)庫中 系統(tǒng)利用這些事實(shí)與規(guī)則的前提匹配 觸發(fā)匹配成功的規(guī)則 即啟用規(guī)則 把其