《產(chǎn)生式系統(tǒng) 》PPT課件.ppt

2019/7/2,1,第五章 產(chǎn)生式系統(tǒng),產(chǎn)生式表示方法 產(chǎn)生式系統(tǒng)基本原理 產(chǎn)生式系統(tǒng)與圖搜索 產(chǎn)生式系統(tǒng)應(yīng)用,2019/7/2,2,第五章 產(chǎn)生式系統(tǒng),產(chǎn)生式系統(tǒng)的體系結(jié)構(gòu)是 實現(xiàn)圖搜索的理想程序結(jié)構(gòu)，產(chǎn)生式已是人工智能系統(tǒng)的一種最典型最普遍的結(jié)構(gòu)形式。 許多專家系統(tǒng)和機器學(xué)習(xí)系統(tǒng)都是用產(chǎn)生式系統(tǒng)實現(xiàn)的。從結(jié)構(gòu)形式上看很多人工智能系統(tǒng)都是產(chǎn)生式系統(tǒng)。,2019/7/2,3,第五章 產(chǎn)生式系統(tǒng),產(chǎn)生式表示方法 產(chǎn)生式系統(tǒng)基本原理 產(chǎn)生式系統(tǒng)與圖搜索 產(chǎn)生式系統(tǒng)應(yīng)用,2019/7/2,4,產(chǎn)生式表示法,產(chǎn)生式 產(chǎn)生式一詞是從波斯特機中借用來的。波斯特機是一種自動機，它是根據(jù)串替換規(guī)則提出的一種計算模型。其中的每一條規(guī)則就叫一個產(chǎn)生式。也稱產(chǎn)生式規(guī)則，簡稱規(guī)則。 這里產(chǎn)生式就是前面討論過的操作、邏輯蘊含式、推理規(guī)則以及各種關(guān)系（包含經(jīng)驗性聯(lián)想）的一種邏輯抽象。,2019/7/2,5,產(chǎn)生式表示法,產(chǎn)生式的一般形式為： 前件后件（情況行為） 前件是前提，規(guī)則的執(zhí)行條件。 后件是結(jié)論或動作，規(guī)則體。 產(chǎn)生式規(guī)則的語義：如果前提滿足，則可得結(jié)論或者執(zhí)行相應(yīng)的動作，即后件由前件觸發(fā)。 從基本事實到結(jié)論之間的復(fù)雜推理可以借助中間結(jié)論形成小型簡單產(chǎn)生式。,2019/7/2,6,產(chǎn)生式表示法,例：一條知識的原始形態(tài)是 R: ( (A B) (C D) (E F) G)=S 引入中間結(jié)論S1，S2，形成一些小型的產(chǎn)生式: R1： A B =S1 R2： C D =S1 R3： E F =S2 R4： S1 G =S R5: S1 S2 =S,2019/7/2,7,產(chǎn)生式表示法,給定一組事實之后可用匹配技術(shù)尋找可用產(chǎn)生式，其基本思想是將已知事實代入產(chǎn)生式的前件，若前件為真，則該產(chǎn)生式是可用的。 提高匹配效率的方法 索引匹配。為狀態(tài)建立可用產(chǎn)生式索引表，減少可用產(chǎn)生式搜索范圍。 分層匹配。將產(chǎn)生式分成若干層或組，按一定特征進行分層搜索。 過濾匹配。邊匹配邊 按某些附加特征或參數(shù)對可用產(chǎn)生式進行精選。,2019/7/2,8,產(chǎn)生式表示法,如果一組事實可以同時使幾個產(chǎn)生式前提為真，常用以下方法進行選擇（沖突消解策略）： 將所有產(chǎn)生式排序，選最早匹配成功的一個，不管其余的產(chǎn)生式； 在所有匹配成功的產(chǎn)生式中取最強的，即前提條件最多或情況元素最多者； 最近用過的產(chǎn)生式優(yōu)先（或反之）； 給情況元素以不同的優(yōu)先權(quán)； 使用估計函數(shù)f(x)排序； 利用上下文限制。,2019/7/2,9,產(chǎn)生式表示法,在產(chǎn)生式系統(tǒng)中，從前提到結(jié)論通常也是一棵與或樹。 合取，與節(jié)點：一個產(chǎn)生式的前提包含了幾個事實，那么它的結(jié)論對應(yīng)這些事實的合取。 析取，或節(jié)點：一個結(jié)論可以由多個產(chǎn)生式得到，則這個結(jié)論對應(yīng)這些產(chǎn)生式的析取。 每個產(chǎn)生式系統(tǒng)都隱含著許多這樣的與或樹。,2019/7/2,10,產(chǎn)生式表示法,事實,中介事實 B、C、D,產(chǎn)生式規(guī)則 P1、P2、P3、P4、P5,結(jié)論,2019/7/2,11,產(chǎn)生式表示法（例）,例 三個聰明人問題。古代有個國王想知道他的三個大王中誰最聰明，就在他們每個人前額上都畫了一個點，他們都能看到別人點的顏色，但看不到別人點的顏色。國王說，你們中間至少有一個人的點式白色的。于是重復(fù)地問他們：“誰知道自己點地顏色？”三位大臣們頭兩次都回答說不知道。題目要求證明下一次他們?nèi)紩f“知道”，并且所有的點都是白色。,2019/7/2,12,產(chǎn)生式表示法（例）,分析： 這類問題的特點是有有限個受試者，每個人對問題都只有部分了解，無法直接求解。但在推理過程中每個人又可以從別人那里獲得新的知識，重新進行推理?？梢杂卯a(chǎn)生式來表達推理過程中所用到的各種知識。,2019/7/2,13,產(chǎn)生式表示法（例）,狀態(tài)集合表示： 用x1,x2,x3表示三個人點的顏色，1表示白色，0表示非白色。 X(x1,x2,x3)表示顏色分布狀態(tài)。 全部可能的狀態(tài)集合(可能界PW0)： (0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1) 實際給定的狀態(tài)為現(xiàn)實界X0 (x10,x20,x30) 用排除法找到X0 。,2019/7/2,14,產(chǎn)生式表示法（例）,排除過程： 第一次，大臣只知道至少有一個人是白點，排除X0(0,0,0)狀態(tài)。這時如果有人看到兩個非白點，根據(jù)排除的狀態(tài)可推知自己是白點。 第二次大臣根據(jù)沒有一個人知道自己點顏色的事實推知至少兩人為白點。排除(0,0,1)(0,1,0)(1,0,0)狀態(tài)。這時如果有人看到一個非白點，根據(jù)排除后得到的狀態(tài)可推知自己的點是白的。 第三次，大臣們根據(jù)仍無人知道自己點顏色的新事實推知沒有一個非白點出現(xiàn)，即X0(1,1,1)。于是三人都知道自己點的顏色是白的。,2019/7/2,15,產(chǎn)生式表示法（例）,引入中介狀態(tài)并定義下述符號： Si i大臣看到的非白點數(shù)； Wi i大臣猜出自己點的顏色否。如果他宣布已知道自己點的顏色，為1，否則為0； nX0中白點的個數(shù)。,2019/7/2,16,產(chǎn)生式表示法（例）,(1)(已知)(n=1) X0 (0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)； (2)(有人看見兩個非白點)(n=1) (Si=2) =(Wi=1),(i=1,2,3,下同)； (3)( i ) (Wi=1) (n=1) = (n=1) ； (4) (n=1) = ( i ) (Wi=1) ； (5) ( i ) (Wi=0) (n=1) = (n=2) ; (6) (n=2) X0 (0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)； (7) (有人看見一個非白點)(n=2) (Si=1) =(Wi=1); (8) ( i ) (Wi=1) (n=2) = (n=2) ; (9) (n=2) = ( i ) (Wi=1); (10) ( i ) (Wi=0) (n=2) = (n=3); (11) (n=3) X0 (1,1,1)； (12) (n=3) = ( i ) (Wi=1).,2019/7/2,17,產(chǎn)生式表示法（例）,上述結(jié)果可以推廣到更一般的情況：設(shè)有m個大臣，國王說至少有l(wèi)個人的點是白色的，則有下述產(chǎn)生式： (1) (n=l) X0 x|x中的白點數(shù)=l； (2) (n=l) (Si=2) =(Wi=1),(i=1,2,m,下同)； (3)( i ) (Wi=1) (n=l) = (n=l) ； (4) (n=l) = ( i ) (Wi=l) ； (5)( i ) (Wi=0) (n=l) (l (n=l1) ; (6)( i ) (Wi=0) (n=l) (lm-1)= (nm)。,2019/7/2,18,第五章 產(chǎn)生式系統(tǒng),產(chǎn)生式表示方法 產(chǎn)生式系統(tǒng)基本原理 產(chǎn)生式系統(tǒng)與圖搜索 產(chǎn)生式系統(tǒng)應(yīng)用,2019/7/2,19,產(chǎn)生式系統(tǒng)基本原理,組成和分類 運行過程 常用算法,2019/7/2,20,產(chǎn)生式系統(tǒng)基本原理（組成和分類）,產(chǎn)生式系統(tǒng)結(jié)構(gòu),產(chǎn)生式規(guī)則庫(知識庫),推理機（控制）,全局數(shù)據(jù)庫,2019/7/2,21,產(chǎn)生式系統(tǒng)基本原理（組成和分類）,組成 全局數(shù)據(jù)庫人工智能系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)中心。是一個動態(tài)數(shù)據(jù)結(jié)構(gòu)，用來存放初始事實數(shù)據(jù)、中間結(jié)構(gòu)和最后結(jié)果。對應(yīng)敘述性知識。 產(chǎn)生式規(guī)則庫作用在全局數(shù)據(jù)庫上的一些規(guī)則的集合。每條規(guī)則都有一定的條件，若全局數(shù)據(jù)庫中內(nèi)容滿足這些條件可調(diào)用這條規(guī)則。對應(yīng)過程性知識。 推理機負責(zé)產(chǎn)生式規(guī)則的前提條件測試或匹配，規(guī)則的調(diào)度和選取，規(guī)則體的解釋和執(zhí)行。對應(yīng)控制性知識。,2019/7/2,22,產(chǎn)生式系統(tǒng)基本原理（組成和分類）,例 旅行推銷員問題。求從A城出發(fā)，經(jīng)過其他城市一次且僅一次，最后回到A城的最小費用路線。城市之間的交通費用標(biāo)在相應(yīng)的聯(lián)線上。建立產(chǎn)生式系統(tǒng)。,2019/7/2,23,產(chǎn)生式系統(tǒng)基本原理（組成和分類）,（1）全局數(shù)據(jù)庫（已訪問過的城鎮(zhèn)名稱序列）。約束條件是除城鎮(zhèn)A之外其他名稱不得在序列中重復(fù)出現(xiàn)；只有所有的名稱都在序列中出現(xiàn)后，城鎮(zhèn)A才能重復(fù)出現(xiàn)。 （2）規(guī)則集如下表所示。 （3）推理： （A） （AB） （ABE） （4）終止條件序列始于A，終止于A，其中包含其他所有城鎮(zhèn)一次，且費用最少。 （5）各種搜索策略選擇規(guī)則，如廣度優(yōu)先搜索，最好優(yōu)先搜索等。,R2,R5,2019/7/2,24,產(chǎn)生式系統(tǒng)基本原理（組成和分類）,規(guī)則集,2019/7/2,25,產(chǎn)生式系統(tǒng)基本原理（組成和分類）,與一般分級組織的計算機軟件相比具有特點： 全局數(shù)據(jù)庫的內(nèi)容可以為所有規(guī)則所訪問，沒有任何部分是專為某一規(guī)則建立的，這種特性便于模仿智能行為中的強數(shù)據(jù)驅(qū)動。 規(guī)則本身不調(diào)用其他規(guī)則。規(guī)則之間的聯(lián)系必須通過全部數(shù)據(jù)庫聯(lián)系。 全局數(shù)據(jù)庫、規(guī)則和推理機之間相對獨立，這種積木式結(jié)構(gòu)便于整個系統(tǒng)增加和修改知識。,2019/7/2,26,產(chǎn)生式系統(tǒng)基本原理（組成和分類）,分類體系（尼爾遜） 按搜索策略分 不可挽回（irreversible）的產(chǎn)生式系統(tǒng) 試探性的（Tentative）產(chǎn)生式系統(tǒng) 回溯式（Backing）產(chǎn)生式系統(tǒng) 圖搜索式（Graph Search）產(chǎn)生式系統(tǒng) 按搜索方向分 向前產(chǎn)生式系統(tǒng)（Forward Production System） 向后產(chǎn)生式系統(tǒng)（Backward Production System） 雙向產(chǎn)生式系統(tǒng)（Bidirectional Production System） 兩種特殊的產(chǎn)生式系統(tǒng) 可交換的（Commutative）產(chǎn)生式系統(tǒng) 可分解的（Decomposable）產(chǎn)生式系統(tǒng),2019/7/2,27,產(chǎn)生式系統(tǒng)基本原理,組成和分類 運行過程 控制策略與常用算法,2019/7/2,28,產(chǎn)生式系統(tǒng)基本原理（運行過程）,推理機一次運行過程,2019/7/2,29,產(chǎn)生式系統(tǒng)基本原理（運行過程）,產(chǎn)生式系統(tǒng)運行過程 實際的產(chǎn)生式系統(tǒng)，目標(biāo)條件往往要經(jīng)過多步推理才能滿足或者證明問題無解。產(chǎn)生式系統(tǒng)的運行過程就是推理機不斷的運用規(guī)則庫中的規(guī)則，作用于動態(tài)數(shù)據(jù)庫，不斷進行推理并不斷檢測目標(biāo)條件是否被滿足的過程。 產(chǎn)生式系統(tǒng)運行過程是從初始事實出發(fā)，尋求到達目標(biāo)條件的通路的過程。所以也是一個搜索的過程。,2019/7/2,30,產(chǎn)生式系統(tǒng)基本原理,組成和分類 運行過程 常用算法,2019/7/2,31,產(chǎn)生式系統(tǒng)基本原理（常用算法）,推理方式 正向推理 從初始事實數(shù)據(jù)出發(fā)，正向使用規(guī)則進行推理，朝目標(biāo)方向前進。又稱為前向推理、正向鏈、數(shù)據(jù)驅(qū)動的推理。 反向推理 從目標(biāo)出發(fā)，反向使用規(guī)則進行推理，朝初始事實或數(shù)據(jù)方向前進。又稱反向推理、反向鏈、目標(biāo)驅(qū)動的推理。,2019/7/2,32,產(chǎn)生式系統(tǒng)基本原理（常用算法）,正向推理算法 步1 將初始事實/數(shù)據(jù)置入動態(tài)數(shù)據(jù)庫； 步2 用動態(tài)數(shù)據(jù)庫中的事實匹配目標(biāo)條件，若目標(biāo)條件滿足，推理成功，結(jié)束。 步3 用規(guī)則庫中各規(guī)則的前提匹配動態(tài)數(shù)據(jù)庫中的事實，將匹配成功的規(guī)則組成待用規(guī)則集。 步4 若待用規(guī)則集為空，則運行失敗，退出。 步5 將待用規(guī)則集中各規(guī)則的結(jié)論加入動態(tài)數(shù)據(jù)庫，或者執(zhí)行其動作，轉(zhuǎn)步2。,2019/7/2,33,產(chǎn)生式系統(tǒng)基本原理（常用算法）,反向推理算法 步1 將初始事實/數(shù)據(jù)置入動態(tài)數(shù)據(jù)庫，將目標(biāo)條件置入目標(biāo)鏈； 步2 若目標(biāo)鏈為空，則推理成功，結(jié)束。 步3 取出目標(biāo)鏈中第一個目標(biāo)，用動態(tài)數(shù)據(jù)庫中的事實同其匹配，若匹配成功，轉(zhuǎn)步2。 步4 用規(guī)則集中的各規(guī)則的結(jié)論同該目標(biāo)匹配，若匹配成功，則33將第一個匹配成功且未用過的規(guī)則的前提作為新的目標(biāo)，并取代原來的父目標(biāo)加入目標(biāo)鏈，轉(zhuǎn)步3。 步5 若該目標(biāo)是初始目標(biāo)，則推理失敗，退出。 步6 將該目標(biāo)的父目標(biāo)移回目標(biāo)鏈，取代該目標(biāo)及其兄弟目標(biāo)，轉(zhuǎn)步3。,2019/7/2,34,產(chǎn)生式系統(tǒng)基本原理（常用算法）,例：動物識別系統(tǒng)的產(chǎn)生是系統(tǒng)描述及求解。 規(guī)則： r1： IF 該動物有毛發(fā) THEN 該動物是哺乳動物 r2： IF 該動物有奶 THEN 該動物是哺乳動物 r3： IF 該動物有羽毛 THEN 該動物是鳥 r4： IF 該動物會飛 AND 會下蛋 THEN 該動物是鳥 r5： IF 該動物吃肉 THEN 該動物是食肉動物 r6： IF 該動物有犬齒 AND 有爪 AND 眼盯前方 THEN 該動物是食肉動物動物,2019/7/2,35,產(chǎn)生式系統(tǒng)基本原理（常用算法）,r7： IF 該動物是哺乳動物 AND 有蹄 THEN 該動物是有蹄類動物 r8： IF 該動物是哺乳動物 AND 是嚼反芻動物 THEN 該動物是有蹄動物 r9： IF 該動物是哺乳動物 AND 是食肉動物 AND 是黃褐色 AND 身上有暗斑點 THEN 該動物是金錢豹 r10：IF 該動物是哺乳動物 AND 是食肉動物 AND 是黃褐色 AND 身上有黑色條紋 THEN 該動物是虎 r11：IF 該動物是有蹄類動物 AND 有長脖子 AND 有長腿 AND 身上有暗斑點 THEN 該動物是長頸鹿 r12：IF 該動物有蹄類動物 AND 身上有黑色條紋 THEN 該動物是斑馬,2019/7/2,36,產(chǎn)生式系統(tǒng)基本原理（常用算法）,r13： IF 該動物是鳥 AND 有長脖子 AND 有長腿 AND 不會飛 AND 有黑白二色 THEN 該動物是鴕鳥 r14： IF 該動物是鳥 AND 會游泳 AND 不會飛 AND 有黑白二色 THEN 該動物是企鵝 r15：IF 該動物是鳥 AND 善飛 THEN 該動物是信天翁,2019/7/2,37,產(chǎn)生式系統(tǒng)基本原理（常用算法）,初始事實： f1：某動物有毛發(fā)。 f2：吃肉。 f3：黃褐色。 f4：有黑色條紋 目標(biāo)條件為：該動物為什么？,2019/7/2,38,產(chǎn)生式系統(tǒng)基本原理（常用算法）,2019/7/2,39,產(chǎn)生式系統(tǒng)基本原理（常用算法）,2019/7/2,40,第五章 產(chǎn)生式系統(tǒng),產(chǎn)生式表示方法 產(chǎn)生式系統(tǒng)基本原理 產(chǎn)生式系統(tǒng)與圖搜索 產(chǎn)生式系統(tǒng)應(yīng)用,2019/7/2,41,產(chǎn)生式系統(tǒng)與圖搜索,產(chǎn)生式系統(tǒng)與圖搜索對比,2019/7/2,42,第五章 產(chǎn)生式系統(tǒng),產(chǎn)生式表示方法 產(chǎn)生式系統(tǒng)基本原理 產(chǎn)生式系統(tǒng)與圖搜索 產(chǎn)生式系統(tǒng)應(yīng)用,2019/7/2,43,產(chǎn)生式系統(tǒng)的應(yīng)用實例,基于消解原理的產(chǎn)生式系統(tǒng) 基于自然演繹法的產(chǎn)生式系統(tǒng) 基于專用知識的產(chǎn)生式系統(tǒng),2019/7/2,44,基于消解原理的產(chǎn)生式系統(tǒng),消解原理的產(chǎn)生式系統(tǒng) 全局數(shù)據(jù)庫：子句集合S 產(chǎn)生式規(guī)則集：一般形式是消解 控制系統(tǒng) 終止條件：NIL S 搜索策略：是個可交換的系統(tǒng)，使用各個具體的消解與先后順序無關(guān)，采用不可挽回的控制策略。,2019/7/2,45,基于消解原理的產(chǎn)生式系統(tǒng),過程RESOLUTION 步1 CLAUSES S； 步2 until NIL是CLAUSES中的元素為止，do； 步3 begin 步4 在CLAUSES中選取兩個可消解的子句Ci和Cj； 步5 計算Ci和Cj的消解式Rij； 步6 把Rij并入到CLAUSES中； 步7 end。,2019/7/2,46,基于消解原理的產(chǎn)生式系統(tǒng),控制策略 廣度優(yōu)先搜索策略 相當(dāng)于水平浸透法。完備的但效率低。 支持集消解策略 反向產(chǎn)生式系統(tǒng)。完備的，但不一定得到最優(yōu)解。 啟發(fā)式搜索策略 利用消解原理求解問題的經(jīng)驗，設(shè)計啟發(fā)函數(shù)。,2019/7/2,47,補充：解樹代換的一致性（一）,設(shè)有一個代換集u1,u2,，un，其中每個ui都是一個代換ti1/ vi1, ti2/ vi2,， tim(i)/ vim(i) 又設(shè)U1v11, , vim(1),， vn1, , vnm(n)（所有下邊的變量） U2t11, , tim(1),， tn1, , tnm(n) （所有上邊的項） 定義：代換集u1,u2,，un是一致的，當(dāng)且僅當(dāng)U1和U2是可合一的。 定義：u1,u2,，un的合一復(fù)合U是U1和U2的最一般合一。 解樹上所有代換是一致的，則該問題有解，最后的代換是合一復(fù)合U。,2019/7/2,48,補充：解樹代換的一致性（二）,例設(shè)有一個代換集u1,u2，其中 u1f(g(x1)/x3,f(x2)/x4 U1和U2是可合一的，其最一般合一是： Uf(g(x1)/x3,f(g(x1)/x4， g(x1)/x2,u2x4/x3,g(x1)/x2 U1=x3, x4, x3 ,x2 U2=f(g(x1) f(x2) ,x4 ,g (x1),2019/7/2,49,產(chǎn)生式系統(tǒng)的應(yīng)用實例,基于消解原理的產(chǎn)生式系統(tǒng) 基于自然演繹法的產(chǎn)生式系統(tǒng) 基于專用知識的產(chǎn)生式系統(tǒng),2019/7/2,50,基于自然演繹法的產(chǎn)生式系統(tǒng),消解原理產(chǎn)生式系統(tǒng)特點 優(yōu)點：形式單一，處理規(guī)則簡單。 缺點：太一般化，丟失了原公式重要語義信息，對應(yīng)用啟發(fā)搜索系統(tǒng)和人機交互帶來了困難；組合爆炸，難以直接使用。 自然演繹法 保持專家知識原始的邏輯形態(tài)，保留了控制信息。 推理規(guī)則復(fù)雜，但便于設(shè)計啟發(fā)函數(shù)。 推理過程直觀，便于理解。,2019/7/2,51,基于自然演繹法的產(chǎn)生式系統(tǒng),規(guī)則基產(chǎn)生式系統(tǒng) 事實 用非蘊含形式謂詞公式表示， 規(guī)則 用蘊含形式表示 F規(guī)則 前向推理系統(tǒng)中應(yīng)用 B規(guī)則 后向推理系統(tǒng)中應(yīng)用,2019/7/2,52,1、基于規(guī)則的向前推理系統(tǒng)（一）,基本原理 從代表初始事實的謂詞公式F0出發(fā)通過一組F規(guī)則F1，F(xiàn)2來證明目標(biāo)公式G成立。 初始事實F0 任意謂詞公式 前束范式表示；運用Skolem函數(shù)消去存在量詞；省去全稱量詞；得到任意與或型事實表達式，改名，使各主要合取項的變量應(yīng)不相同。 與或圖表示：析取部分用與節(jié)點表示合取部分用或節(jié)點表示,2019/7/2,53,1、基于規(guī)則的向前推理系統(tǒng)（二）,F規(guī)則 形如 L=W L為單一文字 W為任意與或型謂詞公式；W中用Skolem消去存在量詞，變元只受全稱量詞約束；改名，使不同規(guī)則具有不同變元，規(guī)則變元與事實變元也不同。 復(fù)雜規(guī)則化為簡單規(guī)則。,2019/7/2,54,1、基于規(guī)則的向前推理系統(tǒng)（三）,終止條件 用目標(biāo)謂詞G表示 G為文字的析取式（文字都為目標(biāo)文字）；用Skolem函數(shù)消去全稱量詞；消去存在量詞；改名，使同一變元在各目標(biāo)文字、規(guī)則、事實中最多出現(xiàn)一次。 推理基本過程 不斷將規(guī)則L=W利用匹配弧連接在與或圖的L葉結(jié)點上；目標(biāo)文字G本身可看作G =G作用在與或圖上； 一致解樹各個葉結(jié)點都終止在目標(biāo)節(jié)點，成功終止。,2019/7/2,55,1、基于規(guī)則的向前推理系統(tǒng)（四）,例:命題邏輯中一個定理證明問題 構(gòu)造一個向前的規(guī)則基推理系統(tǒng)來求解。 事實 F0： 規(guī)則 F1： F2 ： F3： 目標(biāo) G：,2019/7/2,56,1、基于規(guī)則的向前推理系統(tǒng)（五）,2019/7/2,57,1、基于規(guī)則的向前推理系統(tǒng)（六）,例:謂詞邏輯中一個定理證明問題 自然數(shù)都是大于0的整數(shù) 所有整數(shù)不是偶數(shù)就是奇數(shù) 偶數(shù)的一半是整數(shù) 所有自然數(shù)不是奇數(shù)就是一半為整數(shù)的數(shù)。 構(gòu)造一個向前的規(guī)則基推理系統(tǒng)來求解,2019/7/2,58,1、基于規(guī)則的向前推理系統(tǒng)（六）,一、預(yù)處理F0為事實表達式方法： （1）將公式化稱任意與或型前束范式，每個否定詞僅管 轄一個謂詞； （2）用Skolem函數(shù)去掉存在量詞并改名使主合取項之間無相同變量； （3）隱去全稱量詞。,2019/7/2,59,1、基于規(guī)則的向前推理系統(tǒng)（七）,二、預(yù)處理F1 F2為F規(guī)則方法： （1）暫時消去； （2）將公式化為前束范式，一個否定詞管轄一個謂詞； （3）用Skolem函數(shù)消去存在量詞； （4）改變變元名稱使其與其他公式不同； （5）恢復(fù)蘊含式。,2019/7/2,60,1、基于規(guī)則的向前推理系統(tǒng)（八）,三、處理目標(biāo)G： （1）用Skolem函數(shù)消去全稱量詞； （2）隱去存在量詞。,2019/7/2,61,1、基于規(guī)則的向前推理系統(tǒng)（九）,2019/7/2,62,2、基于規(guī)則的向后推理系統(tǒng)（一）,基本原理 從代表目標(biāo)的謂詞公式出發(fā)，通過一組B規(guī)則證明事實公式成立。 目標(biāo) 任意謂詞公式，Skolem函數(shù)消去全稱量詞；隱去存在量詞；改名，公式中主要析取項的變元應(yīng)不相同。 與或圖表示：與節(jié)點對應(yīng)合取；或節(jié)點對應(yīng)析取；根節(jié)點上任何后裔都為子目標(biāo)。,2019/7/2,63,2、基于規(guī)則的向后推理系統(tǒng)（二）,B規(guī)則 W=L； L為單一文字； W為任意與或型謂詞公式，變元受全稱量詞約束，變元改名。 復(fù)雜規(guī)則化為簡單規(guī)則。,2019/7/2,64,2、基于規(guī)則的向后推理系統(tǒng)（三）,推理過程 目標(biāo)謂詞公式的與或圖中有一節(jié)點標(biāo)為L，且可與L合一，則可將規(guī)則作用在該與或樹上。其結(jié)果使在與或樹上從L引出一條匹配弧，連接一個以L為根，表示W(wǎng)的與或圖， 為L與L的最一般合一。 終止條件 當(dāng)與或樹的一致解樹各個葉節(jié)點都終止在事實節(jié)點時，此產(chǎn)生式系統(tǒng)成功終止。,2019/7/2,65,2、基于規(guī)則的向后推理系統(tǒng)（四）,例:基于規(guī)則的向后推理系統(tǒng)。 給定事實為: Fido是狗 Fido不會吠叫 Fido會搖尾巴 Myetle會咪咪叫,2019/7/2,66,2、基于規(guī)則的向后推理系統(tǒng)（五）,已知規(guī)則為 目標(biāo)：存在貓不怕狗的現(xiàn)象，即,2019/7/2,67,2、基于規(guī)則的向后推理系統(tǒng)（六）,2019/7/2,68,3、F系統(tǒng)和B系統(tǒng)的對比（一）,2019/7/2,69,3、F系統(tǒng)和B系統(tǒng)的對比（一）,2019/7/2,70,產(chǎn)生式系統(tǒng)的應(yīng)用實例,基于消解原理的產(chǎn)生式系統(tǒng) 基于自然演繹法的產(chǎn)生式系統(tǒng) 基于專用知識的產(chǎn)生式系統(tǒng),2