人工智能 謂詞演算

1、第第2 2講講 基于謂詞邏輯的機(jī)器推理基于謂詞邏輯的機(jī)器推理 一階謂詞邏輯一階謂詞邏輯 歸結(jié)演繹推理歸結(jié)演繹推理 歸結(jié)原理的應(yīng)用歸結(jié)原理的應(yīng)用 Horn子句與子句與Prolog程序設(shè)計程序設(shè)計1第一節(jié)第一節(jié) 一階謂詞邏輯一階謂詞邏輯w 命題：凡可確定真假的陳述句稱為命題命題：凡可確定真假的陳述句稱為命題n可以取值可以取值“真真”（T）或或“假假”（F）n在一定的條件下，只能取其中一個值在一定的條件下，只能取其中一個值n例：例：l（1）北京是中國的首都）北京是中國的首都l（2）3 + 2 10l（3）1 + 11 = 100（根據(jù)制數(shù)）（根據(jù)制數(shù)）l（4）禁止吸煙）禁止吸煙 （祈使句）（祈使句）

2、l（5）本命題是假的）本命題是假的 （悖論）（悖論）2w 謂詞：是用來刻畫個體詞的性質(zhì)或個體詞之間的關(guān)系的詞（帶參量謂詞：是用來刻畫個體詞的性質(zhì)或個體詞之間的關(guān)系的詞（帶參量的命題叫謂詞）的命題叫謂詞）nn 元謂詞，元謂詞，P（x1, x2, x3, , xn）lP 是謂詞符號，代表一個確定的特征（一個參量）或關(guān)系（多個參量）是謂詞符號，代表一個確定的特征（一個參量）或關(guān)系（多個參量）lx1, x2, x3, , xn 稱為參量或項（個體常元或個體變元）稱為參量或項（個體常元或個體變元）l論述域（個體域）：個體變元的取值范圍論述域（個體域）：個體變元的取值范圍n例：例：l北京是一個城市北京是一

3、個城市 CITY（北京）北京）lx 是人是人 HUMAN（x）lA是是B的兄弟的兄弟 兄弟（兄弟（A，B）lx 大于大于 y G（x，y）n不帶個體變元的謂詞公式叫命題，命題是謂詞公式的特例不帶個體變元的謂詞公式叫命題，命題是謂詞公式的特例3w 邏輯連接詞：研究單個謂詞是不夠的，還必須研究多個謂詞之間的邏輯連接詞：研究單個謂詞是不夠的，還必須研究多個謂詞之間的關(guān)系，這需要引入邏輯連接詞關(guān)系，這需要引入邏輯連接詞n ：否定詞：否定詞l A A讀為讀為“非非A”A”，當(dāng)當(dāng)A A為真時，為真時， A A為假，當(dāng)為假，當(dāng)A A為假時，為假時， A A為真為真n：合取詞合取詞lA B讀為讀為“A并且并且

4、B”，當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A和和B都為真時，都為真時， A B為真，否則為真，否則A B為假為假n：析取詞析取詞lA B讀為讀為“A或者或者B”，當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A和和B都為假時，都為假時， A B為假，否則為假，否則A B為真為真4n：蘊(yùn)涵詞蘊(yùn)涵詞lA B讀為讀為“若若A則則B”，當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A為真，且為真，且B為假時，為假時， A B為假，否則為假，否則A B為真為真l在在A B中，中，A稱為前件，稱為前件，B稱為后件稱為后件n：等值詞：等值詞lA B讀為讀為“A等值于等值于B”，當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A和和B同為真或同為假時，同為真或同為假時， A B為真，為真，否則否則A B為假為假5w 量

5、詞：有些陳述句包含表示數(shù)量的詞，如量詞：有些陳述句包含表示數(shù)量的詞，如“所有所有”、“任一任一”、“存在存在”、“至少有一個至少有一個”等，為了表示這樣的陳述句，需引入新等，為了表示這樣的陳述句，需引入新的符號，稱為量詞的符號，稱為量詞n全稱量詞全稱量詞 l（ x ）表示表示 “ 對于所有的對于所有的 x ”l例：例：w凡是人都有名字凡是人都有名字 （ x ）（）（M （x） N（x）l（ x ）A（x） A（a1） A（a2） A（an），），若論域為有限集若論域為有限集合，合， 且且a1、 a2、 、an是論域中的所有個體是論域中的所有個體n存在量詞存在量詞 l（ x ）表示表示 “ 對于

6、某個對于某個 x ”l例：例：w存在不是偶數(shù)的整數(shù)存在不是偶數(shù)的整數(shù) （ x ）（）（G （x） E（x）l（ x ）A（x） A（a1） A（a2） A（an）n例：見例：見P56例例136w 項：項： （ P64 定義定義1）n（1）個體常元和個體變元都是項）個體常元和個體變元都是項n（2）f (t1, t2, , tn)是項，是項，f 是是 n 元函數(shù)，元函數(shù)， t1, t2, , tn 是項是項n（3）只有有限次使用（）只有有限次使用（1）、（）、（2）得到的符號串才是項）得到的符號串才是項w 原子公式：原子公式： （ P64 定義定義2）n設(shè)設(shè) P 為為 n 元謂詞符號，元謂詞符號，

7、 t1, t2, , tn 是項，則是項，則P（ t1, t2, , tn ）稱為原子稱為原子謂詞公式，簡稱原子公式謂詞公式，簡稱原子公式7w 謂詞公式：謂詞公式： （ P56 定義定義3）n（1）原子公式是謂詞公式）原子公式是謂詞公式n（2）若）若A、B是謂詞公式，則是謂詞公式，則 AB、AB、 A、AB、A B、 x A、 x A也是謂詞公式也是謂詞公式n（3）只有有限次應(yīng)用（）只有有限次應(yīng)用（1）、（）、（2）生成的公式才是謂詞公式）生成的公式才是謂詞公式l謂詞公式又稱為謂詞邏輯中的合式公式，記為謂詞公式又稱為謂詞邏輯中的合式公式，記為 Wff (well-formed formula)

8、l幾個概念：幾個概念：w轄域（轄域（P57）：）：緊接于量詞之后被量詞作用的（說明的）謂詞公式稱為該量詞的緊接于量詞之后被量詞作用的（說明的）謂詞公式稱為該量詞的轄域轄域w指導(dǎo)變元、約束變元和自由變元指導(dǎo)變元、約束變元和自由變元 （ P57）w改名規(guī)則（改名規(guī)則（ P57），），保證一個變元或者是約束變元，或者是自由變元保證一個變元或者是約束變元，或者是自由變元w例：例： x （H（x） G（x, y） x A（x） B（x）8w 合取范式：合取范式： （ P58定義定義4）lA為合取范式，為合取范式，B1 B2 B n ,其中其中 Bi 形如形如L1 L2 Lm, L j為原子公式或其否定為

9、原子公式或其否定w例例：（：（P（x） Q（y） （ P（x） Q（y） R（x，y） w任一謂詞公式均可化為與之等價的合取范式，但一般不唯一任一謂詞公式均可化為與之等價的合取范式，但一般不唯一w 析取范式：析取范式： （ P66 定義定義5）lA為析取范式，為析取范式，B1 B2 B n ,其中其中 Bi 形如形如L1 L2 Lm, L j為為原子公式或其否定原子公式或其否定w例例：（：（P（x） Q（y） （ P（x） Q（y） R（x，y） w任一謂詞公式均可化為與之等價的析取范式，但一般不唯一任一謂詞公式均可化為與之等價的析取范式，但一般不唯一9w 謂詞公式的永真（有效）、永假（不可滿

10、足）、可滿足：謂詞公式的永真（有效）、永假（不可滿足）、可滿足： （ P58定定義義6、7）n與個體域有關(guān)與個體域有關(guān)w 謂詞公式之間的關(guān)系謂詞公式之間的關(guān)系n常用邏輯等價式常用邏輯等價式 P59表表3.1l注意注意與與的區(qū)別，的區(qū)別，是等價符號，說明兩個謂詞公式之間的等價性，是等價符號，說明兩個謂詞公式之間的等價性，是邏輯連接詞，是謂詞公式的組成部分是邏輯連接詞，是謂詞公式的組成部分 n常用邏輯蘊(yùn)涵式常用邏輯蘊(yùn)涵式 P60 表表3.2l注意注意與與的區(qū)別，的區(qū)別， 是推導(dǎo)符號，說明由是推導(dǎo)符號，說明由左邊的謂詞公式可以推導(dǎo)出左邊的謂詞公式可以推導(dǎo)出右邊的謂詞公式，右邊的謂詞公式， 是邏輯連接

11、詞，是謂詞公式的組成部分是邏輯連接詞，是謂詞公式的組成部分 10w 自然演繹推理：自然演繹推理：n（1）將自然語言命題轉(zhuǎn)化為謂詞公式）將自然語言命題轉(zhuǎn)化為謂詞公式n（2）利用上面的邏輯等價式和邏輯蘊(yùn)涵式，可以進(jìn)行推理，得出一些）利用上面的邏輯等價式和邏輯蘊(yùn)涵式，可以進(jìn)行推理，得出一些隱含在謂詞公式中的結(jié)論隱含在謂詞公式中的結(jié)論l例：例：P61 例例4-6l自然演繹推理實施困難，推理規(guī)則太多、應(yīng)用規(guī)則需要很強(qiáng)的模式識別能自然演繹推理實施困難，推理規(guī)則太多、應(yīng)用規(guī)則需要很強(qiáng)的模式識別能力、中間結(jié)論呈指數(shù)增長力、中間結(jié)論呈指數(shù)增長l引入新的推理技術(shù)引入新的推理技術(shù)歸結(jié)演繹推理技術(shù)歸結(jié)演繹推理技術(shù)w歸

12、結(jié)歸結(jié)消解（消解（Resolution），），由由Robinson于于1965年提出，大大推動了自動定理年提出，大大推動了自動定理證明的發(fā)展證明的發(fā)展11練習(xí)：練習(xí)：w 1、設(shè)已知以下事實：、設(shè)已知以下事實：ABACBCDDQ求證：求證：Q為真。為真。12證明：證明：因為因為A，AC CB，C B CBC，BCD DD，DQ Q所以所以Q為真為真13w 2、設(shè)已知如下事實：、設(shè)已知如下事實：（1）凡是容易的課程小王都喜歡。）凡是容易的課程小王都喜歡。（2）C班的課程都是容易的。班的課程都是容易的。（3）ds 是是C班的一門課程。班的一門課程。求證：小王喜歡求證：小王喜歡 ds 這門課程。這門課

13、程。14證明：證明：事實事實 x （ EASY（x）LIKE（Wang，x） x （C（x） EASY（x）C（ds）LIKE（Wang，ds）因為因為 x （C（x） EASY（x）所以所以 C（ds） EASY（ds）所以所以 C（ds），）， C（ds） EASY（ds） EASY（ds）因為因為 x （ EASY（x）LIKE（Wang，x） ）所以所以 EASY（ds） LIKE（Wang，ds） 所以所以 EASY（ds），）， EASY（ds）LIKE（Wang，ds） LIKE（Wang，ds）15第二節(jié)第二節(jié) 歸結(jié)演繹推理歸結(jié)演繹推理w 建立子句集建立子句集n文字、子句、空子

14、句文字、子句、空子句 （P62 定義定義1）n建立謂詞公式建立謂詞公式 G 的子句集合的子句集合 （P62定義定義2）l例：例：P62例例3.7l例：例：P63 例例2 有關(guān)消去存在量詞有關(guān)消去存在量詞l子句集中各子句的關(guān)系是子句集中各子句的關(guān)系是 合取合取 n經(jīng)過變換后的子句集經(jīng)過變換后的子句集 S ，與謂詞公式與謂詞公式 G 并不等價并不等價n子句集的不可滿足子句集的不可滿足 （P64 定義定義3）nG不可滿足當(dāng)且僅當(dāng)不可滿足當(dāng)且僅當(dāng)S不可滿足（不可滿足（P64 定理定理1），即），即G永假是永假是S永假的充永假的充分必要條件分必要條件16練習(xí)：練習(xí)：P93 1、（1 1）p(x,y),Q

15、(u,v)p(x,y),Q(u,v)（2 2） p(x,y)Q(x,y)p(x,y)Q(x,y) （3 3）P(x,f(x)P(x,f(x) Q(x,f(x)R (x,f(x)Q(x,f(x)R (x,f(x) （4 4） P(x,z)Q(x,y)R(x,y)P(x,z)Q(x,y)R(x,y) （5 5）P(a,b,z,f(z),v,g(z,v),P(a,b,z,f(z),v,g(z,v),Q(a,b,f(t),s,g(t,s)Q(a,b,f(t),s,g(t,s) R(a,t,g(t,s) R(a,t,g(t,s) 17w 命題邏輯中的歸結(jié)原理命題邏輯中的歸結(jié)原理n在定理證明系統(tǒng)中，已知一

16、公式集在定理證明系統(tǒng)中，已知一公式集F1，F(xiàn)2，F(xiàn)n，要證明要證明W（定理）定理）是否成立，即要證明是否成立，即要證明W是公式集的邏輯結(jié)果，有兩種方法：是公式集的邏輯結(jié)果，有兩種方法：l1、證明、證明 F1 F2 Fn W 為永真式（見上一節(jié)）為永真式（見上一節(jié)）l2、（反證法）證明、（反證法）證明 F1 F2 Fn W 永假，即要證明對應(yīng)子句集永假，即要證明對應(yīng)子句集永假（不可滿足）永假（不可滿足）n幾個概念：（幾個概念：（P64 定義定義4、5）互補(bǔ)文字、歸結(jié)式（消解式）、親本子）互補(bǔ)文字、歸結(jié)式（消解式）、親本子句、消解基句、消解基 l例：例例：例3.9n歸結(jié)式是其親本子句的邏輯結(jié)果歸結(jié)

17、式是其親本子句的邏輯結(jié)果 P64 定理定理2l單向推導(dǎo)關(guān)系單向推導(dǎo)關(guān)系18n歸結(jié)原理：歸結(jié)原理： C1 C2 （C1-L1） （C2-L2）n互補(bǔ)文字進(jìn)行歸結(jié)得空子句（互補(bǔ)文字進(jìn)行歸結(jié)得空子句（L L =），），另另L L = F（假），假），故空子句即永假子句故空子句即永假子句n關(guān)于消解前后子句集的可滿足性關(guān)于消解前后子句集的可滿足性 P65 推論推論 （證明略）（證明略）n故：要證明一子句集永假，可以通過對子句集應(yīng)用消解原理得到空子故：要證明一子句集永假，可以通過對子句集應(yīng)用消解原理得到空子句來證明句來證明n運用歸結(jié)原理證明定理的例子：運用歸結(jié)原理證明定理的例子：P65 例例11、12l*

18、 歸結(jié)過程可以用一棵歸結(jié)過程可以用一棵 歸結(jié)演繹樹歸結(jié)演繹樹 表示表示19w 替換與合一替換與合一n為了對謂詞邏輯的子句集運用消解原理，即在子句集合中尋找含互補(bǔ)為了對謂詞邏輯的子句集運用消解原理，即在子句集合中尋找含互補(bǔ)文字的子句對，必須對子句進(jìn)行替換合一操作文字的子句對，必須對子句進(jìn)行替換合一操作n替換：替換：P66 定義定義6 t1/x1， t2/x2， ，t n /x nl對表達(dá)式的替換過程對表達(dá)式的替換過程 P66 定義定義7l表達(dá)式表達(dá)式 項、原子公式、文字、子句項、原子公式、文字、子句n兩個替換的乘積兩個替換的乘積 P66-67 定義定義8 l一部分仍是一部分仍是的替換對，只是的替

19、換對，只是的項被的項被作了替換；另一部分是作了替換；另一部分是中與中與不同的不同的那些變量對那些變量對l例：例例：例3.13l替換的乘積滿足結(jié)合律替換的乘積滿足結(jié)合律20n合一：合一：P67 定義定義9l是是 S 的一個合一的一個合一l其中其中S 是一個原子謂詞公式集，是一個原子謂詞公式集， 是一個替換是一個替換l滿足滿足 F1 = F2 = =Fn l一個公式集的合一一般不唯一一個公式集的合一一般不唯一n最一般的合一：最一般的合一：P67 定義定義10l是是 S 的一個合一的一個合一l對于對于S 的任何一個合一的任何一個合一，存在替換存在替換，使使 = l稱稱為為S 的最一般（最普通、最簡單

20、）合一的最一般（最普通、最簡單）合一 MGUw例：例例：例3.14lMGU 的替換限制最少，所產(chǎn)生的例更一般化，這有利于歸結(jié)過程的靈活使的替換限制最少，所產(chǎn)生的例更一般化，這有利于歸結(jié)過程的靈活使用用l一個公式集的最一般合一也可不唯一，如一個公式集的最一般合一也可不唯一，如 P（x），），P（y），y/x、 x/y都是它的最一般合一都是它的最一般合一21n差異集：差異集：P67 定義定義11l針對具有相同謂詞名的原子公式集針對具有相同謂詞名的原子公式集l例：例例：例3.15n合一算法：求非空有限具有相同謂詞名的原子公式集的最一般合一合一算法：求非空有限具有相同謂詞名的原子公式集的最一般合一lP

21、67-68l合一算法是解決兩個表達(dá)式匹配的問題，兩個表達(dá)式都可以含有變量，通合一算法是解決兩個表達(dá)式匹配的問題，兩個表達(dá)式都可以含有變量，通過算法求得過算法求得 MGU 并進(jìn)行替換后就可以得到匹配的例并進(jìn)行替換后就可以得到匹配的例l例：例例：例16、17l合一定理：合一定理： P68-69 定理定理3w可合一公式集一定存在最一般合一，用上述合一算法求得可合一公式集一定存在最一般合一，用上述合一算法求得22w 謂詞邏輯中的歸結(jié)原理謂詞邏輯中的歸結(jié)原理n歸結(jié)過程：歸結(jié)過程：l若若S 中的兩子句間有相同互補(bǔ)文字的謂詞，但它們的項不同，則必須找出中的兩子句間有相同互補(bǔ)文字的謂詞，但它們的項不同，則必須

22、找出對應(yīng)的不一致項對應(yīng)的不一致項l進(jìn)行變量替換合一操作，使它們的對應(yīng)項一致進(jìn)行變量替換合一操作，使它們的對應(yīng)項一致l求歸結(jié)式看能否導(dǎo)出空子句求歸結(jié)式看能否導(dǎo)出空子句n幾個概念：（幾個概念：（P69 定義定義12）謂詞邏輯中的二元歸結(jié)式（二元消解式）、）謂詞邏輯中的二元歸結(jié)式（二元消解式）、親本子句、消解文字親本子句、消解文字 l例：例例：例18、19l子句用文字的集合表示，各文字之間的關(guān)系是子句用文字的集合表示，各文字之間的關(guān)系是 析取析取 l首先對子句內(nèi)部的可合一文字進(jìn)行合一首先對子句內(nèi)部的可合一文字進(jìn)行合一23n因子、單因子因子、單因子 （ P69 定義定義13）l例：例例：例14n子句的

23、歸結(jié)（消解）式子句的歸結(jié)（消解）式 （ P69 定義定義14）n定理：謂詞邏輯中的消解式是它的親本子句的邏輯結(jié)果定理：謂詞邏輯中的消解式是它的親本子句的邏輯結(jié)果l謂詞邏輯中的歸結(jié)原理：謂詞邏輯中的歸結(jié)原理：C1 C2 （C1- L1 ）（ C2 - L2 ）n關(guān)于消解前后子句集的可滿足性關(guān)于消解前后子句集的可滿足性 P70 （同命題邏輯）（同命題邏輯）n故：要證明故：要證明F1 F2 Fn W 為永真式，可證明為永真式，可證明 F1 F2 Fn W 永假，這又可以通過對對應(yīng)子句集應(yīng)用消解原理得到空子句永假，這又可以通過對對應(yīng)子句集應(yīng)用消解原理得到空子句來證明（同命題邏輯）來證明（同命題邏輯）2

24、4n例：例例：例15、16n定理：歸結(jié)原理的完備性定理：歸結(jié)原理的完備性 （ P71）練習(xí)：練習(xí)：P93 3、（、（1）-（5）25第三節(jié)第三節(jié) 歸結(jié)原理的應(yīng)用歸結(jié)原理的應(yīng)用w 例例3.23：P71w 例例3.24：P72練習(xí)：練習(xí)： P94 5、6、26w 歸結(jié)策略歸結(jié)策略w 計算機(jī)實現(xiàn)歸結(jié)原理的一般算法：計算機(jī)實現(xiàn)歸結(jié)原理的一般算法：1.將子句集將子句集S置入置入CLAUSES表；表；2.若空子句若空子句NIL在在CLAUSES中，則歸結(jié)成功，結(jié)束。中，則歸結(jié)成功，結(jié)束。3.若若CLAUSES中存在可歸結(jié)子句對，則歸結(jié)之，并將歸結(jié)式放入中存在可歸結(jié)子句對，則歸結(jié)之，并將歸結(jié)式放入CLAUS

25、ES中；中；4.歸結(jié)失敗，退出。歸結(jié)失敗，退出。歸結(jié)策略的完備性歸結(jié)策略的完備性策略：刪除策略、支持集策略、線性歸結(jié)策略、輸入歸結(jié)策略、單元策略：刪除策略、支持集策略、線性歸結(jié)策略、輸入歸結(jié)策略、單元歸結(jié)策略、祖先過濾形策略。歸結(jié)策略、祖先過濾形策略。27歸結(jié)舉例Sam、Clyde和和Oscar是大象。關(guān)于它們，我們知道以下事實：是大象。關(guān)于它們，我們知道以下事實：1）Sam是粉紅色的；是粉紅色的；2）Clyde是灰色的且喜歡是灰色的且喜歡Oscar；3）Oscar是粉紅色或者是灰色（但不是兩種顏色）且喜歡是粉紅色或者是灰色（但不是兩種顏色）且喜歡Sam。用歸結(jié)法證明一個灰色大象喜歡一個粉紅色

26、大象。用歸結(jié)法證明一個灰色大象喜歡一個粉紅色大象。即證明：即證明： x yGray(x) Pink(y) Likes(x,y) 謂詞：謂詞：Gray(x), Pink(x), Like（x,y）事實：事實： 1）Pinky(Sam)2）Gray(Clyde) Like(Clyde,Oscar)3）(Gray(Oscar) Pink(Oscar)Likes(Oscar,Sam)28子句集：子句集：1）Pink(Sam)2）Gray(Clyde) 3）Like(Clyde,Oscar)4）Gray(Oscar) Pink(Oscar)5）Likes(Oscar,Sam)6） Gray(x) Pink(y) Likes(x,y)歸結(jié)：歸結(jié)：7） Gray(Oscar) Pink (Sam )5，6得得8） Gray(Clyde) Pink(Oscar) 3，6得得9） Pink(Oscar) Pink (Sam )4，7得得10） Pink(Oscar) 8，2得得11 ） Pink (Sam )9，10得得12）NIL1，10得得 29第四節(jié)第四節(jié) Horn子句與子句與Prolog程序設(shè)計程序設(shè)計w