人工智能技術(shù)導(dǎo)論

人工智能技術(shù)導(dǎo)論第1頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月參考書(shū)《人工智能》馬少平、朱小燕編著，清華大學(xué)出版社《人工智能及其應(yīng)用》蔡自興、徐光祐編著，清華大學(xué)出版社

ArtificialIntelligenceANewSynthesis(人工智能)NilsJ.Nilsson第2頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月第一章人工智能概述人工智能的概念人工智能的研究途經(jīng)與方法人工智能的分工領(lǐng)域人工智能的基本技術(shù)人工智能的發(fā)展概括第3頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月什么是人工智能人工智能(ArtificialIntelligence)是指由計(jì)算機(jī)實(shí)現(xiàn)的人造智能。作為一門學(xué)科，人工智能可定義為：人工智能是一門研究如何構(gòu)造智能機(jī)器（智能計(jì)算機(jī)）或智能系統(tǒng)，使它能模擬、延伸、擴(kuò)展人類智能的學(xué)科人工智能是一門交叉邊緣學(xué)科，與人工智能有關(guān)的學(xué)科有：計(jì)算機(jī)科學(xué)、數(shù)學(xué)、語(yǔ)言學(xué)、神經(jīng)生理學(xué)、神經(jīng)心理學(xué)、腦科學(xué)、認(rèn)知科學(xué)、邏輯學(xué)、控制論等第4頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月什么是人的智能智能是人腦的屬性和產(chǎn)物。智能具有的主要特征：A、具有感知能力。通過(guò)視覺(jué)、聽(tīng)覺(jué)、觸覺(jué)、味覺(jué)和嗅覺(jué)感知外部世界。B、具有記憶與思維能力。記憶能存儲(chǔ)由感知器官感知到的外部信息以及由思維所產(chǎn)生的知識(shí)。思維用于對(duì)記憶的信息進(jìn)行處理。思維可分為邏輯思維和形象思維。C、具有學(xué)習(xí)能力及自適應(yīng)能力。D、具有行為能力。發(fā)現(xiàn)規(guī)律應(yīng)用規(guī)律分析問(wèn)題解決問(wèn)題圖靈測(cè)試中文屋子問(wèn)題（約翰·希爾勒）第5頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月為什么要研究人工智能現(xiàn)有計(jì)算機(jī)系統(tǒng)的局限性。智能低下、缺乏自學(xué)習(xí)、自適應(yīng)、自優(yōu)化能力。人類智能的局限性。學(xué)習(xí)能力因人而異、學(xué)習(xí)速度慢、效率低。信息化社會(huì)的迫切要求。第6頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的目標(biāo)近期目標(biāo)：使現(xiàn)有的電子數(shù)字計(jì)算機(jī)能模擬人類的部分智能行為。遠(yuǎn)期目標(biāo)：制造智能計(jì)算機(jī)，使計(jì)算機(jī)具有看、聽(tīng)、說(shuō)等感知和交互能力、具有聯(lián)想、推理、理解、學(xué)習(xí)等高級(jí)思維能力，還要有分析問(wèn)題、解決問(wèn)題和發(fā)明創(chuàng)造的能力。深藍(lán)（32CPU，200萬(wàn)次/秒，200萬(wàn)個(gè)棋局）第7頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的表現(xiàn)形式智能軟件智能設(shè)備智能網(wǎng)絡(luò)智能計(jì)算機(jī)智能機(jī)器人智能體(Agent)(艾真體)第8頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的研究途徑與方法結(jié)構(gòu)模擬（神經(jīng)計(jì)算、生理學(xué)派、連接主義）模擬人腦的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)實(shí)現(xiàn)智能。主要特征：1、通過(guò)神經(jīng)元之間的并行協(xié)同作用實(shí)現(xiàn)信息處理，具有并行性、動(dòng)態(tài)性、全局性。2、通過(guò)神經(jīng)元間分布式的物理聯(lián)接存儲(chǔ)信息。聯(lián)想記憶、容錯(cuò)性。3、通過(guò)神經(jīng)元間連接強(qiáng)度的動(dòng)態(tài)調(diào)整實(shí)現(xiàn)自學(xué)習(xí)和自適應(yīng)功能。4、善于模擬人類的形象思維過(guò)程。第9頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的研究途徑與方法功能模擬（符號(hào)主義、心理學(xué)派、邏輯學(xué)派）以人腦的心理模型為基礎(chǔ)，將問(wèn)題或知識(shí)表示成某種邏輯網(wǎng)絡(luò)，采用符號(hào)推演的方法，實(shí)現(xiàn)搜索、推理和學(xué)習(xí)等功能。主要特征：1、立足于邏輯運(yùn)算和符號(hào)操作，適合于模擬人的邏輯思維過(guò)程。2、知識(shí)用顯式的符號(hào)表示，容易表達(dá)人的心理模型。3、現(xiàn)有的數(shù)字計(jì)算機(jī)可以方便地實(shí)現(xiàn)高速的符號(hào)處理。4、能與傳統(tǒng)的符號(hào)數(shù)據(jù)庫(kù)進(jìn)行鏈接，易于模塊化。5、以知識(shí)為基礎(chǔ)。第10頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的研究途徑與方法行為模擬（行為主義、進(jìn)化主義、控制論學(xué)派）基于感知-行為模型的研究途徑和方法。模擬人在控制過(guò)程中的智能活動(dòng)和行為特征：自尋優(yōu)、自適應(yīng)、自組織、自學(xué)習(xí)。強(qiáng)調(diào)智能系統(tǒng)與環(huán)境的交互，認(rèn)為智能取決于感知和行動(dòng),智能行為可以不要知識(shí)。智能只有放在環(huán)境中才是真正的智能，智能的高低體現(xiàn)在對(duì)環(huán)境的適應(yīng)性上Brooks，機(jī)器蟲(chóng)第11頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的分支領(lǐng)域基于腦功能模擬的領(lǐng)域劃分1、機(jī)器感知（信息輸入）。使計(jì)算機(jī)具有類似于人的感知能力，能通過(guò)“感知”直接從外界獲取信息，是對(duì)人的感知的模擬及延伸。機(jī)器視覺(jué)、機(jī)器聽(tīng)覺(jué)。相關(guān)學(xué)科：模式識(shí)別（語(yǔ)音識(shí)別、圖像識(shí)別）。信息->電信號(hào)序列->預(yù)處理->提取特征->模式匹配2、機(jī)器聯(lián)想。基于內(nèi)容的聯(lián)想，與具體存儲(chǔ)位置無(wú)關(guān)。聯(lián)想存儲(chǔ)技術(shù)。3、機(jī)器推理。又稱為計(jì)算機(jī)推理、自動(dòng)推理，是人工智能的核心課題之一。推理：從一些已知判斷（前提）推出一個(gè)新判斷（結(jié)論）的思維過(guò)程。演繹推理、歸納推理、類比推理確定性推理、不確定性推理基于概率邏輯的或然推理(隨機(jī)性)、基于模糊邏輯的似然推理(模糊性)串行推理、并行推理第12頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的分支領(lǐng)域4、機(jī)器學(xué)習(xí)。使機(jī)器自己獲取知識(shí)。對(duì)人類已有知識(shí)的獲取、對(duì)客觀規(guī)律的發(fā)現(xiàn)、對(duì)自身行為的修正。機(jī)器學(xué)習(xí)分為：機(jī)械學(xué)習(xí)、指導(dǎo)學(xué)習(xí)、解釋學(xué)習(xí)、類比學(xué)習(xí)、示例學(xué)習(xí)、發(fā)現(xiàn)學(xué)習(xí)等。這些屬于符號(hào)學(xué)習(xí)。另外還有神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)。5、機(jī)器理解。圖形理解（物景分析）、自然語(yǔ)言理解。理解是感知的延伸和深化。6、機(jī)器行為（機(jī)器人行動(dòng)規(guī)劃）。智能機(jī)器人的核心技術(shù)，反映了機(jī)器人的智能水平解決問(wèn)題依靠規(guī)劃功能確定行動(dòng)步驟和動(dòng)作序列任務(wù)：在一個(gè)特定的工作區(qū)域中自動(dòng)生成從初始狀態(tài)到目標(biāo)狀態(tài)的動(dòng)作序列、運(yùn)動(dòng)路徑和軌跡的控制程序第13頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的分支領(lǐng)域基于研究途徑和實(shí)現(xiàn)技術(shù)的領(lǐng)域劃分1、符號(hào)智能以符號(hào)知識(shí)為基礎(chǔ)，通過(guò)符號(hào)推理進(jìn)行問(wèn)題求解知識(shí)工程(知識(shí)獲取、知識(shí)表示、知識(shí)管理、知識(shí)運(yùn)用、知識(shí)庫(kù)系統(tǒng))、符號(hào)處理2、計(jì)算智能以數(shù)據(jù)為基礎(chǔ)，通過(guò)數(shù)值計(jì)算進(jìn)行問(wèn)題求解人工神經(jīng)網(wǎng)絡(luò)、進(jìn)化計(jì)算(遺傳算法、遺傳程序設(shè)計(jì)、進(jìn)化規(guī)劃、進(jìn)化策略)、模糊技術(shù)、人工生命第14頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的分支領(lǐng)域基于應(yīng)用領(lǐng)域的領(lǐng)域劃分1、難題求解難題的概念路徑規(guī)劃、組合優(yōu)化、天氣預(yù)報(bào)、股市分析、市場(chǎng)預(yù)測(cè)、機(jī)器博弈NP(NondeterministicPolynomial)和NPC(NondeterministicPolynomialComplete)問(wèn)題難題求解技術(shù)能促進(jìn)人工智能其他領(lǐng)域的發(fā)展2、自動(dòng)定理證明自然演繹法、判定法、定例證明器、計(jì)算機(jī)輔助證明四色問(wèn)題(1976.6,K.Appeel)。3、自動(dòng)程序設(shè)計(jì)超級(jí)編譯系統(tǒng)自動(dòng)程序綜合和自動(dòng)程序驗(yàn)證。第15頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的分支領(lǐng)域4、自動(dòng)翻譯。機(jī)器翻譯。自然語(yǔ)言理解。一邊站著一個(gè)人他想起來(lái)了5、智能控制1965，KS.FU(傅京孫)提出將啟發(fā)式推理規(guī)則用于學(xué)習(xí)控制系統(tǒng)6、智能管理。人工智能與管理科學(xué)、系統(tǒng)工程和計(jì)算機(jī)技術(shù)的結(jié)合。7、智能決策。人工智能應(yīng)用于決策支持系統(tǒng)。8、智能通訊。在通訊的各個(gè)環(huán)節(jié)和層次上實(shí)現(xiàn)智能化。如網(wǎng)控、轉(zhuǎn)接、信息轉(zhuǎn)換等。使通訊網(wǎng)隨時(shí)運(yùn)行于最佳狀態(tài)。9、智能仿真。仿真是在三種類型知識(shí)-描述性知識(shí)、目的性知識(shí)和處理知識(shí)的基礎(chǔ)上產(chǎn)生另一種形式的知識(shí)-結(jié)論性知識(shí)。10、智能CAD。人工智能應(yīng)用于CAD的設(shè)計(jì)自動(dòng)化、智能交互、智能圖形學(xué)、自動(dòng)數(shù)據(jù)采集方面。11、智能CAI。人工智能應(yīng)用于CAI：自動(dòng)生成各種問(wèn)題與練習(xí)、自動(dòng)選擇與調(diào)整教學(xué)內(nèi)容和進(jìn)度、自動(dòng)生成答案、自然語(yǔ)言理解能力、不斷改善教學(xué)策略。第16頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的分支領(lǐng)域基于應(yīng)用系統(tǒng)的領(lǐng)域劃分1、專家系統(tǒng)?；谌祟悓＜抑R(shí)的程序系統(tǒng)。能模擬專家的思維方式。2、知識(shí)庫(kù)系統(tǒng)。3、智能數(shù)據(jù)庫(kù)系統(tǒng)。傳統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)+人工智能。4、智能機(jī)器人系統(tǒng)。具備感知、思維、人-機(jī)通訊和運(yùn)動(dòng)能力。第17頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的分支領(lǐng)域基于計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的領(lǐng)域劃分1、智能操作系統(tǒng)。并行性、分布性和智能性。2、智能多媒體系統(tǒng)。人工智能與多媒體技術(shù)的有機(jī)結(jié)合。3、智能計(jì)算機(jī)系統(tǒng)。4、智能網(wǎng)絡(luò)系統(tǒng)。模糊和神經(jīng)網(wǎng)絡(luò)技術(shù)應(yīng)用于網(wǎng)絡(luò)的業(yè)務(wù)量預(yù)測(cè)和控制、資源動(dòng)態(tài)分配、動(dòng)態(tài)路由選擇等方面。第18頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的分支領(lǐng)域基于實(shí)現(xiàn)工具與環(huán)境的領(lǐng)域劃分1、智能軟件工具。人工智能程序設(shè)計(jì)語(yǔ)言，如表處理語(yǔ)言LISP、邏輯程序設(shè)計(jì)語(yǔ)言PROLOG、面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言Smalltalk等。知識(shí)表示語(yǔ)言FRL、OPS5。專家系統(tǒng)工具、知識(shí)工程工具等。2、智能硬件平臺(tái)。直接支持智能系統(tǒng)開(kāi)發(fā)和運(yùn)行的機(jī)器硬件。第19頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的分支領(lǐng)域基于體系結(jié)構(gòu)的領(lǐng)域劃分集中式人工智能（個(gè)體智能）分布式人工智能（群體智能）個(gè)體智能的組合或疊加DPS（分布式問(wèn)題求解），自頂向下MAS（多智能體系統(tǒng)），自底向上第20頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的基本技術(shù)推理技術(shù)。推理是智能的核心。推理以邏輯為基礎(chǔ)?；谥^詞邏輯的自然演繹推理和歸結(jié)反演推理?；诜菢?biāo)準(zhǔn)邏輯如多值邏輯、模態(tài)邏輯、時(shí)態(tài)邏輯、模糊邏輯、非單調(diào)邏輯的推理。搜索技術(shù)。人工智能的基本技術(shù)。許多智能活動(dòng)的過(guò)程，都可以看作或抽象為一個(gè)“問(wèn)題求解”過(guò)程?！皢?wèn)題求解”就是在問(wèn)題空間中進(jìn)行搜索的過(guò)程。盲目搜索、啟發(fā)式搜索。神經(jīng)網(wǎng)絡(luò)搜索。知識(shí)表示與知識(shí)庫(kù)技術(shù)。知識(shí)表示是指知識(shí)在計(jì)算機(jī)中的表示方式。知識(shí)表示要符合知識(shí)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，并適合于計(jì)算機(jī)存儲(chǔ)和處理。知識(shí)庫(kù)由知識(shí)構(gòu)成。知識(shí)的組織、管理、維護(hù)和優(yōu)化。第21頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的基本技術(shù)歸納技術(shù)。機(jī)器自動(dòng)提取概念、獲取知識(shí)、發(fā)現(xiàn)規(guī)律的技術(shù)。歸納技術(shù)與知識(shí)獲取和機(jī)器學(xué)習(xí)密切相關(guān)?；诜?hào)處理的歸納和基于神經(jīng)網(wǎng)絡(luò)的歸納。數(shù)據(jù)庫(kù)知識(shí)發(fā)現(xiàn)（KDD,KnowledgeDiscoveryinDatabase)和數(shù)據(jù)挖掘(DataMining)技術(shù)。聯(lián)想技術(shù)。聯(lián)想記憶，聯(lián)想存儲(chǔ)。第22頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的發(fā)展概況孕育期（1956年之前）1、公元前，Aristotle提出形式邏輯的一些主要定律，三段論至今仍是演繹推理的基本依據(jù)。2、培根（1561-1626）曾系統(tǒng)地提出了歸納法。提出“知識(shí)就是力量”3、德國(guó)數(shù)學(xué)家Leibniz（1646-1716）提出了萬(wàn)能符號(hào)和推理計(jì)算的思想，為數(shù)理邏輯的產(chǎn)生和發(fā)展奠定了基礎(chǔ)。4、英國(guó)邏輯學(xué)家Boole（1815-1864）創(chuàng)立了布爾代數(shù)，在《思維法則》一書(shū)中首次用符號(hào)語(yǔ)言描述了思維活動(dòng)的基本推理法則。5、英國(guó)數(shù)學(xué)家Turing于1936年提出理想計(jì)算機(jī)的數(shù)學(xué)模型，即圖靈機(jī)。Turing測(cè)試。6、1943年，McCulloch和Pitts提出M-P神經(jīng)元模型。7、1946年，世界上第一臺(tái)電子計(jì)算機(jī)誕生。第23頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的發(fā)展概況人工智能學(xué)科的產(chǎn)生（1956年）

1956年夏季，McCarthy,Minsky,Lochester,Shannon,More,Samuel,Selfridge,Solomonff,Newell,Simon等十人在Dartmouth大學(xué)召開(kāi)歷時(shí)兩個(gè)多月的研討會(huì)，討論機(jī)器智能的有關(guān)問(wèn)題。由McCarthy提出“人工智能”一詞，人工智能從此成為一門學(xué)科。第24頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的發(fā)展概況符號(hào)主義AI發(fā)展概況1、形成（1956-1965）（人工智能的推理期。結(jié)構(gòu)良好問(wèn)題。搜索策略和算法）（1）、1956年，Samuel的跳棋程序。1959,1962（2）、定理證明方面，1956年Newell等的邏輯理論機(jī)（LT）程序；1958年，王浩的工作；1965年，Robinson提出的消解原理。（3）、模式識(shí)別方面，1959年Selfridge的模式識(shí)別程序；1965年Roberts編制了可以分辨積木構(gòu)造的程序。（4）、問(wèn)題求解方面。1960年，Newell的通用問(wèn)題求解(GPS)程序。（5）、1960年，McCarthy研制成功LISP語(yǔ)言。第25頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的發(fā)展概況人工智能的知識(shí)期（1965-70年代末）（1）、專家系統(tǒng)方面。1965年，F(xiàn)eigenbaum的專家系統(tǒng)DENDRAL，1968年投入使用。DENDRAL對(duì)知識(shí)表示、存儲(chǔ)、獲取和推理的技術(shù)為以后的專家系統(tǒng)的建造樹(shù)立了榜樣，對(duì)AI的發(fā)展產(chǎn)生了深刻的影響。之后著名的專家系統(tǒng)有：醫(yī)學(xué)專家系統(tǒng)MYCIN，地質(zhì)勘探專家系統(tǒng)PROSPECTOR，計(jì)算機(jī)配置專家系統(tǒng)R1等。（2）、1969年，國(guó)際人工智能聯(lián)合會(huì)議(IJCAI)召開(kāi)。1970年，“ArtificialIntelligence”雜志創(chuàng)刊。（3）、1977年，F(xiàn)eigenbaum在第五屆國(guó)際人工智能會(huì)議上，提出了“知識(shí)工程”的概念。發(fā)展期（20世紀(jì)80年代后）專家系統(tǒng)與知識(shí)工程在理論、技術(shù)和應(yīng)用方面都有長(zhǎng)足的進(jìn)步和發(fā)展。出現(xiàn)了多專家系統(tǒng)、大型專家系統(tǒng)、微專家系統(tǒng)、分布式專家系統(tǒng)等。智能管理信息系統(tǒng)、智能決策支持系統(tǒng)、智能控制系統(tǒng)等。第26頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月人工智能的發(fā)展概況連接主義途徑發(fā)展概況1、1943年，神經(jīng)生理學(xué)家McCulloch和Pitts提出M-P神經(jīng)元模型。1944年，Hebb提出Hebb學(xué)習(xí)規(guī)則。2、1957年，Rosenblatt提出Perceptron單層神經(jīng)網(wǎng)絡(luò)模型。1962年，Widrow提出自適應(yīng)線性元件Adaline。應(yīng)用于天氣預(yù)報(bào)、電子線路板分析、人工視覺(jué)等。3、1969年，Minsky和Papert發(fā)表《Perceptrons》，證明了單層人工神經(jīng)網(wǎng)絡(luò)無(wú)法實(shí)現(xiàn)一個(gè)簡(jiǎn)單的異或邏輯函數(shù)XOR，把神經(jīng)網(wǎng)絡(luò)的研究帶入低谷。4、在低谷期，KohonenGrossberg和Anderson等人仍堅(jiān)持研究，取得了一些有價(jià)值的結(jié)果。5、20世紀(jì)80年代中期以后，神經(jīng)網(wǎng)絡(luò)研究復(fù)蘇，掀起了新一輪研究熱潮。1986年，Hopfield網(wǎng)絡(luò)成功應(yīng)用于TSP問(wèn)題。1986年Rumelhart提出BP算法，解決了多層人工神經(jīng)元網(wǎng)絡(luò)的學(xué)習(xí)問(wèn)題。1987年6月，第一屆國(guó)際神經(jīng)網(wǎng)絡(luò)大會(huì)（IJCNN）召開(kāi)，盛況空前。目前，NN與專家系統(tǒng)、知識(shí)工程成為AI的兩個(gè)主流方向。NN在智能控制、信號(hào)處理、最優(yōu)化、知識(shí)工程等領(lǐng)域都有成功應(yīng)用。第27頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月當(dāng)前發(fā)展趨勢(shì)1、傳統(tǒng)以符號(hào)處理為中心的人工智能與神經(jīng)網(wǎng)絡(luò)的結(jié)合。神經(jīng)網(wǎng)絡(luò)：識(shí)別聯(lián)想學(xué)習(xí)適應(yīng)，負(fù)責(zé)對(duì)外界的感知和交互專家系統(tǒng)：判斷推理搜索，負(fù)責(zé)高層的決策與控制2、新理論、新技術(shù)的出現(xiàn)。Fuzzy,GeneticAlgorithm,Chaos,Artificiallife,SoftComputing,ComputationalIntelligence,Roughset,DataMining,Knowledgediscoveryindatabase,Datawarehouse,SituatedAI,Agent-baseddistributedAI

等。第28頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月第二章基于謂詞邏輯的機(jī)器推理謂詞、函詞、量詞個(gè)體：研究對(duì)象中可以獨(dú)立存在的具體的或抽象的客體。個(gè)體用個(gè)體常元或個(gè)體變?cè)硎?，如x,y,z,a,b,c,…等。謂詞：描述個(gè)體性質(zhì)及個(gè)體之間相互關(guān)系的詞。如P、Q、R，…等。例、命題“2是素?cái)?shù)”中，2是個(gè)體，“是素?cái)?shù)”是謂詞。可表示為P(2).函詞（函數(shù)）：某些個(gè)體是其它個(gè)體的函數(shù)，描述這種關(guān)系的詞稱為函詞。例、命題“小李的父親是醫(yī)生”可表示為Doctor(father(Li)).量詞：存在量詞“”；全稱量詞“”。例、“任何實(shí)數(shù)的平方都非負(fù)”可表示為x(R(x)N(s(x))?！按嬖谂妓?cái)?shù)”可表示為x(E(x)P(x))。第29頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月一些命題的表示凡是人都有名字x(M(x)N(x))不存在最大的整數(shù)x(G(x)y(G(y)D(x,y))

x(G(x)y(G(y)D(y,x))對(duì)所有的自然數(shù)，均有X+Y>Xxy(N(x)N(y)S(x,y,x))某些人對(duì)某些食物過(guò)敏xy(M(x)F(y)G(x,y))第30頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月謂詞公式項(xiàng)的定義：1、個(gè)體常元和個(gè)體變?cè)琼?xiàng)；2、設(shè)f是n元函詞符號(hào)，t1,t2,…,tn是項(xiàng)，則f(t1,t2,…,tn)是項(xiàng)。3、只有有限次使用1，2得到的符號(hào)串才是項(xiàng)。原子公式：P是n元謂詞，t1,t2,…,(tn是項(xiàng)，則P(t1,t2,…,tn)稱為原子謂詞公式(原子公式)(原子)。謂詞公式：1、原子公式是謂詞公式；2、若A、B是謂詞公式，則

A，AB，AB，AB，AB，xA，xA也是謂詞公式；3、只有有限次地應(yīng)用步驟1，2形成的符號(hào)串才是謂詞公式。轄域：xA和xA中，x稱為量詞的指導(dǎo)(作用)變?cè)?，A稱為x的轄域。轄域中與該量詞的指導(dǎo)變?cè)嗤淖冊(cè)Q為約束變?cè)?，其它變?cè)?如果存在的話)稱為自由變?cè)?。例、xP(x)；x(H(x)G(x,y))；xA(x)B(x)約束變?cè)母拿?/p>

：兩個(gè)規(guī)則第31頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月部分邏輯蘊(yùn)含式（p59-p60)析取三段論：

A(AB)B假言推理（分離規(guī)則）：A(AB)B拒取式：B(AB)A假言三段論：(AB)(BC)AC二難推論:(AB)

(AC)(BC)C全稱指定規(guī)則US(UniversalSpecification)：xA(x)A(y)，y是個(gè)體域中任一確定元素。存在指定規(guī)則ES(ExistentialSpecification)：xA(x)A(c)，c是個(gè)體域中某一確定元素。全稱推廣規(guī)則UG(UniversalGeneralization)：A(y)xA(x)，y是個(gè)體域中任一確定元素。存在推廣規(guī)則EG(UniversalGeneralization)：A(c)xA(x)，c是個(gè)體域中某一確定元素。第32頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月自然演繹推理以謂詞公式的等價(jià)式及推理定律為基礎(chǔ)進(jìn)行的推理稱為自然演繹推理。例見(jiàn)教材p61。推理過(guò)程是一個(gè)符號(hào)變換過(guò)程，類似于人們使用自然語(yǔ)言進(jìn)行推理的思維過(guò)程。推理與謂詞公式的含義無(wú)關(guān)，是一種形式推理。自然演繹推理在機(jī)器上實(shí)施比較困難推理規(guī)則太多應(yīng)用規(guī)則需要很強(qiáng)的模式識(shí)別能力中間結(jié)論的指數(shù)遞增第33頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月子句集定義1

原子謂詞公式及其否定稱為文字；若干個(gè)文字的一個(gè)析取式稱為一個(gè)子句；由r個(gè)文字組成的子句稱為r-文字子句，1-文字子句稱為單元子句，不含任何文字的子句稱為空子句，記為□或NIL。定義2

對(duì)一個(gè)謂詞公式G，通過(guò)一定的步驟得到的子句集合S稱為G的子句集。第34頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月子句集（1）、利用等價(jià)式ABAB和AB(AB)(BA)消去聯(lián)結(jié)詞“”和“”。（2）、縮小否定聯(lián)結(jié)詞的作用范圍，使其僅作用于原子公式?？衫孟铝械葍r(jià)式：

AA；(AB)

AB，(AB)AB；xA(x)xA(x)，xA(x)xA(x)（3）、重新命名變?cè)共煌吭~約束的變?cè)胁煌拿?。?）、消去存在量詞。若存在量詞不在全稱量詞的轄域內(nèi)，則用一個(gè)常量符號(hào)替換該存在量詞轄域中的相應(yīng)約束變?cè)?。這樣的常量稱為Skolem常量；若該存在量詞在一個(gè)或多個(gè)全稱量詞的轄域內(nèi)，則用這些全稱量詞指導(dǎo)變?cè)囊粋€(gè)函數(shù)替換該存在量詞約束的變?cè)?。這樣的函數(shù)稱為Skolem函數(shù)。例如x1x2???xnyP(x1,x2,…,xn,y)中y可用Skolem函數(shù)f(x1,x2,…,xn)替換為x1x2???xnP(x1,x2,…,xn,f(x1,x2,…,xn))。第35頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月子句集（5）、把全稱量詞全部移到公式的左邊。（6）、把全稱量詞后面的公式利用等價(jià)關(guān)系A(chǔ)(BC)

(AB)(AC)化為子句的合取式，得到的公式稱為Skolem標(biāo)準(zhǔn)形。Skolem標(biāo)準(zhǔn)形的一般形式為x1x2???xnM，其中M是子句的合取式。（7）、消去全稱量詞。（8）、對(duì)變?cè)?，使子句間無(wú)同名變?cè)＃?）、消去合取詞，以子句為元素組成的集合稱為謂詞公式的子句集。例：把如下謂詞公式化為子句集。x{yP(x,y)y[Q(x,y)R(x,y)]}第36頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月子句集求解過(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{yP(x,y)y[Q(x,y)

R(x,y)]}3)x{yP(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不可滿足。子句集S是不可滿足的是指其全部子句的合取式是不可滿足的。第37頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月命題邏輯中的歸結(jié)原理要證明在前提P下結(jié)論Q成立，即是證明PQ永真，這只須證明PQ不可滿足。根據(jù)定理1，只須證明PQ的子句集不可滿足。由于子句之間是合取關(guān)系，只要有一個(gè)子句不滿足，則整個(gè)子句集不可滿足。由于空子句是不可滿足的，所以如果子句集中包含空子句，則該子句集是不可滿足的。若子句集中不包含空子句，則可通過(guò)Robinson提出的歸結(jié)原理對(duì)子句集進(jìn)行歸結(jié)，歸結(jié)過(guò)程保證子句集的不可滿足性不變。一旦歸結(jié)出空子句，則證明結(jié)束。因此，歸結(jié)原理把定理的證明化為子句集中歸結(jié)出空子句的過(guò)程。第38頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月命題邏輯中的歸結(jié)原理定義４、設(shè)L是一個(gè)文字，則稱L與L為互補(bǔ)文字。定義５、設(shè)C1、C2是命題邏輯中的兩個(gè)子句，C1

中有文字L1

，C２中有文字L２，且L1與L２互補(bǔ)，從C1，C２中分別刪除L1

，L２，再將剩余部分析取起來(lái)，構(gòu)成的新子句C1２稱為C1與C2的歸結(jié)式（消解式），C1，C2稱為C1２的親本子句。C1=PQR,C2=QS,C1２

=PRS定理２、歸結(jié)式C1２是其親本子句C1與C2的邏輯結(jié)論。推論、設(shè)C1，C2是子句集S的兩個(gè)子句，C1２是它們的歸結(jié)式，則（１）若用C1２代替C1和C2后得到新子句集S1，則由S1的不可滿足性可推出原子句集S的不可滿足性。即 S1不可滿足S不可滿足２）若把C1２加入到S中，得到新子句集S２，則S２與S在不可滿足意義上是等價(jià)的。即 S2不可滿足

S不可滿足第39頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月命題邏輯中的歸結(jié)原理例、用歸結(jié)原理證明R是P,(PQ)R，(SU)Q，U的邏輯結(jié)果。求子句集P,(PQ)R,(SU)Q,U,RP,(PQ)R,(SU)Q,U,RP,PQR,SQ,UQ,U,R(子句集)歸結(jié)演繹PQRRPQPQPQQUQUUU□第40頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月替換與合一問(wèn)題的提出謂詞邏輯和命題邏輯中使用歸結(jié)原理的差別C1=P(x)Q(x),C2=P(a)R(y)C1’=P(a)Q(a),C2’=P(a)R(y)定義６一個(gè)替換(Substitution)是形如{t1/x1,t2/x2,…,tn/

xn}的有限集合，其中t1,t2,…,tn是項(xiàng)(替換的分子)，x1,x2,…,xn是互不相同的個(gè)體變?cè)?替換的分母)。ti/

xi表示用ti代換xi。ti與xi不同，xi也不能循環(huán)出現(xiàn)在tj中(j=1,2,…,n)?；鎿Q(t1,t2,…,tn均不含變?cè)?、空替換ε例：｛a/x,g(c)/y,f(g(b))/z}，{g(y)/x,f(x)/y}第41頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月替換與合一定義7設(shè)＝{t1/

x1,t2/

x2,…,tn/

xn}是一個(gè)替換，E是一個(gè)表達(dá)式，把E中出現(xiàn)的所有個(gè)體變?cè)獂i都用ti替換，記為E，得到的結(jié)果稱為E在下的替換實(shí)例(Instance)。Eg：E=P(x,y,g(z)),＝{a

/

x,f(b)

/y

,c

/z

}，E=P(a,f(b),g(c))定義８設(shè)＝{t1/

x1,t2/

x2,…,tn/

xn}，＝{u1/

y1,u2/

y2,…,um/

ym}是兩個(gè)替換，則將集合{t1

/

x1,t2

/

x2,…,tn

/

xn，u1/

y1,u2/

y2,…,um/

ym}中符合下列條件的兩種情形刪除：ti

/

xi，當(dāng)ti

＝

xi

ui/

yi，當(dāng)yi

{

x1,

x2,…,

xn}＊

得到的集合仍是一個(gè)替換，稱為與的復(fù)合或乘積，記為·例:設(shè)

={f(y)/x,z/y}={a/x,b/y,y/z}·={f(b)/x,y/y,a/x,b/y,y/z}={f(b)/x,y/z}第42頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月替換與合一定義９設(shè)S={

F1,

F2,…,

Fn}是一個(gè)原子謂詞公式集，若存在一個(gè)替換，使得F1＝

F2＝…＝

Fn，則稱為S的一個(gè)合一(Unifier)，并稱S為可合一的。一個(gè)公式集的合一一般不唯一定義10設(shè)是公式集S的一個(gè)合一，如果對(duì)S的任何一個(gè)合一，都存在一個(gè)替換，使得＝·，則稱為S的一個(gè)最一般合一(MostGeneralUnifier)，簡(jiǎn)稱MGU

設(shè)S={P(u,y,g(y)),P(x,f(u),z)},有={u/x,f(u)/y,g(f(u))/z}

對(duì)其它某個(gè)合一,如={a/x,f(a)/y,g(f(a))/z,a/u}，可找到替換={a/u}，使得＝·第43頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月替換與合一定義11設(shè)S是一個(gè)非空的具有相同謂詞名的原子公式集，從S中各公式的左邊第一個(gè)項(xiàng)開(kāi)始，同時(shí)向右比較，每一組不都相同的項(xiàng)的差異部分組成的集合稱為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頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月替換與合一設(shè)S為一非空有限具有相同謂詞名的原子謂詞公式集，求S的MGU的算法：(1)令k=0,Sk=S,k=（表示空替換）(2)若Sk只含有一個(gè)謂詞公式，則算法停止，k就是要求的最一般合一(3)求Sk的差異集Dk(4)若Dk中存在元素xk和tk，其中xk是變?cè)?，tk是項(xiàng)且xk不在tk中出現(xiàn)，則置Sk+1=Sk{tk/xk}，k+1=k·{tk/xk}，k=k+1，然后轉(zhuǎn)步(2)(5)算法停止，S的最一般合一不存在第45頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月替換與合一求S={P(a,x,f(g(y))),P(z,h(z,u),f(u))}的MGUk=0S0=S,0=,D0={a,z}1=0·{a/z}={a/z}S1=S0{a/z}={P(a,x,f(g(y))),P(a,h(a,u),f(u))}k=1D1={x,h(a,u)}2=1·{h(a,u)/x}={a/z}·{h(a,u)/x}={a/z,h(a,u)/x}S2=S1{h(a,u)/x}={P(a,h(a,u),f(g(y))),P(a,h(a,u),f(u))}第46頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月替換與合一S2=S1{h(a,u)/x}={P(a,h(a,u),f(g(y))),P(a,h(a,u),f(u))}k=2D2={g(y),u}3=2·{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=3S3為單元素集，所以3為所求的S的MGU說(shuō)明：MGU可能是不唯一的，如Dk={xk,yk}時(shí)第47頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月謂詞邏輯中的歸結(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é)式(二元消解式)。C1和C2稱為C12的親本子句，L1，L2稱為消解文字。例：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é)原理：C1C2(C1-{L1})(C2-{L2})第48頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月謂詞邏輯中的歸結(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ì)PQ與P

Q不能同時(shí)消去第49頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月歸結(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中。如此反復(fù)進(jìn)行，直到出現(xiàn)空子句，就證明了Q為真。定理5（歸結(jié)原理的完備性）、如果子句集S是不可滿足的，則必存在一個(gè)由S推出空子句的歸結(jié)序列。第50頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月歸結(jié)反演舉例例：自然數(shù)都是大于零的整數(shù)；所有整數(shù)不是偶數(shù)就是奇數(shù)；偶數(shù)除以2是整數(shù)。求證：所有自然數(shù)不是奇數(shù)就是其一半為整數(shù)的數(shù)。證明：前提：F1

：x(N(x)GZ(x)I(x))N(x)：x是自然數(shù)

F2

：x(I(x)E(x)O(x))GZ(x)：x>0I(x)：x是整數(shù)

F3

：x(E(x)I(h(x)))E(x)：x是偶數(shù)O(x)：x是奇數(shù)結(jié)論：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))歸結(jié)：（8）I(c)((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頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月應(yīng)用歸結(jié)原理求解應(yīng)用歸結(jié)原理求取問(wèn)題答案的步驟把已知前提用謂詞公式表示出來(lái)，并化為子句集S把待求解問(wèn)題也用謂詞公式表示出來(lái)，然后把它的否定與謂詞ANS構(gòu)成析取式。ANS的變?cè)獞?yīng)與問(wèn)題的變?cè)耆恢掳汛宋鋈∈交癁樽泳浼?，并把該子句集并入S中得到子句集S‘對(duì)S‘應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)若得到歸結(jié)式ANS，則答案就在ANS中第52頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月應(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ō)謊者”。問(wèn)：誰(shuí)是老實(shí)人？解、設(shè)T(x)表示x說(shuō)真話。如果A說(shuō)的是真話，則有：

T(A)T(B)T(C)如果A說(shuō)的是假話，則有：T(A)T(B)T(C)。同理，對(duì)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)第53頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月應(yīng)用歸結(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)并入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是老實(shí)人。無(wú)論如何歸結(jié)，推不出ANS(A),ANS(B)第54頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月歸結(jié)策略歸結(jié)反演的一般過(guò)程。步1將子句集S置入CLAUSES表；步2若空子句NIL在CLAUSES中，則歸結(jié)成功，結(jié)束。步3若CLAUSES表中存在可歸結(jié)的子句對(duì)，則歸結(jié)之，并將歸結(jié)式并入CLAUSES表，轉(zhuǎn)步２；步4歸結(jié)失敗，退出。窮舉算法（廣度優(yōu)先策略）第一輪：將原子句集S中的子句兩兩歸結(jié)，產(chǎn)生的歸結(jié)式集合記為S1，再將S1并入CLAUSES表；第二輪：將新的CLAUSES表，即SS1中的子句與S1中的子句兩兩歸結(jié)，產(chǎn)生的歸結(jié)式集合記為S2，再將S2并入CLAUSES；第三輪：將新的CLAUSES表即SS1S2中的子句與S2中的子句兩兩歸結(jié)，…。如此下去，直到出現(xiàn)空子句。第55頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月歸結(jié)策略例1設(shè)有如下的子句集，用窮舉算法歸結(jié)如下：S：（1）PQ

（2）PQ

（3）PQ

（4）

PQS1：（5）Q[(1),(2)]

（6）P[(1),(3)]

（7）QQ[(1),(4)]

（8）PP[(1),(4)]

（9）QQ[(2),(3)]

（10）PP[(2),(3)]

（11）P[(2),(4)]

（12）Q[(3),(4)]S2：（13）P

Q[(1),(7)]（14）P

Q[(1),(8)]第56頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月歸結(jié)策略（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）PQ[(3),(7)]（27）PQ[(3),(8)]（28）PQ[(3),(9)]（29）PQ[(3),(10)]（30）Q[(3),(11)]（31）

P[(4),(5)]（32）Q[(4),(6)]（33）PQ[(4),(7)]（34）PQ[(4),(8)]（35）PQ[(4),(9)]（36）PQ[(4),(10)]（37）Q[(5),(7)]（38）Q[(5),(9)]（39）□[(5),(12)]第57頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月歸結(jié)策略定義：設(shè)C1，C2是兩個(gè)子句，若存在替換，使得C1C2

，則稱子句C1類含C2

。

P(x)類含P(a)Q(y)P(x)類含P(a)刪除策略。在歸結(jié)過(guò)程中可隨時(shí)刪除以下子句：（1）、含有純文字的子句。純文字是指在子句中無(wú)補(bǔ)文字的文字。{P(x)Q(x,y)R(x)，

P(a)Q(u,v)，

Q(b,z)，

P(w)}解釋：永遠(yuǎn)無(wú)法得到空子句（2）、含有永真式的子句；解釋：對(duì)子句集的不可滿足性不起作用（3）、被子句集中別的子句類含的子句。解釋：C=P(x)替換后得C=P(a)，D=P(a)Q(y)第58頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月歸結(jié)策略使用刪除策略，例1可簡(jiǎn)化為：（1）PQ（7）

P[(2),(4)]（2）PQ（8）Q[(3),(4)]（3）PQ（9）□[(5),(8)]（4）

PQ（5）Q[(1),(2)]（6）P[(1),(3)]刪除策略的特點(diǎn)：刪除策略的思想是及早刪除無(wú)用字句，以避免無(wú)效歸結(jié)，縮小搜索空間。刪除策略是完備的。一個(gè)歸結(jié)策略是完備的，是指對(duì)于不可滿足的子句集，使用該策略進(jìn)行歸結(jié)，最終必導(dǎo)出空子句。第59頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月歸結(jié)策略支持集策略支持集：目標(biāo)公式的否定的子句集支持集策略：每次歸結(jié)時(shí)，兩個(gè)親本子句中至少要有一個(gè)是目標(biāo)公式否定的子句或其后裔。支持集策略的特點(diǎn)：支持集策略實(shí)際是一種目標(biāo)制導(dǎo)的反向推理。支持集策略是完備的。線性歸結(jié)策略在歸結(jié)過(guò)程中，除第一次歸結(jié)可都用初始子句集S中的子句外，其它的各次歸結(jié)至少要有一個(gè)親本子句是前次歸結(jié)的結(jié)果。線性歸結(jié)策略的特點(diǎn)：完備、高效、與別的策略兼容。第60頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月歸結(jié)策略歸結(jié)策略的類型簡(jiǎn)化性策略思想：盡量簡(jiǎn)化子句和子句集，以減少和避免無(wú)效歸結(jié)。缺點(diǎn)：額外開(kāi)銷(eg:檢驗(yàn)、真值計(jì)算)限制性策略思想：縮小搜索范圍，提高搜索效率有序性策略思想：給子句安排一定的順序，一邊盡快推出空子句歸結(jié)反演的一般算法步1將子句集S置入CLAUSES表；步2若空子句NIL在CLAUSES中，則歸結(jié)成功，結(jié)束。步3按某種策略在CLAUSES表中尋找可歸結(jié)的子句對(duì)，若存在則歸結(jié)之，并將歸結(jié)式并入CLAUSES表，轉(zhuǎn)步２；步4歸結(jié)失敗，退出。第61頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月第四章圖搜索技術(shù)搜索：根據(jù)問(wèn)題的實(shí)際情況不斷尋找可利用的知識(shí)，從而構(gòu)造一條代價(jià)較少的推理路線，使問(wèn)題得到圓滿解決的過(guò)程。應(yīng)用：結(jié)構(gòu)不良問(wèn)題，無(wú)成熟算法；或有算法，但問(wèn)題復(fù)雜，如博弈圖：由節(jié)點(diǎn)和有向邊組成的網(wǎng)絡(luò)圖的分類：或圖(狀態(tài)圖、直接圖)與或圖第62頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月?tīng)顟B(tài)圖狀態(tài)圖的概念迷宮問(wèn)題八數(shù)碼難題/華容道問(wèn)題以上問(wèn)題的本質(zhì)：在某個(gè)有向圖中尋找目標(biāo)或路徑，該有向圖稱為狀態(tài)空間圖或狀態(tài)圖。狀態(tài)是描述問(wèn)題求解過(guò)程中任一時(shí)刻的狀況。引起狀態(tài)中某些分量發(fā)生變化，從而使問(wèn)題從一個(gè)狀態(tài)變?yōu)榱硪粋€(gè)狀態(tài)的操作、規(guī)則、變換稱為算符。問(wèn)題求解就是尋找一個(gè)從初始狀態(tài)到目標(biāo)狀態(tài)的算符序列的過(guò)程。問(wèn)題求解過(guò)程可描述為一個(gè)有向圖，其中的節(jié)點(diǎn)代表狀態(tài)，邊表示狀態(tài)轉(zhuǎn)換之間的算符。2318476512384765第63頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月?tīng)顟B(tài)圖搜索搜索樹(shù)：搜索過(guò)程中經(jīng)過(guò)的節(jié)點(diǎn)和邊按原圖的連接關(guān)系構(gòu)成一個(gè)樹(shù)型的有向圖，稱為搜索樹(shù)。搜索方式樹(shù)式搜索：記錄搜索過(guò)程中所經(jīng)過(guò)的所有節(jié)點(diǎn)和邊線式搜索：記錄當(dāng)前認(rèn)為是所找路徑上的節(jié)點(diǎn)和邊不可回溯(隨機(jī)碰撞式搜索)可回溯(窮舉式搜索)兩種方式下路徑的獲得樹(shù)式搜索：反向求解線式搜索：搜索線本身第64頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月?tīng)顟B(tài)圖搜索搜索策略盲目搜索(無(wú)向?qū)?：按預(yù)定的控制策略進(jìn)行搜索，在搜索過(guò)程中獲得的中間信息不用來(lái)改進(jìn)控制策略。啟發(fā)式搜索(有向?qū)?：在搜索過(guò)程中加入了與問(wèn)題有關(guān)的啟發(fā)性信息，用以指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問(wèn)題的求解過(guò)程并找到最優(yōu)解。按搜索范圍的擴(kuò)展順序不同廣度優(yōu)先搜索深度優(yōu)先搜索第65頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月搜索算法CLOSED表和OPEN表樹(shù)式搜索算法步1把初始節(jié)點(diǎn)放入OPEN表；步2檢查OPEN表，若為空，則問(wèn)題無(wú)解，退出；步3移出OPEN表中第一個(gè)節(jié)點(diǎn)N并放入CLOSED表中，并編號(hào)為n;步4考察節(jié)點(diǎn)N是否為目標(biāo)節(jié)點(diǎn)，若是，則搜索成功，退出；步5若N不可擴(kuò)展，則轉(zhuǎn)步2；步6擴(kuò)展節(jié)點(diǎn)N，生成所有子節(jié)點(diǎn)，對(duì)這組子節(jié)點(diǎn)作如下處理：（1）、如果有節(jié)點(diǎn)N的先輩節(jié)點(diǎn)，則刪除；（2）、如果有已存在于OPEN表的節(jié)點(diǎn)，也刪除；但刪除之前要比較其返回初始節(jié)點(diǎn)的新路徑與原路徑，如果新路徑“短”，則修改這些節(jié)點(diǎn)在OPEN表中的原指向父節(jié)點(diǎn)的指針，使其指向新的父節(jié)點(diǎn)。（3）、如果有已存在于CLOSED表中的節(jié)點(diǎn)，則作與（2）同樣的處理，并且再將其移出CLOSED表，放入OPEN表重新擴(kuò)展；（4）、對(duì)其余子節(jié)點(diǎn)，配上指向父節(jié)點(diǎn)n的指針后放入OPEN表，對(duì)OPEN表按某種搜索策略排序后轉(zhuǎn)步2。第66頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月搜索算法不回溯的線式搜索步1把初始節(jié)點(diǎn)S0放入CLOSED表中；步2令N=S0

；步3若N是目標(biāo)節(jié)點(diǎn)，則搜索成功，結(jié)束;步4若N不可擴(kuò)展，則搜索失敗，退出。步5擴(kuò)展N，選取一個(gè)未在CLOSED表中出現(xiàn)的子節(jié)點(diǎn)N1放入CLOSED表中，令N=N1，轉(zhuǎn)步3?？苫厮莸木€式搜索步1把初始節(jié)點(diǎn)S0放入CLOSED表中；步2令N=S0

；步3若N是目標(biāo)節(jié)點(diǎn)，則搜索成功，結(jié)束;步4若N不可擴(kuò)展，則移出CLOSED表的末端節(jié)點(diǎn)Ne

，若Ne=S0

，則搜索失敗，退出。否則，以CLOSED表新的末端節(jié)點(diǎn)Ne作為N,即令N=Ne

，轉(zhuǎn)步4步5擴(kuò)展N，選取一個(gè)未在CLOSED表中出現(xiàn)的子節(jié)點(diǎn)N1放入CLOSED表中，令N=N1，轉(zhuǎn)步3。第67頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月窮舉式搜索廣度優(yōu)先搜索：優(yōu)先在同一級(jí)節(jié)點(diǎn)中考察，只有當(dāng)同一級(jí)節(jié)點(diǎn)擴(kuò)展完以后，才擴(kuò)展下一級(jí)節(jié)點(diǎn)。廣度優(yōu)先搜索算法：步1把初始節(jié)點(diǎn)S0放入OPEN表中；步2若OPEN表為空，則搜索失敗，退出；步3取OPEN表中前面第一個(gè)節(jié)點(diǎn)N放入CLOSED表中；步4若目標(biāo)節(jié)點(diǎn)Sg=N，則搜索成功，結(jié)束;步5若N不可擴(kuò)展，則轉(zhuǎn)步2。步6擴(kuò)展N，將其所有子節(jié)點(diǎn)配上指向N的指針依次放入OPEN表的尾部，轉(zhuǎn)步2。(OPEN表為一個(gè)隊(duì)列)例、解八數(shù)碼問(wèn)題。初始狀態(tài)(2，3，1，8，4，7，6，5)，目標(biāo)狀態(tài)(1，2，3，8，4，7，6，5)第68頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標(biāo)8234187654第69頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月窮舉式搜索深度優(yōu)先搜索：在搜索的每一層，始終只擴(kuò)展一個(gè)節(jié)點(diǎn)，不斷地向縱深前進(jìn)，直到不能再前進(jìn)時(shí)，才從當(dāng)前節(jié)點(diǎn)返回到上一級(jí)節(jié)點(diǎn)，延另一節(jié)點(diǎn)又繼續(xù)前進(jìn)。深度優(yōu)先搜索算法：步1把初始節(jié)點(diǎn)S0放入OPEN表中；步2若OPEN表為空，則搜索失敗，退出；步3取OPEN表中前面第一個(gè)節(jié)點(diǎn)N放入CLOSED表中；步4若目標(biāo)節(jié)點(diǎn)Sg=N，則搜索成功，結(jié)束;步5若N不可擴(kuò)展，則轉(zhuǎn)步2。步6擴(kuò)展N，將其所有子節(jié)點(diǎn)配上指向N的返回指針依次放入OPEN表的首部，轉(zhuǎn)步2。(OPEN表為一個(gè)堆棧)第70頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月窮舉式搜索廣度優(yōu)先搜索的性質(zhì)當(dāng)問(wèn)題有解時(shí)，一定能找到解當(dāng)問(wèn)題為單位耗散值，且問(wèn)題有解時(shí)，一定能找到最優(yōu)解方法與問(wèn)題無(wú)關(guān)，具有通用性效率較低深度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解當(dāng)深度限制不合理時(shí)，可能找不到解最壞情況時(shí)，搜索空間等同于窮舉是一個(gè)通用的與問(wèn)題無(wú)關(guān)的方法第71頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月窮舉式搜索有界深度優(yōu)先搜索：搜索深度限制。當(dāng)深度優(yōu)先搜索到一定深度后，就不在向縱深搜索，而是改變方向繼續(xù)搜索。有界深度搜索算法步1把初始節(jié)點(diǎn)S0放入OPEN表中，置S0的深度d(S0)=0；步2若OPEN表為空，則搜索失敗，退出；步3取OPEN表中前面第一個(gè)節(jié)點(diǎn)N放入CLOSED表中；步4若目標(biāo)節(jié)點(diǎn)Sg=N，則搜索成功，結(jié)束;步5若N的深度d(N)=dm，或者N無(wú)子節(jié)點(diǎn)，則轉(zhuǎn)步2。步6擴(kuò)展N，將其所有子節(jié)點(diǎn)Ni配上指向N的返回指針后依次放入OPEN表的前部，置d(Ni)=d(N)+1，轉(zhuǎn)步2。第72頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月啟發(fā)式搜索問(wèn)題的提出窮舉法的局限性組合爆炸：梵塔問(wèn)題，博弈：國(guó)際象棋10120，圍棋10761啟發(fā)性信息（1）、用于擴(kuò)展節(jié)點(diǎn)的選擇的信息；（2）、用于生成節(jié)點(diǎn)的選擇的信息；（3）、用于刪除節(jié)點(diǎn)的選擇的信息。Eg：八數(shù)碼問(wèn)題啟發(fā)函數(shù)用來(lái)估計(jì)搜索樹(shù)上節(jié)點(diǎn)X與目標(biāo)節(jié)點(diǎn)Sg接近程度的函數(shù)，記為h(x).第73頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月啟發(fā)式搜索算法(1)全局擇優(yōu)搜索算法：步1把初始節(jié)點(diǎn)S0放入OPEN表中，計(jì)算h(S0)；步2若OPEN表為空，則搜索失敗，退出；步3取OPEN表中前面第一個(gè)節(jié)點(diǎn)N放入CLOSED表中；步4若目標(biāo)節(jié)點(diǎn)Sg=N，則搜索成功，結(jié)束;步5若N不可擴(kuò)展，則轉(zhuǎn)步2。步6

擴(kuò)展N，計(jì)算每個(gè)子節(jié)點(diǎn)x的函數(shù)值h(x)，并將所有子節(jié)點(diǎn)配上指向N的返回指針?lè)湃隣PEN表中，再對(duì)OPEN表中的所有子節(jié)點(diǎn)按其函數(shù)值大小以升序排序，轉(zhuǎn)步2。Eg:八數(shù)碼問(wèn)題P95(2)局部擇優(yōu)搜索擴(kuò)展節(jié)點(diǎn)后僅對(duì)N的子節(jié)點(diǎn)按啟發(fā)函數(shù)值排序后放入OPEN的首部。(問(wèn)題：優(yōu)秀個(gè)體的后代未必優(yōu)秀)第74頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月加權(quán)狀態(tài)圖搜索加權(quán)狀態(tài)圖與代價(jià)樹(shù)Eg:交通圖加權(quán)狀態(tài)圖的搜索要增加權(quán)值的計(jì)算與傳播過(guò)程，并且要由權(quán)值來(lái)確定節(jié)點(diǎn)的擴(kuò)展順序。代價(jià)：g(xj)=g(xi)+c(xi,xj);g(S0)=0.分支界限法：相當(dāng)于啟發(fā)式搜索中的全局擇優(yōu)搜索，不過(guò)用代價(jià)函數(shù)代替啟發(fā)函數(shù)。最近擇優(yōu)法：相當(dāng)于啟發(fā)式搜索中的局部擇優(yōu)搜索，不過(guò)用代價(jià)函數(shù)代替啟發(fā)函數(shù)。第75頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月啟發(fā)式搜索的A算法和A*算法估價(jià)函數(shù)f(x)=g(x)+h(x);其中g(shù)(x)是代價(jià)函數(shù)，h(x)是啟發(fā)函數(shù)?；蚨x為：f(x)=d(x)+h(x);d(x)是x的深度g(x),h(x)對(duì)搜索的影響最小代價(jià)搜索A算法步1把附有f(S0)的初始節(jié)點(diǎn)S0放入OPEN表中；步2若OPEN表為空，則搜索失敗，退出；步3取OPEN表中前面第一個(gè)節(jié)點(diǎn)N放入CLOSED表中；步4若目標(biāo)節(jié)點(diǎn)Sg=N，則搜索成功，結(jié)束;步5若N不可擴(kuò)展，則轉(zhuǎn)步2。第76頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月啟發(fā)式搜索的A算法和A*算法步6擴(kuò)展N，計(jì)算每個(gè)子節(jié)點(diǎn)x的估價(jià)函數(shù)值f(x)，并對(duì)這組子節(jié)點(diǎn)作如下處理：（1）考察是否有已在OPEN表或CLOSED表中存在的節(jié)點(diǎn)；若有，則再考察其中有無(wú)N的先輩節(jié)點(diǎn)，若有則刪除之；對(duì)于其余節(jié)點(diǎn)，也刪除之，但由于它們又被第二次生成，因而需考慮是否修改已經(jīng)存在于OPEN表或CLOSED表中的這些節(jié)點(diǎn)及其后裔的返回指針和f(x)值，修改原則是“抄f(x)值小的路走”；（2）對(duì)其余子節(jié)點(diǎn)配上指向N的返回指針后放入OPEN表中，并對(duì)OPEN表按f(x)值以升序排序，轉(zhuǎn)步2?？梢钥闯?，A算法是樹(shù)式搜索算法加估價(jià)函數(shù)f(x)的一種啟發(fā)式搜索算法。第77頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月啟發(fā)式搜索的A算法和A*算法A算法加上限制：對(duì)所有節(jié)點(diǎn)x均有h(x)h*(x)。其中h*(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的最小代價(jià)。h(x)為啟發(fā)式函數(shù)。由Nilsson提出定理1對(duì)有限圖，如果從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則算法A一定成功結(jié)束。定理2對(duì)無(wú)限圖，若從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則A*一定成功結(jié)束。定理3(可采納性定理)：若存在從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑，則A*必能找到最佳解結(jié)束。第78頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月?tīng)顟B(tài)圖問(wèn)題求解問(wèn)題的狀態(tài)圖表示狀態(tài)：節(jié)點(diǎn)；記錄、對(duì)象、……規(guī)則：邊；數(shù)據(jù)對(duì)(x,y)，條件語(yǔ)句(ifx…y…)，……一個(gè)問(wèn)題的狀態(tài)圖表示為一個(gè)三元組(S,F,G)S:初始狀態(tài)集；G:目標(biāo)狀態(tài)集；F:狀態(tài)轉(zhuǎn)換規(guī)則集合迷宮問(wèn)題的狀態(tài)圖表示 P99顯式狀態(tài)圖八數(shù)碼問(wèn)題的狀態(tài)圖表示 P100隱式狀態(tài)圖TSP問(wèn)題第79頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月與或圖與或圖的引入本質(zhì)：復(fù)雜問(wèn)題分解為簡(jiǎn)單問(wèn)題與或樹(shù) 與或圖狀態(tài)圖和與或圖的關(guān)系目標(biāo)目標(biāo)初始節(jié)點(diǎn)第80頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月與或圖解樹(shù)：?jiǎn)栴}的求解路徑構(gòu)成的樹(shù)。本原問(wèn)題：直接可解的簡(jiǎn)單問(wèn)題。終止節(jié)點(diǎn)：本原問(wèn)題對(duì)應(yīng)的節(jié)點(diǎn)。端節(jié)點(diǎn)：無(wú)子節(jié)點(diǎn)的節(jié)點(diǎn)。終止節(jié)點(diǎn)一定是端節(jié)點(diǎn)，反之不成立。與節(jié)點(diǎn)：子節(jié)點(diǎn)之間是“與”關(guān)系的節(jié)點(diǎn)?；蚬?jié)點(diǎn)：子節(jié)點(diǎn)之間是“或”關(guān)系的節(jié)點(diǎn)。第81頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月與或圖搜索搜索特點(diǎn)：邊擴(kuò)展邊判斷可解判斷終止節(jié)點(diǎn)是可解節(jié)點(diǎn)一個(gè)與節(jié)點(diǎn)可解，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全部可解一個(gè)或節(jié)點(diǎn)可解，只要其子節(jié)點(diǎn)中至少一個(gè)可解不可解判斷非終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn)一個(gè)與節(jié)點(diǎn)不可解，只要其子節(jié)點(diǎn)中至少一個(gè)不可解一個(gè)或節(jié)點(diǎn)可解，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全部不可解盲目搜索(窮舉(廣度/深度)，盲目碰撞)，啟發(fā)式搜索第82頁(yè)，課件共187頁(yè)，創(chuàng)作于2023年2月與或樹(shù)搜索步1把初始節(jié)點(diǎn)S0放入OPEN表中；步2取OPEN表中第一個(gè)節(jié)點(diǎn)N放入CLOSED表中；步3