【正文】 。 ANS的變元應與問題的變元完全一致 ?把此析取式化為子句集，并把該子句集并入 S中得到子句集 S‘ ?對 S‘應用歸結(jié)原理進行歸結(jié) ?若得到歸結(jié)式 ANS，則答案就在 ANS中 應用歸結(jié)原理求解 ? 例：設 A、 B、 C三人中有人從不說真話，也有人從不說假話，某人向這三人分別提出同一個問題： 誰是說謊者？ A答：“ B和 C都是說謊者”； B答：“ A和 C都是說謊者”； C答：“ A和B中至少有一個是說謊者”。{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 說明： MGU可能是不唯一的，如 Dk={xk,yk}時 謂詞邏輯中的歸結(jié)原理 ?定義 12 設 C1,C2是兩個沒有相同變元的子句， L1,L2分別是 C1,C2中的兩個文字，如果 L1與 ?L2有最一般合一? ，則子句 C12=(C1?{L1?})? (C2?{L2?})，稱作 C1和C2的 二元歸結(jié)式 (二元消解式 )。 ? 一個公式集的合一一般不唯一 ?定義 10 設 ?是公式集 S的一個合一，如果對 S的任何一個合一 ?，都存在一個替換 ?，使得 ?＝ ? 即 S2不可滿足 ? S不可滿足 命題邏輯中的歸結(jié)原理 ?例、用歸結(jié)原理證明 R是 P, (P ? Q) ? R， (S?U) ? Q， U的邏輯結(jié)果。 ?若子句集中不包含空子句，則可通過 Robinson提出的歸結(jié)原理對子句集進行歸結(jié)，歸結(jié)過程保證子句集的不可滿足性不變。 （ 9） 、消去合取詞 ? ，以子句為元素組成的集合稱為謂詞公式的子句集。這樣的常量稱為 Skolem常量；若該存在量詞在一個或多個全稱量詞的轄域內(nèi)，則用這些全稱量詞指導變元的一個函數(shù)替換該存在量詞約束的變元。 ?推理與謂詞公式的含義無關，是一種形式推理。轄域中與該量詞的指導變元相同的變元稱為約束變元，其它變元 (如果存在的話 )稱為自由變元。 例、命題“小李的父親是醫(yī)生”可表示為 Doctor(father(Li)). 量詞 ：存在量詞“ ? ”；全稱量詞“ ? ”。 ? 神經(jīng)網(wǎng)絡：識別 聯(lián)想 學習 適應，負責對外界的感知和交互 ? 專家系統(tǒng)：判斷 推理 搜索，負責高層的決策與控制 ? 新理論、新技術(shù)的出現(xiàn)。 ? 在低谷期， Kohonen Grossberg和 Anderson等人仍堅持研究，取得了一些有價值的結(jié)果。出現(xiàn)了多專家系統(tǒng)、大型專家系統(tǒng)、微專家系統(tǒng)、分布式專家系統(tǒng)等。 人工智能的發(fā)展概況 ? 人工智能的知識期（ 196570年代末） ?（ 1）、專家系統(tǒng)方面。 人工智能的發(fā)展概況 ?符號主義 AI發(fā)展概況 ? 形成（ 19561965）（人工智能的推理期。提出“知識就是力量” ? 德國數(shù)學家 Leibniz（ 16461716）提出了萬能符號和推理計算的思想，為數(shù)理邏輯的產(chǎn)生和發(fā)展奠定了基礎。機器自動提取概念、獲取知識、發(fā)現(xiàn)規(guī)律的技術(shù)。盲目搜索、啟發(fā)式搜索。推理是智能的核心。模糊和神經(jīng)網(wǎng)絡技術(shù)應用于網(wǎng)絡的業(yè)務量預測和控制、資源動態(tài)分配、動態(tài)路由選擇等方面。 ? 智能機器人系統(tǒng)。 ? 1智能 CAI。 ? 智能通訊。 ? 自動程序設計 ?超級編譯系統(tǒng) ?自動程序綜合和自動程序驗證。 ?機器學習分為：機械學習、指導學習、解釋學習、類比學習、示例學習、發(fā)現(xiàn)學習等。基于內(nèi)容的聯(lián)想，與具體存儲位置無關。 人工智能的研究途徑與方法 ?行為模擬（行為主義、進化主義、控制論學派） ? 基于感知 行為模型的研究途徑和方法。 ? 通過神經(jīng)元間連接強度的動態(tài)調(diào)整實現(xiàn)自學習和自適應功能。 學習能力因人而異、學習速度慢、效率低。思維用于對記憶的信息進行處理。作為一門學科，人工智能可定義為：人工智能是一門研究如何構(gòu)造智能機器（智能計算機）或智能系統(tǒng)，使它能模擬、延伸、擴展人類智能的學科 ?人工智能是一門交叉邊緣學科，與人工智能有關的學科有：計算機科學、數(shù)學、語言學、神經(jīng)生理學、神經(jīng)心理學、腦科學、認知科學、邏輯學、控制論等 什么是人的智能 ?智能是人腦的屬性和產(chǎn)物。 ? D、具有行為能力。 ?遠期目標：制造智能計算機，使計算機具有看、聽、說等感知和交互能力、具有聯(lián)想、推理、理解、學習等高級思維能力，還要有分析問題、解決問題和發(fā)明創(chuàng)造的能力。主要特征： ? 立足于邏輯運算和符號操作，適合于模擬人的 邏輯思維過程。 ? 智能只有放在環(huán)境中才是真正的智能，智能的高低體現(xiàn)在對環(huán)境的適應性上 ? Brooks，機器蟲 人工智能的分支領域 ? 基于腦功能模擬的領域劃分 ? 機器感知（信息輸入）。又稱為計算機推理、自動推理，是人工智能的核心課題之一。 ? 機器理解。自然語言理解。使通訊網(wǎng)隨時運行于最佳狀態(tài)?；谌祟悓＜抑R的程序系統(tǒng)。并行性、分布性和智能性。知識表示語言 FRL、 OPS5?；诜菢藴蔬壿嬋缍嘀颠壿?、模態(tài)邏輯、時態(tài)邏輯、模糊邏輯、非單調(diào)邏輯的推理。知識表示是指知識在計算機中的表示方式。數(shù)據(jù)庫知識發(fā)現(xiàn)（ KDD, Knowledge Discovery in Database) 和數(shù)據(jù)挖掘 (Data Mining)技術(shù)。Turing測試。 1959,1962 ?（ 2）、定理證明方面， 1956年 Newell等的邏輯理論機（ LT）程序；1958年，王浩的工作； 1965年， Robinson提出的消解原理。之后著名的專家系統(tǒng)有：醫(yī)學專家系統(tǒng) MYCIN，地質(zhì)勘探專家系統(tǒng) PROSPECTOR，計算機配置專家系統(tǒng) R1等。 1944年， Hebb提出 Hebb學習規(guī)則。 1986年 Rumelhart提出BP算法，解決了多層人工神經(jīng)元網(wǎng)絡的學習問題。個體用個體常元或個體變元表示，如 x,y,z,a,b,c,… 等。 一些命題的表示 ?凡是人都有名字 ? ?x(M(x) ?N(x)) ?不存在最大的整數(shù) ???x(G(x) ??y(G(y) ? D(x,y)) ? ?x(G(x) ? ?y(G(y) ? D(y,x)) ?對所有的自然數(shù)，均有 X+YX ??x ?y(N(x) ? N(y) ? S(x,y,x)) ?某些人對某些食物過敏 ? ?x ?y(M(x) ? F(y) ? G(x,y)) 謂詞公式 項的定義 ： 個體常元和個體變元是項； 設 f是 n元函詞符號， t1, t2 , …, tn是項，則 f(t1, t2 , …, tn)是項。 全稱推廣規(guī)則 UG (Universal Generalization) ： A(y) ? ?xA(x)， y是個體域中任一確定元素。 子句集 （ 1） 、利用等價式 A ? B ? ?A ?B 和 A ? B ? (A ? B) ?(B ? A)消去聯(lián)結(jié)詞“ ? ” 和 “ ? ”。 子句集 （ 5） 、把全稱量詞全部移到公式的左邊。子句集 S是不可滿足的是指其全部子句的合取式是不可滿足的。 命題邏輯中的歸結(jié)原理 定義４ 、設 L是一個文字，則稱 L與 ?L為 互補文字 。 ti與 xi不同， xi也不能 循環(huán) 出現(xiàn)在 tj中(j=1,2,…,n) 。 ?公式集 S={P(a,x,f(g(y))) , P(z,h(z,u),f(u))}的差異集為{a,z}, {x,h(z,u)}, {g(y),u } 替換與合一 ?設 S為一非空有限具有相同謂詞名的原子謂詞公式集，求 S的 MGU的算法： ? (1) 令 k=0, Sk=S, ?k= ?（ ? 表示空替換） ? (2) 若 Sk只含有一個謂詞公式，則算法停止， ?k就是要求的最一般合一 ? (3) 求 Sk的差異集 Dk ? (4) 若 Dk中存在元素 xk 和 tk ，其中 xk是變元， tk是項且 xk不在 tk中出現(xiàn)，則置 Sk+1 = Sk{tk /xk} ， ?k+1 = ?k如此反復進行，直到出現(xiàn)空子句，就證明了 Q為真。 同理，對 B和 C有： T(B) ? ? T(A) ??T(C ) ?T(B) ?T(A)? T(C ) T(C) ? ? T(A)? ? T(B ) ? T(C) ? T(A) ?T(B ) 應用歸結(jié)原理求解 化為子句集 S： 1) ? T(A)? ? T(B ) 2) ? T(A)? ? T(C ) 3) T(A)?T(B)?T(C ) 4) ? T(B)? ? T(C ) 5) ? T(A)? ? T(B ) ? ? T(C ) 6) T(C)?T(A) 7) T(C)?T(B) 把 ?T(x)? ANS(x)并入 S 8) ?T(x)? ANS(x) 9) T(A)? ANS( C) ( 8, 6, C/x ) 10)T(B)? ANS(C) ( 7, 8, C/x ) 11) ?T(B)? ANS(C) ( 9, 1) 12) ANS(C ) ( 10, 11) 因此 C是老實人。在歸結(jié)過程中可隨時刪除以下子句： ? （ 1）、含有純文字的子句。 ?支持集策略是完備的。 ?狀態(tài) 是描述問題求解過程中任一時刻的狀況。 ? 步 4 考察節(jié)點 N是否為目標節(jié)點，若是，則搜索成功，退出； ? 步 5 若 N不可擴展，則轉(zhuǎn)步 2； ? 步 6 擴展節(jié)點 N，生成所有子節(jié)點，對這組子節(jié)點作如下處理： ?（ 1）、如果有節(jié)點 N的先輩節(jié)點，則刪除； ?（ 2）、如果有已存在于 OPEN表的節(jié)點，也刪除；但刪除之前要比較其返回初始節(jié)點的新路徑與原路徑，如果新路徑“短”，則修改這些節(jié)點在OPEN表中的原指向父節(jié)點的指針，使其指向新的父節(jié)點。 窮舉式搜索 ?廣度優(yōu)先搜索：優(yōu)先在同一級節(jié)點中考察，只有當同一級節(jié)點擴展完以后，才擴展下一級節(jié)點。 ? 步 6 擴展 N，將其所有子節(jié)點配上指向 N的返回指針依次放入 OPEN表的 首部 ，轉(zhuǎn)步 2。 ? 步 5 若 N不可擴展，則轉(zhuǎn)步 2。 其中 g(x)是代價函數(shù)， h(x)是啟發(fā)函數(shù)。 h(x)為啟發(fā)式函數(shù)。終止節(jié)點一定是端節(jié)點，反之不成立。如果初始節(jié)點也被標記為不可解節(jié)點，則搜索失敗，退出。 ? （ 3）、任何一方都要選取對自己最有利而對對方最不利的對策。 ? （ 2）為了找到當前的最優(yōu)行動方案，需要考慮每一方案實施后對方可能采取的所有行動，并計算可能的得分。這一過程稱為 ?剪枝。 ? 產(chǎn)生式規(guī)則與邏輯蘊含式的區(qū)別與聯(lián)系 ?邏輯蘊含式是產(chǎn)生式，反之則不然。動態(tài)數(shù)據(jù)結(jié)構(gòu)，存放初始事實、中間結(jié)果和最后結(jié)果。以某種動態(tài)數(shù)據(jù)結(jié)構(gòu)來組織； ? 推理機 。 ? 產(chǎn)生式的含義是：如果前提 P被滿足，則可推出結(jié)論 Q或執(zhí)行 Q所規(guī)定的動作。對“ 或 ”節(jié)點，選取其子節(jié)點中 最大 的得分作為父節(jié)點的得分；對“ 與 ”節(jié)點，取其子節(jié)點中 最小 的一個得分作為父節(jié)點的得分。自己一方擴展的節(jié)點是“或”的關系，對方擴展的節(jié)點之間是“與”的關系。計算一下擴展這個節(jié)點可能要付出的代價，并選擇代價最小的節(jié)點進行擴展。若有，則標記它們?yōu)榭山夤?jié)點，并將它們也放入 CLOSED表，然后由它們的可解 返回推斷 其先輩節(jié)點的可解性，并對其中的可解節(jié)點進行標記。 狀態(tài)圖問題求解 ?問題的狀態(tài)圖表示 ? 狀態(tài)：節(jié)點；記錄、對象、 …… ? 規(guī)則：邊；數(shù)據(jù)對 (x,y)，條件語句 (if x …y…) ， …… ? 一個問題的狀態(tài)圖表示為一個三元組 (S,F,G) ? S:初始狀態(tài)集； G:目標狀態(tài)集； F:狀態(tài)轉(zhuǎn)換規(guī)則集合 ?迷宮問題的狀態(tài)圖表示 P99 ?顯式狀態(tài)圖 ?八數(shù)碼問題的狀態(tài)圖表示 P100 ?隱式狀態(tài)圖 ? TSP問題 與或圖 ?與或圖的引入 ?本質(zhì)：復雜問題分解為簡單問題 ?與或樹 與或圖 ?狀態(tài)圖和與或圖的關系 目標 目標 初始節(jié)點 與或圖 ?解樹：問題的求解路徑構(gòu)成的樹。 啟發(fā)式搜索的 A算法和 A*算法 ? 步 6 擴展 N，計算每個子節(jié)點 x的估價函數(shù)值 f(x)，并對這組子節(jié)點作如下處理： ?（ 1）考察是否有已在 OPEN表或 CLOSED表中存在的節(jié)點；若有，則再考察其中有無 N的先輩節(jié)點，若有則刪除之；對于其余節(jié)點，也刪除之，但由于它們又被第二次生成，因而需考慮是否修改已經(jīng)存在于 OPEN表或CLOSED表中的這些節(jié)點及其后裔的返回指針和 f(x)值，修改原則是“抄 f(x)值小的路走”； ?（ 2）對其余子節(jié)點配上指向 N的返回指針后放入 OPEN表中，并對 OPEN表按 f(x)值以升序排序，轉(zhuǎn)步 2。 ? 代價： g(xj)