Logic-based knowledge representation

Logic-basedKnowledgeRepresentation?FranzBaaderTheoreticalComputerScience,RWTHAachen,52074Aachen,[e-mail]requirementsthataknowledgerepresentationlanguagemustsatisfy,weintroduceDescriptionLogics,ModalLogics,andNonmonotonicLogicsasformalismsforrepresentingterminologicalknowledge,time-dependentorsubjectiveknowledge,andincompleteknowledgerespectively.Attheendofeachsection,webrieycommentontheconnectiontoLogicProgramming.1IntroductionThissectionisconcernedwiththequestionunderwhichconditionsonemayrightfullyclaimtohaverepresentedknowledgeaboutanapplicationdomain,andnotjuststoreddataoccurringinthisdomain.1IntheearlydaysofArticialIntelligenceandKnowledgeRepresentation,therewasaheateddiscussiononwhetherlogiccanatallbeusedasaformalismforKnowledgeRepresentation(seee.g.[135,91,92]).Oneaspectoftherequirementsonknowledgerepresentationformalismsthatcanbederivedfromtheconsiderationsinthissectionisverywellsatisedbylogicalformalisms.Weshallsee,however,thatsomeotheraspectsarenottreatedsatisfactorily,atleastnotbyclassicalrst-orderpredicatelogic.Themainpurposeofthisarticleistodemonstratethatthesedecienciescanbeovercomewiththehelpofotherlogic-basedformalisms,namelyDescriptionLogics,ModalLogics,andNonmonotonicLogics.Morerecently,ithasbeenargued(seee.g.[110,23])thatLogicProgrammingcanserveasaconvenientanduniversalformalismforKnowledgeRepresentation.However,asindicatedbytheirname,LogicProgramminglanguagesareprogramminglanguages,andthusnotnecessarilyappropriateasrepresentationlanguages.Inanut-shell(andsomewhatexaggerated),thedierencebetweenknowledge-basedprogramming(whichprocessesknowledge)andclassicalprogramming(whichprocessesdata)canbeformulatedasfollows.Inclassicalprogramming,onedesignsspecializedprogramsthataretailoredtoaspecicapplicationprob-lem.Theknowledgeabouttheproblemdescriptionandtheapplicationdomainisimplicitlyrepresentedinthestructureoftheprogram,andmustthusbeacquiredbytheprogrammer.Inknowledge-basedprogramming,theknowledgeaboutthe?Thisisanextendedandupdatedversionofanarticlethathasappeared(inGerman)inthejournalKI,3/96:8-16,1996.1Thedivisionbetweenknowledgeanddatais,ofcourse,notstrict,andthisarticlewillnotgiveadenitiveanswertotheproblemofdistinguishingbetweenboth.applicationdomainisrepresentedexplicitly(inanappropriaterepresentationformalism);ideally,theprocessingcanbedonewiththehelpofgeneral(i.e.,application-independent)problemsolvingmethods.Thus,theknowledgecanbeacquiredandrepresentedbyanapplicationdomainexpert,whoneednotbewell-acquaintedwithdetailsoftheimplementation.Asasimpleexample,letuscon-siderthetaskofndingoutwhethertwonodesinadirectedgraph(whichmayrepresentthehierarchicalorganizationofacompany)areconnected(whetheroneemployeeisthebossofanotherone).Arstsolution,whichisveryfarawayfrombeingknowledge-based,mightbeaprogramthatencodesthestructureofthespecicgraphinitscontrolstructure.Asecond,morereasonable,solutionmightexplicitlyrepresentthegraphinanappropriatedatastructure(whichlistthenodesthataredirectlyconnected),andthencodethemeaningof\con-nectedinaprogramthatisindependentofthespecicgraph.Thisprogrammustbeabletocomputetheconnectednodesfromthegiveninformationaboutthedirectlyconnectednodes.Finally,anevenmoreknowledge-basedsolutioncouldbeoneinwhichtheknowledgeaboutthemeaningof\connectedisalsorepresentedinanexplicitway,forexample,bythefollowingHornclauses:directly-connected(x;y)!connected(x;y);directly-connected(x;z)^connected(z;y)!connected(x;y):Ageneralproblemsolvingcomponent,whichisabletohandlesuchclauses(e.g.,theinterpreterofaLogicProgramminglanguage),couldnowusetheseformulaetogetherwiththeexplicitinformationonthedirectlyconnectednodestoinfertheconnectednodes.Aknowledgerepresentation(KR)formalismshouldallowforthesymbolicrepresentationofalltheknowledgerelevantinagivenapplicationdomain.Fromwhatwehavesaidsofarabouttheuseofknowledgeinknowledge-basedpro-gramming,wecanderivetworequirementsthatsuchaformalismmustsatisfy.Ontheonehand,itmustbeequippedwithadeclarativesemantics,thatis,themeaningoftheentriesinaknowledgebase(KB)mustbedenedindependentlyoftheprogramsthatoperateontheKB(nopurelyproceduralsemantics).Oth-erwise,theknowledgecannotbeacquiredbyadomainexpertwithoutdetailedknowledgeoftheimplementationoftheseprograms.Usually,suchadeclarativesemanticsisgivenbymappingthesymbolicexpressionsinto(anabstractionof)therelevantsegmentofthe\world.Inaddition,oneneedsanotionof\truth,whichmakesitpossibletodeterminewhichofthesymbolicstatementsholdinthecurrent\world.Ontheotherhand,oneneedsan\intelligentretrievalmechanism,whichisabletorealizetheabove-mentionedgeneralproblemsolvingcomponent.ThismechanismshouldallowtoretrieveknowledgethatisonlyimplicitlypresentintheKB,thatis,itshouldbeabletodeduceimplicitlyrepresentedknowledgefromtheexplicitknowledge.Inouraboveexample,theinformationthattwonodesareconnectedisimplicitknowledge,whichmustbededucedfromtheexplicitknowledge(i.e.,theinformationaboutdirectlyconnectednodesandtheHornclausesspecifyingthemeaningof\connected)withthe