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

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

PrinciplesandApplicationofArtificialIntelligence課程簡(jiǎn)介本課程主要講述人工智能的基本概念、基本方法，會(huì)用搜索算法、推理方法和機(jī)器學(xué)習(xí)求解簡(jiǎn)單問(wèn)題，如證明定理、機(jī)器推理、建造簡(jiǎn)單的專家系統(tǒng)，自然語(yǔ)言分析和理解。要求了解人工智能的提出，幾種智能觀，人工智能重要的研究領(lǐng)域，以及人工智能求解問(wèn)題的方法與傳統(tǒng)的數(shù)學(xué)方法的不同；掌握啟發(fā)式搜索概念，會(huì)用搜索方法求解簡(jiǎn)單問(wèn)題掌握歸結(jié)推理方法，會(huì)用歸結(jié)法證明定理，求解問(wèn)題。掌握一種不確定推理方法，會(huì)建造帶有不確定推理的專家系統(tǒng)。了解其它的推理方法；掌握知識(shí)的表示方法，會(huì)用來(lái)表達(dá)某一具體的場(chǎng)景；掌握機(jī)器學(xué)習(xí)概念和學(xué)習(xí)模型，會(huì)用實(shí)例學(xué)習(xí)方法進(jìn)行學(xué)習(xí)，了解數(shù)據(jù)挖掘的過(guò)程，會(huì)用關(guān)聯(lián)規(guī)則挖掘算法做數(shù)據(jù)挖掘；掌握自然語(yǔ)言理解的過(guò)程，會(huì)用基本的切分和語(yǔ)法分析方法做自然語(yǔ)句分析；理解神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)智能的另一種觀點(diǎn)。掌握BP神經(jīng)網(wǎng)的工作原理，會(huì)用來(lái)求解（如識(shí)別）問(wèn)題；了解遺傳算法（GA）概念及如何使用遺傳算法參考資料：《人工智能原理與應(yīng)用》，張仰森，高等教育出版社《人工智能》，蔡自興《人工智能原理》，石純一黃昌寧王家欽編著，清華大學(xué)出版社《人工智能》（上下冊(cè)），陸汝鈴編著，科學(xué)出版社，1996《人工智能與知識(shí)工程》，田盛豐、黃厚寬，中國(guó)鐵道出版社，1999《高級(jí)人工智能》，史忠植，科學(xué)出版社，1998《人工智能基礎(chǔ)》，高濟(jì)、朱森良、何欽銘，高等教育出版社，2002第一章人工智能概述1.1人工智能的起源與發(fā)展計(jì)算機(jī)所能處理對(duì)象的改變：純粹數(shù)值計(jì)算→非數(shù)值計(jì)算（自然語(yǔ)言理解、圖象語(yǔ)音識(shí)別、專家系統(tǒng)、機(jī)器博弈系統(tǒng)等等符號(hào)知識(shí)處理）試探性搜索、啟發(fā)式搜索、不確定性推理方法更符合人類思維過(guò)程。也就是說(shuō)在解決這類問(wèn)題時(shí)，沒(méi)有算法解或即使有算法解但在當(dāng)今計(jì)算技術(shù)不能實(shí)現(xiàn)。對(duì)這類問(wèn)題可行的解決方法是搜索、試探，加上經(jīng)驗(yàn)的啟發(fā)式知識(shí)。這是一種來(lái)自專門領(lǐng)域的經(jīng)驗(yàn)知識(shí)，限于特定場(chǎng)合，經(jīng)常會(huì)取得成功但又不能保證必然成功，常能求得有關(guān)問(wèn)題的滿意解答。醫(yī)生一定能根據(jù)病人的癥狀診斷出是何種疾病嗎？我們能用傳統(tǒng)的算法設(shè)計(jì)一個(gè)程序進(jìn)行疾病診斷嗎？能用傳統(tǒng)的算法設(shè)計(jì)一個(gè)程序能理解自然語(yǔ)言所組成的文檔的含義嗎？以上原因促使人工智能學(xué)科的誕生。主要經(jīng)歷了以下幾個(gè)階段：孕育期（1956年以前）——從理論、技術(shù)和物質(zhì)上奠定基礎(chǔ)成長(zhǎng)期（1956－1972）——邏輯推理機(jī)程序、跳棋程序、通用問(wèn)題求解（GPS：GeneralProblemSolver）、人工智能程序設(shè)計(jì)語(yǔ)言LISP/PROLOG發(fā)展期（1972－）——知識(shí)工程、專家系統(tǒng)（MYCIN，探礦系統(tǒng)）學(xué)習(xí)期1.2什么是人工智能1.什么是人類智能？有何特點(diǎn)？計(jì)算機(jī)到底能不能有人類智能？英國(guó)數(shù)學(xué)家Turing于1950提出的著名的Turing實(shí)驗(yàn)。識(shí)別、推理、聯(lián)想、自學(xué)習(xí)...（人腦的智能很復(fù)雜?。┯?jì)算機(jī)到底能不能有人類智能，至今沒(méi)有完整的論證（人工智能是一門正在探索和發(fā)展的學(xué)科，至今還沒(méi)有完全形成完整的理論體系。目前人工智能與人腦的智能還相差很遠(yuǎn)）2.什么是人工智能？人工智能簡(jiǎn)稱為AI（ArtificialIntelligence）,是研究如何制造出智能機(jī)器或智能系統(tǒng)，來(lái)模擬人類智能活動(dòng)、延伸人類智能的學(xué)科。已實(shí)現(xiàn)的人工智能系統(tǒng)：第一個(gè)人工智能專家系統(tǒng)DENDRAL,能根據(jù)有機(jī)化合物的質(zhì)譜數(shù)據(jù)，推斷出給有機(jī)化合物的分子結(jié)構(gòu)，該系統(tǒng)得到甚至超過(guò)化學(xué)專家水平。該系統(tǒng)是由Stanford大學(xué)的Feigenbaum領(lǐng)導(dǎo)研制成功的。醫(yī)療專家系統(tǒng)MYCIN探礦專家系統(tǒng)PROSPECTOR1995年美國(guó)智能機(jī)器人駕駛汽車以55km/h速度從東部一直開到西部（機(jī)器視覺(jué)）1997年國(guó)際象棋大師卡斯帕羅夫與IBM深藍(lán)巨型機(jī)上的博弈系統(tǒng)對(duì)弈自然語(yǔ)言理解系統(tǒng)機(jī)器翻譯系統(tǒng)機(jī)器證明系統(tǒng)（證明了“四色問(wèn)題”、數(shù)學(xué)中的定理）1.3AI的研究途徑、方法、不同學(xué)派1．目標(biāo)：近期目標(biāo)：使機(jī)器更聰明遠(yuǎn)期目標(biāo)：探討研制智能機(jī)2.方法、途徑仿生學(xué)方法：對(duì)人腦思維進(jìn)行生理學(xué)模擬，通過(guò)微觀方法直接模擬人腦和神經(jīng)系統(tǒng)的結(jié)構(gòu)功能計(jì)算機(jī)方法：利用計(jì)算機(jī)科學(xué)的觀點(diǎn)，從宏觀上模擬人的智能活動(dòng)數(shù)學(xué)方法：建立數(shù)學(xué)模型，利用算法求解問(wèn)題心理學(xué)方法：建立心理學(xué)模型，利用啟發(fā)式程序求解問(wèn)題3．人工智能研究的各種學(xué)派及其理論功能模擬，符號(hào)演繹模擬人腦的邏輯思維，將問(wèn)題和知識(shí)表示成某種邏輯網(wǎng)絡(luò)，采用符號(hào)推演的方法，實(shí)現(xiàn)搜索、推理、學(xué)習(xí)等功能。這種方法目前還在使用，人工智能研究中的很多成果都是用該方法取得的，如定理證明，自動(dòng)推理，專家系統(tǒng)、博弈系統(tǒng)等。采用這種方法的研究者稱為心理學(xué)派或邏輯學(xué)派或符號(hào)主義，代表人物是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ò)模型來(lái)存儲(chǔ)信息和知識(shí)，用神經(jīng)計(jì)算（數(shù)值計(jì)算）的方法實(shí)現(xiàn)自學(xué)習(xí)、聯(lián)想、識(shí)別和推理功能。神經(jīng)網(wǎng)絡(luò)具有高度的并行分布性。該研究方法適于實(shí)現(xiàn)圖象、聲音信息識(shí)別。采用這種研究途徑稱為生理學(xué)派或連接主義，代表人物是Newell行為模擬，控制進(jìn)化這種方法模擬人在控制過(guò)程中的智能活動(dòng)和行為特性（自尋優(yōu)，自適應(yīng)，自學(xué)習(xí)），強(qiáng)調(diào)“現(xiàn)場(chǎng)AI”（situatedAI）即智能系統(tǒng)或智能機(jī)器能與環(huán)境交互，能對(duì)環(huán)境進(jìn)行感知從而表現(xiàn)出智能行為，也就是說(shuō)智能行為不需要知識(shí)從而與“符號(hào)主義”相悖。這種方法的研究者稱為行為主義、進(jìn)化主義或控制論學(xué)派。代表人物是MIT的Brooks教授。人工智能是引起爭(zhēng)議最多的學(xué)科之一,因而各種研究學(xué)派在發(fā)展的過(guò)程都經(jīng)歷了許多挫折.通過(guò)什么途徑有效地實(shí)現(xiàn)智能(如符號(hào)演繹推理,知識(shí)工程,神經(jīng)網(wǎng)絡(luò)計(jì)算,圖搜索技術(shù),不確定推理等).人工智能的研究范圍問(wèn)題,一般認(rèn)為包括:知識(shí)表示,推理技術(shù),自然語(yǔ)言理解,知識(shí)工程,計(jì)算機(jī)視覺(jué)等許多方面.引起爭(zhēng)議的原因,第一是由于邊界不分明,某些分支與數(shù)學(xué)有交界(如定理證明,謂詞邏輯),或與語(yǔ)言學(xué)有交界(如自然語(yǔ)言理解),或與心理學(xué)有交界(如認(rèn)知模型),或與電子學(xué)機(jī)械學(xué)有交界(如計(jì)算機(jī)視覺(jué),機(jī)器人).第二是由于科學(xué)的發(fā)展,各分支的內(nèi)容在不斷的變化.第三,隨著研究工作的深入,一些傳統(tǒng)的觀念在發(fā)生變化,例如在歷史上認(rèn)為數(shù)值計(jì)算發(fā)展到符號(hào)演算是AI的一個(gè)重要特征,但在近年的研究中,計(jì)算機(jī)視覺(jué)和機(jī)器人學(xué)的研究中又回到了數(shù)值計(jì)算的現(xiàn)象,提高了數(shù)學(xué)在人工智能研究中的地位.1.4AI的研究領(lǐng)域搜索算法：狀態(tài)空間圖、博弈樹搜索推理方法：歸結(jié)推理、不確定性推理自然語(yǔ)言理解：不僅能識(shí)別文字而且能理解文本含義的機(jī)器系統(tǒng)模式識(shí)別（圖象與語(yǔ)音識(shí)別）知識(shí)工程（知識(shí)獲取、知識(shí)表示、知識(shí)數(shù)據(jù)庫(kù)、知識(shí)運(yùn)用等一系列知識(shí)處理技術(shù)，是以知識(shí)為中心來(lái)組織智能系統(tǒng)）神經(jīng)網(wǎng)絡(luò)技術(shù)專家系統(tǒng)機(jī)器人1.5人工智能求解方法的特點(diǎn)AI研究的是以符號(hào)表示的知識(shí)而不是數(shù)值數(shù)據(jù)為研究對(duì)象；AI中采用的啟發(fā)式搜索算法（HeuristicResearchAlgorithm）而不是常規(guī)的算法（Algorithm）控制結(jié)構(gòu)與知識(shí)是分離的允許出現(xiàn)不正確的答案1.6人類智能和人工智能1．人類智能特性 感知能力思維能力反應(yīng)能力2．人工智能特性 機(jī)器感知能力機(jī)器思維能力（知識(shí)表示）機(jī)器行為能力第二章知識(shí)表示2.1知識(shí)及其表示1.知識(shí)的概念Feigenbaum認(rèn)為知識(shí)是經(jīng)過(guò)削減、塑造、解釋和轉(zhuǎn)換的信息。簡(jiǎn)單地說(shuō)，知識(shí)是經(jīng)過(guò)加工的信息。Bernstein說(shuō)知識(shí)是特定領(lǐng)域的描述、關(guān)系和過(guò)程組成。Hayes-Roth認(rèn)為知識(shí)是事實(shí)、信念和啟發(fā)式規(guī)則。知識(shí)可從（范圍，目的，有效性）加以三維描述。其中知識(shí)的范圍是由具體到一般，知識(shí)的目的是由說(shuō)明到指定，知識(shí)的有效性是由確定到不確定。例如“為了證明A→B，只需證明A∧~B是不可滿足的”這種知識(shí)是一般性、指示性、確定性的。而像“桌子有四條腿”這種知識(shí)是具體的、說(shuō)明性、不確定性。知識(shí)表示是研究用機(jī)器表示知識(shí)的可行性、有效性的一般方法，是一種數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)的統(tǒng)一體，既考慮知識(shí)的存儲(chǔ)又考慮知識(shí)的使用。知識(shí)表示可看成是一組描述事物的約定，以把人類知識(shí)表示成機(jī)器能處理的數(shù)據(jù)結(jié)構(gòu)。2.人工智能系統(tǒng)所關(guān)心的知識(shí)一個(gè)智能程序高水平的運(yùn)行需要有關(guān)的事實(shí)知識(shí)、規(guī)則知識(shí)、控制知識(shí)和元知識(shí)。事實(shí)：是有關(guān)問(wèn)題環(huán)境的一些事物的知識(shí)，常以“...是...”的形式出現(xiàn)。如事物的分類、屬性、事物間關(guān)系、科學(xué)事實(shí)、客觀事實(shí)等，在知識(shí)庫(kù)中屬于低層的知識(shí)。如雪是白色的、鳥有翅膀、張三李四是好朋友。規(guī)則：是有關(guān)問(wèn)題中與事物的行動(dòng)、動(dòng)作相聯(lián)系的因果關(guān)系知識(shí)，是動(dòng)態(tài)的，常以“如果...那么...”形式出現(xiàn)。特別是啟發(fā)式規(guī)則是屬于專家提供的專門經(jīng)驗(yàn)知識(shí)，這種知識(shí)雖無(wú)嚴(yán)格解釋但很有用處?？刂疲菏怯嘘P(guān)問(wèn)題的求解步驟，技巧性知識(shí)，告訴怎么做一件事。也包括當(dāng)有多個(gè)動(dòng)作同時(shí)被激活時(shí)應(yīng)選哪一個(gè)動(dòng)作來(lái)執(zhí)行的知識(shí)。元知識(shí)：是有關(guān)知識(shí)的知識(shí)，是知識(shí)庫(kù)中的高層知識(shí)。包括怎樣使用規(guī)則、解釋規(guī)則、校驗(yàn)規(guī)則、解釋程序結(jié)構(gòu)等知識(shí)。2.2邏輯表示法對(duì)知識(shí)通過(guò)引入謂詞、函數(shù)來(lái)加以形式描述，獲得有關(guān)的邏輯公式，進(jìn)而以機(jī)器內(nèi)部代碼表示。設(shè)在一個(gè)房間里，有一個(gè)機(jī)器人ROBOT，一個(gè)壁室ALCOVE，一個(gè)積木塊BOX，兩個(gè)桌子A和B。機(jī)器人可把積木塊BOX從一種狀態(tài)變換成另一種狀態(tài)。引入謂詞：TABLE（A）表示A是桌子EMPTYHANDED（ROBOT）表示機(jī)器人雙手是空的AT（ROBOT，A）表示機(jī)器人在A旁HOLDS（ROBOT，BOX）表示機(jī)器人拿著積木塊ON（BOX，A）表積木塊BOX在A上2.3產(chǎn)生式表示法產(chǎn)生式是一種知識(shí)表達(dá)方法，具有和Turing機(jī)一樣的表達(dá)能力。2.3.1事實(shí)與規(guī)則的表示事實(shí)可看成是斷言一個(gè)語(yǔ)言變量的值或是多個(gè)語(yǔ)言變量間的關(guān)系的陳述句，語(yǔ)言變量的值或語(yǔ)言變量間的關(guān)系可以是一個(gè)詞。不一定是數(shù)字。如雪是白色的，其中雪是語(yǔ)言變量，其值是白色的。John喜歡Mary，其中John、Mary是兩個(gè)語(yǔ)言變量，兩者的關(guān)系值是喜歡。一般使用三元組（對(duì)象，屬性，值）或（關(guān)系，對(duì)象1，對(duì)象2）來(lái)表示事實(shí)，其中對(duì)象就是語(yǔ)言變量，若考慮不確定性就成了四元組表示（增加可信度）。這種表示的機(jī)器內(nèi)部實(shí)現(xiàn)就是一個(gè)表。如事實(shí)“老李年齡是35歲”，便寫成（Lee,age,35）事實(shí)“老李、老張是朋友”，可寫成（friend,Lee,Zhang）對(duì)于規(guī)則是表示事物間的因果關(guān)系，以下列形式表示：condition->actioncondition作為前件或模式，而action稱作動(dòng)作或后件或結(jié)論。前件部分常是一些事實(shí)Ai的合取，而結(jié)論常是某一事實(shí)B，如考慮不確定性，需另附可信度度量值。2.3.2產(chǎn)生式系統(tǒng)的組成和推理多數(shù)較為簡(jiǎn)單的專家系統(tǒng)（ExpertSystem）都是以產(chǎn)生式表示知識(shí)的，相應(yīng)的系統(tǒng)稱作產(chǎn)生式系統(tǒng)。產(chǎn)生式系統(tǒng)，由知識(shí)庫(kù)和推理機(jī)兩部分組成。其中知識(shí)庫(kù)由規(guī)則庫(kù)和數(shù)據(jù)庫(kù)組成。規(guī)則庫(kù)是產(chǎn)生式規(guī)則的集合，數(shù)據(jù)庫(kù)是事實(shí)的集合。規(guī)則是以產(chǎn)生式表示的。規(guī)則集蘊(yùn)涵著將問(wèn)題從初始狀態(tài)轉(zhuǎn)換解狀態(tài)的那些變換規(guī)則，規(guī)則庫(kù)是專家系統(tǒng)的核心。規(guī)則可表成與或樹形式，基于數(shù)據(jù)庫(kù)中的事實(shí)對(duì)這與或樹的求值過(guò)程就是推理。數(shù)據(jù)庫(kù)中存放著初始事實(shí)、外部數(shù)據(jù)庫(kù)輸入的事實(shí)、中間結(jié)果事實(shí)和最后結(jié)果事實(shí)。推理機(jī)是一個(gè)程序，控制協(xié)調(diào)規(guī)則庫(kù)與數(shù)據(jù)庫(kù)的運(yùn)行，包含推理方式和控制策略。產(chǎn)生式系統(tǒng)的推理方式有正向推理、反向推理和雙向推理正向推理：從已知事實(shí)出發(fā)，通過(guò)規(guī)則庫(kù)求得結(jié)論，或稱數(shù)據(jù)驅(qū)動(dòng)方式。推理過(guò)程是規(guī)則集中的規(guī)則前件與數(shù)據(jù)庫(kù)中的事實(shí)進(jìn)行匹配，得匹配的規(guī)則集合。從匹配規(guī)則集合中選擇一條規(guī)則作為使用規(guī)則。執(zhí)行使用規(guī)則的后件。將該使用規(guī)則的后件送入數(shù)據(jù)庫(kù)中重復(fù)這個(gè)過(guò)程直至達(dá)到目標(biāo)具體說(shuō)如數(shù)據(jù)庫(kù)中含有事實(shí)A，而規(guī)則庫(kù)中有規(guī)則A->B，那么這條規(guī)則便是匹配規(guī)則，進(jìn)而將后件B送入數(shù)據(jù)庫(kù)中。這樣可不斷擴(kuò)大數(shù)據(jù)庫(kù)直至包含目標(biāo)便成功結(jié)束。如有多條匹配規(guī)則需從中選一條作為使用規(guī)則，不同的選擇方法直接影響著求解效率，選規(guī)則的問(wèn)題稱作控制策略。正向推理會(huì)得出一些與目標(biāo)無(wú)直接關(guān)系的事實(shí)，是有浪費(fèi)的。反向推理：從目標(biāo)（作為假設(shè)）出發(fā)，反向使用規(guī)則，求得已知事實(shí)，或稱目標(biāo)驅(qū)動(dòng)方式，推理過(guò)程是：規(guī)則集中的規(guī)則后件與目標(biāo)事實(shí)進(jìn)行匹配，得匹配的規(guī)則集合；從匹配的規(guī)則集合中選擇一條規(guī)則作為使用規(guī)則；將使用規(guī)則的前件作為子目標(biāo)；重復(fù)這個(gè)過(guò)程直至各子目標(biāo)均為已知事實(shí)成功結(jié)束；如果目標(biāo)明確，使用反向推理方式效率較高。雙向推理：同時(shí)使用正向推理又使用反向推理。2.3.3產(chǎn)生式表示的特點(diǎn)產(chǎn)生式表示格式固定，形式單一，規(guī)則（知識(shí)單位）間相互較為獨(dú)立，沒(méi)有直接關(guān)系使知識(shí)庫(kù)的建立較為容易，處理較為簡(jiǎn)單的問(wèn)題是可取的。另外推理方式單純，也沒(méi)有復(fù)雜計(jì)算。特別是知識(shí)庫(kù)與推理機(jī)是分離的，這種結(jié)構(gòu)給知識(shí)的修改帶來(lái)方便，無(wú)須修改程序，對(duì)系統(tǒng)的推理路徑也容易作出解釋。所以，產(chǎn)生式表示知識(shí)常作為構(gòu)造專家系統(tǒng)的第一選擇的知識(shí)表示方法。2.4語(yǔ)義網(wǎng)絡(luò)表示法邏輯表示法和產(chǎn)生式表示法常用于表示有關(guān)論域中各個(gè)不同狀態(tài)間的關(guān)系，然而用于表示一個(gè)事物同其各個(gè)部分間的分類知識(shí)就不方便了。槽（slot）與填槽表示方法便于表示這種分類知識(shí)。語(yǔ)義網(wǎng)絡(luò)和框架表示方法就屬于其中的兩種。2.4.1語(yǔ)義網(wǎng)絡(luò)的結(jié)構(gòu)語(yǔ)義網(wǎng)絡(luò)是對(duì)知識(shí)的有向圖表示方法。一個(gè)語(yǔ)義網(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”，可表示成：這樣事實(shí)與規(guī)則的表示是相同的，區(qū)別僅是弧上的標(biāo)注有別。從邏輯表示法來(lái)看，一個(gè)語(yǔ)義網(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對(duì)應(yīng)于結(jié)點(diǎn)1、結(jié)點(diǎn)2，而弧及其上標(biāo)注的結(jié)點(diǎn)1與結(jié)點(diǎn)2的關(guān)系由謂詞P來(lái)體現(xiàn)。語(yǔ)義網(wǎng)絡(luò)視作一種知識(shí)的單位，人腦的記憶是由存儲(chǔ)了大量的語(yǔ)義網(wǎng)絡(luò)來(lái)體現(xiàn)的。而產(chǎn)生式表示法是以一條產(chǎn)生式規(guī)則作為知識(shí)的單位，而各條產(chǎn)生式規(guī)則沒(méi)有直接的聯(lián)系。結(jié)點(diǎn)間的關(guān)系有isa，a-part-of，is型(1)ISA鏈用來(lái)表示具體-抽象關(guān)系，或說(shuō)表示一種隸屬關(guān)系，體現(xiàn)某種層次分類。特點(diǎn)是具體層結(jié)點(diǎn)可繼承抽象層結(jié)點(diǎn)的屬性。(2)a-part-of鏈用來(lái)表示部分-全體關(guān)系，或說(shuō)表示包含關(guān)系。特點(diǎn)是part-of關(guān)系下各層結(jié)點(diǎn)的屬性可能是很不相同的。(3)is鏈用于表示一個(gè)結(jié)點(diǎn)是另一個(gè)結(jié)點(diǎn)的屬性例：蘋果的語(yǔ)義網(wǎng)絡(luò)2.4.2語(yǔ)義網(wǎng)絡(luò)表示下的推理語(yǔ)義網(wǎng)絡(luò)表示下的推理方法不像邏輯表示法和產(chǎn)生式表示法的推理方法那樣明了。語(yǔ)義網(wǎng)絡(luò)表示法是依匹配和繼承來(lái)進(jìn)行推理的。最簡(jiǎn)單的isa關(guān)系下的推理是直接繼承，如：也可以將語(yǔ)義網(wǎng)絡(luò)引入邏輯含義，表示出∧，∨，～關(guān)系，便可以使用歸結(jié)推理法。還有人將語(yǔ)義網(wǎng)絡(luò)中的結(jié)點(diǎn)看成有限自動(dòng)機(jī)（DFA），為尋求幾個(gè)概念間的關(guān)系，起動(dòng)相應(yīng)的自動(dòng)機(jī)，如有回合點(diǎn)便可求得解答。2.5框架表示法2.5.1框架理論1975年Minsky的論文“Aframeworkforrespresentingknowledge”中提出了框架理論。其基本觀點(diǎn)是人腦已存儲(chǔ)有大量典型情景，當(dāng)人面臨新的情景時(shí)，就從記憶中選擇一個(gè)稱為框架的基本知識(shí)結(jié)構(gòu)，這個(gè)框架是以前記憶的一個(gè)知識(shí)空框，而其具體內(nèi)容依新的情景而改變，對(duì)這空框的細(xì)節(jié)加工修改和補(bǔ)充，形成對(duì)新情景的認(rèn)識(shí)又記憶于人腦中?？蚣芾碚搶⒖蚣芤曌鞯闹R(shí)單位，將一組有關(guān)的框架連接起來(lái)便形成框架系統(tǒng)。系統(tǒng)中不同框架可以有共同結(jié)點(diǎn)，系統(tǒng)的行為由系統(tǒng)內(nèi)框架的變化來(lái)表現(xiàn)的。推理過(guò)程是由框架間的協(xié)調(diào)來(lái)完成的?？蚣鼙硎痉ㄊ且环N適應(yīng)性強(qiáng)、概括性高、結(jié)構(gòu)化良好、推理方式靈活又能把陳述性知識(shí)與過(guò)程性知識(shí)相結(jié)合的知識(shí)表示方法。2.5.2框架結(jié)構(gòu)框架是由若干結(jié)點(diǎn)和關(guān)系（統(tǒng)稱為槽slot）構(gòu)成的網(wǎng)絡(luò)。是語(yǔ)義網(wǎng)絡(luò)一般化形式化的一種結(jié)構(gòu)，同語(yǔ)義網(wǎng)絡(luò)沒(méi)有本質(zhì)區(qū)別。將語(yǔ)義網(wǎng)絡(luò)中結(jié)點(diǎn)間弧上的標(biāo)注也放入槽內(nèi)就成了框架表示法?？蚣苁潜硎灸骋活惽榫暗慕Y(jié)構(gòu)化的一種數(shù)據(jù)結(jié)構(gòu)?？蚣苡煽蚣苊鸵恍┎郏╯lot）組成，每個(gè)槽有一些值，槽值可以是邏輯的、數(shù)字的，可以是程序、條件、默認(rèn)值或是一個(gè)子框架。槽值含有如何使用框架信息、下一步可能發(fā)生的信息、預(yù)計(jì)未實(shí)現(xiàn)該如何做的信息等。框架的一般格式：FRAMEWORK：<frameworkname><slot1><face11>:value...<face1n>:value<slot2><face21>:value...<face2n>:value...例：framework:<大學(xué)教師>類屬：<教師>學(xué)歷：（學(xué)士，碩士，博士）專業(yè)：<學(xué)科專業(yè)>職稱：（助教，講師，副教授，教授）外語(yǔ)：范圍：（英，法，德，...）默認(rèn)：英水平：（優(yōu)、良、中、差）默認(rèn)：良2.5.3框架表示下的推理框架表示法沒(méi)有固定的推理機(jī)理。但框架系統(tǒng)的推理和語(yǔ)義網(wǎng)絡(luò)一樣遵循匹配和繼承的原則，而且框架中如if-needed、if-added等槽的槽值是附加過(guò)程，在推理過(guò)程中起重要作用。如確定一個(gè)人的年齡，已匹配的知識(shí)庫(kù)中的框架為槽名年齡：NILif-needed:ASKif-added:CHECK在推理的過(guò)程中便啟動(dòng)了if-needed和if-added兩個(gè)槽的附加過(guò)程ASK和CHECK。4.5.4框架與產(chǎn)生式表示法的比較

productionframework知識(shí)表示單位規(guī)則框架推理固定、與知識(shí)庫(kù)獨(dú)立可變，與知識(shí)庫(kù)成一體建立知識(shí)庫(kù)容易困難通用性低高應(yīng)用簡(jiǎn)單問(wèn)題復(fù)雜問(wèn)題用戶初學(xué)者專家2.6面向?qū)ο蟮谋硎痉?.7腳本表示法2.8過(guò)程表示法2.9狀態(tài)空間表示法：用來(lái)表示問(wèn)題及其搜索過(guò)程的一種方法。1．問(wèn)題狀態(tài)空間的構(gòu)成（1）狀態(tài)：是描述問(wèn)題求解過(guò)程中不同時(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ā)生變化，從而使問(wèn)題由一個(gè)狀態(tài)轉(zhuǎn)變?yōu)榱硪粋€(gè)狀態(tài)的操作。（3）狀態(tài)空間：由表示一個(gè)問(wèn)題的全部狀態(tài)及一切可用算符構(gòu)成的集合。一般由三部分構(gòu)成：?jiǎn)栴}的所有可能的初始狀態(tài)構(gòu)成的集合S，算符集合F，目標(biāo)狀態(tài)集合G，用一個(gè)三元組表示：（S，F(xiàn)，G）狀態(tài)空間的圖示形式稱為狀態(tài)空間圖，其中，節(jié)點(diǎn)表示狀態(tài)，有向邊表示算符。（4）問(wèn)題的解：從問(wèn)題的初始狀態(tài)集S出發(fā)，經(jīng)過(guò)一系列的算符運(yùn)算，到達(dá)目標(biāo)狀態(tài)，由初始狀態(tài)到目標(biāo)狀態(tài)所用算符的序列就構(gòu)成了問(wèn)題的一個(gè)解。2．用狀態(tài)空間表示問(wèn)題的步驟（1）定義問(wèn)題狀態(tài)的描述形式（2）用所定義的狀態(tài)描述形式吧問(wèn)題的所有可能的狀態(tài)都表示出來(lái)，并確定出問(wèn)題的初始狀態(tài)集合描述和目標(biāo)狀態(tài)集合描述。（3）定義一組算符，使得利用這組算符可把問(wèn)題由一種狀態(tài)轉(zhuǎn)變到另一種狀態(tài)。3．利用狀態(tài)空間求解問(wèn)題的過(guò)程例：二階Hanoi塔問(wèn)題（見(jiàn)P72）解：第一步，定義問(wèn)題狀態(tài)的描述形式第二步，用所定義的狀態(tài)描述形式把問(wèn)題的所有可能的狀態(tài)都表示出來(lái)，并確定出問(wèn)題的初始狀態(tài)集合描述和目標(biāo)狀態(tài)集合描述第三步，定義一組算符2.10與/或樹表示法1、與或樹的概念用一個(gè)類似圖的結(jié)構(gòu)來(lái)表示把問(wèn)題歸約為后繼問(wèn)題的替換集合，畫出歸約問(wèn)題圖。例如，設(shè)想問(wèn)題A需要由求解問(wèn)題B、C和D來(lái)決定，那么可以用一個(gè)與圖來(lái)表示；同樣，一個(gè)問(wèn)題A或者由求解問(wèn)題B、或者由求解問(wèn)題C來(lái)決定，則可以用一個(gè)或樹來(lái)表示。2、與或樹的有關(guān)術(shù)語(yǔ)父節(jié)點(diǎn)是一個(gè)初始問(wèn)題或是可分解為子問(wèn)題的問(wèn)題節(jié)點(diǎn)；子節(jié)點(diǎn)是一個(gè)初始問(wèn)題或是子問(wèn)題分解的子問(wèn)題節(jié)點(diǎn)；或節(jié)點(diǎn)只要解決某個(gè)問(wèn)題就可解決其父輩問(wèn)題的節(jié)點(diǎn)集合；與節(jié)點(diǎn)只有解決所有子問(wèn)題，才能解決其父輩問(wèn)題的節(jié)點(diǎn)集合；弧線是父輩節(jié)點(diǎn)指向子節(jié)點(diǎn)的圓弧連線；終葉節(jié)點(diǎn)是對(duì)應(yīng)于原問(wèn)題的本原節(jié)點(diǎn)。3、與或樹的有關(guān)定義可解節(jié)點(diǎn)與或樹中一個(gè)可解節(jié)點(diǎn)的一般定義可以歸納如下：(1)終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)(因?yàn)樗鼈兣c本原問(wèn)題相關(guān)連)。(2)如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只有當(dāng)其后繼節(jié)點(diǎn)至少有一個(gè)是可解的時(shí)，此非終葉節(jié)點(diǎn)才是可解的。(3)如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只要當(dāng)其后繼節(jié)點(diǎn)全部為可解時(shí)，此非終葉節(jié)點(diǎn)才是可解的。不可解節(jié)點(diǎn)不可解節(jié)點(diǎn)的一般定義歸納于下：(1)沒(méi)有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。(2)如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只有當(dāng)其全部后裔為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。(3)如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只要當(dāng)其后裔至少有一個(gè)為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。4、與或樹構(gòu)樹規(guī)則(1)與或樹中的每個(gè)節(jié)點(diǎn)代表一個(gè)要解決的單一問(wèn)題或問(wèn)題集合。樹中所含起始節(jié)點(diǎn)對(duì)應(yīng)于原始問(wèn)題。(2)對(duì)應(yīng)于本原問(wèn)題的節(jié)點(diǎn)，叫做終葉節(jié)點(diǎn)，它沒(méi)有后裔。(3)

對(duì)于把算符應(yīng)用于問(wèn)題A的每種可能情況，都把問(wèn)題變換為一個(gè)子問(wèn)題集合；有向弧線自A指向后繼節(jié)點(diǎn)，表示所求得的子問(wèn)題集合。(4)一般對(duì)于代表兩個(gè)或兩個(gè)以上子問(wèn)題集合的每個(gè)節(jié)點(diǎn)，有向弧線從此節(jié)點(diǎn)指向此子問(wèn)題集合中的各個(gè)節(jié)點(diǎn)。(5)在特殊情況下，當(dāng)只有一個(gè)算符可應(yīng)用于問(wèn)題A，而且這個(gè)算符產(chǎn)生具有一個(gè)以上子問(wèn)題的某個(gè)集合時(shí)，由上述規(guī)則3和規(guī)則4所產(chǎn)生的圖可以得到簡(jiǎn)化。第三章推理方法謂詞邏輯是一種表達(dá)力很強(qiáng)的形式語(yǔ)言，謂詞邏輯及其推理方法是人工智能中知識(shí)表示方法,機(jī)器推理,定理證明的基本方法。另外謂詞邏輯中的替換合一技術(shù)，也是符號(hào)推理中模式匹配的基本技術(shù)。本章主要講解基于謂詞邏輯的歸結(jié)演繹推理。3.1歸結(jié)推理方法（確定性推理方法）3.1.1謂詞、函數(shù)、量詞謂詞：表示個(gè)體對(duì)象之間的關(guān)系、屬性或狀態(tài)。其表示形式如下：P(x1,x2,x3,...xn)其中：P是謂詞符號(hào)，表示x1,x2,x3,...xn個(gè)體對(duì)象之間的屬性、狀態(tài)或關(guān)系。x1,x2,x3,...xn是謂詞的參量（或稱項(xiàng)），一般表示個(gè)體，它可以是個(gè)體常量、個(gè)體變量或是個(gè)體函數(shù)。個(gè)體變?cè)淖兓秶Q為個(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）謂詞符號(hào)有大寫字母表示，如P，Q，R，S等；（2）用小寫字母x,y,z等作為個(gè)體變?cè)?hào)；（3）用小寫字母a,b,c等作為個(gè)體常元符號(hào)；（4）用小寫字母f,g,h表示個(gè)體函數(shù)符號(hào)。量詞全稱量詞：“所有”,“一切”,“任一”,“全體”,“凡是”等詞稱為全稱量詞，記為x存在量詞：“存在”、“有些”、“至少有一個(gè)”、“有的”等詞統(tǒng)稱為存在量詞，記為x引入量詞和連接符（→蘊(yùn)涵，∧合取，∨析取，否定詞～）之后，謂詞的表達(dá)能力大大擴(kuò)充了例1：謂詞M(x):表示x是人，謂詞N(x):表示x有名字，則x(M(x)→N(x))表示“凡是人都有名字”。例2：謂詞G(x):表示x是整數(shù)，E(x)：表示x是偶數(shù)，則x（G(x)∧～E(x))表示“存在不是偶數(shù)的整數(shù)”例3：知識(shí)“不存在最大的整數(shù)”的表示設(shè)：謂詞G(x):表示x是整數(shù)，D(x,y)表示x大于y。則表示如下：～x(G(x)∧y(G(y)→D(x,y)))或x(G(x)∧y(G(y)∧D(y,x)))謂詞公式：用謂詞、量詞（存在量詞，全稱量詞）、聯(lián)接詞（→蘊(yùn)涵，∧合取，∨析取）連接而成的復(fù)雜的符號(hào)表達(dá)式稱為謂詞公式。3.1.2命題邏輯的歸結(jié)法1.概念:不帶參數(shù)（肯定也不含量詞）)的謂詞稱為命題.謂詞的表達(dá)能力更強(qiáng)，命題沒(méi)有概括能力；命題：P1:代表“北京是一個(gè)城市”P2：代表“上海是一個(gè)城市”P3：代表“廣州是一個(gè)城市”謂詞：CITY(x)：代表“x是一個(gè)城市”，x的論域?yàn)镈={北京，上海，廣州}謂詞代表變化著的情況，而命題代表固定的情況；P：北京是一個(gè)城市；Q：煤球是白的；則P為永真式，Q為永假式；而對(duì)于以上的謂詞CITY(x)，當(dāng)x取值為“北京”時(shí)為“真”值，當(dāng)x取值為“煤球”時(shí)為“假”值。謂詞和命題相比的優(yōu)點(diǎn)是謂詞在不同的知識(shí)之間建立聯(lián)系；例如下面四個(gè)知識(shí)單元：HUMAN(x)：代表x是人；LAWED(x):代表x受法律管制；COMMIT(x):代表x犯法；PUNISHED(x):x受法律制裁；則HUMAN(x)→LAWED(x)表示一個(gè)高級(jí)的知識(shí)單元“人人都受法律的管制”。COMMIT(x)→PUNISHED(x)表示只要x犯罪，x就要受法律制裁。{（HUMAN(x)→LAWED(x)）→（COMMIT(x)→PUNISHED(x)）}表示“如果由于某個(gè)x是人而受到法律管制，則這個(gè)人犯了罪就一定要受到懲罰”由連接詞(→蘊(yùn)涵，∧合取，∨析取，等價(jià)<->，否定詞~)將命題連接在一起構(gòu)成命題公式。A->B，A稱為前件，B稱為后件，其真值表如下所示：ABA->B001011100111A<->B等價(jià)于(A->B)∧(B->A)一些概念：永真式：真值為T的命題公式稱為永真式或重言式或有效的。永假式：真值為F的命題公式稱為永假式或不可滿足的。非永真式：不是永真式的命題公式；可滿足式：不是永假公式的命題公式；原子公式:不含任何連接詞的命題公式稱為原子公式或稱原子.例如P,Q文字:原子公式及其否定形式稱為文字.例如P,～L子句:文字的析取稱為子句.例如:P∨R∨～Q互補(bǔ)文字：設(shè)L為一個(gè)文字，則稱L與～L為互補(bǔ)文字。一些有用的等價(jià)關(guān)系：～～A<=>A雙重否定A∧A<=>A等冪律A∨A<=>AA∧B<=>B∧A交換律A∨B<=>B∨A(A∧B)∧C<=>A∧(B∧C)結(jié)合律(A∨B)∨C<=>A∨(B∨C)A∧(B∨C)<=>(A∧B)∨(A∧C)分配律A∨(B∧C)<=>(A∨B)∧(A∨C)A∧(A∨B)<=>A吸收律A∨(A∧B)<=>A～(A∧B)<=>～A∨～B摩根定律～(A∨B)<=>～A∧～BA→B<=>～A∨B蘊(yùn)含表達(dá)式A<->B<=>(A→B)∧(B→A)等價(jià)表達(dá)式A∧T<=>AA∧F<=>FA∨T<=>TA∨F<=>AA∧～A<=>F矛盾律A∨～A<=>T排中律A→(B→C)<=>A∧B→C輸出律(A→B)∧(A→～B)<=>～A歸謬律A→B<=>～B→～A逆反律2命題邏輯中的歸結(jié)推理方法若命題邏輯描述的命題A1,A2,...An和B,要證明在A1∧A2∧...∧An成立的條件下有B成立，或說(shuō)A1∧A2∧...∧An→B。很顯然A1∧A2∧...∧An→B等價(jià)于證明A1∧A2∧...∧An∧～B是矛盾(永假)式。歸結(jié)推理的方法就是從A1∧A2∧...∧An∧～B出發(fā)使用歸結(jié)推理規(guī)則來(lái)尋找矛盾，從而證明A1∧A2∧...∧An→B的成立。這種方法稱為反演推理方法。3歸結(jié)式設(shè)有兩個(gè)子句C1=P∨C1'C2=～P∨C2'從中消去互補(bǔ)對(duì)，所得新子句R(C1,C2)=C1'∨C2'，稱為子句C1'，C2'的歸結(jié)式。沒(méi)有互補(bǔ)對(duì)的兩子句沒(méi)有歸結(jié)式。歸結(jié)推理規(guī)則就指的是對(duì)兩子句做歸結(jié)，也即求歸結(jié)式。下面證明歸結(jié)推理規(guī)則是正確的，即C1∧C2=>R(C1,C2)，也即證明歸結(jié)式是兩子句的邏輯結(jié)論，或者說(shuō)任一使C1，C2為真的解釋I下必有R(C1,C2)也為真。證：設(shè)I是使C1，C2為真的任一解釋，若在I下P為真，從而～P為假，則C2'必為真，那么R(C1,C2)=C1'∨C2'為真。若在I下P為假，則C1'必為真，那么R(C1,C2)=C1'∨C2'為真。從而證明了C1∧C2=>R(C1,C2)，即歸結(jié)式是子句的邏輯結(jié)論。特別地，當(dāng)C1=P，C2=～P時(shí)，R(C1,C2)=□，記作為空子句。顯然C1，C2同時(shí)為真是矛盾，或者說(shuō)空子句□體現(xiàn)了矛盾。4命題邏輯的歸結(jié)推理過(guò)程(1)利用邏輯蘊(yùn)含式和邏輯等價(jià)式將命題公式化成合取范式(子句的析取)(2)子句集：將若干個(gè)子句的合取式中的合取詞∧換成逗號(hào)，形成的集合稱為子句集。(3)從子句集S出發(fā)，僅只對(duì)S的子句間使用歸結(jié)推理規(guī)則（即求歸結(jié)式），并將所得歸結(jié)式仍放入S中，進(jìn)而再對(duì)新子句集使用歸結(jié)推理規(guī)則，重復(fù)這些步驟直到得到空子句□（說(shuō)明有矛盾）。便說(shuō)明S是不可滿足的，從而與子句集S對(duì)應(yīng)的定理是成立的。例：證明(P→Q)∧～Q==>～P證：先將已知以及結(jié)論的反化成合取范式(～P∨Q)∧～Q∧(～～P)==>(～P∨Q)∧～Q∧P，建立子句集S=｛～P∨Q，～Q，P｝對(duì)S作歸結(jié)(1)～P∨Q(2)～Q(3)P(4)～P..............對(duì)(1)(2)求歸結(jié)式(5)□...............對(duì)(3)(4)求歸結(jié)式得證。例:證明(P→Q)∧(R→～Q)==>(R→～P)證明:將已知以及結(jié)論的反化成合取范式==>(～P∨Q)∧(～R∨～Q)∧(～(～R∨～P))==>(～P∨Q)∧(～R∨～Q)∧R∧P化成子句集S=｛～P∨Q，～R∨～Q，R,P｝,對(duì)S做歸結(jié):(1)～P∨Q(2)～R∨～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有如下形式B1∧B2∧...∧Bn,其中Bi(i=1,2,...n)形如L1∨L2∨...∨Ln，并且L1,L2,...Ln都是文字。例：(P(x)∨～Q(y))∧(～P(x)∨R(x,y))∧(～Q(y)∨～R(x,y))應(yīng)用邏輯等價(jià)式可以將任一謂詞公式化成合取范式。（2）析取范式：若謂詞公式A有如下形式B1∨B2∨...∨Bn,其中Bi(i=1,2,...n)形如L1∧L2∧...∧Ln，并且L1,L2,...Ln都是文字。例：(P(x)∧～Q(y)∧R(x,y))∨(～P(x)∧R(x,y))應(yīng)用邏輯等價(jià)式和邏輯蘊(yùn)含式可以將任一謂詞公式化成析取范式。（3）前束范式:將所有的量詞都放在謂詞公式的前面。如xy(P(x,y)∧Q(a)∧R(z))就是前束范式。x(N(x)∧yD(y,x))就不是前束范式。前束范式可分成前束合取范式和前束析取范式?；汕笆先》妒降牟襟E：step1:去掉多余的量詞，即沒(méi)意義的量詞step2:將同名的約束變?cè)c自由變?cè)拿?，使它們不同名。消去∧，∨，~以外的連接詞A->B.............~A∨BA<->B............(~A∨B)∧(~B∨A)step4:將連接詞~內(nèi)移，移到原子公式之前～(～A)=A

～(A∧B)<=>～A∨～B

～(A∨B)<=>～A∧～B

～xA(x)<=>x～A(x)

～xA(x)<=>x～A(x)step5:將量詞盡可能向左推，推到前綴所在的位置，用下列公式：xA(x)∨B............x（A(x)∨B），其中B中不含約束變?cè)狟∨xA(x)............x（B∨A(x)），其中B中不含約束變?cè)獂A(x)∨B............x（A(x)∨B），其中B中不含約束變?cè)狟∨xA(x)............x（B∨A(x)），其中B中不含約束變?cè)瑯訉?duì)上面式子中的∨改為∧可得到另一組關(guān)于的∧的替換式。另外還可用下式進(jìn)行替換：xA(x)∧xB(x)..................x（A(x)∧B(x)）xA(x)∨xB(x)..................xy（A(x)∨B(y)）,采用更名規(guī)則xA(x)∨xB(x)..................x（A(x)∨B(x)）xA(x)∧xB(x)..................xy（A(x)∧B(y)）,采用更名規(guī)則step6:使用∧，∨的分配律化成合取范式。例：將下列謂詞公式化成前束合取范式：（4）Skolem（斯克林）標(biāo)準(zhǔn)型：將一個(gè)謂詞公式中所有存在量詞消去之后，便得到該謂詞公式的Skolem標(biāo)準(zhǔn)型。（5）建立謂詞公式的子句集2將謂詞公式化成子句集的步驟：按上述步驟化成前束合取范式；化成Skolem標(biāo)準(zhǔn)型，消去存在量詞

消取存在量詞時(shí)，還要進(jìn)行變?cè)鎿Q。變?cè)鎿Q分兩種情況：

①若該存在量詞在某些全稱量詞的轄域內(nèi)，則用這些全稱量詞指導(dǎo)變?cè)囊粋€(gè)函數(shù)代替該存在量詞轄域中的相應(yīng)約束變?cè)?，這樣的函數(shù)稱為Skolem函數(shù)；

②若該存在量詞不在任何全稱量詞的轄域內(nèi)，則用一個(gè)常量符號(hào)代替該存在量詞轄域中相應(yīng)約束變?cè)?，這樣的常量符號(hào)稱為Skolem常量；消去所有全稱量詞消去合取詞∧，用逗號(hào)代替，以子句為元素組成一個(gè)集合S，即是謂詞公式的子句集例1：求謂詞公式G=xyz((～P(x,y)∨R(x,y,z))∧(Q(x,z)∨R(x,y,z)))的子句集。解：已經(jīng)是前束范式，并且不含連接詞。由于存在量詞y,z都在全稱量詞x的轄域中，所以將y,z分別用Skolem函數(shù)f(x)、g(x)代替。x((～P(x,f(x))∨R(x,f(x),g(x)))∧(Q(x,g(x))∨R(x,f(x),g(x))))已經(jīng)是合取范式了，所以謂詞公式G的子句集是｛～P(x,f(x))∨R(x,f(x),g(x))，Q(x,g(x))∨R(x,f(x),g(x))｝例2：求謂詞公式的子句集:x(yP(x,y)→～y(Q(x,y)→R(x,y)))解：x(yP(x,y)→～y(Q(x,y)→R(x,y)))==>x(yP(x,y)→y～(～Q(x,y)∨R(x,y)))==>x(yP(x,y)→y(Q(x,y)∧～R(x,y)))==>x(yP(x,y)→z(Q(x,z)∧～R(x,z)))...改名==>xy(P(x,y)→z(Q(x,z)∧～R(x,z)))...量詞分配率==>xyz(P(x,y)→(Q(x,z)∧～R(x,z)))...量詞分配率==>xyz(～P(x,y)∨(Q(x,z)∧～R(x,z)))==>xyz[(～P(x,y)∨Q(x,z))∧(～P(x,y)∨～R(x,z))]...分配律==>x[(～P(x,f(x))∨Q(x,g(x)))∧(～P(x,f(x))∨～R(x,g(x))]...消取存在量詞從而謂詞公式的子句集是｛～P(x,f(x))∨(Q(x,g(x)，～P(x,f(x))∨～R(x,g(x))｝例3：設(shè)G=xyzuvw(P(x,y,z)∧～Q(u,v,w))，求其子句集解：xyzuvw(P(x,y,z)∧～Q(u,v,w)==>yzuvw(P(a,y,z)∧～Q(u,v,w))......消去x=a（常數(shù)）==>yzvw(P(a,y,z)∧～Q(f(y,z),v,w))......消去u=f(y,z)==>yzv(P(a,y,z)∧～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ī)器證明"梯形的對(duì)角線與上下底構(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，問(wèn)題的描述和相應(yīng)的子句集為xyuv[T(x,y,u,v)→P(x,y,u,v)]...梯形上下底平行子句：～T(x,y,u,v)∨P(x,y,u,v)xyuv[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)∨P(x,y,u,v)，～P(x,y,u,v)∨E(x,y,v,u,v,y)，T(a,b,c,d)，～E(a,b,d,c,d,b)｝

利用后面學(xué)到的替換和合一知識(shí)之后可給出證明過(guò)程。3.1.4Herbrand理論：證明一個(gè)謂詞公式的不可滿足性是困難的，這是因?yàn)橹^詞中個(gè)體變量的論域D的任意性，以及解釋的個(gè)數(shù)的無(wú)限性。例如：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)；所以如果對(duì)一個(gè)具體的謂詞公式能找到一個(gè)比較簡(jiǎn)單的特殊的論域，使得只要在這個(gè)論域上該公式是不可滿足的，便能保證該公式在任一論域上也是不可滿足的。所要建立的Herbrand域（簡(jiǎn)稱H域）就具有這樣的性質(zhì)。1H域設(shè)G是謂詞公式，定義在論域D上，令H0是G中所出現(xiàn)的常量的集合。若G中沒(méi)有常量出現(xiàn)，就任取常量a∈D，而規(guī)定H0={a}；Hi=Hi-1∪{所有形如f(t1,...tn)的元素}，其中f(t1,...,tn)是出現(xiàn)于G中的任一函數(shù)符號(hào)，而t1...tn是Hi-1的元素，i=1,2,...。規(guī)定H∞為G的H域。不難看出H域是直接依賴于G的最多只有可數(shù)個(gè)元素。例1：S={P(a),~P(x)∨P(f(x))}，依H域的定義有：H0={a}H1={a}∪{f(a)}={a,f(a)}H2={a,f(a)}∪{f(a),f(f(a))}={a,f(a),f(f(a))}……H∞={a,f(a),f(f(a)),…}例2：S={~P(z),P(x)∨~Q(y)}依定義有H0={a}a是論域D中的一個(gè)常量H1=H0H2=H1……H∞={a}例3：S={P(f(x),a,g(y),b)}依定義有H0={a,b}H1={a,b}∪{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)}∪{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(b)),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∞=H0∪H1∪H2∪……注意：如果在謂詞或子句集中出現(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中的任一謂詞符號(hào)，而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)∨Q(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ù)集。2H解釋由子句集S建立H域、原子集A，從而討論S在一般論域D上為真的解釋I，就可依賴于在H域上的某個(gè)解釋I*來(lái)實(shí)現(xiàn)。也就是子句集S在D上的不可滿足問(wèn)題轉(zhuǎn)化成了在H上的不可滿足問(wèn)題。下例說(shuō)明由I尋求I*的過(guò)程例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)∧Q(1,f(1,2))∧P(1)∧Q(2,f(2,1))∧P(2)∧Q(1,f(1,2))∧P(2)∧Q(2,f(2,2))=T可按下列方法選取相應(yīng)的I*，a→2f(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)→1...P(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)∨Q(x),R(f(y))}的H域、原子集A，I*解釋。仍然設(shè)D={1，2}，解釋I設(shè)定如下：f(1)--f(2)--P(1)--P(2)--Q(1)--Q(2)--R(1)--R(2)2------2-----T-----F-----F-----T------F----T于是由S|I=P(1)∨Q(1)∧R(f(1))∧P(1)∨Q(1)∧R(f(2))∧P(2)∨Q(2)∧R(f(1))∧P(2)∨Q(2)∧R(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上的解釋，存在對(duì)應(yīng)于I的H解釋I*，使得若有S|I=T,必有S|I*=T定理：子句集S是不可滿足的，當(dāng)且僅當(dāng)在所有的S的H解釋下為假。定理：子句集S是不可滿足的當(dāng)且僅當(dāng)對(duì)每個(gè)解釋I下，至少有S的某個(gè)子句的某個(gè)基例為假。3語(yǔ)義樹討論S的不可滿足性問(wèn)題，可將S的所有解釋展現(xiàn)在一棵二叉樹上（這是一個(gè)完全二叉樹），但要依賴于S的H解釋以及S的原子集A。例：對(duì)子句集S={P(x)∨Q(y),~P(a),~Q(b)}畫出相應(yīng)的語(yǔ)義樹因?yàn)镠={a，b}A={P(a),Q(a),P(b),Q(b)}從A出發(fā)可畫出語(yǔ)義樹（部分）為了方便常以I（N）表示從根結(jié)點(diǎn)到結(jié)點(diǎn)N分支上所標(biāo)記的所有文字的集合。例如I(N32)={P(a),Q(a),~P(b)},I(N42)={P(a),Q(a),P(b),~Q(b)}例：對(duì)子句集S={~P(x)∨Q(x)，P(f(y)),~Q(f(y))}畫出相應(yīng)的語(yǔ)義樹。因?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的語(yǔ)義樹，而且是無(wú)限樹。通過(guò)對(duì)S的完全語(yǔ)義樹的觀察，便可看到S的所有解釋，這棵樹的每個(gè)直到葉結(jié)點(diǎn)的分支都對(duì)應(yīng)于S的一個(gè)解釋。特別對(duì)有限樹來(lái)說(shuō)，若N是葉結(jié)點(diǎn)，那么I(N)便是S的一個(gè)解釋。為討論S的不可滿足性，就可通過(guò)對(duì)語(yǔ)義樹每個(gè)分支來(lái)計(jì)算S的真值而實(shí)現(xiàn)。有時(shí)并不需要無(wú)限延伸某個(gè)分支方能確定在相應(yīng)的解釋下S取假值。例如某個(gè)分支延伸到結(jié)點(diǎn)N時(shí)，I(N)已使S的某個(gè)子句的某一基例為假，就無(wú)需對(duì)N再做延伸了。此時(shí)就說(shuō)N是失敗結(jié)點(diǎn)。如果S的完全語(yǔ)義樹的每個(gè)分支上都有一個(gè)失敗結(jié)點(diǎn)，就說(shuō)它是一個(gè)封閉樹。即S的不可滿足性<=>S的語(yǔ)義樹是封閉語(yǔ)義樹。在上圖中如果畫出完全語(yǔ)義樹的話，則每個(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)。同樣的方法可看出每個(gè)分支上都存在失敗結(jié)點(diǎn)。4Herbrand定理定理一：子句集S是不可滿足的，當(dāng)且僅當(dāng)對(duì)應(yīng)于S的完全語(yǔ)義樹都是一棵有限的封閉語(yǔ)義樹。定理二：子句集S是不可滿足的，當(dāng)且僅當(dāng)存在不可滿足的有限基例集（即存在有限個(gè)失敗結(jié)點(diǎn)）。Herbrand定理給出了一階邏輯的半可判定算法。其中的“半”字指的是有條件下的判定算法，即僅當(dāng)被證定理是成立的，使用該算法方可得證。而當(dāng)被證定理并不成立時(shí)，使用該算法得不出任何結(jié)果。說(shuō)是算法，那指的是有限步內(nèi)是可實(shí)現(xiàn)的，因?yàn)闊o(wú)論從有限的封閉樹觀點(diǎn)，還是從不可滿足的有限基例集觀點(diǎn)都是可判定的，因?yàn)檫@已經(jīng)是有限的命題邏輯問(wèn)題了。使用Herbrand定理來(lái)證明定理或子句集S是不可滿足的，或是尋找有限的封閉樹，或是尋找有限的不可滿足的基例集。一個(gè)具體實(shí)現(xiàn)證明的方法是，對(duì)S的H域中的Hi做出基例集Si'，即將Hi中的元素依次代入S中的各子句便構(gòu)成Si'，若Si'是不可滿足的必有S是不可滿足的，或說(shuō)相應(yīng)的定理成立。若被證定理成立，必可在有限步內(nèi)證明某個(gè)SN’是不可滿足的。3.1.5謂詞邏輯的歸結(jié)原理（消解原理）1替換與合一（回顧謂詞公式、原子公式、文字、子句、項(xiàng)、個(gè)體的概念）命題邏輯中的歸結(jié)原理很簡(jiǎn)單，因?yàn)樵诿}邏輯中不含量詞，而謂詞邏輯中含有量詞和個(gè)體變?cè)?，這樣尋找互補(bǔ)文字對(duì)就變得較復(fù)雜。例：子句C1=P(x)∨Q(x)，子句C2=～P(a)∨R(y),如直接比較，似乎找不到互補(bǔ)文字，但如果使用替換辦法，將C1中的x替換成a,則C1和C2的歸結(jié)式為R(C1,C2)=Q(a)∨R(y)即可消去互補(bǔ)文字。從而對(duì)謂詞邏輯使用歸結(jié)原理求解問(wèn)題的步驟是：求出謂詞公式的Skolem標(biāo)準(zhǔn)型-->謂詞公式的子句集-->利用替換和合一-->再利用歸結(jié)原理消去互補(bǔ)對(duì)---->求解/證明結(jié)論。替換(Substitution):形如｛t1/x1,t2/x2,...tn/xn｝,ti是項(xiàng)，稱為替換的分子，xi是互不相同的個(gè)體變?cè)?，稱為替換分母(i=1,2,...n)，且ti與xi不相同，xi與ti互不循環(huán)出現(xiàn)。ti/xi表示xi用ti替換。若ti都是不含變?cè)捻?xiàng)（基項(xiàng)），該替換稱為基替換；沒(méi)有元素的替換稱為空替換，記作ε，他表示不做替換。例：｛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è)謂詞公式，θ=｛t1/x1,t2/x2,...tn/xn｝是一個(gè)替換，對(duì)E施行θ替換之后所得的結(jié)果記為Eθ，稱為E在θ下的例（instance）例：設(shè)謂詞公式G=P(x,y,z),替換θ=｛a/x,f(b)/y,c/z｝，則Gθ=P(a,f(b),c)替換的乘積（復(fù)合替換）：設(shè)θ=｛t1/x1,...,tn/xn｝，λ=｛u1/y1,...,um/ym｝是兩個(gè)替換，則將集合｛t1λ/x1,...,tnλ/xn，u1/y1,...,um/ym｝中凡符合下列條件的元素刪除(1)tiλ/xi......當(dāng)tiλ=xi時(shí)(2)ui/yi........當(dāng)yi∈｛x1,x2,...xn｝如此得到的集合仍然是一個(gè)替換，該替換稱為θ與λ的復(fù)合或乘積，記為θ·λ例：θ=｛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é)合律，但不滿足交換律，即有：(θ·λ)·u=θ·(λ·u)，θ·λ≠λ·θ，λ·ε=λ例：若謂詞公式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))s1·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)可見(jiàn)(Es1)s2=E(s1·s2)≠E(s2·s1)2合一置換（替換）定義1：設(shè)S=｛F1,F2,...,Fn｝是一個(gè)子句集（F1,F2,...Fn是文字的析?。?，若存在一個(gè)替換θ，可使F1θ=F2θ=...Fnθ，則稱θ為S的一個(gè)合一（Unifier）,并稱S為可合一的。一個(gè)謂詞公式的合一不唯一。定義2：設(shè)δ是謂詞公式子句集S的一個(gè)合一，如果對(duì)S的任何一個(gè)合一θ，都存在一個(gè)替換λ,使得θ=δ·λ則稱δ是子句集的最一般合一，簡(jiǎn)稱MGU(MostGeneralUnifier)。例：設(shè)子句集S=｛P(u,y,g(y)),P(x,f(u),z)｝,S有一個(gè)最一般合一MGU，δ=｛u/x,f(u)/y,g(f(u))/z｝,對(duì)S的任一合一，例如θ=｛a/x,f(a)/y,g(f(a))/z,a/u｝,存在一個(gè)替換λ=｛a/u｝，使得θ=δ·λ求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,δk=ε;②若Sk是單元素集，則算法停止，MGU=δk③求Sk的差異集Dk;④若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)⑤算法停止，S的MGU不存在(若S是可合一的，算法總是在步②停止)例：求公式集S=｛P(a,x,f(g(y)),P(z,h(z,u),f(u))｝的MGU。解：k=0;S0=S;δ0=ε;S0不是單元素集，求得差異集D0=｛a/z｝,其中z是變?cè)?，a是項(xiàng)，且z不在a中出現(xiàn)。k=k+1=1有δ1=δ0·｛a/z｝=ε·｛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;δ2=δ1·｛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))｝，S2不是單元素集，求得差異集D2=｛g(y),u｝,k=k+1=3δ3=δ2·｛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ù)求MGU算法，MGU=δ3=｛a/z,h(a,g(y))/x,g(y)/u｝3謂詞邏輯中的歸結(jié)式謂詞邏輯下求兩個(gè)子句的歸結(jié)式，和命題邏輯一樣也是消去互補(bǔ)對(duì)，但需考慮變量的合一與置換。設(shè)S=｛C1,C2｝C1,C2是子句集中的子句，L1、L2分別是C1，C2中的文字，并且L1和～L2有最一般合一δ，則子句｛C1δ-L1δ｝∪｛C2δ-L2δ｝稱為C1、C2的歸結(jié)式。C1，C2稱為歸結(jié)式的親本子句，L1、L2稱為歸結(jié)文字。例：S=｛C1,C2｝=S=｛P(x)∨Q(x),～P(a)∨R(y)｝，求C1，C2的歸結(jié)式。L1=P(x)，L2=～P(a)，則L1與L2的MGUδ=｛a/x｝,則｛C1δ-L1δ｝∪｛C2δ-L2δ｝=｛P(a)∨Q(a)｝-｛P(a)｝∪｛～P(a)∨R(y)｝-｛～P(a)｝=｛Q(a)∨R(y)｝即R(C1,C2)=Q(a)∨R(y).........δ=｛a/x｝例：C1=｛P(x,y)～Q(a)｝,C2=｛Q(x)∨R(y)｝求C1、C2的歸結(jié)式。在對(duì)子句進(jìn)行歸結(jié)之前，可先在子句內(nèi)部進(jìn)行化簡(jiǎn)。如子句C=P(x)∨P(f(y)),令置換δ=｛f(y)/x｝，則Cδ=P(f(y))∨～Q(f(y)),Cδ稱為C的因子。R(C1,C2)=R(C1δ,C2)=R(C1,C2δ)=R(C1δ,C2δ)定理:謂詞邏輯中的歸結(jié)式是它的親本子句的邏輯結(jié)果,即:C1∧C2=>(C1δ-｛L1δ｝)∨(C2δ-｛L2δ｝),這就是謂詞邏輯的歸結(jié)原理.4利用歸結(jié)原理證明/求解例1:求證:G是A1和A2的邏輯結(jié)果A1:x(P(x)→(Q(x)∧R(x)))A2:x(P(x)∧S(x))G:x(S(x)∧R(x))證:①～P(x)∨Q(x)...從A1變換②～P(y)∨R(y)...從A1變換③P(a)④S(a)⑤～S(z)∨～R(z)...結(jié)論的否定⑥R(a)......②③歸結(jié)｛a/y｝⑦～R(a)......④⑤歸結(jié)｛a/z｝⑧□......⑥⑦歸結(jié)得證.例2:設(shè)已知:(1)能閱讀者是識(shí)字的;(2)海豚不識(shí)字;(3)有些海豚是聰明的;求證:有些聰明者并不能閱讀.證:定義如下命題:R(x):x能閱讀;L(x):x識(shí)字;I(x):x是聰明的;D(x):x是海豚;把已知條件及求證結(jié)論翻譯成謂詞公式為x(R(x)→L(x))...已知x(D(x)→～L(x))...已知x(D(x)∧I(x))...已知x(I(x)∧～R(x))...求證結(jié)論將已知條件,求證結(jié)論的反化成子句集①～R(x)∨L(x)②～D(y)∨～L(y)③D(a)④I(a)⑤～I(xiàn)(z)∨R(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:求解問(wèn)題,已知:如果x和y是同班同學(xué),則x的老師也是y的老師;王先生是小李的老師;小李和小張是同班同學(xué);問(wèn)小張的老師是誰(shuí)?解:定義謂詞T(x,y):x是y的老師;C(x,y):x與y是同班同學(xué);則已知可表示成如下的謂詞公式xyz((C(x,y)∧T(z,x))→T(z,y))T(wang,Li)......wang,Li是常元C(Li,Zhang)xT(x,zhang)......(先證明zhang的老師是存在的)以上謂詞公式及結(jié)論的反化成子句集如下:①～C(x,y)∨～T(z,x)∨T(z,y)②T(wang,Li)③C(Li,Zhang)④～T(u,zhang)⑤～C(Li,y)∨T(wang,y)......1,2歸結(jié),｛wang/z,Li/x｝⑥～C(Li,zhang)......4,5歸結(jié),｛wang/u,zhang/y｝⑦□......3,6歸結(jié)說(shuō)明zhang的老師存在.為了求解用一個(gè)重言式代替④④～T(u,zhang)∨T(u,zhang)......用重言式代替結(jié)論的否定,重言式恒為真⑤～C(Li,y)∨T(wang,y)......1,2歸結(jié),｛wang/z,Li/x｝⑥～C(Li,zhang)∨T(wang,zhang)......4,5歸結(jié),｛wang/u,zhang/y｝⑦T(wang,zhang)......3,6歸結(jié)得結(jié)果:張的老師是王先生.也可用輔助謂詞ANS(u)④～T(u,zhang)∨ANS(u)......用輔助謂詞ANS(u)⑤～C(Li,y)∨T(wang,y)......1,2歸結(jié),｛wang/z,Li/x｝⑥～C(Li,zhang)∨ANS(wang)......4,5歸結(jié),｛wang/u,zhang/y｝⑦□∨ANS(wang)......3,6歸結(jié)得結(jié)果:張的老師是王先生.3.1.6歸結(jié)過(guò)程的控制策略1.刪除策略概念:設(shè)C1,C2是兩個(gè)子句,若存在替換θ,使得C1θ包含在C2中,則稱子句C1類含C2。如:P(x)類含P(a)∨Q(y),取θ=｛a/x｝,或者說(shuō)P(x)把P(a)∨Q(y)歸類P(a,x)∨P(y,b)類含P(a,b),取θ=｛b/x,a/y｝純文字：在子句集中無(wú)補(bǔ)的文字。如下列子句集｛P(x)∨Q(x,y)∨R(x),～P(a)∨Q(u,v)｝中的文字R(x)就是一個(gè)純文字。在歸結(jié)的過(guò)程中刪除以下子句含有純文字的子句;含有永真式的子句;子句集中被別的子句類含的子句;刪除含有純文字的子句，是因?yàn)樵跉w結(jié)過(guò)程中純文字永遠(yuǎn)不會(huì)消去，因而用包含它的子句進(jìn)行歸結(jié)不可能得到空子句。刪除永真式是因?yàn)橛勒媸綄?duì)子句集的不可滿足性不起任何作用。刪除被類含的子句是因?yàn)楸活惡淖泳涫穷惡淖泳涞倪壿嬏N(yùn)含，故它是多余的。如P(a,x)∨P(y,b)類含P(a,b)，則可將P(a,b)刪除。例：利用刪除策略對(duì)下列子句集進(jìn)行歸結(jié)(1)P∨Q...已知(2)～P∨Q...已知(3)P∨～Q...已知(4)～P∨～Q...已知(5)Q...(1)(2)歸結(jié),此時(shí)可將子句(1)(2)刪除,因它們被子句(5)類含,此時(shí)歸結(jié)只在3,4,5之間進(jìn)行(6)～Q...(3)(4)歸結(jié)(7)□...(5)(6)歸結(jié)例:利用刪除策略對(duì)下列子句集進(jìn)行歸結(jié)(1)P(x)∨Q(x)∨～R(x)...已知(2)～Q(a)...已知(3)～R(a)∨Q(a)...已知(4)P(y)...已知(5)～P(z)∨R(z)...已知,子句(4)類含(1),所以將子句(1)刪除(6)～R(a)...(2)(3)歸結(jié),此時(shí)子句(3)可刪除,因?yàn)樗?6)類含(7)～P(a)...(5)(6)歸結(jié)｛a/z｝,此時(shí)子句(5)可刪除,因?yàn)樗?7)類含(8)□...(4)(7)歸結(jié)｛a/y｝刪除策略是及早刪除無(wú)用子句,縮小搜索規(guī)模.刪除策略是完備的,即對(duì)不可滿足的子句集,使用刪除策略進(jìn)行歸結(jié)必能導(dǎo)出空子句.2.語(yǔ)義歸結(jié)一種語(yǔ)義歸結(jié)是把子句S分成兩部分，約定每部分內(nèi)的子句間不允許做歸結(jié)。還引入了文字次序，約定歸結(jié)時(shí)其中的一個(gè)子句的被歸結(jié)文字只能是該子句中“最大”的文字例：子句集S={~P∨~Q∨R,P∨R,Q∨R,~R}先規(guī)定S中文字的出現(xiàn)順序如依次為P，Q，R，再選取S的一個(gè)解釋如令I(lǐng)={~P，~Q，~R}用它將S分成兩部分。在解釋I下為假的子句放入S1'中，在解釋I下為真的子句放入S2'中，于是有：S1'={P∨R,Q∨R}S2'={~P∨~Q∨R,~R}規(guī)定在Si'內(nèi)部的子句不允許歸結(jié)，S1'與S2'子句間的歸結(jié)必須是S1'中的最大文字方可進(jìn)行。這樣所得的歸結(jié)式仍按解釋I放入S1'或S2'中。歸結(jié)過(guò)程：（1）~P∨~Q∨R................按順序排列，屬于S2'（2）P∨R................按順序排列，屬于S1'（3）Q∨R................按順序排列，屬于S1'（4）~R................按順序排列，屬于S2'（5）~Q∨R.............(2)和(1)歸結(jié)，因?yàn)檫x取S1'最大文字方向（6）~P∨R.............(3)和(1)歸結(jié)，因?yàn)檫x取S1'最大文字方向（7）R.............(2)和(6)歸結(jié)（8）□............（7）和（4）歸結(jié)明顯地減少了歸結(jié)次數(shù)，阻止了（1）與（4）歸結(jié)（因?yàn)樗鼈兪荢2'內(nèi)部子句），也阻止了（2）（4）歸結(jié)（因?yàn)椴皇亲畲笪淖址较颍┝硪环N語(yǔ)義歸結(jié)稱為支持集策略對(duì)子句集S每次歸結(jié)時(shí)至少要有一個(gè)是要證明的目標(biāo)公式否定的子句或其后裔.這里的要證明的目標(biāo)公式的否定形式所形成的子句集即為支持集T,很顯然S-T是可滿足的.所以也可這樣理解支持集策略:每次歸結(jié)時(shí),至少有一個(gè)子句來(lái)自支持集T或由T導(dǎo)出的歸結(jié)式.例:子句集合S=｛～I(xiàn)(x)∨R(x),I(a),～R(y)∨～L(y),L(a)｝,其中I(x)∧~R(x)是要證明的結(jié)論，其否定形式是子句～I(xiàn)(x)∨R(x).利用支持集策略歸結(jié)如下:(1)～I(xiàn)(x)∨R(x)..............支持集T(2)I(a)(3)R(y)∨～L(y)(4)L(a)(5)R(a)............1,2歸結(jié)｛a/x｝(6)～L(a)...........3,5歸結(jié)｛a/y｝(7)□...............(4)(6)歸結(jié)支持集策略是完備的.3.線性歸結(jié)策略在歸結(jié)過(guò)程中,除第一次歸結(jié)可用給定的子句集S中子句（該子句稱為頂子句）外,其后各次歸結(jié)則至少要有一個(gè)親本子句是上次歸結(jié)的結(jié)果.線性歸結(jié)可用一個(gè)歸結(jié)演繹樹加以表示,例如上例中的歸結(jié)過(guò)程:線性歸結(jié)策略是完備的4.輸入歸結(jié)策略每次參加歸結(jié)的兩個(gè)親本子句，必須至少有一個(gè)子句是初始子句集S中的子句。輸入歸結(jié)策略是不完備的。例如子句集S=｛P∨Q，～P∨Q，P∨～Q，～P∨～Q｝是不可滿足的，但用輸入歸結(jié)策略不能導(dǎo)出空子句5.單元?dú)w結(jié)策略每次歸結(jié)都有一個(gè)子句是單元（只含一個(gè)文字即原子或其否定）子句或單元的因子時(shí)的歸結(jié)稱作單元?dú)w結(jié)。單元?dú)w結(jié)也是不完備的。3.2不確定性推理概述3.2.1不確定性推理知識(shí)庫(kù)是人工智能的核心，而知識(shí)庫(kù)中的知識(shí)既有規(guī)律性的一般原理，又有大量的不完全的專家知識(shí)，即知識(shí)帶有模糊性、隨機(jī)性、不可靠或不知道不確定因素。世界上幾乎沒(méi)有什么事情是完全確定的。不確定性推理即是通過(guò)某種推理得到問(wèn)題的精確判斷。（1）不確定性問(wèn)題的代數(shù)模型一個(gè)問(wèn)題的代數(shù)模型由論域、運(yùn)算和公理組成。建立不確定性問(wèn)題模型必須說(shuō)明不確定知識(shí)的表示、計(jì)算、與語(yǔ)義解釋。表示問(wèn)題：指用什么方法描述不確定性，通常有數(shù)值和非數(shù)值的語(yǔ)義表示方法。數(shù)值表示便于計(jì)算，比較，再考慮到定性的非數(shù)值描述才能較好的解決不確定性問(wèn)題。例如對(duì)規(guī)則A->B（即A真能推導(dǎo)B真）和命題（或稱證據(jù)、事實(shí)）A，分別用f(B,A)來(lái)表示不確定性度量。計(jì)算問(wèn)題：指不確定性的傳播和更新，也即獲得新的信息的過(guò)程。包括：①已知C(A),A->B,f(B,A)，如何計(jì)算C(B)②證據(jù)A的原度量值為C1(A),又得C2(A)，如何確定C(A)③如何由C(A1)和C(A2)來(lái)計(jì)算C(A1∧A2)，C(A1∨A2)等。一般初始命題/規(guī)則的不確定性度量常常由有關(guān)領(lǐng)域的專家主觀確定。語(yǔ)義問(wèn)題：是指上述表示和計(jì)算的含義是什么？即對(duì)它們進(jìn)行解釋，概率方法可以較好地回答這個(gè)問(wèn)題，例如f(B,A)可理解為前提A為真時(shí)對(duì)結(jié)論B為真的一種影響程度，C(A)可理解為A為真的程度。特別關(guān)心的是f(B,A)的值是：①A真則B真，這時(shí)f(B,A)=?

②A真則B假，這時(shí)f(B,A)=?

③A對(duì)B沒(méi)有影響時(shí)，這時(shí)f(B,A)=?對(duì)C(A)關(guān)心的值是①A真時(shí)，C(A)=?

②A假時(shí)，C(A)=?

③對(duì)A一無(wú)所知時(shí)，C(A)=?（2）不確定推理方法的分類不確定推理方法在人工智能系統(tǒng)中通常是不夠嚴(yán)謹(jǐn)?shù)?，但尚能解決某些實(shí)際問(wèn)題，符合人類專家的直覺(jué)，在概率上也可給出某種解釋。不確定性推理模型沒(méi)有一個(gè)統(tǒng)一的模型，種類不計(jì)其數(shù)，其中比較著名的有：Shortliffe在1975年結(jié)合醫(yī)療專家系統(tǒng)MYCIN建立的確定性理論Duda在1976年結(jié)合探礦專家系統(tǒng)PROSPECTOR建立的主觀Bayes推理DempsterShafer在1976年提出的證據(jù)理論Zadeh在1978年提出的可能性理論，1983年提出的模糊邏輯和邏輯推理Nilsson在1986年提出的概率邏輯Pearl在1986年提出的信任網(wǎng)絡(luò)3.2.2不確定性推理方法在以產(chǎn)生式作為知識(shí)表示的MYCIN系統(tǒng)中，第一次使用了不確定推理方法，給出了可信度作為不確定性的度量。1.規(guī)則的不確定性度量規(guī)則以A->B表示，其中前提A可以是一些命題的合取，引入可信度CF(B,A)作為規(guī)則A->B的不確定性度量。其中引入P(B)表示結(jié)論B為真的概率,P(B|A)表示在規(guī)則A->B,證據(jù)A為真的作用下結(jié)論B為真的概率。則可信度CF（B，A）表示證據(jù)A為真時(shí)，相對(duì)于P（～B）=1-P（B）來(lái)說(shuō)A對(duì)B為真的支持程度（當(dāng)CF（B，A）≥0），或