人工智能原理及其應(yīng)用.ppt

1、ARTIFICIAL INTELLIGENCE,人工智能原理及其應(yīng)用 GOYAL990.NET 2001.9,第三章確定性推理,一、推理的基本概念 定義 推理：已知事實 結(jié)論 知識推理是指在計算機或智能機器中，在知識表達的基礎(chǔ)上，利用形式化的知識模型，進行機器思維求解問題，實現(xiàn)狀態(tài)轉(zhuǎn)移的智能操作序列。,策略,第三章確定性推理,基本問題：推理的方法和控制的策略 推理方法及分類 根據(jù)知識表示方式分類 “圖搜索”方法 如：狀態(tài)空間法、與或圖 “邏輯論證”方法 如：謂詞邏輯等 推理算法與推理步驟 算法：完備性 如寬度優(yōu)先 步驟：不完備 如深度優(yōu)先 啟發(fā)式與非啟發(fā)式 啟發(fā)性知識：即解決問題的策略、技巧、

2、竅門等實踐經(jīng)驗和知識。例：瞎子爬山,第三章確定性推理,按邏輯基礎(chǔ) 演繹推理：一般到個別 三段論 歸納推理：個別到一般 完全歸納、不完全歸納 枚舉歸納、類比歸納等 默認（缺省）推理：知識不完備 按知識的確定性 確定性推理：知識和結(jié)論都是精確的 非確定性推理,第三章確定性推理,按推理過程的單調(diào)性 單調(diào)推理 非單調(diào)推理：加入新知識會否定原來推出的結(jié)論，使推理過程回退 控制策略及分類 推理的控制策略：指如何使用領(lǐng)域知識使推理過程盡快達到目標的策略。 推理策略：推理方向控制策略、求解策略、限制策略、沖突消解策略 搜索策略（第五章）：推理線路、推理效果、推理效率,第三章確定性推理,正向推理 知識庫、綜合數(shù)

3、據(jù)庫、推理機 正向推理的過程（圖3-1） 優(yōu)點：直觀。適合于診斷、監(jiān)控、設(shè)計、預(yù)測等領(lǐng)域。 缺點；推理無明確目標，效率較低。 逆向推理 逆向推理的過程（圖3-2） 優(yōu)點：目標明確，效率較高 缺點：情況不明時，選擇假設(shè)目標的盲目性比較大，可能多次提出假設(shè)，降低系統(tǒng)效率,第三章確定性推理,混合推理 方法 先正后逆（圖3-3） 先逆后正（圖3-4） 雙向（圖3-5） 適用場合 事實不夠充分 正向推理推出的結(jié)論可性度不高 希望得到更多結(jié)論,第三章確定性推理,沖突消解策略 基本思想：對可用知識排序 特殊知識優(yōu)先 新鮮知識優(yōu)先 差異性大的知識優(yōu)先 領(lǐng)域特點優(yōu)先 上下文關(guān)系優(yōu)先 前提條件少者優(yōu)先,第三章確定

4、性推理,二、推理的邏輯基礎(chǔ) 基本概念 謂詞公式的解釋 對所包含的常量、函數(shù)、謂詞賦值 謂詞公式的永真性與可滿足性 非空個體域上的任一解釋（在D上永真）；任何非空個體域 （永真） 謂詞公式的等價性與永真蘊含性 在D上等價與等價PQ ,永真蘊含PQ 常用的等價式、永真蘊含式（牢記）,第三章確定性推理,謂詞公式的范式 前束范式： 前綴 母式 置換與合一 已知：W1(A), ( x)(W1(x) W2(x) 結(jié)論：W2(A) 置換：在表達式中用置換項置換變量。 t1/x1, t2/x2, ,tn/xn,量詞串,無量詞公式,第三章確定性推理,置換的例 置換的合成 (Ls1)s2=L(s1s2) 置換一般

5、不可交換 s1s2s2s1 例： 表達式P(x,g(y),c) 置換 s1=f(y)/x,z/y s2=a/x,b/y,y/z Ps1=P(f(z),g(z),c) Ps2=P(a,g(b),c) Ps1s2=P(f(b),g(b),c) s1s2=f(b)/x,b/y,y/z Ps2s1=P(a,g(b),c) s2s1=a/x,b/y,第三章確定性推理,合一：尋找項對變量的置換，以使表達式一致。 Pg(x),f(y),B,Ph(x),f(B),B不可合一 盡管s=A/x,B/y是Px,f(y),B,Px,f(B),B的一個合一者，但是最簡單的合一者是g=B/y 最一般(通用)合一者(mgu

6、)：置換最少的變量以使表達式一致。 分歧集： 例：F=P(x,y,z),P(x,f(a),h(b)的分歧集 D1=y,f(a) D2=z,h(b),第三章確定性推理,合一算法(p89) 例： F=P(a,x,f(g(y),P(z,h(z,u),f(u),第三章確定性推理,三、自然演繹推理 已知事實 結(jié)論 注意肯定前件、否定后件的錯誤 例3.8： 定義謂詞：Prog(x) Like(x,y) Lang(x) 事實：Prog(x) Like(Wang,x) ( x) (Lang(x) Prog(x) ) Lang(C) 結(jié)論：Like(Wang,C),經(jīng)典邏輯推理規(guī)則,第三章確定性推理,四、歸結(jié)演

7、繹推理（Robinson消解原理） 對前提P，結(jié)論Q，證明P Q永真 P Q與PQ等價 只需證明 （PQ）即P Q不可滿足。,第三章確定性推理,子句集 概念 文字：原子謂詞公式及其否定 子句：任何文字的析取式 空子句NIL：永假、不可滿足 化為子句集 消去蘊涵和等價符號 減少否定符號的轄域 對變量標準化，保證每個量詞有其唯一的啞元 消去存在量詞 skolem函數(shù),第三章確定性推理,化為前束形 前綴（全稱量詞串） 母式（元量詞公式） 把母式化為合取范式 消去全稱量詞 消去連詞符號 更換變量名稱,第三章確定性推理,例（ x）P(x) ( y)P(y)P(f(x,y)( y)Q(x,y)P(y),第

8、三章確定性推理,二、p9398: 只要求記住兩條有用的結(jié)論： 原謂詞公式不可滿足，其標準子句集則一定不可滿足。 Herbrand(海伯倫)定理：子句集S不可滿足的充要條件是存在一個有限的不可滿足的基子句集S。,第三章確定性推理,三、魯賓遜（ Robinson ）歸結(jié)原理 基本思想 否定結(jié)論，加入前提子句集，應(yīng)用歸結(jié)原理，是否能導出空子句，若存在，證明否定結(jié)論錯誤，即原結(jié)論得證。（反證法） 實際上歸結(jié)原理不僅應(yīng)用在定理證明，還可應(yīng)用于問題求解過程。 歸結(jié)原理 互補文字：P、 P 歸結(jié)式：分為命題邏輯歸結(jié)和謂詞邏輯歸結(jié).,第三章確定性推理,命題邏輯歸結(jié) 定義： L1、L2分別是子句C1、C2中的文

9、字， 并且L1、L2 互補，即L1 L2 ，將它們從C1、C2中消去，并將兩子句余下部分按析取關(guān)系組成新子句C12，即歸結(jié)式。 C1、C2叫做親本子句。 例：p99 3.15、3.16、3.17,第三章確定性推理,定理：歸結(jié)式C12是親本子句C1和C2的邏輯結(jié)論。 定理：子句集S是不可滿足的，當且僅當存在一個從S到空子句的歸結(jié)過程。,第三章確定性推理,歸結(jié)反演定理證明過程： 公式集S，目標公式G 否定G，得到 G 把 G添加到S中去 新產(chǎn)生 G，S化為子句集 應(yīng)用歸結(jié)原理，力圖推導出一個矛盾空子句 例：p101 3.18,第三章確定性推理,謂詞邏輯歸結(jié) 定義：對含有變元的子句C1、C2中文字L1、L2，如果L1、 L2存在最一般合一者，則有歸結(jié)式 C12C1L1 C2-L2 二元歸結(jié)式不作要求 例：p102 謂詞邏輯歸結(jié)反演定理證明 例：p103105,第三章確定性推理,謂詞邏輯歸結(jié)反演問題求解 答案求取涉及到把一棵根部有空子句的反演樹變換為在根部帶有可用作答案的某個語句的一棵證明樹 把由目標公式的否定產(chǎn)生的每個子句添加到目標公式否定的否定的子句中去 按照反演樹，執(zhí)行和以前相同的消解，直至在根部得到某個子句止。 用根部的子句作為一個回答語句 例：p110,第三章確定性推理,歸結(jié)演