人工智能原理與應用 教案

人工智能原理與應用

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

productionframework知識表示單位規(guī)則框架推理固定、與知識庫獨立可變，與知識庫成一體建立知識庫容易困難通用性低高應用簡單問題復雜問題用戶初學者專家2.6面向對象的表示法2.7腳本表示法2.8過程表示法2.9狀態(tài)空間表示法：用來表示問題及其搜索過程的一種方法。1．問題狀態(tài)空間的構成（1）狀態(tài)：是描述問題求解過程中不同時刻狀況的數據結構。一般用一組變量的有序集合表示：Q＝（q0,q1,q2,…,qn）,其中qi為集合的分量，稱為狀態(tài)變量。當一個分量以確定的值時，就得到一個具體的狀態(tài)。（2）算符：引起狀態(tài)中某些分量發(fā)生變化，從而使問題由一個狀態(tài)轉變?yōu)榱硪粋€狀態(tài)的操作。（3）狀態(tài)空間：由表示一個問題的全部狀態(tài)及一切可用算符構成的集合。一般由三部分構成：問題的所有可能的初始狀態(tài)構成的集合S，算符集合F，目標狀態(tài)集合G，用一個三元組表示：（S，F，G）狀態(tài)空間的圖示形式稱為狀態(tài)空間圖，其中，節(jié)點表示狀態(tài)，有向邊表示算符。（4）問題的解：從問題的初始狀態(tài)集S出發(fā)，經過一系列的算符運算，到達目標狀態(tài)，由初始狀態(tài)到目標狀態(tài)所用算符的序列就構成了問題的一個解。2．用狀態(tài)空間表示問題的步驟（1）定義問題狀態(tài)的描述形式（2）用所定義的狀態(tài)描述形式吧問題的所有可能的狀態(tài)都表示出來，并確定出問題的初始狀態(tài)集合描述和目標狀態(tài)集合描述。（3）定義一組算符，使得利用這組算符可把問題由一種狀態(tài)轉變到另一種狀態(tài)。3．利用狀態(tài)空間求解問題的過程例：二階Hanoi塔問題（見P72）解：第一步，定義問題狀態(tài)的描述形式第二步，用所定義的狀態(tài)描述形式把問題的所有可能的狀態(tài)都表示出來，并確定出問題的初始狀態(tài)集合描述和目標狀態(tài)集合描述第三步，定義一組算符2.10與/或樹表示法1、與或樹的概念用一個類似圖的結構來表示把問題歸約為后繼問題的替換集合，畫出歸約問題圖。例如，設想問題A需要由求解問題B、C和D來決定，那么可以用一個與圖來表示；同樣，一個問題A或者由求解問題B、或者由求解問題C來決定，則可以用一個或樹來表示。2、與或樹的有關術語父節(jié)點是一個初始問題或是可分解為子問題的問題節(jié)點；子節(jié)點是一個初始問題或是子問題分解的子問題節(jié)點；或節(jié)點只要解決某個問題就可解決其父輩問題的節(jié)點集合；與節(jié)點只有解決所有子問題，才能解決其父輩問題的節(jié)點集合；弧線是父輩節(jié)點指向子節(jié)點的圓弧連線；終葉節(jié)點是對應于原問題的本原節(jié)點。3、與或樹的有關定義可解節(jié)點與或樹中一個可解節(jié)點的一般定義可以歸納如下：(1)終葉節(jié)點是可解節(jié)點(因為它們與本原問題相關連)。(2)如果某個非終葉節(jié)點含有或后繼節(jié)點，那么只有當其后繼節(jié)點至少有一個是可解的時，此非終葉節(jié)點才是可解的。(3)如果某個非終葉節(jié)點含有與后繼節(jié)點，那么只要當其后繼節(jié)點全部為可解時，此非終葉節(jié)點才是可解的。不可解節(jié)點不可解節(jié)點的一般定義歸納于下：(1)沒有后裔的非終葉節(jié)點為不可解節(jié)點。(2)如果某個非終葉節(jié)點含有或后繼節(jié)點，那么只有當其全部后裔為不可解時，此非終葉節(jié)點才是不可解的。(3)如果某個非終葉節(jié)點含有與后繼節(jié)點，那么只要當其后裔至少有一個為不可解時，此非終葉節(jié)點才是不可解的。4、與或樹構樹規(guī)則(1)與或樹中的每個節(jié)點代表一個要解決的單一問題或問題集合。樹中所含起始節(jié)點對應于原始問題。(2)對應于本原問題的節(jié)點，叫做終葉節(jié)點，它沒有后裔。(3)

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

消取存在量詞時，還要進行變元替換。變元替換分兩種情況：

①若該存在量詞在某些全稱量詞的轄域內，則用這些全稱量詞指導變元的一個函數代替該存在量詞轄域中的相應約束變元，這樣的函數稱為Skolem函數；

②若該存在量詞不在任何全稱量詞的轄域內，則用一個常量符號代替該存在量詞轄域中相應約束變元，這樣的常量符號稱為Skolem常量；消去所有全稱量詞消去合取詞∧，用逗號代替，以子句為元素組成一個集合S，即是謂詞公式的子句集例1：求謂詞公式G=xyz((～P(x,y)∨R(x,y,z))∧(Q(x,z)∨R(x,y,z)))的子句集。解：已經是前束范式，并且不含連接詞。由于存在量詞y,z都在全稱量詞x的轄域中，所以將y,z分別用Skolem函數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))))已經是合取范式了，所以謂詞公式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：設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（常數）==>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標準型從而G的子句集是｛P(a,y,z)，～Q(f(y,z),v,g(y,z,v))｝例4:將機器證明"梯形的對角線與上下底構成的內錯角相等"給出邏輯描述,建立子句集合.解：設梯形頂點依次為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，問題的描述和相應的子句集為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)]...平行則內錯交相等子句：T(a,b,c,d)...已知子句：T(a,b,c,d)E(a,b,d,c,d,b)...要證明的結論子句：～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)｝

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

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

③A對B沒有影響時，這時f(B,A)=?對C(A)關心的值是①A真時，C(A)=?

②A假時，C(A)=?

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