1、人 工 智 能Artificial Intelligence (AI)曲維光南京師范大學計算機學院第2章 知識表示方法2.1 謂詞邏輯法2.2 狀態空間法2.3問題歸約法2.1 謂詞邏輯法數理邏輯（符號邏輯）是用數學方法研究形式邏輯的一個分支。它通過符號系統來表達客觀對象以及相關的邏輯推理。常用的是命題邏輯和謂詞邏輯謂詞邏輯是數理邏輯的基本形式，是基于謂詞分析的一種形式化（數學）語言人工智能中的謂詞邏輯法是指用一階謂詞來描述問題求解和定理證明（限于本課程）2.1.0 命題邏輯的復習 1、命題邏輯的基本概念命題 是能夠判斷真或假的陳述句通常用大寫字母來表示，如A, B, P, Q等命題的真假值一

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

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

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

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

6、域：由個體組成的集合。（個體）變量：定義在某一個論域上的變量。用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

7、,a)原子（謂詞）公式的（遞歸）定義：原子命題是原子公式如果t1,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”。 例1：“所有的機器人都是灰色的”，用謂詞邏輯可以表示成： （x）ROBOT(x) COLOR(x，g

8、ray)例2： “一號房間里有一個物體”，可以表示成 （x）INROOM（x , r1） 我們稱 x 是被量化了的變量，稱為約束變量。否則稱之為自由變量。一階謂詞：只允許對變量施加量詞，不允許對謂詞和函數施加量詞。2.1.2 謂詞公式1、謂詞公式的定義 利用連詞和量詞可以將原子（謂詞）公式組成復合謂詞公式，稱之為分子謂詞公式、謂詞合適公式、謂詞公式、合適公式。 （謂詞）合適公式 的（遞歸）定義：原子（謂詞）公式是合適公式。若 A 是合適公式，則 A 也是合適公式。若 A 和 B 是合適公式，則 AB 、AB 、AB 、AB 也是合適公式。若 A 是合適公式， x 為 A 的自由變元（變量），則

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

10、 P PQ 等價于 PQ狄.摩根定律 （PQ）等價于 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) (

11、x)P(x) 等價于 (y)P(y) (x)P(x) 等價于 (y)P(y)注釋：這兩個關系說明，在一個量化的表達式中的約束變量是一類虛元，它們可以用任何不在表達式中出現的其它變量來代替。 2.1.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的四個置換及其對應

12、的四個例子 （B是常量） s1=z/x, w/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, , sn/ym 其中，yj 是 x1,xn 之一者消去，對于任何 tj=xj 者消去，并記成。如

13、何求 ti :s1/y1 , , sm/ym如果 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

14、, w/y s2=A/y s1s2=z/x , 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) ,

15、 Bs = PA , f(B) , B Px , 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中各個公式的第一個符號同時向右比較，直到發現第一個彼此不盡相同的

16、符號為止，從 F 中的各個公式中取出那些以第一個不一致符號開始的最大的子表達式為元素，組成一個集合 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=(空置換，即不含元素的置換)。

17、 若 Fk 只有一個表達式，則算法終止，其中k就是要求的mgu。 找出 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

18、, x , f(g(y), P(z , h(z , u) , f(u)的最一般的合一者。解：我們根據合一算法一步一步地求出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 , 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