第三章推理技術(shù) 4 1消解原理 4 1消解原理 3 1消解原理 3 2規(guī)則演繹系統(tǒng) 3 3不確定性推理 3 4非單調(diào)推理 3 1消解原理消解原理的基礎(chǔ)知識(shí) 1 謂詞公式 某些推理規(guī)則以及置換合一等概念 2 文字 一個(gè)原子公式和原子公式的否定都叫做文字 3 子句 由文字的析取組成的公式 4 子句集 子句通過合取符號(hào)聯(lián)接起來形成子句集 任一謂詞演算公式可以化成一個(gè)子句集 3 1 1子句集的求取 1 步驟 1 消去蘊(yùn)涵符號(hào)以 A B替換A B 例 A B B C 在消去蘊(yùn)涵符號(hào)后得到公式 A A B B CB A B B C 5 消解 如果存在某個(gè)公理E1 E2和另一公理 E2 E3 那么E1 E3在邏輯上成立 這就是消解 而稱E1 E3為E1 E2和 E2 E3的消解式 resolvent 2 減少否定符號(hào)的轄域每個(gè)否定符號(hào) 最多只用到一個(gè)謂詞符號(hào)上 并反復(fù)應(yīng)用狄 摩根定律 3 對變量標(biāo)準(zhǔn)化在任一量詞轄域內(nèi) 受該量詞約束的變量為一啞元 虛構(gòu)變量 它可以在該轄域內(nèi)處處統(tǒng)一地被另一個(gè)沒有出現(xiàn)過的任意變量所代替 而不改變公式的真值 合適公式中變量的標(biāo)準(zhǔn)化意味著對啞元改名以保證每個(gè)量詞有其自己唯一的啞元 4 消去存在量詞 Skolem函數(shù) 在公式 y Skolem函數(shù) 在公式 y x P x y 中 存在量詞是在全稱量詞的轄域內(nèi) 我們允許所存在的x可能依賴于y值 令這種依賴關(guān)系明顯地由函數(shù)g y 所定義 它把每個(gè)y值映射到存在的那個(gè)x 這種函數(shù)叫做Skolem函數(shù) 如果用Skolem函數(shù)代替存在的x 我們就可以消去全部存在量詞 并寫成 y P g y y 如果要消去的存在量詞不在任何一個(gè)全稱量詞的轄域內(nèi) 那么我們就用不含變量的Skolem函數(shù)即常量 例如 x P x 化為P A 5 化為前束形把所有全稱量詞移到公式的左邊 并使每個(gè)量詞的轄域包括這個(gè)量詞后面公式的整個(gè)部分 所得公式稱為前束形 前束形公式由前綴和母式組成 前綴由全稱量詞串組成 母式由沒有量詞的公式組成 即前束形 前綴 母式 全稱量詞串無量詞公式 6 把母式化為合取范式任何母式都可寫成由一些謂詞公式和 或 謂詞公式的否定的析取的有限集組成的合取 這種母式叫做合取范式 例如 A B C 化為 A B A C 7 消去全稱量詞可以消去明顯出現(xiàn)的全稱量詞 8 消去連詞符號(hào) 用用 A B A C 代替 A B A C 以消去明顯的符號(hào) 反復(fù)代替的結(jié)果 最后得到一個(gè)有限集 其中每個(gè)公式是文字的析取 任一個(gè)只由文字的析取構(gòu)成的合適公式叫做一個(gè)子句 9 更換變量名稱可以更換變量符號(hào)的名稱 使一個(gè)變量符號(hào)不出現(xiàn)在一個(gè)以上的子句中 例如 對于子集 P x P y P f x y P x Q x g x P x P g x 在更改變量名后 可以得到子句集 將下列謂詞演算公式化為一個(gè)子句集 x P x y P y P f x y y Q x y P y 3 1 2消解推理規(guī)則1 消解式已知兩子句L1 和 L2 如果L1和L2具有最一般合一者 那么通過消解可以從這兩個(gè)父輩子句推導(dǎo)出一個(gè)新子句 這個(gè)新子句叫做消解式 它是由取這兩個(gè)子句的析取 然后消去互補(bǔ)對而得到的 2 消解式求法 1 假言推理父輩子句P P Q 即P Q 消解式Q 2 合并 3 重言式 4 空子句 矛盾 5 鏈?zhǔn)?三段論 3 1 3含有變量的消解式為了對含有變量的子句使用消解規(guī)則 我們必須找到一個(gè)置換 作用于父輩子句使其含有互補(bǔ)文字 例1 例2 表3 1消解推理常用規(guī)則 3 1 4消解反演求解過程1基本思想把要解決的問題作為一個(gè)要證明的命題 其目標(biāo)公式被否定并化成子句形 然后添加到命題公式集中去 把消解反演系統(tǒng)應(yīng)用于聯(lián)合集 并推導(dǎo)出一個(gè)空子句 NIL 產(chǎn)生一個(gè)矛盾 這說明目標(biāo)公式的否定式不成立 即有目標(biāo)公式成立 定理得證 問題得到解決 這與數(shù)學(xué)中反證法的思想十分相似 2消解反演 1 反演求解的步驟給出一個(gè)公式集S和目標(biāo)公式L 通過反證或反演來求證目標(biāo)公式L 其證明步驟如下 1 否定L 得 L 2 把 L添加到S中去 3 把新產(chǎn)生的集合 L S 化成子句集 4 應(yīng)用消解原理 力圖推導(dǎo)出一個(gè)表示矛盾的空子句NIL 2 反演求解的正確性設(shè)公式L在邏輯上遵循公式集S 那么按照定義滿足S的每個(gè)解釋也滿足L 決不會(huì)有滿足S的解釋能夠滿足 L的 所以不存在能夠滿足并集S L 的解釋 因此 如果L在邏輯上遵循S 那么由并集S L 消解得到的子句 最后將產(chǎn)生空子句 反之 可以證明 如果從S L 的子句消解得到空子句 那么L在邏輯上遵循S 3 反演求解舉例例1某公司招聘工作人員 有A B C三人面試 公司表達(dá)想法 1 三人中至少取一人 2 如果錄取A而不錄取B 則一定錄取C 3 如果錄取B 則一定錄取C 求證 公司一定錄取C 例2 有些患者喜歡任一醫(yī)生 沒有任一患者喜歡任一庸醫(yī) 所以沒有庸醫(yī)的醫(yī)生 消解反演可以表示為一棵反演樹 其根節(jié)點(diǎn)為NIL 3問題求解 把已知前提用謂詞公式表示出來 并且化為子句集 把待求解的問題也用謂詞公式表示出來 并且與謂詞ANSWER一起構(gòu)成析取式 變元要一致 也化為子句集 并將其并入 構(gòu)成新子句集 對新子句集消解反演 若得到歸結(jié)式ANSWER 則答案就在ANSWER中 下面舉例說明問題求解過程 例 已知 王先生是小李的老師 小李與小張是同班同學(xué) 如果 與 是同班同學(xué) 則 的老師也是的 老師 求 小張的老師是誰 例 說 和 說假話 說 和 中至少有一人說假話 說 和 說假話 求誰說真話 3 2規(guī)則演繹系統(tǒng) 本節(jié)將研究采用易于敘述的if then 如果 那么 規(guī)則來求解問題 基于規(guī)則的問題求解系統(tǒng)運(yùn)用下述規(guī)則 其中 If部分可能由幾個(gè)if組成 而Then部分可能由一個(gè)或一個(gè)以上的then組成 這種基于規(guī)則的系統(tǒng)叫做規(guī)則演繹系統(tǒng) rulebaseddeductionsystem 在這種系統(tǒng)中 通常稱每個(gè)if部分為前項(xiàng) 稱每個(gè)then部分為后項(xiàng) 有時(shí) then部分用于規(guī)定動(dòng)作 這時(shí) 稱這種基于規(guī)則的系統(tǒng)為反應(yīng)式系統(tǒng) reactionsystem 或產(chǎn)生式系統(tǒng) productionsystem 3 2 1規(guī)則正向演繹系統(tǒng)基于規(guī)則的演繹系統(tǒng)和產(chǎn)生式系統(tǒng) 均有兩種推理方式 正向推理和逆向推理 正向推理 從if部分向then部分推理的過程 它是從事實(shí)或狀況向目標(biāo)或動(dòng)作進(jìn)行操作的 逆向推理 從then部分向if部分推理的過程 它是從目標(biāo)或動(dòng)作向事實(shí)或狀況進(jìn)行操作的 1 事實(shí)表達(dá)式的與或形變換在基于規(guī)則的正向演繹系統(tǒng)中 把事實(shí)表示為謂詞演算公式 并把這些公式變換為叫做與或形的非蘊(yùn)涵形式 與或形表達(dá)式是由符號(hào) 和 連接的一些文字的子表達(dá)式組成的 要把一個(gè)公式化為與或形 可采用下列步驟 1 利用 W1 W2 和 W1 W2 的等價(jià)關(guān)系 消去符號(hào) 如果存在該符號(hào)的話 實(shí)際上 在事實(shí)中間很少有符號(hào) 出現(xiàn) 因?yàn)榭砂烟N(yùn)涵式表示為規(guī)則 2 用狄 摩根 DeMorgan 定律把否定符號(hào)移進(jìn)括號(hào)內(nèi) 直到每個(gè)否定符號(hào)的轄域最多只含有一個(gè)謂詞為止 3 對所得到的表達(dá)式進(jìn)行Skolem化和前束化 4 對全稱量詞轄域內(nèi)的變量進(jìn)行改名和變量標(biāo)準(zhǔn)化 而存在量詞量化變量用Skolem函數(shù)代替 5 刪去全稱量詞 而任何余下的變量都被認(rèn)為具有全稱量化作用 例如 有事實(shí)表達(dá)式 u v Q v u R v P v S u v 把它化為 Q v A R v P v S A v Q w A R v P v S A v 對變量更名標(biāo)準(zhǔn)化 使得同一變量不出現(xiàn)在事實(shí)表達(dá)式的不同主要合取式中 更名后得與或形表達(dá)式 2 事實(shí)表達(dá)式的與或圖表示與或形的事實(shí)表達(dá)式可用與或圖來表示 如圖的與或樹表示出上述例子的與或形事實(shí)表達(dá) 3與或圖的F規(guī)則變換F規(guī)則 L W式中 L是單文字 W為與或形的唯一公式 把形式為L W的規(guī)則應(yīng)用到任一個(gè)具有葉節(jié)點(diǎn)n并由文字L標(biāo)記的與或圖上 可以得到一個(gè)新的與或圖 在新的圖上 節(jié)點(diǎn)n由一個(gè)單線連接符接到后繼節(jié)點(diǎn) 也由L標(biāo)記 它是表示為W的一個(gè)與或圖結(jié)構(gòu)的根節(jié)點(diǎn) 例如 把規(guī)則S X Y Z應(yīng)用到下圖所示的與或圖中標(biāo)有S的葉節(jié)點(diǎn)上 圖中標(biāo)記S的兩個(gè)節(jié)點(diǎn)由一條叫做匹配弧的弧線連接起來 我們希望在應(yīng)用規(guī)則之后得到的圖 既能表示原始事實(shí) 又能表示從原始事實(shí)和該規(guī)則推出的事實(shí)表達(dá)式 事實(shí)表達(dá)式 Q w A R v P v S A v 與規(guī)則S X Y Z的消解式 X Z P Q Y Z P Q R X Z R Y Z全部包含在解圖所表示的子句之中 4 作為終止條件的目標(biāo)公式應(yīng)用F規(guī)則的目的在于從某個(gè)事實(shí)公式和某個(gè)規(guī)則集出發(fā)來證明某個(gè)目標(biāo)公式 目標(biāo)文字和規(guī)則可用來對與或圖添加后繼節(jié)點(diǎn) 當(dāng)一個(gè)目標(biāo)文字與該圖中文字節(jié)點(diǎn)n上的一個(gè)文字相匹配時(shí) 我們就對該圖添加這個(gè)節(jié)點(diǎn)n的新后裔 并標(biāo)記為匹配的目標(biāo)文字 這個(gè)后裔叫做目標(biāo)節(jié)點(diǎn) 舉例 用消解反演來證明目標(biāo)公式 結(jié)論 當(dāng)正向演繹系統(tǒng)產(chǎn)生一個(gè)含有以目標(biāo)節(jié)點(diǎn)作為終止的解圖時(shí) 此系統(tǒng)就成功地終止 3 2 2規(guī)則逆向演繹系統(tǒng)基于規(guī)則的逆向演繹系統(tǒng) 其操作過程與正向演繹系統(tǒng)相反 即為從目標(biāo)到事實(shí)的操作過程 從then到if的推理過程 1 目標(biāo)表達(dá)式的與或形式逆向演繹系統(tǒng)能夠處理任意形式的目標(biāo)表達(dá)式 首先 采用與變換事實(shí)表達(dá)式同樣的過程 把目標(biāo)公式化成與或形 即消去蘊(yùn)涵符號(hào) 把否定符號(hào)移進(jìn)括號(hào)內(nèi) 對全稱量詞Skolem化并刪去存在量詞 舉例如下 目標(biāo)表達(dá)式被化成與或形 P f y Q f y y P f y S y 式中 f y 為一Skolem函數(shù) 對目標(biāo)的主要析取式中的變量分離標(biāo)準(zhǔn)化可得 P f z Q f y y P f y S y 應(yīng)注意不能對析取的子表達(dá)式內(nèi)的變量y改名而使每個(gè)析取式具有不同的變量 與或形的目標(biāo)公式也可以表示為與或圖 不過 與事實(shí)表達(dá)式的與或圖不同的是 對于目標(biāo)表達(dá)式 與或圖中的k線連接符用來分開合取關(guān)系的子表達(dá)式 上例所用的目標(biāo)公式的與或圖如下所示 這個(gè)目標(biāo)公式的子句形表示中的子句集可從終止在葉節(jié)點(diǎn)上的解圖集讀出 P f z Q f y y R f y Q f y y S y 可見目標(biāo)子句是文字的合取 而這些子句的析取是目標(biāo)公式的子句形 2 與或圖的B規(guī)則變換B規(guī)則 即逆向推理規(guī)則 B規(guī)則是建立在確定的蘊(yùn)涵式基礎(chǔ)上的 我們把B規(guī)則限制為 W L其中 W為任一與或形公式 L為文字 把B規(guī)則限制為這種形式的蘊(yùn)涵式還可以簡化匹配 可以把像W L1 L2 這樣的蘊(yùn)涵式化為兩個(gè)規(guī)則W L1和W L2 3 作為終止條件的事實(shí)節(jié)點(diǎn)的一致解圖逆向系統(tǒng)中的事實(shí)表達(dá)式均限制為文字合取形 它可以表示為一個(gè)文字集 當(dāng)一個(gè)事實(shí)文字和標(biāo)在該圖文字節(jié)點(diǎn)上的文字相匹配時(shí) 就可把相應(yīng)的后裔事實(shí)節(jié)點(diǎn)添加到該與或圖中去 這個(gè)事實(shí)節(jié)點(diǎn)通過標(biāo)有mgu的匹配弧與匹配的子目標(biāo)文字節(jié)點(diǎn)連接起來 逆向系統(tǒng)成功的終止條件是與或圖包含有某個(gè)終止在事實(shí)節(jié)點(diǎn)上的一致解圖 下面以一個(gè)簡單的例子 分析基于規(guī)則的逆向演繹系統(tǒng)的工作過程 這個(gè)例子的事實(shí) 應(yīng)用規(guī)則和問題分別表示于下 事實(shí) F1 DOG FIDO 狗的名字叫FidoF2 BARKS FIDO Fido是不叫的F3 WAGSTAIL FIDO Fido搖尾巴F4 MEOWS MYRTLE 貓咪的名字叫Myrtle規(guī)則 R1 WAGSTAIL 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 貓咪是貓問題 是否存在這樣的一只貓和一條狗 使得這只貓不怕這條狗 用目標(biāo)表達(dá)式表示此問題為 x y CAT x DOG y AFRAID x y 下圖表示出這個(gè)問題的一致解圖 圖中 用雙線框表示事實(shí)節(jié)點(diǎn) 用規(guī)則編號(hào)R1 R2和R5等來標(biāo)記所應(yīng)用的規(guī)則 此解圖中有八條匹配弧 每條匹配弧上都有一個(gè)置換 終止在事實(shí)節(jié)點(diǎn)前的置換為 MYRTLE x 和 FIDO y 把它應(yīng)用到目標(biāo)表達(dá)式 我們就得到該問題的回答語句如下 CAT MYRTLE DOG FIDO AFRAID MYRTLE FIDO 3 3不確定性推理 推理 從已知事實(shí)出發(fā) 通過運(yùn)用相關(guān)的知識(shí)逐步推出某個(gè)結(jié)論的過程 不確定性推理 就是從不確定性初始證據(jù)出發(fā) 通過運(yùn)用不確定性的知識(shí) 最終推出具有一定程度的不確定性但卻有合理或者近乎合理的結(jié)論的思維過程 不確定性是智能問題的本質(zhì)特征 智能離不開對不確定性知識(shí)的處理 智能主要反映在求解不確定性問題的能力上 3 3 1概率推理基于概率論的不確定性推理有很多種 在這里僅討論比較成熟的一種推理方法 主觀Bayes方法 1 Bayes公式及主觀Bayes方法主觀Bayes方法是最早用于處理不確定性推理的方法之一 已在地礦勘探專家系統(tǒng)PROSPECTOR中得到了成功的應(yīng)用 Bayes公式 若有諸事件A1 A2 An 彼此獨(dú)立 B為任何事件 且P Ai 0 i 1 2 n P B 0 那么Bayes公式可表示為 為先驗(yàn)概率 為后驗(yàn)概率 Bayes公式就是從先驗(yàn)概率推導(dǎo)出后驗(yàn)概率的公式 為闡明主觀Bayes方法 先引入幾個(gè)概念 1 幾率函數(shù)幾率函數(shù)定義為 它表示x的出現(xiàn)概率與不出現(xiàn)概率之比 顯然隨P x 的加大o x 也加大 而且當(dāng)P x 0時(shí) 有o x 0當(dāng)P x 1時(shí) 有o x 于是 取值于 0 1 的P x 被放大為取值于 0 的o x 2 充分性度量充分性度量定義為 它表示E對H的支持程度 取值于 0 由專家給出 3 必要性度量 必要性度量定義為 它表示 E對 的支持程度 即E對H為真的必要性程度 取值范圍為 0 也是由專家憑經(jīng)驗(yàn)給出 2 證據(jù)的不確定性描述在主觀Bayes方法中 證據(jù)的不確定性也是用概率表示的 在PROSPECTOR中 由于根據(jù)觀察S直接求出P E S 非常困難 所以它采用了一種變通的方法 即引進(jìn)了可信度C E S 的概念 用戶可根據(jù)實(shí)際情況在 5 5 中選取一個(gè)整數(shù)作為初始證據(jù)的可信度 可信度C E S 與