人工智能邏輯課件

人工智能邏輯

2022/10/14史忠植邏輯基礎1史忠植中國科學院計算技術研究所高級人工智能第二章人工智能邏輯

2022/10/10史忠植邏輯基礎1史忠植主要內容邏輯簡介邏輯程序設計非單調邏輯默認邏輯限定邏輯真值維護系統(tǒng)情景演算動態(tài)描述邏輯2022/10/14史忠植邏輯基礎2主要內容邏輯簡介2022/10/10史忠植邏輯基礎2邏輯簡介邏輯的歷史邏輯系統(tǒng)命題邏輯謂詞邏輯2022/10/14史忠植邏輯基礎3邏輯簡介邏輯的歷史2022/10/10史忠植邏輯基礎3邏輯的歷史Aristotle——邏輯學Leibnitz——數理邏輯GottlobFrege(1848-1925)——一階謂詞演算系統(tǒng),《符號論》20世紀30年代，數理邏輯廣泛發(fā)展2022/10/14史忠植邏輯基礎4邏輯的歷史Aristotle——邏輯學2022/10/10史邏輯系統(tǒng)一個邏輯系統(tǒng)是定義語言和它的含義的方法。邏輯系統(tǒng)中的一個邏輯理論是該邏輯的語言的一個語句集合，它包括：邏輯符號集合：在所有該邏輯的邏輯理論中均出現的符號；非邏輯符號集合：不同的邏輯理論中出現的不同的符號；語句規(guī)則：定義什么樣的符號串是有意義的；證明：什么樣的符號串是一個合理的證明；語義規(guī)則：定義符號串的語義。2022/10/14史忠植邏輯基礎5邏輯系統(tǒng)一個邏輯系統(tǒng)是定義語言和它的含義的方法。20222022/10/14史忠植邏輯基礎6邏輯程序語言邏輯符號保留字或者符號非邏輯符號用戶自定義的符號(變量名，函數名等)語句規(guī)則構造一個程序的語句規(guī)則語義規(guī)則定義程序做什么的語句規(guī)則推理規(guī)則、公理和證明沒有邏輯與程序語言的對比2022/10/10史忠植邏輯基礎6邏輯程序語言邏輯符號2022/10/14史忠植邏輯基礎7

一個證明是一個語法結構，它由符號串根據一定的規(guī)則組成。它包括假設和結論。在公理化邏輯中，邏輯給出一個邏輯公理和推理規(guī)則的集合。推理規(guī)則是可以從一個語句的集合得到另一語句的集合。

公理化邏輯中的證明就是一個語句序列，使得其中的每個語句要么是邏輯公理，要么是一個假設，要么是由前面的語句通過推理規(guī)則得到的。證明2022/10/10史忠植邏輯基礎7一個證2022/10/14史忠植邏輯基礎8

在語法上，如果存在一個從假設到的證明，則記為

?，稱由可推導出的，或可證明的。如果在沒有任何假設下是可推導出的，則記為?，稱為可證明的。稱一個假設是不協(xié)調的，如果存在一個語句使得和的否定均可由推導得出。稱一個邏輯系統(tǒng)是一致的，或相容的(consistent)，如果不存在邏輯系統(tǒng)的公式A，使得?A與??A同時成立。證明(語法)2022/10/10史忠植邏輯基礎8在語法2022/10/14史忠植邏輯基礎9

語言的解釋是在某個論域(domain)中定義非邏輯符號。語句的語義是在解釋下定義出語言L的真假值。如果I是L的一個解釋，且在I中為真，則記為I

?

，稱作I滿足，或者I是的一個模型。類似地，給定一個語句和一個語句，如果對每個解釋I

，有I

?

蘊含I

?

，換言之，如果I是的一個模型則I也是的一個模型，則記為

?，我們稱為的一個邏輯結果。解釋(語義)2022/10/10史忠植邏輯基礎9語言的解釋是2022/10/14史忠植邏輯基礎10可靠性(reliable)一個邏輯是可靠的，如果它的證明保持真假值，即在任何解釋I下，如果I是的模型，且可由推導出，則I也是的一個模型。即，一個邏輯是可靠的，如果對任何語句集合和語句，

?蘊涵

??？煽啃院屯陚湫酝陚湫?complete)一個邏輯是完備的，如果任何永真語句是可證的。即，對任何語句集合和語句，

?蘊涵

?。如果一個邏輯是完備的，則該邏輯的證明系統(tǒng)已強到可以推出任何永真式。G?del完備性定理：一階邏輯是完備的2022/10/10史忠植邏輯基礎10可靠性(relia2022/10/14史忠植邏輯基礎11可判定的一個邏輯稱為是可判定的(decidable)，如果存在一個算法對邏輯中的任一公式A，可確定?

A是否成立。否則，稱為是不可判定的(undecidable)。如果上述算法雖不一定存在，卻有一個過程，可對該系統(tǒng)的定理做出肯定的判斷，但對非定理的公式過程未必終止，因而未必能作出判斷。這時稱邏輯是半可判定的。可判定性一階邏輯是不可判定的，但它是半可判定的。2022/10/10史忠植邏輯基礎11可判定的可判定性一

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

命題邏輯命題是可以確定其真假的陳述句。Bolle提出了布爾代數。語言:

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

◆(A

(B

A))

◆((A

(B

C))((A

B)(A

C)))

◆(((?A))(?B)(B

A))推理規(guī)則:分離規(guī)則(modusponens，MP規(guī)則)2022/10/14史忠植邏輯基礎13命題邏輯命題是可以確定其真假的陳述句。2022/10/10史謂詞邏輯(一階邏輯)Frege謂詞演算語言:

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

◆(A

(B

A))

◆((A

(B

C))((A

B)(A

C)))

◆(((?A)(?B))(B

A))

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

◆v(AB)(vAvB)

◆AvA(v在A中無自由出現)推理規(guī)則:分離規(guī)則2022/10/14史忠植邏輯基礎14謂詞邏輯(一階邏輯)Frege謂詞演算2022/10/10史謂詞邏輯與命題邏輯的區(qū)別2022/10/14史忠植邏輯基礎15謂詞邏輯給出了原子語句的內部結構，將原子公式看作是事物直接的關系；它引入了“推廣”(泛化)，加強了邏輯的表示能力和推理能力。這樣，我們可以說某種性質對某個對象是成立的，或對所有的對象成立，或不對任何對象成立。謂詞邏輯與命題邏輯的區(qū)別2022/10/10史忠植邏輯基邏輯程序設計歸結原理(消解原理)Horn邏輯Prolog邏輯程序設計語言2022/10/14史忠植邏輯基礎16邏輯程序設計歸結原理(消解原理)2022/10/10史忠植歸結原理例：

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

??2022/10/14史忠植邏輯基礎17歸結原理例：2022/10/10史忠植邏輯基礎17Horn邏輯文字：原子公式(正文字)或原子公式的否定(負文字)。P,Q,?R子句：若干文字的析取。?P∨Q∨RHorn子句：子句L1∨L2∨…∨Ln中如果至多只含一個正文字，那么該子句稱為Horn子句。Horn子句P∨?Q1∨?Q2∨…∨?Qn通常表示為：PQ1,Q2,…,Qn2022/10/14史忠植邏輯基礎18Horn邏輯文字：原子公式(正文字)或原子公式的否定(負文字Horn子句的類型2022/10/14史忠植邏輯基礎19

◆過程：PQ1,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)，與事實匹配，產生目標?。因而調用成功，輸出“是”。Horn子句的類型2022/10/10史忠植邏輯基礎19

PrologProlog(Programminginlogic)語言是以Horn子句邏輯為基礎的高級程序設計語言。1972年，法國馬賽大學的Alain.Colmerauer提出了Prolog的雛型。1975年，Prolog被用于問題求解系統(tǒng)。此后，它在許多領域獲得了應用，如關系數據庫、定理證明、智能問題求解、計算機輔助設計、規(guī)劃生成等領域。2022/10/14史忠植邏輯基礎20PrologProlog(ProgramminginlProlog的構成事實：關于對象性質和關系的事實語句；student(john)，married(tom,mary)規(guī)則：關于對象性質和關系的定義規(guī)則語句；它與事實的不同在于，規(guī)則所定義的性質、關系依賴與其它的性質和關系，因此規(guī)則呈蘊涵語句形式。

B:—

A “如果A則B”bird(x):—animal(x)，has(x,feather)問題：關于對象性質或關系的詢問。

?—student(john)

?—married(mary，x)2022/10/14史忠植邏輯基礎21Prolog的構成事實：關于對象性質和關系的事實語句；2022022/10/14史忠植邏輯基礎22Prolog的執(zhí)行方式搜索：在程序中自上而下地搜索事實和規(guī)則；匹配：將目標中的項與事實和規(guī)則進行匹配；回溯：當目標中一項失敗時，如果目標中有已經成功的的項(應在失敗項的左邊)，那末就重新調用這些成功項中最右邊的一個，謀求新的成功。2022/10/10史忠植邏輯基礎22Prolog的執(zhí)行2022/10/14史忠植邏輯基礎23Prolog語言的基本文法Prolog語言的最基本語言成分是項(term)，一個項或者是常量，或者是變量，或者是一個結構。常量：是指對象和對象之間的特定關系的名；

整數，如0，22，1586等；

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

Prolog中變量可以用大寫字母，下劃線，以及由它們開頭的字母串。如X,Y,Answer,_value等。結構：是常量和變量的序列，它由一個函子(函詞或謂詞)和該函子的自變量所組成。如：likes(john,X) married(mary,jack)2022/10/10史忠植邏輯基礎23Prolog語言的例子2022/10/14史忠植邏輯基礎24(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)(規(guī)則)(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是朋友例子2022/10/10史忠植邏輯基礎24(事實)(7)2022/10/14史忠植邏輯基礎25Prolog的基本特點Horn子句邏輯是Prolog的基礎。Prolog既是一種邏輯程序設計語言，又是一個邏輯系統(tǒng)。Prolog是一種描述性語言，它是一種面向問題的語言，你只需要告訴它要做什么，即給出問題的形式描述，而不需要知道應該如何做。Prolog完全依靠匹配、回溯來進行搜索。Prolog的求解過程是一個尋求否證的消解過程。Prolog也使用元語言種的謂詞，有很強的描述能力。Prolog采用統(tǒng)一的數據結構——項，它包含控制成分，且有專門進行數值計算和符號處理的模塊。2022/10/10史忠植邏輯基礎25Prolog的基本非單調邏輯單調邏輯非單調邏輯區(qū)別2022/10/14史忠植邏輯基礎26非單調邏輯單調邏輯2022/10/10史忠植邏輯基礎26單調邏輯在現有知識的基礎上，通過嚴密的邏輯論證和推理獲得的新知識必須與已有的知識相一致。A，AB

B推理系統(tǒng)的定理集合隨著推理過程的進行而單調地增大。單調性：

(1)∈

Th() (2)若1?

2，則Th(1)?Th(2) (3)Th(Th())＝Th() (不動點)2022/10/14史忠植邏輯基礎27單調邏輯在現有知識的基礎上，通過嚴密的邏輯論證和推理獲得的新2022/10/14史忠植邏輯基礎28非單調邏輯推理系統(tǒng)的定理集合并不隨著推理過程的進行而單調地增大，新推出的定理很可能會否定、改變原來的一些定理，使得原來能夠解釋的某些現象變得不能解釋了。新規(guī)則：

(4)

??P (不動點)2022/10/10史忠植邏輯基礎28非單調邏輯推理系統(tǒng)默認邏輯1980年，Reiter提出了默認邏輯(DefaultLogic)。

“一般情況下鳥是會飛的”

“鴕鳥不會飛”

“企鵝不會飛”2022/10/14史忠植邏輯基礎29默認邏輯1980年，Reiter提出了默認邏輯(Defaul2022/10/14史忠植邏輯基礎30默認規(guī)則一個默認規(guī)則是如下形式的規(guī)則：

(x):稱為前提條件

i(x):稱為默認條件，或檢驗條件

(x):稱為結論為簡便，通常情況下可以省略檢驗條件中的M。規(guī)則的使用：如果規(guī)則的前提條件滿足，且現有的知識導不出檢驗條件的否定?i(x)，則可以得出結論成立。2022/10/10史忠植邏輯基礎30默認規(guī)則一個默2022/10/14史忠植邏輯基礎31默認理論一個默認理論由兩個部分組成，即默認規(guī)則集D和公式集W，一般用二元組來表示

＝<D,W>若D中的規(guī)則是閉規(guī)則時，則為閉默認理論。定義：設＝<D,W>為一閉默認理論，為關于D的一個算子，作用于任意的命題集合S，而其值為滿足下列三個性質的最小命題集合(S)：

(1)W

(S) (2)Th((S))=(S)，其中Th((S))={A|(S)?

A} (3)如果D中有規(guī)則 ，且∈(S)，?1,…,?m?

S，那么∈(S)2022/10/10史忠植邏輯基礎31默認理論一個默2022/10/14史忠植邏輯基礎32默認理論的擴充定義：對命題集合E，如果(E)=E，則E稱為關于D的算子的不動點(fixpoint)。此時稱E為默認理論＝<D,W>的一個擴充(extension)。例1：設D

＝{ }，W

＝，計算默認理論＝<D,W>的擴充。＝<D,W>有唯一的擴充E

＝Th({?B,?F})。2022/10/10史忠植邏輯基礎32默認理論的擴充定義默認理論的擴充2022/10/14史忠植邏輯基礎33例2：設D

＝{ }，W

＝{B,CF∨A,A∧C

?E}，計算默認理論＝<D,W>的擴充。＝<D,W>有三個擴充E1

＝Th(W{A,C})E2

＝Th(W{A,E})E3

＝Th(W{C,E,G})默認理論的擴充2022/10/10史忠植邏輯基礎33例22022/10/14史忠植邏輯基礎34限定推理1980年，McCarthy提出了一種非單調的推理——限定推理(Circumscription)。基本思想：從某些事實A出發(fā)能夠推出具有某一性質的P的對象就是滿足性質P的全部對象。只有當發(fā)現其它對象也具有該性質時，才修改這種看法。2022/10/10史忠植邏輯基礎34限定推理1980年限定邏輯2022/10/14史忠植邏輯基礎35

限定邏輯CIRC是一種極小化邏輯。下面，從一個基于極小模型定義的命題限定出發(fā)，給出限定的基本定義,進而給出一階限定的基本結果，并將它推廣。定義2.1設L0是一個命題語言，p1,p2是在命題語言L0

中的兩個賦值。稱p1小于p2

，記為p1p2,當且僅當對任一命題變元x,如果p1(x)=l,則p2(x)=l。限定邏輯2022/10/10史忠植邏輯基礎35限限定邏輯2022/10/14史忠植邏輯基礎36

定義2.2設A

是一個公式，稱A的一個賦值p是極小的，當且僅當不存在A的其它賦值p'使得p'p。顯然,是一個偏序關系。p1

p2表示p1包含的真命題比p2

少。極小賦值包含的真命題極小。定義2.3極小后承M。設A,B是兩個公式，A

M

B

當且僅當B在所有A

的極小模型中都為真。極小模型是非單調的，它以命題的極小化作為優(yōu)先模型的準則。限定邏輯2022/10/10史忠植邏輯基礎36定限定邏輯2022/10/14史忠植邏輯基礎37

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

Z-極小賦值，當且僅當不存在A的其它賦值p‘使得pp’,定義如下：設p1,p2

是兩個賦值，p1

Z-p2

當且僅當對任一zZ,

若p1

(Z)=l,則p2

(Z)=l。

限定邏輯2022/10/10史忠植邏輯基礎37定限定邏輯2022/10/14史忠植邏輯基礎38

定義2.5命題限定P

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

P

當且僅當

在所有A的

p-

極小賦值中都為真。

定理2.1Ap當且僅當A

P

限定邏輯2022/10/10史忠植邏輯基礎38定義限定邏輯2022/10/14史忠植邏輯基礎39

定義2.6令L是一個一階語言，T是一個L的公式，它包含謂詞元組集。設M[T]和M*[T]是公式T的兩個模型。定義M*[T]優(yōu)先于M[T],

記為M*[T]

M[T]，當且僅當

(1)M和M*有相同的對象域，

(2)除外，公式T中所有的其它關系和函數常數在M和M*都有相同的解釋，

(3)在M*中的外延是在M中的子集。限定邏輯2022/10/10史忠植邏輯基礎39定義限定邏輯2022/10/14史忠植邏輯基礎40

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

M。定義2.7Mm是的最小模型，當且僅當

MMm,M=Mm

限定邏輯2022/10/10史忠植邏輯基礎40限定邏輯2022/10/14史忠植邏輯基礎41

例如設論域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

限定邏輯2022/10/10史忠植邏輯基礎41例如2022/10/14史忠植邏輯基礎42真值維護系統(tǒng)TMS1979年，Doyle提出了一種非單調推理系統(tǒng)——真值維護系統(tǒng)(TruthMaintenanceSystem)真值維護系統(tǒng)是大型推理系統(tǒng)的的一個子系統(tǒng)，實現知識庫中信念(belief)的修改與維護。其基本問題有：必須在不完全的、有限的信息基礎上作出假設的決策，使得該假設成為知識庫的信念；當這些決策的結論被以后的事實證明為錯誤時，如何對其信念進行修正。2022/10/10史忠植邏輯基礎42真值維護系統(tǒng)TMS2022/10/14史忠植邏輯基礎43基本數據結構:

結點：表示信念

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

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

新理由的加入——把某個信念與該結點聯(lián)接起來實現過程： 默認假設的形成； 相關性回溯過程。真值維護系統(tǒng)TMS2022/10/10史忠植邏輯基礎43基本數據結構:基本2022/10/14史忠植邏輯基礎44信念知識表示每一個命題或規(guī)則均稱為結點，它分為兩類：

IN-結點：相信為真

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

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

條件證明CP：出現矛盾的原因。2022/10/10史忠植邏輯基礎44信念知識表示每一個2022/10/14史忠植邏輯基礎45(SL(<IN-結點表>)(<OUT-結點表>))IN-結點表中的IN-結點表示知識庫中的已知知識;OUT-結點表中的OUT-結點表示這些結點的否定。例1:(1)現在是夏天 (SL()())(2)天氣很潮濕 (SL(1)())結點(1)不依賴于任何別的結點中的當前信念或默認信念,因而這種結點稱為前提;結點(2)則依賴于當前結點(1)的信念.所以，與一階邏輯不同的是,TMS可以撤消前提,并可以對知識庫作適當修改.（1）支持表SL信念知識表示2022/10/10史忠植邏輯基礎45(SL(<IN-結2022/10/14史忠植邏輯基礎46例2:

(1)現在是夏天 (SL()()) (2)天氣很潮濕 (SL(1)(3)) (3)天氣很干燥若結點(1)是IN,結點(3)是OUT,則結點(2)才為IN.若在某個時刻出現結點(3)的證據,則結點(2)就變?yōu)镺UT,因為它不再有一個有效的證實.象結點(2)這樣的結點稱為假設,它與非空的OUT結點表的SL證實有關.OUT結點(3)是結點(2)的證實的一部分.但如果結點(3)不存在,就不能這樣表示了.在TMS中,它僅利用證實來維持一個相容的信念數據庫,而它本身并不產生證實.信念知識表示2022/10/10史忠植邏輯基礎46例2:信念知識表示2022/10/14史忠植邏輯基礎47(CP<結論><IN-假設><OUT-假設>)如果結論結點為IN-結點,以及下列條件成立: (1)IN假設中的每個結點都是IN-結點; (2)OUT-假設中的每個結點都是OUT-結點.那么條件證明CP是有效的.一般說來,OUT-假設總是空集.TMS要求假設集劃分成兩個不相交的子集,分別為不導致矛盾的假設和導致矛盾的假設.通常只要在IN-假設中的結點為IN,OUT-假設中的結點為OUT,則結論結點為IN.（2）條件證明CP信念知識表示2022/10/10史忠植邏輯基礎47(CP<結論>2022/10/14史忠植邏輯基礎48默認假設

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

,Fi+1,…,Fn))而選取Fi為默認假設.如果不存在任何其它關于如何進行選擇的信息，則可以認為除Fi之外其它任何時候選都不是可信的．這樣Fi為IN,其它Fj(ij)均為OUT.但如果接收到一個有效的理由支持某個其它的侯選Fj,則Fj就為IN,而導致Fi的假設失敗而變?yōu)镺UT.2022/10/10史忠植邏輯基礎48默認假設令{F2022/10/14史忠植邏輯基礎49相關回溯當知識庫中出現不一致時,TMS將尋找并刪除已做的一個不正確的默認邏輯,恢復一致性.它包括三個步驟: (1)從產生的矛盾結點開始,回溯跟蹤該矛盾結點的理由充足的支持以尋找矛盾的假設集,并從中去掉至少一個假設信念以消除矛盾. (2)構造一個結點記錄矛盾產生的原因. (3)從S中選取假設A(即不合理假設),并證實列在其理由充足的支持條件中的一個OUT-結點.2022/10/10史忠植邏輯基礎49相關回溯當知識2022/10/14史忠植邏輯基礎50

(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.進而矛盾就消除了.相關回溯2022/10/10史忠植邏輯基礎50 (4)矛盾 2022/10/14史忠植邏輯基礎51情景演算

情景演算是一種一階邏輯語言，主要是用來表示動態(tài)變化的世界的。世界的所有變化過程都是“動作”的結果。一個可能世界歷史可以簡單表示為動作的序列，它是通過稱之為情景的一階項所表示的。

常量S0表示初始情景，即動作還沒有發(fā)生時的情景。

do(,s)表示在情景s中執(zhí)行動作之后的后繼情景。

do(put(A,B),s)表示當世界狀態(tài)為s時，將A放到B上的結果這種情景。

do(putdown(A)),do(walk(L)),do(pickup(A))是一種表示世界歷史由動作序列[pickup(A),walk(L),

putdown(A)]所組成的，它們按照從右到左的方式組織。

2022/10/10史忠植邏輯基礎51情景演算情2022/10/14史忠植邏輯基礎52定義1定義Lsitcalc語言的動作理論D為如下形式：D=∑?Dss?Dap

?Duna?DSo

其中：

∑：基礎的、針對情景演算的獨立于領域的公理。

Dap：動作前提條件公理；

Dss：后續(xù)狀態(tài)公理；

Duna：針對原子動作的唯一命名公理；

DSo：描述初始情形的公理。

情景演算2022/10/10史忠植邏輯基礎52定義1定義Lsi2022/10/14史忠植邏輯基礎53

基于情景演算的一些基本理論和方法，我們利用它們來刻畫主體的復雜動作和過程，將主體的各個部件加以描述。

<1>原子動作Do(a,s,s)Poss(a[s],s)∧s=do(a[s],s)

<2>檢驗動作Do(φ?,s,s)φ[s]∧s=s

<3>順序動作Do([δ1,δ2],s,s)(?s*).Do([δ1],s,s*)∧Do([δ2],s*,s)def＝def＝def＝情景演算2022/10/10史忠植邏輯基礎53 基于情景演算2022/10/14史忠植邏輯基礎54<4>兩個動作的不確定選擇Do((δ1|δ2),s,s)(?s*).Do(δ1,s,s)∨Do(δ2,s,s)def＝<5>動作參數的不確定選擇Do((πx)δ(x),s,s)(?x).Do(δ(x),s,s)

def＝<6>不確定反復Do(δ*,s,s) (?P).{(?s1)P(s1,s1)∧(?s1,s2,s3) [P(s1,s2)∧Do(δ,s2,s3)?P(s1,s3)]} ?P(s,s)def＝情景演算2022/10/10史忠植邏輯基礎54<4>兩個動作的2022/10/14史忠植邏輯基礎55動作理論與情景演算的研究◆MaCarthy針對動態(tài)領域中的問題求解和邏輯程序設計提出了情景演算?！?/p>

Reiter，FangzhenLin，Pirria，Lifschitz等人主要將情景演算進行了一些擴充，對狀態(tài)約束、動作理論、動態(tài)關系等方面進行了深入的研究，并以數據庫、機器人等動態(tài)領域為背景，做了一些邏輯程序設計以及應用等研究。

◆

Levesque和Reiter提出了一種新的動態(tài)邏輯設計語言

Golog/ConGolog◆Baral等人重點對狀態(tài)的描述、動作的表示與推理以及動態(tài)領域中的知識表示等方面做了一些工作，提出了一種邏輯程序設計語言

A-Prolog，

2022/10/10史忠植邏輯基礎55動作理論與情景演算2022/10/14史忠植高級人工智能56描述邏輯

DescriptionLogics◆

什么是描述邏輯？◆為什么用描述邏輯？◆描述邏輯的研究進展◆描述邏輯的體系結構◆描述邏輯的構造算子◆描述邏輯的推理問題◆我們的工作2022/10/10史忠植高級人工智能56描述邏輯2022/10/14史忠植高級人工智能57什么是描述邏輯(DL)？

一種基于對象的知識表示的形式化，也叫概念表示語言或術語邏輯。建立在概念和關系(Role)之上

－概念解釋為對象的集合 －關系解釋為對象之間的二元關系源于語義網絡和KL-ONE是一階邏輯FOL的一個可判定的子集具有合適定義的語義(基于邏輯)2022/10/10史忠植高級人工智能57什么是描述邏輯2022/10/14史忠植高級人工智能58描述邏輯的特點◆是以往表示工具的邏輯重構和統(tǒng)一形式化 －

框架系統(tǒng)

(Frame-basedsystems)

－

語義網絡

(SemanticNetworks)

－

面向對象表示

(OOrepresentation)

－

語義數據模型

(Semanticdatamodels)

－

類型系統(tǒng)

(Typesystems)

－

特征邏輯

(FeatureLogics)◆

具有很強的表達能力◆是可判定的，總能保證推理算法終止2022/10/10史忠植高級人工智能58描述邏輯的特點2022/10/14史忠植高級人工智能59描述邏輯的應用

◆概念建?！舨樵儍?yōu)化和視圖維護◆自然語言語義◆智能信息集成◆信息存取和智能接口◆工程的形式化規(guī)范◆術語學和本體論◆規(guī)劃◆…2022/10/10史忠植高級人工智能59描述邏輯的應用2022/10/14史忠植高級人工智能60為什么用描述邏輯？若直接使用一階邏輯，而不附加任何約束，則：◆知識的結構將被破壞，這樣就不能用來驅動推理◆對獲得可判定性和有效的推理問題來說，其表達能力太高，（也許是太抽象了）◆對興趣表達，但仍然可判定的理論，其推理能力太低。DL的重要特征是：◆很強的表達能力；◆可判定性，它能保證推理算法總能停止，并返回正確的結果。2022/10/10史忠植高級人工智能60為什么用描述邏2022/10/14史忠植高級人工智能61在眾多知識表示的形式化方法中，描述邏輯在十多年來受到人們的特別關注，主要原因在于以下三點:◆它們有清晰的模型-理論機制;◆它們很適合于通過概念分類學來表示應用領域；◆它們提供了很用的推理服務。它們可以被認為是從基于框架的表示形式化向著精確的語義特征方向發(fā)展。此外，描述邏輯將分類學中表示和推理（專業(yè)推理）與在分類學中項的事實或實例的表示和推理（斷言推理）區(qū)別開來。為什么用描述邏輯？2022/10/10史忠植高級人工智能61在眾多知識表示描述邏輯的研究進展2022/10/14史忠植高級人工智能62◆描述邏輯的基礎研究 研究描述邏輯的構造算子、表示和推理的基本問題，如可滿足性、包含檢測、一致性、可判定性等。 一般都在最基本的ALC的基礎上在擴展一些構造算子，如數量約束、逆關系、特征函數、關系的復合等。

TBox和Abox上的推理問題、包含檢測算法等。

Schmidt-Schaub

和Smolka首先建立了基于描述邏輯ALC的Tableau算法，該算法能在多項式時間內判斷描述邏輯ALC概念的可滿足性問題。描述邏輯的研究進展2022/10/10史忠植高級人工智能描述邏輯的擴展研究2022/10/14史忠植高級人工智能63

A.Artale和E.Franconi(1998)提出了一個知識表示系統(tǒng)，用時間約束的方法將狀態(tài)、動作和規(guī)劃的表示統(tǒng)一起來。 為了能讓描述邏輯處理模態(tài)詞，F.Baader將模態(tài)操作引入描述邏輯，證明了該描述邏輯公式的可滿足性問題是可判定的。

Wolter等對具有模態(tài)算子的描述邏輯進行了深入系統(tǒng)的調查分析，并證明在恒定的領域假設下多種認知和時序描述邏輯是可判定的。

另外如時序擴展(Artale,Wolter)、模糊擴展(Straccia)等。描述邏輯的擴展研究2022/10/10史忠植高級人工智能2022/10/14史忠植高級人工智能64描述邏輯在許多領域中被作為知識表示的工具，如 信息系統(tǒng)（Catarci,1993） 數據庫（Borgida,1995;Bergamaschi1992;Sheth,1993） 軟件工程(Devambu,1991)

網絡智能訪問（Levy，

1996；

Blanco，1994） 規(guī)劃（Seida,1992）等

Horrocks對表達能力較強的描述邏輯進行了研究，并建立了一些邏輯框架和系統(tǒng)，如FaCT，SHIQ等。他和DieterFensel等人將描述邏輯、語義網和DAML結合起來，提出了DAML+OIL，其中以描述邏輯作為核心的表示和推理基礎。并在XML及其RDF上面進行了擴展，用描述邏輯來研究語義網絡和本體論。描述邏輯的應用研究2022/10/10史忠植高級人工智能64描述邏輯在許多研究背景語義Web[Bemers-Lee1998,2006]

描述邏輯：OWL的邏輯基礎[Horrocks2003]特點：描述能力+可判定；有效的判定算法和推理機制。局限：不能處理動態(tài)領域中與動作相關的知識。OWLLiteOWLDLOWLFullSHIF(D)SHOIN(D)不可判定研究背景語義Web[Bemers-Lee1998,22022/10/14史忠植高級人工智能66描述邏輯的體系結構一個描述邏輯系統(tǒng)包含四個基本組成部分：1）表示概念和關系（Role）的構造集2）Tbox——關于概念術語的斷言3）Abox——關于個體的斷言4）Tbox和Abox上的推理機制。

2022/10/10史忠植高級人工智能66描述邏輯的體系2022/10/14史忠植高級人工智能67◆概念

——解釋為一個領域的子集

例子：所有在校學習的人員的集合構成“學生”概念 又如：孩子，已婚的，哺乳動物等概念{x|Student(x)}，{x|Married(x)}◆

關系(Roles)——屬性(二元謂詞，關系)例子：朋友，愛人，{<x,y>|Friend(x,y)}，{<x,y>|Loves(x,y)}DL的基本元素——概念和關系2022/10/10史忠植高級人工智能67◆概念——2022/10/14史忠植高級人工智能68知識庫TBox(模式)Man?Human?MaleHappy-father?Human?

?Has-child.Female?

…Abox(數據)John:Happy-father<John,Mary>:Has-child推理系統(tǒng)接口2022/10/10史忠植高級人工智能68TBox(模式TBox語言2022/10/14史忠植高級人工智能69TBox語言是描述領域結構的公理的集合定義:引入概念的名稱A?

C,A

?

CFather?

Man?

?

has-child.HumanHuman?

Animal?

Biped包含：聲明包含關系的公理C

?

D

(C?

D

C

?

D

，D

?

C)?

has-degree.Masters?

?

has-degree.Bachelors一個解釋I滿足：C?

D

iffCI

=DI C?

D

iffCI

?

DI一個解釋I滿足TBoxT

iff它滿足T中的每個公理(I?T)TBox語言2022/10/10史忠植高級人工智能69T2022/10/14史忠植高級人工智能70◆概念斷言

——表示一個對象是否屬于某個概念

a:C例如：Tom是個學生，表示為

Tom

:Student 或者 Student(Tom)

John

:Man?

?

has-child.Female◆關系斷言

——表示兩個對象是否滿足一定的關系

<a,b>:R例如：John有個孩子叫Mary

<John,

Mary>

:has-childABox語言是描述具體情形的公理的集合ABox語言2022/10/10史忠植高級人工智能70◆概念斷言語義解釋2022/10/14史忠植高級人工智能71一個解釋I滿足：a:

C

iffaI

∈

CI

<a,b>:R

iff<aI,bI>

∈RI一個解釋I滿足ABoxA

iff它滿足A中的每個公理記為：I?A一個解釋I滿足知識庫=<T,A

>

iff它滿足T和A

記為：I?語義解釋2022/10/10史忠植高級人工智能71一個解2022/10/14史忠植高級人工智能72

語法和語義構造算子語法語義例子原子概念AAI?△IHuman原子關系RRI?△I△Ihas-child對概念C,D和關系(role)R合取C?DCI∩DIHuman?Male析取C?DCI?

DIDoctor?Lawyer非?C△I\C?Male存在量詞?

R.C{x|?y.<x,y>∈

RI∧y∈CI}?

has-child.Male全稱量詞?R.C{x|?y.<x,y>∈

RI

y∈CI}?

has-child.Doctor2022/10/10史忠植高級人工智能72語法和語義構2022/10/14史忠植高級人工智能73一般地，描述邏輯依據提供的構造算子，在簡單的概念和關系上構造出復雜的概念和關系。通常DL至少包含以下算子： ◆合取(?)，吸取(?)，非(?) ◆量詞約束：存在量詞(?)，全稱量詞(?)最基本的DL稱之為ALC例如，ALC中概念Happy-father定義為：

Man?

?

has-child.Male

?

?

has-child.Female

?

?has-child.(Doctor?

Lawyer)DL中的構造算子2022/10/10史忠植高級人工智能73一般地，描述邏2022/10/14史忠植高級人工智能74構造算子語法語義例子數量約束≥nR.C{x||{y|<x,y>∈

RI,y∈CI}

|≥n}≥3

has-child.Male≤nR.C{x||{y|<x,y>∈

RI,y∈CI}

|≤n}≤3

has-child.Male逆R-{<y,x>|<x,y>∈

RI}has-child-傳遞閉包R*(RI)*has-child*DL中的其它算子topT△IMale?

?MaleBottomMan?

?Man另外，有兩個類似于FOL中的全集(true)和空集(false)的算子2022/10/10史忠植高級人工智能74構造算子語法語2022/10/14史忠植高級人工智能75DL中添加算子一般地，在描述邏輯中添加不同的算子，則得到不同表達能力的描述邏輯，其復雜性問題也不盡相同。例如，在ALC的基礎上添加逆(-)算子，則構成ALCI若再加上數量約束算子(≥n,≤n)，則構成ALCIQ。若在描述邏輯中添加時序算子，則構成為時序描述邏輯(TemporalDescriptionLogic)，例如，可以添加：

Until算子U：C

U

D Since算子S：CSD還可以加入其它算子，如模態(tài)算子□，

，○等。2022/10/10史忠植高級人工智能75DL中添加算子2022/10/14史忠植高級人工智能76描述邏輯中的推理1)

一致性（協(xié)調性consistency）2)可滿足性(satisfiability)3)包含檢測（subsumption）4)實例檢測

(instancechecking)5)Tableaux算法6）可判定性7）計算復雜性2022/10/10史忠植高級人工智能76描述邏輯中的推2022/10/14史忠植高級人工智能77一致性檢測(Consistency)◆知識庫<T,A>是協(xié)調的嗎？ 即檢測是否有<T,A>的模型(解釋)I？◆C關于TboxT是協(xié)調的嗎？

即檢測是否有T的模型I使得C

≠

？2022/10/10史忠植高級人工智能77一致性檢測(C2022/10/14史忠植高級人工智能78概念可滿足性(Satisfiablity)

對一個概念C，如果存在一個解釋I使得CI是非空的，則稱概念C是可滿足的，否則是不可滿足的。

檢驗一個概念的可滿足性，實際上就是看是否有解釋使得這個概念成立。例如：概念Male?

Female，即需要檢測是否有性別既是男的又是女的這樣的人。若確實是沒有這種兩性人，則我們斷言，這個概念是不可滿足的。又如概念：student?worker，它是可滿足的。即代表那些在職學生的集合。定理：概念C是可滿足的，當且僅當C不包含于。

2022/10/10史忠植高級人工智能78概念可滿足性(2022/10/14史忠植高級人工智能79◆在知識庫中檢測：

C?

D？ 即檢測CI

?

DI是否在所有的解釋中成立？概念包含(Subsumption)例如：

bird?animal computer?equipment◆在Tbox中檢測：

C?

D？ 即檢測CI

?

DI是否在TboxT的所有解釋中成立？2022/10/10史忠植高級人工智能79◆在知識庫中檢2022/10/14史忠植高級人工智能80C?

Diff

C?

?D是不可滿足的。C?T

Diff

C?

?D關于T是不可滿足的。C關于T是一致的iffC?T

A?

?A包含與可滿足性的關系?DDCC?

?D＝