第二章人工智能邏輯第二部分課件

第二章人工智能邏輯

第二部分史忠植中國科學(xué)院計(jì)算技術(shù)研究所高級(jí)人工智能12/10/20221史忠植高級(jí)人工智能第二章人工智能邏輯

第二部分史忠植高級(jí)人工智能12/8/描述邏輯

DescriptionLogics12/10/20222史忠植高級(jí)人工智能描述邏輯

DescriptionLogics12/主要內(nèi)容◆

什么是描述邏輯？◆為什么用描述邏輯？◆描述邏輯的研究進(jìn)展◆描述邏輯的體系結(jié)構(gòu)◆描述邏輯的構(gòu)造算子◆描述邏輯的推理問題◆我們的工作12/10/20223史忠植高級(jí)人工智能主要內(nèi)容◆什么是描述邏輯？12/8/20223史忠植高1什么是描述邏輯(DL)？ 一種基于對(duì)象的知識(shí)表示的形式化，也叫概念表示語言或術(shù)語邏輯。建立在概念和關(guān)系(Role)之上

－概念解釋為對(duì)象的集合 －關(guān)系解釋為對(duì)象之間的二元關(guān)系源于語義網(wǎng)絡(luò)和KL-ONE是一階邏輯FOL的一個(gè)可判定的子集具有合適定義的語義(基于邏輯)12/10/20224史忠植高級(jí)人工智能1什么是描述邏輯(DL)？ 一種基于對(duì)象的知識(shí)表示的形式化特點(diǎn)◆是以往表示工具的邏輯重構(gòu)和統(tǒng)一形式化 －

框架系統(tǒng)(Frame-basedsystems) －

語義網(wǎng)絡(luò)(SemanticNetworks) －

面向?qū)ο蟊硎?OOrepresentation) －

語義數(shù)據(jù)模型(Semanticdatamodels) －

類型系統(tǒng)(Typesystems) －

特征邏輯(FeatureLogics)◆

具有很強(qiáng)的表達(dá)能力◆是可判定的，總能保證推理算法終止12/10/20225史忠植高級(jí)人工智能特點(diǎn)◆是以往表示工具的邏輯重構(gòu)和統(tǒng)一形式化12/8/2022描述邏輯的應(yīng)用

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

Schmidt-Schaub和Smolka首先建立了基于描述邏輯ALC的Tableau算法，該算法能在多項(xiàng)式時(shí)間內(nèi)判斷描述邏輯ALC概念的可滿足性問題。12/10/20229史忠植高級(jí)人工智能3描述邏輯的研究進(jìn)展12/8/20229史忠植高級(jí)人工◆描述邏輯的擴(kuò)展研究

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

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

另外如時(shí)序擴(kuò)展(Artale,Wolter)、模糊擴(kuò)展(Straccia)等。12/10/202210史忠植高級(jí)人工智能◆描述邏輯的擴(kuò)展研究12/8/202210史忠植高級(jí)人◆描述邏輯的應(yīng)用研究描述邏輯在許多領(lǐng)域中被作為知識(shí)表示的工具，如 信息系統(tǒng)（Catarci,1993） 數(shù)據(jù)庫（Borgida,1995;Bergamaschi1992;Sheth,1993） 軟件工程(Devambu,1991) 網(wǎng)絡(luò)智能訪問（Levy，1996；Blanco，1994） 規(guī)劃（Seida,1992）等 Horrocks對(duì)表達(dá)能力較強(qiáng)的描述邏輯進(jìn)行了研究，并建立了一些邏輯框架和系統(tǒng)，如FaCT，SHIQ等。他和DieterFensel等人將描述邏輯、語義網(wǎng)和DAML結(jié)合起來，提出了DAML+OIL，其中以描述邏輯作為核心的表示和推理基礎(chǔ)。并在XML及其RDF上面進(jìn)行了擴(kuò)展，用描述邏輯來研究語義網(wǎng)絡(luò)和本體論。12/10/202211史忠植高級(jí)人工智能◆描述邏輯的應(yīng)用研究12/8/202211史忠植高級(jí)人4描述邏輯的體系結(jié)構(gòu)一個(gè)描述邏輯系統(tǒng)包含四個(gè)基本組成部分：1）表示概念和關(guān)系（Role）的構(gòu)造集2）Tbox——關(guān)于概念術(shù)語的斷言3）Abox——關(guān)于個(gè)體的斷言4）Tbox和Abox上的推理機(jī)制。

12/10/202212史忠植高級(jí)人工智能4描述邏輯的體系結(jié)構(gòu)一個(gè)描述邏輯系統(tǒng)包含四個(gè)基本組成部分：◆概念——解釋為一個(gè)領(lǐng)域的子集

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

關(guān)系(Roles)——屬性(二元謂詞，關(guān)系)例子：朋友，愛人，{<x,y>|Friend(x,y)}，{<x,y>|Loves(x,y)}1）DL的基本元素——概念和關(guān)系12/10/202213史忠植高級(jí)人工智能◆概念——解釋為一個(gè)領(lǐng)域的子集◆關(guān)系(Roles)知識(shí)庫TBox(模式)Man?Human?MaleHappy-father?Human?

?Has-child.Female?

…Abox(數(shù)據(jù))John:Happy-father<John,Mary>:Has-child推理系統(tǒng)接口12/10/202214史忠植高級(jí)人工智能TBox(模式)Abox(數(shù)據(jù))推理系統(tǒng)接口12/8/2022）TBox語言 是描述領(lǐng)域結(jié)構(gòu)的公理的集合定義:引入概念的名稱A?

C,A

?

CFather?

Man?

?

has-child.HumanHuman?

Animal?

Biped包含：聲明包含關(guān)系的公理C

?

D

(C?

D

C

?

D，D

?

C)?

has-degree.Masters?

?

has-degree.Bachelors一個(gè)解釋I滿足：C?

D

iffCI

=DI C?

D

iffCI

?

DI一個(gè)解釋I滿足TBoxT

iff它滿足T中的每個(gè)公理(I?T)12/10/202215史忠植高級(jí)人工智能2）TBox語言定義:引入概念的名稱12/8/20221◆概念——表示實(shí)體(一元謂詞，類)例子：學(xué)生，已婚的{x|Student(x)}，{x|Married(x)} Bird

?

Animal,Man?Human◆

關(guān)系(Roles)——屬性(二元謂詞，關(guān)系)例子：朋友，愛人{(lán)<x,y>|Friend(x,y)}，{<x,y>|Loves(x,y)}TBox實(shí)例12/10/202216史忠植高級(jí)人工智能◆概念——表示實(shí)體(一元謂詞，類)◆關(guān)系(Roles)◆概念斷言——表示一個(gè)對(duì)象是否屬于某個(gè)概念 a:C例如：Tom是個(gè)學(xué)生，表示為

Tom

:Student 或者 Student(Tom)

John

:Man?

?

has-child.Female◆

關(guān)系斷言——表示兩個(gè)對(duì)象是否滿足一定的關(guān)系 <a,b>:R例如：John有個(gè)孩子叫Mary

<John,

Mary>

:has-child3）ABox語言（斷言部分） 是描述具體情形的公理的集合12/10/202217史忠植高級(jí)人工智能◆概念斷言——表示一個(gè)對(duì)象是否屬于某個(gè)概念◆關(guān)系斷言一個(gè)解釋I滿足：a:

C

iffaI

∈

CI<a,b>:R

iff<aI,bI>

∈RI一個(gè)解釋I滿足ABoxA

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

>

iff它滿足T和A記為：I?12/10/202218史忠植高級(jí)人工智能一個(gè)解釋I滿足：a:CiffaI∈CI14）語法和語義構(gòu)造算子語法語義例子原子概念A(yù)AI?△IHuman原子關(guān)系RRI?△I△Ihas-child對(duì)概念C,D和關(guān)系(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.Doctor12/10/202219史忠植高級(jí)人工智能4）語法和語義構(gòu)造算子語法語義例子原子概念A(yù)AI?△I一般地，描述邏輯依據(jù)提供的構(gòu)造算子，在簡單的概念和關(guān)系上構(gòu)造出復(fù)雜的概念和關(guān)系。通常DL至少包含以下算子： ◆合取(?)，吸取(?)，非(?) ◆量詞約束：存在量詞(?)，全稱量詞(?)最基本的DL稱之為ALC例如，ALC中概念Happy-father定義為： Man?

?

has-child.Male

?

?

has-child.Female

?

?has-child.(Doctor?

Lawyer)5DL中的構(gòu)造算子12/10/202220史忠植高級(jí)人工智能一般地，描述邏輯依據(jù)提供的構(gòu)造算子，在簡單的5DL中的構(gòu)造構(gòu)造算子語法語義例子數(shù)量約束≥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另外，有兩個(gè)類似于FOL中的全集(true)和空集(false)的算子12/10/202221史忠植高級(jí)人工智能構(gòu)造算子語法語義例子數(shù)量約束≥nR.C{x||{y在DL中添加算子一般地，在描述邏輯中添加不同的算子，則得到不同表達(dá)能力的描述邏輯，其復(fù)雜性問題也不盡相同。例如，在ALC的基礎(chǔ)上添加逆(-)算子，則構(gòu)成ALCI若再加上數(shù)量約束算子(≥n,≤n)，則構(gòu)成ALCIQ。若在描述邏輯中添加時(shí)序算子，則構(gòu)成為時(shí)序描述邏輯(TemporalDescriptionLogic)，例如，可以添加： Until算子U：C

U

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

，○等。12/10/202222史忠植高級(jí)人工智能在DL中添加算子一般地，在描述邏輯中添加不同的算子，則得到不6描述邏輯中的推理1)

一致性（協(xié)調(diào)性consistency）2)可滿足性(satisfiability)3)包含檢測(cè)（subsumption）4)實(shí)例檢測(cè)(instancechecking)5)Tableaux算法6）可判定性7）計(jì)算復(fù)雜性12/10/202223史忠植高級(jí)人工智能6描述邏輯中的推理1)一致性（協(xié)調(diào)性consistenc1)一致性檢測(cè)(Consistency)◆知識(shí)庫<T,A>是協(xié)調(diào)的嗎？ 即檢測(cè)是否有<T,A>的模型(解釋)I？◆C關(guān)于TboxT是協(xié)調(diào)的嗎？

即檢測(cè)是否有T的模型I使得C

≠

？12/10/202224史忠植高級(jí)人工智能1)一致性檢測(cè)(Consistency)◆知識(shí)庫<T,A>2)概念可滿足性(Satisfiablity)

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

檢驗(yàn)一個(gè)概念的可滿足性，實(shí)際上就是看是否有解釋使得這個(gè)概念成立。例如：概念Male?

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

12/10/202225史忠植高級(jí)人工智能2)概念可滿足性(Satisfiablity)對(duì)一◆在知識(shí)庫中檢測(cè)： C?

D？ 即檢測(cè)CI

?

DI是否在所有的解釋中成立？3)概念包含(Subsumption)例如： bird?animal computer?equipment◆在Tbox中檢測(cè)： C?

D？ 即檢測(cè)CI

?

DI是否在TboxT的所有解釋中成立？12/10/202226史忠植高級(jí)人工智能◆在知識(shí)庫中檢測(cè)：3)概念包含(Subsumption)例C?

Diff

C?

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

Diff

C?

?D關(guān)于T是不可滿足的。C關(guān)于T是一致的iffC?T

A?

?A包含與可滿足性的關(guān)系?DDCC?

?D＝

12/10/202227史忠植高級(jí)人工智能C?DiffC??D是不可滿足的。包含與可滿足4）實(shí)例檢測(cè)(Instancechecking)概念的實(shí)例： Student(John)，或者表示為John:Student關(guān)系的實(shí)例： Father(John,Mary) 實(shí)例檢索：檢索屬于某個(gè)概念的所有實(shí)例的集合12/10/202228史忠植高級(jí)人工智能4）實(shí)例檢測(cè)(Instancechecking)概念的實(shí)例5）可滿足性檢測(cè)算法——Tableaux算法1)

?規(guī)則:S→?{

x:C1,x:C2}?S，若x:C1?

C2在S中，且x:C1和x:C2不在S中同時(shí)出現(xiàn)。2)?規(guī)則:S→?

{x:D}?S，若x:C1?C2在S中，x:C1和x:C2都不在S中，且D=C1或者D=C2。3)?規(guī)則:S→?

{xP1y,…,xPky,y:C}?S，若x:?R.C在S中，R=P1?…?Pk，沒有z使得xRz在S中成立，且z:C在S中，y為一個(gè)新變量。4)?規(guī)則:S→?{y:C}?S，若x:?R.C在S中，xRy在S中成立，且y:C不在S中。

12/10/202229史忠植高級(jí)人工智能5）可滿足性檢測(cè)算法——Tableaux算法1)?規(guī)則:1例子：檢測(cè)概念的可滿足性：(?has-child.Male)?(?has-child.?Male)，其檢測(cè)過程為：((?has-child.Male)?(?has-child.?Male))(x)(?has-child.Male)(x) ?規(guī)則(?has-child.?Male)(x) ?規(guī)則has-child(x,y) ?規(guī)則?Male(y) ?規(guī)則Male(y) ?規(guī)則

矛盾所以這個(gè)概念是不可滿足的。12/10/202230史忠植高級(jí)人工智能例子：檢測(cè)概念的可滿足性：12/8/202230史忠植高6）可判定性描述邏輯中的可滿足性問題是可判定的。其它推理問題基本上可以歸結(jié)為可滿足性問題。7）計(jì)算復(fù)雜性描述邏輯中的推理問題其計(jì)算復(fù)雜性一般是多項(xiàng)式時(shí)間的。但通常由于構(gòu)造的不同，其復(fù)雜性也有一定的差異。12/10/202231史忠植高級(jí)人工智能6）可判定性描述邏輯中的可滿足性問題是可判定的。7）計(jì)算復(fù)雜SemanticWebArchitecture12/10/202232史忠植高級(jí)人工智能SemanticWebArchitecture12/8我們的工作◆帶缺省的描述邏輯定義

一個(gè)缺省規(guī)則是形如這樣的表達(dá)式，其中C、D、E為概念名，x是一個(gè)變?cè)?。C(x)稱為前提條件，D(x)稱為檢驗(yàn)條件(缺省)，E(x)稱為缺省的結(jié)論。定義1.2一個(gè)知識(shí)庫是一個(gè)三元組<T,A,D>，其中T為Tbox，A為Abox，D為缺省規(guī)則集。12/10/202233史忠植高級(jí)人工智能我們的工作◆帶缺省的描述邏輯12/8/202233史忠植◆動(dòng)態(tài)描述邏輯描述邏輯最開始只是用來表示靜態(tài)知識(shí)的。為了考慮在時(shí)間上的變化，或者在一定動(dòng)作下的變化，以及保持其語言的相對(duì)簡單性，很自然地我們需要通過相應(yīng)的模態(tài)算子來擴(kuò)展它，以保留其命題模態(tài)狀態(tài)。提出動(dòng)態(tài)描述邏輯，用來描述主體中的動(dòng)態(tài)知識(shí)以及推理。描述邏輯動(dòng)態(tài)邏輯＋主體面向主體的動(dòng)態(tài)描述邏輯12/10/202234史忠植高級(jí)人工智能◆動(dòng)態(tài)描述邏輯描述邏輯最開始只是用來表示靜態(tài)知識(shí)的。以客觀世界的形式化建模為研究內(nèi)容，提出一種統(tǒng)一的形式化框架，同時(shí)從靜態(tài)和動(dòng)態(tài)兩個(gè)方面來刻畫世界的模型。為動(dòng)態(tài)領(lǐng)域的建模提供一種有效的形式化理論工具；將世界中的概念、關(guān)系和個(gè)體，公理、事實(shí)和動(dòng)作有機(jī)地整合在一起，形成統(tǒng)一的關(guān)聯(lián)和運(yùn)作機(jī)制，使動(dòng)作與公理和事實(shí)相互作用，統(tǒng)一表示并進(jìn)行推理；對(duì)概念、公式和動(dòng)作都給出了統(tǒng)一的、合適的語法和語義；主體與本體的結(jié)合

動(dòng)態(tài)描述邏輯DDL12/10/202235史忠植高級(jí)人工智能動(dòng)態(tài)描述邏輯DDL12/8/202235史忠植高級(jí)人工動(dòng)態(tài)描述邏輯DDLDDL：語義環(huán)境中對(duì)服務(wù)過程方面的建模和推理服務(wù)改變環(huán)境的狀態(tài)：前提條件和執(zhí)行結(jié)果，Action服務(wù)描述：基于WorldModel，e.g.,描述服務(wù)的前提和結(jié)果的詞匯來自WorldModelTBox描述WorldModel的結(jié)構(gòu)所有狀態(tài)的描述以數(shù)據(jù)庫或文本的形式分散在Web中用戶或Agent通過查詢的方式獲得狀態(tài)的信息，存放于各自的ABox中DL與Action的交互體現(xiàn)在：Action采用TBox中的詞匯描述前提和結(jié)果Action的執(zhí)行導(dǎo)致ABox的變化DDL＝DL＋Action12/10/202236史忠植高級(jí)人工智能動(dòng)態(tài)描述邏輯DDLDDL：語義環(huán)境中對(duì)服務(wù)過程方面的建模和推Anactiondescriptionistheformof

where

(1)Aistheactionname.(2)x1,…,xn

areindividualvariables,whichdenotetheobjectstheactionoperateon.(3)PA

isthesetofpreconditions,whichmustbesatisfiedbeforetheactionisexecuted.(4)EA

isthesetofresults,whichdenotetheeffectsoftheaction.

DynamicDescriptionLogic12/10/202237史忠植高級(jí)人工智能Anactiondescriptionisthef描述邏輯與語義Web有何區(qū)別與聯(lián)系？思考描述邏輯與Prolog有何區(qū)別與聯(lián)系？描述邏輯可以在哪些方面進(jìn)行擴(kuò)展與完善？12/10/202238史忠植高級(jí)人工智能描述邏輯與語義Web有何區(qū)別與聯(lián)系？思考描述邏輯與Prol參考文獻(xiàn)12/10/202239史忠植高級(jí)人工智能參考文獻(xiàn)12/8/202239史忠植高級(jí)人工智能謝謝！12/10/202240史忠植高級(jí)人工智能謝謝！12/8/202240史忠植高級(jí)人工智能第二章人工智能邏輯

第二部分史忠植中國科學(xué)院計(jì)算技術(shù)研究所高級(jí)人工智能12/10/202241史忠植高級(jí)人工智能第二章人工智能邏輯

第二部分史忠植高級(jí)人工智能12/8/描述邏輯

DescriptionLogics12/10/202242史忠植高級(jí)人工智能描述邏輯

DescriptionLogics12/主要內(nèi)容◆

什么是描述邏輯？◆為什么用描述邏輯？◆描述邏輯的研究進(jìn)展◆描述邏輯的體系結(jié)構(gòu)◆描述邏輯的構(gòu)造算子◆描述邏輯的推理問題◆我們的工作12/10/202243史忠植高級(jí)人工智能主要內(nèi)容◆什么是描述邏輯？12/8/20223史忠植高1什么是描述邏輯(DL)？ 一種基于對(duì)象的知識(shí)表示的形式化，也叫概念表示語言或術(shù)語邏輯。建立在概念和關(guān)系(Role)之上

－概念解釋為對(duì)象的集合 －關(guān)系解釋為對(duì)象之間的二元關(guān)系源于語義網(wǎng)絡(luò)和KL-ONE是一階邏輯FOL的一個(gè)可判定的子集具有合適定義的語義(基于邏輯)12/10/202244史忠植高級(jí)人工智能1什么是描述邏輯(DL)？ 一種基于對(duì)象的知識(shí)表示的形式化特點(diǎn)◆是以往表示工具的邏輯重構(gòu)和統(tǒng)一形式化 －

框架系統(tǒng)(Frame-basedsystems) －

語義網(wǎng)絡(luò)(SemanticNetworks) －

面向?qū)ο蟊硎?OOrepresentation) －

語義數(shù)據(jù)模型(Semanticdatamodels) －

類型系統(tǒng)(Typesystems) －

特征邏輯(FeatureLogics)◆

具有很強(qiáng)的表達(dá)能力◆是可判定的，總能保證推理算法終止12/10/202245史忠植高級(jí)人工智能特點(diǎn)◆是以往表示工具的邏輯重構(gòu)和統(tǒng)一形式化12/8/2022描述邏輯的應(yīng)用

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

Schmidt-Schaub和Smolka首先建立了基于描述邏輯ALC的Tableau算法，該算法能在多項(xiàng)式時(shí)間內(nèi)判斷描述邏輯ALC概念的可滿足性問題。12/10/202249史忠植高級(jí)人工智能3描述邏輯的研究進(jìn)展12/8/20229史忠植高級(jí)人工◆描述邏輯的擴(kuò)展研究

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

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

另外如時(shí)序擴(kuò)展(Artale,Wolter)、模糊擴(kuò)展(Straccia)等。12/10/202250史忠植高級(jí)人工智能◆描述邏輯的擴(kuò)展研究12/8/202210史忠植高級(jí)人◆描述邏輯的應(yīng)用研究描述邏輯在許多領(lǐng)域中被作為知識(shí)表示的工具，如 信息系統(tǒng)（Catarci,1993） 數(shù)據(jù)庫（Borgida,1995;Bergamaschi1992;Sheth,1993） 軟件工程(Devambu,1991) 網(wǎng)絡(luò)智能訪問（Levy，1996；Blanco，1994） 規(guī)劃（Seida,1992）等 Horrocks對(duì)表達(dá)能力較強(qiáng)的描述邏輯進(jìn)行了研究，并建立了一些邏輯框架和系統(tǒng)，如FaCT，SHIQ等。他和DieterFensel等人將描述邏輯、語義網(wǎng)和DAML結(jié)合起來，提出了DAML+OIL，其中以描述邏輯作為核心的表示和推理基礎(chǔ)。并在XML及其RDF上面進(jìn)行了擴(kuò)展，用描述邏輯來研究語義網(wǎng)絡(luò)和本體論。12/10/202251史忠植高級(jí)人工智能◆描述邏輯的應(yīng)用研究12/8/202211史忠植高級(jí)人4描述邏輯的體系結(jié)構(gòu)一個(gè)描述邏輯系統(tǒng)包含四個(gè)基本組成部分：1）表示概念和關(guān)系（Role）的構(gòu)造集2）Tbox——關(guān)于概念術(shù)語的斷言3）Abox——關(guān)于個(gè)體的斷言4）Tbox和Abox上的推理機(jī)制。

12/10/202252史忠植高級(jí)人工智能4描述邏輯的體系結(jié)構(gòu)一個(gè)描述邏輯系統(tǒng)包含四個(gè)基本組成部分：◆概念——解釋為一個(gè)領(lǐng)域的子集

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

關(guān)系(Roles)——屬性(二元謂詞，關(guān)系)例子：朋友，愛人，{<x,y>|Friend(x,y)}，{<x,y>|Loves(x,y)}1）DL的基本元素——概念和關(guān)系12/10/202253史忠植高級(jí)人工智能◆概念——解釋為一個(gè)領(lǐng)域的子集◆關(guān)系(Roles)知識(shí)庫TBox(模式)Man?Human?MaleHappy-father?Human?

?Has-child.Female?

…Abox(數(shù)據(jù))John:Happy-father<John,Mary>:Has-child推理系統(tǒng)接口12/10/202254史忠植高級(jí)人工智能TBox(模式)Abox(數(shù)據(jù))推理系統(tǒng)接口12/8/2022）TBox語言 是描述領(lǐng)域結(jié)構(gòu)的公理的集合定義:引入概念的名稱A?

C,A

?

CFather?

Man?

?

has-child.HumanHuman?

Animal?

Biped包含：聲明包含關(guān)系的公理C

?

D

(C?

D

C

?

D，D

?

C)?

has-degree.Masters?

?

has-degree.Bachelors一個(gè)解釋I滿足：C?

D

iffCI

=DI C?

D

iffCI

?

DI一個(gè)解釋I滿足TBoxT

iff它滿足T中的每個(gè)公理(I?T)12/10/202255史忠植高級(jí)人工智能2）TBox語言定義:引入概念的名稱12/8/20221◆概念——表示實(shí)體(一元謂詞，類)例子：學(xué)生，已婚的{x|Student(x)}，{x|Married(x)} Bird

?

Animal,Man?Human◆

關(guān)系(Roles)——屬性(二元謂詞，關(guān)系)例子：朋友，愛人{(lán)<x,y>|Friend(x,y)}，{<x,y>|Loves(x,y)}TBox實(shí)例12/10/202256史忠植高級(jí)人工智能◆概念——表示實(shí)體(一元謂詞，類)◆關(guān)系(Roles)◆概念斷言——表示一個(gè)對(duì)象是否屬于某個(gè)概念 a:C例如：Tom是個(gè)學(xué)生，表示為

Tom

:Student 或者 Student(Tom)

John

:Man?

?

has-child.Female◆

關(guān)系斷言——表示兩個(gè)對(duì)象是否滿足一定的關(guān)系 <a,b>:R例如：John有個(gè)孩子叫Mary

<John,

Mary>

:has-child3）ABox語言（斷言部分） 是描述具體情形的公理的集合12/10/202257史忠植高級(jí)人工智能◆概念斷言——表示一個(gè)對(duì)象是否屬于某個(gè)概念◆關(guān)系斷言一個(gè)解釋I滿足：a:

C

iffaI

∈

CI<a,b>:R

iff<aI,bI>

∈RI一個(gè)解釋I滿足ABoxA

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

>

iff它滿足T和A記為：I?12/10/202258史忠植高級(jí)人工智能一個(gè)解釋I滿足：a:CiffaI∈CI14）語法和語義構(gòu)造算子語法語義例子原子概念A(yù)AI?△IHuman原子關(guān)系RRI?△I△Ihas-child對(duì)概念C,D和關(guān)系(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.Doctor12/10/202259史忠植高級(jí)人工智能4）語法和語義構(gòu)造算子語法語義例子原子概念A(yù)AI?△I一般地，描述邏輯依據(jù)提供的構(gòu)造算子，在簡單的概念和關(guān)系上構(gòu)造出復(fù)雜的概念和關(guān)系。通常DL至少包含以下算子： ◆合取(?)，吸取(?)，非(?) ◆量詞約束：存在量詞(?)，全稱量詞(?)最基本的DL稱之為ALC例如，ALC中概念Happy-father定義為： Man?

?

has-child.Male

?

?

has-child.Female

?

?has-child.(Doctor?

Lawyer)5DL中的構(gòu)造算子12/10/202260史忠植高級(jí)人工智能一般地，描述邏輯依據(jù)提供的構(gòu)造算子，在簡單的5DL中的構(gòu)造構(gòu)造算子語法語義例子數(shù)量約束≥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另外，有兩個(gè)類似于FOL中的全集(true)和空集(false)的算子12/10/202261史忠植高級(jí)人工智能構(gòu)造算子語法語義例子數(shù)量約束≥nR.C{x||{y在DL中添加算子一般地，在描述邏輯中添加不同的算子，則得到不同表達(dá)能力的描述邏輯，其復(fù)雜性問題也不盡相同。例如，在ALC的基礎(chǔ)上添加逆(-)算子，則構(gòu)成ALCI若再加上數(shù)量約束算子(≥n,≤n)，則構(gòu)成ALCIQ。若在描述邏輯中添加時(shí)序算子，則構(gòu)成為時(shí)序描述邏輯(TemporalDescriptionLogic)，例如，可以添加： Until算子U：C

U

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

，○等。12/10/202262史忠植高級(jí)人工智能在DL中添加算子一般地，在描述邏輯中添加不同的算子，則得到不6描述邏輯中的推理1)

一致性（協(xié)調(diào)性consistency）2)可滿足性(satisfiability)3)包含檢測(cè)（subsumption）4)實(shí)例檢測(cè)(instancechecking)5)Tableaux算法6）可判定性7）計(jì)算復(fù)雜性12/10/202263史忠植高級(jí)人工智能6描述邏輯中的推理1)一致性（協(xié)調(diào)性consistenc1)一致性檢測(cè)(Consistency)◆知識(shí)庫<T,A>是協(xié)調(diào)的嗎？ 即檢測(cè)是否有<T,A>的模型(解釋)I？◆C關(guān)于TboxT是協(xié)調(diào)的嗎？

即檢測(cè)是否有T的模型I使得C

≠

？12/10/202264史忠植高級(jí)人工智能1)一致性檢測(cè)(Consistency)◆知識(shí)庫<T,A>2)概念可滿足性(Satisfiablity)

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

檢驗(yàn)一個(gè)概念的可滿足性，實(shí)際上就是看是否有解釋使得這個(gè)概念成立。例如：概念Male?

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

12/10/202265史忠植高級(jí)人工智能2)概念可滿足性(Satisfiablity)對(duì)一◆在知識(shí)庫中檢測(cè)： C?

D？ 即檢測(cè)CI

?

DI是否在所有的解釋中成立？3)概念包含(Subsumption)例如： bird?animal computer?equipment◆在Tbox中檢測(cè)： C?

D？ 即檢測(cè)CI

?

DI是否在TboxT的所有解釋中成立？12/10/202266史忠植高級(jí)人工智能◆在知識(shí)庫中檢測(cè)：3)概念包含(Subsumption)例C?

Diff

C?

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

Diff

C?

?D關(guān)于T是不可滿足的。C關(guān)于T是一致的iffC?T

A?

?A包含與可滿足性的關(guān)系?DDCC?

?D＝

12/10/202267史忠植高級(jí)人工智能C?DiffC??D是不可滿足的。包含與可滿足4）實(shí)例檢測(cè)(Instancechecking)概念的實(shí)例： Student(John)，或者表示為John:Student關(guān)系的實(shí)例： Father(John,Mary) 實(shí)例檢索：檢索屬于某個(gè)概念的所有實(shí)例的集合12/10/202268史忠植高級(jí)人工智能4）實(shí)例檢測(cè)(Instancechecking)概念的實(shí)例5）可滿足性檢測(cè)算法——Tableaux算法1)

?規(guī)則:S→?{

x:C1,x:C2}?S，若x:C1?

C2在S中，且x:C1和x:C2不在S中同時(shí)出現(xiàn)。2)?規(guī)則:S→?

{x:D}?S，若x:C1?C2在S中，x:C1和x:C2都不在S中，且D=C1或者D=C2。3)?規(guī)則:S→?

{xP1y,…,xPky,y:C}?S，若x:?R.C在S中，R=P1?…?Pk，沒有z使得xRz在S中成立，且z:C在S中，y為一個(gè)新變量。4)?規(guī)則:S→?{y:C}?S，若x:?R.C在S中，xRy在S中成立，且y:C不在S中。

12/10/202269史忠植高級(jí)人工智能5）可滿足性檢測(cè)算法——Tableaux算法1)?規(guī)則:1例子：檢測(cè)概念的可滿足性：(?has-child.Male)?(?has-child.?Male)，其檢測(cè)過程為：((?has-child.Male)?(?has-child.?Male))(x)(?has-child.Male)(x) ?規(guī)則(?has-child.?Male)(x) ?規(guī)則has-child(x,y) ?規(guī)則?Male(y) ?規(guī)則Male(y) ?規(guī)則