人工智能謂詞演算.ppt

《人工智能謂詞演算.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《人工智能謂詞演算.ppt（32頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、第2講 基于謂詞邏輯的機(jī)器推理,一階謂詞邏輯 歸結(jié)演繹推理 歸結(jié)原理的應(yīng)用 Horn子句與Prolog程序設(shè)計(jì),2,第一節(jié) 一階謂詞邏輯,命題：凡可確定真假的陳述句稱為命題 可以取值“真”（T）或“假”（F） 在一定的條件下，只能取其中一個(gè)值 例： （1）北京是中國的首都 √ （2）3 + 2 > 10 （3）1 + 11 = 100 （根據(jù)制數(shù)） （4）禁止吸煙 （祈使句） （5）本命題是假的 （悖論）,3,謂詞：是用來刻畫個(gè)體詞的性質(zhì)或個(gè)體詞之間的關(guān)系的詞（帶參量的命題叫謂詞） n 元謂詞，P（x1, x2, x3, …, xn） P 是謂詞符號(hào)，代表一個(gè)確定的特征（一個(gè)參量）或關(guān)系（

2、多個(gè)參量） x1, x2, x3, …, xn 稱為參量或項(xiàng)（個(gè)體常元或個(gè)體變元） 論述域（個(gè)體域）：個(gè)體變元的取值范圍 例： 北京是一個(gè)城市 —— CITY（北京） x 是人 —— HUMAN（x） A是B的兄弟 ——兄弟（A，B） x 大于 y —— G（x，y） 不帶個(gè)體變元的謂詞公式叫命題，命題是謂詞公式的特例,4,邏輯連接詞：研究單個(gè)謂詞是不夠的，還必須研究多個(gè)謂詞之間的關(guān)系，這需要引入邏輯連接詞 ：否定詞 A讀為“非A”，當(dāng)A為真時(shí)， A為假，當(dāng)A為假時(shí)， A為真 ∧：合取詞 A ∧B讀為“A并且B”，當(dāng)且僅當(dāng)A和B都為真時(shí)， A ∧B為真，否則A ∧B為假 ∨：析取詞 A ∨ B

3、讀為“A或者B”，當(dāng)且僅當(dāng)A和B都為假時(shí)， A ∨ B為假，否則A ∨ B為真,5,→：蘊(yùn)涵詞 A → B讀為“若A則B”，當(dāng)且僅當(dāng)A為真，且B為假時(shí)， A → B為假，否則A → B為真 在A → B中，A稱為前件，B稱為后件 ?：等值詞 A ? B讀為“A等值于B”，當(dāng)且僅當(dāng)A和B同為真或同為假時(shí)， A ? B為真，否則A ? B為假,6,量詞：有些陳述句包含表示數(shù)量的詞，如“所有”、“任一”、“存在”、“至少有一個(gè)”等，為了表示這樣的陳述句，需引入新的符號(hào)，稱為量詞 全稱量詞 ? （ ? x ）表示 “ 對于所有的 x … ” 例： 凡是人都有名字 —— （ ? x ）（M （x） →

4、N（x）） （ ? x ）A（x）? A（a1）∧ A（a2） ∧… ∧ A（an），若論域?yàn)橛邢藜希?且a1、 a2、 … 、an是論域中的所有個(gè)體 存在量詞 ? （ ? x ）表示 “ 對于某個(gè) x … ” 例： 存在不是偶數(shù)的整數(shù) —— （ ? x ）（G （x） ∧ E（x）） （ ? x ）A（x）? A（a1）∨ A（a2）∨… ∨ A（an） 例：見P56例1—3,7,項(xiàng)： （ P64 定義1） （1）個(gè)體常元和個(gè)體變元都是項(xiàng) （2）f (t1, t2, …, tn)是項(xiàng)，f 是 n 元函數(shù)， t1, t2, …, tn 是項(xiàng) （3）只有有限次使用（1）、（2）得到的符號(hào)串才

5、是項(xiàng) 原子公式： （ P64 定義2） 設(shè) P 為 n 元謂詞符號(hào)， t1, t2, …, tn 是項(xiàng)，則P（ t1, t2, …, tn ）稱為原子謂詞公式，簡稱原子公式,8,謂詞公式： （ P56 定義3） （1）原子公式是謂詞公式 （2）若A、B是謂詞公式，則 A∧B、A∨B、 A、A→B、A? B、 ? x A、 ? x A也是謂詞公式 （3）只有有限次應(yīng)用（1）、（2）生成的公式才是謂詞公式 謂詞公式又稱為謂詞邏輯中的合式公式，記為 Wff (well-formed formula) 幾個(gè)概念： 轄域（P57）：緊接于量詞之后被量詞作用的（說明的）謂詞公式稱為該量詞的轄域 指導(dǎo)變元、

6、約束變元和自由變元 （ P57） 改名規(guī)則（ P57），保證一個(gè)變元或者是約束變元，或者是自由變元 例： ? x （H（x）→ G（x, y）） ∧ ? x A（x） ∧ B（x）,9,合取范式： （ P58定義4） A為合取范式，B1 ∧ B2 ∧ … ∧ B n ,其中 Bi 形如L1 ∨ L2 ∨ … ∨ Lm, L j為原子公式或其否定 例：（P（x） ∨ Q（y）） ∧ （ P（x） ∨ Q（y） ∨ R（x，y）） ∧… 任一謂詞公式均可化為與之等價(jià)的合取范式，但一般不唯一 析取范式： （ P66 定義5） A為析取范式，B1 ∨ B2 ∨ … ∨ B n ,其中 Bi 形如L1

7、 ∧ L2 ∧ … ∧ Lm, L j為原子公式或其否定 例：（P（x） ∧ Q（y）） ∨ （ P（x） ∧ Q（y） ∧ R（x，y）） ∨ … 任一謂詞公式均可化為與之等價(jià)的析取范式，但一般不唯一,10,謂詞公式的永真（有效）、永假（不可滿足）、可滿足： （ P58定義6、7） 與個(gè)體域有關(guān) 謂詞公式之間的關(guān)系 常用邏輯等價(jià)式 P59表3.1 注意?與?的區(qū)別，?是等價(jià)符號(hào)，說明兩個(gè)謂詞公式之間的等價(jià)性，?是邏輯連接詞，是謂詞公式的組成部分 常用邏輯蘊(yùn)涵式 P60 表3.2 注意?與?的區(qū)別， ?是推導(dǎo)符號(hào)，說明由?左邊的謂詞公式可以推導(dǎo)出?右邊的謂詞公式， ?是邏輯連接詞，是謂詞公式

8、的組成部分,11,自然演繹推理： （1）將自然語言命題轉(zhuǎn)化為謂詞公式 （2）利用上面的邏輯等價(jià)式和邏輯蘊(yùn)涵式，可以進(jìn)行推理，得出一些隱含在謂詞公式中的結(jié)論 例：P61 例4-6 自然演繹推理實(shí)施困難，推理規(guī)則太多、應(yīng)用規(guī)則需要很強(qiáng)的模式識(shí)別能力、中間結(jié)論呈指數(shù)增長 引入新的推理技術(shù)——?dú)w結(jié)演繹推理技術(shù) 歸結(jié)——消解（Resolution），由Robinson于1965年提出，大大推動(dòng)了自動(dòng)定理證明的發(fā)展,12,練習(xí)： 1、設(shè)已知以下事實(shí)： A B A→C B∧C→D D→Q 求證：Q為真。,13,證明： 因?yàn)? A，A→C ? C B，C ? B ∧C B∧C，B∧C

9、→D ? D D，D→Q ? Q 所以 Q為真,14,2、設(shè)已知如下事實(shí)： （1）凡是容易的課程小王都喜歡。 （2）C班的課程都是容易的。 （3）ds 是C班的一門課程。 求證：小王喜歡 ds 這門課程。,15,證明： 事實(shí) ? x （ EASY（x）→LIKE（Wang，x）） ? x （C（x）→ EASY（x）） C（ds） LIKE（Wang，ds） 因?yàn)?? x （C（x）→ EASY（x）） 所以 C（ds）→ EASY（ds） 所以 C（ds）， C（ds）→ EASY（ds）? EASY（ds） 因?yàn)?? x （ EASY（x）→LIKE（Wan

10、g，x） ） 所以 EASY（ds） →LIKE（Wang，ds） 所以 EASY（ds）， EASY（ds）→LIKE（Wang，ds） ? LIKE（Wang，ds）,16,第二節(jié) 歸結(jié)演繹推理,建立子句集 文字、子句、空子句 （P62 定義1） 建立謂詞公式 G 的子句集合 （P62定義2） 例：P62例3.7 例：P63 例2 有關(guān)消去存在量詞 子句集中各子句的關(guān)系是 合取 ∧ 經(jīng)過變換后的子句集 S ，與謂詞公式 G 并不等價(jià) 子句集的不可滿足 （P64 定義3） G不可滿足當(dāng)且僅當(dāng)S不可滿足（P64 定理1），即G永假是S永假的充分必要條件,17,練習(xí)： P93 1、 （1

11、）{p(x,y),Q(u,v)} （2）{p(x,y)∨Q(x,y)} （3）{P(x,f(x))∨ Q(x,f(x))∨R (x,f(x))} （4）{P(x,z)∨Q(x,y)∨R(x,y)} （5）{P(a,b,z,f(z),v,g(z,v)), Q(a,b,f(t),s,g(t,s))∨ R(a,t,g(t,s))},18,命題邏輯中的歸結(jié)原理 在定理證明系統(tǒng)中，已知一公式集F1，F(xiàn)2，…，F(xiàn)n，要證明W（定理）是否成立，即要證明W是公式集的邏輯結(jié)果，有兩種方法： 1、證明 F1 ∧ F2 ∧ … ∧ Fn →W 為永真式（見上一節(jié)） 2、（反證法）證明 F1 ∧ F2 ∧ … ∧

12、 Fn ∧ W 永假，即要證明對應(yīng)子句集永假（不可滿足） 幾個(gè)概念：（P64 定義4、5）互補(bǔ)文字、歸結(jié)式（消解式）、親本子句、消解基 例：例3.9 歸結(jié)式是其親本子句的邏輯結(jié)果 P64 定理2 單向推導(dǎo)關(guān)系,19,歸結(jié)原理： C1 ∧ C2 ? （C1-{L1}）∨ （C2-{L2}） 互補(bǔ)文字進(jìn)行歸結(jié)得空子句（L ∧ L =?），另L ∧ L = F（假），故空子句即永假子句 關(guān)于消解前后子句集的可滿足性 —— P65 推論 （證明略） 故：要證明一子句集永假，可以通過對子句集應(yīng)用消解原理得到空子句來證明 運(yùn)用歸結(jié)原理證明定理的例子：P65 例11、12 * 歸結(jié)過程可以用一棵 歸結(jié)

13、演繹樹 表示,20,替換與合一 為了對謂詞邏輯的子句集運(yùn)用消解原理，即在子句集合中尋找含互補(bǔ)文字的子句對，必須對子句進(jìn)行替換合一操作 替換：P66 定義6 {t1/x1， t2/x2，… ，t n /x n} 對表達(dá)式的替換過程 P66 定義7 表達(dá)式—— 項(xiàng)、原子公式、文字、子句 兩個(gè)替換的乘積 P66-67 定義8 一部分仍是θ的替換對，只是θ的項(xiàng)被λ作了替換；另一部分是λ中與θ不同的那些變量對 例：例3.13 替換的乘積滿足結(jié)合律,21,合一：P67 定義9 θ是 S 的一個(gè)合一 其中S 是一個(gè)原子謂詞公式集， θ是一個(gè)替換 滿足 F1θ = F2θ = …=Fnθ 一個(gè)公式集的合一

14、一般不唯一 最一般的合一：P67 定義10 σ是 S 的一個(gè)合一 對于S 的任何一個(gè)合一θ，存在替換λ，使 θ= σ? λ 稱σ為S 的最一般（最普通、最簡單）合一 MGU 例：例3.14 MGU 的替換限制最少，所產(chǎn)生的例更一般化，這有利于歸結(jié)過程的靈活使用 一個(gè)公式集的最一般合一也可不唯一，如{ P（x），P（y）}，{y/x}、 {x/y}都是它的最一般合一,22,差異集：P67 定義11 針對具有相同謂詞名的原子公式集 例：例3.15 合一算法：求非空有限具有相同謂詞名的原子公式集的最一般合一 P67-68 合一算法是解決兩個(gè)表達(dá)式匹配的問題，兩個(gè)表達(dá)式都可以含有變量，通過算法求得 M

15、GU 并進(jìn)行替換后就可以得到匹配的例 例：例16、17 合一定理： P68-69 定理3 可合一公式集一定存在最一般合一，用上述合一算法求得,23,謂詞邏輯中的歸結(jié)原理 歸結(jié)過程： 若S 中的兩子句間有相同互補(bǔ)文字的謂詞，但它們的項(xiàng)不同，則必須找出對應(yīng)的不一致項(xiàng) 進(jìn)行變量替換合一操作，使它們的對應(yīng)項(xiàng)一致 求歸結(jié)式看能否導(dǎo)出空子句 幾個(gè)概念：（P69 定義12）謂詞邏輯中的二元?dú)w結(jié)式（二元消解式）、親本子句、消解文字 例：例18、19 子句用文字的集合表示，各文字之間的關(guān)系是 析取 ∨ 首先對子句內(nèi)部的可合一文字進(jìn)行合一,24,因子、單因子 （ P69 定義13） 例：例14 子句的歸結(jié)（消解）

16、式 （ P69 定義14） 定理：謂詞邏輯中的消解式是它的親本子句的邏輯結(jié)果 謂詞邏輯中的歸結(jié)原理：C1 ∧ C2 ? （C1σ- {L1 σ }）∪（ C2 σ- {L2 σ }） 關(guān)于消解前后子句集的可滿足性 —— P70 （同命題邏輯） 故：要證明F1 ∧ F2 ∧ … ∧ Fn →W 為永真式，可證明 F1 ∧ F2 ∧ … ∧ Fn ∧ W 永假，這又可以通過對對應(yīng)子句集應(yīng)用消解原理得到空子句來證明（同命題邏輯）,25,例：例15、16 定理：歸結(jié)原理的完備性 （ P71） 練習(xí)： P93 3、（1）-（5）,26,第三節(jié) 歸結(jié)原理的應(yīng)用,例3.23：P71 例3.24：P72 練

17、習(xí)： P94 5、6、,27,歸結(jié)策略 計(jì)算機(jī)實(shí)現(xiàn)歸結(jié)原理的一般算法： 1.將子句集S置入CLAUSES表； 2.若空子句NIL在CLAUSES中，則歸結(jié)成功，結(jié)束。 3.若CLAUSES中存在可歸結(jié)子句對，則歸結(jié)之，并將歸結(jié)式放入CLAUSES中； 4.歸結(jié)失敗，退出。 歸結(jié)策略的完備性 策略：刪除策略、支持集策略、線性歸結(jié)策略、輸入歸結(jié)策略、單元?dú)w結(jié)策略、祖先過濾形策略。,28,歸結(jié)舉例,Sam、Clyde和Oscar是大象。關(guān)于它們，我們知道以下事實(shí)： 1）Sam是粉紅色的； 2）Clyde是灰色的且喜歡Oscar； 3）Oscar是粉紅色或者是灰色（但不是兩種顏色）且喜歡Sam。 用

18、歸結(jié)法證明一個(gè)灰色大象喜歡一個(gè)粉紅色大象。 即證明：?x ? y[Gray(x) ∧ Pink(y) ∧ Likes(x,y)], ? ? ∧ ? ∨,謂詞： Gray(x), Pink(x), Like（x,y） 事實(shí)： 1）Pinky(Sam) 2）Gray(Clyde) ∧Like(Clyde,Oscar) 3）(Gray(Oscar) ∨Pink(Oscar))∧Likes(Oscar,Sam),29,子句集：1）Pink(Sam) 2）Gray(Clyde) 3）Like(Clyde,Oscar) 4）Gray(Oscar) ∨Pink(Oscar) 5）Likes(Oscar,Sa

19、m) 6） Gray(x) ∨ Pink(y) ∨ Likes(x,y) 歸結(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）NIL 1，10得, ? ? ∧ ? ∨,30,第四節(jié) Horn子句與Prolog程序設(shè)計(jì),子句的蘊(yùn)含表示 P90 （3-1）—— （3-4、4’、4’’） 蘊(yùn)含型子句的歸結(jié) P90-91 正

20、、負(fù)文字歸結(jié)（在→的兩頭去找） Horn子句 定義：P91 定義1 蘊(yùn)含型Horn子句的三種類型：P91 蘊(yùn)含型Horn子句的歸結(jié) 例：P91 例1 注意歸結(jié)順序,31,Prolog 程序設(shè)計(jì) P30 Prolog 程序的語句均是 Horn 子句 事實(shí)——無條件子句 規(guī)則——條件子句 問題——目標(biāo)子句 Prolog 程序 P31-33 Prolog 程序的運(yùn)行機(jī)制 P33-35 SLD歸結(jié)： 從目標(biāo)子句開始進(jìn)行歸結(jié) 歸結(jié)順序是從左到右 控制策略是深度優(yōu)先 有回溯機(jī)制,32,Prolog 語言的優(yōu)缺點(diǎn)： 優(yōu)點(diǎn)：Prolog 語言是一種描述性語言，用 Prolog 語言進(jìn)行程序設(shè)計(jì)時(shí)，只需要描述待求解問題中的對象以及對象之間的關(guān)系的事實(shí)和變換規(guī)則。從這種意義上說，只需告訴計(jì)算機(jī)“做什么”，而不是“如何做”，大大提高了程序設(shè)計(jì)的效率。 缺點(diǎn)： Prolog 語言的解釋系統(tǒng)或編譯系統(tǒng)都是建立在適合于馮諾依曼計(jì)算機(jī)環(huán)境下的，最終仍然要轉(zhuǎn)化為純過程性的機(jī)器指令序列來執(zhí)行。因此顯著地增加了軟件開銷，使其處理速度難以大幅度提高，從而限制了它們的應(yīng)用范圍。 *** 上機(jī)環(huán)境 Visual Prolog 5.2,