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

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

PrinciplesandApplicationofArtificialIntelligence

課程簡(jiǎn)介

本課程主要講述人工智能的基本概念、基本方法，會(huì)用搜索算法、

推理方法和機(jī)器學(xué)習(xí)求解簡(jiǎn)單問(wèn)題，如證明定理、機(jī)器推理、建造簡(jiǎn)

單的專(zhuān)家系統(tǒng)，自然語(yǔ)言分析和理解。

要求

工了解人工智能的提出，兒種智能觀(guān)，人工智能重要的研究領(lǐng)域，以

及人工智能求解問(wèn)題的方法與傳統(tǒng)的數(shù)學(xué)方法的不同；

工掌握啟發(fā)式搜索概念，會(huì)用搜索方法求解簡(jiǎn)單問(wèn)題

人掌握歸結(jié)推理方法，會(huì)用歸結(jié)法證明定理，求解問(wèn)題。

上掌握一種不確定推理方法，會(huì)建造帶有不確定推理的專(zhuān)家系統(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ù)挖掘；

L掌握自然語(yǔ)言理解的過(guò)程，會(huì)用基本的切分和語(yǔ)法分析方法做自然

語(yǔ)句分析；

工理解神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)智能的另一種觀(guā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ì)算T非數(shù)值計(jì)算（自然語(yǔ)言理解、

圖象語(yǔ)音識(shí)別、專(zhuān)家系統(tǒng)、機(jī)器博弈系統(tǒng)等等符號(hào)知識(shí)處理）

＞試探性搜索、啟發(fā)式搜索、不確定性推理方法更符合人類(lèi)思維過(guò)程。也就是

說(shuō)在解決這類(lèi)問(wèn)題時(shí)，沒(méi)有算法解或即使有算法解但在當(dāng)今計(jì)算技術(shù)不能實(shí)

現(xiàn)。對(duì)這類(lèi)問(wèn)題可行的解決方法是搜索、試探，加上經(jīng)驗(yàn)的啟發(fā)式知識(shí)。這

是一種來(lái)自專(zhuān)門(mén)領(lǐng)域的經(jīng)驗(yàn)知識(shí)，限于特定場(chǎng)合，經(jīng)常會(huì)取得成功但又不能

保證必然成功，常能求得有關(guān)問(wèn)題的滿(mǎ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ǔ)言L(fǎng)ISP/PROLOG

/發(fā)展期（1972-）——知識(shí)工程、專(zhuān)家系統(tǒng)（MYCIN,探礦系統(tǒng)）

/學(xué)習(xí)期

1.2什么是人工智能

1.什么是人類(lèi)智能？有何特點(diǎn)？計(jì)算機(jī)到底能不能有人類(lèi)智能？

英國(guó)數(shù)學(xué)家Turing于1950提出的著名的Turing實(shí)驗(yàn)。

識(shí)別、推理、聯(lián)想、自學(xué)習(xí)...（人腦的智能很復(fù)雜?。?/p>

計(jì)算機(jī)到底能不能有人類(lèi)智能，至今沒(méi)有完整的論證（人工智能是一門(mén)正在

探索和發(fā)展的學(xué)科，至今還沒(méi)有完全形成完整的理論體系。目前人工智能與人

腦的智能還相差很遠(yuǎn)）

2.什么是人工智能？

人工智能簡(jiǎn)稱(chēng)為AI（ArtificialIntel1igence）,是研究如何制造出智能機(jī)

器或智能系統(tǒng)，來(lái)模擬人類(lèi)智能活動(dòng)、延伸人類(lèi)智能的學(xué)科。

已實(shí)現(xiàn)的人工智能系統(tǒng)：

令第一個(gè)人工智能專(zhuān)家系統(tǒng)DENDRAL,能根據(jù)有機(jī)化合物的質(zhì)譜數(shù)據(jù)，推斷出給

有機(jī)化合物的分子結(jié)構(gòu)，該系統(tǒng)得到甚至超過(guò)化學(xué)專(zhuān)家水平。該系統(tǒng)是由

Stanford大學(xué)的Feigenbaum領(lǐng)導(dǎo)研制成功的。

令醫(yī)療專(zhuān)家系統(tǒng)MYCIN

令探礦專(zhuān)家系統(tǒng)PROSPECTOR

令1995年美國(guó)智能機(jī)器人駕駛汽車(chē)以55km/h速度從東部一直開(kāi)到西部（機(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ò)微觀(guān)方法直接模擬人腦和神

經(jīng)系統(tǒng)的結(jié)構(gòu)功能

令計(jì)算機(jī)方法：利用計(jì)算機(jī)科學(xué)的觀(guān)點(diǎn)，從宏觀(guā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)推理，專(zhuān)家系

統(tǒng)、博弈系統(tǒng)等。

采用這種方法的研究者稱(chē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í)別。

采用這種研究途徑稱(chēng)為生理學(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)主義”相悖。

這種方法的研究者稱(chēng)為行為主義、進(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)的觀(guān)念在發(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)空間圖、博弈樹(shù)搜索

?推理方法：歸結(jié)推理、不確定性推理

?自然語(yǔ)言理解：不僅能識(shí)別文字而且能理解文本含義的機(jī)器系統(tǒng)

?模式識(shí)別（圖象與語(yǔ)音識(shí)別）

外界信息?感受獲取電信號(hào)-一Z特征提取

?知識(shí)工程（知識(shí)獲取、知識(shí)表示、知識(shí)數(shù)據(jù)庫(kù)、知識(shí)運(yùn)用等一系列知識(shí)處

理技術(shù)，是以知識(shí)為中心來(lái)組織智能系統(tǒng)）

?神經(jīng)網(wǎng)絡(luò)技術(shù)

?專(zhuān)家系統(tǒng)

知識(shí)庫(kù)推理機(jī)

?機(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人類(lèi)智能和人工智能

1.人類(lèi)智能特性

感知能力思維能力反應(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,只需證明AA?B是不可滿(mǎn)足的”這種知識(shí)是一般性、指示性、

確定性的。而像“桌子有四條腿”這種知識(shí)是具體的、說(shuō)明性、不確定性。

知識(shí)表示是研究用機(jī)器表示知識(shí)的可行性、有效性的一般方法，是一種數(shù)據(jù)結(jié)

構(gòu)與控制結(jié)構(gòu)的統(tǒng)一體，既考慮知識(shí)的存儲(chǔ)又考慮知識(shí)的使用。知識(shí)表示可看

成是一組描述事物的約定，以把人類(lèi)知識(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)。

如事物的分類(lèi)、屬性、事物間關(guān)系、科學(xué)事實(shí)、客觀(guān)事實(shí)等，在知識(shí)庫(kù)中屬于

低層的知識(shí)。如雪是白色的、鳥(niǎo)有翅膀、張三李四是好朋友。

規(guī)則:是有關(guān)問(wèn)題中與事物的行動(dòng)、動(dòng)作相聯(lián)系的因果關(guān)系知識(shí)，是動(dòng)態(tài)的，

常以“如果...那么...”形式出現(xiàn)。特別是啟發(fā)式規(guī)則是屬于專(zhuān)家提供的專(zhuān)門(mén)

經(jīng)驗(yàn)知識(shí)，這種知識(shí)雖無(wú)嚴(yán)格解釋但很有用處。

控制:是有關(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和Bo機(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喜歡Mairy，其中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歲”，便寫(xiě)成(Lee,age,35)

事實(shí)“老李、老張是朋友”，可寫(xiě)成(friend,Lee,Zhang)

對(duì)于規(guī)則是表示事物間的因果關(guān)系，以下列形式表示：

condition->action

condition作為前件或模式，而action稱(chēng)作動(dòng)作或后件或結(jié)論。前件部分常

是一些事實(shí)Ai的合取，而結(jié)論常是某一事實(shí)B,如考慮不確定性，需另附可信

度度量值。

2.3.2產(chǎn)生式系統(tǒng)的組成和推理

多數(shù)較為簡(jiǎn)單的專(zhuān)家系統(tǒng)(ExpertSystem)都是以產(chǎn)生式表示知識(shí)的，相

應(yīng)的系統(tǒng)稱(chē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ù)是專(zhuān)家系統(tǒng)的核心。規(guī)則可表成與或樹(shù)形式，基于數(shù)據(jù)庫(kù)中

的事實(shí)對(duì)這與或樹(shù)的求值過(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é)論，或稱(chēng)數(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)題稱(chēng)作控制策略。正向推理會(huì)得出一些與目

標(biāo)無(wú)直接關(guān)系的事實(shí)，是有浪費(fèi)的。

反向推理：從目標(biāo)（作為假設(shè)）出發(fā)，反向使用規(guī)則，求得已知事實(shí)，或稱(chēng)

目標(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)造專(zhuān)家系統(tǒng)的第一選擇的知識(shí)表示方法。

2.4語(yǔ)義網(wǎng)絡(luò)表示法

邏輯表示法和產(chǎn)生式表示法常用于表示有關(guān)論域中各個(gè)不同狀態(tài)間的關(guān)系，

然而用于表示一個(gè)事物同其各個(gè)部分間的分類(lèi)知識(shí)就不方便了。槽（slot）與

填槽表示方法便于表示這種分類(lèi)知識(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í)“雪是白色的”，可表示成：

顏色

,雪,

A白色的

如規(guī)理“如果A那么B"，可表示成:

R

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）可寫(xiě)成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型

⑴ISA鏈用來(lái)表示具體-抽象關(guān)系，或說(shuō)表示一種隸屬關(guān)系，體現(xiàn)某種層次分類(lèi)。

特點(diǎn)是具體層結(jié)點(diǎn)可繼承抽象層結(jié)點(diǎn)的屬性。

特點(diǎn)是part-of

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)系下

的推理是直接繼承，如：

便有：

--------isa--------

A-------------->C

也可以將語(yǔ)義網(wǎng)絡(luò)引入邏輯含義，表示出A,V,?關(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”中提

出了框架理論。其基本觀(guān)點(diǎn)是人腦已存儲(chǔ)有大量典型情景，當(dāng)人面臨新的情景

時(shí)，就從記憶中選擇一個(gè)稱(chēng)為框架的基本知識(shí)結(jié)構(gòu)，這個(gè)框架是以前記憶的一

個(gè)知識(shí)空框，而其具體內(nèi)容依新的情景而改變，對(duì)這空框的細(xì)節(jié)加工修改和補(bǔ)

充，形成對(duì)新情景的認(rèn)識(shí)又記憶于人腦中。框架理論將框架視作的知識(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)完成

的。

框架表示法是一種適應(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)稱(chē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)就成了框架表示法。

框架是表示某一類(lèi)情景的結(jié)構(gòu)化的一種數(shù)據(jù)結(jié)構(gòu)。框架由框架名和一些槽

（slot）組成，每個(gè)槽有一些值，槽值可以是邏輯的、數(shù)字的，可以是程序、

條件、默認(rèn)值或是一個(gè)子框架。槽值含有如何使用框架信息、下一步可能發(fā)生

的信息、預(yù)計(jì)未實(shí)現(xiàn)該如何做的信息等。

框架的一般格式：

FRAMEWORK：<frameworkname>

<slot1>

<face11>:value

<faceln>:value

<slot2>

<face21>:value

<face2n>:value

例：

framework:〈大學(xué)教師》

類(lèi)屬:〈教師＞

學(xué)歷:（學(xué)士，碩士，博士）

專(zhuān)業(yè):〈學(xué)科專(zhuān)業(yè)〉

職稱(chēng)：（助教，講師，副教授，教授）

外語(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ù)中的框架為

槽名

年齡：NIL

if-needed:ASK

if-added:CHECK

在推理的過(guò)程中便啟動(dòng)了if-needed和if-added兩個(gè)槽的附加過(guò)程ASK和

CHECKo

4.5.4框架與產(chǎn)生式表示法的比較

productionframework

知識(shí)表示

規(guī)則框架

單位

推理固定、與知識(shí)庫(kù)獨(dú)立可變，與知識(shí)庫(kù)成一體

建立知識(shí)

容易困難

庫(kù)

通用性低高

應(yīng)用簡(jiǎn)單問(wèn)題復(fù)雜問(wèn)題

用戶(hù)初學(xué)者專(zhuān)家

2.6面向?qū)ο蟮谋硎痉?/p>

2.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,ql,q2,…,qn）,其中qi為集合的分量，稱(chēng)為狀態(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,G）

狀態(tài)空間的圖示形式稱(chēng)為狀態(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與/或樹(shù)表示法

1、與或樹(shù)的概念

用一個(gè)類(lèi)似圖的結(jié)構(gòu)來(lái)表示把問(wèn)題歸約為后繼問(wèn)題的替換集合，畫(huà)出歸約問(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è)或樹(shù)來(lái)表示。

2、與或樹(shù)的有關(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)集合；

弧線(xiàn)是父輩節(jié)點(diǎn)指向子節(jié)點(diǎn)的圓弧連線(xiàn)；

終葉節(jié)點(diǎn)是對(duì)應(yīng)于原問(wèn)題的本原節(jié)點(diǎn)。

3、與或樹(shù)的有關(guān)定義

可解節(jié)點(diǎn)與或樹(shù)中一個(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、與或樹(shù)構(gòu)樹(shù)規(guī)則

(1)與或樹(shù)中的每個(gè)節(jié)點(diǎn)代表?個(gè)要解決的單一問(wèn)題或問(wèn)題集合。樹(shù)中所含起始節(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)題集合；有向弧線(xiàn)自A指向

后繼節(jié)點(diǎn)，表示所求得的子問(wèn)題集合。

(4)一般對(duì)于代表兩個(gè)或兩個(gè)以上子問(wèn)題集合的每個(gè)節(jié)點(diǎn)，有向弧線(xià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（xl,x2,x3,...xn）

其中：

P是謂詞符號(hào)，表示xl,x2,x3,...xn個(gè)體對(duì)象之間的屬性、狀態(tài)或關(guān)系。

xl,x2,x3,...xn是謂詞的參量（或稱(chēng)項(xiàng)），一般表示個(gè)體，它可以是個(gè)體常

量、個(gè)體變量或是個(gè)體函數(shù)。個(gè)體變?cè)淖兓秶Q(chēng)為個(gè)體域（或論域）

例：

口（外：表示乂是素?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)有大寫(xiě)字母表示，如P,Q,R,S等；（2）用小寫(xiě)字母

x,y,z等作為個(gè)體變?cè)?hào)；（3）用小寫(xiě)字母a,b.c等作為個(gè)體常元符號(hào)；

（4）用小寫(xiě)字母f,g,h表示個(gè)體函數(shù)符號(hào)。

?量詞

全稱(chēng)量詞：“所有”，“一切”，“任一”，“全體”，“凡是”等詞稱(chēng)為全稱(chēng)

量詞，記為“x

存在量詞：“存在”、“有些”、“至少有一個(gè)”、“有的”等詞統(tǒng)稱(chēng)為存

在量詞，記為mx

引入量詞和連接符（一蘊(yùn)涵，八合取，▽析取，否定詞?）之后，謂詞的表

達(dá)能力大大擴(kuò)充了

例1:

謂詞M(x):表示x是人，謂詞N(x):表示x有名字，則\*(14a)一爪9)表示

“凡是人都有名字”。

例2：

謂詞G(x):表示x是整數(shù),E(x)：表示x是偶數(shù)，則mx(G(x)八?E(x))表示

“存在不是偶數(shù)的整數(shù)”

例3：知識(shí)“不存在最大的整數(shù)”的表示

設(shè)：謂詞G(x):表示x是整數(shù)，D(x,y)表示x大于y。則表示如下：

?三x(G(x)AVy(G(y)-*D(x,丫)))或外&&)A3y(G(y)AD(y,x)))

?謂詞公式：用謂詞、量詞(存在量詞，全稱(chēng)量詞)、聯(lián)接詞(一蘊(yùn)涵，A合取,

▽析取)連接而成的復(fù)雜的符號(hào)表達(dá)式稱(chēng)為謂詞公式。

3.1.2命題邏輯的歸結(jié)法

］概念，

不帶參數(shù)(肯定也不含量詞))的謂詞稱(chēng)為命題.

謂詞的表達(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受法律管制；

COMM^'(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)涵，八合取，V析取，等價(jià)否定詞~)將命題連接在一起構(gòu)

成命題公式。

A->B,A稱(chēng)為前件，B稱(chēng)為后件，其真值表如下所示：

ABA->B

001

011

100

111

A<->B等價(jià)于(A->B)A(B->A)

—*叱概念.

4藁：真值為T(mén)的命題公式稱(chēng)為永真式或重言式或有效的。

永假式：真值為F的命題公式稱(chēng)為永假式或不可滿(mǎn)足的。

非永真式：不是永真式的命題公式；

可滿(mǎn)足式：不是永假公式的命題公式；

原子公式:不含任何連接詞的命題公式稱(chēng)為原子公式或稱(chēng)原子.例如P,Q

文字:原子公式及其否定形式稱(chēng)為文字.例如P,?L

子句:文字的析取稱(chēng)為子句.例如:PVRV?Q

互補(bǔ)文字：設(shè)L為一個(gè)文字，則稱(chēng)L與?L為互補(bǔ)文字。

一些有用的等價(jià)關(guān)系：

~~A<=>A雙重否定

AAA<=>A

AVA<=>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)<=>~A八~B

A—B<=>-AVB蘊(yùn)含表達(dá)式

A<->B<=>(A-*B)A(B-*A)

AAT<=>A

AAF<=>F等價(jià)表達(dá)式

AVT<=>T

AVF<=>A

AA~A<=>F矛盾律

AV-A<=>T排中律

A-(B->CX=>AAB-*C輸出律

(AtB)A(A—~B)<=>~A歸謬律

A->B<=>~B—~A逆反律

2命題邏輯中的歸結(jié)推理方法

若命題邏輯描述的命題Al,A2,??.An和B,要證明在AlAA2八.?.AAn成立的

條件下有B成立，或說(shuō)A1AA2八…八AnfB。很顯然A1AA2A...AAnfB等價(jià)

于證明A1AA2A...AAn八?B是矛盾(永假)式。歸結(jié)推理的方法就是從A1AA2

A...AAnA?B出發(fā)使用歸結(jié)推理規(guī)則來(lái)尋找矛盾，從而證明A1AA2A...A

An-B的成立。這種方法稱(chēng)為反演推理方法。

3歸結(jié)式

設(shè)有兩個(gè)子句

ci=pvcr

C2=~PVC2'

從中消去互補(bǔ)對(duì)一，所得新子句R(C1,C2)=C1'VC2',稱(chēng)為子句Cl',C2'的歸結(jié)

式。沒(méi)有互補(bǔ)對(duì)的兩子句沒(méi)有歸結(jié)式。

歸結(jié)推理規(guī)則就指的是對(duì)兩子句做歸結(jié)，也即求歸結(jié)式。

下面證明歸結(jié)推理規(guī)則是正確的，即C1AC2=>R(C1,C2),也即證明歸結(jié)式是兩

子句的邏輯結(jié)論，或者說(shuō)任一使Cl,C2為真的解釋I下必有R(C1,C2)也為真。

證：設(shè)I是使Cl,C2為真的任一解釋?zhuān)粼贗下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=P,C2=~P時(shí),R(C1,C2)=口，記作為空子句。顯然Cl,C2同時(shí)

為真是矛盾，或者說(shuō)空子句口體現(xiàn)了矛盾。

4命題邏輯的歸結(jié)推理過(guò)程

(1)利用邏輯蘊(yùn)含式和邏輯等價(jià)式將命題公式化成合取范式(子句的析取)

(2)子句集：將若干個(gè)子句的合取式中的合取詞人換成逗號(hào)，形成的集合稱(chēng)

為子句集。

(3)從子句集S出發(fā)，僅只對(duì)S的子句間使用歸結(jié)推理規(guī)則(即求歸結(jié)式)，

并將所得歸結(jié)式仍放入S中，進(jìn)而再對(duì)新子句集使用歸結(jié)推理規(guī)則，重復(fù)這

些步驟直到得到空子句口(說(shuō)明有矛盾)。便說(shuō)明S是不可滿(mǎn)足的，從而與

子句集S對(duì)應(yīng)的定理是成立的。

例：證明(PfQ)A?Q==>?P

證：

先將已知以及結(jié)論的反化成合取范式

(?PVQ)八?QA(??P)==>(?PVQ)A?QAP,建立子句集S={?PVQ,?

Q,P)

對(duì)S作歸結(jié)

⑴?PVQ

⑵?Q

⑶P

(4)?P..........................對(duì)(1)(2)求歸結(jié)式

(5)口..............對(duì)(3)(4)求歸結(jié)式

得證。

例:證明(PfQ)A(R-?Q)==>(Rf?P)

證明:將已知以及結(jié)論的反化成合取范式

==〉(?PVQ)A(?RV?Q)A(?(?RV?P))

==>(?PVQ)A(?RV?Q)ARAP化成子句集

S={-PVQ,?RV?Q,R,P}，對(duì)S做歸結(jié)：

⑴?PVQ

(2)?RV?Q

(3)R

(4)P

(5)?Q...(2)(3)歸結(jié)

(6)Q...(1)(4)歸結(jié)

(7)口...(5)(6)歸結(jié)

3.L3謂詞公式的子句集

1合取范式和析取范式

(1)合取范式:若謂詞公式A有如下形式B1AB2A...ABn,其中Bi(i=l,2,...n)

形如L1VL2V...VLn,并且LI,L2,...Ln都是文字。例：

(P(x)V?Q(y))八(?P(x)VR(x,y))八(?Q(y)V?R(x,y))

應(yīng)用邏輯等價(jià)式可以將任一謂詞公式化成合取范式。

(2)析取范式:若謂詞公式A有如下形式BlVB2V...VBn,其中析(i=l,2,...n)

形如L1AL2A...ALn,并且LI,L2,...Ln都是文字。例：

(P(x)/-Q(y)^R(x,y))y(-P(x)/\R(x,y))

應(yīng)用邏輯等價(jià)式和邏輯蘊(yùn)含式可以將任一謂詞公式化成析取范式。

(3)前束范式:將所有的量詞都放在謂詞公式的前面。如

mx〃y(P(x,y)AQ(a)八R(z))就是前束范式。

Vx(N(x)A3yD(y,x))就不是前束范式。前束范式可分成前束合取范式和前束析

取范式。

化成前束合取范式的步驟：

?stepl:去掉多余的量詞，即沒(méi)意義的量詞

?step2:將同名的約束變?cè)c自由變?cè)拿?，使它們不同名?/p>

?消去A,V,~以外的連接詞

A->B........................?AVB

A<->B......................CAVB)ACBVA)

?step4:將連接詞?內(nèi)移，移到原子公式之前

?(?A)=A

?(AAB)<=>?AV?B

?(AVB)<=>?AA?B

?*xA(x)<=>^x?A(x)

xA(x)<=>Vx?A(x)

?step5:將量詞盡可能向左推，推到前綴所在的位置，用下列公式：

3xA(x)VB...........3X(A(x)VB),其中B中不含約束變?cè)?/p>

BV3XA(X)...........3x(BVA(x)),其中B中不含約束變?cè)?/p>

VxA(x)VB............Vx(A(x)VB),其中B中不含約束變?cè)?/p>

BVVxA(x)............Vx(BVA(x)),其中B中不含約束變?cè)?/p>

同樣對(duì)上面式子中的▽改為A可得到另一組關(guān)于的A的替換式。

另外還可用下式進(jìn)行替換：

VxA(x)A^xB(x).................Vx(A(x)AB(x))

^xA(x)V^xB(x).................(A(x)VB(y))，采用更名規(guī)則

3

3xA(x)VXB(X).................3X(A(x)VB(x))

3XA(X)A3XB(X).................3x3y(A(x)AB(y))，采用更名規(guī)則

?step6:使用A,V的分配律化成合取范式。

例：將下列謂詞公式化成前束合取范式：

網(wǎng)((。尸⑸vVzQ(z,))>V亦限詡

=Vx((尸(x)vVzQ(zj))7-VyR(xM)

=>Vx((P(x)vVzQ(zj))

=>Vx((p(x)VVzg(z,7))-?

nVx(?(尸(x)vVzQ(zj))\/加~R(x,u))

=Vx((~P(x)A3Z-Q(z,y))7m然~R(x,u))

=Vx(3z(~P(x)/\~Q(z,y))vBu~&(尤必))

nVx王力((~產(chǎn)Q(zj))V~氏(x,〃))

=Vx生土((?產(chǎn)(x)v?八(?Q(z,y)v?&

(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分兩種情況：

①若該存在量詞在某些全稱(chēng)量詞的轄域內(nèi)，則用這些全稱(chēng)量詞指導(dǎo)變?cè)囊?/p>

個(gè)函數(shù)代替該存在量詞轄域中的相應(yīng)約束變?cè)@樣的函數(shù)稱(chēng)為Skolem函數(shù);

②若該存在量詞不準(zhǔn)任何全稱(chēng)量詞的轄域內(nèi)，則用一個(gè)常量符號(hào)代替該存在

量詞轄域中相應(yīng)約束變?cè)@樣的常量符號(hào)稱(chēng)為Skolem常量；

?消去所有全稱(chēng)量詞

?消去合取詞A,用逗號(hào)代替，以子句為元素組成一個(gè)集合S,即是謂詞公式

的子句集

例1：求謂詞公式G=^x3y3z((?P(x,y)VR(x,y,z))A(Q(x,z)VR(x,y,z)))

的子句集。

解：

已經(jīng)是前束范式，并且不含連接詞。由于存在量詞y,z都在全稱(chēng)量詞x的轄

域中，所以將y,z分別用Skolem函數(shù)f(x)、g(x)代替。

“x((~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：求謂詞公式的子句集:Vx(*yP(x,y)-*~"y(Q(x,y)-*R(x,y)))

解：Vx(VyP(x,y)-*?%(Q(x,y)-*R(x,y)))

==>Vx(VyP(x,y)fmy?(~Q(x,y)VR(x,y)))

==>"x(VyP(x,y)fmy(Q(x,y)A~R(x,y)))

==>Vx(%P(x,y)fmz(Q(x,z)八?R(x,z)))…改名

==>VX3y(p(x,y)Z(Q(x,z)A~R(x,z)))...量詞分配率

==>^x3產(chǎn)z(P(x,y)f(Q(x,z)A~R(x,z)))...量詞分配率

==>VX3y3z(?P(x,y)V(Q(x,z)A~R(x,z)))

==>VX3y3z[(?P(x,y)VQ(x,z))A(?P(x,y)V?R(x,z))]...分配律

==>"x[(?P(x,f(x))VQ(x,g(x)))A(~P(x,f(x))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=mx4y4z閂w(P(x,y,z)A~Q(u,v,w)),求其子句集

解：三xVyVz3uVv3w(P(x,y,z)八?Q(u,v,w)

==>VyVz3uVv3w(p(a>y,z)A-Q(u,v,w))..........消去x=a(常數(shù))

==>VyVzVvaw(p(a)y,z)A~Q(f(y,z),v,w))..........消去u=f(y,z)

==>VyVzVv(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ì)角線(xiàn)與上下底構(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|uv

E(x,y,z,u,v,w)表示Nxyz=Nuvw,問(wèn)題的描述和相應(yīng)的子句集為

VxVyVuVv[T(x,y,u,v)-*P(x,y,u,v)]...梯形上下底平行

子句：?T(x,y,u,v)\/P(x,y,u,v)

VxVyVuVv[p(x；y,.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é)到的替換和合一知識(shí)之后可給出證明過(guò)程。

3.1.4Herbrand理論：

證明一個(gè)謂詞公式的不可滿(mǎn)足性是困難的，這是因?yàn)橹^詞中個(gè)體變量的論域D

的任意性，以及解釋的個(gè)數(shù)的無(wú)限性。例如：

「&):代表*是偶數(shù)。

若x的論域?yàn)?={2,4,6,8},則P是永真式，是可滿(mǎn)足的；

若x的論域?yàn)榭?{1,3,5,7},則P是永假式，是不可滿(mǎn)足的；

若x的論域?yàn)榭?{1,2,5,8},則P的真值與取論域D上的解釋有關(guān)；

所以如果對(duì)一個(gè)具體的謂詞公式能找到一個(gè)比較簡(jiǎn)單的特殊的論域，使得只要

在這個(gè)論域上該公式是不可滿(mǎn)足的，便能保證該公式在任一論域上也是不可滿(mǎn)

足的。所要建立的Herbrand域(簡(jiǎn)稱(chēng)H域)就具有這樣的性質(zhì)。

1H域

設(shè)G是謂詞公式，定義在論域D上，令H。是G中所出現(xiàn)的常量的集合。若G中

沒(méi)有常量出現(xiàn)，就任取常量a￡D,而規(guī)定H°={a}；

U{所有形如f(\tl….tn)的元素},

其中f(tl,...,tn)是出現(xiàn)于G中的任一函數(shù)符號(hào)，而tl...tn是Hi-1的元素，

i=l,2,...o

規(guī)定上為G的H域。不難看出H域是直接依賴(lài)于G的最多只有可數(shù)個(gè)元素。

例1：S={P(a),~P(x)VP(f(x))},依H域的定義有：

HO={a}

Hl={a}U{f(a)}={a,f(a)}

H2={a,f(a)}U{f(a),f(f(a))}={a,f(a),f(f(a))}

H0°={a,f(a),f(f(a)),…}

例2：S={~P(z),P(x)V~Q(y)}

依定義有

HO={a}a是論域D中的一個(gè)常量

H1=HO

H2=H1

H0°={a}

例3：S={P(f(x),a,g(y),b)}

依定義有

HO={a,b}

Hl={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(

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?==HOUH1UH2U....

注意：如果在謂詞或子句集中出現(xiàn)函數(shù)形如f(x,a)仍視為f(x,y)的形式，這時(shí)

若H0={a,b},則Hl中除有f(a,a),f(b,a)外,還出現(xiàn)f(a,b),f(b,b)o

為了討論在H域上子句集S中各謂詞的真值。令集合

A={所有形如P(tl,t2,...,tn)的元素}

稱(chēng)為子句集S(或公式G)的原子集。其中是出現(xiàn)于S中的任

一謂詞符號(hào)，而是S的H域的任意元素。

上述例1中的原子集為A={P(a),P(f中))原子集為)))，...}

上述例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))}

依定義有上匕,￡5),￡(￡1)),...}

原子集

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,就

可依賴(lài)于在H域上的某個(gè)解釋I*來(lái)實(shí)現(xiàn)。也就是子句集S在D上的不可滿(mǎn)足問(wèn)

題轉(zhuǎn)化成了在H上的不可滿(mǎn)足問(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(l,1)—f(l,2)—f(2,1)—f(2,2)

2—1--------2--------2---------1——

P(D—P(2)—Q(l,1)—Q(l,2)—Q(2,D—Q(2,2)

T______T_______p_________T________T________F

于是有

---x=l,y=l---x=l,y=2---x=2,y=l---x=2,y=2一

S|I=P(1)AQ(l,f(l,2))AP(1)AQ(2,f(2,1))AP(2)AQ(1,f(1,2))AP(2)A

Q(2,f(2,2))

=T

可按下列方法選取相應(yīng)的r,

a—2

f(a,a)-*f(2,2)-*l

f(a,f(a,a))ff(2,1)-2

f(f(a,a),a)-f(f(2,2),2)ff(1,2)-2

f(f(a,a),f(a,a))-*f(1,1)-*1

P(a)-P⑵-T

Q(a,a)-Q(2,2)-F

P(f(a,a))-P(l)T

Q(a,f(a,a))-Q(2,1)=T

Q(f(a,a),a)-Q(l,2)=T

Q(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))

5???}

顯然

S|I*=T

例2求5=付&)位0))小(￡6))}的H域、原子集A,I*解釋。

仍然設(shè)D={1,2},解釋I設(shè)定如下：

f(1)—f(2)—P(l)—P(2)—Q(l)—Q(2)—R(l)—R(2)

2______2_____T_____F_____p_____T______F____T

于是由S|I=P⑴VQ(1)AR(f(D)AP(1)VQ(1)AR(f(2))AP(2)VQ(2)A

R(f(l))AP(2)VQ(2)AR(f(2))=T

設(shè)a=l,則相應(yīng)的解釋為：

H*={P(a),?Q(a),?R(a)/P(f(a)),Q(f(a)),R(f(a)),...}

S|I1=T

定理：設(shè)I是S的論域D上的解釋?zhuān)嬖趯?duì)應(yīng)于I的H解釋I*,使得若有S|I=T,

必有S|I*=T

定理：子句集S是不可滿(mǎn)足的，當(dāng)且僅當(dāng)在所有的S的H解釋下為假。

定理：子句集S是不可滿(mǎn)足的當(dāng)且僅當(dāng)對(duì)每個(gè)解釋I下，至少有S的某個(gè)子句

的某個(gè)基例為假。

3語(yǔ)義樹(shù)

討論S的不可滿(mǎn)足性問(wèn)題，可將S的所有解釋展現(xiàn)在一棵二叉樹(shù)上(這是一個(gè)

完全二叉樹(shù))，但要依賴(lài)于S的H解釋以及S的原子集A。

例：對(duì)子句集S={P(x)VQ(y)/P(a),~Q(b)}畫(huà)出相應(yīng)的語(yǔ)義樹(shù)

因?yàn)镠={a,b}

A={P(a),Q(a),P(b),Q(b)}從A出發(fā)可畫(huà)出語(yǔ)義樹(shù)(部分)

N41N42N43N44

為了方便常以I(N)表示從根結(jié)點(diǎn)到結(jié)點(diǎn)N分支上所標(biāo)記的所有文字的集合。

例如I(N32)={P(a),Q(a),~P(b)},I(N42