1、.1人人 工工 智智 能能Artificial Intelligence (AI).2第第3章章 搜索推理技術搜索推理技術 3.1 圖的搜索策略圖的搜索策略3.2 盲目搜索盲目搜索3.3 啟發式搜索啟發式搜索3.4 與或樹搜索（與或樹搜索（補充補充）3.5 博弈樹搜索（博弈樹搜索（補充補充）3.6 消解原理消解原理.33.6 消解原理消解原理3.6.1 子句集的求取子句集的求取3.6.2 消解原理（補充）消解原理（補充）3.6.3 消解推理規則消解推理規則3.6.4 含有變量的消解式含有變量的消解式3.6.5 消解反演求解過程消解反演求解過程3.6.6 Horn子句集消解（補充）子句集消解（補

2、充）3.6.7 Prolog 語言簡介語言簡介 （補充）（補充）.43.6 消解原理消解原理 第第2章中介紹章中介紹： 謂詞邏輯的基本知識謂詞邏輯的基本知識 合一算法（求最一般的一致置換或合一者合一算法（求最一般的一致置換或合一者mgu）本節本節：消解原理（或者歸結原理）消解原理（或者歸結原理）.53.6.1 子句集的求取子句集的求取如何將謂詞公式轉化為子句集，作為合一算法如何將謂詞公式轉化為子句集，作為合一算法的輸入（公式集）的輸入（公式集） 3.6.1.1 若干基本概念若干基本概念3.6.1.2 子句集的求取子句集的求取.63.6.1.1 若干基本概念若干基本概念1 自由變元與約束變元自由

3、變元與約束變元 2 前束范式與前束合取范式前束范式與前束合取范式3 斯科倫（斯科倫（Skolem）范式范式4 子句集子句集.7設設，是一個謂詞公式，將是一個謂詞公式，將量詞量詞記作記作（即即 或或 ）1 自由變元與約束變元自由變元與約束變元.8如果如果中包含部分公式中包含部分公式 (x)，則則中變元中變元 x 的一的一切出現都稱為切出現都稱為 x 在在 中的約束出現，相應地稱中的約束出現，相應地稱 x 為為約束變元約束變元（啞元、虛構變量、約束變量）（啞元、虛構變量、約束變量）約束變元約束變元.9中不在任何量詞作用域內的變元中不在任何量詞作用域內的變元 x ，稱為變稱為變元元 x 在在 中的自

4、由出現，相應地稱中的自由出現，相應地稱 x 為為自由變自由變元元（自由變量）（自由變量）自由變元自由變元：.10 量詞的作用域（轄域）是直接跟在它后面的公量詞的作用域（轄域）是直接跟在它后面的公式式 如果有括號，則是括號里的公式如果有括號，則是括號里的公式 如果沒有括號，則是最短的完整公式如果沒有括號，則是最短的完整公式說明說明：.11例例1： x ( P(x) ) x , y 都是約束變元都是約束變元例例2： x ( P(x) (R(x, y) ) x 是約束變量，是約束變量，y 是自由變元是自由變元.12改名改名：將謂詞公式中一個變元名改成另一個變元：將謂詞公式中一個變元名改成另一個變元名

5、，但是要求改名后的公式與原公式名，但是要求改名后的公式與原公式意義相同意義相同（真假值相同）（真假值相同）原則原則：改成的新的變元名一定是：改成的新的變元名一定是量詞作用域量詞作用域中沒中沒有出現過的變元名（包括約束變元和自由變元）有出現過的變元名（包括約束變元和自由變元）約束變元的改名約束變元的改名或或變量的標準化變量的標準化.13例例3： x ( P(x) (R(x, y) 除了除了 y 外，可以將外，可以將 x 改成任何變元名改成任何變元名例例4： x P(x) Q(y) 可以改成任何變元名，包括可以改成任何變元名，包括 y（建議不要用建議不要用）.142 前束范式與前束合取范式前束范式

6、與前束合取范式 定義定義：設謂詞公式：設謂詞公式具有形式：具有形式： (1x1)(nxn) M其中：其中：i ( i = 1 , , n ) 是是 或或 M 是不包含量詞的謂詞公式是不包含量詞的謂詞公式則，稱則，稱是是前束范式前束范式 稱稱 (1x1)(nxn ) 為為前束前束 稱稱 M 為為母式母式.15定義定義：設謂詞公式：設謂詞公式是一個前束范式，如果是一個前束范式，如果的母式的母式具有形式：具有形式： （M11M12M1 n1） （M21M22M2 n2） (Mm1Mm2Mm nm）其中，其中，M i j 是原子公式或其非，則稱是原子公式或其非，則稱是是前束合取前束合取范式范式。相應地

7、有前束析取范式。相應地有前束析取范式.16前束范式前束范式：( x) ( y) ( z)(P(x)Q(y)R(z) 前束合取范式前束合取范式（交換律、（交換律、分配律分配律）( x) ( y) ( z)(R(z)P(x)(R(z)Q(y)例例：.173 斯柯倫范式斯柯倫范式 定義定義：前束中：前束中不含存在量詞不含存在量詞的前束范式稱為斯的前束范式稱為斯柯倫范式柯倫范式.18若若 xk (1kn )左邊左邊沒有全稱量詞沒有全稱量詞，則取不，則取不在母式中出現的常量替代母式中的所有在母式中出現的常量替代母式中的所有 xk ，并并刪除前束中的刪除前束中的 xk消去存在量詞的規則消去存在量詞的規則

8、或或 前束范式化成斯柯倫的前束范式化成斯柯倫的步驟步驟是：是：.19若若 xk (1 kn )左邊有全稱量詞左邊有全稱量詞 ( xs1) ( xs2)( xsr) ( 1r，1s1s2srk , il )的消解式的消解式消解演繹和反演的定義消解演繹和反演的定義：.77則稱則稱 c1, , cn 是從子句集是從子句集 S 到子句到子句 c 的一個的一個消消解演繹解演繹當當 c= 時的消解演繹稱為（消解）時的消解演繹稱為（消解）反演反演 .78把謂詞公式轉化為子句集把謂詞公式轉化為子句集S（所有子句的變量名不所有子句的變量名不同同）如空子句成為子句集的子句，則算法結束如空子句成為子句集的子句，則算

9、法結束在子句集中選取在子句集中選取兩個不同兩個不同的的可以消解可以消解的子句的子句ci , cj注：子句的個數限制注：子句的個數限制反演的基本算法反演的基本算法：.79計算計算 ci , cj 的消解式的消解式 rij把把 rij 加到子句集中，形成新的子句集加到子句集中，形成新的子句集S轉到轉到.80反演的流程圖反演的流程圖將謂詞公式化成子句集將謂詞公式化成子句集有空子句？有空子句？成功結束成功結束取兩個子句取兩個子句有消解式？有消解式？無解結束無解結束將消解式將消解式送到子句送到子句集集有有無無.81例例1：設子句集為：設子句集為S= PQ, PQ, PQ, PQ求求S的一個反演的一個反演

10、.82S的一個反演為：的一個反演為：PQ (S)PQ (S)PQ (S)PQ (S)Q Q P P S的另一個反演為：的另一個反演為：.83例例2：設：設S= P(z1,a)P(z1,x1)P(x1,z1), P(z2,f(z2)P(a, z2), P(f(z3),z3)P(a, z3) 求求S的一個反演的一個反演.84 P(z1,a)P(z1,x1)P(x1,z1) （S） P(z2,f(z2)P(a ,z2) （S） P(f(z3),z3)P(a ,z3) （S） S的一個反演為：的一個反演為： .85 取取c1=，c1= P(z2,f(z2) 取取c2=，c2= 公式集公式集為：為： P

11、(z1,a), P(z1,x1), P(x1,z1), P(a,z2) 最一般的合一者最一般的合一者為為=a/x1, a/z1, a/z2 對應的對應的消解式消解式：P(a, f(a) P(z1,a)P(z1,x1)P(x1,z1) P(z2,f(z2)P(a ,z2).86 取取c1=，c1= P(f(z3),z3) 取取c2=，c2= 公式集公式集為為 P(z1,a), P(z1,x1), P(x1,z1), P(a, z3) 最一般的合一者最一般的合一者為為=a/x1,a/z1,a/z3 對應的對應的消解式消解式為：為：P(f(a), a) P(z1,a)P(z1,x1)P(x1,z1)

12、 P(f(z3),z3)P(a ,z3).87取取c1=，c1= 取取c2=，c2=P(z1,a)P(z1,x1) 公式集公式集 P(x1,z1), P(a, f(a) 最一般的合一者最一般的合一者為為=a/x1,f(a)/z1 對應的對應的消解式消解式為：為：P(f(a),a) P(z1,a)P(z1,x1)P(x1,z1) P(a, f(a) .88取取c1= ，c1= 取取c2= ，c2= 公式集公式集: P(f(a) , a) 最一般的合一者最一般的合一者為為= 對應的對應的消解式消解式為：為： P(f(a), a) P(f(a),a).89 P(z1,a)P(z1,x1)P(x1,z

13、1) （S） P(z2,f(z2)P(a ,z2) （S） P(f(z3),z3)P(a ,z3) （S） P(a, f(a) ( ) P(f(a), a) ( ) P(f(a),a) ( ) ( )反演過程：反演過程：.903.6.3 消解推理規則消解推理規則 （命題的特殊情況命題的特殊情況）從父子句求消解式的若干例子從父子句求消解式的若干例子1、假言推理假言推理.912、合并合并3、重言式重言式.924、空子句（矛盾）空子句（矛盾）5、鏈式（三段論）鏈式（三段論）.93( )( )B yC y( )B x3.6.4 含有變量的消解式（謂詞情況）含有變量的消解式（謂詞情況）先求最一般的合一者

14、先求最一般的合一者mgu，再求消解式再求消解式例例1 置換置換 / x y( )C x.94例例2例例3.951 消解反演（數學定理的證明，論斷是否成立，消解反演（數學定理的證明，論斷是否成立，即即反演反演）2 反演求解過程（回答問題，即反演求解過程（回答問題，即消解演繹消解演繹）3.6.5 消解反演求解過程消解反演求解過程.961 消解反演消解反演消解反演證明定理的思路非常類似于數學中的消解反演證明定理的思路非常類似于數學中的反證法反證法.97給定一個公式集給定一個公式集 S（前提條件）和目標公式前提條件）和目標公式 L（結結論），通過反演來求證目標公式論），通過反演來求證目標公式 L，其證

15、明過程其證明過程為：為：否定否定 L ，得到得到 L把把 L 加到加到 S 中中把新形成的集合把新形成的集合 S ， L 化為子句集（化為子句集（簡化化簡化化法法）應用消解原理，試圖導出一個表示矛盾的應用消解原理，試圖導出一個表示矛盾的空子句空子句.98設設SF1,Fn 是前提條件，是前提條件，L是欲求證的結論是欲求證的結論則，從前提條件推出結論的問題，可以表示成：則，從前提條件推出結論的問題，可以表示成： F1Fn L （F1Fn ）L 并證明其并證明其永真永真（永遠成立）（永遠成立）反演證明過程的正確性反演證明過程的正確性：.99先將公式取先將公式取“非非” ： （F1Fn ）L）（F1F

16、n ） L F1Fn L利用消解原理來證明它是利用消解原理來證明它是永假永假的（即，構造一個的（即，構造一個反演）反演）.100實際中，我們可以將實際中，我們可以將 F1Fn L中的每一個部分化成子句集（中的每一個部分化成子句集（化法任選化法任選），合），合并后得到完整的子句集，然后利用消解原理導并后得到完整的子句集，然后利用消解原理導出空子句（反演）出空子句（反演）.101設有公式集：設有公式集：F1: ( x)(C(x)(W(x)R(x)F2: ( x)(C(x)O(x)L: ( x)(O(x)R(x)試證試證：L是是F1，F2的邏輯結果，即的邏輯結果，即F1F2L 例例1：.102利用消

17、解原理來構造利用消解原理來構造F1F2L的一個的一個反演反演 首先分別求出首先分別求出F1，F2和和 L 的子句集的子句集證明證明：.103( x)(C(x)(W(x)R(x)= ( x)(C(x)(W(x)R(x)= ( x)(C(x)W(x) )(C(x)R(x) 子句集子句集= C(x)W(x) , C(x)R(x) (未改名未改名)F1的前束合取范式與子句集的前束合取范式與子句集：.104 ( x)(C(x)O(x) = (C(a)O(a)子句集子句集= C(a), O(a) F2的前束合取范式和子句集的前束合取范式和子句集：.105( x)(O(x)R(x) = ( x)(O(x)R

18、(x)子句集子句集=O(x)R(x)L 的前束范式和子句集的前束范式和子句集：.106構成子句集構成子句集（注意改名）（注意改名） C(x)W(x), C(y)R(y), C(a)， O(a), O(z)R(z) .107 C(x)W(x) C(y)R(y) C(a) O(a) O(z)R(z) 證明過程：證明過程：.108 R(a) ，mgu=a/y R(a) mgu=a/z C(y)R(y) C(a) O(a) O(z)R(z).109前提前提：每一個儲蓄錢的人都獲得利息：每一個儲蓄錢的人都獲得利息結論結論：如果沒有利息，那么就沒有人去儲蓄錢：如果沒有利息，那么就沒有人去儲蓄錢例例2：用消

19、解反演證明：用消解反演證明.110S ( x , y )：某人某人 x 儲蓄儲蓄 y（數量）數量）M ( x )：x（數量）數量） 是錢是錢I( x )：x （數量）是利息數量）是利息E( x , y )：某人某人 x 獲得獲得 y （數量）數量）證明證明：設設.111前提前提：每一個儲蓄錢的人都獲得利息每一個儲蓄錢的人都獲得利息結論結論：如果沒有利息，那么就沒有人去儲蓄錢：如果沒有利息，那么就沒有人去儲蓄錢任何人任何人 x 將將 y 數量數量的錢存入銀行的錢存入銀行任何人任何人 x 得到得到 y 數量的利息數量的利息沒有沒有 x 數數量的利息量的利息任何人任何人 x 就不會將任何就不會將任何

20、數量數量 y 的錢存入銀行的錢存入銀行.112將前提條件化成子句集將前提條件化成子句集前束前束范式范式前束合前束合取范式取范式.113前提條件的前提條件的子句集子句集(1) ( , )( )( ( )S x yM yI f x(2) ( , )( )( ,( )S u vM vE u f u.114結論取非：結論取非：化成子句集化成子句集改名、消除改名、消除 .115“結論非結論非”的子句集的子句集(3) ( )I z(4) ( , )S a b(5) ( )M b.116完整的子句集完整的子句集(1) ( , )( )( ( )S x yM yI f x (2) ( , )( )( ,( )

21、S u vM vE u f u(3) ( )I z(4) ( , )S a b(5) ( )M b.117反演過程反演過程 ( )(6) ( , )( ) (1)(3) f xzS x yM ymgu (7) ( ) (6)(4) ,abxyM bmgu (8) (5)(7) mgu (1) ( , )( )( ( )S x yM yI f x (2) ( , )( )( ,( )S u vM vE u f u(3) ( )I z(4) ( , )S a b(5) ( )M b.118儲蓄問題的反演樹（簡單情況下使用）儲蓄問題的反演樹（簡單情況下使用）.1192 反演求解過程反演求解過程從反演

22、樹求取某一個問題的答案，其過程為：從反演樹求取某一個問題的答案，其過程為：將前提條件用謂詞表示出來，并化成子句集將前提條件用謂詞表示出來，并化成子句集 S.120將目標公式（問題）用謂詞表示出來，將目標公式（問題）用謂詞表示出來，把由目把由目標公式的否定所產生的子句標公式的否定所產生的子句及其及其非非（目標公（目標公式否定之否定）用式否定之否定）用析取連接詞析取連接詞相連組成一個相連組成一個新子句新子句（重言式），加到（重言式），加到 S 構成新的子句集構成新的子句集 S.121 對子句集對子句集 S ，進行，進行消解演繹消解演繹，直到得到某一，直到得到某一個個子句子句為止為止將此子句作為將此

23、子句作為問題的答案問題的答案.122例：例： 已知三個前提條件已知三個前提條件F1:：王王(Wang)先生是小李先生是小李(Li)的老師的老師F2：小李與小張小李與小張(Zhang)是同班同學是同班同學F3：如果如果x與與y是同班同學，則是同班同學，則x的老師就是的老師就是y的老師的老師問題：小張的老師是誰？問題：小張的老師是誰？.123解：解：定義謂詞定義謂詞T(x , y) : x 是是 y 的老師的老師C(x , y) : x 與與 y 是同班同學是同班同學.124前提前提：F1：T(Wang , Li)F2：C(Li , Zhang)F3： ( x) ( y) ( z) (C(x,y)

24、T(z,x) T(z,y)目標目標：G： ( x)T(x,Zhang) G： ( x)T(x,Zhang)=( x) ( T(x,Zhang)用謂詞表示前提條件與目標（問題）：用謂詞表示前提條件與目標（問題）：.125前提的子句集前提的子句集：(1) T(Wang, Li)(2) C(Li, Zhang)(3) C(x,y) T(z,x) T(z,y)目標的否定的子句及其非目標的否定的子句及其非組成重言式：組成重言式：(4) T(x,Zhang) T(x,Zhang) .126完整的子句集完整的子句集：(1) T(Wang, Li)(2) C(Li, Zhang)(3) C(x,y) T(z,

25、x) T(z,y)(4) T(u,Zhang) T(u,Zhang) .127(1) T(Wang, Li)(2) C(Li, Zhang)(3) C(x,y) T(z,x) T(z,y)(4) T(u,Zhang) T(u,Zhang)(5) C(Li ,y) T(Wang,y) (1)(3) mgu=Wang/z, Li/x)消解演繹過程消解演繹過程.128(6) C(Li ,Zhang) T(Wang, Zhang) (4)(5) mgu=Wang/u, Zhang/y(7) T(Wang, Zhang) (6)(2) 問題的答案問題的答案(4) T(u,Zhang) T(u,Zhang

26、)(5) C(Li ,y) T(Wang,y)(2) C(Li, Zhang)mgu= .129例例：如果無論約翰：如果無論約翰(John)去哪里，菲多去哪里，菲多(Fido)也就去哪里，那么如果約翰在也就去哪里，那么如果約翰在學校學校里，則菲多里，則菲多在在哪里哪里？.130解：解：定義謂詞定義謂詞 AT(x , y)：人人 x 在在 y 處處.131前提條件（前提條件（F1、F2）與目標（與目標（G）為：為：前提條件的子句集：前提條件的子句集：.132目標目標的的“非非”及其子及其子句句將目標的否定的子句及其非構成將目標的否定的子句及其非構成重言式重言式：.133子句集：子句集：(1) A

27、T(JOHN, )AT(FIDO, )(2) AT(JOHN, SCHOOL)(3) AT(FIDO, )AT(FIDO, )yyxx .134(4) AT(JOHN, )AT(FIDO, ) (3)(1) mgu=x / yxx (2) AT(JOHN, SCHOOL)(3) AT(FIDO, )AT(FIDO, )xx (1) AT(JOHN, )AT(FIDO, )yy 消解過程消解過程(5) AT(FIDO, SCHOOL) (4)(2) mgu=SCHOOL/ x.135(1) AT(JOHN, )AT(FIDO, )yy (3) AT(FIDO, )AT(FIDO, )xx (4)

28、 AT(JOHN, )AT(FIDO, ) xx mgu= / xy(2) AT(JOHN, SCHOOL)(5) AT(FIDO, SCHOOL)mgu=SCHOOL/ x反演樹反演樹.1363.6.6 Horn子句集消解子句集消解 Horn子句集是一階謂詞公式的真子集子句集是一階謂詞公式的真子集 與一階謂詞邏輯具有同樣的表達能力與一階謂詞邏輯具有同樣的表達能力 Horn子句集的特點子句集的特點：.137如果對于謂詞公式如果對于謂詞公式 的任意一組指派（具體的一的任意一組指派（具體的一組值），公式組值），公式 的值均為真，則稱的值均為真，則稱 為為永真公永真公式式 ( x) ( )() ( )PPP xy P y .138如果對于謂詞公式如