數(shù)據(jù)與知識工程4DL

數(shù)據(jù)與知識工程4DL2024/3/26數(shù)據(jù)與知識工程4DL描述邏輯的推理問題(1)概念的可滿足性數(shù)據(jù)與知識工程4DL描述邏輯的推理問題(2)知識庫的可滿足性/知識庫的一致性/ABox相對于TBox的一致性數(shù)據(jù)與知識工程4DL描述邏輯的推理問題(3)公式的可滿足性數(shù)據(jù)與知識工程4DL描述邏輯ALC的判定算法預(yù)處理：轉(zhuǎn)化為negationnormalform(NNF)判斷概念可滿足性的步驟：(令D為待判定的概念)(1)構(gòu)造初始樹T0，僅由單結(jié)點x0組成，并且L(x0)={D}；(2)應(yīng)用Tableau擴(kuò)展規(guī)則對T0進(jìn)行擴(kuò)展；……數(shù)據(jù)與知識工程4DL描述邏輯ALC的判定算法ALC的Tableau擴(kuò)展規(guī)則：數(shù)據(jù)與知識工程4DL描述邏輯ALC的判定算法判斷概念可滿足性的步驟：(令D為待判定的概念)(1)構(gòu)造初始樹T0，僅由單結(jié)點x0組成，并且L(x0)={D}；(2)應(yīng)用Tableau擴(kuò)展規(guī)則對T0進(jìn)行擴(kuò)展；如果存在某種擴(kuò)展方式得到一棵飽和的并且無沖突的樹，則返回“概念D相對于TBoxT是可滿足的”，否則返回“概念D相對于TBoxT不可滿足”。沖突：飽和/完全的樹：不能再應(yīng)用tableau擴(kuò)展規(guī)則進(jìn)行擴(kuò)展。數(shù)據(jù)與知識工程4DL描述邏輯ALC的判定算法{Parent}x{Parent,Father,Mother,Man}{Parent,Father,Mother}{Parent,Father,Mother,Man,Woman}{Parent,Father,Mother,Man,Woman,Person,Woman}y{Person}hasChildz{Person}hasChild數(shù)據(jù)與知識工程4DL描述邏輯ALC的判定算法{Parent}x{Parent,Father,Man}{Parent,Father}{Parent,Father,Man,Person,

Woman}{Parent,Father,Man,Person,Woman,Person}y{Person}hasChild{Parent,Father,Man,Person,Woman,Female}數(shù)據(jù)與知識工程4DL練習(xí)Usetableaualgorithmtodecidewhetherthefollowingconceptissatisfiableornot.

((

R.A)?(

R.B))?

R.(A?B).數(shù)據(jù)與知識工程4DL練習(xí)GiventhefollowingTBox,usetableaualgorithmtodecidewhethertheconceptGrandmotherissatisfiableornot.

數(shù)據(jù)與知識工程4DL對知識庫一致性的判定GivenaTBoxTandanABoxA,usetableaualgorithmtodecidewhetherAisconsistentw.r.t.T.判斷知識庫一致性的步驟：(1)根據(jù)ABoxA構(gòu)造初始圖T0。A中出現(xiàn)的每個個體名對應(yīng)于圖中一個結(jié)點；每個結(jié)點上標(biāo)記其對應(yīng)的個體名所需要滿足的概念；結(jié)點之間的邊對應(yīng)于個體名之間所需要滿足的角色。(2)應(yīng)用Tableau擴(kuò)展規(guī)則對T0進(jìn)行擴(kuò)展；如果存在某種擴(kuò)展方式得到一棵飽和的并且無沖突的樹，則返回“知識庫是一致的”，否則返回“知識庫是不一致的”。數(shù)據(jù)與知識工程4DL例子Usetableaualgorithmtodecidewhetherthefollowingknowledgebaseissatisfiableornot.

數(shù)據(jù)與知識工程4DL練習(xí)Usetableaualgorithmtodecidewhetherthefollowingknowledgebaseissatisfiableornot.

數(shù)據(jù)與知識工程4DL對公式可滿足性的判定GivenaTBox,usetableaualgorithmtodecidewhetheraformulaissatisfiableornot.判斷公式可滿足性的步驟：(令φ為待判定的公式)(1)將公式φ轉(zhuǎn)化為析取范式φ1…φn；(2)將每個析取項φi看作一個ABox，應(yīng)用Tableau方法判斷其相對于TBox是否為一致的；如果其中至少存在一個ABoxAi是相對于TBoxT一致的，則返回“公式φ相對于TBoxT是一致的”，否則返回“公式φ相對于TBoxT不一致”。數(shù)據(jù)與知識工程4DL練習(xí)GiventhefollowingTBox,usetableaualgorithmtodecidewhethertheformulaissatisfiableornot.

數(shù)據(jù)與知識工程4DL描述邏輯ALC

(判定算法的性質(zhì))可終止性：可靠性：完備性：復(fù)雜度：PSPACE-完全數(shù)據(jù)與知識工程4DL算法復(fù)雜度理論幾類多項式時間復(fù)雜度之間的關(guān)系O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)幾類指數(shù)時間復(fù)雜度之間的關(guān)系O(2n)<O(3n)<…<O(n!)<O(nn)

P

NP

PSPACE

EXPTIME

NEXPTIME

EXPSPACE

2EXPTIME

N2EXPTIME…PEXPTIMENPNEXPTIMEPSPACEEXPSPACEEXPTIME2EXPTIMENEXPTIMEN2EXPTIME數(shù)據(jù)與知識工程4DL描述邏輯的推理問題(4)判斷概念之間的包含關(guān)系判斷概念之間的不相交關(guān)系判斷概念之間的等價關(guān)系都可以轉(zhuǎn)化為概念的可滿足性問題進(jìn)而可以轉(zhuǎn)化為公式的可滿足性問題數(shù)據(jù)與知識工程4DL描述邏輯的推理問題(5)AxiomEntailmentWhetheraknowledgebaseKBentailsaDLaxiomα.

WhetherKB?α?KB?αiffConj(KB)

αisunsatisfiable數(shù)據(jù)與知識工程4DL練習(xí)Giventhefollowingknowledgebase,usetableaualgorithmtodecidewhetherKB?Mother(Alice).

數(shù)據(jù)與知識工程4DL描述邏輯的推理問題(6)InstanceRetrievalGivenaknowledgebaseKBandaconceptC,findallindividualnamesa∈NIforwhichaI∈CIforeverymodelIofKB.ItisobviousthatanindividualnameawillbedeliveredaspartoftheanswerofaninstanceretrievalwithrespecttoaconceptCpreciselyifKB|=C(a).Therefore,instanceretrievalcanbeperformedbysuccessivelycheckingwhethertheconsideredknowledgebaseentailsC(a)foreveryindividualnamea.數(shù)據(jù)與知識工程4DL描述邏輯的推理問題(7)ClassificationGivenaknowledgebaseKB,theconceptnamesoccurringthereincanbeputintoahierarchyaccordingtotheirsub-sumptionrelationships.

數(shù)據(jù)與知識工程4DL描述邏輯的推理問題(8)其它推理問題：ConjunctiveQueryAnsweringGivenaknowledgebaseKBandasetofassertions{C1(x1),…,Cn(xn),R1(x1,1,x1,2),…,Rm(xm,1,xm,2)},findalltuples(p1,p2,…,p2)suchthat….AbductionExplanationModuleExtractionConservativeExtensions……數(shù)據(jù)與知識工程4DL

教材BrachmanR,LevesqueH.KnowledgeRepresentationandReasoning.MorganKaufmannPress,2004.AntoniouG,HarmelenF.ASemanticWebPrimer.SecondEdition.

Cambridge,Mass.:MITPress,2008.參考書1.BaaderF,CalvaneseD,McGuinnessD,NardiD,andPatel-SchneiderP.F..TheDescriptionLogicHandbook:Theory,ImplementationandApplications.

CambridgeUniversityPress,2003.2.AntoniouG,H