高級人工智能高級人工智能邏輯教材第1頁第二章人工智能邏輯2.1主要形式工具-----邏輯2.2非單調邏輯2.3默認邏輯2.4限定邏輯2.5自認知邏輯2.6真值維護系統2.7情景演算邏輯基礎2.8動態描述邏輯高級人工智能邏輯教材第2頁

邏輯歷史Aristotle——邏輯學Leibnitz——數理邏輯GottlobFrege(1848-1925)——一階謂詞演算系統,《符號論》20世紀30年代，數理邏輯廣泛發展高級人工智能邏輯教材第3頁主要形式工具──邏輯

在本世紀30年代以后，數學方法廣泛滲透與利用于數理邏輯，使得數理邏輯成為數學領域中與代數、幾何等并列學科之一。當代數理邏輯能夠分為邏輯運算、證實論、公理集合論、遞歸論和模型論。高級人工智能邏輯教材第4頁關于知識表示與推理

智能行為基礎是知識，尤其是所謂常識性知識。人類智能行為對于知識依賴主要表現在對于知識利用，即利用已經含有知識進行分析、猜測、判斷、預測等等。人類利用知識能夠預測未來，由已知情況推測未知情況、由發生事件預測還未發生事件等等。不過，當人們希望計算機含有智能行為時，除了告訴計算機怎樣像人一樣地利用知識以外（對于知識進行推理），一個更為基礎和先行工作是怎樣使計算機含有知識（對于知識進行表示），即在計算機上如何表示人類知識。高級人工智能邏輯教材第5頁關于知識表示與推理多數基于邏輯智能系統使用一階邏輯或者它一些擴張形式。一階邏輯優點是它含有相當強表示能力。有人工智能教授堅信全部人工智能中知識表示問題完全能夠在一階邏輯框架中得以實現。一階邏輯在表示不確定性知識時其表示能力也是很強。比如，

xP(x)表示在所考慮論域中存在一個含有性質P對象，而詳細是哪一個對象含有此性質則是待確定；再如，P

Q表示P和Q這兩個性質之間有一個是成立，至于到底是哪一個成立則是依據詳細情況而定。高級人工智能邏輯教材第6頁關于知識表示與推理有些人堅信從本質上看,一階邏輯對于知識表示是足夠,但從實際應用角度看,為方便、清楚和簡練起見,知識表示不一定非得從一階邏輯出發。實際上，人們從實際應用出發已經創造和建立了許多適合用于不一樣目標邏輯系統。

(1)為了表示關于認知相關概念，如相信、知道、愿望、意圖、目標、承諾等等，人們引進了刻劃各種認知概念模態邏輯；

(2)為了刻劃智能系統中時間原因，人們在邏輯系統中引進時間概念，提出了各種時序邏輯；高級人工智能邏輯教材第7頁關于知識表示與推理

(3)為了描述各種不確定和不準確概念，人們引進了所謂含糊邏輯；含糊邏輯是直接建立在自然語言上邏輯系統，與其它邏輯系統相比較，它考慮了更多自然語言成份。按照其創始人Zadeh說法就是詞語上計算，表示為一個公式,即，fuzzylogic＝computingwithwords；

(4)人類知識與人類活動是息息相關，人類正是在各種活動和行為中取得知識。所以，行為或者動作概念在智能系統中是一個關鍵概念。動作概念與普通邏輯中靜態概念很不相同，它是一個動態概念，動作發生影響著智能系統性質。對于動作考慮，給人工智能界帶來了許多難題，如框架問題、量詞問題等等。為了刻劃動作概念，人們引進了一些新邏輯體系來刻劃它。

高級人工智能邏輯教材第8頁關于知識表示與推理

(5)計算機對于人類進行決議時進行若干方面支持已經成為計算機應用一個主要方面。人類在決議時，對于各種方案和目標有一定偏好和選擇。這時“偏愛”就成為了一個基本概念。為了表述和模擬人類在決議時選擇規律和行為，對于“偏愛”這個詞研究就是不可防止。于是，基于管理科學所謂偏愛邏輯被提出并加以研究。

(6)時間是智能系統中最主要幾個概念之一。人類使用各類副詞來對時間概念加以描述。比如，“一會兒”“相當長”“斷斷續續地”“偶然”等等,這一類詞在我們日常生活中比比皆是。含有這些詞句子顯然是極難用經典時序邏輯來刻劃,于是有些人引進了一個邏輯系統專門刻劃這類句子。其基本思想是利用數學中積分思想，經過對時間某種像積分那樣表示和運算來形式化這些句子。高級人工智能邏輯教材第9頁

邏輯系統一個邏輯系統是定義語言和它含義方法。邏輯系統中一個邏輯理論是該邏輯語言一個語句集合，它包含：邏輯符號集合：在全部該邏輯邏輯理論中均出現符號；非邏輯符號集合：不一樣邏輯理論中出現不一樣符號；語句規則：定義什么樣符號串是有意義；證實：什么樣符號串是一個合理證實；語義規則：定義符號串語義。高級人工智能邏輯教材第10頁邏輯程序語言邏輯符號保留字或者符號非邏輯符號用戶自定義符號(變量名，函數名等)語句規則結構一個程序語句規則語義規則定義程序做什么語句規則推理規則、公理和證實沒有邏輯與程序語言對比高級人工智能邏輯教材第11頁在語法上，假如存在一個從假設

到

證實，則記為

?

，稱

由

可推導出，或可證實。假如在沒有任何假設下

是可推導出，則記為?

，稱

為可證實。稱一個假設

是不協調，假如存在一個語句

使得

和

否定均可由

推導得出。稱一個邏輯系統是一致，或相容(consistent)，假如不存在邏輯系統公式A，使得?A與??A同時成立。證明(語法)高級人工智能邏輯教材第12頁一個證實是一個語法結構，它由符號串依據一定規則組成。它包含假設和結論。在公理化邏輯中，邏輯給出一個邏輯公理和推理規則集合。推理規則是能夠從一個語句集合得到另一語句集合。

公理化邏輯中證實就是一個語句序列，使得其中每個語句要么是邏輯公理，要么是一個假設，要么是由前面語句經過推理規則得到。證明高級人工智能邏輯教材第13頁語言解釋是在某個論語(domain)中定義非邏輯符號。語句語義是在解釋下定義出語言L真假值。假如I是L一個解釋，且

在I中為真，則記為I

?

，稱作I滿足

，或者I是

一個模型。類似地，給定一個語句

和一個語句

，假如對每個解釋I，有I

?

蘊含I

?

，換言之，假如I是

一個模型則I也是

一個模型，則記為

?

，我們稱

為

一個邏輯結果。解釋(語義)高級人工智能邏輯教材第14頁可靠性(reliable)一個邏輯是可靠，假如它證實保持真假值，即在任何解釋I下，假如I是

模型，且

可由

推導出，則I也是

一個模型。即，一個邏輯是可靠，假如對任何語句集合

和語句

，

?

蘊涵

?

。可靠性和完備性完備性(complete)一個邏輯是完備，假如任何永真語句是可證。即，對任何語句集合

和語句

，

?

蘊涵

?

。假如一個邏輯是完備，則該邏輯證實系統已強到能夠推出任何永真式。G?del完備性定理：一階邏輯是完備高級人工智能邏輯教材第15頁可判定一個邏輯稱為是可判定(decidable)，假如存在一個算法對邏輯中任一公式A，可確定?

A是否成立。不然，稱為是不可判定(undecidable)。假如上述算法雖不一定存在，卻有一個過程，可對該系統定理做出必定判斷，但對非定理公式過程未必終止，因而未必能作出判斷。這時稱邏輯是半可判定。可判定性

一階邏輯是不可判定，但它是半可判定。高級人工智能邏輯教材第16頁

哲學邏輯手冊1983-89年間出版了4卷本哲學邏輯手冊(HandbookofPhilosophicalLogic)年開始出版第2版，約為18卷，迄今已經出版12卷。該書由英國倫敦皇家學院計算機系多夫·加貝（DovM.Gabbay）教授和德國路德維希-麥克米蘭大學信息與語言處理中心岡瑟（F.Guenthner）教授共同主編。高級人工智能邏輯教材第17頁

已經出版前12卷內容

高階邏輯沖突多值邏輯含糊邏輯概率論條件句模態邏輯動態邏輯容錯邏輯優先邏輯圖形邏輯偏邏輯

直覺主義邏輯

非單調推理信念邏輯自由邏輯時序邏輯相干邏輯量子邏輯蘊涵邏輯時態邏輯問題邏輯道義邏輯弗協調邏輯目標導向演繹認知邏輯

加標演繹系統（邏輯新框架理論）等高級人工智能邏輯教材第18頁

當代邏輯學與計算機科學、計算語言學和人工智能關系表邏輯自然語程序人工邏輯指令與直數據庫復雜性智能體未來展望言處理控制智能編程陳式語言理論理論理論時序邏輯√√√√√√√√廣泛應用模態邏輯√√√√√√√√非常活躍算法證實√√√√√√√√非單調推理√√√√√√√意義重大概率和含糊√√√√√√√當前主流直覺主義邏輯√√√√√√√√主要替換者高階邏輯，λ-演算√√√√√√更具中心作用經典邏輯片斷√√√√√√前景誘人資源和子結構邏輯√√√√纖維化和組合邏輯√√√√√√可自我指稱謬誤理論在適當語境邏輯動力學√√動態邏輯觀論辯理論游戲√前景光明對象層次/元層次√√總起中心作用機制:溯因缺省相干√√邏輯一部分與神經網絡聯絡極主要，剛開始時間-行動-修正模型√√一類新模型加標演繹系統√√√√√邏輯學統一框架高級人工智能邏輯教材第19頁

命題邏輯命題是能夠確定其真假陳說句。Bolle提出了布爾代數。語言:

?，； 公式，原子公式公理模式:

◆(A

(B

A))

◆((A

(B

C))

((A

B)

(A

C)))

◆(((?A))

(?B)

(B

A))推理規則:分離規則(modusponens，MP規則)高級人工智能邏輯教材第20頁謂詞邏輯(一階邏輯)Frege謂詞演算語言:

?，，，，(，)；常元，變元，函詞，謂詞；公式公理模式:

◆(A

(B

A))

◆((A

(B

C))

((A

B)

(A

C)))

◆(((?A)

(?B))

(B

A))

◆

vA

Atv(t對A中變元v可代入)

◆

v(A

B)(

vA

vB)

◆A

vA(v在A中無自由出現)推理規則:分離規則高級人工智能邏輯教材第21頁謂詞邏輯與命題邏輯區分謂詞邏輯給出了原子語句內部結構，將原子公式看作是事物直接關系；它引入了“推廣”(泛化)，加強了邏輯表示能力和推理能力。這么，我們能夠說某種性質對某個對象是成立，或對全部對象成立，或不對任何對象成立。高級人工智能邏輯教材第22頁邏輯程序設計消解原理(歸結原理)Horn邏輯Prolog邏輯程序設計語言高級人工智能邏輯教材第23頁歸結原理例：

C1=?P∨Q∨R C2=P∨Q則C1與C2消解后結果為：Q∨R若子句集S能導出空子句?(有否證)，則稱S是不可滿足。反證法：S?AiffS

?A

??高級人工智能邏輯教材第24頁Horn邏輯文字：原子公式(正文字)或原子公式否定(負文字)。P,Q,?R子句：若干文字析取。?P∨Q∨RHorn子句：子句L1∨L2∨…∨Ln中假如至多只含一個正文字，那么該子句稱為Horn子句。Horn子句P∨?Q1∨?Q2∨…∨?Qn通常表示為：P

Q1,Q2,…,Qn高級人工智能邏輯教材第25頁Horn子句類型：

◆過程：P

Q1,Q2,…,Qn

◆事實：P

◆目標：

Q1,Q2,…,Qn

◆空子句：?例:

◆過程：AT(dog,x)

AT(Zhang,x)

◆事實：AT(Zhang,train)

◆目標：

AT(dog,train)

首先目標中過程調用AT(dog,train)與過程名AT(dog,x)匹配，合一為{train/x}，調用過程AT(Zhang,x)，從而產生新目標

AT(Zhang,train)，與事實匹配，產生目標?。因而調用成功，輸出“是”。高級人工智能邏輯教材第26頁PrologProlog(Programminginlogic)語言是以Horn子句邏輯為基礎高級程序設計語言。1972年，法國馬賽大學Alain.Colmerauer提出了Prolog雛型。1975年，Prolog被用于問題求解系統。今后，它在許多領域取得了應用，如關系數據庫、定理證實、智能問題求解、計算機輔助設計、規劃生成等領域。高級人工智能邏輯教材第27頁Prolog組成事實：關于對象性質和關系事實語句；student(john)，married(tom,mary)規則：關于對象性質和關系定義規則語句；它與事實不一樣在于，規則所定義性質、關系依賴與其它性質和關系，所以規則呈蘊涵語句形式。 B:—A “假如A則B”bird(x):—animal(x)，has(x,feather)問題：關于對象性質或關系問詢。 ?—student(john)

?—married(mary，x)高級人工智能邏輯教材第28頁Prolog語言基本文法Prolog語言最基本語言成份是項(term)，一個項或者是常量，或者是變量，或者是一個結構。常量：是指對象和對象之間特定關系名；

整數，如0，22，1586等；

原子，如John，student，likes，sister-of變量：表示任意對象，它與FOL中變元相同；

Prolog中變量能夠用大寫字母，下劃線，以及由它們開頭字母串。如X,Y,Answer,_value等。結構：是常量和變量序列，它由一個函子(函詞或謂詞)和該函子自變量所組成。如：likes(john,X) married(mary,jack)高級人工智能邏輯教材第29頁例：(1)likes(bell,sports)(2)likes(mary,smith)(3)likes(mary,sports)(4)likes(jones,smith)(5)friend(john,X):—

likes(X,sports),likes(X,smith)(規則)(6)?—

friends(john,Y) (問題)(事實)(7)?—

likes(X,sports),likes(X,smith)(8)?—likes(bell,smith) (bell/X)(7)?—

likes(X,sports),likes(X,smith)(8)?—likes(mary,smith) (mary/X)Y=mary，John與Mary是朋友高級人工智能邏輯教材第30頁Prolog執行方式搜索：在程序中自上而下地搜索事實和規則；匹配：將目標中項與事實和規則進行匹配；回溯：當目標中一項失敗時，假如目標中有已經成功項(應在失敗項左邊)，那末就重新調用這些成功項中最右邊一個，尋求新成功。高級人工智能邏輯教材第31頁Prolog基本特點Horn子句邏輯是Prolog基礎。Prolog既是一個邏輯程序設計語言，又是一個邏輯系統。Prolog是一個描述性語言，它是一個面向問題語言，你只需要告訴它要做什么，即給出問題形式描述，而不需要知道應該怎樣做。Prolog完全依靠匹配、回溯來進行搜索。Prolog求解過程是一個尋求否證消解過程。Prolog也使用元語言種謂詞，有很強描述能力。Prolog采取統一數據結構——項，它包含控制成份，且有專門進行數值計算和符號處理模塊。高級人工智能邏輯教材第32頁邏輯程序設計

PROLOG

BA1,…,An

B

?A1,…,An高級人工智能邏輯教材第33頁單調邏輯在現有知識基礎上，經過嚴密邏輯論證和推理取得新知識必須與已經有知識相一致。A，A

B

B推理系統定理集合伴隨推理過程進行而單調地增大。單調性： (1)

∈

Th(

) (2)若

1?

2，則Th(

1)?Th(

2) (3)Th(Th(

))＝Th(

) (不動點)高級人工智能邏輯教材第34頁非單調邏輯推理系統定理集合并不伴隨推理過程進行而單調地增大，新推出地定理很可能會否定、改變原來地一些定理，使得原來能夠解釋地一些現象變得不能解釋了。新規則： (4)

?

?

P (不動點)高級人工智能邏輯教材第35頁非單調邏輯

推理系統定理集合并不隨推理過程進行而單調地增大,新推出定理很可能會否定、改變原來一些定理,使得原來能夠解釋一些現象變得不能解釋了。

高級人工智能邏輯教材第36頁非單調邏輯

推理系統定理集合并不隨推理過程進行而單調地增大,新推出定理很可能會否定、改變原來一些定理,使得原來能夠解釋一些現象變得不能解釋了。t1<t2F(t1)F(t2)

高級人工智能邏輯教材第37頁非單調邏輯

鳥會飛鴕鳥是鳥所以,鴕鳥會飛高級人工智能邏輯教材第38頁非單調推理1John在時刻t1是活著2Dell在時刻t2>t1把子彈裝進槍膛3Dell在時刻t3>t2舉槍對John射擊4問題：John在時刻t4>t3還是活著嗎？高級人工智能邏輯教材第39頁非單調邏輯

設表示推理規則集,則單調邏輯語言Th()={A|A}

(1)Th()(2)if1

2,thenTh(1)Th(2)(3)Th(Th())=Th()(不動點)(4)ifP,thenMP

其中M模態詞高級人工智能邏輯教材第40頁默認邏輯1980年，Reiter提出了默認缺省邏輯(DefaultLogic)。 “普通情況下鳥是會飛” “鴕鳥不會飛” “企鵝不會飛”高級人工智能邏輯教材第41頁默認規則一個默認規則是以下形式規則：

(x):稱為前提條件

i(x):稱為缺省條件，或檢驗條件

(x):稱為結論為簡便，通常情況下能夠省略檢驗條件中M。規則使用：假如規則前提條件滿足，且現有知識導不出檢驗條件否定?

i(x)，則能夠得出結論成立。高級人工智能邏輯教材第42頁

默認理論一個默認理論

由兩個部分組成，即默認規則集D和公式集W，普通用二元組來表示

＝<D,W>若D中規則是閉規則時，則

為閉缺省理論。定義：設

＝<D,W>為一閉缺省理論，

為關于D一個算子，

作用于任意命題集合S，而其值為滿足以下三個性質最小命題集合

(S)： (1)W

(S) (2)Th(

(S))=

(S)，其中Th(

(S))={A|

(S)?

A} (3)假如D中有規則 ，且

∈

(S)，?

1,…,?

m?

S，那么

∈

(S)高級人工智能邏輯教材第43頁默認理論擴充定義：對命題集合E，假如

(E)=E，則E稱為關于D算子

不動點(fixpoint)。此時稱E為默認理論

＝<D,W>一個擴充(extension)。例1：設D＝{ }，W＝

，計算默認理論

＝<D,W>擴充。

＝<D,W>有唯一擴充E＝Th({?B,?F})。高級人工智能邏輯教材第44頁例2：設D＝{ }，W＝{B,C

F∨A,A∧C

?E}，計算默認理論

＝<D,W>擴充。

＝<D,W>有三個擴充E1＝Th(W

{A,C})E2＝Th(W

{A,E})E3＝Th(W

{C,E,G})高級人工智能邏輯教材第45頁封閉默認理論擴展

設封閉默認理論

=<D,W>,

為關于D一個算符，

作用于任意命題集合S，其值為滿足以下三個性質最小命題集合(S):

(1)W

(S);

(2)Th(

(S))=

(S);這里，Th(

(S))為命題集{A|

(S)

A};

(3)假如有默認規則

高級人工智能邏輯教材第46頁封閉默認理論擴展

命題集合E稱為關于D算符

固定點，假如

(E)=E,此時又稱E為

=<D,W>$一個擴充。有了擴充概念，便可定義非單調“推出”概念。

假如命題A包含在默認理論

一個擴充中，那么稱A在

中可推出，記為|

。

擴充E必須①含有全部已知事實;②在關系|

下是封閉;③其前提被E滿足,默認條件與E相容任意默認結論必須也在E中。

高級人工智能邏輯教材第47頁封閉默認理論擴展

含有擴展存在條件將顯得十分主要。下面我們討論三種情況。

(1)不含任何默認理論<{},W>:這種理論退化到一階邏輯理論,在這里它雖有唯一一個擴展Th(W),但對默認推理毫無意義和作用。

(2)一個默認理論<D,W>稱為規范默認理論，假如D中默認規則都有以下形式:高級人工智能邏輯教材第48頁封閉默認理論擴展

假如一個理論中全部默認都是規范,則該理論稱為規范理論。因為每個規范默認結論與其合理條件相同,因而這種缺省不會造成不一致性,不會證偽其它已用過默認合理條件。所以我們說規范默認理論是行為良好(well-behaved)理論,而且能夠證實:任何規范默認理論必定最少有一個擴充。

高級人工智能邏輯教材第49頁封閉默認理論擴展

(3)半規范默認理論(SeminormalDefaultTheory):即使規范默認理論最少有一個擴充,從而確保了系統知識庫W一致性。然而現實世界中許多事物、現象是無法用規范默認表示,而用以下形式默認則可有效地進行處理:

高級人工智能邏輯教材第50頁封閉默認理論擴展

為了確保半規范默認理論含有一個擴充,必須對它默認加以限制,Reiter給出了一個半規范默認理論最少含有一個擴充充分條件,這個條件要求封閉半規范默認理論是有序.。有序性建立在一個偏序關系

上,這個偏序要求:假如在推導β過程中用到了α,則α

β。Etheringthon在這種基礎上給出了求算偏序關系及其擴充算法,并討論了算法收斂性問題。高級人工智能邏輯教材第51頁限定推理1980年，McCarthy提出了一個非單調推理——限定推理(Circumscription)。基本思想：從一些事實A出發能夠推出含有某一性質P對象就是滿足性質P全部對象。只有當發覺其它對象也含有該性質時，才修改這種看法。高級人工智能邏輯教材第52頁限定邏輯

限定邏輯CIRC是一個極小化邏輯。下面，從一個基于極小模型定義命題限定出發，給出限定基本定義,進而給出一階限定基本結果，并將它推廣。定義2.1設L0是一個命題語言，p1,p2是在命題語言L0中兩個賦值。稱p1小于p2，記為p1

p2,當且僅當對任一命題變元x,假如p1(x)=l,則p2(x)=l。高級人工智能邏輯教材第53頁限定邏輯

定義2.2設A是一個公式，稱A一個賦值p是極小，當且僅當不存在A其它賦值p'使得p'

p。顯然,

是一個偏序關系。p1

p2表示p1包含真命題比p2少。極小賦值包含真命題極小。定義2.3極小后承

M。設A,B是兩個公式，A

M

B

當且僅當B在全部A極小模型中都為真。極小模型是非單調，它以命題極小化作為優先模型準則。高級人工智能邏輯教材第54頁限定邏輯

定義2.4設A是一個包含命題集P={p1,p2,...,pn}公式，一個A賦值p稱為

Z-極小賦值，當且僅當不存在A其它賦值p‘使得p

p’,定義以下：設p1,p2是兩個賦值，p1

Z-p2當且僅當對任一z

Z,若p1

(Z)=l,則p2

(Z)=l。

高級人工智能邏輯教材第55頁限定邏輯

定義2.5命題限定

P或CIRC(A,P)。設A是一個包含命題集公式，

是一個公式，A

P

當且僅當

在全部A

p-

極小賦值中都為真。

定理2.1A

p

當且僅當A

P

高級人工智能邏輯教材第56頁限定邏輯定義2.6令L是一個一階語言，T是一個L公式，它包含謂詞元組集

。設M[T]和M*[T]是公式T兩個模型。定義M*[T]優先于M[T],記為M*[T]

M[T]，當且僅當(1)M和M*有相同對象域，(2)除

外，公式T中全部其它關系和函數常數在M和M*都有相同解釋，(3)

在M*中外延是

在M中子集。高級人工智能邏輯教材第57頁限定邏輯

一個理論T模型M稱為優先，當且僅當不存在T其它模型M'使得M'

M。定義2.7Mm是

最小模型，當且僅當

M

Mm,M=Mm

高級人工智能邏輯教材第58頁限定邏輯比如設論域D={1,2}T=xy(P(y)Q(x,y))=[(P(1)Q(1,1))(P(2)Q(1,2))][(P(1)Q(2,1))(P(2)Q(2,2))]M:P(1)P(2)Q(1,1)Q(1,2)Q(2,1)Q(2,2)TTFTFTM*:P(1)P(2)Q(1,1)Q(1,2)Q(2,1)Q(2,2)FTFTFT

高級人工智能邏輯教材第59頁自認知邏輯Moore考慮自認知理論T對于一組初始前提A是可靠，當且僅當T中每一個自認知解釋器是一個T中自認知模型，其中全部A公式為真。一個理想理性主體信念必須滿足以下條件：(1)設P1,...,Pn

T,andP1,...,Pn

Q,則Q

T。(2)設P

T,則BP

T。(3)設P

T,則~BP

T。高級人工智能邏輯教材第60頁自認知邏輯在這種情況下，主體不能再得到更深入結論，所以，Moore稱上述理論為穩定自認知理論。當然，下列條件也成立：(4)假如BP

T,則P

T。(5)假如~BP

T,則P

T。高級人工智能邏輯教材第61頁真值維護系統TMS1979年，Doyle提出了一個非單調推理系統——真值維護系統(TruthMaintenanceSystem)真值維護系統是大型推理系統一個子系統，實現知識庫中信念(belief)修改與維護。其基本問題有：必須在不完全、有限信息基礎上作出假設決議，使得該假設成為知識庫信念；當這些決議結論被以后事實證實為錯誤時，怎樣對其信念進行修正。高級人工智能邏輯教材第62頁基本數據結構:

結點：表示信念

理由：表示信念原因信念既包含已知知識，也包含假設知識。基本操作：

新結點形成——將信念賦予該結點；

新理由加入——把某個信念與該結點聯接起來實現過程： 默認假設形成； 相關性回溯過程。高級人工智能邏輯教材第63頁

信念知識表示每一個命題或規則均稱為結點，它分為兩類：

IN-結點：相信為真

OUT-結點：不相信為真，或無理由相信為真， 或當前沒有任何有效理由。每個結點附有理由表，表示詳細結點有效性：

支持表SL：所在結點信念原因，理由；

條件證實CP：出現矛盾原因。高級人工智能邏輯教材第64頁(SL(<IN-結點表>)(<OUT-結點表>))IN-結點表中IN-結點表示知識庫中已知知識;OUT-結點表中OUT-結點表示這些結點否定。例1:(1)現在是夏天 (SL()())(2)天氣很潮濕 (SL(1)())結點(1)不依賴于任何別結點中當前信念或默認信念,因而這種結點稱為前提;結點(2)則依賴于當前結點(1)信念.所以，與一階邏輯不一樣是,TMS能夠撤消前提,并能夠對知識庫作適當修改.（1）支持表SL高級人工智能邏輯教材第65頁例2: (1)現在是夏天 (SL()()) (2)天氣很潮濕 (SL(1)(3)) (3)天氣很干燥若結點(1)是IN,結點(3)是OUT,則結點(2)才為IN.若在某個時刻出現結點(3)證據,則結點(2)就變為OUT,因為它不再有一個有效證實.象結點(2)這么結點稱為假設,它與非空OUT結點表SL證實有關.OUT結點(3)是結點(2)證實一部分.但假如結點(3)不存在,就不能這么表示了.在TMS中,它僅利用證實來維持一個相容信念數據庫,而它本身并不產生證實.高級人工智能邏輯教材第66頁(CP<結論><IN-假設><OUT-假設>)假如結論結點為IN-結點,以及以下條件成立: (1)IN假設中每個結點都是IN-結點; (2)OUT-假設中每個結點都是OUT-結點.那么條件證實CP是有效.普通說來,OUT-假設總是空集.TMS要求假設集劃分成兩個不相交子集,分別為不造成矛盾假設和造成矛盾假設.通常只要在IN-假設中結點為IN,OUT-假設中結點為OUT,則結論結點為IN.（2）條件證實CP高級人工智能邏輯教材第67頁

默認假設令{F1,F2,…,Fn}表示全部可能侯選默認假設結點集,G表示選擇默認假設原因結點,即由G引發在{F1,…,Fn}中進行缺省選擇.這么我們結合結點Node(Fi)以以下理由:(SL(G)(F1,…,Fi-1

,Fi+1,…,Fn))而選取Fi為默認假設.假如不存在任何其它關于怎樣進行選擇信息，則能夠認為除Fi之外其它任何時候選都不是可信．這么Fi為IN,其它Fj(i

j)均為OUT.但假如接收到一個有效理由支持某個其它侯選Fj,則Fj就為IN,而造成Fi假設失敗而變為OUT.高級人工智能邏輯教材第68頁

相關回溯當知識庫中出現不一致時,TMS將尋找并刪除已做一個不正確默認邏輯,恢復一致性.它包含三個步驟: (1)從產生矛盾結點開始,回溯跟蹤該矛盾結點理由充分支持以尋找矛盾假設集,并從中去掉最少一個假設信念以消除矛盾. (2)結構一個結點統計矛盾產生原因. (3)從S中選取假設A(即不合理假設),并證實列在其理由充分支持條件中一個OUT-結點.高級人工智能邏輯教材第69頁 (4)矛盾 (SL(1,3)()) (周三14:00沒有空會議室)例3: (1)會議日期為星期三 (SL()(2)) (2)會議日期不應是星期三 (3)會議時間為14:00 (SL(32,40,61)()) (5)不相容 (CP4(1,3)()) (2)會議日期不應是星期三 (SL(5)())結點(2)與結點(5)為IN,就引發結點(1)為OUT,因為結點(1)證實依賴于結點(2)是OUT.結點(4)現在也變成OUT.進而矛盾就消除了.高級人工智能邏輯教材第70頁情景演算◆MaCarthy針對動態領域中問題求解和邏輯程序設計提出了情景演