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

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

2、問題的策略、技巧、竅門等實(shí)踐經(jīng)驗(yàn)和知識(shí)。例：瞎子爬山第3頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理按邏輯基礎(chǔ) 演繹推理：一般到個(gè)別 三段論 歸納推理：個(gè)別到一般 完全歸納、不完全歸納 枚舉歸納、類比歸納等 默認(rèn)（缺省）推理：知識(shí)不完備按知識(shí)的確定性 確定性推理：知識(shí)和結(jié)論都是精確的 非確定性推理第4頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理按推理過程的單調(diào)性 單調(diào)推理 非單調(diào)推理：加入新知識(shí)會(huì)否定原來推出的結(jié)論，使推理過程回退控制策略及分類 推理的控制策略：指如何使用領(lǐng)域知識(shí)使推理過程盡快達(dá)到目標(biāo)的策略。 推理策略：推理方向控制策

3、略、求解策略、限制策略、沖突消解策略 搜索策略（第五章）：推理線路、推理效果、推理效率第5頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理正向推理 知識(shí)庫、綜合數(shù)據(jù)庫、推理機(jī) 正向推理的過程（圖3-1） 優(yōu)點(diǎn)：直觀。適合于診斷、監(jiān)控、設(shè)計(jì)、預(yù)測(cè)等領(lǐng)域。 缺點(diǎn)；推理無明確目標(biāo)，效率較低。逆向推理 逆向推理的過程（圖3-2） 優(yōu)點(diǎn)：目標(biāo)明確，效率較高 缺點(diǎn)：情況不明時(shí)，選擇假設(shè)目標(biāo)的盲目性比較大，可能多次提出假設(shè)，降低系統(tǒng)效率第6頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理混合推理方法先正后逆（圖3-3）先逆后正（圖3-4）雙向（圖3-5）適

4、用場(chǎng)合事實(shí)不夠充分正向推理推出的結(jié)論可性度不高希望得到更多結(jié)論第7頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理沖突消解策略 基本思想：對(duì)可用知識(shí)排序特殊知識(shí)優(yōu)先新鮮知識(shí)優(yōu)先差異性大的知識(shí)優(yōu)先領(lǐng)域特點(diǎn)優(yōu)先上下文關(guān)系優(yōu)先前提條件少者優(yōu)先第8頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理二、推理的邏輯基礎(chǔ)基本概念謂詞公式的解釋 對(duì)所包含的常量、函數(shù)、謂詞賦值謂詞公式的永真性與可滿足性 非空個(gè)體域上的任一解釋（在D上永真）；任何非空個(gè)體域 （永真）謂詞公式的等價(jià)性與永真蘊(yùn)含性 在D上等價(jià)與等價(jià)PQ ,永真蘊(yùn)含PQ 常用的等價(jià)式、永真蘊(yùn)含式（牢記

5、）第9頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理謂詞公式的范式 前束范式： 前綴 母式置換與合一 已知：W1(A), ( x)(W1(x) W2(x) 結(jié)論：W2(A)置換：在表達(dá)式中用置換項(xiàng)置換變量。 t1/x1, t2/x2, ,tn/xn,量詞串無量詞公式第10頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理 置換的例 置換的合成 (Ls1)s2=L(s1s2) 置換一般不可交換 s1s2s2s1 例： 表達(dá)式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

6、) 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 第11頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理合一：尋找項(xiàng)對(duì)變量的置換，以使表達(dá)式一致。 Pg(x),f(y),B,Ph(x),f(B),B不可合一 盡管s=A/x,B/y是Px,f(y),B,Px,f(B),B的一個(gè)合一者，但是最簡(jiǎn)單的合一者是g=B/y 最一般(通用)合一者(mgu)：置換最少的變量以使表達(dá)式一致。 分歧集： 例：F=P(x,y,z),P(x,f(a),h(b)的

7、分歧集 D1=y,f(a) D2=z,h(b)第12頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理 合一算法(p89) 例： F=P(a,x,f(g(y),P(z,h(z,u),f(u) 第13頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理三、自然演繹推理 已知事實(shí) 結(jié)論 注意肯定前件、否定后件的錯(cuò)誤 例3.8： 定義謂詞：Prog(x) Like(x,y) Lang(x) 事實(shí)：Prog(x) Like(Wang,x) ( x) (Lang(x) Prog(x) ) Lang(C) 結(jié)論：Like(Wang,C) 經(jīng)典邏輯推理規(guī)則第14

8、頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理四、歸結(jié)演繹推理（Robinson消解原理） 對(duì)前提P，結(jié)論Q，證明P Q永真 P Q與PQ等價(jià) 只需證明 （PQ）即P Q不可滿足。第15頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理子句集概念 文字：原子謂詞公式及其否定 子句：任何文字的析取式 空子句NIL：永假、不可滿足化為子句集消去蘊(yùn)涵和等價(jià)符號(hào)減少否定符號(hào)的轄域?qū)ψ兞繕?biāo)準(zhǔn)化，保證每個(gè)量詞有其唯一的啞元消去存在量詞 skolem函數(shù)第16頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理化為前束形 前綴（全稱量

9、詞串） 母式（元量詞公式）把母式化為合取范式消去全稱量詞消去連詞符號(hào)更換變量名稱第17頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理例（ x）P(x) ( y)P(y)P(f(x,y)( y)Q(x,y)P(y) 第18頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理二、p9398:只要求記住兩條有用的結(jié)論：原謂詞公式不可滿足，其標(biāo)準(zhǔn)子句集則一定不可滿足。Herbrand(海伯倫)定理：子句集S不可滿足的充要條件是存在一個(gè)有限的不可滿足的基子句集S。第19頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理三、魯賓遜（

10、 Robinson ）歸結(jié)原理基本思想 否定結(jié)論，加入前提子句集，應(yīng)用歸結(jié)原理，是否能導(dǎo)出空子句，若存在，證明否定結(jié)論錯(cuò)誤，即原結(jié)論得證。（反證法） 實(shí)際上歸結(jié)原理不僅應(yīng)用在定理證明，還可應(yīng)用于問題求解過程。歸結(jié)原理 互補(bǔ)文字：P、 P 歸結(jié)式：分為命題邏輯歸結(jié)和謂詞邏輯歸結(jié).第20頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理 命題邏輯歸結(jié)定義： L1、L2分別是子句C1、C2中的文字， 并且L1、L2 互補(bǔ)，即L1 L2 ，將它們從C1、C2中消去，并將兩子句余下部分按析取關(guān)系組成新子句C12，即歸結(jié)式。 C1、C2叫做親本子句。 例：p99 3.15、3.16

11、、3.17第21頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理定理：歸結(jié)式C12是親本子句C1和C2的邏輯結(jié)論。 定理：子句集S是不可滿足的，當(dāng)且僅當(dāng)存在一個(gè)從S到空子句的歸結(jié)過程。第22頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理歸結(jié)反演定理證明過程： 公式集S，目標(biāo)公式G否定G，得到 G把 G添加到S中去新產(chǎn)生 G，S化為子句集應(yīng)用歸結(jié)原理，力圖推導(dǎo)出一個(gè)矛盾空子句 例：p101 3.18第23頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理謂詞邏輯歸結(jié)定義：對(duì)含有變?cè)淖泳銫1、C2中文字L1、L2，如果

12、L1、 L2存在最一般合一者，則有歸結(jié)式 C12C1L1 C2-L2 二元?dú)w結(jié)式不作要求 例：p102謂詞邏輯歸結(jié)反演定理證明 例：p103105第24頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理謂詞邏輯歸結(jié)反演問題求解 答案求取涉及到把一棵根部有空子句的反演樹變換為在根部帶有可用作答案的某個(gè)語句的一棵證明樹把由目標(biāo)公式的否定產(chǎn)生的每個(gè)子句添加到目標(biāo)公式否定的否定的子句中去按照反演樹，執(zhí)行和以前相同的消解，直至在根部得到某個(gè)子句止。用根部的子句作為一個(gè)回答語句 例：p110第25頁，共27頁，2022年，5月20日，10點(diǎn)55分，星期日第三章確定性推理歸結(jié)演繹推理的歸結(jié)策略 廣度優(yōu)先策略刪除