《謂詞演算推理理論》PPT課件

《《謂詞演算推理理論》PPT課件》由會員分享，可在線閱讀，更多相關《《謂詞演算推理理論》PPT課件（43頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第四章 謂詞演算的推理理論 4.1 謂詞演算的永真推理系統(tǒng) 4.2謂詞演算的假設推理系統(tǒng) 4.3謂詞演算的歸結(jié)推理系統(tǒng) 4.3 謂詞演算的歸結(jié)推理系統(tǒng) 將前提集 S化成子句集， 將目標公式的否定 (即 B)化成子句集， 歸結(jié) 若能歸結(jié)出矛盾，則認為證明完成。 1， 2， ， k B 前提公式集 S 目標公式 B 引例 (p45) 已知： (1)無論誰能讀就有知識； (2)所有的海豚均沒有知識； (3)有些海豚有智慧。 試證明： (4)一些有智慧的個體不能讀。 x(R(x) L(x) x(H(x)L(x) x(H(x)I(x) x(I(x)R(x) 其中： R(x): x能讀； L(x): x有

2、知識； H(x): x是海豚； I(x): x有智慧 引例 (p45，提取子句 ) (1) R(x1) L(x1) (2) H(x2) L(x2) (3) H(a) (4) I(a) (5) I(x3)R(x3) 前提： x(R(x) L(x) x(H(x)L(x) x(H(x)I(x) 結(jié)論的否定 x(I(x)R(x) =x(I(x)R(x) 引例 (p45，歸結(jié) ) (1) R(x1) L(x1) (2) H(x2) L(x2) (3) H(a) (4) I(a) (5) I(x3)R(x3) (6) R(a) a/ x3(4)(5)歸結(jié) (7) L(a) a/ x1(6)(1)歸結(jié) (8

3、) H(a) a/ x2(7)(2)歸結(jié) (9) (8)(3)歸結(jié) 注意：歸結(jié)時使用了未討論過的 置換 的概念。 4.3.1 置換 置換 項對變量的替換。 (1)置換必須處處進行。 (2)要求沒有變量被含有同一變量的項來代替。 例 已知表達式 P(x) P(f(x) x不能用 f(x)替換 例 已知表達式 P(x， g(y)， b)，考察置換 : P(x， g(a)， b) a/y P(a， g(b)， b) a/x， b/y P(f(y)， g(a)， b) f(y)/x， a/y 一般地，置換可通過有序?qū)Φ募?t1/v1， t2/v2， ， tn/vn 來表達，其中 ti/vi表示變量

4、vi處處以項 ti來代替 。 4.3.2 歸結(jié)反演系統(tǒng) 一、謂詞演算公式子句的形成 二、 一般歸結(jié) 三、歸結(jié)反演系統(tǒng) 子句形成的 一般步驟 : (1)消去蘊含詞和等價詞 (2)否定深入 (3)約束變元改名 (4)化為前束范式 (5)消去存在量詞 (按 Skolem標準形 ) (6)消去全稱量詞 (直接去掉 ) (7)化為合取范式 (8)消去合取詞得子句集 ， (9)改變變量的名稱 (變量符號不重復使用 ) 例 求 xP(x)x(A(x)y(B(y)W(x， y)的子句 解 : (1)消去蘊含詞 xP(x)x(A(x)y(B(y)W(x， y) (2)約束變元改名 ： xP(x)z(A(z)y(

5、B(y)W(z， y) (3)化為前束范式 xzy(P(x)(A(z)(B(y)W(z， y) (4)消去存在量詞 (按 Skolem標準形 ) 原式 z(P(a)(A(z)(B(f(z)W(z， f(z) (5)消去全稱量詞 (直接去掉 ) 原式 P(a)(A(z)(B(f(z)W(z， f(z) (6)利用分配律化為合取范式 原式 P(a)(A(z)B(f(z) (A(z)W(z， f(z) (7)消去合取詞得子句集 P(a), A(z)B(f(z), A(z)W(z， f(z) (8)改變變量的名稱 ： P(a), A(z1)B(f(z1), A(z2)W(z2， f(z2) 關于改變變

6、量名的說明 : x(A(x) B(x)= xA(x) yB(y) 互補文字對的歸結(jié) 尋找一個置換使得子句上含有互補的文字對 (如 P和 P) 。 例 設有兩個子句 P(x， g(a)Q(y), P(z， g(a)Q(z) 可得若干歸結(jié)式如下： Q(y) Q(z) z/x Q(y) Q(x) x/z P(x， g(a)P(z， g(a) z/y 歸結(jié)反演系統(tǒng) 要證明定理 A1， A2， ， An B， 只要： 將 A1， A2， ， An, B分別化為子句集； 歸結(jié)出空子句 ,即證明其不可滿足。 第步等價于將 A1A2AnB化為子句集 例 (p47)已知知識： (1)每個作家均寫過作品； (2)

7、有些作家沒寫過小說； 結(jié)論：有些作品不是小說。 x(A(x)y(B(y)W(x， y) x(A(x)y(N(y)W(x， y) x(B(x)N(x) 證明：令 A(e)表示“ e為作家”； B(e)表示“ e為作品”； N(e)表示“ e為小說”； W(e1， e2)表示“ e1 寫了 e2” 求子句 : 每個作家均寫過作品 (1) x(A(x)y(B(y)W(x， y) ) = x(A(x) y(B(y)W(x， y) = x y (A(x) (B(y)W(x， y) x (A(x) (B(f(x)W(x， f(x) A(x) (B(f(x)W(x， f(x) = (A(x) B(f(x)

8、(A(x) W(x， f(x) 得到子句： A(x1)B(f(x1)， A(x2)W(x2， f(x2) 求子句 : 有些作家沒寫過小說 (2) x(A(x)y(N(y)W(x， y) = x(A(x)y(N(y) W(x， y) = x y (A(x) (N(y) W(x， y) y (A(a) (N(y) W(a， y) A(a) (N(y) W(a， y) 得到子句： A(a), N(y) W(a， y) 求子句 :有些作品不是小說 x(B(x)N(x) 否定結(jié)論得到： x(B(x)N(x) = x(B(x)N(x) B(x)N(x) 得到子句： B(x)N(x) (1) A(x1)B(

9、f(x1) (2) A(x2)W(x2， f(x2) (3) A(a) (4) N(y)W(a， y) (5) B(x)N(x) (6) A(x1) N(f(x1) f(x1)/x (5)(1)歸結(jié) (7) N(f(a) a/x1 (6)(3)歸結(jié) (8) W(a， f(a) f(a)/y (7)(4)歸結(jié) (9) A(a) a/x2 (8)(2)歸結(jié) (10) 口 (9)(3)歸結(jié) 補充習題 任何人如果喜歡步行，他就不喜歡乘汽車；每 個人或者喜歡乘汽車，或者喜歡騎自行車；有 的人不喜歡騎自行車，因而有的人不愛步行。 試用歸結(jié)原理證明之。 證明：令 P(e)表示“ e為人”； W(e)表示“

10、e喜歡步行”； D(e)表示“ e喜歡乘汽車”； R(e)表示“ e喜歡騎自行車” 證明 (續(xù) ) 則已知知識可以翻譯為： （ 1） x(P(x) (W(x) D(x) （ 2） x(P(x) (D(x) R(x) （ 3） x(P(x) R(x) 結(jié)論為： x(P(x) W(x) ) 結(jié)論的否定為： x( P(x) W(x) (1) P(x1)W(x1) D(x1) (2) P(x2)D(x2) R(x2) (3) P(a) (4) R(a) (5) P(x)W(x) (6) W(a) D(a) a/x1 (3)(1)歸結(jié) (7) P(a)D(a) a/x2 (4)(2)歸結(jié) (8) P(a

11、) D(a) a/y (5)(6)歸結(jié) (9) P(a) (8)(7)歸結(jié) (10) 口 (9)(3)歸結(jié) 4.3.3 霍恩子句邏輯程序 許多人工智能系統(tǒng)中使用的知識是由一般的 蘊 含表達式 來表示的。 如果把蘊含式 (PQ)R 化為等價的析取式 P Q R ， 往往會丟失可能包含在蘊含式中的重要的 超邏 輯的控制 信息。 基于規(guī)則的演繹系統(tǒng) 知識： 規(guī)則 一般知識，由 蘊含式 表示 事實 專門知識，由不包含蘊含式的 陳述 組成 基于規(guī)則的演繹系統(tǒng) 根據(jù)事實和規(guī)則來證明目標公式 一、子句的蘊含表示形式 一個子句 (析取式 )： C = P1P2 PnQ1Q2 Qm 可以表示為： (P1P2 P

12、n)(Q1Q2 Qm) 簡記為： P1， P2， ， Pn Q1， Q2， ， Qm Q1， Q2， ， Qm P1， P2， ， Pn 子句的類型 Q1， Q2， ， Qm P1， P2， ， Pn m 0,n 0 P1， P2， ， Pn m 0,n 0 Q1， Q2， ， Qm m 0,n 0 口 m=0, n 0 子句的 歸結(jié) 子句 1 子句 2 歸結(jié)式 PR QP QR P, QR QP QR P, QR P,Q PP,R P, QR P,Q QQ,R P, QR Q,R PR P P 口 相同的文字出現(xiàn)在兩邊即可以消除 每次歸結(jié)只能消除一對相同的文字 霍恩子句 定義：子句 L1L2

13、 Ln 中，如果至多只含有一個正文字， 那么該子句稱為霍恩子句。 霍恩子句 PQ1Q2 Qn可表為： PQ1， Q2， ， Qn 霍恩子句的類型 P Q1， Q2， ， Qn n0 P 上式 n=0 Q1， Q2， ， Qn n0 口 上式 n=0 過程 事實 目標 停機語句 過程名 過程調(diào)用，過程調(diào)用， ，過程調(diào)用 霍恩子句邏輯 由 霍恩子句 構(gòu)成的一階謂詞演算系統(tǒng) 執(zhí)行算法： 由目標中的一個 過程調(diào)用 與 事實 或 過程名 匹 配啟動，當匹配成功后，形成新的目標。 兩個霍恩子句的歸結(jié)是一個霍恩子句。 霍恩子句邏輯 要證明定理 A1， A2， ， An B， 只要： 將 A1， A2， ，

14、An, B分別化為 霍恩 子句 集； 歸結(jié)出空子句 ,即證明其不可滿足。 第步等價于將 A1A2AnB化為 霍恩 子句集 例 已知前提 (1) TOM在何處， MARY在何處 (2) MARY在何處，她的 COMPUTER在何處 (3) TOM在圖書館 試證“ MARY的 COMPUTER是在圖書館？” 解：霍恩子句為 (1) At(MARY,x) At(TOM,x) 過程 (2) At(COMPUTER,y) At(MARY,y) 過程 (3) At(TOM, Library) 事實 (4) At(COMPUTER, Library) 目標 解：霍恩子句邏輯程序為 (1) At(MARY,x

15、) At(TOM,x) 過程 (2) At(COMPUTER,y) At(MARY,y) 過程 (3) At(TOM, Library) 事實 (4) At(COMPUTER, Library) 目標 (5) At(MARY, Library) Library/y (2)(4)匹配 (6) At(TOM, Library) ) Library/x (1)(5)匹配 (7) 口 (3)(6)匹配 此程序證明了 MARY的 COMPUTER在圖書館。 例 所有羊都吃草 ,所有死羊都不吃草 . 所以 ,所有死羊都不是羊 . 解 : 知識翻譯為 x(羊 (x) 吃草 (x) x(死羊 (x) 吃草 (

16、x) x(死羊 (x) 羊 (x), 其否定為 x(死羊 (x)羊 (x) 霍恩子句邏輯程序及執(zhí)行過程如下： (1) 吃草 (x)羊 (x) 過程 (2) 死羊 (x1), 吃草 (x1) 目標 (3) 死羊 (a) 事實 (4) 羊 (a) 事實 (5) 死羊 (x), 羊 (x) x/x1(2)(1)歸結(jié) (6) 羊 (a) a/x(5)(3)歸結(jié) (7) 口 (6)(4)歸結(jié) 例 已知知識： (1)有些病人喜歡所有的醫(yī)生； (2)所有的病人均不喜歡庸醫(yī)； 試證明結(jié)論：所有的醫(yī)生均不是庸醫(yī)。 x(P(x)y(D(y)L(x， y) x(P(x)y(Q(y) L(x， y) x(D(x) Q

17、(x) 證明： 令 P(e)表示“ e為病人”； D(e)表示“ e為醫(yī)生”； Q(e)表示“ e為庸醫(yī)”； L(e1， e2)表示“ e1喜歡 e2”； x(D(x) Q(x) 霍恩子句邏輯程序及執(zhí)行過程如下： (1) P(a) 事實 (2) L(a,y) D(y) 過程 (3) P(x1), Q(y1), L(x1,y1） 目標 (4) D(b) 事實 (5) Q(b) 事實 (6) Q(y1), L(a， y1) a/x1(3)(1)歸結(jié) (7) Q(y)， D(y) y/y1(6)(2)歸結(jié) (8) Q(b) b/y(7)(4)歸結(jié) (9) 口 (8)(5)歸結(jié) 例 (p50-51)

18、已知知識： (1)桌子上的每一本書均是杰作； (2)寫出杰作的人是天才； (3)某個不出名的人寫了桌上某本書； 結(jié)論：某個不出名的人是天才。 解：令 A(e)表示“ e為桌上的書”； B(e)表示“ e為杰作”； C(e)表示“ e為天才”； D(e)表示“ e出名”； P(e)表示“ e為人”； W(e1， e2)表示“ e1 寫了 e2”. 例 (p50-51) 已知知識： (1)桌子上的每一本書均是杰作； (2)寫出杰作的人是天才； (3)某個不出名的人寫了桌上某本書； 結(jié)論：某個不出名的人是天才。 (1) x(A(x)B(x) (2) x (P(x) y(B(y) W(x, y)C(x

19、) (3) x (P(x) D(x) y(A(y) W(x， y) x(P(x) D(x) C(x) (1) x(A(x)B(x) (2) x (P(x) y(B(y) W(x, y)C(x) =x y(P(x)B(y) W(x， y)C(x) (P(x)B(y) W(x， y)C(x) (3) x (P(x) D(x) y(A(y) W(x， y) =xy(P(x) A(y) D(x) W(x， y) P(a) A(b) D(a) W(a， b) 否定結(jié)論得到 x(P(x) D(x) C(x) = x ( P(x) D(x) C(x) 解： (7)D(x3) P(x3)， C(x3) 過程

20、(8) P(a)， C(a) a/x3(5)(7)歸結(jié) (9) C(a) (8)(3)歸結(jié) (10) P(a),B(y), W(a， y) a/x2(9)(2)歸結(jié) (11) B(y)， W(a， y) (10)(3)歸結(jié) (12) A(y)， W(a， y) y/x1(11)(1)歸結(jié) (13) W(a， b) b/y(12)(4)歸結(jié) (14)口 (13)(6)歸結(jié) (1)B(x1)A(x1) 過程 (2)C(x2) P(x2)， B(y)， W(x2， y) 過程 (3)P(a) 事實 (4)A(b) 事實 (5) D(a) 目標 (6)W(a， b) 事實 例 已知知識如下： (1)每

21、個程序員均寫過程序； (2)病毒是一種程序 (3)有些程序員沒寫過病毒； 結(jié)論：有些程序不是病毒。 試用霍恩子句邏輯程序證明之。 證明： 令 P(e)表示 e為程序員； A(e)表示 e為程序； B(e)表示 e為病毒； W(e1,e2)表示 e1寫了 e2. 例 已知知識如下： (1)每個程序員均寫過程序； (2)病毒是一種程序 (3)有些程序員沒寫過病毒； 結(jié)論：有些程序不是病毒。 試用霍恩子句邏輯程序證明之。 （ 1） x(P(x) y(A(y) W(x,y) （ 2） x(B(x) A(x) （ 3） x(P(x) y(B(y) W(x,y) x(A(x) B(x) 提取子句 : （

22、1） x(P(x) y(A(y) W(x,y) = x y (P(x) (A(y) W(x,y) x (P(x) (A(y) W(x,f(x) P(x) (A(y) W(x,f(x) （ 2） x(B(x) A(x) （ 3） x(P(x) y(B(y) W(x,y) P(a) y(B(y) W(a,y) 結(jié)論的否定為： x(A(x) B(x) = x(A(x) B(x) (1) A(f(x1) P(x1) 過程 (2) W(x2, f(x2) P(x2) 過程 (3) A(x3) B(x3) 過程 (4) P(a) 事實 (5) B(y), W(a, y) 目標 (6) B(x4) A(x4) 過程 (7) A(y), W(a, y) y/x4(5)(6)歸結(jié) (8) P(x1), W(a, f(x1) f(x1)/y(7)(1)歸結(jié) (9) W(a, f(a) a/x1 (8)(4)歸結(jié) (10) P(a) a/x2 (9)(2)歸結(jié) (11) 口 (4)(10)歸結(jié)