人工智能原理與應(yīng)用教案

人工智能原理與應(yīng)用PrinciplesandApplicationofArtificialIntelligence課程簡介本課程主要講述人工智能的基本概念、 基本方法，會用搜索算法、推理方法和機(jī)器學(xué)習(xí)求解簡單問題，如證明定理、機(jī)器推理、建造簡單的專家系統(tǒng)，自然語言分析和理解。要求*了解人工智能的提由，幾種智能觀，人工智能重要的研究領(lǐng)域，以及人工智能求解問題的方法與傳統(tǒng)的數(shù)學(xué)方法的不同；“掌握啟發(fā)式搜索概念，會用搜索方法求解簡單問題*掌握歸結(jié)推理方法，會用歸結(jié)法證明定理，求解問題。X掌握一種不確定推理方法，會建造帶有不確定推理的專家系統(tǒng)。了解其它的推理方法；“掌握知識的表示方法，會用來表達(dá)某一具體的場景；“掌握機(jī)器學(xué)習(xí)概念和學(xué)習(xí)模型，會用實(shí)例學(xué)習(xí)方法進(jìn)行學(xué)習(xí)，了解數(shù)據(jù)挖掘的過程，會用關(guān)聯(lián)規(guī)則挖掘算法做數(shù)據(jù)挖掘；*掌握自然語言理解的過程，會用基本的切分和語法分析方法做自然語句分析；“理解神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)智能的另一種觀點(diǎn)。 掌握BP神經(jīng)網(wǎng)的工作原理，會用來求解（如識別）問題；“了解遺傳算法（GQ概念及如何使用遺傳算法參考資料：《人工智能原理與應(yīng)用》，張仰森，高等教育由版社《人工智能》，蔡自興《人工智能原理》，石純一 黃昌寧王家欽編著，清華大學(xué)生版社TOC\o"1-5"\h\z《人工智能》（上下冊），陸汝鈴編著，科學(xué)生版社， 1996《人工智能與知識工程》，田盛豐、黃厚寬，中國鐵道由版社，1999《高級人工智能》，史忠植，科學(xué)生版社， 1998《人工智能基礎(chǔ)》，高濟(jì)、朱森良、何欽銘，高等教育由版社， 2002第一章人工智能概述人工智能的起源與發(fā)展?計(jì)算機(jī)所能處理對象的改變：純粹數(shù)值計(jì)算一非數(shù)值計(jì)算（自然語言理解、圖象語音識別、專家系統(tǒng)、機(jī)器博弈系統(tǒng)等等符號知識處理）?試探性搜索、啟發(fā)式搜索、不確定性推理方法更符合人類思維過程。也就是說在解決這類問題時(shí)，沒有算法解或即使有算法解但在當(dāng)今計(jì)算技術(shù)不能實(shí)現(xiàn)。對這類問題可行的解決方法是搜索、試探，加上經(jīng)驗(yàn)的啟發(fā)式知識。這是一種來自專門領(lǐng)域的經(jīng)驗(yàn)知識，限于特定場合，經(jīng)常會取得成功但又不能保證必然成功，常能求得有關(guān)問題的滿意解答。醫(yī)生一定能根據(jù)病人的癥狀診斷出是何種疾病嗎？我們能用傳統(tǒng)的算法設(shè)計(jì)一個(gè)程序進(jìn)行疾病診斷嗎？能用傳統(tǒng)的算法設(shè)計(jì)一個(gè)程序能理解自然語言所組成的文檔的含義嗎？以上原因促使人工智能學(xué)科的誕生。主要經(jīng)歷了以下幾個(gè)階段：?孕育期（ 1956年以前）——從理論、技術(shù)和物質(zhì)上奠定基礎(chǔ)?成長期（ 1956－1972）——邏輯推理機(jī)程序、跳棋程序、通用問題求解（GPS：GeneralProblemSolver）、人工智能程序設(shè)計(jì)語言LISP/PROLOG?發(fā)展期（1972－）——知識工程、專家系統(tǒng)（MYCIN，探礦系統(tǒng)）?學(xué)習(xí)期什么是人工智能.什么是人類智能？有何特點(diǎn)？計(jì)算機(jī)到底能不能有人類智能？英國數(shù)學(xué)家 Turing于1950提出的著名的Turing實(shí)驗(yàn)。識別、推理、聯(lián)想、自學(xué)習(xí) ...（人腦的智能很復(fù)雜?。┯?jì)算機(jī)到底能不能有人類智能，至今沒有完整的論證（人工智能是一門正在探索和發(fā)展的學(xué)科，至今還沒有完全形成完整的理論體系。目前人工智能與人腦的智能還相差很遠(yuǎn) ）.什么是人工智能？人工智能簡稱為AI（ArtificialIntelligence）,是研究如何制造出智能機(jī)器或智能系統(tǒng)，來模擬人類智能活動(dòng)、延伸人類智能的學(xué)科。已實(shí)現(xiàn)的人工智能系統(tǒng)：第一個(gè)人工智能專家系統(tǒng) DENDRAL,能根據(jù)有機(jī)化合物的質(zhì)譜數(shù)據(jù)，推斷出給有機(jī)化合物的分子結(jié)構(gòu)，該系統(tǒng)得到甚至超過化學(xué)專家水平。該系統(tǒng)是由Stanford大學(xué)的Feigenbaum領(lǐng)導(dǎo)研制成功的。醫(yī)療專家系統(tǒng) MYCIN探礦專家系統(tǒng) PROSPECTOR1995年美國智能機(jī)器人駕駛汽車以 55km/h速度從東部一直開到西部（機(jī)器視覺）1997年國際象棋大師卡斯帕羅夫與 IBM深藍(lán)巨型機(jī)上的博弈系統(tǒng)對弈自然語言理解系統(tǒng)機(jī)器翻譯系統(tǒng)機(jī)器證明系統(tǒng)（證明了“四色問題”、數(shù)學(xué)中的定理）.3AI的研究途徑、方法、不同學(xué)派．目標(biāo)：近期目標(biāo)：使機(jī)器更聰明遠(yuǎn)期目標(biāo)：探討研制智能機(jī).方法、途徑仿生學(xué)方法：對人腦思維進(jìn)行生理學(xué)模擬，通過微觀方法直接模擬人腦和神經(jīng)系統(tǒng)的結(jié)構(gòu)功能計(jì)算機(jī)方法：利用計(jì)算機(jī)科學(xué)的觀點(diǎn)，從宏觀上模擬人的智能活動(dòng)數(shù)學(xué)方法：建立數(shù)學(xué)模型，利用算法求解問題心理學(xué)方法：建立心理學(xué)模型，利用啟發(fā)式程序求解問題．人工智能研究的各種學(xué)派及其理論功能模擬，符號演繹模擬人腦的邏輯思維，將問題和知識表示成某種邏輯網(wǎng)絡(luò)，采用符號推演的方法，實(shí)現(xiàn)搜索、推理、學(xué)習(xí)等功能。這種方法目前還在使用，人工智能研究中的很多成果都是用該方法取得的，如定理證明，自動(dòng)推理，專家系統(tǒng)、博弈系統(tǒng)等。采用這種方法的研究者稱為心理學(xué)派或邏輯學(xué)派或符號主義，代表人物是NILSSON，本課程就是講解這種研究方法。結(jié)構(gòu)模擬，神經(jīng)網(wǎng)絡(luò)計(jì)算根據(jù)人腦的生理結(jié)構(gòu)和工作機(jī)理，研究和實(shí)現(xiàn)計(jì)算機(jī)智能。因?yàn)槿四X是由神經(jīng)細(xì)胞組成的神經(jīng)網(wǎng)絡(luò)，所以該研究途徑就是用人工神經(jīng)元組成的人工神經(jīng)網(wǎng)絡(luò)模型來存儲信息和知識，用神經(jīng)計(jì)算（數(shù)值計(jì)算）的方法實(shí)現(xiàn)自學(xué)習(xí)、聯(lián)想、識別和推理功能。神經(jīng)網(wǎng)絡(luò)具有高度的并行分布性。該研究方法適于實(shí)現(xiàn)圖象、聲音信息識別。采用這種研究途徑稱為生理學(xué)派或連接主義，代表人物是 Newell行為模擬，控制進(jìn)化這種方法模擬人在控制過程中的智能活動(dòng)和行為特性（自尋優(yōu)，自適應(yīng)，自學(xué)習(xí)），強(qiáng)調(diào)“現(xiàn)場AI”（situatedAI）即智能系統(tǒng)或智能機(jī)器能與環(huán)境交互，能對環(huán)境進(jìn)行感知從而表現(xiàn)出智能行為，也就是說智能行為不需要知識從而與“符號主義”相悖。這種方法的研究者稱為行為主義、進(jìn)化主義或控制論學(xué)派。代表人物是MIT的Brooks教授。人工智能是引起爭議最多的學(xué)科之一 ,因而各種研究學(xué)派在發(fā)展的過程都TOC\o"1-5"\h\z經(jīng)歷了許多挫折 .?通過什么途徑有效地實(shí)現(xiàn)智能（如符號演繹推理 ,知識工程 ,神經(jīng)網(wǎng)絡(luò)計(jì)算 ,圖搜索技術(shù) ,不確定推理等 ）.?人工智能的研究范圍問題 ,一般認(rèn)為包括 :知識表示 ,推理技術(shù) ,自然語言理解,知識工程 ,計(jì)算機(jī)視覺等許多方面 .引起爭議的原因 ,第一是由于邊界不分明 ,某些分支與數(shù)學(xué)有交界 （如定理證明 ,謂詞邏輯 ）,或與語言學(xué)有交界 （如自然語言理解）,或與心理學(xué)有交界 （如認(rèn)知模型 ）,或與電子學(xué)機(jī)械學(xué)有交界（如計(jì)算機(jī)視覺 ,機(jī)器人 ）.第二是由于科學(xué)的發(fā)展 ,各分支的內(nèi)容在不斷的變化.第三 ,隨著研究工作的深入 ,一些傳統(tǒng)的觀念在發(fā)生變化 ,例如在歷史上認(rèn)為數(shù)值計(jì)算發(fā)展到符號演算是AI的一個(gè)重要特征 ,但在近年的研究中 ,計(jì)算機(jī)視覺和機(jī)器人學(xué)的研究中又回到了數(shù)值計(jì)算的現(xiàn)象，提高了數(shù)學(xué)在人工智能研究中的地位.AI的研究領(lǐng)域?搜索算法：狀態(tài)空間圖、博弈樹搜索?推理方法：歸結(jié)推理、不確定性推理?自然語言理解：不僅能識別文字而且能理解文本含義的機(jī)器系統(tǒng)?模式識別(圖象與語音識別)外界信息，感受獲取t電信號>特征提取輸入信號模式一?模板庫?—|標(biāo)準(zhǔn)模式M模式匹配 分類識別?」識別結(jié)果?知識工程(知識獲取、知識表示、知識數(shù)據(jù)庫、知識運(yùn)用等一系列知識處理技術(shù)，是以知識為中心來組織智能系統(tǒng))?神經(jīng)網(wǎng)絡(luò)技術(shù)?專家系統(tǒng)?機(jī)器人人工智能求解方法的特點(diǎn)?AI研究的是以符號表示的知識而不是數(shù)值數(shù)據(jù)為研究對象；?AI中采用的啟發(fā)式搜索算法(HeuristicResearchAlgorithm)而不是常規(guī)的算法(Algorithm)? 控制結(jié)構(gòu)與知識是分離的? 允許出現(xiàn)不正確的答案人類智能和人工智能．人類智能特性感知能力思維能力反應(yīng)能力．人工智能特性機(jī)器行為能力機(jī)器感知能力機(jī)器思維能力（知識表示）機(jī)器行為能力第二章知識表示知識及其表示.知識的概念Feigenbaum認(rèn)為知識是經(jīng)過削減、塑造、解釋和轉(zhuǎn)換的信息。簡單地說，知識是經(jīng)過加工的信息。Bernstein說知識是特定領(lǐng)域的描述、關(guān)系和過程組成。Hayes-Roth認(rèn)為知識是事實(shí)、信念和啟發(fā)式規(guī)則。知識可從(范圍，目的，有效性)加以三維描述。其中知識的范圍是由具體到一般，知識的目的是由說明到指定，知識的有效性是由確定到不確定。例如“為了證明A-B,只需證明AA~8是不可滿足的”這種知識是一般性、指示性、確定性的。而像“桌子有四條腿”這種知識是具體的、說明性、不確定性。知識表示是研究用機(jī)器表示知識的可行性、有效性的一般方法，是一種數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)的統(tǒng)一體，既考慮知識的存儲又考慮知識的使用。知識表示可看成是一組描述事物的約定，以把人類知識表示成機(jī)器能處理的數(shù)據(jù)結(jié)構(gòu)。.人工智能系統(tǒng)所關(guān)心的知識一個(gè)智能程序高水平的運(yùn)行需要有關(guān)的事實(shí)知識、規(guī)則知識、控制知識和元知識。事實(shí):是有關(guān)問題環(huán)境的一些事物的知識，常以“...是…”的形式出現(xiàn)。如事物的分類、屬性、事物間關(guān)系、科學(xué)事實(shí)、客觀事實(shí)等，在知識庫中屬于低層的知識。如雪是白色的、鳥有翅膀、張三李四是好朋友。規(guī)則:是有關(guān)問題中與事物的行動(dòng)、動(dòng)作相聯(lián)系的因果關(guān)系知識，是動(dòng)態(tài)的，常以“如果…那么…”形式出現(xiàn)。特別是啟發(fā)式規(guī)則是屬于專家提供的專門經(jīng)驗(yàn)知識，這種知識雖無嚴(yán)格解釋但很有用處?？刂?是有關(guān)問題的求解步驟，技巧性知識，告訴怎么做一件事。也包括當(dāng)有多個(gè)動(dòng)作同時(shí)被激活時(shí)應(yīng)選哪一個(gè)動(dòng)作來執(zhí)行的知識。元知識:是有關(guān)知識的知識，是知識庫中的高層知識。包括怎樣使用規(guī)則、解釋規(guī)則、校驗(yàn)規(guī)則、解釋程序結(jié)構(gòu)等知識。邏輯表示法對知識通過引入謂詞、函數(shù)來加以形式描述，獲得有關(guān)的邏輯公式，進(jìn)而以機(jī)器內(nèi)部代碼表示。設(shè)在一個(gè)房間里，有一個(gè)機(jī)器人ROBOT一個(gè)壁室ALCOVE一個(gè)積木塊BOX兩個(gè)桌子A和B。機(jī)器人可把積木塊BOXA一種狀態(tài)變換成另一種狀態(tài)。引入謂詞：TABLE(A)表示A是桌子EMPTYHANDEROBOT表示機(jī)器人雙手是空的AT(ROBOTA)表示機(jī)器人在A旁HOLDSROBOTBOX表示機(jī)器人拿著積木塊ON(BOXA)表積木塊BOXBA上產(chǎn)生式表示法產(chǎn)生式是一種知識表達(dá)方法，具有和Turing機(jī)一樣的表達(dá)能力。事實(shí)與規(guī)則的表示事實(shí)可看成是斷言一個(gè)語言變量的值或是多個(gè)語言變量間的關(guān)系的陳述句，語言變量的值或語言變量間的關(guān)系可以是一個(gè)詞。不一定是數(shù)字。如雪是白色的，其中雪是語言變量，其值是白色的。 John喜歡Mary,其中John、Mary是兩個(gè)語言變量，兩者的關(guān)系值是喜歡。一般使用三元組(對象，屬性，值)或(關(guān)系，對象 1，對象 2)來表示事實(shí)，其中對象就是語言變量，若考慮不確定性就成了四元組表示(增加可信度)這種表示的機(jī)器內(nèi)部實(shí)現(xiàn)就是一個(gè)表。如事實(shí)“老李年齡是 35歲”，便寫成(Lee,age,35)事實(shí)“老李、老張是朋友”，可寫成(friend,Lee,Zhang)對于規(guī)則是表示事物間的因果關(guān)系，以下列形式表示：condition->actioncondition作為前件或模式，而action稱作動(dòng)作或后件或結(jié)論。前件部分常是一些事實(shí)Ai的合取，而結(jié)論常是某一事實(shí) B,如考慮不確定性，需另附可信度度量值。產(chǎn)生式系統(tǒng)的組成和推理多數(shù)較為簡單的專家系統(tǒng)(ExpertSystem)都是以產(chǎn)生式表示知識的，相應(yīng)的系統(tǒng)稱作產(chǎn)生式系統(tǒng)。產(chǎn)生式系統(tǒng)，由知識庫和推理機(jī)兩部分組成。其中知識庫由規(guī)則庫和數(shù)據(jù)庫組成。規(guī)則庫是產(chǎn)生式規(guī)則的集合，數(shù)據(jù)庫是事實(shí)的集合。規(guī)則是以產(chǎn)生式表示的。規(guī)則集蘊(yùn)涵著將問題從初始狀態(tài)轉(zhuǎn)換解狀態(tài)的那些變換規(guī)則，規(guī)則庫是專家系統(tǒng)的核心。規(guī)則可表成與或樹形式，基于數(shù)據(jù)庫中的事實(shí)對這與或樹的求值過程就是推理。數(shù)據(jù)庫中存放著初始事實(shí)、外部數(shù)據(jù)庫輸入的事實(shí)、中間結(jié)果事實(shí)和最后結(jié)果事實(shí)。推理機(jī)是一個(gè)程序，控制協(xié)調(diào)規(guī)則庫與數(shù)據(jù)庫的運(yùn)行，包含推理方式和控制策略。產(chǎn)生式系統(tǒng)的推理方式有正向推理、反向推理和雙向推理正向推理：從已知事實(shí)出發(fā)，通過規(guī)則庫求得結(jié)論，或稱數(shù)據(jù)驅(qū)動(dòng)方式。推理過程是規(guī)則集中的規(guī)則前件與數(shù)據(jù)庫中的事實(shí)進(jìn)行匹配，得匹配的規(guī)則集合。從匹配規(guī)則集合中選擇一條規(guī)則作為使用規(guī)則。執(zhí)行使用規(guī)則的后件。將該使用規(guī)則的后件送入數(shù)據(jù)庫中重復(fù)這個(gè)過程直至達(dá)到目標(biāo)具體說如數(shù)據(jù)庫中含有事實(shí)A,而規(guī)則庫中有規(guī)則A->B,那么這條規(guī)則便是匹配規(guī)則，進(jìn)而將后件B送入數(shù)據(jù)庫中。這樣可不斷擴(kuò)大數(shù)據(jù)庫直至包含目標(biāo)便成功結(jié)束。如有多條匹配規(guī)則需從中選一條作為使用規(guī)則，不同的選擇方法直接影響著求解效率，選規(guī)則的問題稱作控制策略。正向推理會得出一些與目標(biāo)無直接關(guān)系的事實(shí)，是有浪費(fèi)的。反向推理：從目標(biāo)（作為假設(shè)）出發(fā)，反向使用規(guī)則，求得已知事實(shí)，或稱目標(biāo)驅(qū)動(dòng)方式，推理過程是：規(guī)則集中的規(guī)則后件與目標(biāo)事實(shí)進(jìn)行匹配，得匹配的規(guī)則集合；從匹配的規(guī)則集合中選擇一條規(guī)則作為使用規(guī)則；將使用規(guī)則的前件作為子目標(biāo)；重復(fù)這個(gè)過程直至各子目標(biāo)均為已知事實(shí)成功結(jié)束；如果目標(biāo)明確，使用反向推理方式效率較高。雙向推理：同時(shí)使用正向推理又使用反向推理。產(chǎn)生式表示的特點(diǎn)產(chǎn)生式表示格式固定，形式單一，規(guī)則（知識單位）間相互較為獨(dú)立，沒有直接關(guān)系使知識庫的建立較為容易，處理較為簡單的問題是可取的。另外推理方式單純，也沒有復(fù)雜計(jì)算。特別是知識庫與推理機(jī)是分離的，這種結(jié)構(gòu)給知識的修改帶來方便，無須修改程序，對系統(tǒng)的推理路徑也容易作出解釋。所以，產(chǎn)生式表示知識常作為構(gòu)造專家系統(tǒng)的第一選擇的知識表示方法。語義網(wǎng)絡(luò)表示法邏輯表示法和產(chǎn)生式表示法常用于表示有關(guān)論域中各個(gè)不同狀態(tài)間的關(guān)系，然而用于表示一個(gè)事物同其各個(gè)部分間的分類知識就不方便了。梢（slot）與填梢表示方法便于表示這種分類知識。語義網(wǎng)絡(luò)和框架表示方法就屬于其中的兩種。語義網(wǎng)絡(luò)的結(jié)構(gòu)語義網(wǎng)絡(luò)是對知識的有向圖表示方法。一個(gè)語義網(wǎng)絡(luò)是由一些以有向圖表示的三元組（結(jié)點(diǎn)1,弧，結(jié)點(diǎn)2）連接而成。結(jié)點(diǎn)表示概念、事物、事件、情況等?；∈怯蟹较虻挠袠?biāo)注的。方向體現(xiàn)主次，結(jié)點(diǎn)1為主，結(jié)點(diǎn)2為輔。弧上的標(biāo)注表示結(jié)點(diǎn)1的屬性或結(jié)點(diǎn)1和結(jié)點(diǎn)2之間的關(guān)系。如事實(shí)“雪是白色的”，可表示成：顏色 白色的如規(guī)則“如果A那么B"，可表示成:艮A >B這樣事實(shí)與規(guī)則的表示是相同的，區(qū)別僅是弧上的標(biāo)注有別從邏輯表示法來看，一個(gè)語義網(wǎng)絡(luò)相當(dāng)于一組二元謂詞。因?yàn)槿M(結(jié)點(diǎn)1,弧，結(jié)點(diǎn)2)可寫成P(個(gè)體1,個(gè)體2),其中個(gè)體1、個(gè)體2對應(yīng)于結(jié)點(diǎn)1、結(jié)點(diǎn)2,而弧及其上標(biāo)注的結(jié)點(diǎn)1與結(jié)點(diǎn)2的關(guān)系由謂詞P來體現(xiàn)。語義網(wǎng)絡(luò)視作一種知識的單位，人腦的記憶是由存儲了大量的語義網(wǎng)絡(luò)來體現(xiàn)的。而產(chǎn)生式表示法是以一條產(chǎn)生式規(guī)則作為知識的單位，而各條產(chǎn)生式規(guī)則沒有直接的聯(lián)系。結(jié)點(diǎn)間的關(guān)系有isa,a-part-of,is型(1)ISA鏈用來表示具體-抽象關(guān)系，或說表示一種隸屬關(guān)系，體現(xiàn)某種層次分類。特點(diǎn)是具體層結(jié)點(diǎn)可繼承抽象層我點(diǎn)的屬性。鳥類 >動(dòng)捌(2)a-part-of 鏈用來表示部分-全體關(guān)系，或說表示包含關(guān)系。特點(diǎn)是part-of?關(guān)系下4層結(jié)點(diǎn)的屬性?能是很個(gè)相同的。兩5?手—那一口f\人工(3)is鏈用于表示一個(gè)結(jié)點(diǎn)是另「個(gè)結(jié)點(diǎn)的屬性老張—— >140歲例：蘋果的語義網(wǎng)絡(luò)水果——>有營養(yǎng)的A蘋果I甜的中國 國冢語義網(wǎng)絡(luò)表示下的推理語義網(wǎng)絡(luò)表示下的推理方法不像邏輯表示法和產(chǎn)生式表示法的推理方法那樣明了。語義網(wǎng)絡(luò)表示法是依匹配和繼承來進(jìn)行推理的。最簡單的isa關(guān)系下的推理是直接繼承，如:也可以將語義網(wǎng)絡(luò)引入邏輯含義，表示出A,V,?關(guān)系，便可以使用歸結(jié)推理法。還有人將語義網(wǎng)絡(luò)中的結(jié)點(diǎn)看成有限自動(dòng)機(jī)（DFA,為尋求幾個(gè)概念間的關(guān)系，起動(dòng)相應(yīng)的自動(dòng)機(jī)，如有回合點(diǎn)便可求得解答?？蚣鼙硎痉蚣芾碚?975年Minsky的論文“Aframeworkforrespresentingknowledge”中提出了框架理論。其基本觀點(diǎn)是人腦已存儲有大量典型情景，當(dāng)人面臨新的情景時(shí)，就從記憶中選擇一個(gè)稱為框架的基本知識結(jié)構(gòu)，這個(gè)框架是以前記憶的一個(gè)知識空框，而其具體內(nèi)容依新的情景而改變，對這空框的細(xì)節(jié)加工修改和補(bǔ)充，形成對新情景的認(rèn)識又記憶于人腦中?？蚣芾碚搶⒖蚣芤曌鞯闹R單位，將一組有關(guān)的框架連接起來便形成框架系統(tǒng)。系統(tǒng)中不同框架可以有共同結(jié)點(diǎn)，系統(tǒng)的行為由系統(tǒng)內(nèi)框架的變化來表現(xiàn)的。推理過程是由框架間的協(xié)調(diào)來完成的?？蚣鼙硎痉ㄊ且环N適應(yīng)性強(qiáng)、概括性高、結(jié)構(gòu)化良好、推理方式靈活又能把陳述性知識與過程性知識相結(jié)合的知識表示方法?？蚣芙Y(jié)構(gòu)框架是由若干結(jié)點(diǎn)和關(guān)系（統(tǒng)稱為槽 slot）構(gòu)成的網(wǎng)絡(luò)。是語義網(wǎng)絡(luò)一般化形式化的一種結(jié)構(gòu)，同語義網(wǎng)絡(luò)沒有本質(zhì)區(qū)別。將語義網(wǎng)絡(luò)中結(jié)點(diǎn)間弧上的標(biāo)注也放入槽內(nèi)就成了框架表示法。框架是表示某一類情景的結(jié)構(gòu)化的一種數(shù)據(jù)結(jié)構(gòu)?？蚣苡煽蚣苊鸵恍┎郏╯lot）組成，每個(gè)槽有一些值，槽值可以是邏輯的、數(shù)字的，可以是程序、條件、默認(rèn)值或是一個(gè)子框架。槽值含有如何使用框架信息、下一步可能發(fā)生的信息、預(yù)計(jì)未實(shí)現(xiàn)該如何做的信息等?？蚣艿囊话愀袷剑篎RAMEWO：R<Kframeworkname><slot1><face11>:value<face1n>:value<slot2><face21>:value<face2n>:value例：framework:<大學(xué)教師>類屬： <教師>學(xué)歷：（學(xué)士，碩士，博士）專業(yè)： <學(xué)科專業(yè)>職稱：（助教，講師，副教授，教授）外語：范圍：（英，法，德，…）默認(rèn)：英水平：（優(yōu)、良、中、差）默認(rèn)：良框架表示下的推理框架表示法沒有固定的推理機(jī)理。但框架系統(tǒng)的推理和語義網(wǎng)絡(luò)一樣遵循匹配和繼承的原則，而且框架中如if-needed、if-added等梢的梢值是附加過程，在推理過程中起重要作用。如確定一個(gè)人的年齡，已匹配的知識庫中的框架為梢名年齡：NILif-needed:ASKif-added:CHECK在推理的過程中便啟動(dòng)了if-needed和if-added兩個(gè)梢的附加過程ASKSICHECK4.5.4框架與產(chǎn)生式表示法的比較productionframework知識表示單位「推理規(guī)則框架?固定、與知識庫獨(dú)立 1口」受，與知識庫成一體 「建立知識庫容易困難通用性_[低高應(yīng)用_r簡單問題復(fù)雜問題 [用戶一初學(xué)者專家面向?qū)ο蟮谋硎痉_本表示法過程表示法狀態(tài)空間表示法：用來表示問題及其搜索過程的一種方法。1．問題狀態(tài)空間的構(gòu)成（1）狀態(tài)：是描述問題求解過程中不同時(shí)刻狀況的數(shù)據(jù)結(jié)構(gòu)。一般用一組變量的有序集合表示：Q=（q0,q1,q2,…,qn）淇中qi為集合的分量，稱為狀態(tài)變量。當(dāng)一個(gè)分量以確定的值時(shí)，就得到一個(gè)具體的狀態(tài)。（2）算符：引起狀態(tài)中某些分量發(fā)生變化，從而使問題由一個(gè)狀態(tài)轉(zhuǎn)變?yōu)榱硪粋€(gè)狀態(tài)的操作。（3）狀態(tài)空間：由表示一個(gè)問題的全部狀態(tài)及一切可用算符構(gòu)成的集合。一般由三部分構(gòu)成：問題的所有可能的初始狀態(tài)構(gòu)成的集合 S,算符集合F,目標(biāo)狀態(tài)集合 G,用一個(gè)三元組表示：（S,F,G）狀態(tài)空間的圖示形式稱為狀態(tài)空間圖，其中，節(jié)點(diǎn)表示狀態(tài)，有向邊表示算符。（4）問題的解：從問題的初始狀態(tài)集 S出發(fā)，經(jīng)過一系列的算符運(yùn)算，到達(dá)目標(biāo)狀態(tài)，由初始狀態(tài)到目標(biāo)狀態(tài)所用算符的序列就構(gòu)成了問題的一個(gè)解。2．用狀態(tài)空間表示問題的步驟（1）定義問題狀態(tài)的描述形式（2）用所定義的狀態(tài)描述形式吧問題的所有可能的狀態(tài)都表示出來，并確定出問題的初始狀態(tài)集合描述和目標(biāo)狀態(tài)集合描述。（3）定義一組算符，使得利用這組算符可把問題由一種狀態(tài)轉(zhuǎn)變到另一種狀態(tài)。3．利用狀態(tài)空間求解問題的過程例：二階Hanoi塔問題（見 P72）解：第一步，定義問題狀態(tài)的描述形式第二步，用所定義的狀態(tài)描述形式把問題的所有可能的狀態(tài)都表示出來，并確定出問題的初始狀態(tài)集合描述和目標(biāo)狀態(tài)集合描述第三步，定義一組算符2.10與/或樹表示法1、與或樹的概念用一個(gè)類似圖的結(jié)構(gòu)來表示把問題歸約為后繼問題的替換集合，畫出歸約問題圖。例如，設(shè)想問題A需要由求解問題 B、C和D來決定，那么可以用一個(gè)與圖來表示；同樣，一個(gè)問題A或者由求解問題B、或者由求解問題C來決定，則可以用一個(gè)或樹來表示。2、與或樹的有關(guān)術(shù)語父節(jié)點(diǎn) 是一個(gè)初始問題或是可分解為子問題的問題節(jié)點(diǎn)；子節(jié)點(diǎn) 是一個(gè)初始問題或是子問題分解的子問題節(jié)點(diǎn)；或節(jié)點(diǎn) 只需解決某個(gè)問題就可解決其父輩問題的節(jié)點(diǎn)集合；與節(jié)點(diǎn) 只有解決所有子問題，才能解決其父輩問題的節(jié)點(diǎn)集合；弧線是父輩節(jié)點(diǎn)指向子節(jié)點(diǎn)的圓弧連線；終葉節(jié)點(diǎn) 是對應(yīng)于原問題的本原節(jié)點(diǎn)。3、與或樹的有關(guān)定義可解節(jié)點(diǎn) 與或樹中一個(gè)可解節(jié)點(diǎn)的一般定義可以歸納如下：終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)（因?yàn)樗鼈兣c本原問題相關(guān)連 ）。如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只有當(dāng)其后繼節(jié)點(diǎn)至少有一個(gè)是可解的時(shí)，此非終葉節(jié)點(diǎn)才是可解的。如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只需當(dāng)其后繼節(jié)點(diǎn)全部為可解時(shí)，此非終葉節(jié)點(diǎn)才是可解的。不可解節(jié)點(diǎn)不可解節(jié)點(diǎn)的一般定義歸納于下：沒有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只有當(dāng)其全部后裔為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只要當(dāng)其后裔至少有一個(gè)為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。4、與或樹構(gòu)樹規(guī)則與或樹中的每個(gè)節(jié)點(diǎn)代表一個(gè)要解決的單一問題或問題集合。樹中所含起始節(jié)點(diǎn)對應(yīng)于原始問題。對應(yīng)于本原問題的節(jié)點(diǎn)，叫做終葉節(jié)點(diǎn)，它沒有后裔。對于把算符應(yīng)用于問題A的每種可能情況，都把問題變換為一個(gè)子問題集合；有向弧線自A指向后繼節(jié)點(diǎn)，表示所求得的子問題集合。一般對于代表兩個(gè)或兩個(gè)以上子問題集合的每個(gè)節(jié)點(diǎn)，有向弧線從此節(jié)點(diǎn)指向此子問題集合中的各個(gè)節(jié)點(diǎn)。在特殊情況下，當(dāng)只有一個(gè)算符可應(yīng)用于問題A，而且這個(gè)算符產(chǎn)生具有一個(gè)以上子問題的某個(gè)集合時(shí)，由上述規(guī)則3和規(guī)則4所產(chǎn)生的圖可以得到簡化。第三章推理方法謂詞邏輯是一種表達(dá)力很強(qiáng)的形式語言，謂詞邏輯及其推理方法是人工智能中知識表示方法，機(jī)器推理，定理證明的基本方法。另外謂詞邏輯中的替換合一技術(shù)，也是符號推理中模式匹配的基本技術(shù)。本章主要講解基于謂詞邏輯的歸結(jié)演繹推理。歸結(jié)推理方法(確定性推理方法)謂詞、函數(shù)、量詞?謂詞：表示個(gè)體對象之間的關(guān)系、屬性或狀態(tài)。其表示形式如下：P(x1,x2,x3，…xn)其中：P是謂詞符號，表示x1,x2,x3，…xn 個(gè)體對象之間的屬性、狀態(tài)或關(guān)系。x1,x2,x3，…xn 是謂詞的參量(或稱項(xiàng))，一般表示個(gè)體，它可以是個(gè)體常量、個(gè)體變量或是個(gè)體函數(shù)。個(gè)體變元的變化范圍稱為個(gè)體域(或論域)例：P(x):表示x是素?cái)?shù)FRIEND(a,b):表示a和b是朋友?個(gè)體函數(shù)：表示項(xiàng)之間的關(guān)系有了個(gè)體函數(shù)之后，謂詞的表達(dá)能力更強(qiáng)。假如個(gè)體函數(shù)father(b)表示“個(gè)體b的父親”，則謂詞FRIEND(a,father(b))表示“a和b的父親是朋友”，顯然表達(dá)能力更強(qiáng)了。再例：E(x,y):表示x和y相等關(guān)系個(gè)體函數(shù)square(x):表示個(gè)體x的平方則謂詞E(square(a),b)表示什么？約定：(1)謂詞符號有大寫字母表示，如巳Q,RS等；(2)用小寫字母x,y,z等作為個(gè)體變元符號；(3)用小寫字母a,b,c等作為個(gè)體常元符號；(4)用小寫字母f,g,h表示個(gè)體函數(shù)符號。?量詞全稱量詞：“所有”，“一切”，“任一”，“全體”，“凡是”等詞稱為全稱量詞，記為'x存在量詞：“存在”、“有些”、“至少有一個(gè)"、“有的”等詞統(tǒng)稱為存在量詞，記為'x引入量詞和連接符(一蘊(yùn)涵，A合取，V析取，否定詞?)之后，謂詞的表達(dá)能力大大擴(kuò)充了例1:謂詞M(x):表示x是人，謂詞N(x):表示x有名字，則，x(M(x)-N(x))表示“凡是人都有名字”。例2:謂詞G(x):表示x是整數(shù)，E(x):表示x是偶數(shù),則mx(G(x)A~E(x))表示“存在不是偶數(shù)的整數(shù)”例3:知識“不存在最大的整數(shù)”的表示設(shè)：謂詞G(x):表示x是整數(shù)，D(x,y)表示x大于V。則表示如下：?mx(G(x)A^y(G(y)-D(x,y)))或〃x(G(x)A3y(G(y)AD(y,x)))?謂詞公式：用謂詞、量詞(存在量詞，全稱量詞)、聯(lián)接詞(-蘊(yùn)涵，A合取，V析取)連接而成的復(fù)雜的符號表達(dá)式稱為謂詞公式。命題邏輯的歸結(jié)法1.概念：不帶參數(shù)(肯定也不含量詞))的謂詞稱為命題.謂詞的表達(dá)能力更強(qiáng)，命題沒有概括能力；命題：P1:代表“北京是一個(gè)城市”P2:代表“上海是一個(gè)城市”P3:代表“廣州是一個(gè)城市”謂詞：CITY(x):代表“x是一個(gè)城市”，x的論域?yàn)镈=｛北京，上海，廣州｝謂詞代表變化著的情況，而命題代表固定的情況；P:北京是一個(gè)城市；Q:煤球是白的；則P為永真式，Q為永假式；而對于以上的謂詞CITY(x),當(dāng)x取值為“北京”時(shí)為“真”值，當(dāng)x取值為“煤球”時(shí)為“假”值。謂詞和命題相比的優(yōu)點(diǎn)是謂詞在不同的知識之間建立聯(lián)系；例如下面四個(gè)知識單元：HUMAN(x)代表x是人；LAWED(x)代表x受法律管制；COMMIT(x)代表x犯法；PUNISHED(x):x受法律制裁；HUMAN(在LAWED(煤示一個(gè)高級的知識單元“人人都受法律的管制”。COMMIT(xpPUNISHED(■示只要x犯罪，x就要受法律制裁。｛(HUMAN(x)>LAWED(x)—(COMMIT(x)>PUNISHED(x)｝表示“如果由于某個(gè)x是人而受到法律管制，則這個(gè)人犯了罪就一定要受到懲罰”由連接詞(一蘊(yùn)涵，人合取，V析取，等價(jià)<->,否定詞~)將命題連接在一起構(gòu)成命題公式。A->B,A稱為前件，B稱為后件，其真值表如下所示：

ABA->B001011100111A<->B等價(jià)于(A->B)A(B->A)一i些概念：永真式：真值為T的命題公式稱為永真式或重言式或有效的。永假式：真值為F的命題公式稱為永假式或不可滿足的。非永真式：不是永真式的命題公式；可滿足式：不是永假公式的命題公式；原子公式：不含任何連接詞的命題公式稱為原子公式或稱原子.例如P,Q文字：原子公式及其否定形式稱為文字.例如P,?L子句：文字的析取稱為子句.例如:PVRV?Q互補(bǔ)文字：設(shè)L為一個(gè)文字，則稱L與?L為互補(bǔ)文字。一些有用的等價(jià)關(guān)系：~~A<=>A雙重否定AAA<=>AAVA<=>A等哥律AAB<=>BAA交換律AVB<=>BVA(AAB)AC<=>AA(BAC)結(jié)合律(AVB)VC<=>AV(BVC)AA(BVC)<=>(AAB)V(AAC)分配律AV(BAC)<=>(AVB)A(AVC)AA(AVB)<=>A吸收律AV(AAB)<=>A?(AAB)<=>?AV?B摩根定律?(AVB)<=>?AA?BA—B<=>?AVB蘊(yùn)含表遼式A<->B<=>(A-B)A(B-A)等價(jià)表達(dá)式AAT<=>AAAF<=>FAVT<=>TAVF<=>Aaa~a<=>f矛盾律AV?A<=>T排中律Af(B-C)<=>AAB-C輸出律(A—B)A(A-?B)<=>?A歸謬律A—B<=>?B—?A逆反律2命題邏輯中的歸結(jié)推理方法若命題邏輯描述的命題A1,A2,...An和B,要證明在A1AA2A...AAn成立的條件下有B成立，或說A1AA2A...AAn^B。很顯然A1AA2A...AAn-^B等價(jià)于證明A1AA2A...AAnA?B是矛盾(永假)式。歸結(jié)推理的方法就是從A1AA2A...AAnA?B出發(fā)使用歸結(jié)推理規(guī)則來尋找矛盾，從而證明A1AA2A...AAn-^B的成立。這種方法稱為反演推理方法。3歸結(jié)式設(shè)有兩個(gè)子句C1=P\/C1'C2=~PVC2'從中消去互補(bǔ)對，所得新子句R(C1,C2)=C1'VC2',稱為子句C1',C2'的歸結(jié)式。沒有互補(bǔ)對的兩子句沒有歸結(jié)式。歸結(jié)推理規(guī)則就指的是對兩子句做歸結(jié)，也即求歸結(jié)式。下面證明歸結(jié)推理規(guī)則是正確的，即C1AC2=>R(C1,C2),也即證明歸結(jié)式是兩子句的邏輯結(jié)論，或者說任一使C1,C2為真的解釋I下必有R(C1,C2)也為真。證：設(shè)I是使C1,C2為真的任一解釋，若在I下P為真，從而?P為假，則C2,必為真，那么R(C1,C2)=C1'VC2'為真。若在I下P為假，則C1'必為真，那么R(C1,C2)=C1'VC2'為真。從而證明了C1AC2=>R(C1,C2),即歸結(jié)式是子句的邏輯結(jié)論。特別地，當(dāng)C1=HC2=?P時(shí)，R(C1,C2)=口，記作為空子句。顯然C1,C2同時(shí)為真是矛盾，或者說空子句口體現(xiàn)了矛盾。4命題邏輯的歸結(jié)推理過程(1)利用邏輯蘊(yùn)含式和邏輯等價(jià)式將命題公式化成合取范式(子句的析取)(2)子句集：將若干個(gè)子句的合取式中的合取詞人換成逗號，形成的集合稱為子句集。(3)從子句集S出發(fā)，僅只對S的子句間使用歸結(jié)推理規(guī)則(即求歸結(jié)式)，并將所得歸結(jié)式仍放入S中，進(jìn)而再對新子句集使用歸結(jié)推理規(guī)則，重復(fù)這些步驟直到得到空子句口(說明有矛盾)。便說明 S是不可滿足的，從而與子句集S對應(yīng)的定理是成立的。例：證明(P-Q)A?Q==EP證：先將已知以及結(jié)論的反化成合取范式(?PVQA?QA(??P)==>(?PVQ)A?QAP,建立子句集S={?PVQ/Q,P}對S作歸結(jié)(1)?PVQ(2)?Q(3)P(4)?P 對(1)(2)求歸結(jié)式(5)□ 對(3)(4)求歸結(jié)式得證。例：證明(P—Q)A(R-?Q)==>(E?P)證明:將已知以及結(jié)論的反化成合取范式==>(?PVQ)A(?RV?Q)A(?(?RV?P))==>(?PVQ)A(?RV?Q)ARAP化成子句集S={?PVQ,?RV?QR,P},對S做歸結(jié)：(1)?PVQ(2)?RV?Q(3)R(4)P(5)?Q...(2)(3)歸結(jié)(6)Q...(1)(4)歸結(jié)(7)□...(5)(6)歸結(jié)3.1.3謂詞公式的子句集1合取范式和析取范式(1)合取范式：若謂詞公式A有如下形式B1AB2A...ABn,其中Bi(i=1,2,...n)形如L1VL2V...VLn,并且L1,L2,...Ln都是文字。例：(P(x)V?Q(y))A(?P(x)VR(x,y))A(?Q(y)V?R(x,y))應(yīng)用邏輯等價(jià)式可以將任一謂詞公式化成合取范式。(2)析取范式:若謂詞公式A有如下形式B1VB2V...VBn,其中Bi(i=1,2,...n)形如L1AL2A...ALn,并且L1,L2,...Ln都是文字。例：(P(x)A?Q(y)AR(x,y))V(?P(x)AR(x,y))應(yīng)用邏輯等價(jià)式和邏輯蘊(yùn)含式可以將任一謂詞公式化成析取范式。(3)前束范式：將所有的量詞都放在謂詞公式的前面。如xxVy(P(x,y)AQ(a)AR(z))就是前束范式。1x(N(x)AyDyD(y,x))就不是前束范式。前束范式可分成前束合取范式和前束析取范式?；汕笆先》妒降牟襟E：?stepl:去掉多余的量詞，即沒意義的量詞?step2:將同名的約束變元與自由變元改名，使它們不同名。?消去A,V,~以外的連接詞A->B ?A VBA<->B (~A VB)A(~BVA)?step4:將連接詞~內(nèi)移，移到原子公式之前~(~A)=A?(AAB)<=>?AV?B?(AVB)<=>?AA?B?9xA(x)<=>3x~A(x)?=1xA(x)<=即x?A(x)?step5:將量詞盡可能向左推，推到前綴所在的位置，用下列公式:3xA(x)VB mx(A(x)VB),其中B中不含約束變元BV3xA(x) 且x(BVA(x)),其中B中不含約束變元VxA(x)VB ^x(A(x)VB),其中B中不含約束變元BVVxA(x) "x(BVA(x)),其中B中不含約束變元同樣對上面式子中的V改為人可得到另一組關(guān)于的A的替換式。另外還可用下式進(jìn)行替換：甘xA(x)AVxB(x) Vx(A(x)AB(x))甘xA(x)VVxB(x) VxV，y(A(x)VB(y)),采用更名規(guī)則3xA(x)VmxB(x) 3 x(A(x)VB(x))3xA(x)A^xB(x) m xmy(a(x)AB(y)),采用更名規(guī)則?step6:使用A,V的分配律化成合取范式。例：將下列謂詞公式化成前束合取范式：=u丘陞么y))+■VyR(x,y))一寸出七。也力)多干困萬⑷)n力(仍0)VVzQ{z,切)7孔~取再0)二> (嚴(yán)阮)JR(k⑼)=卡4(~尸(?a七~ V3^~R(代飛口￥北士一尸(x)A~Q(E,y))\/九~=V犬生玉(I』尸3八~QUxAm”我(文瑜)生① 玳工"))八(一(4)Skolem(斯克林)標(biāo)準(zhǔn)型：將一個(gè)謂詞公式中所有存在量詞消去之后，便得到該謂詞公式的Skolem標(biāo)準(zhǔn)型。

(5)建立謂詞公式的子句集2將謂詞公式化成子句集的步驟：?按上述步驟化成前束合取范式；?化成Skolem標(biāo)準(zhǔn)型，消去存在量詞消取存在量詞時(shí)，還要進(jìn)行變元替換。變元替換分兩種情況：①若該存在量詞在某些全稱量詞的轄域內(nèi)，則用這些全稱量詞指導(dǎo)變元的一個(gè)函數(shù)代替該存在量詞轄域中的相應(yīng)約束變元， 這樣的函數(shù)稱為Skolem函數(shù);②若該存在量詞不在任何全稱量詞的轄域內(nèi)，則用一個(gè)常量符號代替該存在量詞轄域中相應(yīng)約束變元，這樣的常量符號稱為 Skolem常量；?消去所有全稱量詞?消去合取詞A,用逗號代替，以子句為元素組成一個(gè)集合 S,即是謂詞公式的子句集例1:求謂詞公式G=x3y3z((?P(x,y)VR(x,y,z))A(Q(x,z)VR(x,y,z)))的子句集。解：已經(jīng)是前束范式，并且不含連接詞。由于存在量詞 y,z都在全稱量詞x的轄域中，所以將y,z分別用Skolem函數(shù)f(x)、g(x)代替。vx((?P(x,f(x))vR(x,f(x),g(x)))A(Q(x,g(x))VR(x,f(x),g(x))))已經(jīng)是合取范式了，所以謂詞公式G的子句集是{?P(x,f(x))VR(x,f(x),g(x)) ,Q(x,g(x))VR(x,f(x),g(x)) }例2:求謂詞公式的子句集："x(dyP(x,y)-~'y(Q(x,y)-R(x,y)))改名量詞分配率量詞分配率?R(x,z))]…分配律V?R(x,g(x))]…消解：？x(HyP(x,y)-~dy(Q(x,y)-R(x,y)))==>"x("yP(x,y)-閂y~(~Q(x,y)VR(x,y)))==Nx("yP(x,y)-三y(Q(x,y)A~R(x,y)))==>^x(%P(x,y)-三z(Q(x,z)A?R(x,z)))...__>Vx3y(p(x,y)-三z(Q(x,z)A?R(x,z)))…==>Vx3y^z(P(x,y)—(Q(x,z)A改名量詞分配率量詞分配率?R(x,z))]…分配律V?R(x,g(x))]…消取存在量詞從而謂詞公式的子句集是{?P(x,f(x))V(Q(x,g(x),?P(x,f(x))V?R(x,g(x))}例3:設(shè)G=>x'y"zmu『vmw(P(x,y,z)A~Q(u,v,w)),求其子句集解：^x^y^z3u^v=1w(P(x,y,z)A~Q(u,v,w)==>VyVz3u^v3w(P(a,y,z)A?Q(u,v,w)) 消去 x=a(常數(shù))==>^y^z^v3w(P(a,y,z)A?Q(f(y,z),v,w))……消去u=f(y,z)==>VyVzVv(p(a,y,z) A~Q(f(y,z),v,g(y,z,v)))…… 消去w=g(y,z,v),得Skolem標(biāo)準(zhǔn)型從而G的子句集是{P(a,y,z),~Q(f(y,z),v,g(y,z,v)) }例4:將機(jī)器證明"梯形的對角線與上下底構(gòu)成的內(nèi)錯(cuò)角相等"給出邏輯描述，建立子句集合.解：設(shè)梯形頂點(diǎn)依次為a,b,c,d,定義謂詞：T(x,y,u,v):表示xy為上底,uv為下底的梯形.P(x,y,u,v):表示xy||uvE(x,y,z,u,v,w)表示/xyz=/uvw,問題的描述和相應(yīng)的子句集為VxVy^uVv[T(x,y,u,v) -P(x,y,u,v)]… 梯形上下底平行子句：~T(x,y,u,v)VP(x,y,u,v)"xVy?uVv[P(x,y,u,v) -E(x,y,v,u,v,y)]… 平行則內(nèi)錯(cuò)交相等子句：T(a,b,c,d)… 已知子句：T(a,b,c,d)E(a,b,d,c,d,b)…要證明的結(jié)論子句：?E(a,b,d,c,d,b)子句集S為{~T(x,y,u,v)VP(x,y,u,v),~P(x,y,u,v)VE(x,y,v,u,v,y),T(a,b,c,d),~E(a,b,d,c,d,b)}利用后面學(xué)到的替換和合一知識之后可給出證明過程。3.1.4Herbrand理論：證明一個(gè)謂詞公式的不可滿足性是困難的，這是因?yàn)橹^詞中個(gè)體變量的論域 D的任意性，以及解釋的個(gè)數(shù)的無限性。例如：P(x):代表x是偶數(shù)。若x的論域?yàn)镈={2,4,6,8},則P是永真式，是可滿足的；若x的論域?yàn)镈={1,3,5,7},則P是永假式，是不可滿足的；若x的論域?yàn)镈={1,2,5,8},則P的真值與取論域D上的解釋有關(guān)；所以如果對一個(gè)具體的謂詞公式能找到一個(gè)比較簡單的特殊的論域，使得只要在這個(gè)論域上該公式是不可滿足的，便能保證該公式在任一論域上也是不可滿足的。所要建立的Herbrand域(簡稱H域)就具有這樣的性質(zhì)。H域設(shè)G是謂詞公式，定義在論域D上，令H0是G中所出現(xiàn)的常量的集合。若G中沒有常量出現(xiàn)，就任取常量aSD,而規(guī)定H0={a};H=H1U{所有形如f(t1,…tn) 的元素},其中f(t1,...,tn) 是出現(xiàn)于G中的任一函數(shù)符號，而t1...tn是H-1的元素，i=1,2，…。規(guī)定T為G的H域。不難看出H域是直接依賴于G的最多只有可數(shù)個(gè)元素例1:S={P(a),~P(x)VP(f(x))},依H域的定義有：H0={a}H1={a}U{f(a)}={a,f(a)}H2={a,f(a)}U{f(a),f(f(a))}={a,f(a),f(f(a))}H^={a,f⑻a⑻)， …}例2：S={~P(z),P(x)V~Q(y)}依定義有H0={a}a是論域D中的一個(gè)常量H1=H0H2=H1Hp0={a}例3：S={P(f(x),a,g(y),b)}依定義有H0={a,b}H1={a,b}U{f(a),f(b),g(a),g(b)}={a,b,f(a),f(b),g(a),g(b)}H2={a,b,f(a),f(b) ,g(a),g(b)}U{f(a),f(b),f(f(a)),f(f(b)),f(g(a)),f(g(b)) ,g(a),g(b),g(f(a)),g(f(TOC\o"1-5"\h\zb)),g(g(a)),g(g(b)) }={a,b,f(a),f(b),g(a),g(b), f(f(a)),f(f(b)),f(g(a)),f(g(b)) ,g(f(a)),g(f(b)),g(g(a)),g(g(b)) }H^o=H0UH1UH2U??…注意：如果在謂詞或子句集中出現(xiàn)函數(shù)形如f(x,a)仍視為f(x,y)的形式，這時(shí)若H0={a,b},則H1中除有f(a,a),f(b,a)外，還出現(xiàn) f(a,b),f(b,b) 。為了討論在H域上子句集S中各謂詞的真值。令集合A={所有形如P(t1,t2,…,tn) 的元素}稱為子句集S(或公式G)的原子集。其中P(t1,t2,...,tn) 是出現(xiàn)于S中的任一謂詞符號，而t1,t2,…tn是S的H域的任意元素。上述例 1中的原子集為 A={P(a),P(f(a)),P(f(f(a))),...}上述例 2中的原子集為 A={P(a),Q(a)}上述例 3中的原子集為 A={P(a,a,a,a),P(a,a,a,b),...}例4:S={P(x)VQ(x),R(f(y))}依定義有 H={a,f(a),f(f(a)),...}原子集A={P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),P(f(f(a))),Q(f(f(a))),R(f(f(a))),...}由于S中謂詞個(gè)數(shù)是有限的，而H是可數(shù)集，必然原子集A也是可數(shù)集。H解釋由子句集S建立H域、原子集A,從而討論S在一般論域D上為真的解釋I,就可依賴于在H域上的某個(gè)解釋I來實(shí)現(xiàn)。也就是子句集S在D上的不可滿足問題轉(zhuǎn)化成了在H上的不可滿足問題。下例說明由I尋求I*的過程例1：S={P(x),Q(y,f(y,a))}則有 H={a,f(a,a),f(a,f(a,a)),f(f(a,a),a),f(f(a,a),f(a,a))...}A={P(a),Q(a,a),P(f(a,a)),Q(a,f(a,a)),Q(f(a,a),a),Q(f(a,a),f(a,a)),...}設(shè)論域D={1,2},解釋I作如下設(shè)定a--f(1,1)--f(1,2)--f(2,1)--f(2,2)2--1 2 2 1---P(1)--P(2)--Q(1,1)--Q(1,2)--Q(2,1)--Q(2,2)T T F T T F于是有---x=1,y=1---x=1,y=2---x=2,y=1---x=2,y=2--S|I=P(1)AQ(1,f(1,2))AP(1)AQ(2,f(2,1))AP(2)AQ(1,f(1,2))AP(2)AQ(2,f(2,2))=T可按下列方法選取相應(yīng)的I*，af2f(a,a)-f(2,2)-1f(a,f(a,a)) -f(2,1)-2f(f(a,a),a) -f(f(2,2),2) -f(1,2)-2f(f(a,a),f(a,a)) -f(1,1)-1P(a)-P(2)-TQ(a,a)-Q(2,2)-FP(f(a,a))-P(1)-TQ(a,f(a,a))-Q(2,1)二TQ(f(a,a),a)-Q(1,2)二TQ(f(a,a),f(a,a)) -Q(2,2)二F于是得到相應(yīng)的H域下的解釋I*為I*={P(a),~Q(a,a),P(f(a,a)),Q(a,f(a,a)),Q(f(a,a),a),~Q(f(a,a),f(a,a)),...}顯然S|I*=T例2求S={P(x)VQ(x),R(f(y))}的H域、原子集A,I解釋。仍然設(shè)D={1，2}，解釋I設(shè)定如下：f⑴--f⑵--P⑴--P⑵--Q⑴--Q(2)--R⑴--R⑵2 2 T F F T F—T于是由S|I=P(1)VQ(1)AR(f(1))AP(1)VQ(1)AR(f(2))AP(2)VQ(2)AR(f(1))FP(2)VQ(2)FR(f(2))=T設(shè)a=1,則相應(yīng)的解釋為：I1*={P(a),~Q(a),~R(a),~P(f(a)),Q(f(a)),R(f(a)),…}S|I1*二T定理：設(shè)I是S的論域D上的解釋，存在對應(yīng)于I的H解釋I*,使得若有S|I二T,必有S|I*=T定理：子句集S是不可滿足的，當(dāng)且僅當(dāng)在所有的S的H解釋下為假。定理：子句集S是不可滿足的當(dāng)且僅當(dāng)對每個(gè)解釋I下，至少有S的某個(gè)子句的某個(gè)基例為假。3語義樹討論S的不可滿足性問題，可將S的所有解釋展現(xiàn)在一棵二叉樹上(這是一個(gè)完全二叉樹)，但要依賴于S的H解釋以及S的原子集A例：對子句集S={P(x)VQ(y),~P(a),~Q(b)}畫出相應(yīng)的語義樹因?yàn)镠={a,b}例如I(N32)={P(a),Q(a),~P(b)},I(N42)={P(a),Q(a),P(b),~Q(b)}例：對子句集S={~P(x)VQ(x),P(f(y)),~Q(f(y))}畫出相應(yīng)的語義樹。因?yàn)镠={a,f(a),f(f(a)),…}A={P(a),Q(a),P(f(a)),Q(f(a)),P(f(f(a))),Q(f(f(a))),…} ,從A出發(fā)可畫出S的語義樹，而且是無限樹。N41 N42N43N44通過對S的完全語義樹的觀察，便可看到S的所有解釋，這棵樹的每個(gè)直到葉結(jié)點(diǎn)的分支都對應(yīng)于S的一個(gè)解釋。特別對有限樹來說，若N是葉結(jié)點(diǎn)，那么I(N)便是S的一個(gè)解釋。為討論S的不可滿足性，就可通過對語義樹每個(gè)分支來計(jì)算S的真值而實(shí)現(xiàn)。有時(shí)并不需要無限延伸某個(gè)分支方能確定在相應(yīng)的解釋下S取假值。例如某個(gè)分支延伸到結(jié)點(diǎn)N時(shí)，I(N)已使S的某個(gè)子句的某一基例為假，就無需對N再做延伸了。此時(shí)就說N是失敗結(jié)點(diǎn)。如果S的完全語義樹的每個(gè)分支上都有一個(gè)失敗結(jié)點(diǎn)，就說它是一個(gè)封閉樹。即S的不可滿足性<=>S的語義樹是封閉語義樹。在上圖中如果畫出完全語義樹的話，則每個(gè)分支上都有失敗結(jié)點(diǎn)，它就是一個(gè)封閉樹，從而證明S是不可滿足的。例如I(N42)={P(a),Q(a),P(f(a)),~Q(f(a))} ,它使得子句集S的一個(gè)子句~Q(f(y))的一個(gè)基例~Q(f(a))為假，從而子句集S為假，所以N42為失敗結(jié)點(diǎn)c同樣的方法可看出每個(gè)分支上都存在失敗結(jié)點(diǎn)。4Herbrand定理定理一：子句集S是不可滿足的，當(dāng)且僅當(dāng)對應(yīng)于S的完全語義樹都是一棵有限的封閉語義樹。定理二：子句集S是不可滿足的，當(dāng)且僅當(dāng)存在不可滿足的有限基例集(即存在有限個(gè)失敗結(jié)點(diǎn))。Herbrand定理給出了一階邏輯的半可判定算法。其中的“半”字指的是有條件下的判定算法，即僅當(dāng)被證定理是成立的，使用該算法方可得證。而當(dāng)被證定理并不成立時(shí)，使用該算法得不出任何結(jié)果。說是算法，那指的是有限步內(nèi)是可實(shí)現(xiàn)的，因?yàn)闊o論從有限的封閉樹觀點(diǎn)，還是從不可滿足的有限基例集觀點(diǎn)都是可判定的，因?yàn)檫@已經(jīng)是有限的命題邏輯問題了。使用Herbrand定理來證明定理或子句集S是不可滿足的，或是尋找有限的封閉樹，或易尋找有限的不可滿足的基例集。一個(gè)具體實(shí)現(xiàn)證明的方法是，對S的H域中的Hi做出基例集Si',即將Hi中的元素依次代入S中的各子句便構(gòu)成Si',若Si'是不可滿足的必有S是不可滿足的，或說相應(yīng)的定理成立。若被證定理成立，必可在有限步內(nèi)證明某個(gè) SNf是不可滿足的。3.1.5謂詞邏輯的歸結(jié)原理(消解原理)替換與合一(回顧謂詞公式、原子公式、文字、子句、項(xiàng)、個(gè)體的概念)命題邏輯中的歸結(jié)原理很簡單，因?yàn)樵诿}邏輯中不含量詞，而謂詞邏輯中含有量詞和個(gè)體變元，這樣尋找互補(bǔ)文字對就變得較復(fù)雜。例：子句C1=P(x)VQ(x),子句C2AP(a)VR(y),如直接比較，似乎找不到互補(bǔ)文字，但如果使用替換辦法，將 C1中的x替換成a,則C1和C2的歸結(jié)式為R(C1,C2)=Q(a)VR(y)即可消去互補(bǔ)文字。從而對謂詞邏輯使用歸結(jié)原理求解問題的步驟是：求出謂詞公式的Skolem標(biāo)準(zhǔn)型--＞謂詞公式的子句集--＞利用替換和合一--＞再利用歸結(jié)原理消去互補(bǔ)對 ＞求解/證明結(jié)論。替換(Substitution):形如{t1/x1,t2/x2，…tn/xn },ti是項(xiàng)，稱為替換的分子，xi是互不相同的個(gè)體變元，稱為替換分母 (i=1,2,...n)，且ti與xi不相同，xi與ti互不循環(huán)出現(xiàn) 。ti/xi表示xi用ti替換。若ti都是不含變元的項(xiàng)(基項(xiàng))，該替換稱為基替換；沒有元素的替換稱為空替換，記作￡,他表示不做替換。例：{a/x,g(y)/y,f(g(b))/z }就是一個(gè)替換(但不是基替換)，而{y/x,f(x)/y}就不是一個(gè)替換，因?yàn)槌霈F(xiàn)了x,y的循環(huán)替換。定義：若E是一個(gè)謂詞公式，0={t1/x1,t2/x2，…tn/xn}是一個(gè)替換，對E施行0替換之后所得的結(jié)果記為 E0,稱為E在0下的例(instance)例：設(shè)謂詞公式G=P(x,y,z),替換0={a/x,f(b)/y,c/z},則G0=P(a,f(b),c)替換的乘積(復(fù)合替換)：設(shè)8={t1/x1,…,tn/xn},X={u1/y1,…,um/ym }是兩個(gè)替換，則將集合{t1入/x1，…,tn入/xn,u1/y1,…,um/ym}中凡符合下列條件的元素刪除ti入/xi 當(dāng) ti入=xi時(shí)ui/yi 當(dāng) yi6{x1,x2，…xn }如此得到的集合仍然是一個(gè)替換，該替換稱為0與入的復(fù)合或乘積，記為0?入例：0={f(y)/x,z/y},入={a/x,b/y,y/z},于是{f(y)入/x,z入/y,a/x,b/y,y/z}={f(b)/x, y/y,a/x,b/y,y/z},根據(jù)替換乘積的定義，刪除若干項(xiàng)之后得。?入={f(b)/x,y/z}替換的復(fù)合運(yùn)算滿足結(jié)合律，但不滿足交換律，即有：(0?入)?u=0?(入?u),0?入？入?0,入?￡=入例：若謂詞公式E=P(x,f(y),z),置換s1={f(x,y)/z,z/w },s2={a/x,b/y,w/z},求(Es1)s2,E(s1?s2),E(s2?s1)解：Es1=P(x,f(y),f(x,y))(Es1)s2=P(a,f(b),f(a,b))si?s2={f(a,b)/z, w/w,a/x,b/y, w/z}={f(a,b)/z,a/x,b/y }s2?s1={a/x,b/y,z/z,f(x,y)/z ,z/w}={a/x,b/y,z/w}E(s1?s2)=P(a,f(b),f(a,b))E(s2?s1)=P(a,f(b),z)可見(Es1)s2=E(s1?s2)?E(s2?si)2合一置換(替換)定義1:設(shè)$={F1,F2,…,Fn}是一個(gè)子句集(F1,F2,…Fn 是文字的析取)，若存在一個(gè)替換8,可使F10=F20=...Fn0,則稱0為S的一個(gè)合一(Unifier),并稱S為可合一的。一個(gè)謂詞公式的合一不唯一。定義2:設(shè)S是謂詞公式子句集S的一個(gè)合一，如果對S的任何一個(gè)合一0,都存在一個(gè)替換入，使得0=S?入則稱S是子句集的最一般合一，簡稱MGU(MostGeneralUnifier)。例：設(shè)子句集S={P(u,y,g(y)),P(x,f(u),z) },S有一個(gè)最一般合一MGUS={u/x,f(u)/y,g(f(u))/z }，對S的任一合一，例如8={a/x,f(a)/y,g(f(a))/z,a/u },存在一個(gè)替換入={a/u},使得0=S?入求MGU勺目的是使子句集中的子句中的文字形式結(jié)構(gòu)完全一致，從而得到消取互補(bǔ)文字的目的。差異集：設(shè)S是一個(gè)非空的具有相同謂詞名的原子公式集，從 S中各公式的左邊第一項(xiàng)開始，同時(shí)向右比較，直到發(fā)現(xiàn)第一個(gè)不都相同的項(xiàng)為止，用這些項(xiàng)的差異部分組成一個(gè)集合，這個(gè)集合就是原子公式子句集的一個(gè)差異集。例：S={P(x,y,z),P(x,f(a),h(b))}，則S的差異集D1={y,f(a)},D2={z,h(b)}求子句集S的最一般合一(MGU)的算法，即合一算法(UnificationAlgorithm):①置k=0,Sk=S,Sk=e;②若Sk是單元素集，則算法停止，MGU=k③求Sk的差異集Dk;④若Dk中存在元素xk和tk,其中xk是變元，其中tk是項(xiàng)且xk不在tk中出現(xiàn)，貝U置Sk+1=Sk?{tk/xk},Sk+1=Sk?{tk/xk},k=k+1,轉(zhuǎn)步驟(2)⑤算法停止，S的MGUP存在(若S是可合一的，算法總是在步②停止)例：求公式集S={P(a,x,f(g(y)),P(z,h(z,u),f(u)) }的MGU解：k=0;S0=S;S0=￡;S0不是單元素集，求得差異集D0={a/z}，其中z是變元，a是項(xiàng)，且z不在a中出現(xiàn)。k=k+i=i有S1=S0?{a/z}=e?{a/z}={a/z},S1=S0-{a/z}={P(a,x,f(g(y)),P(a,h(a,u),f(u)) },S1不是單元素集，求得差異集D1={x,h(a,u)},k=k+1=2;S2=S1-{h(a,u)/x}={a/z,h(a,u)/x},TOC\o"1-5"\h\zS2=S1-{h(a,u)/x}={P(a,h(a,u),f(g(y)),P(a,h(a,u),f(u)) },S2不是單元素集，求得差異集D2={g(y),u},k=k+1=353=52-{g(y)/u}={a/z,h(a,u)/x}?{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))) }是單元素集。根據(jù)求MG算法，MGU=3={a/z,h(a,g(y))/x,g(y)/u }3謂詞邏輯中的歸結(jié)式謂詞邏輯下求兩個(gè)子句的歸結(jié)式，和命題邏輯一樣也是消去互補(bǔ)對，但需考慮變量的合一與置換。設(shè)S={C1,C2}C1,C2是子句集中的子句，L1、L2分別是C1,C2中的文字，并且L1和?L2有最一般合一S,則子句{C1S-L1S}U{C2S-L2S}稱為C1、C2的歸結(jié)式。C1,C2稱為歸結(jié)式的親本子句，L1、L2稱為歸結(jié)文字。例：S={C1,C2}=S={P(x)VQ(x),?P(a)VR(y)}，求C1,C2的歸結(jié)式。L1=P(x),L2=~P(a),則L1與L2的MGUS={a/x},貝U{C1S-L1S}U{C2s-L2S}={P(a)VQ(a)}-{P(a)}U{?P(a)VR(y)}-{?P(a)}={Q(a)VR(y)}即R(C1,C2)=Q(a)VR(y) S={a/x}例：C1={P(x,y)?Q(a)},C2={Q(x)VR(y)}求C1、C2的歸結(jié)式。在對子句進(jìn)行歸結(jié)之前，可先在子句內(nèi)部進(jìn)行化簡。如子句C=P(x)VP(f(y)),令置換S={f(y)/x},則CS=P(f(y))V?Q(f(y)),CS稱為C的因子。R(C1,C2)=R(C1S,C2)=R(C1,C2S)=R(C1S,C2S)定理：謂詞邏輯中的歸結(jié)式是它的親本子句的邏輯結(jié)果 ，即：C1AC2=>(C1S-{L1S})V(C2S-{L2S}),這就是謂詞邏輯的歸結(jié)原理.4利用歸結(jié)原理證明/求解例1:求證:G是A1和A2的邏輯結(jié)果A1:Vx(P(x)-(Q(x)AR(x)))A2:3x(P(x)AS(x))G:3x(S(x)AR(x))證：①?P(x)VQ(x)…從A1變換②?P(y)VR(y)…從A1變換③P(a)④S(a)⑤?S(z)V?R(z)...結(jié)論的否定⑥R(a)…… ②③歸結(jié){a/y}⑦?R(a)…… ④⑤歸結(jié){a/z}⑧口……⑥⑦歸結(jié)得證.例2:設(shè)已知：(1)能閱讀者是識字的；(2)海豚不識字；(3)有些海豚是聰明的；求證：有些聰明者并不能閱讀.證:定義如下命題：?R(x):x能閱讀；?L(x):x識字；?I(x):x是聰明的；?D(x):x是海豚；把已知條件及求證結(jié)論翻譯成謂詞公式為?『x(R(x)-L(x))…已知?正乂①儀)7?L(x))… 已知?3x(D(x)AI(x))…已知?=*x(I(x)A~R(x))… 求證結(jié)論將已知條件，求證結(jié)論的反化成子句集①?R(x)VL(x)②?D(y)V?L(y)③D(a)④I(a)⑤?I(z)VR(z)⑥?L(a)……2,3 歸結(jié){a/y}⑦?R(a)……1,6 歸結(jié){a/x}⑧R(a)……4,5 歸結(jié){a/z}⑨口……7,8 歸結(jié)得證.例3:求解問題,已知：?如果x和y是同班同學(xué)，則x的老師也是y的老師；?王先生是小李的老師；?小李和小張是同班同學(xué)；問小張的老師是誰？解:定義謂詞T(x,y):x是y的老師;C(x,y):x與y是同班同學(xué)；則已知可表示成如下的謂詞公式?VxVyVz((C(x,y)AT(z,x))-T(z,y))?T(wang,Li) wang,Li是常元?C(Li,Zhang)?xT(x,zhang) (先證明zhang的老師是存在的)以上謂詞公式及結(jié)論的反化成子句集如下：①?C(x,y)V?T(z,x)VT(z,y)②T(wang,Li)③C(Li,Zhang)T(u,zhang)(D~C(Li,y)VT(wang,y)……1,2 歸結(jié)，{wang/z,Li/x}⑥?C(Li,zhang) 4,5歸結(jié)，{wang/u,zhang/y}⑦口……3,6 歸結(jié)說明zhang的老師存在 .為了求解用一個(gè)重言式代替④T(u,zhang)VT(u,zhang)…… 用重言式代替結(jié)論的否定，重言式恒為真(D~C(Li,y)VT(wang,y)……1,2 歸結(jié)，{wang/z,Li/x}⑥?C(Li,zhang)VT(wang,zhang) 4,5歸結(jié)，{wang/u,zhang/y}⑦T(wang,zhang) 3,6歸結(jié)得結(jié)果:張的老師是王先生 .也可用輔助謂詞ANS(u)④?T(u,zhang)VANS(u)…… 用輔助謂詞ANS(u)(D~C(Li,y)VT(wang,y)……1,2 歸結(jié)，{wang/z,Li/x}⑥?C(Li,zhang)VANS(wang).….4,5 歸結(jié)，{wang/u,zhang/y}⑦口VANS(wang)..…3,6歸結(jié)得結(jié)果:張的老師是王先生 .3.1.6歸結(jié)過程的控制策略刪除策略概念:?設(shè)C1,C2是兩個(gè)子句，若存在替換0,使得C10包含在C2中，則稱子句C1類含C2。如：P(x)類含P(a)VQ(y),取0={a/x},或者說P(x)把P(a)VQ(y)歸類P(a,x)VP(y,b)類含P(a,b),取8={b/x,a/y}?純文字：在子句集中無補(bǔ)的文字。如下列子句集{P(x)VQ(x,y)VR(x),?P(a)VQ(u,v)}中的文字R(x)就是一個(gè)純文字。在歸結(jié)的過程中刪除以下子句?含有純文字的子句 ;?含有永真式的子句 ;?子句集中被別的子句類含的子句;刪除含有純文字的子句，是因?yàn)樵跉w結(jié)過程中純文字永遠(yuǎn)不會消去，因而用包含它的子句進(jìn)行歸結(jié)不可能得到空子句。刪除永真式是因?yàn)橛勒媸綄ψ泳浼牟豢蓾M足性不起任何作用。刪除被類含的子句是因?yàn)楸活惡淖泳涫穷惡淖泳涞倪壿嬏N(yùn)含，故它是多余的。如P(a,x)VP(y,b)類含P(a,b),則可將P(a,b)刪除。例：利用刪除策略對下列子句集進(jìn)行歸結(jié)(1)PVQ..已知(2)?PVQ..已知(3)PV?Q…已知(4)?PV?Q…已知(5)Q...(1)(2)歸結(jié),此時(shí)可將子句(1)(2)刪除,因它們被子句(5)類含,此時(shí)歸結(jié)只在3,4,5之間進(jìn)行(6)?Q...(3)(4)歸結(jié)□...(5)(6)歸結(jié)例:利用刪除策略對下列子句集進(jìn)行歸結(jié)(1)P(x)VQ(x)V-R(x)...已知(2)?Q(a)…已知(3)?R(a)VQ(a)…已知(4)P(y)...已知(5)?P(z)VR⑵…已知，子句(4)類含(1),所以將子句(1)刪除(6)?R⑻…(2)(3)歸結(jié)，此時(shí)子句⑶可刪除，因?yàn)樗?6)類含(7)?P(a)...(5)(6)歸結(jié){a/z},此時(shí)子句⑸可刪除，因?yàn)樗虎祟惡凇?4)(7)歸結(jié){a/y}刪除策略是及早刪除無用子句,縮小搜索規(guī)模.刪除策略是完備的,即對不可滿足的子句集 ,使用刪除策略進(jìn)行歸結(jié)必能導(dǎo)出空子句.語義歸結(jié)一種語義歸結(jié)是把子句S分成兩部分，約定每部分內(nèi)的子句間不允許做歸結(jié)。還引入了文字次序，約定歸結(jié)時(shí)其中的一個(gè)子句的被歸結(jié)文字只能是該子句中“最大”的文字例：子句集S={~PV~QVR,PVR,QVR,~R}先規(guī)定S中文字的出現(xiàn)順序如依次為P,QR,再選取S的一個(gè)解釋如令I(lǐng)={~P，~Q，~R}用它將S分成兩部分。在解釋I下為假的子句放入S1'中，在解釋I下為真的子句放入 S2'中，于是有：S1'={PVR,QVR}S2'={~PV~QVR,~R}規(guī)定在Si′內(nèi)部的子句不允許歸結(jié)，S1'與S2'子句間的歸結(jié)必須是S1'中的最大文字方可進(jìn)行。這樣所得的歸結(jié)式仍按解釋 I放入S1'或S2'中。歸結(jié)過程：~PV~QVR 按順序排列，屬于S2'PVR 按順序排列，屬于S1'QVR 按順序排列，屬于S1'~R 按順序排列，屬于 S2'~QVR (2) 和(1)歸結(jié)，因?yàn)檫x取S1'最大文字方向~PVR (3) 和(1)歸結(jié)，因?yàn)檫x取S1'最大文字方向7)R (2) 和(6)歸結(jié)□ (7)和(4)歸結(jié)明顯地減少了歸結(jié)次數(shù)，阻止了(1)與( 4)歸結(jié)(因?yàn)樗鼈兪?S2'內(nèi)部子句)，也阻止了(2)( 4)歸結(jié)(因?yàn)椴皇亲畲笪淖址较?另一種語義歸結(jié)稱為支持集策略對子句集S每次歸結(jié)時(shí)至少要有一個(gè)是要證明的目標(biāo)公式否定的子句或其后裔.這里的要證明的目標(biāo)公式的否定形式所形成的子句集即為支持集 T,很顯然S-T是可滿足的.所以也可這樣理解支持集策略：每次歸結(jié)時(shí),至少有一個(gè)子句來自支持集T或由T導(dǎo)出的歸結(jié)式.例：子句集合S=?I(x)VR(x),I(a),?R(y)V?L(y),L(a)},其中I(x)A~R(x)是要證明的結(jié)論，其否定形式是子句?I(x)VR(x).利用支持集策略歸結(jié)如下：(1)?I(x)VR(x) 支持集T⑵I(a)(3)R(y)V?L(y)(4)L(a)(5)R(a) 1,2 歸結(jié){a/x}(6)?L(a) 3,5歸結(jié){a/y}□ ⑷(6) 歸結(jié)支持集策略是完備的..線性歸結(jié)策略在歸結(jié)過程中，除第一次歸結(jié)可用給定的子句集S中子句(該子句稱為頂子句)外，其后各次歸結(jié)則至少要有一個(gè)親本子句是上次歸結(jié)的結(jié)果 .線性歸結(jié)可用一個(gè)歸結(jié)演繹樹加以表示，例如上例中的歸結(jié)過程：線性歸結(jié)策略是完備的.輸入歸結(jié)策略每次參加歸結(jié)的兩個(gè)親本子句，必須至少有一個(gè)子句是初始子句集S中的子句。輸入歸結(jié)策略是不完備的。例如子句集S={PVQ,?PVQPV?Q?PV?Q是不可滿足的，但用輸入歸結(jié)策略不能導(dǎo)出空子句.單元?dú)w結(jié)策略每次歸結(jié)都有一個(gè)子句是單元(只含一個(gè)文字即原子或其否定)子句或單元的因子時(shí)的歸結(jié)稱作單元?dú)w結(jié)。單元?dú)w結(jié)也是不完備的。3.2不確定性推理概述不確定性推理知識庫是人工智能的核心，而知識庫中的知識既有規(guī)律性的一般原理，又有大量的不完全的專家知識，即知識帶有 模糊性、隨機(jī)性、不可靠或不知道不確定因素。世界上幾乎沒有什么事情是完全確定的。不確定性推理即是通過某種推理得到問題的精確判斷。(1)不確定性問題的代數(shù)模型一個(gè)問題的代數(shù)模型由論域、運(yùn)算和公理 組成。建立不確定性問題模型必須說明不確定知識的表示 、計(jì)算、與語義解釋。?表示問題：指用什么方法描述不確定性，通常有數(shù)值和非數(shù)值的語義表示方法。數(shù)值表示便于計(jì)算，比較，再考慮到定性的非數(shù)值描述才能較好的解決不確定性問題。例如對規(guī)則A->B(即A真能