人工智能 搜索推理技術(shù)消解原理（課堂PPT）

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

2、充）3.6.7 Prolog 語(yǔ)言簡(jiǎn)介語(yǔ)言簡(jiǎn)介 （補(bǔ)充）（補(bǔ)充）.43.6 消解原理消解原理 第第2章中介紹章中介紹： 謂詞邏輯的基本知識(shí)謂詞邏輯的基本知識(shí) 合一算法（求最一般的一致置換或合一者合一算法（求最一般的一致置換或合一者mgu）本節(jié)本節(jié)：消解原理（或者歸結(jié)原理）消解原理（或者歸結(jié)原理）.53.6.1 子句集的求取子句集的求取如何將謂詞公式轉(zhuǎn)化為子句集，作為合一算法如何將謂詞公式轉(zhuǎn)化為子句集，作為合一算法的輸入（公式集）的輸入（公式集） 3.6.1.1 若干基本概念若干基本概念3.6.1.2 子句集的求取子句集的求取.63.6.1.1 若干基本概念若干基本概念1 自由變?cè)c約束變?cè)杂?/p>

3、變?cè)c約束變?cè)?2 前束范式與前束合取范式前束范式與前束合取范式3 斯科倫（斯科倫（Skolem）范式范式4 子句集子句集.7設(shè)設(shè)，是一個(gè)謂詞公式，將是一個(gè)謂詞公式，將量詞量詞記作記作（即即 或或 ）1 自由變?cè)c約束變?cè)杂勺冊(cè)c約束變?cè)?8如果如果中包含部分公式中包含部分公式 (x)，則則中變?cè)凶冊(cè)?x 的一的一切出現(xiàn)都稱為切出現(xiàn)都稱為 x 在在 中的約束出現(xiàn)，相應(yīng)地稱中的約束出現(xiàn)，相應(yīng)地稱 x 為為約束變?cè)s束變?cè)▎≡?、虛?gòu)變量、約束變量）（啞元、虛構(gòu)變量、約束變量）約束變?cè)s束變?cè)?9中不在任何量詞作用域內(nèi)的變?cè)胁辉谌魏瘟吭~作用域內(nèi)的變?cè)?x ，稱為變稱為變?cè)?x 在在 中的自

4、由出現(xiàn)，相應(yīng)地稱中的自由出現(xiàn)，相應(yīng)地稱 x 為為自由變自由變?cè)ㄗ杂勺兞浚ㄗ杂勺兞浚┳杂勺冊(cè)杂勺冊(cè)?10 量詞的作用域（轄域）是直接跟在它后面的公量詞的作用域（轄域）是直接跟在它后面的公式式 如果有括號(hào)，則是括號(hào)里的公式如果有括號(hào)，則是括號(hào)里的公式 如果沒(méi)有括號(hào)，則是最短的完整公式如果沒(méi)有括號(hào)，則是最短的完整公式說(shuō)明說(shuō)明：.11例例1： x ( P(x) ) x , y 都是約束變?cè)际羌s束變?cè)?： x ( P(x) (R(x, y) ) x 是約束變量，是約束變量，y 是自由變?cè)亲杂勺冊(cè)?12改名改名：將謂詞公式中一個(gè)變?cè)某闪硪粋€(gè)變?cè)簩⒅^詞公式中一個(gè)變?cè)某闪硪粋€(gè)變?cè)?/p>

5、，但是要求改名后的公式與原公式名，但是要求改名后的公式與原公式意義相同意義相同（真假值相同）（真假值相同）原則原則：改成的新的變?cè)欢ㄊ牵焊某傻男碌淖冊(cè)欢ㄊ橇吭~作用域量詞作用域中沒(méi)中沒(méi)有出現(xiàn)過(guò)的變?cè)òs束變?cè)妥杂勺冊(cè)┯谐霈F(xiàn)過(guò)的變?cè)òs束變?cè)妥杂勺冊(cè)┘s束變?cè)母拿s束變?cè)母拿蚧蜃兞康臉?biāo)準(zhǔn)化變量的標(biāo)準(zhǔn)化.13例例3： x ( P(x) (R(x, y) 除了除了 y 外，可以將外，可以將 x 改成任何變?cè)某扇魏巫冊(cè)?： x P(x) Q(y) 可以改成任何變?cè)?，包括可以改成任何變?cè)?，包?y（建議不要用建議不要用）.142 前束范式與前束合取范式前束范式

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

7、有前束析取范式。相應(yīng)地有前束析取范式.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 )左邊左邊沒(méi)有全稱量詞沒(méi)有全稱量詞，則取不，則取不在母式中出現(xiàn)的常量替代母式中的所有在母式中出現(xiàn)的常量替代母式中的所有 xk ，并并刪除前束中的刪除前束中的 xk消去存在量詞的規(guī)則消去存在量詞的規(guī)則

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

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

10、.82S的一個(gè)反演為：的一個(gè)反演為：PQ (S)PQ (S)PQ (S)PQ (S)Q Q P P S的另一個(gè)反演為：的另一個(gè)反演為：.83例例2：設(shè)：設(shè)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的一個(gè)反演的一個(gè)反演.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的一個(gè)反演為：的一個(gè)反演為： .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 對(duì)應(yīng)的對(duì)應(yīng)的消解式消解式：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 對(duì)應(yīng)的對(duì)應(yīng)的消解式消解式為：為：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 對(duì)應(yīng)的對(duì)應(yīng)的消解式消解式為：為：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) 最一般的合一者最一般的合一者為為= 對(duì)應(yīng)的對(duì)應(yīng)的消解式消解式為：為： 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) ( ) ( )反演過(guò)程：反演過(guò)程：.903.6.3 消解推理規(guī)則消解推理規(guī)則 （命題的特殊情況命題的特殊情況）從父子句求消解式的若干例子從父子句求消解式的若干例子1、假言推理假言推理.912、合并合并3、重言式重言式.924、空子句（矛盾）空子句（矛盾）5、鏈?zhǔn)剑ㄈ握摚╂準(zhǔn)剑ㄈ握摚?93( )( )B yC y( )B x3.6.4 含有變量的消解式（謂詞情況）含有變量的消解式（謂詞情況）先求最一般的合一者

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

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

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

17、解原理來(lái)構(gòu)造利用消解原理來(lái)構(gòu)造F1F2L的一個(gè)的一個(gè)反演反演 首先分別求出首先分別求出F1，F(xiàn)2和和 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構(gòu)成子句集構(gòu)成子句集（注意改名）（注意改名） 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) 證明過(guò)程：證明過(guò)程：.108 R(a) ，mgu=a/y R(a) mgu=a/z C(y)R(y) C(a) O(a) O(z)R(z).109前提前提：每一個(gè)儲(chǔ)蓄錢的人都獲得利息：每一個(gè)儲(chǔ)蓄錢的人都獲得利息結(jié)論結(jié)論：如果沒(méi)有利息，那么就沒(méi)有人去儲(chǔ)蓄錢：如果沒(méi)有利息，那么就沒(méi)有人去儲(chǔ)蓄錢例例2：用消

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

20、數(shù)量數(shù)量 y 的錢存入銀行的錢存入銀行.112將前提條件化成子句集將前提條件化成子句集前束前束范式范式前束合前束合取范式取范式.113前提條件的前提條件的子句集子句集(1) ( , )( )( ( )S x yM yI f x(2) ( , )( )( ,( )S u vM vE u f u.114結(jié)論取非：結(jié)論取非：化成子句集化成子句集改名、消除改名、消除 .115“結(jié)論非結(jié)論非”的子句集的子句集(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反演過(guò)程反演過(guò)程 ( )(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儲(chǔ)蓄問(wèn)題的反演樹(shù)（簡(jiǎn)單情況下使用）儲(chǔ)蓄問(wèn)題的反演樹(shù)（簡(jiǎn)單情況下使用）.1192 反演求解過(guò)程反演求解過(guò)程從反演

22、樹(shù)求取某一個(gè)問(wèn)題的答案，其過(guò)程為：從反演樹(shù)求取某一個(gè)問(wèn)題的答案，其過(guò)程為：將前提條件用謂詞表示出來(lái)，并化成子句集將前提條件用謂詞表示出來(lái)，并化成子句集 S.120將目標(biāo)公式（問(wèn)題）用謂詞表示出來(lái)，將目標(biāo)公式（問(wèn)題）用謂詞表示出來(lái)，把由目把由目標(biāo)公式的否定所產(chǎn)生的子句標(biāo)公式的否定所產(chǎn)生的子句及其及其非非（目標(biāo)公（目標(biāo)公式否定之否定）用式否定之否定）用析取連接詞析取連接詞相連組成一個(gè)相連組成一個(gè)新子句新子句（重言式），加到（重言式），加到 S 構(gòu)成新的子句集構(gòu)成新的子句集 S.121 對(duì)子句集對(duì)子句集 S ，進(jìn)行，進(jìn)行消解演繹消解演繹，直到得到某一，直到得到某一個(gè)個(gè)子句子句為止為止將此子句作為將此

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

24、T(z,x) T(z,y)目標(biāo)目標(biāo)：G： ( x)T(x,Zhang) G： ( x)T(x,Zhang)=( x) ( T(x,Zhang)用謂詞表示前提條件與目標(biāo)（問(wèn)題）：用謂詞表示前提條件與目標(biāo)（問(wèn)題）：.125前提的子句集前提的子句集：(1) T(Wang, Li)(2) C(Li, Zhang)(3) C(x,y) T(z,x) T(z,y)目標(biāo)的否定的子句及其非目標(biāo)的否定的子句及其非組成重言式：組成重言式：(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)消解演繹過(guò)程消解演繹過(guò)程.128(6) C(Li ,Zhang) T(Wang, Zhang) (4)(5) mgu=Wang/u, Zhang/y(7) T(Wang, Zhang) (6)(2) 問(wèn)題的答案問(wèn)題的答案(4) T(u,Zhang) T(u,Zhang

26、)(5) C(Li ,y) T(Wang,y)(2) C(Li, Zhang)mgu= .129例例：如果無(wú)論約翰：如果無(wú)論約翰(John)去哪里，菲多去哪里，菲多(Fido)也就去哪里，那么如果約翰在也就去哪里，那么如果約翰在學(xué)校學(xué)校里，則菲多里，則菲多在在哪里哪里？.130解：解：定義謂詞定義謂詞 AT(x , y)：人人 x 在在 y 處處.131前提條件（前提條件（F1、F2）與目標(biāo)（與目標(biāo)（G）為：為：前提條件的子句集：前提條件的子句集：.132目標(biāo)目標(biāo)的的“非非”及其子及其子句句將目標(biāo)的否定的子句及其非構(gòu)成將目標(biāo)的否定的子句及其非構(gòu)成重言式重言式：.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 消解過(guò)程消解過(guò)程(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反演樹(shù)反演樹(shù).1363.6.6 Horn子句集消解子句集消解 Horn子句集是一階謂詞公式的真子集子句集是一階謂詞公式的真子集 與一階謂詞邏輯具有同樣的表達(dá)能力與一階謂詞邏輯具有同樣的表達(dá)能力 Horn子句集的特點(diǎn)子句集的特點(diǎn)：.137如果對(duì)于謂詞公式如果對(duì)于謂詞公式 的任意一組指派（具體的一的任意一組指派（具體的一組值），公式組值），公式 的值均為真，則稱的值均為真，則稱 為為永真公永真公式式 ( x) ( )() ( )PPP xy P y .138如果對(duì)于謂詞公式如