人工智能原理與應用

PrinciplesandApplicationofArtificialIntelligence

課程簡介

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

推理方法和機器學習求解簡單問題，如證明定理、機器推理、建造簡

單的專家系統，自然語言分析和理解。

要求

工了解人工智能的提出，兒種智能觀，人工智能重要的研究領域，以

及人工智能求解問題的方法與傳統的數學方法的不同；

工掌握啟發式搜索概念，會用搜索方法求解簡單問題

人掌握歸結推理方法，會用歸結法證明定理，求解問題。

上掌握一種不確定推理方法，會建造帶有不確定推理的專家系統。

上了解其它的推理方法；

上掌握知識的表示方法，會用來表達某一具體的場景；

工掌握機器學習概念和學習模型，會用實例學習方法進行學習，

工了解數據挖掘的過程，會用關聯規則挖掘算法做數據挖掘；

L掌握自然語言理解的過程，會用基本的切分和語法分析方法做自然

語句分析；

工理解神經網絡實現智能的另一種觀點。掌握BP神經網的工作原理,

會用來求解（如識別）問題；

工了解遺傳算法（GA）概念及如何使用遺傳算法

參考資料：

《人工智能原理與應用》，張仰森，高等教育出版社

《人工智能》，蔡自興

《人工智能原理》，石純一黃昌寧王家欽編著，清華大學出版社

《人工智能》（上下冊），陸汝鈴編著，科學出版社，1996

《人工智能與知識工程》，田盛豐、黃厚寬，中國鐵道出版社，1999

《高級人工智能》，史忠植，科學出版社，1998

《人工智能基礎》，高濟、朱森良、何欽銘，高等教育出版社，2002

第一章人工智能概述

1.1人工智能的起源與發展

＞計算機所能處理對象的改變：純粹數值計算T非數值計算（自然語言理解、

圖象語音識別、專家系統、機器博弈系統等等符號知識處理）

＞試探性搜索、啟發式搜索、不確定性推理方法更符合人類思維過程。也就是

說在解決這類問題時，沒有算法解或即使有算法解但在當今計算技術不能實

現。對這類問題可行的解決方法是搜索、試探，加上經驗的啟發式知識。這

是一種來自專門領域的經驗知識，限于特定場合，經常會取得成功但又不能

保證必然成功，常能求得有關問題的滿意解答。

醫生一定能根據病人的癥狀診斷出是何種疾病嗎？我們能用傳統的算法設

計一個程序進行疾病診斷嗎？能用傳統的算法設計一個程序能理解自然語言所

組成的文檔的含義嗎？

以上原因促使人工智能學科的誕生。

主要經歷了以下幾個階段：

/孕育期（1956年以前）一一從理論、技術和物質上奠定基礎

/成長期（1956—1972）——邏輯推理機程序、跳棋程序、通用問題求解

（GPS:GeneralProblemSolver）,人工智能程序設計語言LISP/PROLOG

/發展期（1972-）——知識工程、專家系統（MYCIN,探礦系統）

/學習期

1.2什么是人工智能

1.什么是人類智能？有何特點？計算機到底能不能有人類智能？

英國數學家Turing于1950提出的著名的Turing實驗。

識別、推理、聯想、自學習...（人腦的智能很復雜?。?/p>

計算機到底能不能有人類智能，至今沒有完整的論證（人工智能是一門正在

探索和發展的學科，至今還沒有完全形成完整的理論體系。目前人工智能與人

腦的智能還相差很遠）

2.什么是人工智能？

人工智能簡稱為AI（ArtificialIntel1igence）,是研究如何制造出智能機

器或智能系統，來模擬人類智能活動、延伸人類智能的學科。

已實現的人工智能系統：

令第一個人工智能專家系統DENDRAL,能根據有機化合物的質譜數據，推斷出給

有機化合物的分子結構，該系統得到甚至超過化學專家水平。該系統是由

Stanford大學的Feigenbaum領導研制成功的。

令醫療專家系統MYCIN

令探礦專家系統PROSPECTOR

令1995年美國智能機器人駕駛汽車以55km/h速度從東部一直開到西部（機器

視覺）

令1997年國際象棋大師卡斯帕羅夫與IBM深藍巨型機上的博弈系統對弈

令自然語言理解系統

令機器翻譯系統

令機器證明系統（證明了“四色問題”、數學中的定理）

1.3AI的研究途徑、方法、不同學派

1.目標：

近期目標：使機器更聰明

遠期目標：探討研制智能機

2.方法、途徑

令仿生學方法：對人腦思維進行生理學模擬，通過微觀方法直接模擬人腦和神

經系統的結構功能

令計算機方法：利用計算機科學的觀點，從宏觀上模擬人的智能活動

令數學方法：建立數學模型，利用算法求解問題

令心理學方法：建立心理學模型，利用啟發式程序求解問題

3.人工智能研究的各種學派及其理論

令功能模擬，符號演繹

模擬人腦的邏輯思維，將問題和知識表示成某種邏輯網絡，采用符號推

演的方法，實現搜索、推理、學習等功能。這種方法目前還在使用，人工智

能研究中的很多成果都是用該方法取得的，如定理證明，自動推理，專家系

統、博弈系統等。

采用這種方法的研究者稱為心理學派或邏輯學派或符號主義，代表人物

是NILSSON,本課程就是講解這種研究方法。

令結構模擬，神經網絡計算

根據人腦的生理結構和工作機理，研究和實現計算機智能。因為人腦是

由神經細胞組成的神經網絡，所以該研究途徑就是用人工神經元組成的人工

神經網絡模型來存儲信息和知識，用神經計算（數值計算）的方法實現自學

習、聯想、識別和推理功能。神經網絡具有高度的并行分布性。該研究方法

適于實現圖象、聲音信息識別。

采用這種研究途徑稱為生理學派或連接主義，代表人物是Newell

令行為模擬，控制進化

這種方法模擬人在控制過程中的智能活動和行為特性（自尋優，自適應，

自學習），強調“現場AI”（situatedAI）即智能系統或智能機器能與環

境交互，能對環境進行感知從而表現出智能行為，也就是說智能行為不需要

知識從而與“符號主義”相悖。

這種方法的研究者稱為行為主義、進化主義或控制論學派。代表人物是

MIT的Brooks教授。

人工智能是引起爭議最多的學科之一，因而各種研究學派在發展的過程

都經歷了許多挫折.

?通過什么途徑有效地實現智能（如符號演繹推理,知識工程,神經網絡計算,

圖搜索技術,不確定推理等）.

?人工智能的研究范圍問題，一般認為包括:知識表示，推理技術，自然語言

理解，知識工程，計算機視覺等許多方面.引起爭議的原因，第一是由于邊

界不分明，某些分支與數學有交界（如定理證明，謂詞邏輯），或與語言學有

交界（如自然語言理解），或與心理學有交界（如認知模型），或與電子學機

械學有交界（如計算機視覺,機器人）.第二是由于科學的發展,各分支的內

容在不斷的變化.第三，隨著研究工作的深入，一些傳統的觀念在發生變化,

例如在歷史上認為數值計算發展到符號演算是AI的一個重要特征,但在近

年的研究中，計算機視覺和機器人學的研究中又回到了數值計算的現象，

提高了數學在人工智能研究中的地位.

1.4AI的研究領域

?搜索算法：狀態空間圖、博弈樹搜索

?推理方法：歸結推理、不確定性推理

?自然語言理解：不僅能識別文字而且能理解文本含義的機器系統

?模式識別（圖象與語音識別）

外界信息?感受獲取電信號-一Z特征提取

?知識工程（知識獲取、知識表示、知識數據庫、知識運用等一系列知識處

理技術，是以知識為中心來組織智能系統）

?神經網絡技術

?專家系統

知識庫推理機

?機器人

1.5人工智能求解方法的特點

?AI研究的是以符號表示的知識而不是數值數據為研究對象；

?AI中采用的啟發式搜索算法(HeuristicResearchAlgorithm)而不是常

規的算法(Algorithm)

?控制結構與知識是分離的

?允許出現不正確的答案

1.6人類智能和人工智能

1.人類智能特性

感知能力思維能力反應能力

2.人工智能特性

機器感知能力機器思維能力(知識表示)機器行為能力

第二章知識表示

2.1知識及其表示

1.知識的概念

Feigenbaum認為知識是經過削減、塑造、解釋和轉換的信息。簡單地說，知

識是經過加工的信息。

Bernstein說知識是特定領域的描述、關系和過程組成。

Hayes-Roth認為知識是事實、信念和啟發式規則。

知識可從(范圍，目的，有效性)加以三維描述。其中知識的范圍是由具體

到一般，知識的目的是由說明到指定，知識的有效性是由確定到不確定。例如

“為了證明A-B,只需證明AA?B是不可滿足的”這種知識是一般性、指示性、

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

知識表示是研究用機器表示知識的可行性、有效性的一般方法，是一種數據結

構與控制結構的統一體，既考慮知識的存儲又考慮知識的使用。知識表示可看

成是一組描述事物的約定，以把人類知識表示成機器能處理的數據結構。

2.人工智能系統所關心的知識

一個智能程序高水平的運行需要有關的事實知識、規則知識、控制知識和元

知識。

事實:是有關問題環境的一些事物的知識，常以“???是??.”的形式出現。

如事物的分類、屬性、事物間關系、科學事實、客觀事實等，在知識庫中屬于

低層的知識。如雪是白色的、鳥有翅膀、張三李四是好朋友。

規則:是有關問題中與事物的行動、動作相聯系的因果關系知識，是動態的，

常以“如果...那么...”形式出現。特別是啟發式規則是屬于專家提供的專門

經驗知識，這種知識雖無嚴格解釋但很有用處。

控制:是有關問題的求解步驟，技巧性知識，告訴怎么做一件事。也包括當

有多個動作同時被激活時應選哪一個動作來執行的知識。

元知識:是有關知識的知識，是知識庫中的高層知識。包括怎樣使用規則、

解釋規則、校驗規則、解釋程序結構等知識。

2.2邏輯表示法

對知識通過引入謂詞、函數來加以形式描述，獲得有關的邏輯公式，進而以

機器內部代碼表示。

設在一個房間里，有一個機器人ROBOT,一個壁室ALCOVE,一個積木塊BOX,

兩個桌子A和Bo機器人可把積木塊BOX從一種狀態變換成另一種狀態。

引入謂詞：

TABLE(A)表示A是桌子

EMPTYHANDED(ROBOT)表示機器人雙手是空的

AT(ROBOT,A)表示機器人在A旁

HOLDS(ROBOT,BOX)表示機器人拿著積木塊

ON(BOX,A)表積木塊BOX在A上

2.3產生式表示法

產生式是一種知識表達方法，具有和Turing機一樣的表達能力。

2.3.1事實與規則的表示

事實可看成是斷言一個語言變量的值或是多個語言變量間的關系的陳述句，

語言變量的值或語言變量間的關系可以是一個詞。不一定是數字。如雪是白色

的，其中雪是語言變量，其值是白色的。John喜歡Mairy，其中John、Mary是

兩個語言變量，兩者的關系值是喜歡。

一般使用三元組(對象，屬性，值)或(關系，對象1,對象2)來表示事

實，其中對象就是語言變量，若考慮不確定性就成了四元組表示(增加可信度)。

這種表示的機器內部實現就是一個表。

如事實“老李年齡是35歲”，便寫成(Lee,age,35)

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

對于規則是表示事物間的因果關系，以下列形式表示：

condition->action

condition作為前件或模式，而action稱作動作或后件或結論。前件部分常

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

度度量值。

2.3.2產生式系統的組成和推理

多數較為簡單的專家系統(ExpertSystem)都是以產生式表示知識的，相

應的系統稱作產生式系統。

產生式系統，由知識庫和推理機兩部分組成。其中知識庫由規則庫和數據庫

組成。規則庫是產生式規則的集合，數據庫是事實的集合。

規則是以產生式表示的。規則集蘊涵著將問題從初始狀態轉換解狀態的那些

變換規則，規則庫是專家系統的核心。規則可表成與或樹形式，基于數據庫中

的事實對這與或樹的求值過程就是推理。

數據庫中存放著初始事實、外部數據庫輸入的事實、中間結果事實和最后結

果事實。

推理機是一個程序，控制協調規則庫與數據庫的運行，包含推理方式和控制

策略。

產生式系統的推理方式有正向推理、反向推理和雙向推理

正向推理：從已知事實出發，通過規則庫求得結論，或稱數據驅動方式。推

理過程是

規則集中的規則前件與數據庫中的事實進行匹配，得匹配的規則集合。

從匹配規則集合中選擇一條規則作為使用規則。

執行使用規則的后件。將該使用規則的后件送入數據庫中

重復這個過程直至達到目標

具體說如數據庫中含有事實A,而規則庫中有規則A->B,那么這條規則便是

匹配規則，進而將后件B送入數據庫中。這樣可不斷擴大數據庫直至包含目標

便成功結束。如有多條匹配規則需從中選一條作為使用規則，不同的選擇方法

直接影響著求解效率，選規則的問題稱作控制策略。正向推理會得出一些與目

標無直接關系的事實，是有浪費的。

反向推理：從目標（作為假設）出發，反向使用規則，求得已知事實，或稱

目標驅動方式，推理過程是：

規則集中的規則后件與目標事實進行匹配，得匹配的規則集合；

從匹配的規則集合中選擇一條規則作為使用規則；

將使用規則的前件作為子目標；

重復這個過程直至各子目標均為已知事實成功結束；

如果目標明確，使用反向推理方式效率較高。

雙向推理：同時使用正向推理又使用反向推理。

2.3.3產生式表示的特點

產生式表示格式固定，形式單一，規則（知識單位）間相互較為獨立，沒有

直接關系使知識庫的建立較為容易，處理較為簡單的問題是可取的。另外推理

方式單純，也沒有復雜計算。特別是知識庫與推理機是分離的，這種結構給知

識的修改帶來方便，無須修改程序，對系統的推理路徑也容易作出解釋。所以,

產生式表示知識常作為構造專家系統的第一選擇的知識表示方法。

2.4語義網絡表示法

邏輯表示法和產生式表示法常用于表示有關論域中各個不同狀態間的關系，

然而用于表示一個事物同其各個部分間的分類知識就不方便了。槽（slot）與

填槽表示方法便于表示這種分類知識。語義網絡和框架表示方法就屬于其中的

兩種。

2.4.1語義網絡的結構

語義網絡是對知識的有向圖表示方法。一個語義網絡是由一些以有向圖表示

的三元組（結點1,弧，結點2）連接而成。

結點表示概念、事物、事件、情況等。

弧是有方向的有標注的。方向體現主次，結點1為主，結點2為輔?；∩系臉?/p>

注表示結點1的屬性或結點1和結點2之間的關系。

如事實“雪是白色的”，可表示成：

顏色

,雪,

A白色的

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

R

A----------------------->B

這樣事實與規則的表示是相同的，區別僅是弧上的標注有別。

從邏輯表示法來看，一個語義網絡相當于一組二元謂詞。因為三元組（結點1,

弧，結點2）可寫成P（個體1,個體2）,其中個體1、個體2對應于結點1、

結點2,而弧及其上標注的結點1與結點2的關系由謂詞P來體現。

語義網絡視作一種知識的單位，人腦的記憶是由存儲了大量的語義網絡來體現

的。而產生式表示法是以一條產生式規則作為知識的單位，而各條產生式規則

沒有直接的聯系。

結點間的關系有isa,a-part-of,is型

⑴ISA鏈用來表示具體-抽象關系，或說表示一種隸屬關系，體現某種層次分類。

特點是具體層結點可繼承抽象層結點的屬性。

特點是part-of

2.4.2語義網絡表示下的推理

語義網絡表示下的推理方法不像邏輯表示法和產生式表示法的推理方法那

樣明了。語義網絡表示法是依匹配和繼承來進行推理的。最簡單的isa關系下

的推理是直接繼承，如：

便有：

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

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

也可以將語義網絡引入邏輯含義，表示出A,V,?關系，便可以使用歸結推

理法。

還有人將語義網絡中的結點看成有限自動機（DFA）,為尋求幾個概念間的

關系，起動相應的自動機，如有回合點便可求得解答。

2.5框架表示法

2.5.1框架理論

1975年Minsky的論文“Aframeworkforrespresentingknowledge”中提

出了框架理論。其基本觀點是人腦已存儲有大量典型情景，當人面臨新的情景

時，就從記憶中選擇一個稱為框架的基本知識結構，這個框架是以前記憶的一

個知識空框，而其具體內容依新的情景而改變，對這空框的細節加工修改和補

充，形成對新情景的認識又記憶于人腦中?？蚣芾碚搶⒖蚣芤曌鞯闹R單位，

將一組有關的框架連接起來便形成框架系統。系統中不同框架可以有共同結點,

系統的行為由系統內框架的變化來表現的。推理過程是由框架間的協調來完成

的。

框架表示法是一種適應性強、概括性高、結構化良好、推理方式靈活又能把

陳述性知識與過程性知識相結合的知識表示方法。

2.5.2框架結構

框架是由若干結點和關系（統稱為槽slot）構成的網絡。是語義網絡一般化

形式化的一種結構，同語義網絡沒有本質區別。將語義網絡中結點間弧上的標

注也放入槽內就成了框架表示法。

框架是表示某一類情景的結構化的一種數據結構。框架由框架名和一些槽

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

條件、默認值或是一個子框架。槽值含有如何使用框架信息、下一步可能發生

的信息、預計未實現該如何做的信息等。

框架的一般格式：

FRAMEWORK：<frameworkname>

<slot1>

<face11>:value

<faceln>:value

<slot2>

<face21>:value

<face2n>:value

例：

framework:〈大學教師》

類屬:〈教師＞

學歷:（學士，碩士，博士）

專業:〈學科專業〉

職稱：（助教，講師，副教授，教授）

外語：

范圍：（英，法，德，...）

默認：英

水平：（優、良、中、差）

默認：良

2.5.3框架表示下的推理

框架表示法沒有固定的推理機理。但框架系統的推理和語義網絡一樣遵循匹

配和繼承的原則，而且框架中如if-needed、if-added等槽的槽值是附加過程,

在推理過程中起重要作用。如確定一個人的年齡，已匹配的知識庫中的框架為

槽名

年齡：NIL

if-needed:ASK

if-added:CHECK

在推理的過程中便啟動了if-needed和if-added兩個槽的附加過程ASK和

CHECKo

4.5.4框架與產生式表示法的比較

productionframework

知識表示

規則框架

單位

推理固定、與知識庫獨立可變，與知識庫成一體

建立知識

容易困難

庫

通用性低高

應用簡單問題復雜問題

用戶初學者專家

2.6面向對象的表示法

2.7腳本表示法

2.8過程表示法

2.9狀態空間表示法：用來表示問題及其搜索過程的一種方法。

1.問題狀態空間的構成

（1）狀態：是描述問題求解過程中不同時刻狀況的數據結構。一般用一組變量的有序集合表示：

Q=（q0,ql,q2,…,qn）,其中qi為集合的分量，稱為狀態變量。當-個分量以確定的值時，就得到一個具體

的狀態。

（2）算符：引起狀態中某些分量發生變化，從而使問題由個狀態轉變為另?個狀態的操作。

（3）狀態空間：由表示一個問題的全部狀態及一切可用算符構成的集合。一般由三部分構成：問題的所

有可能的初始狀態構成的集合S,算符集合F,目標狀態集合G,用一個三元組表示：（S,F,G）

狀態空間的圖示形式稱為狀態空間圖，其中，節點表示狀態，有向邊表示算符。

（4）問題的解：從問題的初始狀態集S出發，經過,系列的算符運算，到達目標狀態，由初始狀態到目

標狀態所用算符的序列就構成了問題的一個解。

2.用狀態空間表示問題的步驟

（1）定義問題狀態的描述形式

（2）用所定義的狀態描述形式吧問題的所有可能的狀態都表示出來，并確定出問題的初始狀態集合描述

和目標狀態集合描述。

（3）定義一組算符，使得利用這組算符可把問題由?種狀態轉變到另一種狀態。

3.利用狀態空間求解問題的過程

例：二階Hanoi塔問題（見P72）

解：第一步，定義問題狀態的描述形式

第二步，用所定義的狀態描述形式把問題的所有可能的狀態都表示出來，并確定出問題的初始狀態集

合描述和目標狀態集合描述

第三步，定義一組算符

2.10與/或樹表示法

1、與或樹的概念

用一個類似圖的結構來表示把問題歸約為后繼問題的替換集合，畫出歸約問題圖。

例如，設想問題A需要由求解問題B、C和D來決定，那么可以用一個與圖來表示；同樣，一個問題

A或者由求解問題B、或者由求解問題C來決定，則可以用一個或樹來表示。

2、與或樹的有關術語

父節點是一個初始問題或是可分解為子問題的問題節點；

子節點是一個初始問題或是子問題分解的子問題節點；

或節點只要解決某個問題就可解決其父輩問題的節點集合；

與節點只有解決所有子問題，才能解決其父輩問題的節點集合；

弧線是父輩節點指向子節點的圓弧連線；

終葉節點是對應于原問題的本原節點。

3、與或樹的有關定義

可解節點與或樹中一個可解節點的一般定義可以歸納如下：

（1）終葉節點是可解節點（因為它們與本原問題相關連）。

（2）如果某個非終葉節點含有或后繼節點，那么只有當其后繼節點至少有一個是可解的時，此非終葉

節點才是可解的。

（3）如果某個非終葉節點含有與后繼節點，那么只要當其后繼節點全部為可解時，此非終葉節點才是

可解的。

不可解節點不可解節點的一般定義歸納于下：

（1）沒有后裔的非終葉節點為不可解節點。

(2)如果某個非終葉節點含有或后繼節點，那么只有當其全部后裔為不可解時，此非終葉節點才是不

可解的。

(3)如果某個非終葉節點含有與后繼節點，那么只要當其后裔至少有一個為不可解時，此非終葉節點

才是不可解的。

4、與或樹構樹規則

(1)與或樹中的每個節點代表?個要解決的單一問題或問題集合。樹中所含起始節點對應于原始問題。

(2)對應于本原問題的節點，叫做終葉節點，它沒有后裔。

(3)對于把算符應用于問題A的每種可能情況，都把問題變換為?個子問題集合；有向弧線自A指向

后繼節點，表示所求得的子問題集合。

(4)一般對于代表兩個或兩個以上子問題集合的每個節點，有向弧線從此節點指向此子問題集合中的

各個節點。

(5)在特殊情況下，當只有一個算符可應用于問題A,而且這個算符產生具有一個以上子問題的某個

集合時，山上述規則3和規則4所產生的圖可以得到簡化。

第三章推理方法

謂詞邏輯是一種表達力很強的形式語言，謂詞邏輯及其推理方法是人工智能

中知識表示方法,機器推理,定理證明的基本方法。另外謂詞邏輯中的替換合一

技術，也是符號推理中模式匹配的基本技術。本章主要講解基于謂詞邏輯的歸

結演繹推理。

3.1歸結推理方法（確定性推理方法）

3.1.1謂詞、函數、量詞

?謂詞：表示個體對象之間的關系、屬性或狀態。其表示形式如下：

P（xl,x2,x3,...xn）

其中：

P是謂詞符號，表示xl,x2,x3,...xn個體對象之間的屬性、狀態或關系。

xl,x2,x3,...xn是謂詞的參量（或稱項），一般表示個體，它可以是個體常

量、個體變量或是個體函數。個體變元的變化范圍稱為個體域（或論域）

例：

口（外：表示乂是素數

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

存在量詞：“存在”、“有些”、“至少有一個”、“有的”等詞統稱為存

在量詞，記為mx

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

達能力大大擴充了

例1:

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

“凡是人都有名字”。

例2：

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

“存在不是偶數的整數”

例3：知識“不存在最大的整數”的表示

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

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

?謂詞公式：用謂詞、量詞(存在量詞，全稱量詞)、聯接詞(一蘊涵，A合取,

▽析取)連接而成的復雜的符號表達式稱為謂詞公式。

3.1.2命題邏輯的歸結法

］概念，

不帶參數(肯定也不含量詞))的謂詞稱為命題.

謂詞的表達能力更強，命題沒有概括能力；

命題：

P1:代表“北京是一個城市”

P2：代表“上海是一個城市”

P3：代表“廣州是一個城市”

謂詞：CITY(x)：代表“x是一個城市”，x的論域為口=｛北京，上海，廣州｝

謂詞代表變化著的情況，而命題代表固定的情況；

P：北京是一個城市；

Q：煤球是白的；

則P為永真式，Q為永假式；

而對于以上的謂詞CITY(x),當x取值為“北京”時為“真”值，當x取值為“煤

球”時為“假”值。

謂詞和命題相比的優點是謂詞在不同的知識之間建立聯系；

例如下面四個知識單元：

HUMAN(X)：代表x是人；

LAWED(x):代表x受法律管制；

COMM^'(x):代表x犯法；

PUNISHED(x):x受法律制裁；

則

HUMAN(x)-LAWED(x)表示一個高級的知識單元“人人都受法律的管制”。

COMMIT(x)-PUNISHED(x)表示只要x犯罪，x就要受法律制裁。

｛(HUMAN(x),LAWED(x))-*(COMMIT(x)-PUNISHED(x))｝表示“如果由于

某個x是人而受到法律管制，則這個人犯了罪就一定要受到懲罰”

由連接詞(一蘊涵，八合取，V析取，等價否定詞~)將命題連接在一起構

成命題公式。

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

ABA->B

001

011

100

111

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

—*叱概念.

4藁：真值為T的命題公式稱為永真式或重言式或有效的。

永假式：真值為F的命題公式稱為永假式或不可滿足的。

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

可滿足式：不是永假公式的命題公式；

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

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

子句:文字的析取稱為子句.例如:PVRV?Q

互補文字：設L為一個文字，則稱L與?L為互補文字。

一些有用的等價關系：

~~A<=>A雙重否定

AAA<=>A

AVA<=>A

AAB<=>BAA

交換律

AVB<=>BVA

(AAB)AC<=>AA(BAC)

結合律

(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蘊含表達式

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

AAT<=>A

AAF<=>F等價表達式

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命題邏輯中的歸結推理方法

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

條件下有B成立，或說A1AA2八…八AnfB。很顯然A1AA2A...AAnfB等價

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

A...AAnA?B出發使用歸結推理規則來尋找矛盾，從而證明A1AA2A...A

An-B的成立。這種方法稱為反演推理方法。

3歸結式

設有兩個子句

ci=pvcr

C2=~PVC2'

從中消去互補對一，所得新子句R(C1,C2)=C1'VC2',稱為子句Cl',C2'的歸結

式。沒有互補對的兩子句沒有歸結式。

歸結推理規則就指的是對兩子句做歸結，也即求歸結式。

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

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

證：設I是使Cl,C2為真的任一解釋，若在I下P為真，從而?P為假，則C2'

必為真，那么R(C1,C2)=C1'VC2'為真。若在I下P為假，則C1'必為真，那么

R(C1,C2)=C1'VC2'為真。從而證明了C1AC2=>R(C1,C2),即歸結式是子句的邏

輯結論。

特別地,當C1=P,C2=~P時,R(C1,C2)=口，記作為空子句。顯然Cl,C2同時

為真是矛盾，或者說空子句口體現了矛盾。

4命題邏輯的歸結推理過程

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

(2)子句集：將若干個子句的合取式中的合取詞人換成逗號，形成的集合稱

為子句集。

(3)從子句集S出發，僅只對S的子句間使用歸結推理規則(即求歸結式)，

并將所得歸結式仍放入S中，進而再對新子句集使用歸結推理規則，重復這

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

子句集S對應的定理是成立的。

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

證：

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

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

Q,P)

對S作歸結

⑴?PVQ

⑵?Q

⑶P

(4)?P..........................對(1)(2)求歸結式

(5)口..............對(3)(4)求歸結式

得證。

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

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

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

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

S={-PVQ,?RV?Q,R,P}，對S做歸結：

⑴?PVQ

(2)?RV?Q

(3)R

(4)P

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

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

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

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

應用邏輯等價式可以將任一謂詞公式化成合取范式。

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

應用邏輯等價式和邏輯蘊含式可以將任一謂詞公式化成析取范式。

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

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

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

取范式。

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

?stepl:去掉多余的量詞，即沒意義的量詞

?step2:將同名的約束變元與自由變元改名，使它們不同名。

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

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

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

?step4:將連接詞?內移，移到原子公式之前

?(?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中不含約束變元

BV3XA(X)...........3x(BVA(x)),其中B中不含約束變元

VxA(x)VB............Vx(A(x)VB),其中B中不含約束變元

BVVxA(x)............Vx(BVA(x)),其中B中不含約束變元

同樣對上面式子中的▽改為A可得到另一組關于的A的替換式。

另外還可用下式進行替換：

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

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

3

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

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

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

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

網((。尸⑸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王力((~產Q(zj))V~氏(x,〃))

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

(4)Skolem(斯克林)標準型：將一個謂詞公式中所有存在量詞消去之后，便

得到該謂詞公式的Skolem標準型。

(5)建立謂詞公式的子句集

2將謂詞公式化成子句集的步驟：

?按上述步驟化成前束合取范式；

?化成Skolem標準型，消去存在量詞

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

①若該存在量詞在某些全稱量詞的轄域內，則用這些全稱量詞指導變元的一

個函數代替該存在量詞轄域中的相應約束變元，這樣的函數稱為Skolem函數;

②若該存在量詞不準任何全稱量詞的轄域內，則用一個常量符號代替該存在

量詞轄域中相應約束變元，這樣的常量符號稱為Skolem常量；

?消去所有全稱量詞

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

的子句集

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

的子句集。

解：

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

域中，所以將y,z分別用Skolem函數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))))已

經是合取范式了，所以謂詞公式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產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：設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(常數)

==>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標準型

從而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|uv

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

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)]...平行則內錯交相等

子句：

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)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)}

利用后面學到的替換和合一知識之后可給出證明過程。

3.1.4Herbrand理論：

證明一個謂詞公式的不可滿足性是困難的，這是因為謂詞中個體變量的論域D

的任意性，以及解釋的個數的無限性。例如：

「&):代表*是偶數。

若x的論域為9={2,4,6,8},則P是永真式，是可滿足的；

若x的論域為口={1,3,5,7},則P是永假式，是不可滿足的；

若x的論域為口={1,2,5,8},則P的真值與取論域D上的解釋有關；

所以如果對一個具體的謂詞公式能找到一個比較簡單的特殊的論域，使得只要

在這個論域上該公式是不可滿足的，便能保證該公式在任一論域上也是不可滿

足的。所要建立的Herbrand域(簡稱H域)就具有這樣的性質。

1H域

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

沒有常量出現，就任取常量a￡D,而規定H°={a}；

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

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

i=l,2,...o

規定上為G的H域。不難看出H域是直接依賴于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中的一個常量

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....

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

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

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

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

稱為子句集S(或公式G)的原子集。其中是出現于S中的任

一謂詞符號，而是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中謂詞個數是有限的，而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(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

可按下列方法選取相應的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

于是得到相應的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*解釋。

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

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

設a=l,則相應的解釋為：

H*={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)VQ(y)/P(a),~Q(b)}畫出相應的語義樹

因為H={a,b}

A={P(a),Q(a),P(b),Q(b)}從A出發可畫出語義樹(部分)

N41N42N43N44

為了方便常以I(N)表示從根結點到結點N分支上所標記的所有文字的集合。

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