【正文】 。 ?應(yīng)用：結(jié)構(gòu)不良問(wèn)題，無(wú)成熟算法；或有算法 ，但問(wèn)題復(fù)雜，如博弈 ?圖：由節(jié)點(diǎn)和有向邊組成的網(wǎng)絡(luò) ?圖的分類： ? 或圖 (狀態(tài)圖、直接圖 ) ? 與或圖 狀態(tài)圖 ?狀態(tài)圖的概念 ? 迷宮問(wèn)題 ? 八數(shù)碼難題 /華容道問(wèn)題 ?以上問(wèn)題的本質(zhì)：在某個(gè)有向圖中尋找目標(biāo)或路徑，該有向圖稱為 狀態(tài)空間圖 或 狀態(tài)圖 。 ? 步 3 按某種策略在 CLAUSES表中尋找可歸結(jié)的子句對(duì)，若存在則歸結(jié)之，并將歸結(jié)式并入 CLAUSES表，轉(zhuǎn)步２； ? 步 4 歸結(jié)失敗，退出。 歸結(jié)策略 ? 歸結(jié)策略的類型 ? 簡(jiǎn)化性策略 ?思想：盡量簡(jiǎn)化子句和子句集，以減少和避免無(wú)效歸結(jié)。 ?線性歸結(jié)策略 ? 在歸結(jié)過(guò)程中，除第一次歸結(jié)可都用初始子句集 S中的子句外，其它的各次歸結(jié)至少要有一個(gè)親本子句是前次歸結(jié)的結(jié)果。 ? 支持集策略的特點(diǎn)： ?支持集策略實(shí)際是一種 目標(biāo)制導(dǎo) 的 反向 推理。一個(gè)歸結(jié)策略是完備的，是指對(duì)于不可滿足的子句集，使用該策略進(jìn)行歸結(jié)，最終必導(dǎo)出空子句。 ?解釋： C=P(x)替換后得 C=P(a)， D=P(a) ? Q(y) 歸結(jié)策略 ?使用刪除策略，例 1可簡(jiǎn)化為： （ 1） P?Q （ 7） ? P [ (2), (4) ] （ 2） ? P?Q （ 8） Q [ (3), (4) ] （ 3） P? ? Q （ 9） □ [(5), (8)] （ 4） ? P? ? Q （ 5） Q [(1), (2)] （ 6） P [(1), (3)] ?刪除策略的特點(diǎn)： ? 刪除策略的思想是及早刪除無(wú)用字句，以避免無(wú)效歸結(jié)，縮小搜索空間。 ?純文字 是指在子句中無(wú)補(bǔ)文字的文字。 ? P(x)類含 P(a) ? Q(y) ? P(x)類含 P(a) ?刪除策略。 ? 如此下去，直到出現(xiàn)空子句。 ? 步 3 若 CLAUSES表中存在可歸結(jié)的子句對(duì)，則歸結(jié)之，并將歸結(jié)式并入 CLAUSES表，轉(zhuǎn)步２； ? 步 4 歸結(jié)失敗，退出。無(wú)論如何歸結(jié)，推不出 ANS(A), ANS(B) 歸結(jié)策略 ? 歸結(jié)反演的一般過(guò)程。如果 A說(shuō)的是真話，則有： T(A) ? ? T(B) ? ?T(C ) 如果 A說(shuō)的是假話，則有： ?T(A) ?T(B)? T(C )。 ANS的變?cè)獞?yīng)與問(wèn)題的變?cè)耆恢? ?把此析取式化為子句集，并把該子句集并入 S中得到子句集 S‘ ?對(duì) S‘應(yīng)用歸結(jié)原理進(jìn)行歸結(jié) ?若得到歸結(jié)式 ANS，則答案就在 ANS中 應(yīng)用歸結(jié)原理求解 ? 例：設(shè) A、 B、 C三人中有人從不說(shuō)真話，也有人從不說(shuō)假話，某人向這三人分別提出同一個(gè)問(wèn)題： 誰(shuí)是說(shuō)謊者？ A答：“ B和 C都是說(shuō)謊者”； B答：“ A和 C都是說(shuō)謊者”； C答：“ A和B中至少有一個(gè)是說(shuō)謊者”。求證：所有自然數(shù)不是奇數(shù)就是其一半為整數(shù)的數(shù)。 ?定理 5（歸結(jié)原理的 完備性 ）、如果子句集 S是不可滿足的，則必存在一個(gè)由 S推出空子句的歸結(jié)序列。 例： C1=P(x)?Q(x) , C2= ? P(a)?R(y), C12=Q(a)?R(y) 說(shuō)明：當(dāng)子句內(nèi)部有可合一的文字時(shí)，應(yīng)在歸結(jié)前進(jìn)行合一，使子句最簡(jiǎn) 例： C1=P(x) ?P(f(a))?Q(x)，則 C1=P(f(a))?Q(x) ?歸結(jié)原理： C1 ? C2 ?(C1?{L1?})? (C2?{L2?}) 謂詞邏輯中的歸結(jié)原理 ?歸結(jié)時(shí)的注意事項(xiàng) ? 謂詞的一致性 . 名稱不一致的謂詞不能歸結(jié) ?? P (x) ， R (x) 不能歸結(jié) ? 常量的一致性 . 含有不同常量的謂詞不能歸結(jié) ?P(a,…) ， ? P(b,…) 不能歸結(jié) ? 變量與函數(shù) ?P(x,x,…) ， P(x,f(x),…) 不能歸結(jié) ?P(x,x,…) ， P(x,f(y),…) 能歸結(jié) ? 不能同時(shí)消去兩個(gè)互補(bǔ)對(duì) ?P ? Q 與 ?P ? ?Q 不能同時(shí)消去 歸結(jié)反演 ?歸結(jié)反演：應(yīng)用歸結(jié)原理證明定理的過(guò)程 ?若 F為已知前提的公式集， Q為結(jié)論，用歸結(jié)反演證明Q為真的步驟是： ? （ 1）、否定 Q，得到 ?Q； ? （ 2）、把 ?Q并入到公式集 F中，得到 {F, ?Q}； ? （ 3）、把公式集 {F, ?Q}化為子句集 S； ? （ 4）、應(yīng)用歸結(jié)原理對(duì)子句集 S中的子句進(jìn)行歸結(jié)，并把每次歸結(jié)得到的歸結(jié)式都并入 S中。{g(y)/u}={a/z, h(a, g(y))/x, g(y)/u} ?S3=S2{g(y)/u}={P(a,h(a,g(y)),f(g(y))), P(a,h(a,g(y)),f(g(y)))} = {P(a,h(a,g(y)),f(g(y)))} ?k=3 ?S3為單元素集，所以 ?3為所求的 S的 MGU 說(shuō)明： MGU可能是不唯一的，如 Dk={xk,yk}時(shí) 謂詞邏輯中的歸結(jié)原理 ?定義 12 設(shè) C1,C2是兩個(gè)沒(méi)有相同變?cè)淖泳洌?L1,L2分別是 C1,C2中的兩個(gè)文字，如果 L1與 ?L2有最一般合一? ，則子句 C12=(C1?{L1?})? (C2?{L2?})，稱作 C1和C2的 二元?dú)w結(jié)式 (二元消解式 )。{h(a,u)/x}={a/z }{tk /xk} ，k=k+1，然后轉(zhuǎn)步 (2) ? (5) 算法停止， S的最一般合一不存在 替換與合一 ?求 S={P(a,x,f(g(y))) , P(z,h(z,u),f(u))}的 MGU ?k=0 ?S0=S, ?0= ? , D0={a,z} ??1= ?0? 替換與合一 ?定義 11 設(shè) S是一個(gè)非空的具有 相同 謂詞名的原子公式集，從 S中各公式的左邊第一個(gè)項(xiàng)開(kāi)始，同時(shí)向右比較，每一組不都相同的項(xiàng)的差異部分組成的集合稱為S的 差異集 。 ? 一個(gè)公式集的合一一般不唯一 ?定義 10 設(shè) ?是公式集 S的一個(gè)合一，如果對(duì) S的任何一個(gè)合一 ?，都存在一個(gè)替換 ?，使得 ?＝ ? ? 例 : 設(shè) ? ={f(y)/x,z/y} ?={a/x,b/y,y/z} ? ?基替換 (t1 , t2 ,…,t n 均不含變?cè)?)、 空替換 ε ?例：｛ a/x, g(c)/y, f(g(b))/z} ， {g(y)/x, f(x)/y} 替換與合一 ? 定義 7 設(shè) ?＝ {t1 / x1, t2 / x2 ,…,t n / xn }是一個(gè)替換， E是一個(gè)表達(dá)式，把 E中出現(xiàn)的所有個(gè)體變?cè)?xi都用 ti 替換，記為 E? ，得到的結(jié)果稱為 E在 ?下的 替換實(shí)例 (Instance)。 ti / xi表示用 ti代換 xi 。即 S2不可滿足 ? S不可滿足 命題邏輯中的歸結(jié)原理 ?例、用歸結(jié)原理證明 R是 P, (P ? Q) ? R， (S?U) ? Q， U的邏輯結(jié)果。 推論 、設(shè) C1， C2是子句集 S的兩個(gè)子句， C1２ 是它們的歸結(jié)式，則 （１）若用 C1２ 代替 C1和 C2后得到新子句集 S1，則由 S1的不可滿足性可推出原子句集 S的不可滿足性。 定義５ 、設(shè) C C2是命題邏輯中的兩個(gè)子句， C1 中有文字 L1 ， C２ 中有文字 L２ ，且 L1與 L２ 互補(bǔ)， 從 C1， C２ 中分別刪除 L1 ， L２ ，再將剩余部分 析取 起來(lái)，構(gòu)成的新子句 C1２ 稱為 C1與 C2的 歸結(jié)式 （消解式）， C1， C2稱為 C1２ 的 親本子句 。 ?因此，歸結(jié)原理把定理的證明化為子句集中歸結(jié)出空子句的過(guò)程。 ?若子句集中不包含空子句，則可通過(guò) Robinson提出的歸結(jié)原理對(duì)子句集進(jìn)行歸結(jié)，歸結(jié)過(guò)程保證子句集的不可滿足性不變。由于子句之間是合取關(guān)系，只要有一個(gè)子句不滿足，則整個(gè)子句集不可滿足。 命題邏輯中的歸結(jié)原理 ?要證明在前提 P下結(jié)論 Q成立，即是證明 P ? Q永真，這只須證明 P? ?Q不可滿足。 ?x{?yP(x,y) ? ??y[Q(x,y)?R(x,y)]} 子句集 求解過(guò)程 ?x{?yP(x,y) ? ??y[Q(x,y)?R(x,y)]} ? 1) ?x{??yP(x,y) ? ??y[?Q(x,y) ? R(x,y)]} ? 2) ?x{?y?P(x,y) ? ? y[Q(x,y) ? ? R(x,y)]} ? 3) ?x{?y?P(x,y) ? ? z[Q(x,z) ? ? R(x,z)]} ? 4) ?x{?P(x,f(x)) ? [Q(x,g(x)) ? ? R(x,g(x))]} ? 5) ?P(x,f(x)) ? [Q(x,g(x)) ? ? R(x,g(x))] ? 6) [?P(x,f(x)) ? Q(x,g(x))] ?(?P(x,f(x)) ? ? R(x,g(x))] ? 7) [?P(x,f(x)) ? Q(x,g(x))] ?(?P(y,f(y)) ? ? R(y,g(y))] ? 8) {?P(x,f(x)) ? Q(x,g(x))， (?P(y,f(y)) ? ? R(y,g(y))} ? 定理 1 謂詞公式 G 不可滿足 當(dāng)且僅當(dāng) 其子句集 S不可滿足。 （ 9） 、消去合取詞 ? ，以子句為元素組成的集合稱為謂詞公式的子句集。 （ 7） 、消去全稱量詞。 （ 6） 、把全稱量詞后面的公式利用等價(jià)關(guān)系 A?(B ?C) ? (A?B) ?(A ?C)化為子句的合取式，得到的公式稱為 Skolem標(biāo)準(zhǔn)形 。 例如 ?x1 ?x2 ? ? ???xn?yP(x1,x2,…, x n,y)中 y可用 Skolem函數(shù) f(x1,x2,…, x n)替換為 ?x1 ?x2 ? ? ???xnP(x1,x2,…, x n,f(x1,x2,…, x n))。這樣的常量稱為 Skolem常量；若該存在量詞在一個(gè)或多個(gè)全稱量詞的轄域內(nèi)，則用這些全稱量詞指導(dǎo)變?cè)囊粋€(gè)函數(shù)替換該存在量詞約束的變?cè)? （ 4） 、消去存在量詞。 （ 2） 、縮小否定聯(lián)結(jié)詞的作用范圍，使其僅作用于原子公式。 ?定義 2 對(duì)一個(gè)謂詞公式 G，通過(guò)一定的步驟得到的子句集合 S稱為 G的 子句集 。 ?推理與謂詞公式的含義無(wú)關(guān)，是一種形式推理。例見(jiàn)教材 p61。 存在推廣規(guī)則 EG (Universal Generalization) ： A(c) ? ?xA(x)， c是個(gè)體域中某一確定元素。 存在指定規(guī)則 ES (Existential Specification)： ?xA(x) ?A(c)， c是個(gè)體域中某一確定元素。轄域中與該量詞的指導(dǎo)變?cè)嗤淖冊(cè)Q為約束變?cè)?，其它變?cè)?(如果存在的話 )稱為自由變?cè)? 謂詞公式 ： 原子公式是謂詞公式； 若 A、 B是謂詞公式，則 ? A， A ? B， A ? B， A ? B， A ? B， ?xA， ?xA也是謂詞公式； 只有有限次地應(yīng)用步驟 1， 2形成的符號(hào)串才是謂詞公式。 只有有限次使用 1， 2得到的符號(hào)串才是項(xiàng)。 “存在偶素?cái)?shù)”可表示為 ?x(E(x) ?P(x))。 例、命題“小李的父親是醫(yī)生”可表示為 Doctor(father(Li)). 量詞 ：存在量詞“ ? ”；全稱量詞“ ? ”。 例、命題“ 2是素?cái)?shù)”中， 2是個(gè)體，“是素?cái)?shù)”是謂詞。 謂詞 ：描述個(gè)體性質(zhì)及個(gè)體之間相互關(guān)系的詞。 第二章 基于謂詞邏輯的機(jī)器推理 謂詞、函詞、量詞 個(gè)體 ：研究對(duì)象中可以獨(dú)立存在的具體的或抽象的客體。 ? 神經(jīng)網(wǎng)絡(luò)：識(shí)別 聯(lián)想 學(xué)習(xí) 適應(yīng)，負(fù)責(zé)對(duì)外界的感知和交互 ? 專家系統(tǒng)：判斷 推理 搜索，負(fù)責(zé)高層的決策與控制 ? 新理論、新技術(shù)的出現(xiàn)。 NN在智能控制、信號(hào)處理、最優(yōu)化、知識(shí)工程等領(lǐng)域都有成功應(yīng)用。 1987年 6月，第一屆國(guó)際神經(jīng)網(wǎng)絡(luò)大會(huì)（ IJCNN）召開(kāi)，盛況空前。 1986年， Hopfield網(wǎng)絡(luò)成功應(yīng)用于 TSP問(wèn)題。 ? 在低谷期， Kohonen Grossberg和 Anderson等人仍堅(jiān)持研究，取得了一些有價(jià)值的結(jié)果。應(yīng)用于天氣預(yù)報(bào)、電子線路板分析、人工視覺(jué)等。 ? 1957年， Rosenblatt提出 Perceptron單層神經(jīng)網(wǎng)絡(luò)模型。 人工智能的發(fā)展概況 ? 連接主義途徑發(fā)展概況 ? 1943年，神經(jīng)生理學(xué)家 McCulloch 和 Pi