数据与知识工程 4 DL(2)

教师：常亮E-mail:[e-mail]办公室电话:2291071手机:[phone]办公室：7212数据与知识工程欢迎参加描述逻辑的推理问题(1)概念的可满足性描述逻辑的推理问题(2)知识库的可满足性/知识库的一致性/ABox相对于TBox的一致性描述逻辑的推理问题(3)公式的可满足性描述逻辑ALC的判定算法预处理：转化为negationnormalform(NNF)判断概念可满足性的步骤：(令D为待判定的概念)(1)构造初始树T0，仅由单结点x0组成，并且L(x0)={D}；(2)应用Tableau扩展规则对T0进行扩展；……描述逻辑ALC的判定算法ALC的Tableau扩展规则：描述逻辑ALC的判定算法判断概念可满足性的步骤：(令D为待判定的概念)(1)构造初始树T0，仅由单结点x0组成，并且L(x0)={D}；(2)应用Tableau扩展规则对T0进行扩展；如果存在某种扩展方式得到一棵饱和的并且无冲突的树，则返回“概念D相对于TBoxT是可满足的”，否则返回“概念D相对于TBoxT不可满足”。冲突：饱和/完全的树：不能再应用tableau扩展规则进行扩展。描述逻辑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描述逻辑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}练习Usetableaualgorithmtodecidewhetherthefollowingconceptissatisfiableornot.((R.A)⊓(R.B))⊓R.(A⊓B).练习GiventhefollowingTBox,usetableaualgorithmtodecidewhethertheconceptGrandmotherissatisfiableornot.对知识库一致性的判定GivenaTBoxTandanABoxA,usetableaualgorithmtodecidewhetherAisconsistentw.r.t.T.判断知识库一致性的步骤：(1)根据ABoxA构造初始图T0。A中出现的每个个体名对应于图中一个结点；每个结点上标记其对应的个体名所需要满足的概念；结点之间的边对应于个体名之间所需要满足的角色。(2)应用Tableau扩展规则对T0进行扩展；如果存在某种扩展方式得到一棵饱和的并且无冲突的树，则返回“知识库是一致的”，否则返回“知识库是不一致的”。例子Usetableaualgorithmtodecidewhetherthefollowingknowledgebaseissatisfiableornot.练习Usetableaualgorithmtodecidewhetherthefollowingknowledgebaseissatisfiableornot.对公式可满足性的判定GivenaTBox,usetableaualgorithmtodecidewhetheraformulaissatisfiableornot.判断公式可满足性的步骤：(令φ为待判定的公式)(1)将公式φ转化为析取范式φ1…φn；(2)将每个析取项φi看作一个ABox，应用Tableau方法判断其相对于TBox是否为一致的；如果其中至少存在一个ABoxAi是相对于TBoxT一致的，则返回“公式φ相对于TBoxT是一致的”，否则返回“公式φ相对于TBoxT不一致”。练习GiventhefollowingTBox,usetableaualgorithmtodecidewhethertheformulaissatisfiableornot.描述逻辑ALC(判定算法的性质)可终止性：可靠性：完备性：复杂度：PSPACE-完全算法复杂度理论几类多项式时间复杂度之间的关系O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)几类指数时间复杂度之间的关系O(2n)O(3n)…O(n!)O(nn)PNPPSPACEEXPTIMENEXPTIMEEXPSPACE2EXPTIMEN2EXPTIME…PEXPTIMENPNEXPTIMEPSPACEEXPSPACEEXPTIME2EXPTIMENEXPTIMEN2EXPTIME描述逻辑的推理问题(4)判断概念之间的包含关系判断概念之间的不相交关系判断概念之间的等价关系都可以转化为概念的可满足性问题进而可以转化为公式的可满足性问题描述逻辑的推理问题(5)AxiomEntailmentWhetheraknowledgebaseKBentailsaDLaxiomα.WhetherKB⊨α?KB⊨αiffConj(KB)αisunsatisfiable练习Giventhefollowingknowledgebase,usetableaualgorithmtodecidewhetherKB⊨Mother(Alice).描述逻辑的推理问题(6)InstanceRetrievalGivenaknowledgebaseKBandaconceptC,findallindividualnamesa∈NIforwhichaI∈CIforeverymodelIofKB.ItisobviousthatanindividualnameawillbedeliveredaspartoftheanswerofaninstanceretrievalwithrespecttoaconceptCpreciselyifKB|=C(a).Therefore,instanceretrievalcanbeperformedbysuccessivelycheckingwhethertheconsideredknowledgebaseentailsC(a)foreveryindividualnamea.描述逻辑的推理问题(7)ClassificationGivenaknowledgebaseKB,theconceptnamesoccurringthereincanbeputintoahierarchyaccordingtotheirsub-sumptionrelationships.描述逻辑的推理问题(8)其它推理问题：ConjunctiveQueryAnsweringGivenaknowledgebaseKBandasetofassertions{C1(x1),…,Cn(xn),R1(x1,1,x1,2),…,Rm(xm,1,xm,2)},findalltuples(p1,p2,…,p2)suchthat….AbductionExplanationModuleExtractionConservativeExtensions……教材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,HarmelenF.著,陈小平等译.语义网基础教程(第1版).机械工业出版社,2008.3.BellJ.L.,MachoverM.ACourseinMathematicalLogic.North-HollandPublishingCompany,1977.教材及参考书Thanks！