人工智能技術導論

1、人工智能技術導論第1頁，共187頁，2022年，5月20日，10點57分，星期日參考書人工智能馬少平、朱小燕編著，清華大學出版社人工智能及其應用蔡自興、徐光祐編著，清華大學出版社 Artificial Intelligence A New Synthesis(人工智能) Nils J.Nilsson 第2頁，共187頁，2022年，5月20日，10點57分，星期日第一章 人工智能概述人工智能的概念人工智能的研究途經與方法人工智能的分工領域人工智能的基本技術人工智能的發(fā)展概括第3頁，共187頁，2022年，5月20日，10點57分，星期日什么是人工智能人工智能(Artificial Intell

2、igence)是指由計算機實現的人造智能。作為一門學科，人工智能可定義為：人工智能是一門研究如何構造智能機器（智能計算機）或智能系統(tǒng)，使它能模擬、延伸、擴展人類智能的學科人工智能是一門交叉邊緣學科，與人工智能有關的學科有：計算機科學、數學、語言學、神經生理學、神經心理學、腦科學、認知科學、邏輯學、控制論等第4頁，共187頁，2022年，5月20日，10點57分，星期日什么是人的智能智能是人腦的屬性和產物。智能具有的主要特征：A、具有感知能力。通過視覺、聽覺、觸覺、味覺和嗅覺感知外部世界。B、具有記憶與思維能力。記憶能存儲由感知器官感知到的外部信息以及由思維所產生的知識。思維用于對記憶的信息進行

3、處理。思維可分為邏輯思維和形象思維。C、具有學習能力及自適應能力。D、具有行為能力。發(fā)現規(guī)律 應用規(guī)律 分析問題 解決問題圖靈測試中文屋子問題（約翰希爾勒）第5頁，共187頁，2022年，5月20日，10點57分，星期日為什么要研究人工智能現有計算機系統(tǒng)的局限性。 智能低下、缺乏自學習、自適應、自優(yōu)化能力。人類智能的局限性。 學習能力因人而異、學習速度慢、效率低。信息化社會的迫切要求。第6頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的目標近期目標：使現有的電子數字計算機能模擬人類的部分智能行為。遠期目標：制造智能計算機，使計算機具有看、聽、說等感知和交互能力、具有聯想、

4、推理、理解、學習等高級思維能力，還要有分析問題、解決問題和發(fā)明創(chuàng)造的能力。深藍（32CPU，200萬次/秒，200萬個棋局）第7頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的表現形式智能軟件智能設備智能網絡智能計算機智能機器人智能體(Agent) (艾真體)第8頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的研究途徑與方法結構模擬（神經計算、生理學派、連接主義） 模擬人腦的神經網絡結構實現智能。主要特征：1、通過神經元之間的并行協同作用實現信息處理，具有并行性、動態(tài)性、全局性。2、通過神經元間分布式的物理聯接存儲信息。聯想記憶、容錯性。3、通過神經

5、元間連接強度的動態(tài)調整實現自學習和自適應功能。4、善于模擬人類的形象思維過程。第9頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的研究途徑與方法功能模擬（符號主義、心理學派、邏輯學派） 以人腦的心理模型為基礎，將問題或知識表示成某種邏輯網絡，采用符號推演的方法，實現搜索、推理和學習等功能。主要特征：1、立足于邏輯運算和符號操作，適合于模擬人的邏輯思維過程。2、知識用顯式的符號表示，容易表達人的心理模型。3、現有的數字計算機可以方便地實現高速的符號處理。4、能與傳統(tǒng)的符號數據庫進行鏈接，易于模塊化。5、以知識為基礎。第10頁，共187頁，2022年，5月20日，10點57分

6、，星期日人工智能的研究途徑與方法行為模擬（行為主義、進化主義、控制論學派）基于感知-行為模型的研究途徑和方法。模擬人在控制過程中的智能活動和行為特征：自尋優(yōu)、自適應、自組織、自學習。強調智能系統(tǒng)與環(huán)境的交互，認為智能取決于感知和行動,智能行為可以不要知識。智能只有放在環(huán)境中才是真正的智能，智能的高低體現在對環(huán)境的適應性上Brooks，機器蟲第11頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的分支領域基于腦功能模擬的領域劃分1、機器感知（信息輸入）。使計算機具有類似于人的感知能力，能通過“感知”直接從外界獲取信息，是對人的感知的模擬及延伸。機器視覺、機器聽覺。相關學科：模

7、式識別（語音識別、圖像識別）。 信息-電信號序列-預處理-提取特征-模式匹配2、機器聯想?；趦热莸穆撓?，與具體存儲位置無關。聯想存儲技術。3、機器推理。又稱為計算機推理、自動推理，是人工智能的核心課題之一。推理：從一些已知判斷（前提）推出一個新判斷（結論）的思維過程。演繹推理、歸納推理、類比推理確定性推理、不確定性推理基于概率邏輯的或然推理(隨機性)、基于模糊邏輯的似然推理(模糊性)串行推理、并行推理第12頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的分支領域4、機器學習。使機器自己獲取知識。對人類已有知識的獲取、對客觀規(guī)律的發(fā)現、對自身行為的修正。機器學習分為：機械

8、學習、指導學習、解釋學習、類比學習、示例學習、發(fā)現學習等。這些屬于符號學習。另外還有神經網絡學習。5、機器理解。圖形理解（物景分析）、自然語言理解。理解是感知的延伸和深化。6、機器行為（機器人行動規(guī)劃）。智能機器人的核心技術，反映了機器人的智能水平解決問題依靠規(guī)劃功能確定行動步驟和動作序列任務：在一個特定的工作區(qū)域中自動生成從初始狀態(tài)到目標狀態(tài)的動作序列、運動路徑和軌跡的控制程序第13頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的分支領域基于研究途徑和實現技術的領域劃分1、符號智能以符號知識為基礎，通過符號推理進行問題求解知識工程(知識獲取、知識表示、知識管理、知識運用

9、、知識庫系統(tǒng))、符號處理2、計算智能以數據為基礎，通過數值計算進行問題求解人工神經網絡、進化計算(遺傳算法、遺傳程序設計、進化規(guī)劃、進化策略)、模糊技術、人工生命第14頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的分支領域基于應用領域的領域劃分1、難題求解難題的概念路徑規(guī)劃、組合優(yōu)化、天氣預報、股市分析、市場預測、機器博弈NP (Nondeterministic Polynomial) 和NPC (Nondeterministic Polynomial Complete)問題難題求解技術能促進人工智能其他領域的發(fā)展2、自動定理證明自然演繹法、判定法、定例證明器、計算機輔

10、助證明四色問題(1976.6,K.Appeel)。3、自動程序設計超級編譯系統(tǒng)自動程序綜合和自動程序驗證。第15頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的分支領域4、自動翻譯。機器翻譯。自然語言理解。一邊站著一個人他想起來了5、智能控制1965，KS.FU (傅京孫)提出將啟發(fā)式推理規(guī)則用于學習控制系統(tǒng)6、智能管理。人工智能與管理科學、系統(tǒng)工程和計算機技術的結合。7、智能決策。人工智能應用于決策支持系統(tǒng)。8、智能通訊。在通訊的各個環(huán)節(jié)和層次上實現智能化。如網控、轉接、信息轉換等。使通訊網隨時運行于最佳狀態(tài)。9、智能仿真。仿真是在三種類型知識-描述性知識、目的性知識和

11、處理知識的基礎上產生另一種形式的知識-結論性知識。10、智能CAD。人工智能應用于CAD的設計自動化、智能交互、智能圖形學、自動數據采集方面。11、智能CAI。人工智能應用于CAI： 自動生成各種問題與練習、自動選擇與調整教學內容和進度、自動生成答案、自然語言理解能力、不斷改善教學策略。第16頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的分支領域基于應用系統(tǒng)的領域劃分1、專家系統(tǒng)?；谌祟悓＜抑R的程序系統(tǒng)。能模擬專家的思維方式。2、知識庫系統(tǒng)。3、智能數據庫系統(tǒng)。傳統(tǒng)數據庫系統(tǒng)+人工智能。4、智能機器人系統(tǒng)。具備感知、思維、人-機通訊和運動能力。第17頁，共187頁，

12、2022年，5月20日，10點57分，星期日人工智能的分支領域基于計算機系統(tǒng)結構的領域劃分1、智能操作系統(tǒng)。并行性、分布性和智能性。2、智能多媒體系統(tǒng)。人工智能與多媒體技術的有機結合。3、智能計算機系統(tǒng)。4、智能網絡系統(tǒng)。模糊和神經網絡技術應用于網絡的業(yè)務量預測和控制、資源動態(tài)分配、動態(tài)路由選擇等方面。第18頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的分支領域基于實現工具與環(huán)境的領域劃分1、智能軟件工具。人工智能程序設計語言，如表處理語言LISP、邏輯程序設計語言PROLOG、面向對象程序設計語言Smalltalk等。知識表示語言FRL、OPS5。專家系統(tǒng)工具、知識工

13、程工具等。2、智能硬件平臺。直接支持智能系統(tǒng)開發(fā)和運行的機器硬件。第19頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的分支領域基于體系結構的領域劃分集中式人工智能（個體智能）分布式人工智能（群體智能）個體智能的組合或疊加DPS（分布式問題求解），自頂向下MAS（多智能體系統(tǒng)），自底向上第20頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的基本技術推理技術。推理是智能的核心。推理以邏輯為基礎?；谥^詞邏輯的自然演繹推理和歸結反演推理?；诜菢藴蔬壿嬋缍嘀颠壿嫛⒛B(tài)邏輯、時態(tài)邏輯、模糊邏輯、非單調邏輯的推理。搜索技術。人工智能的基本技術。許多智能活動的

14、過程，都可以看作或抽象為一個“問題求解”過程。“問題求解”就是在問題空間中進行搜索的過程。盲目搜索、啟發(fā)式搜索。神經網絡搜索。知識表示與知識庫技術。知識表示是指知識在計算機中的表示方式。知識表示要符合知識的邏輯結構和物理結構，并適合于計算機存儲和處理。知識庫由知識構成。知識的組織、管理、維護和優(yōu)化。第21頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的基本技術歸納技術。機器自動提取概念、獲取知識、發(fā)現規(guī)律的技術。歸納技術與知識獲取和機器學習密切相關。基于符號處理的歸納和基于神經網絡的歸納。數據庫知識發(fā)現（KDD, Knowledge Discovery in Databa

15、se) 和數據挖掘(Data Mining)技術。聯想技術。聯想記憶，聯想存儲。第22頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的發(fā)展概況孕育期（1956年之前）1、公元前，Aristotle提出形式邏輯的一些主要定律，三段論至今仍是演繹推理的基本依據。2、培根（1561-1626）曾系統(tǒng)地提出了歸納法。提出“知識就是力量”3、德國數學家Leibniz（1646-1716）提出了萬能符號和推理計算的思想，為數理邏輯的產生和發(fā)展奠定了基礎。4、英國邏輯學家Boole（1815-1864）創(chuàng)立了布爾代數，在思維法則一書中首次用符號語言描述了思維活動的基本推理法則。5、英國

16、數學家Turing于1936年提出理想計算機的數學模型，即圖靈機。Turing測試。6、1943年，McCulloch 和 Pitts提出M-P神經元模型。7、1946年，世界上第一臺電子計算機誕生。第23頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的發(fā)展概況人工智能學科的產生（1956年） 1956年夏季，McCarthy, Minsky, Lochester, Shannon, More, Samuel, Selfridge, Solomonff, Newell, Simon等十人在Dartmouth大學召開歷時兩個多月的研討會，討論機器智能的有關問題。由McCar

17、thy提出“人工智能”一詞，人工智能從此成為一門學科。第24頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的發(fā)展概況符號主義AI發(fā)展概況1、形成（1956-1965）（人工智能的推理期。結構良好問題。搜索策略和算法）（1）、1956年，Samuel的跳棋程序。1959,1962（2）、定理證明方面，1956年Newell等的邏輯理論機（LT）程序；1958年，王浩的工作；1965年，Robinson提出的消解原理。（3）、模式識別方面，1959年Selfridge的模式識別程序；1965年Roberts編制了可以分辨積木構造的程序。（4）、問題求解方面。1960年，New

18、ell的通用問題求解(GPS)程序。（5）、1960年，McCarthy研制成功LISP語言。第25頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的發(fā)展概況人工智能的知識期（1965-70年代末）（1）、專家系統(tǒng)方面。1965年，Feigenbaum的專家系統(tǒng)DENDRAL，1968年投入使用。DENDRAL對知識表示、存儲、獲取和推理的技術為以后的專家系統(tǒng)的建造樹立了榜樣，對AI的發(fā)展產生了深刻的影響。之后著名的專家系統(tǒng)有：醫(yī)學專家系統(tǒng)MYCIN，地質勘探專家系統(tǒng)PROSPECTOR，計算機配置專家系統(tǒng)R1等。（2）、1969年，國際人工智能聯合會議(IJCAI)召開。

19、1970年，“Artificial Intelligence”雜志創(chuàng)刊。（3）、1977年，Feigenbaum在第五屆國際人工智能會議上，提出了“知識工程”的概念。發(fā)展期（20世紀80年代后） 專家系統(tǒng)與知識工程在理論、技術和應用方面都有長足的進步和發(fā)展。出現了多專家系統(tǒng)、大型專家系統(tǒng)、微專家系統(tǒng)、分布式專家系統(tǒng)等。智能管理信息系統(tǒng)、智能決策支持系統(tǒng)、智能控制系統(tǒng)等。第26頁，共187頁，2022年，5月20日，10點57分，星期日人工智能的發(fā)展概況連接主義途徑發(fā)展概況1、1943年，神經生理學家McCulloch 和Pitts提出M-P神經元模型。1944年，Hebb提出Hebb學習規(guī)則。

20、2、1957年，Rosenblatt提出Perceptron單層神經網絡模型。1962年，Widrow提出自適應線性元件Adaline。應用于天氣預報、電子線路板分析、人工視覺等。3、1969年，Minsky和Papert發(fā)表Perceptrons，證明了單層人工神經網絡無法實現一個簡單的異或邏輯函數XOR，把神經網絡的研究帶入低谷。4、在低谷期，Kohonen Grossberg和Anderson等人仍堅持研究，取得了一些有價值的結果。5、20世紀80年代中期以后，神經網絡研究復蘇，掀起了新一輪研究熱潮。1986年，Hopfield網絡成功應用于TSP問題。1986年Rumelhart提出B

21、P算法，解決了多層人工神經元網絡的學習問題。1987年6月，第一屆國際神經網絡大會（IJCNN）召開，盛況空前。目前，NN與專家系統(tǒng)、知識工程成為AI的兩個主流方向。NN在智能控制、信號處理、最優(yōu)化、知識工程等領域都有成功應用。第27頁，共187頁，2022年，5月20日，10點57分，星期日當前發(fā)展趨勢1、傳統(tǒng)以符號處理為中心的人工智能與神經網絡的結合。神經網絡：識別 聯想 學習 適應，負責對外界的感知和交互專家系統(tǒng)：判斷 推理 搜索，負責高層的決策與控制2、新理論、新技術的出現。Fuzzy, Genetic Algorithm, Chaos, Artificial life, Soft C

22、omputing, Computational Intelligence, Rough set, Data Mining, Knowledge discovery in database, Data warehouse, Situated AI, Agent-based distributed AI 等。第28頁，共187頁，2022年，5月20日，10點57分，星期日第二章 基于謂詞邏輯的機器推理謂詞、函詞、量詞個體：研究對象中可以獨立存在的具體的或抽象的客體。個體用個體常元或個體變元表示，如x,y,z,a,b,c,等。謂詞：描述個體性質及個體之間相互關系的詞。 如P、Q、R，等。例、命題“

23、2是素數”中，2是個體，“是素數”是謂詞?？杀硎緸镻(2).函詞（函數）：某些個體是其它個體的函數，描述這種關系的詞稱為函詞。例、命題“小李的父親是醫(yī)生”可表示為Doctor(father(Li).量詞：存在量詞“ ”；全稱量詞“ ”。例、“任何實數的平方都非負”可表示為 x(R(x) N(s(x)。 “存在偶素數”可表示為 x(E(x) P(x)。第29頁，共187頁，2022年，5月20日，10點57分，星期日一些命題的表示凡是人都有名字 x(M(x) N(x)不存在最大的整數x(G(x) y(G(y) D(x,y) x(G(x) y(G(y) D(y,x)對所有的自然數，均有X+YXx

24、y(N(x) N(y) S(x,y,x)某些人對某些食物過敏 x y(M(x) F(y) G(x,y)第30頁，共187頁，2022年，5月20日，10點57分，星期日謂詞公式項的定義：1、個體常元和個體變元是項；2、設f是n元函詞符號， t1, t2 , , tn是項，則f(t1, t2 , , tn)是項。3、只有有限次使用1，2得到的符號串才是項。原子公式：P是n元謂詞， t1, t2 , ,( tn是項，則P(t1, t2 , , tn)稱為原子謂詞公式(原子公式)(原子)。謂詞公式：1、原子公式是謂詞公式；2、若A、B是謂詞公式，則 A，A B，A B，A B，A B， xA， xA

25、也是謂詞公式；3、只有有限次地應用步驟1，2形成的符號串才是謂詞公式。轄域： xA 和 xA中，x稱為量詞的指導(作用)變元，A稱為x的轄域。轄域中與該量詞的指導變元相同的變元稱為約束變元，其它變元(如果存在的話)稱為自由變元。例、xP(x)； x(H(x) G(x,y)； xA(x) B(x)約束變元的改名 ：兩個規(guī)則第31頁，共187頁，2022年，5月20日，10點57分，星期日部分邏輯蘊含式（p59-p60)析取三段論： A (A B) B假言推理（分離規(guī)則）： A (A B) B拒取式： B (A B) A假言三段論： (A B) (BC) A C二難推論: (A B) (A C)

26、(BC) C全稱指定規(guī)則US (Universal Specification) ： xA(x) A(y)，y是個體域中任一確定元素。存在指定規(guī)則ES (Existential Specification)： xA(x) A(c)，c是個體域中某一確定元素。全稱推廣規(guī)則UG (Universal Generalization) ：A(y) xA(x)，y是個體域中任一確定元素。存在推廣規(guī)則 EG (Universal Generalization) ：A(c) xA(x)，c是個體域中某一確定元素。第32頁，共187頁，2022年，5月20日，10點57分，星期日自然演繹推理以謂詞公式的等價式

27、及推理定律為基礎進行的推理稱為自然演繹推理。例見教材p61。推理過程是一個符號變換過程，類似于人們使用自然語言進行推理的思維過程。推理與謂詞公式的含義無關，是一種形式推理。自然演繹推理在機器上實施比較困難推理規(guī)則太多應用規(guī)則需要很強的模式識別能力中間結論的指數遞增第33頁，共187頁，2022年，5月20日，10點57分，星期日子句集定義1 原子謂詞公式及其否定稱為文字；若干個文字的一個析取式稱為一個子句；由r個文字組成的子句稱為r-文字子句，1-文字子句稱為單元子句，不含任何文字的子句稱為空子句，記為或NIL。定義2 對一個謂詞公式G，通過一定的步驟得到的子句集合S稱為G的子句集。第34頁，

28、共187頁，2022年，5月20日，10點57分，星期日子句集（1）、利用等價式A B A B和 A B (A B) (B A)消去聯結詞“ ” 和 “ ”。 （2）、縮小否定聯結詞的作用范圍，使其僅作用于原子公式?？衫孟铝械葍r式： A A； (AB) A B， (A B) A B；xA(x) x A(x)， xA(x) x A(x)（3）、重新命名變元名，使不同量詞約束的變元有不同的名字。（4）、消去存在量詞。若存在量詞不在全稱量詞的轄域內，則用一個常量符號替換該存在量詞轄域中的相應約束變元。這樣的常量稱為Skolem常量；若該存在量詞在一個或多個全稱量詞的轄域內，則用這些全稱量詞指導變元

29、的一個函數替換該存在量詞約束的變元。這樣的函數稱為Skolem函數。例如x1 x2 xnyP(x1,x2, xn,y)中y可用Skolem函數f(x1,x2, xn)替換為x1 x2 xnP(x1,x2, xn,f(x1,x2, xn)。第35頁，共187頁，2022年，5月20日，10點57分，星期日子句集（5）、把全稱量詞全部移到公式的左邊。（6）、把全稱量詞后面的公式利用等價關系A(B C) (AB) (A C)化為子句的合取式，得到的公式稱為Skolem標準形。Skolem標準形的一般形式為x1 x2 xnM，其中M是子句的合取式。（7）、消去全稱量詞。（8）、對變元更名，使子句間無同

30、名變元。（9）、消去合取詞 ，以子句為元素組成的集合稱為謂詞公式的子句集。例：把如下謂詞公式化為子句集。 xyP(x,y) yQ(x,y)R(x,y)第36頁，共187頁，2022年，5月20日，10點57分，星期日子句集求解過程 xyP(x,y) yQ(x,y)R(x,y)1) xyP(x,y) yQ(x,y) R(x,y)2) xyP(x,y) yQ(x,y) R(x,y)3) xyP(x,y) zQ(x,z) R(x,z)4) xP(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

31、,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 不可滿足當且僅當其子句集S不可滿足。子句集S是不可滿足的是指其全部子句的合取式是不可滿足的。第37頁，共187頁，2022年，5月20日，10點57分，星期日命題邏輯中的歸結原理要證明在前提P下結論Q成立，即是證明P Q永真，這只須證明P Q不可滿足。根據定理1，只須證明P Q的子句集不可滿足。由于子句之間是合取關系，只要有一個子句不滿足，則整個子句集不可滿足。由于空子句是不可滿足的，所以如果

32、子句集中包含空子句，則該子句集是不可滿足的。若子句集中不包含空子句，則可通過Robinson提出的歸結原理對子句集進行歸結，歸結過程保證子句集的不可滿足性不變。一旦歸結出空子句，則證明結束。因此，歸結原理把定理的證明化為子句集中歸結出空子句的過程。第38頁，共187頁，2022年，5月20日，10點57分，星期日命題邏輯中的歸結原理定義、設L是一個文字，則稱L與L為互補文字。定義、設C1、C2是命題邏輯中的兩個子句， C1 中有文字L1 ， C 中有文字L，且L1與L互補， 從C1，C中分別刪除L1 ， L，再將剩余部分析取起來，構成的新子句C1稱為C1與C2的歸結式（消解式）， C1，C2稱

33、為C1的親本子句。C1 = PQ R, C2 = Q S, C1 = P R S定理、歸結式C1是其親本子句C1與C2的邏輯結論。推論、設C1，C2是子句集S的兩個子句， C1是它們的歸結式，則（）若用C1代替C1和C2后得到新子句集S1，則由S1的不可滿足性可推出原子句集S的不可滿足性。即S1不可滿足S不可滿足）若把C1加入到S中，得到新子句集S，則S與S在不可滿足意義上是等價的。即S2不可滿足 S不可滿足第39頁，共187頁，2022年，5月20日，10點57分，星期日命題邏輯中的歸結原理例、用歸結原理證明R是P, (P Q) R， (SU) Q，U的邏輯結果。求子句集P, (PQ)R,

34、(SU) Q, U, RP, (P Q) R, ( S U) Q, U, RP, P Q R, S Q , U Q, U, R (子句集)歸結演繹P Q R R P Q P Q P QQ U Q U U U 第40頁，共187頁，2022年，5月20日，10點57分，星期日替換與合一問題的提出謂詞邏輯和命題邏輯中使用歸結原理的差別C1 = P (x) Q (x) , C2 = P (a) R (y)C1 = P (a) Q (a) , C2 = P (a) R (y)定義 一個替換(Substitution)是形如t1/x1 , t2/x2 , tn/ xn 的有限集合，其中t1 , t2 ,

35、tn 是項(替換的分子)， x1, x2 ,xn是互不相同的個體變元(替換的分母)。ti / xi表示用ti代換xi 。 ti與xi不同，xi也不能循環(huán)出現在tj中(j=1,2,n)?；鎿Q(t1 , t2 ,tn 均不含變元)、空替換例：a/x, g(c)/y, f(g(b)/z ，g(y)/x, f(x)/y第41頁，共187頁，2022年，5月20日，10點57分，星期日替換與合一定義7 設t1 / x1, t2 / x2 ,tn / xn 是一個替換，E是一個表達式，把E中出現的所有個體變元xi都用ti 替換，記為E ，得到的結果稱為E在下的替換實例(Instance)。Eg：E=P(

36、x,y,g(z), a / x, f(b) /y ,c /z ，E= P(a,f(b),g(c)定義 設t1 / x1, t2 / x2 ,tn / xn ， u1 / y1, u2 / y2 ,um / ym 是兩個替換，則將集合t1 / x1, t2 / x2 ,tn / xn，u1 / y1, u2 / y2 ,um / ym 中符合下列條件的兩種情形刪除： ti / xi ，當ti xi ui / yi ，當yi x1, x2 , xn 得到的集合仍是一個替換，稱為與的復合或乘積，記為 例: 設 =f(y)/x,z/y =a/x,b/y,y/z =f(b)/x,y/y,a/x,b/y,

37、y/z=f(b)/x,y/z第42頁，共187頁，2022年，5月20日，10點57分，星期日替換與合一定義 設S= F1, F2 , Fn 是一個原子謂詞公式集，若存在一個替換，使得F1 F2 Fn ，則稱為S的一個合一(Unifier)，并稱S為可合一的。一個公式集的合一一般不唯一定義10 設是公式集S的一個合一，如果對S的任何一個合一，都存在一個替換，使得 ，則稱為S的一個最一般合一(Most General Unifier)，簡稱MGU 設S=P(u,y,g(y),P(x,f(u),z),有=u/x,f(u)/y,g(f(u)/z 對其它某個合一,如=a/x,f(a)/y,g(f(a)

38、/z,a/u，可找到替換=a/u，使得 第43頁，共187頁，2022年，5月20日，10點57分，星期日替換與合一定義11 設S是一個非空的具有相同謂詞名的原子公式集，從S中各公式的左邊第一個項開始，同時向右比較，每一組不都相同的項的差異部分組成的集合稱為S的差異集。公式集S=P(a,x,f(g(y) , P(z,h(z,u),f(u)的差異集為a,z, x,h(z,u), g(y),u 第44頁，共187頁，2022年，5月20日，10點57分，星期日替換與合一設S為一非空有限具有相同謂詞名的原子謂詞公式集，求S的MGU的算法：(1) 令k=0, Sk=S, k= （ 表示空替換）(2)

39、若Sk只含有一個謂詞公式，則算法停止， k就是要求的最一般合一(3) 求Sk的差異集Dk(4) 若Dk中存在元素 xk 和 tk ，其中xk是變元， tk是項且xk不在tk中出現，則置Sk+1 = Sktk /xk ， k+1 = ktk /xk ，k=k+1，然后轉步(2) (5) 算法停止，S的最一般合一不存在第45頁，共187頁，2022年，5月20日，10點57分，星期日替換與合一求S=P(a,x,f(g(y) , P(z,h(z,u),f(u)的MGUk=0S0=S, 0= , D0=a,z1= 0a/z=a/zS1=S0a/z =P(a,x,f(g(y) , P(a,h(a,u),

40、f(u)k=1D1=x,h(a,u)2= 1h(a,u)/x=a/z h(a,u)/x=a/z, h(a,u)/xS2=S1h(a,u)/x= P(a,h(a,u),f(g(y) , P(a,h(a,u),f(u)第46頁，共187頁，2022年，5月20日，10點57分，星期日替換與合一S2=S1h(a,u)/x= P(a,h(a,u),f(g(y) , P(a,h(a,u),f(u)k=2D2=g(y),u3= 2g(y)/u=a/z, h(a, g(y)/x, g(y)/uS3=S2g(y)/u=P(a,h(a,g(y),f(g(y), P(a,h(a,g(y),f(g(y) = P(a

41、,h(a,g(y),f(g(y)k=3S3為單元素集，所以3為所求的S的MGU說明：MGU可能是不唯一的，如Dk=xk,yk時第47頁，共187頁，2022年，5月20日，10點57分，星期日謂詞邏輯中的歸結原理定義12 設C1,C2是兩個沒有相同變元的子句，L1,L2分別是C1,C2中的兩個文字，如果L1與L2有最一般合一 ，則子句C12=(C1-L1) (C2-L2)，稱作C1和C2的二元歸結式(二元消解式)。 C1和C2稱為C12的親本子句， L1，L2稱為消解文字。例：C1=P(x)Q(x) , C2= P(a)R(y), C12=Q(a)R(y)說明：當子句內部有可合一的文字時，應在

42、歸結前進行合一，使子句最簡例：C1=P(x) P(f(a)Q(x)，則C1=P(f(a)Q(x)歸結原理：C1 C2 (C1-L1) (C2-L2)第48頁，共187頁，2022年，5月20日，10點57分，星期日謂詞邏輯中的歸結原理歸結時的注意事項謂詞的一致性. 名稱不一致的謂詞不能歸結 P (x) ，R (x) 不能歸結常量的一致性. 含有不同常量的謂詞不能歸結P(a,) ， P(b,) 不能歸結變量與函數P(x,x,) ，P(x,f(x),) 不能歸結P(x,x,) ，P(x,f(y),) 能歸結不能同時消去兩個互補對P Q 與 P Q 不能同時消去第49頁，共187頁，2022年，5月

43、20日，10點57分，星期日歸結反演歸結反演：應用歸結原理證明定理的過程若F為已知前提的公式集，Q為結論，用歸結反演證明Q為真的步驟是：（1）、否定Q，得到Q；（2）、把Q并入到公式集F中，得到F, Q；（3）、把公式集F, Q化為子句集S；（4）、應用歸結原理對子句集S中的子句進行歸結，并把每次歸結得到的歸結式都并入S中。如此反復進行，直到出現空子句，就證明了Q為真。定理5（歸結原理的完備性）、如果子句集S是不可滿足的，則必存在一個由S推出空子句的歸結序列。第50頁，共187頁，2022年，5月20日，10點57分，星期日歸結反演舉例例：自然數都是大于零的整數；所有整數不是偶數就是奇數；偶數

44、除以2是整數。求證：所有自然數不是奇數就是其一半為整數的數。證明：前提： F1 ：x(N(x) GZ(x) I(x) N(x)：x是自然數 F2 ：x(I(x) E(x) O(x) GZ(x)：x0 I(x)：x是整數 F3 ：x(E(x) I(h(x) E(x)：x是偶數 O(x)：x是奇數 結論：G：x(N(x) O(x) I(h(x) h(x)：half(x) F1、 F2、 F3 及G 化為子句集：（1） N(x)GZ(x)（2） N(y)I(y)（3） I(z)E(z) O(z)（4） E(u)I(h(u)（5）N( c)（6） O(c)（7） I(h( c)歸結： （8）I( c)

45、 ( (2), (5), c/y ) （9） I(c) E( c) ( (3), (6), c/z )（10） E( c) ( (8), (9) )（11） I(h( c) ( (4), (10), c/u )（12） ( (7), (11) )第51頁，共187頁，2022年，5月20日，10點57分，星期日應用歸結原理求解應用歸結原理求取問題答案的步驟把已知前提用謂詞公式表示出來，并化為子句集S把待求解問題也用謂詞公式表示出來，然后把它的否定與謂詞ANS構成析取式。ANS的變元應與問題的變元完全一致把此析取式化為子句集，并把該子句集并入S中得到子句集S對S應用歸結原理進行歸結若得到歸結式A

46、NS，則答案就在ANS中第52頁，共187頁，2022年，5月20日，10點57分，星期日應用歸結原理求解例：設A、B、C三人中有人從不說真話，也有人從不說假話，某人向這三人分別提出同一個問題：誰是說謊者？A答：“B和C都是說謊者”；B答：“A和C都是說謊者”；C答：“A和B中至少有一個是說謊者”。問：誰是老實人？解、設T(x)表示x說真話。如果A說的是真話，則有： T(A) T(B) T(C )如果A說的是假話，則有： T(A) T(B) T(C )。 同理，對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(

47、B )第53頁，共187頁，2022年，5月20日，10點57分，星期日應用歸結原理求解化為子句集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)并入S8) 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是老實人。無論如何歸結，推不出ANS(A

48、), ANS(B)第54頁，共187頁，2022年，5月20日，10點57分，星期日歸結策略 歸結反演的一般過程。步1將子句集S置入CLAUSES表；步2若空子句NIL在CLAUSES中，則歸結成功，結束。步3若CLAUSES表中存在可歸結的子句對，則歸結之，并將歸結式并入CLAUSES表，轉步；步4歸結失敗，退出。窮舉算法（廣度優(yōu)先策略）第一輪：將原子句集S中的子句兩兩歸結，產生的歸結式集合記為S1，再將S1并入CLAUSES表；第二輪：將新的CLAUSES表，即S S1中的子句與S1中的子句兩兩歸結，產生的歸結式集合記為S2，再將S2并入CLAUSES；第三輪：將新的CLAUSES表即S

49、S1 S2中的子句與S2中的子句兩兩歸結，。如此下去，直到出現空子句。第55頁，共187頁，2022年，5月20日，10點57分，星期日歸結策略例1 設有如下的子句集，用窮舉算法歸結如下：S： （1） PQ （2） PQ （3） P Q （4） P QS1： （5） Q (1), (2) （6） P (1), (3) （7） Q Q (1), (4) （8） P P (1), (4) （9） Q Q (2), (3) （10） P P (2), (3) （11） P (2), (4) （12） Q (3), (4)S2：（13） P Q (1), (7) （14） P Q (1), (8)第5

50、6頁，共187頁，2022年，5月20日，10點57分，星期日歸結策略 （15） P Q (1), (9) （16） P Q (1), (10) （17） Q (1), (11) （18） P (1), (12) （19） Q (2), (6) （20） PQ (2), (7) （21） PQ (2), (8) （22） PQ (2), (9) （23） PQ (2), (10) （24） P (2), (12) （25） P (3), (5) （26） P Q (3), (7) （27） P Q (3), (8) （28） P Q (3), (9) （29） P Q (3), (10) （3

51、0） Q (3), (11) （31） P (4), (5) （32） Q (4), (6) （33） P Q (4), (7) （34） P Q (4), (8) （35） P Q (4), (9) （36） P Q (4), (10) （37） Q (5), (7) （38） Q (5), (9) （39） (5), (12)第57頁，共187頁，2022年，5月20日，10點57分，星期日歸結策略定義：設C1，C2是兩個子句，若存在替換，使得C1 C2 ，則稱子句C1類含C2 。 P(x)類含P(a) Q(y) P(x)類含P(a)刪除策略。在歸結過程中可隨時刪除以下子句：（1）、含有純

52、文字的子句。純文字是指在子句中無補文字的文字。P(x) Q(x,y) R(x)， P(a) Q(u,v)， Q(b,z)， P(w)解釋：永遠無法得到空子句（2）、含有永真式的子句；解釋：對子句集的不可滿足性不起作用（3）、被子句集中別的子句類含的子句。解釋：C=P(x)替換后得C=P(a)，D=P(a) Q(y)第58頁，共187頁，2022年，5月20日，10點57分，星期日歸結策略使用刪除策略，例1可簡化為： （1） PQ （7） P (2), (4) （2） PQ （8） Q (3), (4) （3） P Q （ 9） (5), (8) （4） P Q （5） Q (1), (2) （

53、6） P (1), (3)刪除策略的特點：刪除策略的思想是及早刪除無用字句，以避免無效歸結，縮小搜索空間。刪除策略是完備的。一個歸結策略是完備的，是指對于不可滿足的子句集，使用該策略進行歸結，最終必導出空子句。第59頁，共187頁，2022年，5月20日，10點57分，星期日歸結策略支持集策略支持集：目標公式的否定的子句集支持集策略：每次歸結時，兩個親本子句中至少要有一個是目標公式否定的子句或其后裔。支持集策略的特點：支持集策略實際是一種目標制導的反向推理。支持集策略是完備的。線性歸結策略在歸結過程中，除第一次歸結可都用初始子句集S中的子句外，其它的各次歸結至少要有一個親本子句是前次歸結的結果

54、。線性歸結策略的特點：完備、高效、與別的策略兼容。第60頁，共187頁，2022年，5月20日，10點57分，星期日歸結策略歸結策略的類型簡化性策略思想：盡量簡化子句和子句集，以減少和避免無效歸結。缺點：額外開銷 (eg:檢驗、真值計算)限制性策略思想：縮小搜索范圍，提高搜索效率有序性策略思想：給子句安排一定的順序，一邊盡快推出空子句歸結反演的一般算法步1將子句集S置入CLAUSES表；步2若空子句NIL在CLAUSES中，則歸結成功，結束。步3按某種策略在CLAUSES表中尋找可歸結的子句對，若存在則歸結之，并將歸結式并入CLAUSES表，轉步；步4歸結失敗，退出。第61頁，共187頁，20

55、22年，5月20日，10點57分，星期日第四章 圖搜索技術搜索：根據問題的實際情況不斷尋找可利用的知識，從而構造一條代價較少的推理路線，使問題得到圓滿解決的過程。應用：結構不良問題，無成熟算法；或有算法 ，但問題復雜，如博弈圖：由節(jié)點和有向邊組成的網絡圖的分類：或圖(狀態(tài)圖、直接圖)與或圖第62頁，共187頁，2022年，5月20日，10點57分，星期日狀態(tài)圖狀態(tài)圖的概念迷宮問題八數碼難題/華容道問題以上問題的本質：在某個有向圖中尋找目標或路徑，該有向圖稱為狀態(tài)空間圖或狀態(tài)圖。狀態(tài)是描述問題求解過程中任一時刻的狀況。引起狀態(tài)中某些分量發(fā)生變化，從而使問題從一個狀態(tài)變?yōu)榱硪粋€狀態(tài)的操作、規(guī)則、變

56、換稱為算符。問題求解就是尋找一個從初始狀態(tài)到目標狀態(tài)的算符序列的過程。問題求解過程可描述為一個有向圖，其中的節(jié)點代表狀態(tài)，邊表示狀態(tài)轉換之間的算符。2 31 8 47 6 51 2 38 47 6 5第63頁，共187頁，2022年，5月20日，10點57分，星期日狀態(tài)圖搜索搜索樹：搜索過程中經過的節(jié)點和邊按原圖的連接關系構成一個樹型的有向圖，稱為搜索樹。搜索方式樹式搜索：記錄搜索過程中所經過的所有節(jié)點和邊線式搜索：記錄當前認為是所找路徑上的節(jié)點和邊不可回溯 (隨機碰撞式搜索)可回溯 (窮舉式搜索)兩種方式下路徑的獲得樹式搜索：反向求解線式搜索：搜索線本身第64頁，共187頁，2022年，5月

57、20日，10點57分，星期日狀態(tài)圖搜索搜索策略盲目搜索(無向導) ：按預定的控制策略進行搜索，在搜索過程中獲得的中間信息不用來改進控制策略。啟發(fā)式搜索(有向導) ：在搜索過程中加入了與問題有關的啟發(fā)性信息，用以指導搜索朝著最有希望的方向前進，加速問題的求解過程并找到最優(yōu)解。按搜索范圍的擴展順序不同廣度優(yōu)先搜索深度優(yōu)先搜索第65頁，共187頁，2022年，5月20日，10點57分，星期日搜索算法CLOSED表和OPEN表樹式搜索算法步1 把初始節(jié)點放入OPEN表；步2 檢查OPEN表，若為空，則問題無解，退出；步3 移出OPEN表中第一個節(jié)點N并放入CLOSED表中，并編號為n;步4 考察節(jié)點N

58、是否為目標節(jié)點，若是，則搜索成功，退出；步5 若N不可擴展，則轉步2；步6 擴展節(jié)點N，生成所有子節(jié)點，對這組子節(jié)點作如下處理：（1）、如果有節(jié)點N的先輩節(jié)點，則刪除；（2）、如果有已存在于OPEN表的節(jié)點，也刪除；但刪除之前要比較其返回初始節(jié)點的新路徑與原路徑，如果新路徑“短”，則修改這些節(jié)點在OPEN表中的原指向父節(jié)點的指針，使其指向新的父節(jié)點。（3）、如果有已存在于CLOSED表中的節(jié)點，則作與（2）同樣的處理，并且再將其移出CLOSED表，放入OPEN表重新擴展；（4）、對其余子節(jié)點，配上指向父節(jié)點n的指針后放入OPEN表，對OPEN表按某種搜索策略排序后轉步2。第66頁，共187頁，

59、2022年，5月20日，10點57分，星期日搜索算法不回溯的線式搜索步1 把初始節(jié)點S0放入CLOSED表中；步2 令N= S0 ；步3 若N是目標節(jié)點，則搜索成功，結束;步4 若N不可擴展，則搜索失敗，退出。步5 擴展N，選取一個未在CLOSED表中出現的子節(jié)點N1放入CLOSED表中，令N=N1，轉步3?？苫厮莸木€式搜索步1 把初始節(jié)點S0放入CLOSED表中；步2 令N= S0 ；步3 若N是目標節(jié)點，則搜索成功，結束;步4 若N不可擴展，則移出CLOSED表的末端節(jié)點Ne ，若Ne = S0 ，則搜索失敗，退出。否則，以CLOSED表新的末端節(jié)點Ne作為N,即令N= Ne ，轉步4步5

60、 擴展N，選取一個未在CLOSED表中出現的子節(jié)點N1放入CLOSED表中，令N=N1，轉步3。第67頁，共187頁，2022年，5月20日，10點57分，星期日窮舉式搜索廣度優(yōu)先搜索：優(yōu)先在同一級節(jié)點中考察，只有當同一級節(jié)點擴展完以后，才擴展下一級節(jié)點。廣度優(yōu)先搜索算法：步1 把初始節(jié)點S0放入OPEN表中；步2 若OPEN表為空，則搜索失敗，退出；步3 取OPEN表中前面第一個節(jié)點N放入CLOSED表中；步4 若目標節(jié)點Sg =N，則搜索成功，結束;步5 若N不可擴展，則轉步2。步6 擴展N，將其所有子節(jié)點配上指向N的指針依次放入OPEN表的尾部，轉步2。 (OPEN表為一個隊列)例、解八