ARTIFICIALINTELLIGENCE

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

2001.9第三章確定性推理一、推理的基本概念定義

推理：已知事實(shí)結(jié)論

知識(shí)推理是指在計(jì)算機(jī)或智能機(jī)器中，在知識(shí)表達(dá)的基礎(chǔ)上，利用形式化的知識(shí)模型，進(jìn)行機(jī)器思維求解問題，實(shí)現(xiàn)狀態(tài)轉(zhuǎn)移的智能操作序列。策略第三章確定性推理

基本問題：推理的方法和控制的策略推理方法及分類根據(jù)知識(shí)表示方式分類“圖搜索”方法如：狀態(tài)空間法、與或圖“邏輯論證”方法如：謂詞邏輯等推理算法與推理步驟

算法：完備性如寬度優(yōu)先

步驟：不完備如深度優(yōu)先啟發(fā)式與非啟發(fā)式

啟發(fā)性知識(shí)：即解決問題的策略、技巧、竅門等實(shí)踐經(jīng)驗(yàn)和知識(shí)。例：瞎子爬山第三章確定性推理按邏輯基礎(chǔ)演繹推理：一般到個(gè)別三段論歸納推理：個(gè)別到一般完全歸納、不完全歸納枚舉歸納、類比歸納等默認(rèn)（缺省）推理：知識(shí)不完備按知識(shí)的確定性確定性推理：知識(shí)和結(jié)論都是精確的非確定性推理第三章確定性推理按推理過程的單調(diào)性

單調(diào)推理

非單調(diào)推理：加入新知識(shí)會(huì)否定原來推出的結(jié)論，使推理過程回退控制策略及分類

推理的控制策略：指如何使用領(lǐng)域知識(shí)使推理過程盡快達(dá)到目標(biāo)的策略。

推理策略：推理方向控制策略、求解策略、限制策略、沖突消解策略

搜索策略（第五章）：推理線路、推理效果、推理效率第三章確定性推理正向推理

知識(shí)庫、綜合數(shù)據(jù)庫、推理機(jī)

正向推理的過程（圖3-1）

優(yōu)點(diǎn)：直觀。適合于診斷、監(jiān)控、設(shè)計(jì)、預(yù)測等領(lǐng)域。

缺點(diǎn)；推理無明確目標(biāo)，效率較低。逆向推理逆向推理的過程（圖3-2）

優(yōu)點(diǎn)：目標(biāo)明確，效率較高

缺點(diǎn)：情況不明時(shí)，選擇假設(shè)目標(biāo)的盲目性比較大，可能多次提出假設(shè)，降低系統(tǒng)效率第三章確定性推理混合推理方法先正后逆（圖3-3）先逆后正（圖3-4）雙向（圖3-5）適用場合事實(shí)不夠充分正向推理推出的結(jié)論可性度不高希望得到更多結(jié)論第三章確定性推理沖突消解策略基本思想：對可用知識(shí)排序特殊知識(shí)優(yōu)先新鮮知識(shí)優(yōu)先差異性大的知識(shí)優(yōu)先領(lǐng)域特點(diǎn)優(yōu)先上下文關(guān)系優(yōu)先前提條件少者優(yōu)先第三章確定性推理二、推理的邏輯基礎(chǔ)基本概念謂詞公式的解釋對所包含的常量、函數(shù)、謂詞賦值謂詞公式的永真性與可滿足性非空個(gè)體域上的任一解釋（在D上永真）；任何非空個(gè)體域（永真）謂詞公式的等價(jià)性與永真蘊(yùn)含性在D上等價(jià)與等價(jià)P＜﹦＞Q,永真蘊(yùn)含P﹦＞Q常用的等價(jià)式、永真蘊(yùn)含式（牢記）第三章確定性推理謂詞公式的范式前束范式：前綴＋母式置換與合一已知：W1(A),(x)(W1(x)→W2(x))

結(jié)論：W2(A)置換：在表達(dá)式中用置換項(xiàng)置換變量。{t1/x1,t2/x2,…,tn/xn,}量詞串無量詞公式第三章章確確定性性推理理置換的的例置換的的合成成(Ls1)s2=L(s1s2)置換一一般不不可交交換s1s2≠≠s2s1例：表達(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)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}第三章章確確定性性推理理合一：：尋找找項(xiàng)對對變量量的置置換，，以使使表達(dá)達(dá)式一一致。。{P[g(x),f(y),B],P[h(x),f(B),B]}不可合合一盡管s={A/x,B/y}是{P[x,f(y),B],P[x,f(B),B]}的一個(gè)個(gè)合一一者，，但是是最簡簡單的的合一一者是是g={B/y}最一般般(通通用)合一者者(mgu)：：置換最最少的的變量量以使使表達(dá)達(dá)式一一致。。分歧集集：例：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))}第三章章確確定性性推理理三、自自然演演繹推推理已知事事實(shí)結(jié)結(jié)論論注意肯肯定前前件、、否定定后件件的錯(cuò)錯(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ī)規(guī)則第三章章確確定性性推理理四、歸歸結(jié)演演繹推推理（（Robinson消解原原理））對前提提P，結(jié)論Q，證明P→Q永真P→Q與﹁P∨∨Q等價(jià)只需證證明﹁（﹁P∨∨Q））即P∧﹁﹁Q不可滿滿足。第三章章確確定性性推理理子句集集概念文字：：原子謂謂詞公公式及及其否否定子句：：任何文文字的的析取取式空子句句NIL：永假、、不可可滿足足化為子子句集集消去蘊(yùn)蘊(yùn)涵和和等價(jià)價(jià)符號(hào)號(hào)減少否否定符符號(hào)的的轄域域?qū)ψ兞苛繕?biāo)準(zhǔn)準(zhǔn)化，，保證證每個(gè)個(gè)量詞詞有其其唯一一的啞啞元消去存存在量量詞skolem函數(shù)第三章章確確定性性推理理化為前前束形形前綴（（全稱稱量詞詞串））＋母式式（元元量詞詞公式式）把母式式化為為合取取范式式消去全全稱量量詞消去連連詞符符號(hào)更換變變量名名稱第三章章確確定性性推理理例（x）{P(x)→{(y)[P(y)→P(f(x,y))]∧﹁(y)[Q(x,y)→P(y)]}}第三章章確確定性性推理理二、p93~98:只要求求記住住兩條條有用用的結(jié)結(jié)論：：原謂詞詞公式式不可可滿足足，其其標(biāo)準(zhǔn)準(zhǔn)子句句集則則一定定不可可滿足足。Herbrand(海伯倫倫)定定理：子句句集S不可滿滿足的的充要要條件件是存存在一一個(gè)有有限的的不可可滿足足的基基子句句集S’。。第三章章確確定性性推理理三、魯魯賓遜遜（Robinson）歸結(jié)結(jié)原理理基本本思思想想否定定結(jié)結(jié)論論，，加加入入前前提提子子句句集集，，應(yīng)應(yīng)用用歸歸結(jié)結(jié)原原理理，，是是否否能能導(dǎo)導(dǎo)出出空空子子句句，，若若存存在在，，證證明明否否定定結(jié)結(jié)論論錯(cuò)錯(cuò)誤誤，，即即原原結(jié)結(jié)論論得得證證。。（（反反證證法法））實(shí)際際上上歸歸結(jié)結(jié)原原理理不不僅僅應(yīng)應(yīng)用用在在定定理理證證明明，，還還可可應(yīng)應(yīng)用用于于問問題題求求解解過過程程。。歸結(jié)結(jié)原原理理互補(bǔ)補(bǔ)文文字字：：P、、﹁﹁P歸結(jié)結(jié)式式：：分分為為命命題題邏邏輯輯歸歸結(jié)結(jié)和和謂謂詞詞邏邏輯輯歸歸結(jié)結(jié).第三三章章確確定定性性推推理理命題題邏邏輯輯歸歸結(jié)結(jié)定義義：：L1、、L2分別別是是子子句句C1、、C2中的的文文字字，，并并且且L1、、L2互補(bǔ)補(bǔ)，，即即L1＝＝﹁﹁L2，將將它它們們從從C1、、C2中消消去去，，并并將將兩兩子子句句余余下下部部分分按按析取取關(guān)關(guān)系系組成成新新子子句句C12，，即歸結(jié)結(jié)式式。C1、、C2叫做做親本本子子句句。例：：p993.15、、3.16、、3.17第三三章章確確定定性性推推理理定理理：歸歸結(jié)結(jié)式式C12是親親本本子子句句C1和C2的邏邏輯輯結(jié)結(jié)論論。。定理理：子子句句集集S是不不可可滿滿足足的的，，當(dāng)當(dāng)且且僅僅當(dāng)當(dāng)存存在在一一個(gè)個(gè)從從S到空空子子句句的的歸歸結(jié)結(jié)過過程程。。第三三章章確確定定性性推推理理歸結(jié)結(jié)反反演演定定理理證證明明過過程程：：公式式集集S，目標(biāo)標(biāo)公公式式G否定定G，，得到到﹁G把﹁G添加加到到S中去去新產(chǎn)產(chǎn)生生{﹁G，S}化為為子子句句集集應(yīng)用用歸歸結(jié)結(jié)原原理理，，力力圖圖推推導(dǎo)導(dǎo)出出一一個(gè)個(gè)矛矛盾盾空空子子句句例：p1013.18第三三章章確確定定性性推推理理謂詞詞邏邏輯輯歸歸結(jié)結(jié)定義義：對對含含有有變變元元的的子子句句C1、、C2中文文字字L1、、L2，，如果果L1、、﹁﹁L2存在在最最一一般般合合一一者者ɑ，則則有有歸歸結(jié)結(jié)式式C12＝＝{C1－－L1}ɑ∨{C2-L2}ɑ二元元?dú)w歸結(jié)結(jié)式式不不作作要要求求例：：p102謂詞詞邏邏輯輯歸歸結(jié)結(jié)反反演演定定理理證證明明例：：p103～～105第三三章章確確定定性性推推理理謂詞詞邏邏輯輯歸歸結(jié)結(jié)反反演演問問題題求求解解答案案求求取取涉涉及及到到把把一一棵棵根根部部有有空空子子句句的的反演演樹樹變變換換為為在根根部部帶帶有有可可用用作作答答案案的的某某個(gè)個(gè)語語句句的的一一棵棵證明明樹樹把由由目目標(biāo)標(biāo)公公式式的的否否定定產(chǎn)產(chǎn)生生的的每每個(gè)個(gè)子子句句添添加加到到目目標(biāo)標(biāo)公公式式否否定定的的否否定定的的子子句句中中去去按照照反反演演樹樹，，執(zhí)執(zhí)行行和和以以前前相相同