1、人 工 智 能Artificial Intelligence (AI)第2章 知識表示方法2.1 狀態空間法2.2 問題歸約法2.3 謂詞邏輯法五房間問題： 1、有5棟5種顏色的房子2、每一位房子的主人國籍都不同3、這5個人只喝一個牌子的飲料，只抽一個牌子的香煙，只養一種寵物4、沒有人有相同的寵物，抽相同牌子的香煙，喝相同的飲料誰養魚？ 已知條件：1、英國人住在紅房子里2、瑞典人養了一條狗3、丹麥人喝茶4、綠房子在白房子左邊5、綠房子主人喝咖啡6、抽PALLMALL煙的人養了一只鳥7、黃房子主人抽DUNHILL煙8、住在中間那間房子的人喝牛奶9、挪威人住在第一間房子10、抽混合煙的人住在養貓人

2、的旁邊11、養馬人住在DUNHILL煙的人旁邊12、抽BLUEMASTER煙的人喝啤酒13、德國人抽PRINCE煙14、挪威人住在藍房子旁邊15、抽混合煙的人的鄰居喝礦泉水房間號12345顏色國籍香煙飲料寵物挪威人牛奶4、綠房子在白房子左邊5、綠房子主人喝咖啡咖啡1、英國人住在紅房子里英國人7、黃房子主人抽DUNHILL煙11、養馬人住在DUNHILL煙的人旁邊DUNHILL馬3、丹麥人喝茶12、抽BLUEMASTER煙的人喝啤酒礦泉水2、瑞典人養了一條狗3、丹麥人喝茶12、抽BLUEMASTER煙的人喝啤酒13、德國人抽PRINCE煙瑞典人BLUEMASTER啤酒狗丹麥人茶德國人PRINCE

3、混合煙PALLMALL鳥貓魚推理的一般形式已知： 事實一，事實二， 如果事實一，那么結論一； 如果事實二，那么結論二；得到：結論一，結論二，如果將事實和規則抽象出來，不涉及具體內容，借助一些符號來表示，推理過程可形式化為： P：某已知事實 PQ：如果P，則Q 結論：Q 自然語言不適合計算機推理 如：小王不方便接電話，他方便去了。需要一種無歧義，方便存儲和表達的形式化符號表征體系邏輯經典邏輯： 命題邏輯、謂詞邏輯非經典邏輯： 不確定性推理、非單調性推理命題邏輯謂詞邏輯如果今天不下雨，我就去你家今天沒有下雨我去了你家 QPPQ命題邏輯核心思想：原子命題不可再分凡人都會死蘇格拉底是人蘇格拉底會死Ma

4、n(Socrates)Mortal(Socrates)x(Man(x)Mortal(x)2.3 謂詞邏輯法數理邏輯（符號邏輯）是用數學方法研究形式邏輯的一個分支。它通過符號系統來表達客觀對象以及相關的邏輯推理。常用的是命題邏輯和謂詞邏輯謂詞邏輯是數理邏輯的基本形式，是基于謂詞分析的一種形式化（數學）語言人工智能中的謂詞邏輯法是指用一階謂詞來描述問題求解和定理證明（限于本課程）2.3.0 命題邏輯的復習 1、命題邏輯的基本概念命題 是能夠判斷真或假的陳述句通常用大寫字母來表示，如A, B, P, Q等命題的真假值一般用 T 或 F 來表示 例：雪是白的。（陳述句，T）雪是藍的。（陳述句，F）雪是

5、黑的。（陳述句，F）他是學生。（陳述句，他泛指，無法判斷真假）你今天上課沒有？（疑問句）去北校區，請坐校車！（祈使句） 命題邏輯是研究命題及命題之間關系的符號邏輯系統。在命題邏輯中，表示單一意義的命題，稱之為原子命題。原子命題通過 “聯結詞” 構成 復合命題。五個聯結詞： “” 表示 “非”復合命題P為真，當且僅當P為假。 “” 表示 “合取”復合命題“PQ”為真，當且僅當P和Q都為真。 “” 表示 “蘊含”復合命題“PQ”為假，當且僅當P為真且Q為假。 “” 表示 “析取”復合命題“PQ”為真，當且僅當P、Q兩者之一為真。 “” 表示 “等價”復合命題“PQ”為真，當且僅當P、Q同時為真、或

6、者同時為假。 聯接詞的優先順序：非 、合取 、析取 、蘊含 、等價注：可以用括號表示優先級真值表 PQPPQPQPQPQFFTFFTTFTTFTTFTFFFTFFTTFTTTT命題變元：用符號P、Q等表示的不具有固定、具體含義的命題。它可以表示具有“真”、“假”含義的各種命題。命題變元可以利用聯結詞構成所謂的合適公式。 合適公式的定義若P為原子命題，則P為合適公式，稱為原子公式。若P是合適公式，則P也是一個合適公式。若P和Q是合適公式，則PQ、 PQ 、PQ 、PQ都是合適公式。經過有限次使用規則1、2、3，得到的由原子公式、聯結詞和園括號所組成的符號串，也是合適公式。對于合適公式，規定下列運

7、算優先級： 邏輯聯結詞的運算優先次序為： 、 、 、 同級聯結詞按出現順序優先運算 在命題邏輯中，主要研究推理的有效性。即：能否根據一些合適公式（前提）推導出新的合適公式（結論）。 一些合適公式（前提條件）合適公式（結論）？在命題邏輯中，最基本的單元是命題，它是作為一個不可分割的整體。例如：雪是黑的命題邏輯具有較大的局限性，不合適于表達比較復雜的問題。例：所有科學都是有用的（假設1）。數理邏輯是科學（假設2）。所以，數理邏輯是有用的（結論）。很明顯，我們無法用兩個假設推斷出結論。謂詞邏輯是命題邏輯的擴充和發展。它將一個原子命題分解成客體和謂詞兩個組成部分。例如： 雪 是黑的 客體 謂詞本課程主

8、要介紹一階謂詞邏輯。 2.3.1 謂詞演算 1、語法與語義謂詞邏輯的基本組成部分謂詞變量函數常量圓括號、方括號、花括號和逗號例“機器人（Robot）在第一個房間（Room1）內”，可以表示為： INROOM（ROBOT，r1）其中 INROOM是謂詞 ROBOT和r1是常量謂詞是指個體（客體）所具有的性質或者若干個體之間的關系。用大寫字母來表示。 個體是可以具體的（如: 小張、3、5）也可以是抽象的（如: x, y）。例：小明是學生，A表示是“是學生”，x表示“小明”，記作A(x)。x大于y，G表示“大于”，記作G（x, y）。論域：由個體組成的集合。（個體）變量：定義在某一個論域上的變量。用

9、x, y, z 來表示。函數（或函詞）：以個體為變量，以個體為值的函數。一般用小寫字母來表示，例如 f(x), f(x,a)。如果謂詞有 n 個變量，稱之為 n 元謂詞，并約定 0 元謂詞就是命題（謂詞的特例）。如果函數有 n 個個體，稱之為 n 元函數，并約定 0 元函數就是常量。常量習慣上用小寫字母來表示，如a, b, c。項的定義：常量是項變量是項如果 f 是n元函數，且t1 , tn(n1)是項，則 f (t1 , tn)也是項所有的項都必須是有限次應用上述規則產生的項的例子：常量：a變量：x函數：f(x,a) g(f(x,a)原子（謂詞）公式的（遞歸）定義：原子命題是原子公式如果t1

10、,tn(n1)是項，P是謂詞，則P(t1,tn)是原子公式其它表達式都不是原子公式 原子公式的例子1、原子公式：P（原子命題）2、項：x, a, f(x, a)，謂詞：P 原子公式：P(x, a, f(x,a)2、連詞和量詞聯結詞（連詞）就是命題邏輯中的五個，它們的含義也是一樣的。兩個量詞：全稱量詞，記作“x”,含義是 “對每一個x” 或“對一切x”。存在量詞，記作“x”，含義是 “存在某個x” 、“有一個x” 或者 “某些x”。 AllAExistE例1：“所有的機器人都是灰色的”，用謂詞邏輯可以表示成： （x）ROBOT(x) COLOR(x，gray)例2： “一號房間里有一個物體”，可

11、以表示成 （x）INROOM（x , r1） 我們稱 x 是被量化了的變量，稱為約束變量。否則稱之為自由變量。一階謂詞：只允許對變量施加量詞，不允許對謂詞和函數施加量詞。2.3.2 謂詞公式1、謂詞公式的定義 利用連詞和量詞可以將原子（謂詞）公式組成復合謂詞公式，稱之為分子謂詞公式、謂詞合適公式、謂詞公式、合適公式。 （謂詞）合適公式 的（遞歸）定義：原子（謂詞）公式是合適公式。若 A 是合適公式，則 A 也是合適公式。若 A 和 B 是合適公式，則 AB 、AB 、AB 、AB 也是合適公式。若 A 是合適公式， x 為 A 的自由變元（變量），則（x）A 和（x）A 都是合適公式。只有按上

12、述規則求得的公式才是合適公式。 例：任何整數或者為正或者為負。數學表達：對于所有的 x，如果 x 是整數，則 x 或者為正、或者為負。記作： I(x)：“ x 是整數”。 P(x)：“ x 是正數”。 N(x)：“ x 是負數”。謂詞公式： （x）（I(x) (P(x) N(x)）2、合適公式的性質 如果 P 和 Q 是合適公式，則由這兩個合適公式構成的合適公式的真值表與前面介紹的真值表相同。 如果兩個合適公式的真值表相同，則我們稱這兩個合適公式是等價的，可以用“”來表示。 對于命題合適公式和謂詞合適公式有下列等價關系： 否定之否定： （P） 等價于 P PQ 等價于 PQ狄.摩根定律 （PQ

13、）等價于 PQ （PQ）等價于 PQ分配律 P(QR) 等價于 (PQ)(PR) P(QR) 等價于 (PQ)(PR)交換律 PQ 等價于 QP PQ 等價于 QP結合律 (PQ)R 等價于 P(QR) (PQ)R 等價于 P(QR)逆否律 PQ 等價于 QP說明：上述等價關系對命題合適公式、謂詞合適公式都成立。對于謂詞合適公式有下列等價關系： (x)P(x) 等價于 (x)P(x) (x)P(x) 等價于 (x)P(x) (x)P(x)Q(x) 等價于 (x)P(x)(x)Q(x) (x)P(x)Q(x) 等價于 (x)P(x) (x)Q(x) (x)P(x) 等價于 (y)P(y) (x)

14、P(x) 等價于 (y)P(y)注釋：這兩個關系說明，在一個量化的表達式中的約束變量是一類虛元，它們可以用任何不在表達式中出現的其它變量來代替。 2.3.3 置換與合一 1、置換 置換的定義：形如 t1 / v1 , , tn / vn 的集合，稱為一個置換，其中 vi 是不同的變量，ti 是與 vi 不同的項。 例或例子的定義：設 t1/v1 , , tn/vn 為一個置換，E是一個原子謂詞公式。則E表示將E中的 vi 同時用 ti（i=1,n）代入后所得到的結果，E稱為E的一個例子。 例：表達式（原子謂詞公式）Px,f(y),B的四個置換及其對應的四個例子 （B是常量） s1=z/x, w

15、/ys2=A/y s3=q(z)/x, A/ys4=c/x, A/y Px, f(y), Bs1=Pz, f(w), BPx, f(y), Bs2=Px, f(A), B Px, f(y), Bs3=Pq(z), f(A), BPx, f(y), Bs4=Pc, f(A), BPx,f(y),B置換的合成：設t1/x1, ,tn/xn和s1/y1, ,sm/ym是兩個置換，則和的合成是如下置換： t1/x1 , ti/xi , tn/xn, s1/y1, , sm/ym 其中，若yj 是 x1,xn 之一者消去，對于任何 tj=xj 者消去，并記成。如何求 ti :s1/y1 , , sm/y

16、m如果 ti 出現 y1, ., ym中的變量 yi ， 則用其對應的項 si 來代替。例： = t1/x1 , t2/x2f(y)/x , z/y = s1/y1 , s2/y2 , s3/y3 = a/x , b/y , y/z =t1/x1 , t2/x2 , s1/y1 , s2/y2 , s3/y3 =f(b)/x , y/y , a/x , b/y , y/z =f(b)/x , y/z注意：置換的合成滿足結合律，不滿足交換律。 (s1s2)s3 = s1(s2s3) (滿足結合律） s1s2 s2s1 （不滿足交換律）例： s1=z/x , w/y s2=A/y s1s2=z/x

17、 , w/y , A/y=z/x , w/y s2s1=A/y, z/x , w/y=A/y , z/x2、合一 當某一個置換 s 作用于表達式集合 Ei 的每一個元素，此時我們用 Eis 來表示置換例子的集合。如果存在一個置換 s ，使得 E1s = E2s = = Eis = 則我們稱表達式集合 Ei 是可合一的，并稱 s 為Ei 的合一者。原因是它的作用是使集合 Ei 成為單一形式。 其中，Ei 是原子謂詞公式。例：表達式集合Px , f(y) , B , Px , f(B) , B的合一者為是 s = A/x , B/y Px , f(y) , Bs = PA , f(B) , B P

18、x , f(B) , Bs = PA , f(B) , B如果 s 是 Ei 的任意一個合一者，又存在某一個 s，使得 s = g s 或者 Ei s = Ei g s則 稱 g 是 Ei 的最通用（最一般）的合一者，記作mgu。 例：s = A/x , B/y 是表達式集合 Px , f(y) , B , Px , f(B) , B的一個合一者，該集合的最一般的合一者是： g = B/y3、合一算法 分歧集（或不一致集合）的定義。設有一非空有限公式集合 F = F1 , , Fn，從 F中各個公式的第一個符號同時向右比較，直到發現第一個彼此不盡相同的符號為止，從 F 中的各個公式中取出那些以

19、第一個不一致符號開始的最大的子表達式為元素，組成一個集合 D ，稱為 F 的分歧集（不一致集合）。 其中，F i ( i=1 , , n)是原子謂詞公式例：公式集：F=P(x , g( f(y , z) , x) , y), P(x , g( a , b) , b) , P(x , g( g(h(x) , a) , y) , h(x)分歧集為： D=f(y , z) , a , g(h(x) , a) 設 F 為非空有限表達式集合，則可以按下列步驟求出 mgu： 置 k=0 ，Fk = F ,k=(空置換，即不含元素的置換)。 若 Fk 只有一個表達式，則算法終止，其中k就是要求的mgu。 找

20、出 Fk 的分歧集 Dk 。 合一算法：若 Dk 中存在元素 ak 和 tk ，其中 ak 是變元，tk是項，且 ak 不在 tk 中出現，則置： k+1 =k tk / ak Fk+1 = Fk tk / ak k = k+1然后轉向。否則，繼續。算法終止，F的 mgu 不存在。 合一算法的流程圖k=0, Fk=F,k=|Fk|1？求得mgu、結束求出不一致集合有置換？求出新置換；更新公式集合與舊置換，k+無解、結束說明：1、合一算法是消解原理的基礎。2、合一算法中的公式集就是從謂詞合適公式化成的子句集。例：求F= P(a , x , f(g(y), P(z , h(z , u) , f(u

21、)的最一般的合一者。解：我們根據合一算法一步一步地求出mgu。第一步：k = 0, F0= F, 0= F0的分歧集合D0=a , z 置換：a/z 1 =0a/z = a/z F1 = F0 a/z = P(a , x , f(g(y), P(a , h(a , u) , f(u) k=1 F1 不是單一表達式F=P(a,x,f(g(y)， P(z,h(z,u),f(u)第二步：D1x , h(a,u) 置換：h(a , u)/x 21h(a , u)/x=a/z , h(a , u)/x F2=F1h(a , u)/x =P(a , h(a , u) , f(g(y), P(a , h(a

22、 , u) , f(u) k=2F=P(a,x,f(g(y)， P(a,h(a,u),f(u)第三步：D2g(y) , u 置換：g(y)/u 32g(y)/u=a/z , h(a,g(y)/x , g(y)/u F3=F2g(y)/u=P(a , h(a , g(y) , f(g(y) k=3F=P(a, h(a,u), f(g(y)， P(a, h(a,u), f(u) F3是單一表達式，所以 3a/z , h(a , g(y)/x , g(y)/u是 F 的最一般合一者 例：F=Q(f(a) , g(x) , Q(y , y)是否可合一？第一步：k=0, F0=F, 0= F0的分歧集合

23、D0=f(a) , y 置換：f(a)/y 10f(a)/y= f(a)/y F1=F0 f(a)/y =Q(f(a) , g(x) , Q(f(a) , f(a) k=1 F1不是單一表達式第二步：D1g(x), f(a) 不存在著變量，所以不可合一。F1=Q(f(a),g(x), Q(f(a),f(a)練習：求公式集 W= Q(x , y, z) , Q(a , f(b) , a) 的最一般的合一者? 其中，x, y, z為變量，a為常量，f 為函數第一步：k=0, W0=W, 0= W0的分歧集合D0=a , x 置換： a / x 10a/x= a / x W1=W0 a / x =Q

24、(a , y, z) , Q(a , f(b) , a) k=1 W1不是單一表達式 Q(x , y, z) , Q(a , f(b) , a) 第二步：W1的分歧集合D1=f(b) ，y 置換： f(b) / y 21 f(b) / y = a / x , f(b) / y W2=W1 f(b) / y =Q(a , f(b), z) , Q(a , f(b) , a) k=2 W2不是單一表達式 Q(a , y, z) , Q(a , f(b) , a) 第三步：W2的分歧集合D0=a , z 置換： a / z 32 a / z = a / x , f(b) / y , a / z W3

25、=W2 a / z =Q(a , f(b), a) k=3 W3是單一表達式，mgu= 3 = a / x , f(b) / y , a / z Q(a , f(b), z) , Q(a , f(b) , a) 謂詞的一致性，P()與Q()， 不可以常量的一致性，P(a, )與P(b,.)， 不可以；變量，P(a, .)與P(x, )， 可以變量與函數，P(a, x, .)與P(x, f(x), )，不可以；但P(a, x, )與P(x, f(y), )，可以是不能同時消去兩個互補對，PQ與PQ的空，不可以先進行內部簡化（置換、合并）置換和合一的注意事項：例如假設用下列定義P（x, a） 表示某人x的職業為a；A（y, b） 表示Y的年齡為b；GE（x,y） 表示 x yS（z, c） 表示z的性別為c；W（w, d） 表示w的工齡為d；E（u，e） 表示u的文化程度為e；R（t） 表示t已退休。（1）事實知識的描述應用舉例：以下事實可以用謂詞邏輯表示為：王的職業是教師： P（Wang, Teacher）張是工程師： P（Zhang, Engineer） 王是男性： S（Wang，Male）趙是男性： S（Zhao，Male）張是女性： S（Zhang，Female）趙70歲： A（Zhao，70）張工齡38年： W（Zhang，38）王工齡30年： W（Wang，30